Úvod
"Generovanie náhodných čísel je príliš dôležité na to, aby bolo ponechané náhode."
Robert Cavue, 1970
Tento článok je venovaný praktickej aplikácii riešení pomocou kolektívneho generovania náhodných čísel v nedôveryhodnom prostredí. Stručne povedané, ako a prečo sa náhoda používa v blockchainoch a trochu o tom, ako rozlíšiť „dobrú“ náhodu od „zlej“. Generovanie skutočne náhodného čísla je mimoriadne náročný problém, dokonca aj na jednom počítači, a kryptografi ho už dlho skúmali. V decentralizovaných sieťach je generovanie náhodných čísel ešte zložitejšie a dôležitejšie.
Práve v sieťach, kde si účastníci navzájom neveria, nám schopnosť generovať nespochybniteľné náhodné číslo umožňuje efektívne riešiť mnohé kritické problémy a výrazne zlepšiť existujúce schémy. Hazardné hry a lotérie tu navyše nie sú cieľom číslo jeden, ako sa neskúsenému čitateľovi na prvý pohľad môže zdať.
Generovanie náhodných čísel
Počítače nedokážu generovať náhodné čísla samy, na to potrebujú pomoc zvonku. Počítač môže získať určitú náhodnú hodnotu napríklad z pohybu myši, množstva použitej pamäte, bludných prúdov na kolíkoch procesora a mnohých ďalších zdrojov nazývaných zdroje entropie. Tieto hodnoty samy o sebe nie sú úplne náhodné, pretože sú v určitom rozsahu alebo majú predvídateľný vzor zmien. Aby sa takéto čísla zmenili na skutočne náhodné číslo v danom rozsahu, aplikujú sa na ne kryptotransformácie, aby sa vytvorili rovnomerne rozdelené pseudonáhodné hodnoty z nerovnomerne rozdelených hodnôt zdroja entropie. Výsledné hodnoty sa nazývajú pseudonáhodné, pretože nie sú skutočne náhodné, ale sú deterministicky odvodené od entropie. Akýkoľvek dobrý kryptografický algoritmus pri šifrovaní údajov vytvára šifrové texty, ktoré by mali byť štatisticky nerozoznateľné od náhodnej sekvencie, takže na vytvorenie náhodnosti môžete použiť zdroj entropie, ktorý poskytuje iba dobrú opakovateľnosť a nepredvídateľnosť hodnôt aj v malých rozsahoch, zvyšok práce je rozptýlenie a miešanie bitov v Výslednú hodnotu prevezme šifrovací algoritmus.
Na dokončenie krátkeho vzdelávacieho programu dodám, že generovanie náhodných čísel aj na jednom zariadení je jedným z pilierov zaistenia bezpečnosti našich dát.Vygenerované pseudonáhodné čísla sa používajú pri nadväzovaní bezpečných spojení v rôznych sieťach, na generovanie kryptografické kľúče, na vyrovnávanie záťaže, monitorovanie integrity a pre mnoho ďalších aplikácií. Bezpečnosť mnohých protokolov závisí od schopnosti vygenerovať spoľahlivý, navonok nepredvídateľný náhodný súbor, uložiť ho a neodhaliť ho až do ďalšieho kroku protokolu, inak bude bezpečnosť narušená. Útok na generátor pseudonáhodných hodnôt je mimoriadne nebezpečný a bezprostredne ohrozuje všetok softvér, ktorý používa generovanie náhodnosti.
Toto všetko by ste mali vedieť, ak ste absolvovali základný kurz kryptografie, poďme teda pokračovať o decentralizovaných sieťach.
Náhodné v blockchainoch
V prvom rade budem hovoriť o blockchainoch s podporou smart kontraktov, práve tie dokážu naplno využiť príležitosti, ktoré poskytuje kvalitná, nepopierateľná náhodnosť. Ďalej, pre stručnosť, budem túto technológiu nazývať „Verejne overiteľné náhodné majáky“ alebo PVRB. Keďže blockchainy sú siete, v ktorých si informácie môže overiť každý účastník, kľúčová časť názvu je “Publicly Verifiable”, t.j. Ktokoľvek môže použiť výpočty na získanie dôkazu, že výsledné číslo zverejnené na blockchaine má nasledujúce vlastnosti:
- Výsledok musí mať preukázateľne rovnomerné rozloženie, t. j. musí byť založený na preukázateľne silnej kryptografii.
- Nie je možné ovládať žiadny z bitov výsledku. Výsledkom je, že výsledok nemožno predvídať vopred.
- Generačný protokol nemôžete sabotovať tým, že sa nezúčastníte na protokole alebo preťažením siete správami o útoku
- Všetky vyššie uvedené musia byť odolné voči tajným dohodám s prípustným počtom nepoctivých účastníkov protokolu (napríklad 1/3 účastníkov).
Akákoľvek možnosť tajnej dohody menšej skupiny účastníkov vytvoriť čo i len kontrolovaný párny/nepárny náhod je bezpečnostnou dierou. Akákoľvek schopnosť skupiny zastaviť vydávanie náhodných čísel je bezpečnostnou dierou. Vo všeobecnosti existuje veľa problémov a táto úloha nie je jednoduchá...
Zdá sa, že najdôležitejšou aplikáciou pre PVRB sú rôzne hry, lotérie a všeobecne akýkoľvek typ hazardu na blockchaine. Toto je skutočne dôležitý smer, ale náhodnosť v blockchainoch má ešte dôležitejšie aplikácie. Pozrime sa na ne.
Konsenzuálne algoritmy
PVRB hrá obrovskú úlohu pri organizovaní konsenzu siete. Transakcie v blockchainoch sú chránené elektronickým podpisom, takže „útok na transakciu“ je vždy zahrnutie/vylúčenie transakcie do bloku (alebo niekoľkých blokov). A hlavnou úlohou konsenzuálneho algoritmu je dohodnúť sa na poradí týchto transakcií a poradí blokov, ktoré tieto transakcie obsahujú. Nevyhnutnou vlastnosťou skutočných blockchainov je tiež konečnosť – schopnosť siete súhlasiť s tým, že reťazec až po dokončený blok je konečný a nikdy nebude vylúčený z dôvodu objavenia sa nového forku. Na odsúhlasenie platnosti bločku, a hlavne konečného, je zvyčajne potrebné zozbierať podpisy od väčšiny výrobcov bločkov (ďalej len BP - výrobcovia bločkov), čo si vyžaduje minimálne dodanie blokového reťazca. všetkým BP a distribúcia podpisov medzi všetkými BP. Ako počet BP rastie, počet potrebných správ v sieti rastie exponenciálne, preto konsenzuálne algoritmy, ktoré vyžadujú konečnosť, používané napríklad v Hyperledger pBFT konsenze, nefungujú požadovanou rýchlosťou, počnúc niekoľkými desiatkami BP, ktoré vyžadujú obrovské množstvo spojení.
Ak je v sieti nepopierateľný a čestný PVRB, potom je možné aj v najjednoduchšej aproximácii na základe neho vybrať jedného z výrobcov blokov a určiť ho za „vodcu“ počas jedného kola protokolu. Ak máme N blokových výrobcov, z toho M: M > 1/2 N sú čestní, necenzurujú transakcie a nerozdvojujú reťazec, aby vykonali útok „dvojitého míňania“, potom použitie rovnomerne distribuovaného nenapadnutého PVRB umožní vybrať si čestného lídra s pravdepodobnosťou M / N (M / N > 1/2). Ak má každý vodca pridelený svoj vlastný časový interval, počas ktorého môže vytvoriť blok a overiť reťazec, a tieto intervaly sú rovnaké v čase, potom reťazec blokov čestných BP bude dlhší ako reťazec tvorený zlomyseľnými BP a konsenzus Algoritmus sa spolieha na dĺžku reťazca. jednoducho zahodí „zlý“. Tento princíp prideľovania rovnakých časových úsekov každému BP bol prvýkrát aplikovaný v Graphene (predchodca EOS) a umožňuje väčšinu blokov uzavrieť jediným podpisom, čo výrazne znižuje zaťaženie siete a umožňuje, aby tento konsenzus fungoval extrémne rýchlo a stabilne. Sieť EOS však teraz musí používať špeciálne bloky (Last Irreversible Block), ktoré sú potvrdené podpismi 2/3 BP. Tieto bloky slúžia na zabezpečenie finality (nemožnosť štartovania reťazovej vidlice pred posledným posledným nezvratným blokom).
V reálnych implementáciách je schéma protokolu komplikovanejšia - hlasovanie o navrhovaných blokoch sa vykonáva v niekoľkých fázach, aby sa zachovala sieť v prípade chýbajúcich blokov a problémov so sieťou, ale aj keď to vezmeme do úvahy, konsenzuálne algoritmy využívajúce PVRB vyžadujú podstatne menej správ medzi BP, čo umožňuje ich rýchlejšie ako tradičné PVFT, alebo jeho rôzne modifikácie.
Najvýznamnejší predstaviteľ takýchto algoritmov: z tímu Cardano, čo je vraj matematicky dokázateľné proti tajnej dohode BP.
V Ouroboros sa PVRB používa na definovanie takzvaného „rozvrhu BP“ – harmonogramu, podľa ktorého má každý BP pridelený vlastný časový úsek na zverejnenie bloku. Veľkou výhodou použitia PVRB je úplná „rovnosť“ BP (podľa veľkosti ich súvah). Integrita PVRB zaisťuje, že zlomyseľní BP nemôžu kontrolovať plánovanie časových úsekov, a preto nemôžu manipulovať s reťazou prípravou a analýzou vidlíc reťazca vopred a na výber vidlice sa stačí spoľahnúť na dĺžku reťazca, bez použitia zložitých spôsobov na výpočet „úžitku“ BP a „hmotnosti“ jeho blokov.
Vo všeobecnosti vo všetkých prípadoch, keď je potrebné vybrať náhodného účastníka v decentralizovanej sieti, je PVRB takmer vždy najlepšou voľbou, a nie deterministickou možnosťou založenou napríklad na blokovom hashove. Bez PVRB vedie možnosť ovplyvňovať voľbu účastníka k útokom, pri ktorých si útočník môže vybrať z viacerých futures, aby si vybral ďalšieho skorumpovaného účastníka, alebo viacerých naraz, aby si zabezpečil väčší podiel na rozhodovaní. Použitie PVRB diskredituje tieto typy útokov.
Škálovanie a vyrovnávanie záťaže
PVRB môže byť tiež veľkým prínosom v úlohách, ako je zníženie zaťaženia a škálovanie platieb. Na začiatok má zmysel zoznámiť sa Rivesta „Elektronické lotériové lístky ako mikroplatby“. Všeobecnou myšlienkou je, že namiesto platby 100 1c od platiteľa príjemcovi môžete hrať poctivú lotériu s cenou 1 $ = 100 c, kde platiteľ daruje banke jeden zo 1 svojich „losov“ za každého. 100c platba. Jeden z týchto lístkov vyhráva pohár 1 dolára a práve tento lístok môže príjemca zaznamenať do blockchainu. Najdôležitejšie je, že zvyšných 99 lístkov sa prenesie medzi príjemcom a platiteľom bez akejkoľvek externej účasti, cez privátny kanál a ľubovoľnou rýchlosťou. Dá sa prečítať dobrý popis protokolu založeného na tejto schéme na sieti Emercoin .
Táto schéma má niekoľko problémov, napríklad príjemca môže prestať slúžiť platiteľovi ihneď po prijatí výherného tiketu, ale v prípade mnohých špeciálnych aplikácií, ako je minútová fakturácia alebo elektronické predplatné služieb, môžu byť tieto zanedbané. Hlavnou požiadavkou je samozrejme férovosť lotérie a na jej realizáciu je PVRB absolútne nevyhnutný.
Výber náhodného účastníka je mimoriadne dôležitý aj pre protokoly shardingu, ktorých účelom je horizontálne škálovať blokový reťazec, čo umožňuje rôznym BP spracovať len svoj rozsah transakcií. Ide o mimoriadne náročnú úlohu najmä z hľadiska bezpečnosti pri spájaní črepov. Úlohou PVRB je aj spravodlivý výber náhodného BP za účelom priradenia osôb zodpovedných za konkrétny fragment, ako v konsenzuálnych algoritmoch. V centralizovaných systémoch sú shardy prideľované balancerom, ktorý jednoducho vypočíta hash z požiadavky a odošle ho požadovanému vykonávateľovi. V blockchainoch môže možnosť ovplyvniť toto zadanie viesť k útoku na konsenzus. Napríklad obsah transakcií môže ovládať útočník, môže kontrolovať, ktoré transakcie smerujú do úlomku, ktorý ovláda, a manipulovať s reťazcom blokov v ňom. Môžete si prečítať diskusiu o probléme používania náhodných čísel na shardovacie úlohy v Ethereu
Sharding je jedným z najambicióznejších a najvážnejších problémov v oblasti blockchainu, jeho riešenie umožní budovať decentralizované siete s fantastickým výkonom a objemom. PVRB je len jedným z dôležitých blokov na jeho vyriešenie.
Hry, ekonomické protokoly, arbitráže
Úlohu náhodných čísel v hernom priemysle je ťažké preceňovať. Explicitné použitie v online kasínach a implicitné použitie pri výpočte účinkov hráčovej akcie sú mimoriadne zložité problémy pre decentralizované siete, kde neexistuje spôsob, ako sa spoľahnúť na centrálny zdroj náhodnosti. Náhodný výber však môže vyriešiť aj mnohé ekonomické problémy a pomôcť vytvoriť jednoduchšie a efektívnejšie protokoly. Predpokladajme, že v našom protokole sú spory o platbe za niektoré lacné služby a tieto spory sa vyskytujú pomerne zriedka. V tomto prípade, ak existuje nesporný PVRB, zákazníci a predajcovia sa môžu dohodnúť na riešení sporov náhodne, ale s danou pravdepodobnosťou. Napríklad so 60% pravdepodobnosťou vyhrá klient a so 40% pravdepodobnosťou vyhrá predajca. Tento na prvý pohľad absurdný prístup umožňuje automaticky riešiť spory s presne predvídateľným podielom výhier/prehier, čo vyhovuje obom stranám bez akejkoľvek účasti tretej strany a zbytočného plytvania časom. Okrem toho môže byť pomer pravdepodobnosti dynamický a môže závisieť od niektorých globálnych premenných. Ak sa napríklad firme darí, má nízky počet sporov a vysokú ziskovosť, dokáže automaticky posunúť pravdepodobnosť vyriešenia sporu smerom k zákazníckej orientácii, napríklad 70/30 alebo 80/20 a naopak. ak spory vyžadujú veľa peňazí a sú podvodné alebo neadekvátne, môžete posunúť pravdepodobnosť opačným smerom.
Veľké množstvo zaujímavých decentralizovaných protokolov, ako sú registre spravované tokenmi, predikčné trhy, spojovacie krivky a mnohé ďalšie, sú ekonomickými hrami, v ktorých je dobré správanie odmeňované a zlé je penalizované. Často obsahujú bezpečnostné problémy, pre ktoré sú ochrany vo vzájomnom konflikte. To, čo je chránené pred útokom „veľryby“ s miliardami tokenov („veľký vklad“), je zraniteľné voči útokom tisícok účtov s malými zostatkami („vklad sybil“) a opatreniam prijatým proti jedinému útoku, ako napr. lineárne poplatky vytvorené na to, aby bola práca s veľkým podielom nerentabilná, sú zvyčajne zdiskreditované iným útokom. Keďže hovoríme o ekonomickej hre, príslušné štatistické váhy je možné vypočítať vopred a jednoducho nahradiť provízie náhodnými s príslušným rozdelením. Takéto pravdepodobnostné provízie sa implementujú mimoriadne jednoducho, ak má blockchain spoľahlivý zdroj náhodnosti a nevyžadujú žiadne zložité výpočty, čo sťažuje život veľrybám aj sybilám.
Zároveň je potrebné naďalej pamätať na to, že kontrola nad jedným bitom v tejto náhodnosti umožňuje podvádzať, znižovať a zvyšovať pravdepodobnosti na polovicu, takže poctivý PVRB je najdôležitejšou zložkou takýchto protokolov.
Kde nájsť tú správnu náhodu?
Teoreticky spravodlivý náhodný výber v decentralizovaných sieťach robí takmer každý protokol preukázateľne bezpečným proti tajnej dohode. Zdôvodnenie je celkom jednoduché – ak sa sieť zhodne na jedinom 0 alebo 1 bite a menej ako polovica účastníkov je nečestných, potom je pri dostatočnom počte opakovaní zaručené, že sieť dosiahne konsenzus na tomto bite s pevnou pravdepodobnosťou. Jednoducho preto, že úprimný náhodný výber vyberie 51 zo 100 účastníkov v 51 % prípadov. Ale to je teoreticky, pretože... v reálnych sieťach sa na zabezpečenie takej úrovne bezpečnosti ako v článkoch vyžaduje veľa správ medzi hostiteľmi, komplexná viacpriechodová kryptografia a akákoľvek komplikácia protokolu okamžite pridáva nové vektory útoku.
Preto zatiaľ v blockchainoch nevidíme overený odolný PVRB, ktorý by bol dostatočne dlho používaný na to, aby ho otestovali reálne aplikácie, viacnásobné audity, záťaže a samozrejme reálne útoky, bez ktorých sa dá len ťažko nazvať produkt skutočne bezpečný.
Sľubných prístupov je však viacero, líšia sa v mnohých detailoch a jeden z nich určite problém vyrieši. S modernými výpočtovými prostriedkami sa dá kryptografická teória celkom šikovne previesť do praktických aplikácií. V budúcnosti sa radi porozprávame o implementáciách PVRB: v súčasnosti ich je niekoľko, každá má svoj vlastný súbor dôležitých vlastností a implementačných prvkov a za každou sa skrýva dobrý nápad. Do randomizácie nie je zapojených veľa tímov a skúsenosti každého z nich sú mimoriadne dôležité pre všetkých ostatných. Dúfame, že naše informácie umožnia ostatným tímom postupovať rýchlejšie, berúc do úvahy skúsenosti ich predchodcov.
Zdroj: hab.com