Kas me saame genereerida juhuslikke numbreid, kui me ei usalda üksteist? Osa 1

Tere, Habr!

Selles artikkel räägin tõenäosuslike numbrite genereerimisest osalejate poolt, kes üksteisesse ei usalda. Nagu allpool näeme, on "peaaegu" hea generaatori rakendamine suhteliselt lihtne, kuid väga hea loomine on keeruline.

Miks on üldse vajalik genereerida juhuslikke numbreid osalejatele, kes üksteisesse ei usalda? Üks rakenduse valdkondi on detsentraliseeritud rakendused. Näiteks rakendus, mis võtab osalejalt panuse ja kas kahekordistab summa 49% tõenäosusega või võtab 51%, töötab ainult siis, kui see suudab erapooletult saada juhuslikku numbrit. Kui küberkurjategija saab mõjutada juhuslike numbrite generaatori tulemust ja isegi vähesel määral suurendada oma võimalust saada rakenduses väljamakse, võib ta selle kergesti tühjaks teha.

Kui arendame jaotatud protokolli juhuslike numbrite genereerimiseks, soovime, et see omaks kolme omadust:

1. See peab olema erapooletu. Teisisõnu, ükski osaleja ei tohiks mingil viisil mõjutada juhuslike numbrite generaatori tulemust.

2. See peab olema ettearvamatu. Teisisõnu, ükski osaleja ei tohi suuta prognoosida, milline number genereeritakse (või sellega seotud omadusi) enne, kui see on genereeritud.

3. Protokoll peab olema elujõuline, st vastupidav sellele, et teatud protsent osalejatest lülitub välja või üritab teadlikult protokolli peatada.

Selles artiklis vaatleme kahte lähenemist: RANDAO + VDF ja lähenemine, mis põhineb kustutavatel koodidel. Järgmisel osal käsitleme üksikasjalikult lähenemist, mis põhineb piirimüügialustel.

Aga kõigepealt vaatame lihtsat ja sageli kasutatavat algoritmi, mis on elujõuline, ettearvamatu, kuid kallutatud.

RANDAO

RANDAO on väga lihtne ja seetõttu üsna sageli kasutatav lähenemine juhuslikkuse saamiseks. Kõik võrgu osalejad valivad kõigepealt kohalikult pseudojuhuslikku arvu, seejärel saadab iga osaleja valitud arvu räsimise. Seejärel avavad osalejad kordamööda oma valitud arvud ja teevad nende avatud arvudega XOR-operatsiooni, mille tulemusest saab protokolli tulemus.

Avaldamisprotsessi esimene samm enne numberite avamist on vajalik, et ründajal ei oleks võimalik valida oma numbrit pärast seda, kui ta on näinud teiste osalejate numbreid. See võimaldaks tal tegelikult üksi määrata juhuslike numbrite generaatori väljundi.

Protokolli käigus peavad osalejad kaks korda jõudma ühisotsusele (nn konsensusele): millal alustada valitud numbrite avamist ja seega lõpetada hashide vastuvõtt, ning millal lõpetada valitud numbrite vastuvõtt ja arvutada välja tulemuslik juhuslik number. Selliste otsuste vastuvõtmine osalejate vahel, kes üksteise usaldusväärsuses ei ole kindlad, on iseenesest keeruline ülesanne, ja me tuleme selle juurde tagasi tulevastes artiklites; praeguses artiklis eeldame, et selline konsensusalgoritm on meile kergesti kättesaadav.

Milliseid eelnevalt kirjeldatud omadusi omab RANDAO? See on ettearvamatu, omab sama elujõudu kui selle aluseks olev konsensusprotokoll, kuid on siiski kallutatud. Eriti kui ründaja jälgib võrku, võib ta pärast seda, kui teised osalejad oma numbreid avaldavad, arvutada nende XOR ja otsustada, kas oma numbri avaldamine mõjutab tulemust. Kuigi see ei luba ründajal üksi määrata juhusliku arvu generaatori väljundit, annab see siiski 1 bitti mõju. Kui ründajad kontrollivad mitmeid osalejaid, siis kontrollitavate bitide arv vastab nende halduses olevate osalejate arvule.

Ründajate mõju saab oluliselt vähendada, kui nõuda, et osalejad avalikustaksid numbreid järjekorras. Sellisel juhul saab ründaja mõjutada tulemust ainult juhul, kui ta avaldab oma numbri viimase. Kuigi mõju on oluliselt väiksem, on algoritm endiselt kallutatud.

RANDAO + VDF

Üks võimalus, kuidas muuta RANDAO erapooletuks, on järgmine: pärast kõigi numbrite avamist ja XOR-i arvutamist esitatakse selle tulemus funktsioonile, mille arvutamine võtab väga palju aega, kuid mis võimaldab arvutuse õigsust kiiresti kontrollida.

(vdf_output, vdf_proof) = VDF_compute(input) // see on väga aeglane
correct = VDF_verify(input, vdf_output, vdf_proof) // see on väga kiire

Sellist funktsiooni nimetatakse Verifiable Delay Function ehk VDF. Kui lõpptulemuse arvutamine võtab rohkem aega kui numbrite avamise etapp, siis ei saa kurjategija ennustada, milline mõju tagab tema numbri esitlemine või varjamine, seega kaotab ta võimaluse tulemusele mõjutada.

Heade VDF-de väljatöötamine on äärmiselt keeruline. Viimasel ajal on tehtud mitmeid läbimurdeid, näiteks seda ja see, mille, mis muudavad VDF rakendamise praktilisemaks ning Ethereum 2.0 plaanib pikaajalises perspektiivis kasutada RANDAO-d koos VDF-ga juhuslike numbrite allikana. Lisaks sellele, et see lähenemine on ettearvamatu ja erapooletu, on sellel ka täiendav eelis, mis seisneb elujõulisuses, kui vähemalt kaks osalist on võrku saadaval (tingimusel, et kasutatav konsensuse protokoll toimib nii väikeses osalejate arvus).

Selle lähenemise suurim keerukus seisneb VDF seadistamises nii, et isegi osaline, kellel on väga kallis spetsialiseeritud varustus, ei suudaks VDF-d arvutada enne avalikustamise etapi lõppu. Ideaalis peaks algoritmil olema isegi märkimisväärne varu, ütleme 10x. Alloleval joonisel on kujutatud osalise rünnakut, kellel on spetsialiseeritud ASIC, mis võimaldab tal käivitada VDF-d kiiremini kui aeg, mis on määratud RANDAO kinnituste avalikustamiseks. Selline osaline suudab ikkagi arvutada lõpptulemust, kasutades oma numbrit ja ilma selleta, ning seejärel oma arvutuste põhjal otsustada, kas seda näidata või mitte.

Käideldava VDF perekonna puhul võib spetsialiseeritud ASIC-i tootlikkus olla üle 100 korra suurem kui tavalise varustuse puhul. Seega, kui avalikustamise faas kestab 10 sekundit, peab sellisel ASIC-il arvutatud VDF võtma aega üle 100 sekundi, et olla 10-kordne ohutusvaru, ning seega, tavalise varustuse puhul arvutatud VDF peab kestma 100 x 100 sekundit = umbes 3 tundi.

Ethereum Foundation plaanib selle probleemi lahendada, luues oma tasuta avalikud ASIC-id. Kui see juhtub, saavad kõik muud protokollid samuti kasutada selle tehnoloogia eeliseid, kuid seni ei ole RANDAO + VDF lähenemine sama elujõuline protokollide jaoks, mis ei saa investeerida oma ASIC-ide arendamisse.

Palju artikleid, videoid ja muud teavet VDF kohta on kogutud sellel veebilehel.

Kasutame kustutuskoode

Selles jaotises vaatleme juhuslike arvude genereerimise protokolli, mis kasutab kustutuskoode. Ta suudab taluda kuni ⅓ pahatahtlikest osalejatest, jäädes samas elujõuliseks, ja lubab kuni ⅔ pahatahtlike olemasolu, enne kui nad suudavad ennustada või mõjutada tulemust.

Protokolli põhidee on järgmine. Lihtsuse huvides oletame, et selles on täpselt 100 osalejat. Eeldame ka, et kõigil osalejatel on kohalikult teatud privaatne võti ja kõigi osalejate avalikud võtmed on kõigile osalejatele teada.

1. Iga osaleja mõtleb kohalikult välja pika stringi, jagab selle 67 ossa, loob kustutuskoodid, et saada 100 osakest, nii et mistahes 67 on piisavad stringi taastamiseks, määrab iga 100 osakese ühele osalejale ja krüpteerib need selle osaleja avaliku võtmega. Seejärel avalikustatakse kõik kodeeritud osakesed.

2. Osalejad kasutavad mingit konsensust, et saavutada üksmeel konkreetsete 67 osaleja kodeeritud komplektide üle.

3. Kuna konsensus on saavutatud, võtab iga osaleja igast 67 komplektist oma avaliku võtme abil krüpteeritud osakesed, dekrüpteerib kõik sellised osakesed ja avalikustab kõik sellised dekrüpteeritud osakesed.

4. Kui 67 osalejat on läbinud etapi (3), saab kõik kokku lepitud komplektid täielikult dekodeerida ja taastada kustutamise koodide omaduste tõttu, ja lõplik number saab kätte XOR-iga algsetest ridadest, millega osalejad alustasid (1).

On võimalik näidata, et see protokoll on erapooletu ja ettearvamatu. Tulemuse juhuslik number määratletakse pärast konsensuse saavutamist, kuid ei ole veel kellelegi teada, kuni ⅔ osalejat ei dekodeeri osi, mis on nende avaliku võtmega krüpteeritud. Seega on juhuslik number määratletud enne, kui teave, mis on vajalik selle taastamiseks, avalikustatakse.

Mis toimub, kui etapis (1) saadab üks osalejatest teistele osalejatele kodeeritud osad, mis ei ole mõne rea korrektne kustutamise kood? Ilma täiendavate muudatusteta ei suuda erinevad osalejad kas täielikult taastada rida või taastavad nad erinevaid ridasid, mille tulemusena saavad erinevad osalejad erineva juhusliku numbri. Selle vältimiseks võib teha järgmist: iga osaleja, lisaks kodeeritud osadele, arvutab samuti Merkle puu kõiki selliseid osi, ja iga osalejale saadetakse nii kooditud osa kui ka Merkle puu juur ja tõend osa kuulumisest Merkle puusse. Konsensuse sammul (2) nõustuvad osalejad mitte ainult mitmete komplektide osas, vaid ka mitmete konkreetsete selliste puude juurte osas (kui mõni osaleja on protokollist kõrvale läinud ja on saatnud erinevad Merkle puu juured erinevatele osalejatele ning kaks sellist juurt […] konsensuse ajal on näidatud, ei kuulu tema rida lõplikku komplekti). Konsensuse tulemusena saame 67 kodeeritud rida ja vastavad Merkle puu juured, nii et on vähemalt 67 osalejat (mitte tingimata need, kes esitasid vastavad read), kelle jaoks iga 67 rea puhul on sõnum kustutuskoodi osaga ning tõend nende osade kuulumisest vastavasse Merkle puusse.

Kui sammul (4) osaleja dekrüpteerib 67 osa mõne rea jaoks ja püüab nende põhjal originaalset rida taastada, on võimalik üks järgmistest variantidest:

1. Rida taastatakse, ja kui seejärel kodeerida see uuesti kustutuskoodidega ning arvutada välja Merkle'i puu kohalike osade jaoks, siis juur vastab sellele, millega on saavutatud konsensus.

2. Rida taastatakse, kuid kohaliku arvutuse juur ei vasta sellele, millega on saavutatud konsensus.

3. Rida ei taastata.

On lihtne näidata, et kui vähemalt ühe osalise puhul juhtus variant (1), siis juhtub see kõigi osaliste puhul, ja vastupidi, kui vähemalt ühe osalise puhul juhtus variant (2) või (3), siis juhtus see kõigi osaliste puhul variant (2) või (3). Seeläbi, iga rida kogumis kas kõik osalised taastavad selle edukalt või ei suuda seda taastada. Siis on tulemuslik juhuslik number – see on XOR ainult nende ridade osas, mida osalised suudavad taastada.

Piirväärsete allkirjad

Teine lähenemine juhuslikkusele seisneb nii-öelda läveallkirjade BLS kasutamises. Läveallkirjadele põhinev juhusliku arvu generaator omab täpselt samu garantiisid nagu eespool kirjeldatud kustutuskoodide põhine algoritm, kuid sellel on tõeliselt madalam asymptootika võrreldes võrgus edastatavate sõnumite arvuga iga genereeritud arvu kohta.

BLS allkirjad on konstruktsioon, mis võimaldab mitmel osalejal luua ühe ühise allkirja sõnumile. Selliseid allkirju kasutatakse sageli ruumi ja ribalaiuse kokkuhoiu nimel, kuna need ei vaja mitme allkirja saatmist. 

BLS-allkirjade sagedane rakendamine plokiahela protokollides, lisaks juhuslike arvude genereerimisele, on BFT-protokollides plokkide allkirjastamine. Oletame, et 100 osalejat loovad blokke ja plokk loetakse lõplikuks, kui 67 neist allkirjastab selle. Kõik nad võivad esitada oma BLS-allkirja osi ja kasutada mingit konsensuse algoritmi, et koondada 67 neist, ning seejärel ühendada need üheks BLS-allkiri. Igasugused 67 (või enam) osa võivad olla kasutatud lõpliku allkirja loomisel, sõltudes sellest, millised konkreetsed 67 allkirja on ühendatud, ja seega võivad need erineda, kuid vaatamata sellele, et erinev valik 67 osalejat tekitab erineva allkirja, on iga selline allkiri ploki jaoks korrektne. Ülejäänud osalejatele piisab siis, kui nad saavad võrgus ja kontrollivad iga ploki kohta vaid ühte allkirja, mitte 67, mis oluliselt vähendab võrgu koormust.

Küsimus on selles, et kui osalejate kasutatavad privaatvõtmed genereeritakse teatud viisil, siis sõltumata sellest, kui palju allkirju (67 või rohkem, kuid mitte vähem) on kokku kogutud, saab tulemusena saadud allkiri olema sama. Seda saab kasutada juhuslikkuse allikana: osalejad lepivad esmalt kokku mingi sõnumi, mida nad allkirjastavad (see võib olla RANDAO väljund või lihtsalt viimase ploki hash, tegelikult ei ole sellel tähtsust, peaasi, et see iga kord muutuks ja oleks kooskõlastatud), ja loovad sellele BLS-allkirja. Generatsiooni tulemus on unpredictable kuni 67 osalejat esitavad oma osalused, ja pärast seda on väljund juba ette määratud ja ei saa sõltuda ühegi osaleja tegevusest.

Seda lähenemine juhuslikkusele on elujõuline, kui vähemalt ⅔ osalistest on online ja järgivad protokolli, ning on erapooletud ja ettearvamatud, kuni vähemalt ⅓ osalistest järgib protokolli. Oluline on märkida, et kurjategija, kes kontrollib rohkem kui ⅓, kuid vähem kui ⅔ osalistest, võib protokolli peatada, kuid ei saa ennustada ega mõjutada selle väljundit.

Piirangutega allkirjad iseenesest on väga huvitav teema. Artikli teises osas käsitleme üksikasjalikult, kuidas need töötavad ja kuidas osaliste võtmeid genereerida, et piirangutega allkirju saaks kasutada juhuslike numbrite generaatorina.

Kokkuvõtteks

See artikkel on esimene tehniliste artiklite seerias blogis NEAR. NEAR on plokiahela protokoll ja platvorm detsentraliseeritud rakenduste arendamiseks, keskendudes arendamise lihtsusele ja lõppkasutajate kasutusmugavusele.

Protokolli kood on avatud, meie teostus on kirjutatud Rustis, selle leiate siin.

Vaata, milline näeb välja NEAR-i arendamine, ja katseta online-IDE-s. siit.

Jälgi kõiki uudiseid eesti keeles Telegrami grupis ja VKontakte grupis., aga inglise keeles ametlikul Twitteris.

Kohtumiseni!

Allikas: habr.com