Ali je mogoče ustvariti naključna števila, če si ne zaupamo? 1. del

Pozdravljeni, Habr!

V tem članku bom govoril o ustvarjanju psevdo-naključnih števil s strani udeležencev, ki si ne zaupajo. Kot bomo videli spodaj, je izvedba "skoraj" dobrega generatorja precej preprosta, zelo dobrega pa je težko.

Zakaj bi bilo potrebno ustvarjati naključna števila med udeleženci, ki si ne zaupajo? Eno področje uporabe so decentralizirane aplikacije. Na primer, aplikacija, ki sprejme stavo od udeleženca in podvoji znesek z 49-odstotno verjetnostjo ali odvzame z 51-odstotno verjetnostjo, bo delovala le, če lahko nepristransko prejme naključno število. Če lahko napadalec vpliva na izid generatorja naključnih števil in celo nekoliko poveča svojo možnost prejema izplačila v aplikaciji, jo bo zlahka opustošil.

Ko oblikujemo protokol za distribuirano generiranje naključnih števil, želimo, da ima tri lastnosti:

1. Mora biti nepristranski. Z drugimi besedami, noben udeleženec ne sme na noben način vplivati ​​na rezultat generatorja naključnih števil.

2. Mora biti nepredvidljiv. Z drugimi besedami, noben udeleženec ne bi smel predvideti, katero število bo ustvarjeno (ali sklepati o kateri koli njegovi lastnosti), preden je ustvarjeno.

3. Protokol mora biti sposoben preživetja, torej odporen na to, da se določen odstotek udeležencev izključi iz omrežja ali namerno poskuša zaustaviti protokol.

V tem članku si bomo ogledali dva pristopa: RANDAO + VDF in pristop kod za brisanje. V naslednjem delu bomo podrobno preučili pristop, ki temelji na mejnih podpisih.

Najprej pa si poglejmo preprost in pogosto uporabljen algoritem, ki je izvedljiv, nepredvidljiv, a pristranski.

RANDAO

RANDAO je zelo preprost in zato precej pogosto uporabljen pristop za generiranje naključnosti. Vsi udeleženci omrežja najprej lokalno izberejo psevdonaključno številko, nato vsak udeleženec pošlje zgoščeno vrednost izbrane številke. Nato udeleženci izmenično razkrijejo svoje izbrane številke in izvedejo operacijo XOR nad razkritimi številkami, rezultat te operacije pa postane rezultat protokola.

Korak objave zgoščenih vrednosti pred razkritjem številk je potreben, da napadalec ne more izbrati svoje številke, potem ko je videl številke drugih udeležencev. To bi mu omogočilo, da tako rekoč sam določi izhod generatorja naključnih števil.

Med potekom protokola morajo udeleženci dvakrat priti do skupne odločitve (tako imenovanega soglasja): kdaj začeti razkrivati ​​izbrana števila in s tem prenehati sprejemati zgoščene vrednosti in kdaj prenehati sprejemati izbrana števila in računati nastalo naključno število. število. Sprejemanje takšnih odločitev med udeleženci, ki si ne zaupajo, samo po sebi ni lahka naloga in k njej se bomo vrnili v naslednjih člankih, v tem članku pa bomo predvidevali, da nam je tak algoritem soglasja na voljo.

Katere lastnosti, ki smo jih opisali zgoraj, ima RANDAO? Je nepredvidljiv, ima enako vitalnost kot temeljni protokol soglasja, vendar je pristranski. Natančneje, napadalec lahko opazuje omrežje in potem, ko drugi udeleženci razkrijejo svoje številke, lahko izračuna njihov XOR in se odloči, ali bo razkril svojo številko ali ne, da bi vplival na izid. Čeprav to napadalcu preprečuje, da bi samostojno določil izhod generatorja naključnih števil, mu še vedno daje 1 bit vpliva. In če napadalci nadzorujejo več udeležencev, bo število bitov, ki jih nadzorujejo, enako številu udeležencev pod njihovim nadzorom.

Vpliv napadalcev se lahko močno zmanjša, če se od udeležencev zahteva, da razkrijejo številke po vrstnem redu. Nato bo napadalec lahko vplival na izid le, če bo odprt zadnji. Čeprav je vpliv bistveno manjši, je algoritem še vedno pristranski.

RANDAO+VDF

Eden od načinov, kako narediti RANDAO nepristranski, je tale: ko so razkrita vsa števila in je XOR izračunan, se njegov rezultat vnese v vhod funkcije, ki traja zelo dolgo za izračun, vendar vam omogoča, da preverite pravilnost izračun zelo hitro.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Ta funkcija se imenuje Verifiable Delay Function ali VDF. Če izračun končnega rezultata traja dlje kot faza razkritja številke, potem napadalec ne bo mogel predvideti učinka prikaza ali skrivanja svoje številke, zato bo izgubil možnost vplivanja na rezultat.

Razviti dobre VDF je izjemno težko. V zadnjem času je bilo več prebojev, npr. ta и to, zaradi česar je bil VDF bolj praktičen v praksi, Ethereum 2.0 pa namerava dolgoročno uporabljati RANDAO z VDF kot vir naključnih števil. Poleg dejstva, da je ta pristop nepredvidljiv in nepristranski, ima dodatno prednost, da je izvedljiv, če sta v omrežju na voljo vsaj dva udeleženca (ob predpostavki, da je uporabljeni soglasni protokol izvedljiv pri tako majhnem številu udeležencev).

Največji izziv tega pristopa je nastavitev VDF tako, da tudi udeleženec z zelo drago specializirano strojno opremo ne bo mogel izračunati VDF pred koncem faze odkrivanja. V idealnem primeru bi moral imeti algoritem celo precejšnjo varnostno rezervo, recimo 10x. Spodnja slika prikazuje napad igralca, ki ima specializiran ASIC, ki mu omogoča, da zažene VDF hitreje od časa, dodeljenega za razkritje potrditve RANDAO. Takšen udeleženec lahko še vedno izračuna končni rezultat s svojo številko ali ne, nato pa na podlagi izračuna izbere, ali jo bo prikazal ali ne.

Za zgoraj omenjeno družino VDF je zmogljivost namenskega ASIC lahko 100+-krat višja od običajne strojne opreme. Torej, če faza uvajanja traja 10 sekund, mora VDF, izračunan na takšnem ASIC-u, trajati več kot 100 sekund, da ima 10-kratno varnostno rezervo, zato mora isti VDF, izračunan na običajni strojni opremi, trajati 100x 100 sekund = ~3 ure.

Fundacija Ethereum namerava to težavo rešiti z ustvarjanjem lastnih javno dostopnih brezplačnih ASIC-jev. Ko se to zgodi, lahko tudi vsi drugi protokoli izkoristijo to tehnologijo, vendar do takrat pristop RANDAO+VDF ne bo tako izvedljiv za protokole, ki ne morejo vlagati v razvoj lastnih ASIC-jev.

Veliko člankov, videoposnetkov in drugih informacij o VDF je bilo zbranih na to spletno mesto.

Uporabljamo kode za brisanje

V tem razdelku si bomo ogledali protokol za generiranje naključnih števil, ki uporablja brisanje kod. Lahko prenese do ⅓ napadalcev, medtem ko ostane sposoben preživetja, in dovoli do ⅔ napadalcem, da obstajajo, preden lahko napovejo ali vplivajo na izid.

Glavna ideja protokola je naslednja. Za poenostavitev predpostavimo, da je natanko 100 udeležencev. Predpostavimo tudi, da imajo vsi udeleženci lokalno nek zasebni ključ in da so javni ključi vseh udeležencev znani vsem udeležencem:

1. Vsak udeleženec lokalno pride z dolgim ​​nizom, ga razdeli na 67 delov, ustvari kode za izbris, da pridobi 100 deležev, tako da je poljubnih 67 dovolj za obnovitev niza, dodeli vsakega od 100 deležev enemu od udeležencev in jih šifrira z javni ključ istega udeleženca. Vse kodirane skupne rabe so nato objavljene.

2. Udeleženci uporabljajo nekakšno soglasje, da dosežejo dogovor o kodiranih nizih določenih 67 udeležencev.

3. Ko je doseženo soglasje, vsak udeleženec vzame kodirane deleže v vsakem od 67 nizov, šifriranih s svojim javnim ključem, dešifrira vse take deleže in objavi vse take dešifrirane deleže.

4. Ko 67 udeležencev zaključi korak (3), je mogoče vse dogovorjene nize popolnoma dekodirati in rekonstruirati zaradi lastnosti kod za izbris, končno število pa je mogoče dobiti kot XOR začetnih vrstic, s katerimi so udeleženci začeli v (1) .

Ta protokol se lahko pokaže kot nepristranski in nepredvidljiv. Nastalo naključno število se določi po doseženem soglasju, vendar ni znano nikomur, dokler ⅔ udeležencev ne dekodira delov, šifriranih z njihovim javnim ključem. Tako je naključno število določeno, preden so objavljene informacije, ki zadostujejo za njegovo rekonstrukcijo.

Kaj se zgodi, če v koraku (1) eden od udeležencev drugim udeležencem pošlje kodirane skupne rabe, ki niso pravilna koda za izbris za neki niz? Brez dodatnih sprememb različni udeleženci bodisi sploh ne bodo mogli obnoviti niza ali pa bodo obnovili različne nize, zaradi česar bodo različni udeleženci prejeli različno naključno število. Da bi to preprečili, lahko naredite naslednje: vsak udeleženec poleg kodiranih deležev tudi izračuna Merklovo drevo vse take deleže in vsakemu udeležencu pošlje sam kodirani delež in koren drevesa merkle ter dokazilo o vključitvi deleža v drevo merkle. V soglasju v koraku (2) se udeleženci potem ne strinjajo samo o naboru naborov, ampak na naboru specifičnih korenin takih dreves (če je nek udeleženec odstopal od protokola in različnim udeležencem poslal različne korenine drevesa Merkle, in dva taka korena sta prikazana med soglasjem, njegova vrstica ni vključena v niz rezultatov). Kot rezultat konsenza bomo imeli 67 kodiranih vrstic in pripadajočih korenin merklovega drevesa, tako da je vsaj 67 udeležencev (ne nujno istih, ki so predlagali ustrezne vrstice), ki imajo za vsako od 67 vrstic sporočilo z deležem kode za izbris in dokaz o pojavu njihovega deleža v ustreznem drevesu je zbledel.

Ko v koraku (4) udeleženec dešifrira 67 taktov za določeno struno in poskuša iz njih rekonstruirati originalno struno, je možna ena od možnosti:

1. Niz se obnovi in ​​če se nato znova kodira z izbrisom in se Merklovo drevo izračuna za lokalno izračunane deleže, koren sovpada s tistim, o katerem je bilo doseženo soglasje.

2. Vrstica je obnovljena, vendar se lokalno izračunani koren ne ujema s tistim, pri katerem je bilo doseženo soglasje.

3. Vrstica ni obnovljena.

Enostavno je pokazati, da če se možnost (1) zgodi za vsaj enega udeleženca zgoraj, potem se možnost (1) zgodi za vse udeležence, in obratno, če se možnost (2) ali (3) zgodi za vsaj enega udeleženca, potem za vse udeležence se zgodi možnost (2) ali (3). Tako jo bodo za vsako vrstico v nizu vsi udeleženci uspešno obnovili ali pa je vsem udeležencem ne bo uspelo obnoviti. Nastalo naključno število je nato XOR samo tistih vrstic, ki so jih udeleženci lahko obnovili.

Mejni podpisi

Drug pristop k naključnosti je uporaba tako imenovanih podpisov praga BLS. Generator naključnih števil, ki temelji na mejnih podpisih, ima popolnoma enaka jamstva kot algoritem, ki temelji na kodi za brisanje, opisan zgoraj, vendar ima znatno nižje asimptotično število sporočil, poslanih po omrežju za vsako generirano število.

Podpisi BLS so zasnova, ki omogoča več udeležencem, da ustvarijo en skupen podpis za sporočilo. Ti podpisi se pogosto uporabljajo za prihranek prostora in pasovne širine, saj ni treba poslati več podpisov. 

Običajna aplikacija za podpise BLS v protokolih blockchain je poleg generiranja naključnih števil tudi podpisovanje blokov v protokolih BFT. Recimo, da bloke ustvari 100 udeležencev, blok pa velja za dokončnega, če ga podpiše 67 udeležencev. Vsi lahko predložijo svoje dele podpisa BLS in uporabijo algoritem soglasja, da se dogovorijo o 67 od njih in jih nato združijo v en podpis BLS. Katerih koli 67 (ali več) delov je mogoče uporabiti za ustvarjanje končnega podpisa, kar bo odvisno od tega, kateri 67 podpisov je bilo združenih in se zato lahko razlikuje, čeprav bodo različne izbire 67 udeležencev ustvarile drugačen podpis, vsak tak podpis bo veljaven podpis za blok. Preostali udeleženci morajo nato po omrežju prejeti in preveriti samo en podpis na blok, namesto 67, kar bistveno zmanjša obremenitev omrežja.

Izkazalo se je, da če so zasebni ključi, ki jih udeleženci uporabljajo, ustvarjeni na določen način, bo končni podpis enak, ne glede na to, katerih 67 podpisov (ali več, vendar ne manj) je zbranih. To se lahko uporabi kot vir naključnosti: udeleženci se najprej dogovorijo o sporočilu, ki ga bodo podpisali (to je lahko rezultat RANDAO ali samo zgoščena vrednost zadnjega bloka, ni pomembno, če se vsakič spremeni in je dosleden) in zanj ustvarite podpis BLS. Rezultat generiranja bo nepredvidljiv, dokler 67 udeležencev ne zagotovi svojih delov, nato pa je rezultat že vnaprej določen in ne more biti odvisen od dejanj katerega koli udeleženca.

Ta pristop k naključnosti je izvedljiv, dokler vsaj ⅔ udeležencev na spletu upošteva protokol, in je nepristranski in nepredvidljiv, dokler vsaj ⅓ udeležencev upošteva protokol. Pomembno je omeniti, da lahko napadalec, ki nadzoruje več kot ⅓, vendar manj kot ⅔ udeležencev, ustavi protokol, vendar ne more predvideti ali vplivati ​​na njegov rezultat.

Sami pragovi podpisov so zelo zanimiva tema. V drugem delu članka bomo podrobno analizirali, kako delujejo in kako natančno je treba generirati ključe udeležencev, da se lahko podpisi praga uporabljajo kot generator naključnih števil.

Na koncu

Ta članek je prvi v nizu člankov o tehničnih blogih NEAR. NEAR je blockchain protokol in platforma za razvoj decentraliziranih aplikacij s poudarkom na enostavnosti razvoja in enostavni uporabi za končne uporabnike.

Koda protokola je odprta, naša implementacija je napisana v Rustu, lahko jo najdete tukaj.

Ogledate si lahko, kako izgleda razvoj za NEAR, in preizkusite v spletnem IDE tukaj.

Vse novice v ruščini lahko spremljate na skupina telegramov in skupina na VKontakte, v angleščini pa v uradnem twitter.

Se vidiva kmalu!

Vir: www.habr.com