Tilfeldige tall og desentraliserte nettverk: implementeringer

Innledning

function getAbsolutelyRandomNumer() {
        return 4; // returns absolutely random number!
}

Som med konseptet med absolutt sikker kryptering fra kryptografi, prÞver faktiske protokoller "Publicly Verifiable Random Beacon" (heretter PVRB) bare Ä nÊrme seg den ideelle ordningen, siden den ikke er anvendbar i ren form i faktiske nettverk: man mÄ bli enige om en enkelt bit, det mÄ vÊre mange runder, og alle meldinger mÄ vÊre perfekt raske og alltid bli levert. SelvfÞlgelig er ikke dette tilfelle i faktiske nettverk. Derfor, nÄr man designer PVRB for spesifikke oppgaver i moderne blokkjeder, oppstÄr det, i tillegg til umuligheten av Ä kontrollere det tilfeldige tallet og kryptografisk sikkerhet, mange rent arkitektoniske og tekniske problemer.

Selve blokkjeden fungerer som en kommunikasjonsmiljĂž for PVRB, hvor meldinger = transaksjoner. Dette gjĂžr det mulig Ă„ delvis abstrahere fra nettverksproblemer, manglende levering av meldinger, og problemer med mellomprogramvare — alle disse risikoene pĂ„tar seg det desentraliserte nettverket, og dens stĂžrste verdi for PVRB er umuligheten av Ă„ tilbakekalle eller Ăždelegge en allerede sendt transaksjon — dette hindrer deltakerne i Ă„ trekke seg fra protokollen, med mindre de har gjennomfĂžrt et vellykket angrep pĂ„ konsensus. Et slikt sikkerhetsnivĂ„ er akseptabelt, derfor mĂ„ PVRB vĂŠre motstandsdyktig mot samarbeid mellom deltakerne i samme grad som hovedkjeden i blokkjeden. Dette antyder ogsĂ„ at PVRB mĂ„ vĂŠre en del av konsensus, hvis nettverket har blitt enige om hovedkjeden med blokker, la oss si at de samtidig blir enige om et eneste rettferdig resultat av tilfeldighet. Eller, PVRB er bare en selvstendig protokoll, implementert som et smartkontrakt, som fungerer asynkront i forhold til blokkjeden og blokkene. Begge metodene har sine egne fordeler og ulemper, og valget mellom dem er ekstremt udelt.

To mÄter Ä implementere PVRB pÄ

Vi vil beskrive to varianter for implementering av PVRB mer detaljert — en standalone versjon som fungerer med en smarte kontrakt uavhengig av blokkjeden, og en consensus-integrated som er integrert i protokollen der nettverket avtaler om blokkserien og transaksjoner som skal inkluderes. I alle tilfeller vil jeg ha i mente de populére blokkjede-motorene: Ethereum, EOS, og lignende systemer for smartkontrakter.

Standalone contract

I denne varianten er PVRB en smarte kontrakt som mottar transaksjoner fra random-producerne (RP), behandler dem, kombinerer resultatene og kommer til en viss verdi som enhver bruker kan hente fra denne kontrakten. Denne verdien trenger ikke Ă„ lagres direkte i kontrakten, men kan vĂŠre representert ved data som deterministisk kan gi ett og bare ett resultat av det tilfeldig genererte tallet. I dette systemet er RP brukerne av blokkjeden, og hvem som helst kan delta i prosessen med generering.

Standalone-contract alternativet har sine fordeler:

  • portabilitet (kontraktene kan flyttes fra en blokkjede til en annen)
  • enkelhet i implementering og testing (kontraktene er enkle Ă„ skrive og teste)
  • praktisk for implementering av Ăžkonomiske ordninger (lett Ă„ lage sin egen token som klart oppfyller PVRB-formĂ„lene)
  • muligheten for Ă„ starte i eksisterende blokkjeder

Det har ogsÄ ulemper:

  • strenge begrensninger pĂ„ ressurser under beregningene, volumet av transaksjoner og lagring (enkelt sagt cpu/mem/io)
  • begrensninger for operasjoner innen kontrakten (ikke alle instruksjoner er tilgjengelige, vanskelig Ă„ koble eksterne biblioteker til)
  • umuligheten av Ă„ organisere meldingsutveksling raskere enn transaksjoner blir inkludert i blokkjeden

Dette alternativet er egnet for implementering av PVRB som mÄ starte i et eksisterende nettverk, uten komplisert kryptografi og som ikke krever mange interaksjoner.

Consensus-integrated

I denne varianten er PVRB implementert i koden til blockchain-noden, enten innebygd eller som jobber parallelt med meldingsutvekslingen mellom blockchain-noder. Resultatene av protokollen skrives direkte inn i de produserte blokkene, og protokollmeldinger sendes over P2P-nettverket mellom nodene. Siden protokollen har resultater som mĂ„ skrives inn i blokkene, mĂ„ nettverket oppnĂ„ konsensus om dem. Det betyr at PVRB-meldinger, som transaksjoner, mĂ„ valideres av nodene og inkluderes i blokkene, slik at enhver deltaker i nettverket kan validere at PVRB-protokollen blir overholdt. Dette fĂžrer oss automatisk til en Ă„penbar lĂžsning — dersom nettverket blir enige om konsensus angĂ„ende blokken og transaksjonene i den, mĂ„ PVRB vĂŠre en del av konsensus og ikke en separat protokoll. Ellers kan en situasjon oppstĂ„ der blokken er gyldig fra et konsensussynspunkt, men PVRB-protokollen ikke er overholdt, og fra PVRB sitt stĂ„sted kan ikke blokken aksepteres. SĂ„ hvis det valgte alternativet er “konsensus-integrert,” blir PVRB en viktig del av konsensus.

NĂ„r man beskriver implementeringer av PVRB pĂ„ konsensusnivĂ„ i nettverket, mĂ„ man under ingen omstendigheter unngĂ„ spĂžrsmĂ„l om finalitet. Finalitet er en mekanisme som brukes i deterministiske konsensus, som fastsetter en blokk (og kjeden som fĂžrer til den) som er endelig og aldri vil bli kastet ut, selv om det oppstĂ„r en parallell fork. For eksempel, i Bitcoin finnes det ingen slik mekanisme — hvis man publiserer en kjede med stĂžrre kompleksitet, vil den erstatte enhver mindre kompleks kjede, uavhengig av kjedenes lengde. Og i EOS, for eksempel, er de sĂ„kalte Last Irreversible Blocks (LIB) de som er endelige, som dukker opp i gjennomsnitt hver 432 blokk (12*21 + 12*15, pre-vote + pre-commit). Denne prosessen er i hovedsak venting pĂ„ 2/3 av signaturene fra block-producers (BP). NĂ„r det kommer fork som er eldre enn den siste LIB, blir de bare forkastet. Denne mekanismen gjĂžr det mulig Ă„ garantere at en transaksjon er inkludert i blokkjedens, og aldri vil bli rullet tilbake, uansett hvilke ressurser angriperen mĂ„tte ha. OgsĂ„, finalitetsblokker er blokkene signert av 2/3 BP i Hyperledger, Tendermint og andre pBFT-baserte konsensus. Dessuten gir det mening Ă„ lage en protokoll for Ă„ sikre finalitet over konsensus, ettersom den kan operere asynkront med produksjon og publisering av blokker. Her er et godt article om finalitet i Ethereum.

Finalitet er ekstremt viktig for brukere som uten det kan bli ofre for "double spend" angrep, nĂ„r BP "holder tilbake" blokker og publiserer dem etter at nettverket har "sett" en god transaksjon. Uten finalitet kan den publiserte hardgaflen erstatte blokken med den "gode" transaksjonen med en annen fra den "dĂ„rlige" hardgaflen, der de samme midlene overfĂžres til angriperens adresse. NĂ„r det gjelder PVRB, strammes kravene til finalitet ytterligere, ettersom bygging av hardgafler for PVRB betyr at angriperen kan forberede flere former for tilfeldig tall med mĂ„l om Ă„ publisere det mest fordelaktige for seg selv, og begrense tiden for et mulig angrep — en god lĂžsning.

Derfor er den beste lĂžsningen Ă„ kombinere PVRB og finalitet i ett protokoll — da er den finaliserte blokken = finalisert tilfeldighet, og det er nettopp det vi Ăžnsker Ă„ oppnĂ„. NĂ„ vil spillerne fĂ„ garantert tilfeldig tall innen N sekunder, og de kan vĂŠre sikre pĂ„ at det ikke er mulig Ă„ rulle det tilbake eller spille det pĂ„ nytt.

Alternativet med consensus-integrated er bra:

  • Muligheten for asynkron implementering i forhold til blokkproduksjon — blokkene produseres som vanlig, men parallelt med dette kan PVRB-protokollen kjĂžre, som produserer tilfeldig tall ikke hver blokk.
  • Muligheten for Ă„ implementere selv tung kryptografi, uten begrensninger pĂ„lagt av smarte kontrakter.
  • Muligheten til Ă„ organisere meldingsutveksling raskere enn transaksjoner inkluderes i blokkjeden; for eksempel kan en del av protokollen kjĂžre mellom noder uten Ă„ spre meldinger over nettet.

Det har ogsÄ ulemper:

  • Vansker ved testing og utvikling — man mĂ„ emulere nettverksfeil, tapte noder, hardgafler i nettverket.
  • Feil i implementeringen krever en hardgafler i nettverket.

Begge implementeringsmetodene for PVRB har rett til Ä eksistere, men implementering pÄ smarte kontrakter i moderne blokkjeder er fortsatt ganske sterkt begrenset i beregningsressurser, og enhver overgang til seriÞs kryptografi er ofte ganske enkelt umulig. Og seriÞs kryptografi vil vi trenge, som vil bli demonstrert senere. Selv om dette problemet Äpenbart er av midlertidig karakter, er seriÞs kryptografi i kontrakter nÞdvendig for Ä lÞse mange oppgaver, og gradvis blir det mer tilgjengelig (for eksempel systemkontrakter for zkSNARKs i Ethereum).

Blockchain, which provides a transparent and reliable communication channel for protocols, does not do this for free. Any decentralized protocol must consider the possibility of Sybil attacks, as any action can be executed by colluding forces of multiple accounts, so it is necessary to account for the attackers' capabilities to create an arbitrary number of protocol participants acting in collusion during the design.

PVRB and block variables.

I wasn’t lying when I said that there has not yet been a good PVRB, tested by numerous gambling applications, implemented in blockchains. So where does the abundance of gambling applications in Ethereum and EOS come from? I am just as surprised as you are; how did they manage to extract so many 'resilient' randoms in a completely deterministic environment?

The favorite way to generate randomness in blockchain is to take some 'unpredictable' information from a block and use it to create randomness — simply by hashing one or more values. There is a good article on the problems with such schemes. her. One can take any of the 'unpredictable' values in a block, such as the block hash, the number of transactions, network difficulty, and other unknown values in advance. Then hash them, one or more, and theoretically, a genuine random should be produced. You can even add in the whitepaper that your scheme is 'post-quantum secure' (since there are quantum-proof hash functions :)).

But even post-quantum secure hashes are not enough, unfortunately. The key lies in the requirements for PVRB, which I will remind you of from the previous article:

  1. The result must have provably uniform distribution, i.e., be based on provably secure cryptography.
  2. It is impossible to control any of the bits of the result. Consequently, the result cannot be predicted in advance.
  3. The protocol generation cannot be sabotaged by not participating in the protocol or by overloading the network with attacking messages.
  4. All of the above must be resilient to collusion from a permissible number of dishonest protocol participants (for example, 1/3 of the participants).

I dette tilfellet oppfylles bare krav 1, og 2 overholdes ikke. Ved Ä hash'e uforutsigbare verdier fra blokken vil vi fÄ en jevn fordeling og gode tilfeldigheter. Men BP har i det minste muligheten til Ä "publisere blokken eller ikke". Dermed kan BP som minimum velge mellom TO tilfeldigheter: "sin egen" og den som oppstÄr hvis noen andre offentliggjÞr blokken. BP kan pÄ forhÄnd "kikke" pÄ hva som vil skje hvis han publiserer blokken, og bare ta en beslutning om Ä gjÞre dette eller ikke. Dermed, for eksempel i "oddetall-eller-par" eller "rÞd/svart" i rulett, kan han publisere blokken bare hvis han ser at han vinner. Dette gjÞr ogsÄ strategien for Ä bruke, for eksempel, en hash av blokken "fra fremtiden" ubrukelig. I sÄ fall sier man at "det vil bli brukt en tilfeldighet som oppstÄr ved hashing av nÄvÊrende data og hash av fremtidig blokk med hÞyde, for eksempel N + 42, der N er nÄvÊrende hÞyde av blokken. Dette forsterker ordningen litt, men lar likevel BP, om enn i fremtiden, velge Ä holde tilbake blokken eller publisere den.

Programvaren til BP blir i denne sammenhengen mer kompleks, men ikke mye. Bare ved validering og inkludering av transaksjonen i blokken gÄr det en rask sjekk for Ä se om det blir gevinst, og muligens justering av ett parameter for transaksjonen for Ä oppnÄ hÞy sannsynlighet for gevinst. For Ä fange en smart BP er det praktisk talt umulig Ä ta initiativ til slike manipulasjoner, hver gang kan man bruke nye adresser, og vinne sakte men sikkert uten Ä vekke mistanke.

SÄ metoder som bruker informasjon fra blokken er ikke egnet som en universell implementering av PVRB. I en begrenset versjon, med restriksjoner pÄ innsatsstÞrrelser, begrensninger pÄ antall spillere og/eller KYC-registrering (for Ä ikke gi én spiller muligheten til Ä bruke flere adresser), kan disse ordningene fungere for smÄ spill, men ikke mer enn det.

PVRB og commit-reveal.

Greit, takk til hashing og i det minste relativ uforutsigbarhet av hash'en fra blokken og andre variabler. Hvis vi lĂžser front-running-problemet for minerne, burde vi kunne oppnĂ„ noe bedre. La oss ogsĂ„ legge til brukerne i dette systemet – de mĂ„ ogsĂ„ pĂ„virke tilfeldigheten: enhver ansatt i kundestĂžtte vil fortelle deg at det mest tilfeldige i IT-systemer er brukernes handlinger 🙂

En naiv ordning der brugerne blot sender tilfĂŠldige tal, og resultatet beregnes som f.eks. en hash af deres sum, er ikke praktisk. I dette tilfĂŠlde kan den sidste spiller, ved at vĂŠlge sin egen tilfĂŠldighed, kontrollere, hvilket resultat der opnĂ„s. Derfor bruges et meget udbredt mĂžnster kaldet commit-reveal. Deltagerne sender fĂžrst hashes af deres tilfĂŠldigheder (commits), og derefter afslĂžrer de selve tilfĂŠldighederne (reveals). Reveal-fasen begynder fĂžrst, efter at de nĂždvendige commits er indsamlet, sĂ„ deltagerne kan sende prĂŠcis den tilfĂŠldighed, hvis hash de tidligere har sendt. Nu kan vi kombinere alt dette med blokparametre, helst fra fremtiden (den tilfĂŠldighed kan kun kendes i en af de fremtidige blokke), og voila — tilfĂŠldigheden er klar! Nu pĂ„virker enhver spiller den resulterende tilfĂŠldighed og kan "vinde" over den ondsindede BP ved at dĂŠkke hans tilfĂŠldighed med sin egen, som ikke kendes pĂ„ forhĂ„nd... Desuden kan vi tilfĂžje beskyttelse mod sabotering af protokollen ved ikke at afslĂžre i reveal-fasen — simpelthen ved at krĂŠve, at der ved commit skal vedlĂŠgges et belĂžb til transaktionen — en depositum, som kun tilbagebetales ved reveal-processen. I dette tilfĂŠlde vil det vĂŠre ufordelagtigt at lave et commit og ikke lave et reveal.

Det var et godt forsÞg, og sÄdanne ordninger findes ogsÄ i spille DApp'er, men desvÊrre er det stadig ikke tilstrÊkkeligt. Nu kan resultatet pÄvirkes ikke kun af minerne, men ogsÄ af enhver deltager i protokollen. Det faktiske belÞb kan stadig kontrolleres, men med mindre variabilitet og for penge, men ligesom i tilfÊlde med minerne, hvis resultaterne fra lodtrÊkningen er mere vÊrdifulde end betalingen for deltagelse i PVRB-protokollen, kan random-produceren (RP) beslutte, om de vil lave et reveal og kan stadig vÊlge mellem mindst to muligheder for tilfÊldighed.
Der er dog opstÄet mulighed for at straffe dem, der laver et commit og ikke laver et reveal, og denne ordning vil ogsÄ vÊre nyttig. Dens enkelhed er en stor fordel - mere omfattende protokoller krÊver langt mere kraftfulde beregninger.

PVRB og deterministiske signaturer.

Det er en annen mĂ„te Ă„ fĂ„ RP til Ă„ gi et pseudotilfeldig tall som han ikke kan pĂ„virke, hvis han fĂ„r en «mal» - dette er en deterministisk signatur. En slik signatur er for eksempel RSA, og ikke ECDSA. Hvis RP har et nĂžkkelpar: RSA og ECDSA, og han signerer en viss verdi med sin private nĂžkkel, vil han i tilfellet RSA fĂ„ ÉN OG BARE ÉN signatur, mens i tilfellet ECDSA kan han generere et hvilket som helst antall forskjellige gyldige signaturer. Dette skjer fordi det under opprettelsen av ECDSA-signaturen brukes et tilfeldig tall som velges av signerende, og det kan velges som man Ăžnsker, noe som gir signeren muligheten til Ă„ velge en av flere signaturer. I RSA: «ett inngangsverdi» + «ett nĂžkkelpar» = «en signatur». Det er ikke mulig Ă„ forutsi hvilken signatur en annen RP vil fĂ„, derfor kan PVRB med deterministiske signaturer organiseres ved Ă„ kombinere RSA-signaturene fra flere deltakere som har signert den samme verdien. For eksempel - tidligere tilfeldig. I et slikt system spares det betydelig ressurser, da signaturene bĂ„de bekrefter korrekt oppfĂžrsel i henhold til protokollen og er en kilde til tilfeldighet.

Likevel, selv med deterministiske signaturer, er systemet fremdeles sÄrbart for problemet «den siste aktÞren». Den siste deltakeren kan fortsatt bestemme om han vil publisere signaturen eller ikke, og dermed kontrollere resultatet. Man kan forbedre systemet, legge til blokkhash-er, lage runder slik at resultatet pÄ forhÄnd ikke kan forutses, men alle disse tiltakene, selv med mange forbedringer, lÞser likevel ikke problemet med innflytelsen til én deltaker pÄ det kollektive resultatet i et usikkert miljÞ, og kan kun fungere under Þkonomiske og tidsmessige begrensninger. I tillegg er stÞrrelsen pÄ RSA-nÞkler (1024 og 2048 bit) ganske stor, mens stÞrrelsen for blokkjedetransaksjoner er en ekstremt viktig parameter. Det ser ut til at det ikke er mulig Ä lÞse problemet enkelt, sÄ vi gÄr videre.

PVRB og hemmelig deling av ordninger

I kryptografi finnes det ordninger som lar et nettverk bli enige om én og bare én verdi av PVRB, samtidig som disse ordningene er motstandsdyktige mot enhver ondsinnet handling fra deltakernes side. En nyttig protokoll Ä bli kjent med er Shamir's hemmelighetsdeling. Den brukes til Ä dele et hemmelighet (for eksempel en hemmelig nÞkkel) i flere deler og dele disse delene med N deltakere. Hemmeligheten deles slik at for Ä gjenopprette den, er det nok med M deler fra N, og det kan vÊre hvilken som helst M deler. For Ä forklare det enkelt, sÄ bytter deltakerne punkter pÄ grafen til en ukjent funksjon, og etter Ä ha mottatt M punkter, kan hele funksjonen gjenopprettes.
En god forklaring finnes i wiki og det er nyttig Ä leke med det praktisk for Ä fÄ protokollen til Ä sitte i hodet demo siden.

Hvis FSSS (Fiat-Shamir Secret Sharing) ordningen kunne brukes i sin reneste form - ville det vĂŠrt en uknuselig PVRB. I det enkleste tilfellet kan protokollen se slik ut:

  • Hver deltaker genererer sin egen tilfeldige tall og deler ut andeler fra den til de andre deltakerne.
  • Hver deltaker avdekker sin del av andelene fra de andre deltakerne.
  • Hvis deltakeren har samlet inn mer enn M andeler, kan dette deltakerens tall beregnes, og det vil vĂŠre unikt, uansett hvilken kombinasjon av deltakere som blir avslĂžrt.
  • Kombinasjonen av de avdekkede tilfeldige tallene utgjĂžr den Ăžnskede PVRB.

Her pÄvirker en enkelt deltaker ikke resultatene av protokollen, unntatt i tilfeller der det kun avhenger av dem for Ä oppnÄ threshold for avslÞring av den tilfeldige tall. Derfor, med tilstrekkelig andel av deltakerne som fÞlger protokollen og tilgjengelige RP, fungerer denne protokollen og oppfyller kravene til kryptografisk sikkerhet, og er motstandsdyktig mot problemet med "siste aktÞr".

Dette kunne vÊrt det ideelle tilfellet, denne PVRB-ordningen basert pÄ Fiat-Shamir hemmelighetsdeling er beskrevet, for eksempel i denne artikkelen. Men, som nevnt tidligere, hvis man prÞver Ä bruke den direkte i blockchain, oppstÄr det allerede tekniske begrensninger. Her er et eksempel pÄ en testimplementering av protokollen i EOS smartkontrakt og dens mest viktige del - verifisering av avdekket andel fra deltakeren: koden. Koden viser at valideringen av proof krever flere skalar multiplikasjoner, og tallene som brukes er veldig store. Det er viktig Ä forstÄ at i blokkjedene skjer verifiseringen pÄ det tidspunktet nÄr block-producer prosesserer transaksjonen, og enhver deltaker mÄ lett kunne verifisere protokollens korrekthet, sÄ kravene til hastigheten pÄ verifiseringsfunksjonen er svÊrt strenge. Denne versjonen viste seg Ä vÊre ubrukelig, da verifiseringen ikke var innenfor transaksjonsgrensen (0,5 sek).

Effektiviteten av verifisering er et av de viktigste kravene for bruk av i prinsippet enhver avansert kryptografisk ordning i blokkjedene. Oppretting av proof, forberedelse av meldinger — disse prosedyrene kan flyttes off-chain og utfĂžres pĂ„ hĂžyytelses datamaskiner, men det gĂ„r ikke an Ă„ omgĂ„ verifiseringen — dette er et annet viktig krav til PVRB.

PVRB og threshold-signaturer

Etter Ă„ ha blitt kjent med ordningen for secret sharing, har vi Ă„pnet en hel klasse protokoller samlet under nĂžkkelordet “threshold”. NĂ„r M ĂŠrlige deltakere fra N kreves for Ă„ avdekke viss informasjon, og settet av ĂŠrlige deltakere kan vĂŠre en godtykkelig delmengde av N, snakker vi om “threshold”-ordninger. Disse lar oss hĂ„ndtere problemet med “siste aktĂžr”, nĂ„ hvis den angripende parten ikke avdekker sin del av hemmeligheten, vil en annen ĂŠrlig deltaker gjĂžre det. Disse ordningene tillater Ă„ bli enige om ett og bare ett verdifullt resultat, selv med sabotasje av protokollen fra noen deltakere.

Kombinasjonen av deterministiske signaturer og threshold-ordninger har gjort det mulig Ă„ utvikle en svĂŠrt praktisk og lovende ordning for implementering av PVRB — det er deterministiske threshold-signaturer. Her article om ulike anvendelser av threshold-signaturer, og her er enda en god longread fra Dash.

I den siste artikkelen beskrives BLS-signaturer (BLS stĂ„r for Boneh-Lynn-Shacham, her en artikkel som har en veldig viktig og ekstremt praktisk kvalitet for programmerere – offentlige, hemmelige, offentlige nĂžkler og BLS-signaturer kan kombineres med hverandre ved hjelp av enkle matematiske operasjoner, samtidig som kombinasjonene forblir gyldige nĂžkler og signaturer, noe som gjĂžr det enkelt Ă„ aggregere mange signaturer til Ă©n og mange offentlige nĂžkler til Ă©n. De har ogsĂ„ determinisme og gir det samme resultatet for de samme inputene. Takket vĂŠre denne egenskapen er BLS-signaturkombinasjoner gyldige nĂžkler, noe som gjĂžr det mulig Ă„ implementere en variant der M av N deltakere lager Ă©n og bare Ă©n signatur, som er deterministisk, offentlig verifiserbar, og uforutsigbar inntil den avslĂžres av den M-ende deltakeren.

I ordningen med threshold BLS-signaturer signerer hver deltaker med BLS noe (f.eks. forrige tilfeldig tall), og den samlede threshold-signaturen er det sĂžkte tilfeldige tallet. De kryptografiske egenskapene til BLS-signaturene tilfredsstiller kravene til kvalitetsrand, threshold-delen beskytter mot “last-actor”, og den unike kombinerbarheten av nĂžkler gjĂžr det mulig Ă„ implementere mange interessante algoritmer, som for eksempel effektivt aggregere meldinger fra protokollen.

SÄ hvis du bygger PVRB i blokkjeden din, vil du med stor sannsynlighet komme til ordningen BLS threshold-signaturer, som allerede brukes av flere prosjekter. For eksempel DFinity (her benchmark som implementerer ordningen, og here et eksempel pÄ implementering av verifiable secret sharing), eller Keep.network (her er deres random beacon yellowpaper, men eksempel smartkontrakten som betjener protokollen).

Implementering av PVRB

Dessverre ser vi fortsatt ikke et ferdig, implementert PVRB-protokoll i blokkjedene som har bevist sin sikkerhet og stabilitet. Selv om selve protokollene er klare, er det teknisk vanskelig Ă„ anvende dem pĂ„ eksisterende lĂžsninger. For sentraliserte systemer gir PVRB ikke mening, mens desentraliserte systemer er strengt begrenset i alle beregningsressurser: CPU, minne, lagring, I/O. Design av PVRB er en kombinasjon av forskjellige protokoller for Ă„ skape noe som tilfredsstiller alle krav til en livskraftig blokkjede. Én protokoll regner mer effektivt, men krever flere meldinger mellom RP, mens en annen krever svĂŠrt fĂ„ meldinger, men genereringen av et bevis kan vĂŠre en oppgave som tar ti minutter eller til og med timer.

Jeg vil liste opp faktorene du mÄ ta hensyn til nÄr du velger en kvalitets PVRB:

  • Kryptografisk styrke. Din PVRB mĂ„ vĂŠre strengt unbiasable, uten mulighet for Ă„ kontrollere en eneste bit. I noen ordninger er det ikke slik, sĂ„ involver en kryptograf.
  • Problemet med “last actor”. Din PVRB mĂ„ vĂŠre motstandsdyktig mot angrep hvor angriperen, som kontrollerer en eller flere RP, kan velge mellom to resultatalternativer.
  • Problemet med sabotasje av protokollen. Din PVRB mĂ„ vĂŠre motstandsdyktig mot angrep hvor angriperen, som kontrollerer en eller flere RP, bestemmer om det skal vĂŠre tilfeldig eller ikke, og kan garantere, enten med en bestemt sannsynlighet, pĂ„virke dette.
  • Problemet med antall meldinger. Dine RP mĂ„ sende minimum meldinger til blokkjedene og unngĂ„ synkrone handlinger, som situasjoner der “jeg sendte noen informasjon, venter pĂ„ svar fra en spesifikk deltaker”. I p2p-nettverk, spesielt nĂ„r de geografisk er spredt, bĂžr man ikke forvente raske svar.
  • Problemet med beregningskompleksitet. Verifisering av hvert trinn i PVRB on-chain mĂ„ vĂŠre ekstremt lett, da det utfĂžres av alle fullverdige klienter i nettverket. Hvis implementasjonen gjĂžres ved hjelp av smartkontrakt, mĂ„ kravene til hastighet vĂŠre svĂŠrt strenge.
  • Problemet med tilgjengelighet og liveness. Din PVRB bĂžr vĂŠre motstandsdyktig mot situasjoner der en del av nettverket har blitt utilgjengelig i en viss tid, og en del RP bare har sluttet Ă„ fungere.
  • Problemet med trusted setup og innledende distribusjon av nĂžkler.. Hvis PVRB-en din bruker en primĂŠr oppsettsprotokoll, er dette en helt annen stor og alvorlig historie. Her er eksempel. Hvis deltakerne mĂ„ informere hverandre om nĂžklene sine fĂžr de starter protokollen — er dette ogsĂ„ et problem, hvis deltakerlisten endres
  • Utviklingsproblemer. Tilgjengeligheten av biblioteker pĂ„ nĂždvendige sprĂ„k, deres sikkerhet og ytelse, offentlighet, komplekse tester osv.

For eksempel eksisterer det et betydelig problem med threshold BLS-signaturer — fĂžr de begynner Ă„ jobbe, mĂ„ deltakerne absolutt dele nĂžklene sine med hverandre og organisere en gruppe der threshold vil fungere. Dette betyr at man mĂ„ vente minst en runde med utveksling i et desentralisert nettverk, og ettersom den genererte tilfeldigheten, for eksempel, er nĂždvendig i spill, praktisk talt i sanntid, betyr dette at sabotasje av protokollen er mulig pĂ„ dette stadiet, og fordelene med threshold-skjemaet gĂ„r tapt. Dette problemet er allerede enklere enn det forrige, men krever fortsatt utviklingen av en egen prosedyre for dannelsen av threshold-grupper, som mĂ„ beskyttes Ăžkonomisk, gjennom innskudd og fratakelse av midler (slashing) fra deltakere som ikke fĂžlger protokollen. Dessuten passer ikke verifiseringen av BLS med et akseptabelt sikkerhetsnivĂ„, for eksempel, inn i en standardtransaksjon i EOS eller Ethereum — det er ganske enkelt ikke nok tid til verifisering. Koden for kontrakter er WebAssembly eller EVM, og kjĂžres av en virtuell maskin. Krypto-funksjonene er ikke implementert nativt (ennĂ„), og fungerer ti ganger tregere enn vanlige kryptobiblioteker. Mange protokoller er uegnet i henhold til kravene bare basert pĂ„ nĂžkkelvolumet, for eksempel 1024 og 2048 bit for RSA, 4-8 ganger mer enn en standard transaksjonssignatur i Bitcoin og Ethereum.

Det spiller ogsĂ„ en rolle at det finnes implementasjoner pĂ„ forskjellige programmeringssprĂ„k — som det er fĂ„ av, spesielt for nye protokoller. Alternativet med integrasjon i konsensus krever at man skriver protokollen pĂ„ plattformens sprĂ„k, sĂ„ man mĂ„ lete etter kode pĂ„ Go for geth, pĂ„ Rust for Parity, pĂ„ C++ for EOS. Kode pĂ„ JavaScript mĂ„ alle lete etter, og siden JavaScript og kryptografi ikke er spesielt nĂŠre venner, vil WebAssembly, som nĂ„ absolutt kan bli den neste viktige internettstandarden, hjelpe.

Konklusjon

Jeg hÄper at det i forrige artikkelen Jeg har klart Ä overbevise deg om at generering av tilfeldige tall pÄ blokkjeden er kritisk viktig for mange aspekter ved livet i desentraliserte nettverk, og med denne artikkelen har jeg vist at oppgaven er ekstremt ambisiÞs og ikke enkel, men gode lÞsninger er allerede tilgjengelige. Generelt kan den endelige designen av protokollen bare bli realisert etter omfattende testing som tar hensyn til alle aspekter fra oppsett til simulering av feil, sÄ du vil sannsynligvis ikke finne klare oppskrifter i whitepaperne til teamene eller i artikler, og vi vil i lÞpet av det neste Äret eller to ikke tÞrre Ä skrive 'gjÞr slik, det er helt riktig'.

SĂ„ langt, for vĂ„r PVRB i den utviklede blokkjeden Haya, har vi stoppet opp ved bruken av threshold BLS-signaturer, og planlegger Ă„ implementere PVRB pĂ„ konsensusnivĂ„, siden verifisering i smarte kontrakter med et akseptabelt sikkerhetsnivĂ„ fortsatt ikke er mulig. Det kan hende at vi bruker to ordninger: fĂžrst en kostbar secret sharing for Ă„ skape langvarig random_seed, og deretter bruke den som base for hĂžyfrekvent generering av tilfeldigheter ved hjelp av deterministiske threshold BLS-signaturer, eller vi kan begrense oss til bare en av ordningene. Å si pĂ„ forhĂ„nd hvordan protokollen vil vĂŠre, er dessverre umulig, det som gleder er at som i vitenskap, i ingeniĂžroppgaver er et negativt resultat ogsĂ„ et resultat, og hvert nytt forsĂžk pĂ„ Ă„ lĂžse oppgaven er et nytt skritt for forskningen til alle som jobber med problemet. For Ă„ tilfredsstille kravene fra virksomheten jobber vi med et konkret praktisk problem - Ă„ sikre spillapplikasjoner en pĂ„litelig kilde til entropi, derfor mĂ„ vi ogsĂ„ ta hensyn til selve blokkjeden, sĂŠrlig spĂžrsmĂ„l om kjede- og nettverks governance.

Og selv om vi fortsatt ikke ser en beviselig robust PVRB pÄ blokkjeder, som har vÊrt brukt lenge nok til Ä bestÄ tester fra ekte applikasjoner, flere revisjoner, belastninger, og selvfÞlgelig virkelige angrep, sÄ bekrefter antall mulige veier at lÞsningen finnes, og en av disse algoritmene vil til slutt lÞse problemet. Vi vil gjerne dele resultatene vÄre og takker andre team som ogsÄ jobber med dette problemet for artikler og kode som lar ingeniÞrer unngÄ Ä gjÞre de samme feilene pÄ nytt.

NĂ„r du mĂžter en programmerer som designer en desentralisert tilfeldighet, vĂŠr oppmerksom og omsorgsfull, og gi psykologisk hjelp om nĂždvendig 🙂

Kilde: habr.com

KjĂžp pĂ„litelig hosting for nettsteder med DDoS-beskyttelse, VPS VDS-servere đŸ”„ KjĂžp pĂ„litelig hosting for nettsteder med DDoS-beskyttelse, VPS VDS-servere | ProHoster