Je možné generovat náhodná čísla, když si nevěříme? Část 1

Čau Habr!

V tomto článku budu hovořit o generování pseudonáhodných čísel účastníky, kteří si navzájem nedůvěřují. Jak uvidíme níže, implementace „téměř“ dobrého generátoru je poměrně jednoduchá, ale velmi dobrý je obtížný.

Proč by bylo nutné generovat náhodná čísla mezi účastníky, kteří si navzájem nedůvěřují? Jednou aplikační oblastí jsou decentralizované aplikace. Například aplikace, která přijme sázku od účastníka a buď zdvojnásobí částku se 49% pravděpodobností, nebo odebere s 51% pravděpodobností, bude fungovat pouze v případě, že dokáže nezaujatě získat náhodné číslo. Pokud útočník dokáže ovlivnit výsledek generátoru náhodných čísel a byť jen nepatrně zvýšit svou šanci na výplatu v aplikaci, snadno ji zdevastuje.

Když navrhujeme distribuovaný protokol generování náhodných čísel, chceme, aby měl tři vlastnosti:

1. Musí být nezaujatý. Jinými slovy, žádný účastník by neměl žádným způsobem ovlivňovat výsledek generátoru náhodných čísel.

2. Musí být nepředvídatelný. Jinými slovy, žádný účastník by neměl být schopen předpovědět, jaké číslo bude vygenerováno (nebo odvodit některou z jeho vlastností), než bude vygenerováno.

3. Protokol musí být životaschopný, tedy odolný vůči tomu, že se určité procento účastníků odpojí od sítě nebo se záměrně pokusí protokol zastavit.

V tomto článku se podíváme na dva přístupy: RANDAO + VDF a přístup k vymazání kódů. V další části podrobně prozkoumáme přístup založený na prahových signaturách.

Nejprve se však podívejme na jednoduchý a běžně používaný algoritmus, který je životaschopný, nepředvídatelný, ale neobjektivní.

RANDAO

RANDAO je velmi jednoduchý a tedy zcela běžně používaný přístup ke generování náhodnosti. Všichni účastníci sítě nejprve lokálně vyberou pseudonáhodné číslo, poté každý účastník pošle hash zvoleného čísla. Dále se účastníci střídají v odhalování svých vybraných čísel a provádění operace XOR na odhalených číslech a výsledek této operace se stává výsledkem protokolu.

Krok zveřejnění hashů před odhalením čísel je nutný, aby si útočník nemohl vybrat své číslo poté, co viděl čísla ostatních účastníků. To by mu umožnilo prakticky jednou rukou určit výstup generátoru náhodných čísel.

V průběhu protokolu musí účastníci dospět ke společnému rozhodnutí (tzv. konsensu) dvakrát: kdy začít odhalovat vybraná čísla, a tedy přestat přijímat hashe, a kdy přestat přijímat vybraná čísla a počítat výsledný náhodný výsledek. číslo. Dělat taková rozhodnutí mezi účastníky, kteří si navzájem nedůvěřují, není samo o sobě snadný úkol a vrátíme se k tomu v dalších článcích, v tomto článku budeme předpokládat, že takový konsensusní algoritmus máme k dispozici.

Které z vlastností, které jsme popsali výše, má RANDAO? Je nepředvídatelný, má stejnou vitalitu jako základní konsensuální protokol, ale je zaujatý. Konkrétně může útočník pozorovat síť a poté, co ostatní účastníci odhalí svá čísla, může vypočítat jejich XOR a rozhodnout se, zda své číslo odhalí, aby ovlivnil výsledek. I když to brání útočníkovi, aby sám určil výstup generátoru náhodných čísel, stále mu to dává 1 bit vlivu. A pokud útočníci ovládají několik účastníků, pak počet bitů, které ovládají, se bude rovnat počtu účastníků pod jejich kontrolou.

Vliv útočníků lze výrazně snížit tím, že bude požadováno, aby účastníci odhalovali čísla v pořadí. Útočník pak bude moci ovlivnit výsledek pouze v případě, že bude otevřen jako poslední. I když je vliv výrazně menší, algoritmus je stále neobjektivní.

RANDAO+VDF

Jedním ze způsobů, jak učinit RANDAO nezaujatým, je tento: po odhalení všech čísel a výpočtu XOR je jeho výsledek vložen do vstupu funkce, jejíž výpočet trvá velmi dlouho, ale umožňuje vám zkontrolovat správnost výpočet velmi rychle.

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

Tato funkce se nazývá Verifiable Delay Function nebo VDF. Pokud bude výpočet konečného výsledku trvat déle než fáze zveřejnění čísla, pak útočník nebude schopen předvídat účinek zobrazení nebo skrytí svého čísla, a proto ztratí možnost výsledek ovlivnit.

Vyvinout dobré VDF je extrémně obtížné. V poslední době došlo k několika průlomům, např. tento и tento, díky čemuž je VDF praktičtější v praxi a Ethereum 2.0 plánuje dlouhodobě používat RANDAO s VDF jako zdroj náhodných čísel. Kromě skutečnosti, že tento přístup je nepředvídatelný a nezaujatý, má další výhodu v tom, že je životaschopný, pokud jsou v síti k dispozici alespoň dva účastníci (za předpokladu, že použitý konsensus protokol je životaschopný při jednání s tak malým počtem účastníků).

Největší výzvou tohoto přístupu je nastavení VDF tak, že ani účastník s velmi drahým specializovaným hardwarem nebude schopen vypočítat VDF před koncem fáze zjišťování. V ideálním případě by měl mít algoritmus dokonce významnou bezpečnostní rezervu, řekněme 10x. Obrázek níže ukazuje útok herce, který má specializovaný ASIC, který mu umožňuje spustit VDF rychleji, než je čas vyhrazený k odhalení potvrzení RANDAO. Takový účastník může i nadále spočítat konečný výsledek pomocí svého čísla či nikoli a na základě výpočtu si pak vybrat, zda jej zobrazí či nikoliv.

U výše uvedené rodiny VDF může být výkon vyhrazeného ASIC 100+krát vyšší než u běžného hardwaru. Pokud tedy fáze nasazení trvá 10 sekund, pak VDF vypočítané na takovém ASIC musí trvat déle než 100 sekund, aby bylo dosaženo 10x bezpečnostní rezervy, a tedy stejné VDF vypočítané na komoditním hardwaru musí trvat 100x 100 sekund = ~3 hodiny.

Ethereum Foundation plánuje tento problém vyřešit vytvořením vlastních veřejně dostupných bezplatných ASIC. Jakmile k tomu dojde, všechny ostatní protokoly mohou také využít této technologie, ale do té doby nebude přístup RANDAO+VDF tak životaschopný pro protokoly, které nemohou investovat do vývoje vlastních ASIC.

Mnoho článků, videí a dalších informací o VDF bylo shromážděno na na tomto webu.

Používáme mazací kódy

V této části se podíváme na protokol generování náhodných čísel, který používá mazání kódů. Dokáže tolerovat až ⅓ útočníků, přičemž zůstává životaschopný, a umožňuje existenci až ⅔ útočníků, než mohou předvídat nebo ovlivnit výsledek.

Hlavní myšlenka protokolu je následující. Pro zjednodušení předpokládejme, že účastníků je přesně 100. Předpokládejme také, že všichni účastníci lokálně mají nějaký soukromý klíč a veřejné klíče všech účastníků jsou všem účastníkům známy:

1. Každý účastník lokálně přijde s dlouhým řetězcem, rozdělí ho na 67 částí, vytvoří mazací kódy, aby získal 100 sdílení, takže k obnovení řetězce stačí libovolných 67, přiřadí každé ze 100 sdílení jednomu z účastníků a zašifruje je pomocí veřejný klíč stejného účastníka. Všechny zakódované podíly jsou poté zveřejněny.

2. Účastníci používají určitý druh konsensu k dosažení dohody o kódovaných sadách od konkrétních 67 účastníků.

3. Jakmile je dosaženo konsensu, každý účastník vezme zakódované sdílené položky v každé ze 67 sad zašifrované svým veřejným klíčem, dešifruje všechny tyto sdílené položky a všechny takto dešifrované položky zveřejní.

4. Jakmile 67 účastníků dokončí krok (3), všechny dohodnuté sady mohou být kompletně dekódovány a rekonstruovány díky vlastnostem mazacích kódů a konečný počet lze získat jako XOR počátečních řádků, se kterými účastníci začali v (1) .

Tento protokol lze ukázat jako nezaujatý a nepředvídatelný. Výsledné náhodné číslo je určeno po dosažení konsensu, ale není známo nikomu, dokud ⅔ účastníků nedekóduje části zašifrované svým veřejným klíčem. Náhodné číslo je tedy určeno před zveřejněním informací postačujících k jeho rekonstrukci.

Co se stane, když v kroku (1) jeden z účastníků odešle ostatním účastníkům zakódované sdílené položky, které nejsou správným kódem pro vymazání pro nějaký řetězec? Bez dalších změn nebudou různí účastníci buď schopni obnovit řetězec vůbec, nebo obnoví různé řetězce, což povede k tomu, že různí účastníci obdrží různá náhodná čísla. Abyste tomu zabránili, můžete udělat následující: každý účastník kromě zakódovaných podílů také počítá strom Merkla všechny takové akcie a zašle každému účastníkovi jak samotný zakódovaný podíl, tak kořen merkle stromu a důkaz o zahrnutí podílu do merkle stromu. V konsensu v kroku (2) se pak účastníci nejen dohodnou na sadě sad, ale na sadě konkrétních kořenů takových stromů (pokud se některý účastník odchýlil od protokolu a poslal různé kořeny merkle stromů různým účastníkům, a dva takové kořeny jsou zobrazeny během konsensu, jeho řádek není zahrnut do sady výsledků). V důsledku konsensu budeme mít 67 zakódovaných linií a odpovídající kořeny stromu merkle tak, že existuje alespoň 67 účastníků (ne nutně ti, kteří navrhli odpovídající linie), kteří pro každou z 67 linií mají zpráva s podílem mazacího kódu a důkaz, že výskyt jejich podílu v odpovídajícím stromu zmizel.

Když v kroku (4) účastník dešifruje 67 úderů pro určitou strunu a pokusí se z nich rekonstruovat původní strunu, je možná jedna z možností:

1. Řetězec se obnoví, a pokud je poté znovu zakódován vymazáním a Merkle strom se vypočítá pro lokálně vypočítané podíly, kořen se shoduje s tím, na kterém bylo dosaženo konsensu.

2. Řádek se obnoví, ale místně vypočítaný kořen neodpovídá tomu, na kterém bylo dosaženo konsensu.

3. Řádek není obnoven.

Je snadné ukázat, že pokud možnost (1) nastala alespoň u jednoho účastníka výše, pak možnost (1) nastala u všech účastníků, a naopak, pokud možnost (2) nebo (3) nastala alespoň u jednoho účastníka, pak pro všechny účastníky nastane možnost (2) nebo (3). Pro každý řádek v sadě jej tedy buď všichni účastníci úspěšně obnoví, nebo se jej nepodaří obnovit ani všichni účastníci. Výsledné náhodné číslo je pak XOR pouze těch řádků, které byli účastníci schopni obnovit.

Podpisy na prahu

Dalším přístupem k náhodnosti je použití toho, čemu se říká prahové signatury BLS. Generátor náhodných čísel založený na prahových signaturách má přesně stejné záruky jako výše popsaný algoritmus založený na výmazovém kódu, ale má výrazně nižší asymptotický počet zpráv odeslaných přes síť pro každé vygenerované číslo.

Podpisy BLS jsou návrhem, který umožňuje více účastníkům vytvořit jeden společný podpis pro zprávu. Tyto podpisy se často používají k úspoře místa a šířky pásma tím, že nevyžadují odesílání více podpisů. 

Běžnou aplikací pro BLS podpisy v blockchainových protokolech je kromě generování náhodných čísel blokové podepisování v BFT protokolech. Řekněme, že 100 účastníků vytvoří bloky a blok je považován za konečný, pokud jej podepíše 67 z nich. Všichni mohou odeslat své části podpisu BLS a pomocí nějakého konsensuálního algoritmu se dohodnout na 67 z nich a poté je sloučit do jednoho podpisu BLS. K vytvoření konečného podpisu lze použít libovolných 67 (nebo více) částí, což bude záviset na tom, kterých 67 podpisů bylo zkombinováno, a proto se mohou lišit, ačkoli různé volby 67 účastníků vytvoří jiný podpis, každý takový podpis bude platný. podpis pro blok. Zbývajícím účastníkům pak stačí po síti přijmout a ověřit pouze jeden podpis na blok namísto 67, což výrazně snižuje zatížení sítě.

Ukazuje se, že pokud jsou soukromé klíče, které účastníci používají, generovány určitým způsobem, pak bez ohledu na to, kterých 67 podpisů (nebo více, ale ne méně) se agreguje, bude výsledný podpis stejný. To může být použito jako zdroj náhodnosti: účastníci se nejprve dohodnou na nějaké zprávě, kterou podepíší (může to být výstup RANDAO nebo jen hash posledního bloku, na tom nezáleží, protože se pokaždé změní a je konzistentní) a vytvořte pro něj podpis BLS. Výsledek generování bude nepředvídatelný, dokud 67 účastníků neposkytne své části, a poté je výstup již předem určen a nemůže záviset na akci žádného účastníka.

Tento přístup k náhodnosti je životaschopný, pokud alespoň ⅔ účastníků online oba dodržuje protokol, a je nezaujatý a nepředvídatelný, pokud alespoň XNUMX účastníků protokol dodržuje. Je důležité si uvědomit, že útočník, který ovládá více než ⅓, ale méně než ⅔ účastníků, může zastavit protokol, ale nemůže předvídat ani ovlivnit jeho výstup.

Samotné prahové podpisy jsou velmi zajímavým tématem. V druhé části článku si podrobně rozebereme, jak fungují a jak přesně je nutné generovat účastnické klíče, aby bylo možné prahové podpisy použít jako generátor náhodných čísel.

Konečně,

Tento článek je prvním ze série technických blogových článků NEAR. NEAR je blockchain protokol a platforma pro vývoj decentralizovaných aplikací s důrazem na snadnost vývoje a snadné použití pro koncové uživatele.

Kód protokolu je otevřený, naše implementace je napsána v Rustu, lze jej najít zde.

Můžete se podívat, jak vývoj pro NEAR vypadá a experimentovat v online IDE zde.

Všechny novinky v ruštině můžete sledovat na telegramová skupina a skupina na VKontaktea v angličtině v oficiálním twitter.

Brzy se uvidíme!

Zdroj: www.habr.com