Ahoj, Habr!
V tomto článku se budu zabývat generováním pseudo-ná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á, zatímco velmi dobrý generátor je složitější.
Proč je vlastně nutné generovat náhodná čísla účastníkům, kteří si navzájem nedůvěřují? Jednou z oblastí použití jsou decentralizované aplikace. Například aplikace, která od účastníka přijímá sázku a buď zdvojnásobuje částku s pravděpodobností 49%, nebo ji bere s 51%, bude fungovat pouze tehdy, pokud může nestranně získat náhodné číslo. Pokud útočník může nějak ovlivnit výsledek práce generátoru náhodných čísel a dokonce i lehce zvýšit svůj šance na výplatu v aplikaci, snadno ji vyprázdní.
Když vyvíjíme distribuovaný protokol pro generování náhodných čísel, chceme, aby měl tři vlastnosti:
Musí být nestranný. Jinými slovy, žádný účastník by neměl mít žádný vliv na výsledek generátoru náhodných čísel.
Musí být nepředvídatelný. Jinými slovy, žádný účastník by neměl být schopen odhadnout, které číslo bude vygenerováno (nebo odvodit jakékoli jeho vlastnosti) před tím, než bude vygenerováno.
Protokol musí být životaschopný, což znamená, že je odolný vůči situaci, kdy určité procento účastníků se odpojí od sítě nebo se pokusí protokol úmyslně zastavit.
V tomto článku se podíváme na dva přístupy: RANDAO + VDF a přístup založený na erasure codes. V následující části podrobně prozkoumáme přístup založený na threshold signaturách.
Ale nejprve si objasníme jednoduchý a často používaný algoritmus, který je životaschopný, nepředvídatelný, ale přesto zaujatý.
RANDAO
RANDAO je velmi jednoduchý a proto často používaný přístup k získávání náhodnosti. Všichni účastníci sítě nejprve lokálně vyberou pseudo-náhodné číslo, poté každý účastník odešle hash vybraného čísla. Následně účastníci postupně odhalují svá vybraná čísla a provádějí nad odkrytými čísly operaci XOR, a výsledek této operace se stává výsledkem práce protokolu.
Krok s publikováním hashů před odhalením čísel je nezbytný, aby útočník nemohl vybrat své číslo poté, co viděl čísla ostatních účastníků. To by mu ve skutečnosti umožnilo jednorázově určit výstup generátoru náhodných čísel.
Během protokolu musí účastníci dvakrát dosáhnout společného rozhodnutí (tzv. konsensu): kdy začít odhalovat vybraná čísla, a tedy přestat přijímat hash, a kdy ukončit přijímání vybraných čísel a vypočítat výsledné náhodné číslo. Přijetí takových rozhodnutí mezi účastníky, kteří si navzájem nedůvěřují, je samo o sobě složitý úkol, a k tomu se vrátíme v budoucích článcích; v tomto článku budeme předpokládat, že takový konsensuální algoritmus máme k dispozici.
Jaké vlastnosti, které jsme popsali výše, má RANDAO? Je nepředvídatelný, má stejnou životaschopnost jako protokol konsensu, na kterém je založen, ale je předpojatý. Zejména útočník může sledovat síť, a poté, co ostatní účastníci odhalí svá čísla, může vypočítat jejich XOR a rozhodnout se, zda odhalit nebo neodhalit své číslo, aby ovlivnil výsledek. Přestože to útočníkovi neumožňuje jednorázově určit výstup generátoru náhodných čísel, stále mu to poskytuje 1 bit vlivu. A pokud útočníci ovládají několik účastníků, pak bude počet kontrolovaných bitů roven počtu účastníků pod jejich kontrolou.
Vliv útočníků lze významně snížit, pokud se vyžaduje, že účastníci odhalují čísla v řadě. Poté útočník může ovlivnit výsledek pouze tehdy, když se odhalí jako poslední. Přestože je vliv značně menší, algoritmus si stále zachovává předpojatost.
RANDAO + VDF
Jednou z možností, jak učinit RANDAO nepředpojatým, je to, že po odhalení všech čísel a výpočtu XOR se výsledný výstup předkládá funkci, jejíž výpočet trvá velmi dlouho, ale umožňuje velmi rychle ověřit správnost výpočtu.
(vdf_output, vdf_proof) = VDF_compute(input) // to je velmi pomalé
correct = VDF_verify(input, vdf_output, vdf_proof) // to je velmi rychléTato funkce se nazývá Verifiable Delay Function neboli VDF. Pokud výpočet konečného výsledku trvá déle než fáze odhalení čísel, útočník nebude schopen předpovědět efekt ukázání nebo zadržení svého čísla, a tedy ztratí možnost ovlivnit výsledek.
Vývoj dobrých VDF je extrémně složitý. V poslední době došlo k několika průlomům, například a které činí VDF praktičtějšími, a Ethereum 2.0 plánuje v dlouhodobém horizontu používat RANDAO s VDF jako zdroj náhodných čísel. Kromě toho, že je tento přístup nepředvídatelný a nestranný, má také další výhodu, kterou je životaschopnost, pokud jsou v síti dostupní alespoň dva účastníci (za předpokladu, že použitý konsenzuální protokol je životaschopný při tak malém počtu účastníků).
Největší problém tohoto přístupu spočívá v nastavení VDF tak, aby ani účastník s velmi drahým specializovaným zařízením nebyl schopen vypočítat VDF do konce fáze odhalení. Ideálně by měl algoritmus mít dokonce podstatnou rezervu, řekněme 10x. Na obrázku níže je znázorněn útok účastníka, který má specializovaný ASIC, což mu umožňuje spouštět VDF rychleji, než je čas určený pro odhalení potvrzení RANDAO. Takový účastník může stále vypočítat konečný výsledek využitím i nevyužitím svého čísla a poté na základě těchto výpočtů rozhodnout, zda ho ukázat nebo ne.
Pro výše zmíněnou rodinu VDF může být výkon specializovaného ASIC více než 100krát vyšší než u běžného zařízení. Pokud tedy fáze odhalení trvá 10 sekund, VDF vypočítaná na takovém ASIC by měla trvat déle než 100 sekund, aby měla 10násobnou bezpečnostní rezervu, a tedy stejná VDF vypočítaná na běžném zařízení by měla trvat 100 x 100 sekund = přibližně 3 hodiny.
Nadace Ethereum plánuje vyřešit tento problém tím, že vytvoří vlastní veřejně dostupné bezplatné ASIC. Jakmile se to stane, budou moci všechny ostatní protokoly rovněž využívat výhod této technologie, ale do té doby přístup RANDAO + VDF nebude tak životaschopný pro protokoly, které nemohou investovat do vývoje vlastních ASIC.
Na .
Používáme vymazávací kódy
V této části se podíváme na protokol generování náhodných čísel, který používá . Může snést až ⅓ útočníků a přitom zůstává funkční, a umožňuje existenci až ⅔ útočníků, než budou schopni předpovědět nebo ovlivnit výsledek.
Hlavní myšlenka protokolu je následující. Pro zjednodušení předpokládejme, že se ho účastní přesně 100 účastníků. Předpokládejme také, že všichni účastníci mají na místě určitý soukromý klíč a veřejné klíče všech účastníků jsou známy všem účastníkům:
Každý účastník si lokálně vymyslí dlouhý řetězec, rozdělí ho na 67 částí, vytvoří vymazávací kódy tak, aby získal 100 podílů, přičemž jakýchkoli 67 je dostatečných k obnovení řetězce, a přidělí každý z 100 podílů jednomu z účastníků a šifruje je pomocí veřejného klíče toho samého účastníka. Poté jsou všechny kódované podíly publikovány.
Účastníci používají nějaký konsenzus, aby dosáhli shody o kódovaných sadách od konkrétních 67 účastníků.
Jakmile je konsenzus dosažen, každý účastník vezme kódované podíly z každé z 67 sad, zašifrované jejich veřejným klíčem, dešifruje všechny takové podíly a publikuje všechny takto dešifrované podíly.
Jakmile 67 účastníků dokončí krok (3), všechny dohodnuté sady mohou být plně dekódovány a obnoveny díky vlastnostem vymazávacích kódů, a konečné číslo může být získáno jako XOR počátečních řetězců, ze kterých účastníci začali v (1).
Lze ukázat, že tento protokol je neutrální a nepředvídatelný. Výsledné náhodné číslo je určeno až po dosažení konsensu, ale nikdo o něm neví, dokud ⅔ účastníků nerozšifruje části zašifrované jejich veřejným klíčem. Takže náhodné číslo je určeno dříve, než je zveřejněna informace dostatečná k jeho obnovení.
Co se stane, pokud na kroku (1) jeden z účastníků pošle ostatním účastníkům zašifrované podíly, které nejsou platným korekčním kódem nějakého řetězce? Bez dalších úprav různí účastníci buď nebudou schopni řetězec vůbec obnovit, nebo obnoví různé řetězce, což povede k tomu, že různí účastníci obdrží různá náhodná čísla. Aby se tomu zabránilo, lze provést následující: každý účastník, kromě zašifrovaných podílů, také vypočítává všech těchto podílů, a každému účastníku posílá jak samotný zašifrovaný podíl, tak kořen Merkleho stromu a důkaz o zahrnutí podílu do Merkleho stromu. V konsensu na kroku (2) se pak účastníci neshodují pouze na množství sad, ale na množství konkrétních kořenů těchto stromů (pokud se některý účastník odchýlil od protokolu a poslal různé kořeny Merkleho stromu různým účastníkům, a dva takové kořeny byly předloženy během konsensu, jeho řetězec není zahrnut do výsledné sady). Po dosažení konsensu budeme mít 67 zašifrovaných řetězců a jejich odpovídající kořeny Merkleho stromu, tak že existuje alespoň 67 účastníků (ne nutně těch, kteří navrhli odpovídající řetězce), kteří mají pro každý z těchto 67 řetězců zprávy s podíly korekčních kódů a důkaz o zahrnutí jejich podílu do příslušného Merkleho stromu.
Když na kroku (4) účastník dešifruje 67 podílů pro nějaký řetězec a pokusí se z nich obnovit původní řetězec, může nastat jedna z následujících možností:
Řetězec je obnoven, a pokud je poté znovu zašifrován korekčními kódy a spočítá se Merkleho strom pro lokálně spočítané podíly, kořen se shoduje s tím, na kterém byl dosažen konsensus.
Řetězec je obnoven, ale lokálně vypočtený kořen se neshoduje s tím, na kterém byl dosažen konsensus.
Řetězec se neobnoví.
Je snadné ukázat, že pokud alespoň pro jednoho účastníka nastala varianta (1), pak nastane varianta (1) i pro všechny ostatní účastníky, a naopak, pokud alespoň pro jednoho účastníka nastala varianta (2) nebo (3), pak nastane varianta (2) nebo (3) pro všechny účastníky. Takže pro každý řádek v souboru buď všichni účastníci úspěšně obnoví, nebo všichni účastníci nebudou mít možnost obnovit. Výsledné náhodné číslo je tedy XOR pouze těch řádků, které účastníci dokázali obnovit.
Prahové podpisy
Další přístup k náhodnosti spočívá v použití tzv. prahových podpisů BLS. Generátor náhodných čísel založený na prahových podpisech má přesně takové samé záruky jako výše popsaný algoritmus na bázi chybových kódů, ale má výrazně menší asymptotiku počtu zpráv, které se přenášejí po síti pro každé generované číslo.
Podpisy BLS jsou konstrukcí, která umožňuje několika účastníkům vytvářet jeden společný podpis pro zprávy. Tyto podpisy se často používají pro úsporu místa a šířky pásma, protože nevyžadují rozesílání několika podpisů.
Časté použití BLS-podpisů v protokolech blockchainu, kromě generování náhodných čísel, spočívá v podepisování bloků v protokolech BFT. Řekněme, že 100 účastníků vytváří bloky, a blok je považován za konečný, pokud jej podepíše 67 z nich. Všichni mohou předložit své části BLS-podpisu a použít nějaký konsenzusní algoritmus, aby se shodli na 67 z nich, a poté je sloučit do jednoho BLS-podpisu. Jakékoli 67 (nebo více) částí může být použito k vytvoření konečného podpisu, který závisí na těchto konkrétních 67 podepsaných, a proto se může lišit, ale i když různé výběry 67 účastníků vytvoří různý podpis, jakýkoli takový podpis bude platným podpisem pro blok. Ostatním účastníkům pak postačí obdržet po síti a ověřit pouze jeden podpis na každý blok místo 67, což výrazně snižuje zátěž na síť.
Ukazuje se, že pokud jsou soukromé klíče, které používají účastníci, generovány určitým způsobem, pak bez ohledu na to, kolik podpisů (67 nebo více, ale nejméně 67) je agregováno, výsledný podpis bude 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, skutečně na tom nezáleží, jen aby se to pokaždé měnilo a bylo dohodnuté) a vytvoří pro něj BLS-podpis. Výsledek generace bude nepředvídatelný, dokud 67 účastníků neposkytne své části, a poté už budou výstupy předem stanovené a nemohou záviset na jednání kteréhokoli účastníka.
Tento přístup k náhodnosti je životaschopný, pokud je alespoň ⅔ účastníků online a dodržují protokol, a je nestranný a nepředvídatelný, dokud alespoň ⅓ účastníků dodržuje protokol. Je důležité si všimnout, že útočník, který ovládá více než ⅓, ale méně než ⅔ účastníků, může protokol zastavit, ale nemůže předpovědět nebo ovlivnit jeho výstup.
Prahové podpisy samy o sobě jsou velmi zajímavé téma. Ve druhé části článku podrobně prozkoumáme, jak fungují a jakým způsobem je třeba generovat klíče účastníků, aby bylo možné používat prahové podpisy jako generátor náhodných čísel.
Na závěr
Tento článek je první v sérii technických článků na blogu. . NEAR je blockchainový protokol a platforma pro vývoj decentralizovaných aplikací s důrazem na jednoduchost vývoje a jednoduchost použití pro koncové uživatele.
Kód protokolu je otevřený, naše implementace je napsána v jazyce Rust, lze ji nalézt. .
Podívat se, jak vypadá vývoj na NEAR a vyzkoušet si to v online IDE, lze. .
Sledovat všechny novinky v ruštině lze v a v , a anglicky na oficiálním .
Na shledanou!
Zdroj: habr.com
