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

Tere, Habr!

Selles artiklis räägin ma pseudojuhuslike arvude genereerimisest osalistele, kes ei usalda üksteist. Nagu allpool näeme, on 'peaaegu' head generaatorit lihtsalt rakendada, kuid väga hea valmistamine on keeruline.

Miks üldse on vaja osalistel genereerida juhuslikke numbreid, kui nad ei usalda üksteist? Üks rakenduse valdkond on detsentraliseeritud rakendused. Näiteks rakendus, mis võtab panuse osaliselt ja kas kahekordistab summa 49% tõenäosusega või võtab 51%, toimib ainult siis, kui see suudab erapooletult saada juhusliku arvu. Kui küberkurjategija suudab mõjutada juhuslike arvude generaatori tulemusi ja isegi vähesel määral suurendada oma võimalusi rakenduses makse saada, tühjendab ta selle kergesti.

Kui me arendame jagatud protokolli juhuslike arvude genereerimiseks, soovime, et see omaks kolme omadust:

1. See peab olema erapooletu. Teisisõnu, ükski osaline ei tohi mingil moel mõjutada juhuslike arvude generaatori tulemust.

2. See peab olema ettearvamatu. Teisisõnu, ükski osaline ei tohi suuta ennustada, milline number genereeritakse (või tuletada selle omadusi) enne, kui see on genereeritud.

3. Protokoll peab olema elujõuline, st resistentne selle suhtes, et mingi osakaal osalistest lahkub võrgust või üritab tahtlikult protokolli peatada.

Selles artiklis käsitleme kahte lähenemist: RANDAO + VDF ja lähenemist, mis põhineb kustutuskoodidel. Järgmises osas käsitleme põhjalikult lähenemist, mis põhineb läve allkirjadel.

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 liikmed valivad esmalt kohapeal pseudojuhusliku arvu, seejärel saadab iga osaline valitud arvu räsiväärtuse. Edasi avavad osalised kordamööda oma valitud numbrid, ja nende avatud numbrite üle viiakse läbi XOR tehe, mille tulemusena saadakse protokolli tulemus.

Hash publikatsiooni samm enne arvu avamist on vajalik, et ründaja ei saaks valida oma numbrit pärast seda, kui ta on näinud teiste osalejate arve. See võimaldaks tal tegelikult üksi määrata juhuslike numbrite generaatori väljundi.

Protokolli käigus peavad osalejad kaks korda jõudma ühisele otsusele (nn konsensus): millal alustada valitud numbrite avamist ja seega lõpetada hashede vastuvõtmine, ja millal lõpetada valitud numbrite vastuvõtmine ning arvutada lõplik juhuslik number. Nende otsuste vastuvõtmine osalejate vahel, kes ei usalda üksteist, on iseenesest keeruline ülesanne, ja me pöördume selle teema juurde tulevastes artiklites, käesolevas artiklis eeldame, et meil on selline konsensus algoritm olemas.

Millised omadused, millest me eespool rääkisime, on RANDAO-l? See on ettearvamatu, omades sama elujõudlust kui selle põhjal olev konsensusprotokoll, kuid see on kallutatud. Eelkõige võib ründaja jälgida võrgustikku ja pärast seda, kui teised osalejad oma numbrid avavad, suudab ta arvutada nende XOR-i ja otsustada, kas avada oma number või mitte, et tulemusele mõju avaldada. Kuigi see ei luba ründajal üksi määrata juhuslike numbrite generaatori väljundit, annab see talle siiski 1 bitti mõju. Ja kui ründajad kontrollivad mitmeid osalejaid, siis kontrollitud bitite arv on sama, mis nende käes oleva osalejate arv.

Ründajate mõju võib oluliselt vähendada, kui nõuda, et osalejad avavad numbrid järjestikku. Siis saab ründaja tulemusele mõju avaldada ainult juhul, kui ta avab viimase. Kuigi mõju on märkimisväärselt väiksem, on algoritm siiski kallutatud.

RANDAO + VDF

Üks võimalus, kuidas teha RANDAO mitte kallutatud, on järgmine: pärast seda, kui kõik numbrid on avatud ja XOR arvutatud, antakse selle tulemus sisendiks funktsioonile, mille arvutamine võtab väga kaua aega, kuid mille õigsuse kontrollimine on väga kiire.

(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

See funktsioon on tuntud kui Verifiable Delay Function ehk VDF. Kui lõpliku tulemuse arvutamine võtab rohkem aega kui numbrite avamise etapp, ei saa kurjategija ennustada efekti, kui ta oma numbrit demonstreerib või varjab, ning seetõttu kaotab ta võimaluse tulemusele mõju avaldada.

Hea VDF arendamine on äärmiselt keeruline. Viimase aja jooksul on tehtud mitu läbimurret, näiteks see ja see, mis on teinud VDF-de rakendamise praktikas lihtsamaks, ja Ethereum 2.0 plaanib pikaajaliselt kasutada RANDAO-d VDF-ga juhuslike numbrite allikana. Lisaks sellele, et see lähenemine on ettearvamatu ja erapooletu, on sellel lisaks veel üks eelis, mis seisneb töökindluses, kui vähemalt kaks osalejat on võrgus (eeldusel, et kasutatav konsensusprotokoll on toimiv nii väikese osalejate arvu puhul).

Selle lähenemise suurim väljakutse on VDF seadistamine nii, et isegi osaleja, kellel on väga kallis spetsialiseeritud varustus, ei suudaks VDF-d arvutada enne, kui avamise faas on lõppenud. Ideaalis peaks algoritm olema isegi märkimisväärse varu, ütleme, 10x. Alloleval joonisel on kujutatud osa, kus osaleja, kellel on spetsialiseeritud ASIC, suudab käivitada VDF-d kiiremini, kui on RANDAO kinnituse avamiseks ettenähtud aeg. Selline osaleja võib siiski arvutada lõpptulemuse, kasutades või mitte kasutades oma numbrit, ja seejärel, lähtudes arvutustest, valima, kas näidata seda või mitte.

Ülepool toodud VDF perekonna puhul võib spetsialiseeritud ASIC-i jõudlus olla üle 100 korda parem kui tavaliste seadmete omast. Seega, kui avamise faas kestab 10 sekundit, peab sellisel ASIC-il arvutatud VDF võtma rohkem kui 100 sekundit, et omada 10-kordset ohutusvaru, ja seega sama VDF, mis arvutatakse tavalise varustuse abil, peab võtma 100 x 100 sekundit = ~ 3 tundi.

Ethereum Foundation kavatseb selle probleemi lahendada, luues enda avalikud tasuta ASIC-id. Kui see juhtub, saavad kõik teised protokollid samuti seda tehnoloogiat kasutada, kuid kuni selle ajani ei ole RANDAO + VDF lähenemine sama elujõuline protokollide jaoks, kes ei saa investeerida oma ASIC-ide arendamisse.

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

Kasutame kustutuskode

Selles osas vaatleme juhuslike arvude genereerimise protokolli, mis kasutab kustutuskode. See suudab taluda kuni ⅓ pahatahtlikest osalejatest ja lubab kuni ⅔ pahatahtlikku osalejat, enne kui nad suudavad tulemust ennustada või sellele mõju avaldada.

Protokolli põhijõud on järgmine. Lihtsuse huvides eeldame, et selles osaleb täpselt 100 liiget. Eeldame ka, et kõigil liikmetel on kohalikult olemas mõni privaatvõti ning kõigi liikmete avalikud võtmed on kõigile osalejatele teada:

1. Iga liige mõtleb kohalikult välja pika stringi, jagab selle 67 osaks, loob kustutuskoodid 100 osaleja saamiseks, nii et igast 67-st piisab stringi taastamiseks, määrab iga 100 osast ühe osalejale ja krüpteerib need sama osaleja avaliku võtmega. Seejärel avalikustatakse kõik krüpteeritud osad.

2. Osalejad kasutavad mingit konsensust, et jõuda kokkuleppele konkreetsete 67 osaleja krüpteeritud kogumite üle.

3. Kui konsensus on saavutatud, võtab iga liige iga 67 kogumi krüpteeritud osad, mis on krüpteeritud nende avaliku võtmega, dekrüpteerib kõik sellised osad ja avalikustab kõik dekrüpteeritud osad.

4. Kui 67 osalejat on läbinud sammu (3), saab kõiki kokkulepitud kogumeid täielikult dekodeerida ja taastada kustutuskoodide omaduste tõttu, ning lõplik number võib olla saadud algsete stringide XOR-iga, millega osalejad alustasid (1).

On võimalik näidata, et see protokoll on erapooletu ja ettearvamatu. Tulemuslik juhuslik number määratakse pärast konsensuse saavutamist, kuid kellelegi see ei ole teada, kuni ⅔ osalejatest ei dekrüpteeri osi, mis on nende avaliku võtmega krüptitud. Seega on juhuslik number määratud enne, kui teave, mis on piisav selle taastamiseks, on avaldatud.

Mis juhtub, kui sammu (1) jooksul saadab üks osalejatest teistele osalejatele kodeeritud osad, mis ei ole mõne rea korrektne kustutuskood? Ilma täiendavate muudatusteta ei suuda erinevad osalejad kas täielikult rida taastada või taastavad nad erinevaid ridu, mis viib selleni, et erinevad osalejad saavad erineva juhusliku numbri. Selle vältimiseks saab teha järgmist: iga osaleja arvutab peale kodeeritud osade ka Merkle puu , ja saadab igale osalejale nii kodeeritud osa kui Merkle puu juure ja tõendi osa sisestamise kohta Merkle puusse. Konsensuse sammul (2) nõustuvad osalejad siis mitte lihtsalt mitme komplektiga, vaid mitme konkreetse sellise puu juurega (kui mõni osaleja on protokollist kõrvalekaldunud ja on saatnud erinevaid Merkle puude juuri erinevatele osalejatele, ja kaks sellist juurt näidatakse konsensuse ajal, siis ei kaasata tema rida tulemuste komplekti). Konsensuse lõpuks on meil 67 kodeeritud rida ja nendega seotud Merkle puude juured, nii et vähemalt 67 osalejat (mitte tingimata need, kes esitasid vastavad read) saavat igas 67 reas sõnumi kustutuskoodiga osast ja tõendi nende osa vastavuses Merkle puusse.

Kui sammu (4) jooksul osaleja dekrüpteerib 67 osa mõne rea jaoks ja proovib neid järgi taastada, on võimalik üks järgmistest variantidest:

1. Rida taastatakse, ja kui seda seejärel uuesti kustutuskoodide abil kodeerida ja arvutada Merkle puu lokaalsete osade jaoks, siis juur vastab sellele, mille üle on saavutatud konsensus.

2. Rida taastatakse, kuid lokaalsetelt arvutatud juurt ei vastata sellele, mille üle on saavutatud konsensus.

3. Rida ei taastata.

Lihtne on näidata, et kui vähemalt ühel osalejal juhtus variant (1), siis toimub see kõigil osalejatest ja vastupidi, kui vähemalt ühel osalejal juhtus variant (2) või (3), siis toimub see samuti kõigil osalejatest. Seega, iga rida andmestikus kas suudavad kõik osalejad selle taastada või mitte. Seega, tulemuseks olev juhuslik number on XOR vaid nende ridade jaoks, mida osalejad suudavad taastada.

Piirväärtuste allkirjad

Teine lähenemine juhuslikkusele hõlmab nn BLS-i piirväärtuste allkirju. Piirväärtuste põhjal genereeritud juhuslike arvude generaatoril on täpselt samasugused garantiid nagu eelnevalt kirjeldatud kustutuskoodide põhine algoritm, kuid sellel on märkimisväärselt väiksem sõnumite edastamise asümptootika võrreldes iga genereeritud numbri kohta.

BLS-i allkirjad on konstruktsioon, mis võimaldab mitmel osalejal luua ühe ühise allkirja sõnumile. Selliseid allkirju kasutatakse tihti ruumi ja ribalaiuse kokkuhoiuks, kuna need ei nõua mitme allkirja saatmist. 

BLS-allkirjade sage rakendamine plokiahela protokollides, peale juhuslike arvude genereerimise, on plokkide allkirjastamine BFT protokollides. Oletame, et 100 osalejat loovad plokke, ja plokk loetakse lõplikuks, kui 67 neist allkirjastavad selle. Kõik nad saavad esitada oma BLS-allkirja osi ja kasutada mingit konsensusalgoritmi, et koondada 67 neist ja seejärel kombineerida need üheks BLS-allkirjaks. Igasuguseid 67 (või rohkem) osa saab kasutada lõpliku allkirja loomiseks, mis sõltub sellest, millised täpsed 67 allkirja on kokku pandud, ja seetõttu võib see varieeruda, kuid hoolimata sellest, et erinevad valikud 67 osalejast tekitavad erineva allkirja, on iga selline allkiri valideeritud allkiri ploki jaoks. Ülejäänud osalejatele on seejärel piisav, et saada võrgust ainult üks allkiri iga ploki kohta, mitte 67, mis oluliselt vähendab võrgu koormust.

Selgus on, et kui osalejate kasutatavad privaatvõtmed genereeritakse teatud viisil, siis olenemata sellest, kui palju 67 allkirja (või rohkem, kuid mitte vähem) kokku liidetakse, on tulemusena saadud allkiri sama. Seda saab kasutada juhuslikkuse allikana: osalejad lepivad esmalt kokku mingis sõnumis, mille 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) ning loovad sellele BLS-allkirja. Generatsiooni tulemus on ennustamatu, kuni 67 osalejat ei esita oma osi, ja pärast seda on väljund juba ette määratud ega saa sõltuda ühegi osaleja toimingutest.

Selline lähenemine juhuslikkusele on elujõuline, kui vähemalt ⅔ osalejatest on online ja järgivad protokolli, ning on objektiivne ja ettearvamatu, kuni vähemalt ⅓ osalejatest järgivad protokolli. Oluline on tähele panna, et kurjategija, kes kontrollib rohkem kui ⅓, kuid vähem kui ⅔ osalejat, võib protokolli peatada, kuid ei saa ennustada ega mõjutada selle väljundit.

Piiratud allkirjad iseenesest on väga huvitav teema. Artikli teises osas uurime üksikasjalikult, kuidas need töötavad ja kuidas osalejate võtmeid tuleb genereerida, et piiratud allkirju saaks kasutada juhuslike arvude generaatorina.

Kokkuvõtteks

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

Protokolli kood on avatud, meie teostus on kirjutatud Rustis, seda saab leida siit.

Vaata, kuidas NEAR-i arendus välja näeb ja eksperimentida saad veebipõhises IDE-s siin.

Kõiki uudiseid vene keeles saab jälgida grupis Telegramis ja grupis Vkontakte, ja inglise keeles ametlikus Twitteris.

Jõuame taas kokku!

Allikas: habr.com