Je možné generovať náhodné čísla, ak si navzájom neveríme? Časť 2

Čau Habr!

В prvá časť V tomto článku sme diskutovali o tom, prečo by mohlo byť potrebné generovať náhodné čísla pre účastníkov, ktorí si navzájom neveria, aké požiadavky sa kladú na takéto generátory náhodných čísel a zvažovali sme dva prístupy k ich implementácii.

V tejto časti článku sa bližšie pozrieme na ďalší prístup, ktorý využíva prahové podpisy.

Trochu kryptografie

Aby ste pochopili, ako prahové podpisy fungujú, musíte pochopiť trochu základnej kryptografie. Budeme používať dva pojmy: skaláre alebo jednoducho čísla, ktoré budeme označovať malými písmenami (x, y) a body na eliptickej krivke, ktoré budeme označovať veľkými písmenami.

Aby ste pochopili základy prahových podpisov, nemusíte okrem niekoľkých základných vecí rozumieť tomu, ako fungujú eliptické krivky:

1. Body na eliptickej krivke môžeme sčítať a násobiť skalárom (násobenie skalárom budeme označovať ako xG, hoci zápis Gx tiež často používané v literatúre). Výsledkom sčítania a násobenia skalárom je bod na eliptickej krivke.

2. Poznať iba pointu G a jeho súčin so skalárom xG nemožno vypočítať x.

Použijeme aj pojem polynóm p(x) stupňa k-1. Využijeme najmä nasledujúcu vlastnosť polynómov: ak poznáme hodnotu p(x) pre akékoľvek k rozdielny x (a nemáme žiadne ďalšie informácie p(x)), môžeme vypočítať p(x) pre kohokoľvek iného x.

Je zaujímavé, že pre akýkoľvek polynóm p(x) a nejaký bod na krivke Gpoznaním významu p(x)G pre akékoľvek k rôzne významy x, vieme aj vypočítať p(x)G pre akékoľvek x.

Toto je dostatok informácií na to, aby ste sa dostali do podrobností o tom, ako fungujú prahové podpisy a ako ich použiť na generovanie náhodných čísel.

Generátor náhodných čísel na prahových podpisoch

Povedzme si to n účastníci chcú vygenerovať náhodné číslo a chceme, aby sa ho zúčastnil každý k bolo ich dosť na to, aby vygenerovali počet, ale aby útočníci, ktorí ovládajú k-1 alebo menej účastníkov nedokázalo predpovedať ani ovplyvniť vygenerovaný počet.

Predpokladajme, že existuje taký polynóm p(x) stupňa k-1 čo vie prvý účastník p (1), ten druhý vie p(2), a tak ďalej (n- vie p(n)). Tiež predpokladáme, že pre nejaký vopred určený bod G každý vie p(x)G pre všetky hodnoty x. Zavoláme p(i) „súkromný komponent“ iúčastník (len preto, že iúčastník ju pozná) a p(i)G "verejná zložka" i-tá účastníčka (pretože ju poznajú všetci účastníci). Ako si pamätáte, vedomosti p(i)G nestačí obnoviť p(i).

Vytvorenie takéhoto polynómu tak, že iba i-Prvý účastník a nikto iný nepoznal jeho súkromnú zložku - toto je najzložitejšia a najzaujímavejšia časť protokolu a budeme ju analyzovať nižšie. Zatiaľ predpokladajme, že máme takýto polynóm a všetci účastníci poznajú svoje súkromné ​​komponenty.

Ako môžeme použiť takýto polynóm na generovanie náhodného čísla? Na začiatok potrebujeme nejaký reťazec, ktorý predtým nebol použitý ako vstup do generátora. V prípade blockchainu hash posledného bloku h je dobrým kandidátom na takúto líniu. Umožnite účastníkom vytvoriť náhodné číslo pomocou h ako semeno. Účastníci konvertujú ako prví h do bodu na krivke pomocou akejkoľvek preddefinovanej funkcie:

H = skalárnyToPoint(h)

Potom každý účastník i vypočítava a zverejňuje Ahoj = p(i)H, čo môžu robiť, pretože vedia p(i) a H. prezradenie HNedovoľujem ostatným účastníkom obnoviť súkromný komponent iúčastníka, a preto je možné z bloku do bloku použiť jednu sadu súkromných komponentov. Takže nákladný algoritmus generovania polynómov opísaný nižšie je potrebné vykonať iba raz.

Kedy k účastníci boli pitvaní Ahoj = p(i)H, každý vie vypočítať Hx = p(x)H pre všetkých x vďaka vlastnosti polynómov, o ktorej sme hovorili v minulej časti. V tejto chvíli všetci účastníci kalkulujú H0 = p(0)H, a toto je výsledné náhodné číslo. Upozorňujeme, že nikto nevie p(0), a teda jediný spôsob výpočtu p(0)H – toto je interpolácia p(x)H, čo je možné len vtedy k hodnoty p(i)H známy. Otváranie akéhokoľvek menšieho množstva p(i)H neposkytuje žiadne informácie o p(0)H.

Vyššie uvedený generátor má všetky vlastnosti, ktoré chceme: iba kontrolu útočníkov k-1 alebo menej účastníkov nemá žiadne informácie ani vplyv na záver, kým žiadne k účastníci môžu vypočítať výsledné číslo a akúkoľvek jeho podmnožinu k účastníci vždy dospejú k rovnakému výsledku pre rovnaké semienko.

Je tu jeden problém, ktorému sme sa vyššie opatrne vyhli. Aby interpolácia fungovala, je dôležité, aby hodnota Hi, ktorý zverejnil každý účastník i naozaj to bolo to isté p(i)H. Keďže nikto okrem i-ty účastník nevie p(i), nikto okrem i-účastník to nemôže overiť Hi skutočne vypočítané správne a bez akéhokoľvek kryptografického dôkazu správnosti HÚtočník môže zverejniť akúkoľvek hodnotu ako Ahoj, a ľubovoľne ovplyvňovať výstup generátora náhodných čísel:

Rôzne hodnoty H_1 odoslané prvým účastníkom vedú k rôznym výsledným H_0

Existujú minimálne dva spôsoby, ako dokázať správnosť Hi, zvážime ich po analýze generovania polynómu.

Generovanie polynómu

V poslednej časti sme predpokladali, že takýto polynóm máme p(x) stupňa k-1 že účastník i vie, p(i)a nikto iný nemá žiadne informácie o tejto hodnote. V ďalšej časti to budeme potrebovať aj pre nejaký vopred určený bod G každý vedel p(x)G pre všetkých x.

V tejto časti budeme predpokladať, že každý účastník má lokálne nejaký súkromný kľúč xi, tak, aby každý poznal príslušný verejný kľúč Xi.

Jeden z možných protokolov generovania polynómov je nasledujúci:

1. Každý účastník i lokálne vytvára ľubovoľný polynóm pi(x) stupeň k-1. Potom pošlú každého účastníka j hodnota pi(j), zašifrované verejným kľúčom Xj. Takto jedine i-th и j-th účastník vedieť pi(j). Účastník i aj verejne oznamuje pi(j)G pre všetkých j od 1 na k inclusive.

2. Všetci účastníci používajú určitý konsenzus na výber k účastníkov, ktorých polynómy budú použité. Keďže niektorí účastníci môžu byť offline, nemôžeme čakať, kým budú všetci n účastníci zverejnia polynómy. Výsledkom tohto kroku je súbor Z pozostávajúce z najmenej k polynómy vytvorené v kroku (1).

3. Účastníci sa ubezpečujú, že hodnoty, ktoré poznajú pi(j) zodpovedajú verejne oznámeným pi(j)G. Po tomto kroku v Z iba polynómy, pre ktoré sú súkromne prenášané pi(j) zodpovedajú verejne oznámeným pi(j)G.

4. Každý účastník j vypočítava jeho súkromnú zložku p(j) ako súčet pi(j) pre všetkých i в Z. Každý účastník tiež vypočíta všetky hodnoty p(x)G ako súčet pi(x)G pre všetky i в Z.

Vezmite prosím na vedomie, že p(x) – je to naozaj polynóm k-1, pretože je to súčet jednotlivca pi(x), z ktorých každý je polynóm stupňa k-1. Potom si všimnite, že kým každý účastník j vie, p(j), nemajú žiadne informácie p(x) pre x ≠ j. Na výpočet tejto hodnoty totiž potrebujú vedieť všetko pi(x), a pokiaľ je účastník j nepozná aspoň jeden z vybraných polynómov, nemá o ňom dostatočné informácie p(x).

Toto je celý proces generovania polynómov, ktorý bol potrebný v poslednej časti. Kroky 1, 2 a 4 vyššie majú celkom zrejmú implementáciu. Krok 3 však nie je taký triviálny.

Konkrétne musíme byť schopní dokázať, že je to šifrované pi(j) skutočne zodpovedajú publikovaným pi(j)G. Ak to nedokážeme, útočník i môže namiesto toho posielať odpadky pi(j) účastníkovi ja účastník j nebude schopný pochopiť skutočný význam pi(j), a nebude môcť vypočítať jeho súkromnú zložku.

Existuje kryptografický protokol, ktorý vám umožňuje vytvoriť ďalšiu správu dôkazi(j), takže každý účastník má nejakú hodnotu e, ako aj dôkaz (j) и pi(j)G, môže to miestne overiť e - je to vážne pi(j), zašifrované kľúčom účastníka j. Bohužiaľ, veľkosť takýchto dôkazov je neuveriteľne veľká a vzhľadom na to je potrebné ich publikovať O(nk) Takéto dôkazy nemožno na tento účel použiť.

Namiesto toho, aby to dokázal pi(j) zodpovedá pi(j)G môžeme v protokole generovania polynómov vyčleniť veľmi dlhé časové obdobie, počas ktorého všetci účastníci kontrolujú prijaté šifrované pi(j), a ak dešifrovaná správa nezodpovedá verejnosti pi(j)G, zverejnia kryptografický dôkaz, že zašifrovaná správa, ktorú dostali, je nesprávna. Dokážte, že správa nie zodpovedá pi(G) oveľa jednoduchšie ako dokázať, že sa to zhoduje. Je potrebné poznamenať, že to vyžaduje, aby sa každý účastník objavil na internete aspoň raz v čase vyhradenom na vytvorenie takéhoto dôkazu, a vychádza z predpokladu, že ak takýto dôkaz zverejní, dostane sa ku všetkým ostatným účastníkom v rovnakom vyhradenom čase.

Ak sa účastník počas tohto časového obdobia neobjavil online a mal aspoň jeden nesprávny komponent, potom sa tento konkrétny účastník nebude môcť zúčastniť na ďalšom generovaní čísla. Protokol však bude stále fungovať, ak existuje aspoň k účastníci, ktorí buď práve dostali správne komponenty alebo stihli zanechať dôkaz o nesprávnosti v stanovenom čase.

Dôkazy správnosti H_i

Posledná časť, ktorú treba prediskutovať, je, ako dokázať správnosť zverejnenia Hja, totiž to Ahoj = p(i)H, bez otvárania p(i).

Pamätajme, že hodnoty H, G, p(i)G verejné a všetkým známe. Operácia príjmu p(i) vediac p(i)G и G nazývaný diskrétny logaritmus, príp dlog, a chceme dokázať, že:

dlog(p(i)G, G) = dlog(Hi, H)

bez zverejnenia p(i). Konštrukcie na takéto dôkazy existujú napr Schnorrov protokol.

S týmto dizajnom každý účastník spolu s Hi zašle doklad o správnosti podľa návrhu.

Po vygenerovaní náhodného čísla ho často musia použiť iní účastníci ako tí, ktorí ho vygenerovali. Takíto účastníci musia spolu s číslom poslať všetky Hi a súvisiace dôkazy.

Zvedavý čitateľ sa môže opýtať: keďže konečné náhodné číslo je H0 a p(0)G – Toto je verejná informácia, prečo potrebujeme dôkaz pre každého jednotlivca HPrečo namiesto toho neposlať dôkaz

dlog(p(0)G, G) = dlog(H0, H)

Problém je, že takýto dôkaz nie je možné vytvoriť pomocou Schnorrovho protokolu, pretože nikto nepozná hodnotu p (0), potrebný na vytvorenie dôkazu, ba čo viac, celý generátor náhodných čísel je založený na tom, že túto hodnotu nikto nepozná. Preto je potrebné mať všetky hodnoty Hi a ich jednotlivé dôkazy na preukázanie správnosti H0.

Ak by však na bodoch na eliptických krivkách došlo k nejakej operácii, ktorá je sémanticky podobná násobeniu, dôkaz správnosti H0 by bolo triviálne, jednoducho by sme to zabezpečili

H0 × G = p(0)G × H

Ak zvolená krivka podporuje páry eliptických kriviek, tento dôkaz funguje. V tomto prípade H0 nie je len výstup generátora náhodných čísel, ktorý si môže overiť každý, kto vie G, H и p(0)G. H0 je tiež podpis na správe, ktorá bola použitá ako základ, čo potvrdzuje k и n účastníci podpísali túto správu. Teda ak semeno - je potom hash bloku v blockchainovom protokole H0 je viacnásobný podpis na bloku a veľmi dobré náhodné číslo.

na záver

Tento článok je súčasťou série technických blogov NEAR. NEAR je blockchain protokol a platforma pre vývoj decentralizovaných aplikácií s dôrazom na jednoduchosť vývoja a jednoduché použitie pre koncových používateľov.

Kód protokolu je otvorený, naša implementácia je napísaná v Ruste, dá sa nájsť tu.

Môžete vidieť, ako vyzerá vývoj pre NEAR a experimentovať v online IDE tu.

Všetky novinky v ruštine môžete sledovať na telegramová skupina a skupina na VKontaktea v oficiálnom jazyku v angličtine cvrlikání.

Uvidíme sa skoro!

Zdroj: hab.com