Je možné generovať náhodné čísla, ak si navzájom neveríme? Časť 1

Čau Habr!

V tomto článku budem hovoriť o generovaní pseudonáhodných čísel účastníkmi, ktorí si navzájom neveria. Ako uvidíme nižšie, implementácia „takmer“ dobrého generátora je pomerne jednoduchá, ale veľmi dobrý je ťažký.

Prečo by bolo potrebné generovať náhodné čísla medzi účastníkmi, ktorí si navzájom neveria? Jednou z oblastí použitia sú decentralizované aplikácie. Napríklad aplikácia, ktorá prijme stávku od účastníka a buď zdvojnásobí sumu so 49% pravdepodobnosťou, alebo odoberie s 51% pravdepodobnosťou, bude fungovať len vtedy, ak dokáže nezaujate získať náhodné číslo. Ak útočník dokáže ovplyvniť výsledok generátora náhodných čísel a čo i len mierne zvýšiť svoju šancu na výplatu v aplikácii, ľahko ju zdevastuje.

Keď navrhujeme distribuovaný protokol generovania náhodných čísel, chceme, aby mal tri vlastnosti:

1. Musí byť nezaujatý. Inými slovami, žiaden účastník by nemal žiadnym spôsobom ovplyvňovať výsledok generátora náhodných čísel.

2. Musí byť nepredvídateľný. Inými slovami, žiadny účastník by nemal byť schopný predpovedať, aké číslo bude vygenerované (alebo odvodiť akékoľvek jeho vlastnosti) pred jeho vygenerovaním.

3. Protokol musí byť životaschopný, teda odolný voči tomu, že sa určité percento účastníkov odpojí od siete alebo sa zámerne pokúsi protokol zastaviť.

V tomto článku sa pozrieme na dva prístupy: RANDAO + VDF a prístup k vymazaniu kódov. V ďalšej časti podrobne preskúmame prístup založený na prahových signatúrach.

Najprv sa však pozrime na jednoduchý a bežne používaný algoritmus, ktorý je životaschopný, nepredvídateľný, ale neobjektívny.

RANDAO

RANDAO je veľmi jednoduchý a teda celkom bežne používaný prístup ku generovaniu náhodnosti. Všetci účastníci siete najprv lokálne vyberú pseudonáhodné číslo, potom každý účastník pošle hash zvoleného čísla. Potom sa účastníci striedajú v odhaľovaní svojich zvolených čísel a vykonávaní operácie XOR na odhalených číslach a výsledok tejto operácie sa stáva výsledkom protokolu.

Krok zverejnenia hashov pred odhalením čísel je potrebný, aby si útočník nemohol vybrať svoje číslo po tom, čo videl čísla ostatných účastníkov. To by mu umožnilo prakticky jednou rukou určiť výstup generátora náhodných čísel.

V priebehu protokolu musia účastníci dospieť k spoločnému rozhodnutiu (tzv. konsenzu) dvakrát: kedy začať odhaľovať vybrané čísla, a teda prestať akceptovať haše, a kedy prestať akceptovať vybrané čísla a počítať výslednú náhodu. číslo. Robiť takéto rozhodnutia medzi účastníkmi, ktorí si navzájom neveria, nie je samo o sebe ľahká úloha a vrátime sa k tomu v ďalších článkoch, v tomto článku budeme predpokladať, že takýto konsenzus algoritmus máme k dispozícii.

Ktoré z vlastností, ktoré sme opísali vyššie, má RANDAO? Je nepredvídateľný, má rovnakú vitalitu ako základný konsenzuálny protokol, ale je neobjektívny. Konkrétne môže útočník pozorovať sieť a po tom, čo ostatní účastníci odhalia svoje čísla, môže vypočítať ich XOR a rozhodnúť sa, či svoje číslo odhalí alebo nie, aby ovplyvnil výsledok. Aj keď to bráni útočníkovi samostatne určiť výstup generátora náhodných čísel, stále mu to dáva 1 bit vplyvu. A ak útočníci ovládajú niekoľkých účastníkov, potom sa počet bitov, ktoré ovládajú, bude rovnať počtu účastníkov pod ich kontrolou.

Vplyv útočníkov možno výrazne znížiť požiadavkou, aby účastníci prezradili čísla v poradí. Potom bude môcť útočník ovplyvniť výsledok iba vtedy, ak bude otvorený ako posledný. Aj keď je vplyv výrazne menší, algoritmus je stále neobjektívny.

RANDAO+VDF

Jedným zo spôsobov, ako urobiť RANDAO nezaujatým, je tento: po odhalení všetkých čísel a vypočítaní XOR sa jeho výsledok vloží do vstupu funkcie, ktorej výpočet trvá veľmi dlho, ale umožňuje vám skontrolovať správnosť výpočet veľmi rýchlo.

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

Táto funkcia sa nazýva Verifiable Delay Function alebo VDF. Ak výpočet konečného výsledku trvá dlhšie ako štádium zverejnenia čísla, útočník nebude schopný predpovedať účinok zobrazenia alebo skrytia svojho čísla, a preto stratí možnosť ovplyvniť výsledok.

Vyvinúť dobré VDF je mimoriadne ťažké. V poslednej dobe došlo k niekoľkým prelomovým, napr. toto и toto, vďaka čomu je VDF v praxi praktickejší a Ethereum 2.0 plánuje z dlhodobého hľadiska používať RANDAO s VDF ako zdroj náhodných čísel. Okrem skutočnosti, že tento prístup je nepredvídateľný a nezaujatý, má ďalšiu výhodu v tom, že je životaschopný, ak sú v sieti k dispozícii aspoň dvaja účastníci (za predpokladu, že použitý konsenzuálny protokol je životaschopný, keď sa jedná o taký malý počet účastníkov).

Najväčšou výzvou tohto prístupu je nastavenie VDF tak, že ani účastník s veľmi drahým špecializovaným hardvérom nebude schopný vypočítať VDF pred koncom fázy zisťovania. V ideálnom prípade by mal mať algoritmus dokonca značnú bezpečnostnú rezervu, povedzme 10x. Obrázok nižšie zobrazuje útok herca, ktorý má špecializovaný ASIC, ktorý mu umožňuje spustiť VDF rýchlejšie, ako je čas pridelený na odhalenie potvrdenia RANDAO. Takýto účastník si stále môže vypočítať konečný výsledok s použitím alebo bez použitia svojho čísla a potom sa na základe výpočtu rozhodnúť, či ho zobrazí alebo nie.

Pre vyššie uvedenú rodinu VDF môže byť výkon dedikovaného ASIC 100+-krát vyšší ako bežný hardvér. Ak teda fáza odhalenia trvá 10 sekúnd, potom VDF vypočítané na takomto ASIC musí trvať viac ako 100 sekúnd, aby sa dosiahla 10-násobná bezpečnostná rezerva, a teda rovnaký VDF vypočítaný na komoditnom hardvéri musí trvať 100 x 100 sekúnd = ~3 hodiny.

Ethereum Foundation plánuje tento problém vyriešiť vytvorením vlastných verejne dostupných, bezplatných ASIC. Akonáhle sa to stane, všetky ostatné protokoly môžu tiež využívať túto technológiu, ale dovtedy nebude prístup RANDAO+VDF taký životaschopný pre protokoly, ktoré nemôžu investovať do vývoja vlastných ASIC.

Mnoho článkov, videí a ďalších informácií o VDF bolo zhromaždených na na tejto stránke.

Používame mazacie kódy

V tejto časti sa pozrieme na protokol generovania náhodných čísel, ktorý používa vymazanie kódov. Dokáže tolerovať až ⅓ útočníkov, pričom zostáva životaschopný, a umožňuje existenciu až ⅔ útočníkov predtým, ako môžu predvídať alebo ovplyvniť výsledok.

Hlavná myšlienka protokolu je nasledovná. Pre jednoduchosť predpokladajme, že účastníkov je presne 100. Predpokladajme tiež, že všetci účastníci lokálne majú nejaký súkromný kľúč a verejné kľúče všetkých účastníkov sú všetkým účastníkom známe:

1. Každý účastník lokálne príde s dlhým reťazcom, rozdelí ho na 67 častí, vytvorí mazacie kódy, aby získal 100 zdieľaní, takže na obnovenie reťazca stačí ľubovoľných 67, priradí každú zo 100 zdieľaní jednému z účastníkov a zašifruje ich pomocou verejný kľúč toho istého účastníka. Všetky zakódované zdieľania sú potom zverejnené.

2. Účastníci používajú určitý druh konsenzu na dosiahnutie dohody o kódovaných súboroch od konkrétnych 67 účastníkov.

3. Po dosiahnutí konsenzu každý účastník vezme zakódované zdieľania v každej zo 67 sád zašifrované svojim verejným kľúčom, dešifruje všetky takéto zdieľania a zverejní všetky takéto dešifrované zdieľania.

4. Keď 67 účastníkov dokončí krok (3), všetky dohodnuté sady môžu byť úplne dekódované a zrekonštruované vďaka vlastnostiam mazacích kódov a konečný počet možno získať ako XOR počiatočných riadkov, s ktorými účastníci začali v (1). .

Tento protokol sa môže ukázať ako nezaujatý a nepredvídateľný. Výsledné náhodné číslo sa určí po dosiahnutí konsenzu, ale nie je známe nikomu, kým ⅔ účastníkov nedekóduje časti zašifrované ich verejným kľúčom. Náhodné číslo je teda určené pred zverejnením informácií postačujúcich na jeho rekonštrukciu.

Čo sa stane, ak v kroku (1) jeden z účastníkov odošle ostatným účastníkom zakódované zdieľania, ktoré nie sú správnym kódom na vymazanie pre nejaký reťazec? Bez dodatočných zmien rôzni účastníci buď nebudú môcť reťazec obnoviť vôbec, alebo obnovia rôzne reťazce, čo bude mať za následok, že rôzni účastníci dostanú rôzne náhodné čísla. Aby ste tomu zabránili, môžete urobiť nasledovné: každý účastník okrem zakódovaných zdieľaní aj počíta Strom Merkla všetky takéto akcie a každému účastníkovi pošle zakódovanú akciu ako aj koreň merkle stromu a dôkaz o zaradení akcie do merkle stromu. V konsenze v kroku (2) sa potom účastníci nielen dohodnú na súbore súborov, ale aj na súbore konkrétnych koreňov takýchto stromov (ak sa niektorý účastník odchýlil od protokolu a poslal rôzne korene merkle stromu rôznym účastníkom, a dva takéto korene sú zobrazené počas konsenzu, jeho riadok nie je zahrnutý do sady výsledkov). V dôsledku konsenzu budeme mať 67 zakódovaných línií a zodpovedajúce korene stromu merkle tak, že existuje aspoň 67 účastníkov (nie nevyhnutne tí, ktorí navrhli zodpovedajúce línie), ktorí majú pre každú zo 67 línií správa s podielom mazacieho kódu a dôkaz, že výskyt ich podielu v príslušnom strome vybledol.

Keď v kroku (4) účastník dešifruje 67 úderov pre určitú strunu a pokúsi sa z nich rekonštruovať pôvodnú strunu, je možná jedna z možností:

1. Reťazec sa obnoví a ak sa potom znova zakóduje vymazaním a vypočíta sa Merkle strom pre lokálne vypočítané podiely, koreň sa zhoduje s tým, na ktorom sa dosiahol konsenzus.

2. Riadok sa obnoví, ale lokálne vypočítaný koreň sa nezhoduje s tým, v ktorom sa dosiahol konsenzus.

3. Riadok nie je obnovený.

Je ľahké ukázať, že ak možnosť (1) nastala aspoň pre jedného účastníka vyššie, potom možnosť (1) nastala pre všetkých účastníkov a naopak, ak možnosť (2) alebo (3) nastala aspoň pre jedného účastníka, potom pre všetkých účastníkov nastane možnosť (2) alebo (3). Pre každý riadok v súprave ho teda buď úspešne obnovia všetci účastníci, alebo sa ho nepodarí obnoviť všetkým účastníkom. Výsledné náhodné číslo je potom XOR iba tých riadkov, ktoré boli účastníci schopní obnoviť.

Prahové podpisy

Ďalším prístupom k náhodnosti je použitie toho, čo sa nazýva prahové podpisy BLS. Generátor náhodných čísel založený na prahových signatúrach má presne tie isté záruky ako algoritmus založený na vymazávacom kóde opísaný vyššie, ale má výrazne nižší asymptotický počet správ odoslaných cez sieť pre každé vygenerované číslo.

Podpisy BLS sú dizajn, ktorý umožňuje viacerým účastníkom vytvoriť jeden spoločný podpis pre správu. Tieto podpisy sa často používajú na úsporu miesta a šírky pásma tým, že nevyžadujú odosielanie viacerých podpisov. 

Bežnou aplikáciou pre BLS podpisy v blockchainových protokoloch je okrem generovania náhodných čísel aj blokové podpisovanie v BFT protokoloch. Povedzme, že 100 účastníkov vytvorí bloky a blok sa považuje za konečný, ak ho podpíše 67 z nich. Všetci môžu odoslať svoje časti podpisu BLS a použiť nejaký konsenzuálny algoritmus na odsúhlasenie 67 z nich a potom ich zlúčiť do jedného podpisu BLS. Na vytvorenie konečného podpisu možno použiť ľubovoľných 67 (alebo viac) častí, čo bude závisieť od toho, ktorých 67 podpisov bolo skombinovaných, a preto sa môžu líšiť, hoci rôzne voľby 67 účastníkov vytvoria odlišný podpis, každý takýto podpis bude platný. podpis pre blok. Zvyšným účastníkom potom stačí prijať a overiť len jeden podpis na blok namiesto 67 cez sieť, čo výrazne znižuje zaťaženie siete.

Ukazuje sa, že ak sú súkromné ​​kľúče, ktoré účastníci používajú, vygenerované určitým spôsobom, potom bez ohľadu na to, ktorých 67 podpisov (alebo viac, ale nie menej) sa agreguje, výsledný podpis bude rovnaký. Toto možno použiť ako zdroj náhodnosti: účastníci sa najprv dohodnú na nejakej správe, ktorú podpíšu (môže to byť výstup RANDAO alebo len hash posledného bloku, na tom nezáleží, pokiaľ sa zakaždým zmení a je konzistentný) a vytvorte preň podpis BLS. Výsledok generovania bude nepredvídateľný, kým svoje časti neposkytne 67 účastníkov a potom je výstup už vopred určený a nemôže závisieť od akcií žiadneho účastníka.

Tento prístup k náhodnosti je životaschopný, pokiaľ aspoň ⅔ účastníkov online dodržiava protokol a je nezaujatý a nepredvídateľný, pokiaľ ho dodržiava aspoň XNUMX/XNUMX účastníkov. Je dôležité poznamenať, že útočník, ktorý ovláda viac ako ⅓, ale menej ako ⅔ účastníkov, môže zastaviť protokol, ale nemôže predvídať ani ovplyvniť jeho výstup.

Samotné prahové podpisy sú veľmi zaujímavou témou. V druhej časti článku si podrobne rozoberieme, ako fungujú a ako presne je potrebné generovať účastnícke kľúče, aby sa prahové podpisy dali použiť ako generátor náhodných čísel.

na záver

Tento článok je prvým zo série technických blogových článkov NEAR. NEAR je blockchain protokol a platforma pre vývoj decentralizovaných aplikácií s dôrazom na jednoduchosť vývoja a jednoduché použitie pre koncových používateľov.

Kód protokolu je otvorený, naša implementácia je napísaná v Ruste, dá sa nájsť tu.

Môžete vidieť, ako vyzerá vývoj pre NEAR a experimentovať v online IDE tu.

Všetky novinky v ruštine môžete sledovať na telegramová skupina a skupina na VKontaktea v oficiálnom jazyku v angličtine cvrlikání.

Uvidíme sa skoro!

Zdroj: hab.com