Ar įmanoma generuoti atsitiktinius skaičius, jei nepasitikime vieni kitais? 1 dalis

Sveiki, Habr!

Šiame straipsnyje kalbėsiu apie vienas kitu nepasitikinčių dalyvių pseudoatsitiktinių skaičių generavimą. Kaip pamatysime toliau, „beveik“ gerą generatorių sukurti gana paprasta, tačiau labai gerą – sunku.

Kodėl reikėtų generuoti atsitiktinius skaičius tarp dalyvių, kurie nepasitiki vienas kitu? Viena taikymo sritis yra decentralizuotos programos. Pavyzdžiui, programa, kuri priima statymą iš dalyvio ir padvigubina sumą su 49% tikimybe arba atima su 51% tikimybe, veiks tik tuo atveju, jei ji gali nešališkai gauti atsitiktinį skaičių. Jei užpuolikas gali paveikti atsitiktinių skaičių generatoriaus rezultatą ir net šiek tiek padidinti savo galimybę gauti išmoką programoje, jis lengvai ją sugriaus.

Kurdami paskirstytą atsitiktinių skaičių generavimo protokolą, norime, kad jis turėtų tris savybes:

1. Jis turi būti nešališkas. Kitaip tariant, joks dalyvis jokiu būdu neturėtų daryti įtakos atsitiktinių skaičių generatoriaus rezultatui.

2. Jis turi būti nenuspėjamas. Kitaip tariant, joks dalyvis neturėtų nuspėti, koks skaičius bus sugeneruotas (arba numanyti bet kurią jo ypatybę), prieš jį sugeneruojant.

3. Protokolas turi būti gyvybingas, tai yra, atsparus tam, kad tam tikras procentas dalyvių atsijungtų nuo tinklo arba tyčia bandytų sustabdyti protokolą.

Šiame straipsnyje apžvelgsime du būdus: RANDAO + VDF ir trynimo kodų metodą. Kitoje dalyje mes išsamiai išnagrinėsime metodą, pagrįstą slenksčio parašais.

Tačiau pirmiausia pažvelkime į paprastą ir dažnai naudojamą algoritmą, kuris yra perspektyvus, nenuspėjamas, bet šališkas.

RANDAO

RANDAO yra labai paprastas ir todėl gana dažnai naudojamas atsitiktinumo generavimo būdas. Visi tinklo dalyviai pirmiausia vietoje pasirenka pseudoatsitiktinį skaičių, tada kiekvienas dalyvis siunčia pasirinkto skaičiaus maišą. Toliau dalyviai paeiliui atskleidžia savo pasirinktus skaičius ir su atskleistais skaičiais atlieka XOR operaciją, o šios operacijos rezultatas tampa protokolo rezultatu.

Maišos paskelbimo veiksmas prieš atskleidžiant skaičius yra būtinas, kad užpuolikas negalėtų pasirinkti savo numerio, pamatęs kitų dalyvių numerius. Tai leistų jam praktiškai vienam nustatyti atsitiktinių skaičių generatoriaus išvestį.

Protokolo eigoje dalyviai turi priimti bendrą sprendimą (vadinamą konsensusą) du kartus: kada pradėti atskleisti pasirinktus skaičius ir dėl to nebepriimti maišos, o kada nustoti priimti pasirinktus skaičius ir skaičiuoti gautą atsitiktinumą. numerį. Priimti tokius sprendimus tarp vienas kitu nepasitikinčių dalyvių nėra lengva užduotis, prie to grįšime kituose straipsniuose, šiame straipsnyje manysime, kad toks sutarimo algoritmas mums yra prieinamas.

Kurias iš aukščiau aprašytų savybių turi RANDAO? Jis nenuspėjamas, turi tokį patį gyvybingumą kaip ir pagrindinis sutarimo protokolas, tačiau jis yra šališkas. Tiksliau, užpuolikas gali stebėti tinklą, o po to, kai kiti dalyviai atskleidžia savo numerius, jis gali apskaičiuoti savo XOR ir nuspręsti, ar atskleisti savo numerį, kad paveiktų rezultatą. Nors tai neleidžia užpuolikui vienam nustatyti atsitiktinių skaičių generatoriaus išvesties, jis vis tiek suteikia jam 1 bitą įtakos. Ir jei užpuolikai valdo kelis dalyvius, tada jų valdomų bitų skaičius bus lygus jų valdomų dalyvių skaičiui.

Užpuolikų įtaka gali būti labai sumažinta reikalaujant, kad dalyviai atskleistų skaičius iš eilės. Tada užpuolikas galės daryti įtaką rezultatui tik tada, kai jis bus atidarytas paskutinis. Nors įtaka žymiai mažesnė, algoritmas vis tiek yra šališkas.

RANDAO+VDF

Vienas iš būdų, kaip padaryti RANDAO nešališką, yra toks: atskleidus visus skaičius ir apskaičiavus XOR, jo rezultatas įvedamas į funkcijos įvestį, kurio skaičiavimas trunka labai ilgai, tačiau leidžia patikrinti labai greitai apskaičiuojama.

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

Ši funkcija vadinama Verifiable Delay Function arba VDF. Jei galutinio rezultato apskaičiavimas užtrunka ilgiau nei skaičių atskleidimo etapas, tai užpuolikas negalės nuspėti savo numerio rodymo ar slėpimo efekto, todėl praras galimybę daryti įtaką rezultatui.

Sukurti gerus VDF yra labai sunku. Pastaruoju metu įvyko keletas proveržių, pvz. tai и tai, Dėl to VDF praktikoje tapo praktiškesnis, o „Ethereum 2.0“ planuoja ilgalaikėje perspektyvoje naudoti RANDAO su VDF kaip atsitiktinių skaičių šaltinį. Be to, kad šis metodas yra nenuspėjamas ir nešališkas, jis turi papildomą naudą, nes yra perspektyvus, jei tinkle yra bent du dalyviai (darant prielaidą, kad naudojamas konsensuso protokolas yra perspektyvus dirbant su tokiu mažu dalyvių skaičiumi).

Didžiausias šio metodo iššūkis yra VDF nustatymas taip, kad net dalyvis, turintis labai brangią specializuotą aparatinę įrangą, negalės apskaičiuoti VDF nepasibaigus atradimo fazei. Idealiu atveju algoritmas turėtų turėti net didelę saugos ribą, tarkime, 10 kartų. Žemiau esančiame paveikslėlyje parodyta ataka, kurią įvykdė veikėjas, turintis specializuotą ASIC, leidžiančią jam paleisti VDF greičiau nei laikas, skirtas RANDAO patvirtinimui atskleisti. Toks dalyvis dar gali apskaičiuoti galutinį rezultatą naudodamas ar nenaudodamas savo numerio, o tada pagal skaičiavimą pasirinkti, rodyti jį ar ne.

Pirmiau minėtai VDF šeimai skirtos ASIC našumas gali būti 100 ir daugiau kartų didesnis nei įprastos aparatinės įrangos. Taigi, jei diegimo fazė trunka 10 sekundžių, tokiu ASIC apskaičiuotas VDF turi užtrukti daugiau nei 100 sekundžių, kad būtų 10 kartų didesnė saugos riba, taigi tas pats VDF, apskaičiuotas naudojant prekinę aparatinę įrangą, turi užtrukti 100 x 100 sekundžių = ~ 3 valandas.

Ethereum fondas planuoja išspręsti šią problemą sukurdamas savo viešai prieinamus nemokamus ASIC. Kai tai įvyks, visi kiti protokolai taip pat gali pasinaudoti šia technologija, tačiau iki tol RANDAO+VDF metodas nebus toks perspektyvus protokolams, kurie negali investuoti į savo ASIC kūrimą.

Apie VDF buvo surinkta daug straipsnių, vaizdo įrašų ir kitos informacijos ši svetainė.

Mes naudojame ištrynimo kodus

Šiame skyriuje apžvelgsime naudojamą atsitiktinių skaičių generavimo protokolą ištrinti kodus. Jis gali toleruoti iki ⅓ užpuolikų, išlikdamas gyvybingas, ir leidžia egzistuoti iki ⅔ užpuolikų, kol jie gali nuspėti ar paveikti rezultatą.

Pagrindinė protokolo idėja yra tokia. Paprastumo dėlei tarkime, kad yra lygiai 100 dalyvių. Taip pat tarkime, kad visi dalyviai lokaliai turi tam tikrą privatų raktą, o visų dalyvių viešieji raktai yra žinomi visiems dalyviams:

1. Kiekvienas dalyvis vietoje sukuria ilgą eilutę, suskaido ją į 67 dalis, sukuria trynimo kodus, kad gautų 100 bendrinimų, kad eilutei atkurti pakaktų bet kurių 67, kiekvieną iš 100 bendrinimų priskiria vienam iš dalyvių ir užšifruoja to paties dalyvio viešasis raktas. Tada visos užkoduotos akcijos paskelbiamos.

2. Dalyviai naudoja tam tikrą sutarimą, kad pasiektų susitarimą dėl koduotų rinkinių iš konkrečių 67 dalyvių.

3. Kai pasiekiamas sutarimas, kiekvienas dalyvis paima užkoduotas dalis kiekviename iš 67 rinkinių, užšifruotų jų viešuoju raktu, iššifruoja visas tokias dalis ir paskelbia visas tokias iššifruotas dalis.

4. 67 dalyviams atlikus (3) veiksmą, visi sutarti rinkiniai gali būti visiškai iškoduoti ir atkurti dėl ištrynimo kodų savybių, o galutinį skaičių galima gauti kaip pradinių eilučių, kurias dalyviai pradėjo nuo (1), XOR. .

Galima įrodyti, kad šis protokolas yra nešališkas ir nenuspėjamas. Gautas atsitiktinis skaičius nustatomas pasiekus sutarimą, bet niekam nežinomas, kol ⅔ dalyvių neiššifruoja jų viešuoju raktu užšifruotų dalių. Taigi atsitiktinis skaičius nustatomas prieš paskelbiant informaciją, kurios pakanka jam atkurti.

Kas atsitiks, jei 1 veiksme vienas iš dalyvių kitiems dalyviams išsiųs užkoduotas dalis, kurios nėra tinkamas tam tikros eilutės ištrynimo kodas? Be papildomų pakeitimų skirtingi dalyviai arba išvis negalės atkurti eilutės, arba atgaus skirtingas eilutes, todėl skirtingi dalyviai gaus skirtingą atsitiktinį skaičių. Norėdami to išvengti, galite atlikti šiuos veiksmus: kiekvienas dalyvis, be užkoduotų akcijų, dar skaičiuoja Merklos medis visas tokias dalis ir kiekvienam dalyviui siunčia ir pačią užkoduotą dalį, ir merklės medžio šaknį bei įrodymą, kad dalis įtraukta į merklių medį. Susitarus 2 veiksme, dalyviai ne tik susitaria dėl rinkinių rinkinio, bet ir dėl konkrečių tokių medžių šaknų rinkinio (jei kuris nors dalyvis nukrypo nuo protokolo ir skirtingiems dalyviams išsiuntė skirtingas medžių šaknis, ir dvi tokios šaknys parodomos konsensuso metu, jo eilutė neįtraukta į rezultatų rinkinį). Dėl bendro sutarimo turėsime 67 užkoduotas eilutes ir atitinkamas merkle medžio šaknis, kad būtų bent 67 dalyviai (nebūtinai tie patys, kurie pasiūlė atitinkamas eilutes), kurie kiekvienai iš 67 eilučių turi pranešimas su ištrynimo kodo dalimi ir įrodymas, kad jų dalis atsirado atitinkamame medyje, išnyko.

Kai (4) veiksme dalyvis iššifruoja 67 tam tikros eilutės taktus ir bando iš jų atkurti pradinę eilutę, galimas vienas iš variantų:

1. Eilutė atkuriama ir, jei ji vėl užkoduojama trynimo būdu, o Merkle medis apskaičiuojamas lokaliai apskaičiuotoms dalims, šaknis sutampa su ta, dėl kurios buvo pasiektas sutarimas.

2. Eilutė atkurta, bet lokaliai apskaičiuota šaknis nesutampa su ta, kurioje buvo pasiektas sutarimas.

3. Eilė neatkurta.

Nesunku parodyti, kad jei (1) variantas įvyko bent vienam aukščiau nurodytam dalyviui, tada (1) variantas įvyko visiems dalyviams ir atvirkščiai, jei (2) arba (3) variantas įvyko bent vienam dalyviui, tada visiems dalyviams įvyks (2) arba (3) variantas. Taigi kiekvienai rinkinio eilutei arba visi dalyviai sėkmingai ją atgaus, arba ne visi dalyviai. Tada gautas atsitiktinis skaičius yra tik tų eilučių, kurias dalyviams pavyko atkurti, XOR.

Parašų slenkstis

Kitas atsitiktinumo metodas yra naudoti vadinamuosius BLS slenksčio parašus. Atsitiktinių skaičių generatorius, pagrįstas slenksčių parašais, turi lygiai tokias pačias garantijas kaip ir anksčiau aprašytas trynimo kodu pagrįstas algoritmas, tačiau turi žymiai mažesnį asimptotinį žinučių, siunčiamų tinklu, skaičių kiekvienam sugeneruotam numeriui.

BLS parašai yra dizainas, leidžiantis keliems dalyviams sukurti vieną bendrą pranešimo parašą. Šie parašai dažnai naudojami siekiant sutaupyti vietos ir pralaidumo, nes nereikia išsiųsti kelių parašų. 

Įprasta BLS parašų programa blokų grandinės protokoluose, be atsitiktinių skaičių generavimo, yra blokinis pasirašymas BFT protokoluose. Tarkime, 100 dalyvių sukuria blokus ir blokas laikomas galutiniu, jei 67 iš jų jį pasirašo. Jie visi gali pateikti savo BLS parašo dalis ir naudoti tam tikrą konsensuso algoritmą, kad susitartų dėl 67 iš jų ir tada sujungtų jas į vieną BLS parašą. Galutiniam parašui sukurti gali būti naudojamos bet kokios 67 (ar daugiau) dalys, kurios priklausys nuo to, kurie 67 parašai buvo sujungti, todėl gali skirtis, nors skirtingi 67 dalyvių pasirinkimai sukurs skirtingą parašą , bet koks toks parašas bus galiojantis. parašas blokui. Tada likusiems dalyviams tereikia gauti ir patikrinti tik vieną parašą viename bloke, o ne 67 tinkle, o tai žymiai sumažina tinklo apkrovą.

Pasirodo, jei privatūs raktai, kuriuos naudoja dalyviai, yra sugeneruoti tam tikru būdu, nesvarbu, kurie 67 parašai (ar daugiau, bet ne mažiau) yra sumuojami, gautas parašas bus toks pat. Tai gali būti panaudota kaip atsitiktinumo šaltinis: dalyviai pirmiausia susitaria dėl kažkokio pranešimo, kurį pasirašys (tai gali būti RANDAO išvestis arba tiesiog paskutinio bloko maiša, nesvarbu, kol jis keičiasi kiekvieną kartą ir yra nuoseklus) ir sukurkite jam BLS parašą. Kartos rezultatas bus nenuspėjamas tol, kol savo dalis nepateiks 67 dalyviai, o po to produkcija jau yra iš anksto nustatyta ir negali priklausyti nuo kurio nors dalyvio veiksmų.

Šis atsitiktinumo metodas yra gyvybingas tol, kol bent ⅔ prisijungusių dalyvių laikosi protokolo, ir yra nešališkas ir nenuspėjamas tol, kol bent ⅓ dalyvių laikosi protokolo. Svarbu pažymėti, kad užpuolikas, valdantis daugiau nei ⅓, bet mažiau nei ⅔ dalyvių, gali sustabdyti protokolą, bet negali numatyti ar paveikti jo išvesties.

Patys slenksčio parašai yra labai įdomi tema. Antroje straipsnio dalyje išsamiai išanalizuosime, kaip jie veikia ir kaip tiksliai reikia sugeneruoti dalyvių raktus, kad slenksčio parašus būtų galima naudoti kaip atsitiktinių skaičių generatorių.

užbaigiant

Šis straipsnis yra pirmasis iš techninių tinklaraščio straipsnių serijos NEAR. NEAR yra blokų grandinės protokolas ir platforma, skirta decentralizuotoms programoms kurti, pabrėžiant kūrimo ir naudojimo paprastumą galutiniams vartotojams.

Protokolo kodas atviras, mūsų diegimas parašytas Rust, galima rasti čia.

Galite pamatyti, kaip atrodo NEAR plėtra, ir eksperimentuoti internetinėje IDE čia.

Visas naujienas rusų kalba galite sekti adresu telegramų grupė ir grupė „VKontakte“., o anglų kalba oficialioje „twitter“.

Greitai pasimatysime!

Šaltinis: www.habr.com