ProHoster > Blogs > Administrācija > Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 1. daļa

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 1. daļa

Čau Habr!

Å ajā rakstā es runāŔu par pseidogadÄ«juma skaitļu Ä£enerÄ“Å”anu, ko veic dalÄ«bnieki, kuri neuzticas viens otram. Kā redzēsim tālāk, ā€œgandrÄ«zā€ laba Ä£eneratora ievieÅ”ana ir diezgan vienkārÅ”a, bet ļoti laba ir sarežģīta.

Kāpēc bÅ«tu nepiecieÅ”ams Ä£enerēt nejauÅ”us skaitļus starp dalÄ«bniekiem, kuri neuzticas viens otram? Viena lietojuma joma ir decentralizētas lietojumprogrammas. Piemēram, lietojumprogramma, kas pieņem likmi no dalÄ«bnieka un vai nu dubulto summu ar 49% varbÅ«tÄ«bu vai atņem ar 51% varbÅ«tÄ«bu, darbosies tikai tad, ja tā var objektÄ«vi saņemt nejauÅ”u skaitli. Ja uzbrucējs var ietekmēt nejauÅ”o skaitļu Ä£eneratora iznākumu un pat nedaudz palielināt savu iespēju saņemt izmaksu aplikācijā, viņŔ to viegli izpostÄ«s.

Izstrādājot sadalÄ«tu nejauÅ”o skaitļu Ä£enerÄ“Å”anas protokolu, mēs vēlamies, lai tam bÅ«tu trÄ«s Ä«paŔības:

  1. Viņam jābÅ«t objektÄ«vam. Citiem vārdiem sakot, neviens dalÄ«bnieks nekādā veidā nedrÄ«kst ietekmēt nejauÅ”o skaitļu Ä£eneratora rezultātu.

  2. Viņam jābÅ«t neparedzamam. Citiem vārdiem sakot, neviens dalÄ«bnieks nedrÄ«kst paredzēt, kāds skaitlis tiks Ä£enerēts (vai izsecināt kādu no tā Ä«paŔībām), pirms tas tiek Ä£enerēts.

  3. Protokolam ir jābūt dzīvotspējīgam, tas ir, izturīgam pret to, ka noteikta daļa dalībnieku atvienojas no tīkla vai apzināti mēģina apturēt protokolu.

Å ajā rakstā mēs aplÅ«kosim divas pieejas: RANDAO + VDF un dzÄ“Å”anas kodu pieeju. Nākamajā daļā mēs detalizēti apskatÄ«sim pieeju, kuras pamatā ir sliekŔņa paraksti.

Bet vispirms apskatÄ«sim vienkārÅ”u un plaÅ”i izmantotu algoritmu, kas ir dzÄ«votspējÄ«gs, neparedzams, bet neobjektÄ«vs.

RANDAO

RANDAO ir ļoti vienkārÅ”a un tāpēc diezgan bieži izmantota pieeja nejauŔības Ä£enerÄ“Å”anai. Visi tÄ«kla dalÄ«bnieki vispirms lokāli izvēlas pseidogadÄ«juma numuru, pēc tam katrs dalÄ«bnieks nosÅ«ta izvēlētā numura jaucējkodu. Tālāk dalÄ«bnieki pārmaiņus atklāj savus izvēlētos skaitļus un veic XOR operāciju atklātajiem skaitļiem, un Ŕīs darbÄ«bas rezultāts kļūst par protokola rezultātu.

Jaucējkodu publicÄ“Å”ana pirms skaitļu atklāŔanas ir nepiecieÅ”ama, lai uzbrucējs nevarētu izvēlēties savu numuru pēc tam, kad ir redzējis citu dalÄ«bnieku numurus. Tas ļautu viņam praktiski vienpersoniski noteikt nejauÅ”o skaitļu Ä£eneratora izvadi.

Protokola laikā dalÄ«bniekiem divreiz ir jāpieņem kopÄ«gs lēmums (tā sauktais konsenss): kad sākt atklāt atlasÄ«tos skaitļus un lÄ«dz ar to pārtraukt jaukÅ”anas pieņemÅ”anu, un kad pārtraukt pieņemt izvēlētos skaitļus un aprēķināt iegÅ«to nejauŔību. numuru. Šādu lēmumu pieņemÅ”ana starp dalÄ«bniekiem, kuri neuzticas viens otram, pats par sevi nav viegls uzdevums, un mēs pie tā atgriezÄ«simies nākamajos rakstos, Å”ajā rakstā pieņemsim, ka Ŕāds konsensa algoritms mums ir pieejams.

Kurām no iepriekÅ” aprakstÄ«tajām Ä«paŔībām piemÄ«t RANDAO? Tas ir neparedzams, tam ir tāds pats vitalitāte kā pamatā esoÅ”ajam konsensa protokolam, taču tas ir neobjektÄ«vs. Konkrēti, uzbrucējs var novērot tÄ«klu, un pēc tam, kad citi dalÄ«bnieki atklāj savus numurus, viņŔ var aprēķināt savu XOR un izlemt, vai atklāt savu numuru, lai ietekmētu rezultātu. Lai gan tas neļauj uzbrucējam vienam paÅ”am noteikt nejauÅ”o skaitļu Ä£eneratora izvadi, tas viņam joprojām dod 1 bitu ietekmes. Un, ja uzbrucēji kontrolē vairākus dalÄ«bniekus, tad viņu kontrolēto bitu skaits bÅ«s vienāds ar viņu kontrolē esoÅ”o dalÄ«bnieku skaitu.

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 1. daļa

Uzbrucēju ietekmi var ievērojami samazināt, pieprasot dalībniekiem atklāt skaitļus secībā. Tad uzbrucējs varēs ietekmēt iznākumu tikai tad, ja tas tiks atvērts pēdējais. Lai gan ietekme ir ievērojami mazāka, algoritms joprojām ir neobjektīvs.

RANDAO+VDF

Viens no veidiem, kā padarÄ«t RANDAO objektÄ«vu, ir Ŕāds: pēc tam, kad visi skaitļi ir atklāti un XOR ir aprēķināts, tā rezultāts tiek ievadÄ«ts funkcijas ievadā, kas aizņem ļoti ilgu laiku, lai aprēķinātu, bet ļauj pārbaudÄ«t skaitļu pareizÄ«bu. aprēķins ļoti ātri.

(vdf_output, vdf_proof) = VDF_compute(input) // этŠ¾ Š¾Ń‡ŠµŠ½ŃŒ Š¼ŠµŠ“Š»ŠµŠ½Š½Š¾
correct = VDF_verify(input, vdf_output, vdf_proof) // этŠ¾ Š¾Ń‡ŠµŠ½ŃŒ Š±Ń‹ŃŃ‚Ń€Š¾

Å o funkciju sauc par verificējamo aizkaves funkciju jeb VDF. Ja gala rezultāta aprēķināŔana aizņem ilgāku laiku nekā numura izpauÅ”anas stadija, tad uzbrucējs nevarēs paredzēt sava numura parādÄ«Å”anas vai slēpÅ”anas efektu un lÄ«dz ar to viņŔ zaudēs iespēju ietekmēt rezultātu.

Labu VDF izstrāde ir ārkārtÄ«gi sarežģīta. Pēdējā laikā ir bijuÅ”i vairāki izrāvieni, piem. Å”is Šø Å”is, kas VDF praksē padarÄ«ja praktiskāku, un Ethereum 2.0 plāno ilgtermiņā izmantot RANDAO ar VDF kā nejauÅ”u skaitļu avotu. Papildus tam, ka Ŕī pieeja ir neparedzama un objektÄ«va, tai ir papildu ieguvums, ja tÄ«klā ir pieejami vismaz divi dalÄ«bnieki (pieņemot, ka izmantotais konsensa protokols ir dzÄ«votspējÄ«gs, strādājot ar tik nelielu dalÄ«bnieku skaitu).

Å Ä«s pieejas lielākais izaicinājums ir VDF iestatÄ«Å”ana tā, ka pat dalÄ«bnieks ar ļoti dārgu specializētu aparatÅ«ru nespēs aprēķināt VDF pirms atklāŔanas fāzes beigām. Ideālā gadÄ«jumā algoritmam vajadzētu bÅ«t pat ievērojamai droŔības rezervei, piemēram, 10x. Zemāk esoÅ”ajā attēlā ir parādÄ«ts aktiera uzbrukums, kuram ir specializēts ASIC, kas ļauj viņam palaist VDF ātrāk nekā laiks, kas atvēlēts RANDAO apstiprinājuma atklāŔanai. Šāds dalÄ«bnieks joprojām var aprēķināt gala rezultātu, izmantojot vai neizmantojot savu numuru, un pēc tam, pamatojoties uz aprēķinu, izvēlēties, vai to rādÄ«t vai nē.

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 1. daļa

IepriekÅ” minētajai VDF saimei speciālā ASIC veiktspēja var bÅ«t 100+ reižu augstāka nekā parastajai aparatÅ«rai. Tātad, ja izvietoÅ”anas fāze ilgst 10 sekundes, tad VDF, kas aprēķināts, izmantojot Ŕādu ASIC, ir nepiecieÅ”ams vairāk nekā 100 sekundes, lai iegÅ«tu 10 reizes lielāku droŔības rezervi, un tādējādi tam paÅ”am VDF, kas aprēķināts, izmantojot preču aparatÅ«ru, ir nepiecieÅ”ams 100 x 100 sekundes = ~3 stundas.

Ethereum fonds plāno atrisināt Å”o problēmu, izveidojot savus publiski pieejamos bezmaksas ASIC. Kad tas notiks, arÄ« visi citi protokoli var izmantot Ŕīs tehnoloÄ£ijas priekÅ”rocÄ«bas, taču lÄ«dz tam RANDAO+VDF pieeja nebÅ«s tik dzÄ«votspējÄ«ga protokoliem, kuri nevar ieguldÄ«t savu ASIC izstrādē.

Ir apkopoti daudzi raksti, video un cita informācija par VDF Å”ajā vietnē.

Mēs izmantojam dzÄ“Å”anas kodus

Å ajā sadaļā mēs apskatÄ«sim nejauÅ”o skaitļu Ä£enerÄ“Å”anas protokolu, kas tiek izmantots kodu dzÄ“Å”ana. Tas var paciest lÄ«dz ā…“ uzbrucējiem, vienlaikus saglabājot dzÄ«votspēju, un ļauj pastāvēt lÄ«dz ā…” uzbrucējiem, pirms viņi var paredzēt vai ietekmēt iznākumu.

Protokola galvenā ideja ir Ŕāda. VienkārŔības labad pieņemsim, ka ir tieÅ”i 100 dalÄ«bnieki. Pieņemsim arÄ«, ka visiem dalÄ«bniekiem lokāli ir kāda privātā atslēga un visu dalÄ«bnieku publiskās atslēgas ir zināmas visiem dalÄ«bniekiem:

  1. Katrs dalÄ«bnieks lokāli izdomā garu virkni, sadala to 67 daļās, izveido dzÄ“Å”anas kodus, lai iegÅ«tu 100 koplietojumu, lai ar 67 pietiktu virknes atkopÅ”anai, pieŔķir katru no 100 koplietojumiem vienam no dalÄ«bniekiem un Å”ifrē tos ar tā paÅ”a dalÄ«bnieka publiskā atslēga. Pēc tam tiek publicētas visas kodētās daļas.

  2. DalÄ«bnieki izmanto zināmu vienprātÄ«bu, lai panāktu vienoÅ”anos par kodētiem komplektiem no konkrētiem 67 dalÄ«bniekiem.

  3. Kad tiek panākta vienprātÄ«ba, katrs dalÄ«bnieks ņem kodētās daļas katrā no 67 kopām, kas Å”ifrētas ar savu publisko atslēgu, atÅ”ifrē visas Ŕādas koplietoÅ”anas un publicē visas Ŕādas atÅ”ifrētās daļas.

  4. Kad 67 dalÄ«bnieki ir pabeiguÅ”i 3. darbÄ«bu, visas saskaņotās kopas var pilnÄ«bā atÅ”ifrēt un rekonstruēt dzÄ“Å”anas kodu Ä«paŔību dēļ, un galÄ«go skaitli var iegÅ«t kā sākotnējo rindu XOR, ar kurām dalÄ«bnieki sāka darbÄ«bu (1). .

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 1. daļa

Var pierādÄ«t, ka Å”is protokols ir objektÄ«vs un neparedzams. Rezultātā iegÅ«tais nejauÅ”ais skaitlis tiek noteikts pēc vienprātÄ«bas sasniegÅ”anas, taču tas nevienam nav zināms, lÄ«dz ā…” dalÄ«bnieku atÅ”ifrē daļas, kas Å”ifrētas ar viņu publisko atslēgu. Tādējādi nejauÅ”ais skaitlis tiek noteikts, pirms tiek publicēta informācija, kas ir pietiekama tā rekonstrukcijai.

Kas notiek, ja 1. darbÄ«bā viens no dalÄ«bniekiem nosÅ«tÄ«s citiem dalÄ«bniekiem kodētus koplietojumus, kas nav pareizais dzÄ“Å”anas kods kādai virknei? Bez papildu izmaiņām dažādi dalÄ«bnieki vai nu vispār nevarēs atgÅ«t virkni, vai arÄ« atgÅ«s dažādas virknes, kā rezultātā dažādi dalÄ«bnieki saņems atŔķirÄ«gu nejauŔības skaitli. Lai to novērstu, varat rÄ«koties Ŕādi: katrs dalÄ«bnieks papildus kodētajām daļām arÄ« aprēķina Merklas koks visas Ŕādas daļas un nosÅ«ta katram dalÄ«bniekam gan paÅ”u kodēto daļu, gan merkles koka sakni, kā arÄ« apliecinājumu par daļas iekļauÅ”anu merkles kokā. Konsensā 2. solÄ« dalÄ«bnieki ne tikai vienojas par kopu kopu, bet arÄ« par konkrētu Ŕādu koku sakņu kopu (ja kāds dalÄ«bnieks atkāpās no protokola un dažādiem dalÄ«bniekiem nosÅ«tÄ«ja dažādas merkles koku saknes, un divas Ŕādas saknes tiek parādÄ«tas vienprātÄ«bas laikā, viņa rinda nav iekļauta rezultātu kopā). VienprātÄ«bas rezultātā mums bÅ«s 67 kodētas rindiņas un atbilstoŔās merkle koka saknes, lai bÅ«tu vismaz 67 dalÄ«bnieki (ne vienmēr tie paÅ”i, kas ierosināja atbilstoŔās rindas), kuri katrai no 67 rindām ir izbalējis ziņojums ar dzÄ“Å”anas koda daļu un pierādÄ«jums par to daļas raÅ”anos attiecÄ«gajā kokā.

Kad (4) darbÄ«bā dalÄ«bnieks noteiktai virknei atÅ”ifrē 67 sitienus un mēģina no tiem rekonstruēt sākotnējo virkni, ir iespējama viena no iespējām:

  1. Virkne tiek atjaunota, un, ja tā pēc tam tiek vēlreiz kodēta ar dzÄ“Å”anas kodu un tiek aprēķināts Merkles koks lokāli aprēķinātajām daļām, sakne sakrÄ«t ar to, par kuru tika panākta vienprātÄ«ba.

  2. Rinda tiek atjaunota, bet lokāli aprēķinātā sakne neatbilst tai, kurā tika panākta vienprātība.

  3. Rinda netiek atjaunota.

Ir viegli parādÄ«t, ka, ja (1) variants noticis vismaz vienam dalÄ«bniekam, tad (1) variants noticis visiem dalÄ«bniekiem un otrādi, ja (2) vai (3) variants noticis vismaz vienam dalÄ«bniekam, tad visiem dalÄ«bniekiem bÅ«s iespēja (2) vai (3). Tādējādi katrai komplekta rindai vai nu visi dalÄ«bnieki to veiksmÄ«gi atgÅ«s, vai arÄ« neizdosies to atgÅ«t visiem dalÄ«bniekiem. Rezultātā iegÅ«tais nejauÅ”ais skaitlis ir XOR tikai tām rindām, kuras dalÄ«bnieki varēja atgÅ«t.

Parakstu slieksnis

Vēl viena pieeja nejauŔībai ir izmantot tā sauktos BLS sliekŔņa parakstus. NejauÅ”o skaitļu Ä£eneratoram, kura pamatā ir sliekŔņa paraksti, ir tieÅ”i tādas paÅ”as garantijas kā iepriekÅ” aprakstÄ«tajam uz dzÄ“Å”anas kodu balstÄ«tam algoritmam, taču tam ir ievērojami mazāks tÄ«klā nosÅ«tÄ«to ziņojumu asimptotiskais skaits katram Ä£enerētajam numuram.

BLS paraksti ir dizains, kas ļauj vairākiem dalÄ«bniekiem izveidot vienu kopÄ«gu parakstu ziņojumam. Å os parakstus bieži izmanto, lai ietaupÄ«tu vietu un joslas platumu, neprasot nosÅ«tÄ«t vairākus parakstus. 

IzplatÄ«ta BLS parakstu lietojumprogramma blokķēdes protokolos, papildus nejauÅ”u skaitļu Ä£enerÄ“Å”anai, ir bloku parakstÄ«Å”ana BFT protokolos. Pieņemsim, ka 100 dalÄ«bnieki izveido blokus, un bloks tiek uzskatÄ«ts par galÄ«gu, ja 67 no viņiem to paraksta. Viņi visi var iesniegt savas BLS paraksta daļas un izmantot kādu konsensa algoritmu, lai vienotos par 67 no tiem un pēc tam apvienotu tos vienā BLS parakstā. Lai izveidotu galÄ«go parakstu, var izmantot jebkuras 67 (vai vairāk) daļas, kas bÅ«s atkarÄ«gas no tā, kuri 67 paraksti tika apvienoti, un tāpēc var atŔķirties, lai gan dažādas 67 dalÄ«bnieku izvēles radÄ«s atŔķirÄ«gu parakstu , jebkurÅ” Ŕāds paraksts bÅ«s derÄ«gs. paraksts blokam. Pēc tam atlikuÅ”ajiem dalÄ«bniekiem tÄ«klā ir jāsaņem un jāpārbauda tikai viens paraksts, nevis 67, kas ievērojami samazina tÄ«kla slodzi.

Izrādās, ja privātās atslēgas, kuras dalÄ«bnieki izmanto, tiek Ä£enerētas noteiktā veidā, tad neatkarÄ«gi no tā, kuri 67 paraksti (vai vairāk, bet ne mazāk) tiek apkopoti, iegÅ«tais paraksts bÅ«s vienāds. To var izmantot kā nejauŔības avotu: dalÄ«bnieki vispirms vienojas par kādu ziņojumu, ko viņi parakstÄ«s (tas varētu bÅ«t RANDAO izvade vai tikai pēdējā bloka jaucējvārds, tam nav Ä«sti nozÄ«mes, ja tas mainās katru reizi un ir konsekventa) un izveidojiet tam BLS parakstu. Paaudzes rezultāts bÅ«s neprognozējams, lÄ«dz savas daļas nodroÅ”inās 67 dalÄ«bnieki, un pēc tam iznākums jau ir iepriekÅ” noteikts un nevar bÅ«t atkarÄ«gs no neviena dalÄ«bnieka darbÄ«bām.

Å Ä« pieeja nejauŔībai ir dzÄ«votspējÄ«ga, kamēr vismaz ā…” tieÅ”saistes dalÄ«bnieku ievēro protokolu, un tā ir objektÄ«va un neparedzama, kamēr vismaz ā…“ dalÄ«bnieku ievēro protokolu. Ir svarÄ«gi atzÄ«mēt, ka uzbrucējs, kurÅ” kontrolē vairāk nekā ā…“, bet mazāk nekā ā…” dalÄ«bnieku, var apturēt protokolu, bet nevar paredzēt vai ietekmēt tā izvadi.

PaÅ”i sliekŔņa paraksti ir ļoti interesanta tēma. Raksta otrajā daļā mēs detalizēti analizēsim, kā tie darbojas un kā tieÅ”i nepiecieÅ”ams Ä£enerēt dalÄ«bnieku atslēgas, lai sliekŔņa parakstus varētu izmantot kā nejauÅ”o skaitļu Ä£eneratoru.

Noslēgumā

Å is raksts ir pirmais emuāra tehnisko rakstu sērijā NEAR. NEAR ir blokķēdes protokols un platforma decentralizētu lietojumprogrammu izstrādei ar uzsvaru uz izstrādes un lietoÅ”anas ērtumu galalietotājiem.

Protokola kods ir atvērts, mÅ«su realizācija ir rakstÄ«ta Rustā, to var atrast Å”eit.

JÅ«s varat redzēt, kā izskatās NEAR izstrāde, un eksperimentēt tieÅ”saistes IDE Å”eit.

Visiem jaunumiem krievu valodā var sekot līdzi plkst telegrammu grupa un grupa vietnē VKontakte, un angļu valodā oficiālajā twitter.

Uz drīzu redzēŔanos!

Avots: www.habr.com

Pievieno komentāru