Kas on võimalik genereerida juhuslikke numbreid, kui me üksteist ei usalda? 1. osa

Tere Habr!

Selles artiklis räägin pseudojuhuslike numbrite genereerimisest osalejate poolt, kes üksteist ei usalda. Nagu allpool näeme, on "peaaegu" hea generaatori rakendamine üsna lihtne, kuid väga hea generaator on keeruline.

Miks on vaja genereerida juhuslikke numbreid osalejate seas, kes üksteist ei usalda? Üks rakendusvaldkond on detsentraliseeritud rakendused. Näiteks rakendus, mis võtab osalejalt panuse vastu ja kas kahekordistab summa 49% tõenäosusega või võtab ära 51% tõenäosusega, töötab ainult siis, kui see suudab erapooletult saada juhusliku arvu. Kui ründaja saab mõjutada juhuslike numbrite generaatori tulemust ja isegi veidi suurendada oma võimalust rakenduses väljamakse saada, hävitab ta selle kergesti.

Kui kujundame hajutatud juhuslike arvude genereerimise protokolli, tahame, et sellel oleks kolm omadust:

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

2. Ta peab olema ettearvamatu. Teisisõnu, ükski osaleja ei tohiks enne selle genereerimist ennustada, milline arv genereeritakse (või järeldada selle omadusi).

3. Protokoll peab olema elujõuline, st vastupidav sellele, et teatud protsent osalejatest katkestab võrguühenduse või üritab tahtlikult protokolli peatada.

Selles artiklis vaatleme kahte lähenemisviisi: RANDAO + VDF ja kustutamiskoodide lähenemisviis. Järgmises osas uurime üksikasjalikult läve allkirjadel põhinevat lähenemist.

Kuid 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 genereerimiseks. Kõik võrgus osalejad valivad esmalt kohapeal pseudojuhusliku numbri, seejärel saadab iga osaleja valitud numbri räsi. Järgmisena paljastavad osalejad kordamööda oma valitud numbrid ja sooritavad ilmutatud numbritele XOR-operatsiooni ning selle toimingu tulemus saab protokolli tulemuseks.

Räside avaldamine enne numbrite avaldamist on vajalik selleks, et ründaja ei saaks pärast teiste osalejate numbrite nägemist oma numbrit valida. See võimaldaks tal praktiliselt üksi määrata juhuslike arvude generaatori väljundi.

Protokolli käigus peavad osalejad jõudma ühisele otsusele (nn konsensusele) kaks korda: millal alustada valitud numbrite paljastamist ja seetõttu lõpetada räsi vastuvõtmine ning millal lõpetada valitud numbrite aktsepteerimine ja sellest tuleneva juhusliku arvu arvutamine. number. Selliste otsuste tegemine üksteist mitteusaldavate osalejate vahel ei ole iseenesest lihtne ülesanne ja tuleme selle juurde järgmistes artiklites tagasi, selles artiklis eeldame, et selline konsensusalgoritm on meile kättesaadav.

Milliseid ülalkirjeldatud omadusi RANDAO omab? See on ettearvamatu, sellel on sama elujõud kui selle aluseks oleval konsensuse protokollil, kuid see on kallutatud. Täpsemalt saab ründaja võrku jälgida ja pärast seda, kui teised osalejad on oma numbrid avaldanud, saab ta arvutada oma XOR-i ja otsustada, kas avaldada oma number, et tulemust mõjutada. Kuigi see takistab ründajal juhuslike arvude generaatori väljundit üksi määrata, annab see talle siiski 1 biti mõjuvõimu. Ja kui ründajad kontrollivad mitut osalejat, võrdub nende kontrollitavate bittide arv nende kontrolli all olevate osalejate arvuga.

Ründajate mõju saab oluliselt vähendada, kui nõuda, et osalejad avaldaksid numbrid järjekorras. Siis saab ründaja tulemust mõjutada ainult siis, kui see avatakse viimasena. Kuigi mõju on oluliselt väiksem, on algoritm siiski kallutatud.

RANDAO+VDF

Üks võimalus RANDAO erapooletuks muutmiseks on järgmine: pärast kõigi arvude paljastamist ja XOR-i arvutamist sisestatakse selle tulemus funktsiooni sisendisse, mille arvutamine võtab väga kaua aega, kuid võimaldab kontrollida funktsiooni õigsust. arvutamine väga kiiresti.

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

Seda funktsiooni nimetatakse kontrollitavaks viivitusfunktsiooniks või VDF-iks. Kui lõpptulemuse arvutamine võtab rohkem aega kui numbrite avalikustamise etapp, siis ei suuda ründaja oma numbri näitamise või varjamise mõju ette ennustada ning seetõttu kaob tal võimalus tulemust mõjutada.

Heade VDF-ide väljatöötamine on äärmiselt keeruline. Viimasel ajal on toimunud mitmeid läbimurdeid, nt. see и see, mis muutis VDF-i praktikas praktilisemaks, ja Ethereum 2.0 plaanib pikemas perspektiivis kasutada RANDAO-d koos VDF-iga juhuslike arvude allikana. Peale selle, et see lähenemine on ettearvamatu ja erapooletu, on selle lisaeelis elujõulisus, kui võrgus on saadaval vähemalt kaks osalejat (eeldusel, et kasutatav konsensusprotokoll on nii väikese osalejate arvuga suhtlemisel elujõuline).

Selle lähenemisviisi suurim väljakutse on VDF-i seadistamine nii, et isegi väga kalli spetsiaalse riistvaraga osaleja ei suuda VDF-i enne avastamisfaasi lõppu arvutada. Ideaalis peaks algoritmil olema isegi märkimisväärne ohutusvaru, näiteks 10x. Alloleval joonisel on kujutatud näitleja rünnak, kellel on spetsiaalne ASIC, mis võimaldab tal käivitada VDF-i kiiremini kui RANDAO kinnituse avaldamiseks kuluv aeg. Selline osaleja saab ikkagi oma numbrit kasutades või mitte kasutades lõpptulemuse välja arvutada ning seejärel arvutuse põhjal valida, kas seda näidata või mitte.

Ülalmainitud VDF-i perekonna puhul võib spetsiaalse ASIC-i jõudlus olla 100+ korda suurem kui tavalise riistvara puhul. Seega, kui kasutuselevõtufaas kestab 10 sekundit, peab sellisel ASIC-l arvutatud VDF-il kuluma rohkem kui 100 sekundit, et saada 10-kordne ohutusvaru, ja seega peab sama kaubariistvaraga arvutatud VDF võtma aega 100x 100 sekundit = ~3 tundi.

Ethereumi sihtasutus kavatseb selle probleemi lahendada, luues oma avalikult kättesaadavad tasuta ASIC-id. Kui see juhtub, saavad seda tehnoloogiat ära kasutada ka kõik teised protokollid, kuid seni ei ole RANDAO+VDF-lähenemine nii elujõuline protokollide puhul, mis ei saa investeerida oma ASIC-ide väljatöötamisse.

VDF-i kohta on kogutud palju artikleid, videoid ja muud teavet see sait.

Kasutame kustutuskoode

Selles jaotises vaatleme juhuslike arvude genereerimise protokolli, mida kasutatakse koodide kustutamine. See talub kuni ⅓ ründajat, jäädes samas elujõuliseks, ja võimaldab eksisteerida kuni ⅔ ründajatel, enne kui nad suudavad tulemust ennustada või mõjutada.

Protokolli põhiidee on järgmine. Lihtsuse mõttes oletame, et osalejaid on täpselt 100. Oletame ka, et kõigil osalejatel on kohapeal mingi privaatvõti ja kõigi osalejate avalikud võtmed on kõigile osalejatele teada:

1. Iga osaleja koostab kohapeal pika stringi, jagab selle 67 osaks, loob kustutamiskoodid 100 jagamise saamiseks, nii et stringi taastamiseks piisab 67-st, määrab kõik 100 jagamist ühele osalejatest ja krüpteerib need sama osaleja avalik võti. Seejärel avaldatakse kõik kodeeritud aktsiad.

2. Osalejad kasutavad teatud konsensust, et jõuda kokkuleppele konkreetse 67 osaleja kodeeritud komplektide osas.

3. Kui konsensus on saavutatud, võtab iga osaleja oma avaliku võtmega krüpteeritud 67 komplekti kodeeritud osad, dekrüpteerib kõik sellised jagamised ja avaldab kõik sellised dekrüpteeritud jagamised.

4. Kui 67 osalejat on etapi (3) lõpetanud, saab kustutamiskoodide omaduste tõttu kõik kokkulepitud komplektid täielikult dekodeerida ja rekonstrueerida ning lõpliku numbri saab algsete ridade XOR-na, millega osalejad punktis (1) alustasid. .

Võib näidata, et see protokoll on erapooletu ja ettearvamatu. Saadud juhuslik arv määratakse pärast konsensuse saavutamist, kuid see pole kellelegi teada enne, kui ⅔ osalejatest dekodeerib nende avaliku võtmega krüpteeritud osad. Seega määratakse juhuslik arv enne selle rekonstrueerimiseks piisava teabe avaldamist.

Mis juhtub, kui sammus (1) saadab üks osalejatest teistele osalejatele kodeeritud jagamisi, mis pole mõne stringi jaoks õige kustutamiskood? Ilma täiendavate muudatusteta ei saa erinevad osalejad stringi üldse taastada või taastavad erinevad stringid, mille tulemusena saavad erinevad osalejad erineva juhusliku arvu. Selle vältimiseks saab teha järgmist: iga osaleja arvutab lisaks kodeeritud aktsiatele ka Merkla puu kõik sellised jagamised ja saadab igale osalejale nii kodeeritud aktsia enda kui ka märgipuu juure ning tõendi aktsia lisamise kohta märgipuusse. Etapis (2) saavutatud konsensuse korral ei lepi osalejad kokku mitte ainult komplektide komplektis, vaid selliste puude konkreetsete juurte komplektis (kui mõni osaleja kaldus protokollist kõrvale ja saatis erinevatele osalejatele erinevad märgipuu juured, ja kaks sellist juurt on näidatud konsensuse ajal, tema rida ei sisaldu tulemuste komplektis). Konsensuse tulemusel on meil 67 kodeeritud rida ja vastavad märgipuu juured, nii et osalejaid on vähemalt 67 (mitte tingimata samad, kes vastavad read välja pakkusid), kellel on iga 67 rea kohta. teade kustutamiskoodi osaga ja tõend nende osa esinemise kohta vastavas puus tuhmusid.

Kui etapis (4) dešifreerib osaleja teatud stringi jaoks 67 lööki ja proovib nende põhjal algset stringi taastada, on võimalik üks järgmistest valikutest:

1. String taastatakse ja kui see seejärel uuesti kustutada ja arvutada Merkle puu lokaalselt arvutatud aktsiate jaoks, langeb juur kokku sellega, mille osas jõuti konsensusele.

2. Rida taastatakse, kuid lokaalselt arvutatud juur ei ühti sellega, mille puhul konsensusele jõuti.

3. Rida ei taastata.

Lihtne on näidata, et kui valik (1) juhtus vähemalt ühe ülaltoodud osalejaga, siis valik (1) juhtus kõigi osalejatega ja vastupidi, kui valik (2) või (3) juhtus vähemalt ühe osalejaga, siis kõikide osalejate puhul toimub valik (2) või (3). Seega saavad komplekti iga rea ​​puhul kõik osalejad selle edukalt taastada või kõik osalejad ei suuda seda taastada. Saadud juhuslik arv on siis ainult nende ridade XOR, mille osalejad suutsid taastada.

Allkirjade läve

Teine lähenemine juhuslikkusele on nn BLS-i lävesignatuuride kasutamine. Lävisignatuuridel põhineval juhuslike arvude generaatoril on täpselt samad garantiid kui ülalkirjeldatud kustutamiskoodipõhisel algoritmil, kuid iga genereeritud numbri kohta on võrgu kaudu saadetavate sõnumite asümptootiline arv oluliselt väiksem.

BLS-i allkirjad on kujundus, mis võimaldab mitmel osalejal luua sõnumile ühe ühise allkirja. Neid allkirju kasutatakse sageli ruumi ja ribalaiuse säästmiseks, kuna ei nõuta mitme allkirja väljasaatmist. 

Levinud rakendus BLS-i allkirjade jaoks plokiahela protokollides on lisaks juhuslike numbrite genereerimisele BFT-protokollides plokk-allkirjastamine. Oletame, et 100 osalejat loovad plokke ja plokk loetakse lõplikuks, kui 67 neist allkirjastab selle. Nad kõik saavad esitada oma osad BLS-i allkirjast ja kasutada mõnda konsensusalgoritmi, et leppida kokku 67-s ja seejärel liita need üheks BLS-allkirjaks. Lõpliku allkirja loomiseks võib kasutada mis tahes 67 (või enamat) osa, mis sõltub sellest, millised 67 allkirja kombineeriti ja seetõttu võivad need erineda, kuigi 67 osaleja erinevad valikud loovad erineva allkirja, iga selline allkiri on kehtiv. allkiri ploki jaoks. Ülejäänud osalejad peavad seejärel saama ja kontrollima ainult ühe allkirja ploki kohta, mitte 67, üle võrgu, mis vähendab oluliselt võrgu koormust.

Selgub, et kui osalejate kasutatavad privaatvõtmed genereeritakse teatud viisil, siis olenemata sellest, millised 67 allkirja (või rohkem, kuid mitte vähem) on koondatud, on saadud signatuur sama. Seda saab kasutada juhuslikkuse allikana: osalejad lepivad esmalt kokku mingis sõnumis, millele nad alla kirjutavad (see võib olla RANDAO väljund või lihtsalt viimase ploki räsi, see pole tegelikult oluline, kui see muutub iga kord ja on järjepidev) ja looge selle jaoks BLS-i allkiri. Põlvkonna tulemus on ettearvamatu, kuni 67 osalejat annavad oma osad ja pärast seda on väljund juba ette määratud ega saa sõltuda ühegi osaleja tegevusest.

Selline lähenemine juhuslikkusele on elujõuline seni, kuni vähemalt ⅔ võrgus osalejatest järgib protokolli ning on erapooletu ja ettearvamatu seni, kuni vähemalt ⅓ osalejatest järgib protokolli. Oluline on märkida, et ründaja, kes kontrollib rohkem kui ⅓, kuid vähem kui ⅔ osalejatest, võib protokolli peatada, kuid ei saa ennustada ega mõjutada selle väljundit.

Läve allkirjad ise on väga huvitav teema. Artikli teises osas analüüsime üksikasjalikult, kuidas need töötavad ja kuidas täpselt on vaja osalejavõtmeid genereerida, et lävesignatuure saaks kasutada juhuslike numbrite generaatorina.

Kokkuvõttes

See artikkel on esimene tehniliste ajaveebiartiklite sarjast NEAR. NEAR on plokiahela protokoll ja platvorm detsentraliseeritud rakenduste arendamiseks, rõhuasetusega arendamise lihtsusele ja kasutusmugavusele lõppkasutajate jaoks.

Protokollikood on avatud, meie teostus on kirjutatud Rustis, see on leitav siin.

Saate vaadata, kuidas NEAR-i arendus välja näeb, ja katsetada veebipõhises IDE-s siin.

Kõiki uudiseid saate jälgida vene keeles aadressil telegrammi grupp ja grupp VKontakte'is, ja inglise keeles ametlikus twitter.

Varsti näeme!

Allikas: www.habr.com