Úvod
„Generácia náhodných čísel je príliš dôležitá na to, aby sme ju nechali na náhodu“
Robert Cahill, 1970
Tento článok je venovaný praktickému uplatneniu riešení, ktoré používajú kolektívnu generáciu náhodných čísel v nedôveryhodnom prostredí. Krátko povedané — ako a na čo sa používa náhodnosť v blockchaine a trochu o tom, ako rozlíšiť „dobrú“ náhodnosť od „zlých“. Generovanie naozaj náhodného čísla je mimoriadne zložitý problém, aj na samostatnom počítači, a už dlhú dobu sa ním zaoberajú kryptografi. V decentralizovaných sieťach je generácia náhodných čísel ešte zložitejšia a dôležitejšia.
Práve v sieťach, kde si účastníci navzájom neveria, možnosť vygenerovať nepopierateľné náhodné číslo efektívne rieši množstvo dôležitých úloh a významne zlepšuje už existujúce schémy. Hranie hazardných hier a lotérie tu však vôbec nie sú konečným cieľom, ako by sa na prvý pohľad mohlo zdať nezasvätenému čitateľovi.
Generácia náhodných čísel
Počítače samy nevedia generovať náhodné čísla, na to potrebujú pomoc zvonka. Počítač môže získať nejakú náhodnú hodnotu napríklad pomocou pohybov myši, množstva použitej pamäte, parazitných prúdov na kontaktoch procesora a mnohých ďalších zdrojov, nazývaných zdroje entropie. Tieto hodnoty nie sú úplne náhodné, pretože sa nachádzajú v určitom rozsahu alebo majú predvídateľný charakter zmien. Aby sa také čísla premenili na skutočne náhodné číslo v danom rozsahu, používajú sa kryptologické transformácie, aby sa z nerovnomerne rozdelených hodnôt zdrojov entropie získali rovnomerne rozdelené pseudonáhodné hodnoty. Získané hodnoty sa nazývajú pseudonáhodné, pretože nie sú skutočne náhodné, ale deterministicky vyrobené z entropie. Každý dobrý kryptologický algoritmus, šifrujúci dáta, produkuje šifrované texty, ktoré by štatisticky mali byť nerozoznateľné od náhodnej sekvencie, takže na generovanie náhody môžete brať zdroj entropie, ktorý zabezpečuje len dobrú neopakovateľnosť a nepredvídateľnosť hodnôt, aj v malých rozsahoch, zvyšok práce na rozptyle a premiešaní bitov v výslednej hodnote prevedie šifrovací algoritmus.
Aby som uzavrel krátku lekciu, dodám, že generovanie náhodných čísel, ba ani na jednom zariadení, nie je len jedným zo základných pilierov zabezpečenia našich dát, generované pseudonáhodné čísla sa používajú pri nadviazaní zabezpečených spojení v rôznych sieťach, na generovanie kryptografických kľúčov, na vyváženie zaťaženia, kontrolu integrity a ešte pre množstvo ďalších aplikácií. Bezpečnosť mnohých protokolov závisí od možnosti vygenerovať spoľahlivú, nepredvídateľnú náhodu zvonka, uchovať ju a nezverejniť ju do ďalšieho kroku protokolu, inak bude bezpečnosť ohrozená. Útok na generátor pseudonáhodných hodnôt je mimoriadne nebezpečný a ohrozuje všetok softvér, ktorý využíva generovanie náhodných čísel.
Všetko toto by ste mali vedieť, ak ste absolvovali základný kurz o kryptografii, takže pokračujeme v diskusii o decentralizovaných sieťach.
Náhodnosť v blockchains
Najskôr sa budem rozprávať o blockchains s podporou smart kontraktov, práve tie môžu naplno využiť možnosti, ktoré poskytuje kvalitná nepopierateľná náhodnosť. Ďalej, pre stručnosť, budem túto technológiu nazývať “Publicly Verifiable Random Beacons” alebo PVRB. Keďže blockchains sú siete, ktorých informácie môže overiť každý účastník, kľúčovou časťou názvu je “Publicly Verifiable”, t.j. každý, kto chce, môže pomocou výpočtov získať dôkaz, že získané číslo, umiestnené v blockchaine, má tieto vlastnosti:
- Výsledok musí mať dokazateľne rovnomerné rozdelenie, t.j. musí byť založený na dokazateľne odolnej kryptografii.
- Nie je možné kontrolovať ani jeden z bitov výsledku. V dôsledku toho nie je možné výsledok predpovedať.
- Nie je možné sabotovať protokol generovania pomocou neúčasti v protokole alebo preťažením siete útočnými správami.
- Všetko vyššie uvedené musí byť odolné voči dohodám tolerovateľného počtu nespoľahlivých účastníkov protokolu (napríklad 1/3 účastníkov).
Akákoľvek možnosť zhodnutej menšej skupiny účastníkov vyprodukovat aj kontrolovanú párnu/nepárnu náhodnosť — je bezpečnostná diera. Akákoľvek možnosť skupiny zastaviť vystavovanie náhodnosti — je bezpečnostná diera. Všeobecne povedané, problémov je veľa a táto úloha nie je jednoduchá...
Zdá sa, že najdôležitejšia aplikácia pre PVRB sú rôzne hry, lotérie a vlastne akékoľvek formy hazardu na blockchaine. Naozaj, je to dôležitý smer, ale náhodnosť v blockchains má aj významnejšie aplikácie. Poďme sa na ne pozrieť.
Algoritmy konsenzu
PVRB pre organizáciu sieťového konsenzu zohráva obrovskú úlohu. Transakcie v blockchains sú chránené elektronickým podpisom, preto „útok na transakciu“ znamená vždy zahrnutie/vylúčenie transakcie do bloku (alebo do niekoľkých blokov). Hlavnou úlohou konsenzusného algoritmu je dohodnúť sa na poradí týchto transakcií a na poradí blokov, ktoré obsahujú tieto transakcie. Rovnako nevyhnutnou vlastnosťou pre reálne blockchains je finálnosť — schopnosť siete dohodnúť sa na tom, že reťazec až po finálny blok je konečný a nikdy nebude vylúčený kvôli objaveniu nového fork-u. Zvyčajne, aby sa dohodlo, že blok je platný a, čo je najdôležitejšie, finálny, je potrebné získať podpisy od väčšiny výrobcov blokov (ďalej BP — block-producers), čo si vyžaduje minimálne preniesť reťazec blokov na všetky BP a podpisy rozšíriť medzi všetými BP. Pri raste počtu BP exponenciálne rastie počet potrebných správ v sieti, preto algoritmy konsenzu, ktoré vyžadujú finálnosť, použité napríklad v pBFT-konsenze Hyperledger, nefungujú s potrebnou rýchlosťou, začínajúc už od niekoľkých desiatok BP, vyžadujúc obrovské množstvo pripojení.
Ak v sieti existuje nepopierateľný a čestný PVRB, potom aj v najjednoduchšom prístupe je možné na jeho základe vybrať jedného z block producers a určiť ho za „lídera“ počas jedného kola protokolu. Ak máme N block producer-ov, z ktorých M: M > 1/2 N sú čestní, necenzurujú transakcie a nevytvárajú forky reťaze s cieľom uskutočniť útok „double spend“, potom použitie rovnomerne rozdeleného nepopierateľného PVRB umožní vybrať čestného lídra s pravdepodobnosťou M / N (M / N > 1/2). Ak každému lídrovi priradíme vlastný časový interval, počas ktorého môže vytvoriť blok a validovať reťazec, a tieto intervaly sú časovo rovnaké, reťaz blokov čestných BP bude dlhšia ako reťaz vytvorená zlovestnými BP, a konsenzuálny algoritmus, ktorý sa spolieha na dĺžku reťazca, jednoducho odmietne „zlú“. Tento princíp prideľovania rovnakých časových kvant každému BP bol prvýkrát aplikovaný v Graphene (predchodcovi EOS) a umožňuje väčšine blokov uzatvárať jedným podpisom, čo výrazne znižuje sieťovú záťaž a umožňuje tomuto konsenzu fungovať extrémne rýchlo a stabilne. Napriek tomu sa sieť EOS v súčasnosti musí uchýliť k špeciálnym blokom (Last Irreversible Block), ktoré sú potvrdené podpismi 2/3 BP. Tieto bloky slúžia na zabezpečenie finálnosti (impossibility of a chain fork starting before the last Last Irreversible Block).
Tiež, v reálnych implementáciách, je schéma protokolu zložitejšia – hlasovanie o navrhovaných blokoch sa uskutočňuje v niekoľkých etapách, aby udržalo činnosť siete v prípade vynechania blokov a problémov so sieťou, ale aj s ohľadom na to, algoritmy konsenzu využívajúce PVRB vyžadujú podstatne menej správ medzi BP, čo ich umožňuje rýchlejšie ako tradičný PВFT alebo rôzne jeho modifikácie.
Najvýraznejší zástupca takýchto algoritmov: od tímu Cardano, ktorý, ako bolo oznámené, má matematicky dokázateľnú odolnosť voči prítomnosti sprisahania medzi BP.
V Ouroboros PVRB sa používa na určenie takzvaného „BP schedule“ — rozvrhu, podľa ktorého je každému BP priradený jeho časový slot na publikovanie bloku. Veľkou výhodou používania PVRB je úplné „rovnoprávnosť“ BP (podľa veľkosti ich zostatkov). Čestnosť PVRB zaručuje, že zlovestné BP nemôžu kontrolovať rozvrh časových slotov, a preto nemôžu manipulovať s reťazcom, vopred pripravujúc a analyzujúc forky reťazca, a na výber fork stačí spoľahnúť sa jednoducho na dĺžku reťazca, bez manipulácií s rafinovanými spôsobmi výpočtu „užitočnosti“ BP a „váhy“ jeho blokov.
Vo všetkých prípadoch, keď je potrebné zvoliť náhodného účastníka v decentralizovanej sieti, bude takmer vždy najlepšou voľbou PVRB, a nie deterministická varianta založená napríklad na hashi bloku. Bez PVRB možnosť ovplyvniť výber účastníka vedie k vzniku útokov, v ktorých útočník môže, vyberajúc z niekoľkých možností budúcnosti, zvoliť nasledujúceho skorumpovaného účastníka alebo rovno niekoľkých, aby zabezpečil väčší podiel na rozhodovaní. Použitie PVRB diskredituje tieto typy útokov.
Škálovanie a vyvažovanie záťaže
PVRB môže priniesť vážne výhody aj v úlohách na zníženie záťaže, škálovanie platieb. Najprv stojí za to oboznámiť sa s Rivestom "Electronic Lottery Tickets as Micropayments". Základná myšlienka spočíva v tom, že namiesto toho, aby ste vykonali 100 platieb po 1c od platiča príjemcovi, môžete sa zúčastniť spravodlivej lotérie s cenou 1$ = 100c, kde platič pri každej platbe 1c odovzdáva banke jeden zo svojich 100 "lotériových lístkov". Jeden z týchto lístkov vyhrá banke 1$, a práve tento lístok môže príjemca zaznamenať v blockchaine. Najdôležitejšie je, že ostatných 99 lístkov sa prenáša medzi príjemcom a platičom bez akéhokoľvek vonkajšieho zásahu, prostredníctvom súkromného kanála a akoukoľvek potrebnou rýchlosťou. Dobré opísanie protokolu na základe tejto schémy v sieti Emercoin si môžete prečítať .
Táto schéma má niekoľko problémov, napríklad príjemca môže prestať obsluhovať platiča ihneď po obdržaní výherného lístka, ale pre mnoho špeciálnych aplikácií, ako je cenová štruktúra na minútu alebo elektronické predplatné na služby, je možné na ne zabudnúť. Hlavným požiadavkom je samozrejme čestnosť vykonávanej lotérie, a na jej uskutočnenie je nevyhnutný PVRB.
Výber náhodného účastníka je mimoriadne dôležitý aj pre protokoly shardingu, ktorého cieľom je horizontálne škálovanie blockchainu, čo umožňuje rôznym BP spracovávať len svoj rozsah transakcií. Je to veľmi zložitá úloha, najmä pokiaľ ide o bezpečnosť pri spájaní shardov. Spravodlivý výber náhodného BP na určenie jeho zodpovednosti za konkrétny shard, rovnako ako v konsenzuálnych algoritmoch — to je tiež úloha PVRB. V centralizovaných systémoch sa shardové jednotky priraďujú vyvážovačom, ktorý jednoducho vypočíta hash požiadavky a odošle ho potrebnému vykonávateľovi. V blockchainoch môže mať ovplyvnenie tohto priradenia za následok útok na konsenzus. Napríklad, obsah transakcií môže byť kontrolovaný útočníkom, ktorý môže ovplyvňovať, ktoré transakcie sa dostanú do jeho ovládaného shardu a manipulovať s blockchainom v ňom. Diskusiu o probléme použitia náhodných čísel pre úlohy shardingu v Ethereu si môžete prečítať.
Sharding je jedna z najambicióznejších a najvážnejších úloh v oblasti blockchainu, jej riešenie umožní budovať decentralizované siete fantastického výkonu a objemu. PVRB je len jedným z dôležitých blokov na jej riešenie.
Hry, ekonomické protokoly, arbitráž
Úloha náhodných čísel v hernom priemysle je ťažko preceňovať. Ich jasné využitie v online kasínach a nepriame v hodnotení účinkov akéhokoľvek hráčskeho rozhodnutia predstavujú veľmi zložitý problém pre decentralizované siete, kde nie je možné sa spoľahnúť na centrálny zdroj náhodnosti. Avšak, náhodný výber môže riešiť množstvo ekonomických problémov a pomáhať pri vytváraní jednoduchších a efektívnejších protokolov. Predpokladajme, že v našom protokole sa vyskytujú spory týkajúce sa platieb za niektoré lacné služby, a tieto spory nastávajú dosť zriedka. V tomto prípade, ak existuje nepopierateľný PVRB, klienti a predajcovia sa môžu dohodnúť na náhodnom riešení sporov s vopred stanovenou pravdepodobnosťou. Napríklad, s pravdepodobnosťou 60 % vyhrá klient a s pravdepodobnosťou 40 % vyhrá predajca. Takýto na prvý pohľad absurdný prístup umožňuje automaticky riešiť spory s presne predvídateľným pomerom výhier/prehier, čo vyhovuje obom stranám bez akejkoľvek účasti tretej strany a zbytočnej straty času. Navyše, pomer pravdepodobností môže byť dynamický a závisieť od niektorých globálnych premenných. Napríklad, ak má spoločnosť dobré výsledky, zaznamenáva sa nízky počet sporov a vysoká návratnosť, spoločnosť môže automaticky posunúť pravdepodobnosť riešenia sporu smerom k orientácii na klientov, napríklad 70/30 alebo 80/20, a naopak, ak spory spôsobujú veľké finančné straty a sú podvodné alebo neadekvátne, môžu sa posúvať pravdepodobnosti na opačnú stranu.
Existuje množstvo zaujímavých decentralizovaných protokolov, ako sú tokenom kurátorované registre, predikčné trhy, bonding curves a mnohé ďalšie, ktoré predstavujú ekonomické hry odmeňujúce dobré správanie a trestajúce zlé. Často sa tu objavujú bezpečnostné problémy, pričom opatrenia na ochranu pred nimi si navzájom odporujú. To, čo je chránené pred útokom „veľryb“ s miliardami tokenov („big stake“), je zraniteľné voči útokom tisícky účtov s malými zostatkami („sybil stake“), a opatrenia prijaté proti jednému typu útoku, ako napríklad nelineárne poplatky vytvorené na účely znepríjemnenia práce veľkým stakerom, sú zvyčajne diskreditované iným útokom. Keďže ide o ekonomickú hru, príslušné štatistické váhy sa dajú vypočítať vopred a jednoducho nahradiť poplatky náhodne generovanými s príslušným rozdelením. Takéto pravdepodobnostné poplatky sa implementujú veľmi jednoducho, ak existuje v blockchain-e spoľahlivý zdroj náhody a nevyžadujú žiadne zložené výpočty, čím sťažujú život aj veľrybám, aj sybilom.
Je potrebné si však naďalej pamätať, že kontrola nad jediným bitom v tejto náhode umožňuje podvádzať, zmenšovať a zvyšovať pravdepodobnosti v dvojnásobku, takže čestný PVRB je najdôležitejšou súčasťou takýchto protokolov.
Kde nájsť správnu náhodu?
Teoreticky, čestný náhodný výber v decentralizovaných sieťach umožňuje zabezpečiť dokazateľnú bezpečnosť takmer každého protokolu pred sprisahaním. Odôvodnenie je pomerne jednoduché — ak sieť súhlasí s jedným bitom 0 alebo 1, a medzi účastníkmi je menej ako polovica nečestných, potom pri dostatočnom počte iterácií sieť zaručene dospeje k konsenzu o tomto bite s pevnou pravdepodobnosťou. Proste preto, že čestná náhoda bude vyberať 51 z 100 účastníkov v 51% prípadoch. Ale to je teoretické, pretože v reálnych sieťach, na zabezpečenie takej úrovne bezpečnosti, aká je v článkoch, je potrebných množstvo správ medzi hostiteľmi, zložitá viacstupňová kryptografia a akékoľvek skomplikovanie protokolu okamžite pridáva nové vektory útokov.
Preto zatiaľ nevidíme v blockchainoch overene odolný PVRB, ktorý by bol používaný dostatočne dlhý čas na to, aby prešiel testovaním skutočnými aplikáciami, viacerými auditmi, záťažami a samozrejme aj reálnymi útokmi, bez ktorých je ťažké nazvať produkt naozaj bezpečným.
Napriek tomu existuje niekoľko perspektívnych prístupov, ktoré sa líšia množstvom detailov a niektorý z nich určite vyrieši problém. Pri súčasných výpočtových zdrojoch dokáže kryptografická teória celkom šikovne prechádzať do praktických aplikácií. V budúcnosti s radosťou poskytneme informácie o implementáciách PVRB: teraz ich je niekoľko, pričom každá má svoj vlastný súbor dôležitých vlastností a osobitosti v implementácii a za každou stojí dobrý nápad. Ransom v súčasnosti rieši len zopár tímov a skúsenosti každého z nich sú nesmierne dôležité pre ostatných. Dúfame, že naše informácie umožnia ostatným tímom urýchliť proces s ohľadom na skúsenosti predchodcov.
Zdroj: habr.com
