Úvod
„Generování náhodných čísel je příliš důležité na to, abychom jej ponechali náhodě“
Robert Cavu, 1970
Tento článek je věnován praktickému použití řešení, která využívají kolektivní generaci náhodných čísel v nedůvěryhodném prostředí. Stručně řečeno, jak a proč se náhoda používá v blockchainových technologiích a také o tom, jak rozlišit „dobrou“ náhodu od „špatné“. Generování skutečně náhodného čísla je extrémně složitý problém, i když se provádí na jednom počítači, a kryptografové se mu věnují již dlouho. V decentralizovaných sítích je generování náhodných čísel ještě složitější a důležitější.
Hlavně v sítích, kde si účastníci navzájem nedůvěřují, umožňuje možnost vygenerovat nepopiratelné náhodné číslo efektivně řešit řadu velmi důležitých úkolů a značně vylepšit již existující schémata. Ačkoliv hazardní hry a loterie v tomto ohledu rozhodně nejsou prioritou číslo jedna, jak by se na první pohled mohlo zdát nezkušenému čtenáři.
Generování náhodných čísel
Počítače neumějí samy o sobě generovat náhodná čísla, potřebují k tomu pomoc zvenčí. Počítač může získávat nějaké náhodné hodnoty například pomocí pohybů myši, množství využité paměti, parazitických proudů na kontaktech procesoru a mnoha dalších zdrojů, které se nazývají zdroji entropie. Tyto hodnoty nejsou zcela náhodné, protože se nacházejí v určitém rozsahu nebo mají předvídatelný charakter změn. Aby bylo možné taková čísla převést na skutečně náhodná čísla v daném rozsahu, aplikují se na ně kryptografické transformace, které z nerovnoměrně rozložených hodnot zdroje entropie odvozují rovnoměrně rozložené pseudonáhodné hodnoty. Získané hodnoty se nazývají pseudonáhodné, protože nejsou skutečně náhodné, ale jsou deterministicky odvozené z entropie. Jakýkoli dobrý kryptografický algoritmus, který šifruje data, produkuje šifrované texty, které by měly být statisticky nerozeznatelné od náhodné sekvence, takže pro výrobu náhodnosti lze použít zdroj entropie, který poskytuje pouze dobré opakovatelnost a nepředvídatelnost hodnot i v malých rozsazích, zbytek práce na rozptýlení a promíchání bitů v výsledné hodnotě si vezme na starost šifrovací algoritmus.
Abych dokončil stručný výklad, dodám, že generování náhodných čísel, i na jednom zařízení, je jedním z pilířů zajištění bezpečnosti našich dat. Vygenerovaná pseudonáhodná čísla se používají při vytváření zabezpečených připojení v různých sítích, pro generování kryptografických klíčů, pro vyvažování zátěže, kontrolu integrity a pro mnoho dalších aplikací. Bezpečnost mnoha protokolů závisí na možnosti vygenerovat spolehlivou, nepředvídatelnou náhodu zvenčí, uchovat ji a neodhalit ji do dalšího kroku protokolu, jinak bude bezpečnost ohrožena. Útok na generátor pseudonáhodných hodnot je velmi nebezpečný a ohrožuje veškerý software využívající generování náhodných hodnot.
Toto všechno byste měli vědět, pokud jste absolvovali základní kurz kryptografie, proto pokračujeme s decentralizovanými sítěmi.
Náhodnost v blockchainu
Nejprve budu hovořit o blockchainech, které podporují chytré smlouvy, protože právě ty mohou plně využít možnosti, které nabízí kvalitní nezpochybnitelná náhodnost. Dále, pro stručnost, tuto technologii nazvu “Publicly Verifiable Random Beacons” nebo PVRB. Jelikož blockchainy jsou sítě, jejichž informace může ověřit jakýkoliv účastník, klíčovou částí názvu je “Publicly Verifiable”, tedy každý, kdo si přeje, může pomocí výpočtů získat důkaz, že v blockchainu umístěné číslo má takové vlastnosti:
- Výsledek by měl mít prokazatelně rovnoměrné rozložení, tedy být založen na prokazatelně odolné kryptografii.
- Není možné kontrolovat žádný bit výsledku. V důsledku toho nelze výsledek předem předpovědět.
- Nelze sabotovat protokol generace tím, že se na něm neúčastníte, nebo přetížením sítě útočnými zprávami.
- Všechno výše uvedené musí být odolné vůči spolčení akceptovatelného počtu nečestných účastníků protokolu (např. 1/3 účastníků).
Jakákoli možnost, že se menší skupina účastníků spolčí a vyprodukuje dokonce kontrolovanou sudou/lichou náhodnost, je bezpečnostní díra. Jakákoli možnost skupiny zastavit vydávání náhodnosti je bezpečnostní díra. V zásadě je tu mnoho problémů a tato úloha není jednoduchá...
Zdá se, že nejvýznamnější aplikace pro PVRB jsou různé hry, loterie a obecně jakékoliv formy hazardu na blockchainu. Odkud skutečně se jedná o důležitý směr, ale náhodnost v blockchainech má i významnější použití. Podívejme se na ně.
Konsenzuální algoritmy
PVRB pro organizaci síťového konsensu hraje obrovskou roli. Transakce v blockchainu jsou chráněny elektronickým podpisem, takže „útok na transakci“ vždy znamená zařazení/vyřazení transakce do/bloku (nebo do několika bloků). Hlavním úkolem konsensuálního algoritmu je dohodnout se na pořadí těchto transakcí a o pořadí bloků, které tyto transakce zahrnují. Také je nezbytnou vlastností pro skutečné blockchainy finálnost — schopnost sítě dohodnout se na tom, že řetězec až po finální blok je konečný a nikdy nebude vyloučen kvůli vzniku nového fork. Obvykle je k tomu, aby se dohodlo, že blok je platný a především finální, potřeba shromáždit podpisy od většiny producentů bloků (dále BP — block-producers), což vyžaduje alespoň doručit řetězec bloků všem BP a šířit podpisy mezi všemi BP. S rostoucím počtem BP se množství potřebných zpráv v síti exponenciálně zvyšuje, proto konsensuální algoritmy, které požadují finálnost, používané například v konsensu pBFT v Hyperledgeru, nepracují potřebnou rychlostí, počínaje již několika desítkami BP, vyžadují obrovské množství spojení.
Pokud je v síti nepopiratelný a poctivý PVRB, lze na jeho základě v nejjednodušším přiblížení vybrat jednoho z producentů bloků a jmenovat ho „líderem“ během jednoho kola protokolu. Pokud máme N producentů bloků, z nichž M: M > 1/2 N jsou poctiví, necenzurují transakce a nebudují fork řetězce za účelem provádění útoku „double spend“, pak použití rovnoměrně rozloženého nepopiratelného PVRB umožní vybírat poctivého lídra s pravděpodobností M / N (M / N > 1/2). Pokud každému vedoucímu přiřadíte vlastní časový interval, během kterého může provést blok a validovat řetězec, a tyto intervaly jsou časově stejné, řetězec bloků poctivých BP bude delší než řetězec vytvořený zlovolnými BP, a algoritmus konsensu, který se spoléhá na délku řetězce, jednoduše odmítne "špatný". Tento princip přiřazování rovných časových kvant každému BP byl poprvé aplikován v Graphene (předchůdci EOS) a umožňuje většině bloků uzavírat jedním podpisem, což výrazně snižuje síťové zatížení a umožňuje tomuto konsensu fungovat extrémně rychle a stabilně. Nicméně sítě EOS nyní musí používat speciální bloky (Last Irreversible Block), které jsou potvrzeny podpisy 2/3 BP. Tyto bloky slouží k zajištění konečnosti (nemožnosti vzniku forků řetězce, které začínají před posledním Last Irreversible Block).
Také v reálných implementacích je schéma protokolu složitější — hlasování o navrhovaných blocích probíhá ve více fázích, aby se udržela činnost sítě v případě zmeškání bloků a problémů se sítí, ale i s ohledem na to algoritmy konsensu využívající PVRB vyžadují podstatně méně zpráv mezi BP, což je činí rychlejšími než tradiční PВFT nebo různé jeho modifikace.
Nejvýraznější zástupce takových algoritmů: od týmu Cardano, který, jak bylo oznámeno, má matematicky prokázanou odolnost vůči přítomnosti spiknutí mezi BP.
V Ouroboros PVRB se používá k určení tzv. "BP schedule" - rozvrhu, podle kterého je každému BP přiřazen jeho časový slot pro publikaci bloku. Velkou výhodou používání PVRB je úplná "rovnost" BP (podle velikosti jejich zůstatků). Poctivost PVRB zaručuje, že zlovolní BP nemohou kontrolovat rozvrh časových slotů a proto nemohou manipulovat s řetězcem, předem připravovat a analyzovat forky řetězce, a pro výběr forků je dostatečné spoléhat se jednoduše na délku řetězce, bez použití složitých metod výpočtu "užitečnosti" BP a "váhy" jeho bloků.
Ve všech případech, kdy je v decentralizované síti třeba zvolit náhodného účastníka, bude téměř vždy lepší volbou PVRB než deterministická varianta založená například na hash bloku. Bez PVRB možnost ovlivnit výběr účastníka vede k útokům, při nichž útočník může, vybírajíc z několika variant budoucnosti, zvolit další zkorumpovaného účastníka nebo dokonce několik, aby zajistil větší podíl na rozhodování. Použití PVRB tyto typy útoků diskredituje.
Škálování a vyvažování zátěže
PVRB může také přinést významné výhody v úlohách pro snížení zátěže a škálování plateb. Nejdříve má smysl se seznámit s Rivesty „Elektronické loterijní lístky jako mikroplatby“. Obecná myšlenka je taková, že místo toho, abychom dělali 100 plateb po 1c od plátce příjemci, můžeme hrát férovou loterii s cenou 1$ = 100c, kde plátce při každé platbě 1c předává bance jeden ze svých 100 „loterijních lístků“. Jeden z těchto lístků vyhrává bance 1$, a právě tento lístek může příjemce zapsat do blockchainu. Nejdůležitější je, že ostatních 99 lístků se předává mezi příjemcem a plátcem bez jakékoli externí účasti, prostřednictvím soukromého kanálu a jakoukoli potřebnou rychlostí. Dobré popis protokolu založeného na této schématu v síti Emercoin si můžete přečíst .
Tento systém má několik problémů, například příjemce může přestat obsluhovat plátce hned po obdržení výherního lístku, ale pro mnoho specifických aplikací, jako je minutová tariface nebo elektronické předplatné služeb, lze tyto problémy přehlédnout. Hlavním požadavkem je samozřejmě čestnost probíhající loterie, a pro její realizaci je zcela nezbytné PVRB.
Výběr náhodného účastníka je rovněž velmi důležitý pro protokoly shardingu, jejichž cílem je horizontální škálování blockchainu, což umožňuje různým BP zpracovávat pouze svůj rozsah transakcí. To je velmi složitý úkol, zvláště pokud jde o bezpečnost při spojování shardů. Poctivý výběr náhodného BP za účelem přidělení jeho odpovědnosti za konkrétní shard, stejně jako v konsensuálních algoritmech — to je rovněž úkol PVRB. V centralizovaných systémech jsou shardy přidělovány vyvažovačem, který jednoduše vypočítává hash ze žádosti a posílá ho potřebnému vykonavateli. V blockchainech může možnost ovlivnit toto přidělení vést k útokům na konsensus. Například obsah transakcí může být kontrolován útočníkem, který může ovládat, jaké transakce se dostanou do jím kontrolovaného shardu, a manipulovat s blockchainem v něm. O problému používání náhodných čísel pro úkoly shardingu v Ethereum si můžete přečíst.
Sharding je jedna z nejambicióznějších a nejserióznějších úloh v oblasti blockchainu, jejíž řešení umožní vytvářet decentralizované sítě s fantastickým výkonem a objemem. PVRB je pouze jedním z důležitých bloků pro její řešení.
Hry, ekonomické protokoly, arbitráž
Role náhodných čísel v herním průmyslu je těžké přeceňovat. Výslovné využití v online kasinech a skryté při výpočtu efektů určitých akcí hráče — to vše představuje velmi složité problémy pro decentralizované sítě, kde není možné se spolehnout na centrální zdroj náhody. Náhodný výběr může však řešit i řadu ekonomických problémů a pomáhat vytvářet jednodušší a efektivnější protokoly. Představme si, že v našem protokolu dochází ke sporům ohledně placení za nějaké levné služby, a tyto spory se vyskytují poměrně zřídka. V tomto případě, pokud existuje nepopiratelný PVRB, mohou se klienti a prodejci dohodnout na náhodném vyřešení sporů, ale se stanovenou pravděpodobností. Například s pravděpodobností 60 % vyhrává klient a s pravděpodobností 40 % — prodejce. Tento, na první pohled absurdní přístup, umožňuje automaticky řešit spory s přesně předvídatelným podílem výher/proher, který vyhovuje oběma stranám, bez zapojení třetí strany a zbytečného plýtvání časem. Navíc, poměr pravděpodobností může být dynamický a závislý na některých globálních proměnných. Například, pokud se společnosti daří dobře, zaznamenává se nízký počet sporů a vysoká návratnost, může společnost automaticky posunout pravděpodobnost vyřešení sporu ve prospěch klienta, například 70/30 nebo 80/20, a naopak, pokud spory přinášejí mnoho nákladů a jsou podvodné nebo nevhodné, lze pravděpodobnost posunout na druhou stranu.
Velké množství zajímavých decentralizovaných protokolů, jako jsou tokenem řízené registry, predikční trhy, bondové křivky a mnohé další, představují ekonomické hry, které odměňují dobré chování a trestají špatné. Často se objevují problémy se zabezpečením, přičemž ochrana před nimi si navzájem odporuje. To, co je chráněno před útoky „velryb“ s miliardami tokenů („big stake“), je zranitelné vůči útokům tisíce účtů s malými zůstatky („sybil stake“), a opatření přijatá proti jednomu typu útoku, například nelineární poplatky navržené tak, aby činily práci velkým stakem nevýhodnou, obvykle discreditují jiný typ útoku. Vzhledem k tomu, že se jedná o ekonomickou hru, lze příslušné statistické váhy vypočítat předem a jednoduše nahradit poplatky na randomizované s odpovídajícím rozložením. Takové pravděpodobnostní poplatky se realizují velmi jednoduše, pokud je v blockchainu spolehlivý zdroj náhody a nevyžadují žádné složité výpočty, což komplikuje život jak velrybám, tak sybilům.
Je však třeba mít na paměti, že kontrola nad jediným bitem v této náhodě umožňuje podvádět, když se pravděpodobnosti snižují a zvyšují dvojnásobně, takže poctivý PVRB je nejdůležitější složkou těchto protokolů.
Kde najít správnou náhodu?
Teoreticky, poctivý náhodný výběr v decentralizovaných sítích zaručuje prokazatelnou bezpečnost téměř jakéhokoli protokolu proti spiknutí. Odůvodnění je poměrně jednoduché – pokud se síť dohodne na jednom bitu 0 nebo 1, a mezi účastníky je méně než polovina nepoctivých, pak při dostatečném počtu iterací síť s pevnou pravděpodobností zaručeně dosáhne konsensu ohledně tohoto bitu. Prostě proto, že poctivá náhoda vybere 51 ze 100 účastníků v 51 % případů. Ale to je teorie, neboť v reálných sítích, aby byla zajištěna taková úroveň bezpečnosti, jako v článcích, vyžaduje velké množství zpráv mezi hostiteli, složitou vícestupňovou kryptografii, a jakékoli zkomplikování protokolu okamžitě přidává nové útočné vektory.
Právě proto dosud nevidíme v blockchainech prokazatelně odolný PVRB, který by byl dostatečně dlouho používán, aby prošel testy skutečnými aplikacemi, několika audity, zatíženími a samozřejmě skutečnými útoky, bez nichž se obtížně nazývá produkt skutečně bezpečným.
Nicméně existuje několik perspektivních přístupů, které se liší mnoha detaily, a některý z nich určitě vyřeší problém. Při současných výpočetních zdrojích je kryptografická teorie schopna velmi obratně přecházet do praktických aplikací. V budoucnu s radostí představíme implementace PVRB: v současnosti jich je několik, každá má svou sadu důležitých vlastností a zvláštností v realizaci, a za každou stojí dobrý nápad. Náhodou se zabývá jen málo týmů a zkušenosti každého z nich jsou nesmírně důležité pro všechny ostatní. Doufáme, že naše informace umožní ostatním týmům postupovat rychleji s ohledem na zkušenosti předchůdců.
Zdroj: habr.com
