Čau Habr!
В 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 nedôverujú, aké požiadavky sú kladené na takéto generátory náhodných čísel a zvážili 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 sme pochopili, ako fungujú prahové podpisy, musíme pochopiť základy kryptografie. Budeme používať dva koncepty: skaláry 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.
Na pochopenie základov prahových podpisov nepotrebujete rozumieť fungovaniu eliptických kriviek, okrem niekoľkých základných vecí:
Body na eliptickej krivke možno sčítať a vynásobiť skalárom (násobenie skalárom budeme označovať ako xG, hoci notácia Gx (tiež často používané v literatúre). Výsledkom sčítania a násobenia skalárom je bod na eliptickej krivke.
Poznať len pointu G a jeho súčin so skalárom xG nedá sa vypočítať x.
Budeme tiež používať pojem polynómu p(x) stupňa k-1. Konkrétne použijeme nasledujúcu vlastnosť polynómov: ak poznáme hodnotu p(x) pre akékoľvek k rozdielny x (a nemáme o tom žiadne ďalšie informácie) p(x)), môžeme vypočítať p(x) pre akékoľvek iné x.
Je zaujímavé, že pre akýkoľvek polynóm p(x) a nejaký bod na krivke G, poznajúc význam p(x)G pre akékoľvek k rôzne významy x, môžete tiež vypočítať p(x)G pre akékoľvek x.
Tieto informácie sú dostatočné na to, aby sme sa ponorili do detailov o tom, ako fungujú prahové podpisy a ako ich použiť na generovanie náhodných čísel.
Generátor náhodných čísel založený na prahových podpisoch
Predpokladajme, že n účastníci chcú vygenerovať náhodné číslo a my chceme, aby sa všetci zúčastnili k z nich bolo dosť na vygenerovanie čísla, ale pre útočníkov, ktorí ovládajú k-1 alebo menej účastníkov nedokázalo predpovedať ani ovplyvniť vygenerované číslo.
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-to vie p(n)). Predpokladajme tiež, že pre nejaký vopred určený bod G každý vie p(x)G pre všetky hodnoty xZavoláme p(i) „súkromná zložka“ i-tého účastníka (pretože iba i-tý účastník ju pozná) a p(i)G „verejná zložka“ i-tý účastník (pretože všetci účastníci to vedia). Ako si pamätáte, vedomosti p(i)G nestačí na obnovu p(i).
Vytvorenie takého polynómu tak, aby iba i-Tretí účastník a nikto iný nepoznal svoju súkromnú zložku – toto je najzložitejšia a najzaujímavejšia časť protokolu a budeme ju diskutovať nižšie. Zatiaľ predpokladajme, že máme takýto polynóm a všetci účastníci poznajú svoje súkromné zložky.
Ako môžeme použiť takýto polynóm na generovanie náhodného čísla? Najprv potrebujeme reťazec, ktorý ešte nebol použitý ako vstup do generátora. V prípade blockchainu je to hash posledného bloku h — je dobrým kandidátom na takýto reťazec. Nech účastníci chcú vygenerovať náhodné číslo pomocou h ako semeno. Účastníci najprv konvertujú h do bodu na krivke pomocou ľubovoľnej preddefinovanej funkcie:
H = skalárnyBod(h)
Potom každý účastník i vypočítava a publikuje Hi = p(i)H, čo dokážu, pretože vedia p(i) a H. Zverejnenie HNeumožňuje ostatným účastníkom obnoviť súkromnú zložku i-tého účastníka, a preto je možné z bloku do bloku použiť rovnakú sadu súkromných komponentov. Nákladný algoritmus generovania polynómov opísaný nižšie sa teda musí vykonať iba raz.
Kedy k účastníci boli vystavení Hi = p(i)H, každý si to dokáže domyslieť Hx = p(x)H pre všetkých x vďaka vlastnosti polynómov, o ktorej sme hovorili v predchádzajúcej časti. V tomto bode všetci účastníci vypočítajú H0 = p(0)H, a toto je výsledné náhodné číslo. Všimnite si, že nikto nevie p(0), a preto je to jediný spôsob, ako počítať p(0)H – toto je interpolácia p(x)H, čo je možné len vtedy, keď k hodnoty p(i)H známe. Otvorenie 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 požadované vlastnosti: útočníci ovládajú iba k-1 alebo menej účastníkov nemá žiadne informácie a vplyv na záver, zatiaľ čo ktorýkoľvek k účastníci môžu vypočítať výsledné číslo a ľubovoľnú podmnožinu k účastníci vždy dospejú k rovnakému výsledku pre to isté semeno.
Existuje jeden problém, ktorému sme sa vyššie starostlivo vyhli. Aby interpolácia fungovala, je dôležité, aby hodnota Ha ktorý zverejnil každý účastník i bolo to naozaj rovnaké p(i)H. Keďže nikto iný i- účastník nevie p(i), nikto okrem i-Účastník nemôže overiť, že Hi v skutočnosti to bolo vypočítané správne a bez akéhokoľvek kryptografického dôkazu správnosti HÚtočník môže publikovať akúkoľvek hodnotu ako Ahoj, a ľubovoľne ovplyvniť 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 hodnotám H_0.
Existujú minimálne dva spôsoby, ako dokázať správnosť Hi, budeme ich brať do úvahy po analýze generovania polynómu.
Generovanie polynómov
V poslednej časti sme predpokladali, že máme taký polynóm p(x) stupňa k-1 aký účastník i vie, p(i), a nikto iný nemá žiadne informácie o tejto hodnote. V ďalšej časti budeme potrebovať aj túto informáciu pre určitý 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á nejaký lokálny súkromný kľúč xi, tak, aby každý poznal zodpovedajúci verejný kľúč Xi.
Jeden možný protokol generovania polynómov je nasledovný:
Každý účastník i lokálne vytvára ľubovoľný polynóm pí(x) stupňa k-1. Potom ho pošlú každému účastníkovi j hodnota pi(j), zašifrované verejným kľúčom Xj. Takže iba i-ý и j-ý účastník vie pi(j). Účastník i tiež verejne oznamuje pí(j)G pre všetkých j od 1 na k inclusive.
Všetci účastníci používajú určitý konsenzus na výber k účastníci, ktorých polynómy budú použité. Keďže niektorí účastníci môžu byť offline, nemôžeme čakať, kým všetci n Účastníci budú publikovať polynómy. Výsledkom tohto kroku je množina Z pozostávajúce z minimálne k polynómy vytvorené v kroku (1).
Účastníci sú presvedčení, že hodnoty, ktoré poznajú pi(j) zodpovedajú verejne oznámeným pí(j)G. Po tomto kroku v Z iba polynómy, pre ktoré boli súkromne odovzdané pi(j) zodpovedajú verejne oznámeným pí(j)G.
Každý účastník j vyhodnocuje jeho súkromnú zložku p(j) ako súčet pi(j) pre všetky i в ZKaždý účastník tiež vypočíta všetky hodnoty p(x)G ako súčet pí(x)G pre všetky i в Z.
Vezmite prosím na vedomie, že p(x) – toto je skutočne polynóm určitého stupňa 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 hoci každý účastník j vie, p(j), nemajú žiadne informácie o p(x) pre x ≠ jV skutočnosti, aby mohli vypočítať túto hodnotu, potrebujú vedieť všetko pí(x), a zatiaľ čo úč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 požadovaný v predchádzajúcej časti. Kroky 1, 2 a 4 uvedené vyššie majú pomerne jednoduchú implementáciu. Krok 3 však nie je až taký triviálny.
Konkrétne musíme byť schopní dokázať, že šifrované pi(j) zodpovedajú publikovaným hodnotám pí(j)G. Ak to nedokážeme, útočník i môže namiesto toho poslať odpadky pi-tý účastník ja účastník j nebude schopný pochopiť skutočný význam pí(j), a nebude schopný 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 s určitou hodnotou e, ako aj dôkaz(j) и pi(j)G, môže lokálne overiť, že e - naozaj je pí(j), zašifrované kľúčom účastníka j. Bohužiaľ, rozsah takýchto dôkazov je neuveriteľne veľký a vzhľadom na to, že je potrebné ich zverejniť O(nk) takéto dôkazy nemožno na tento účel použiť.
Namiesto toho, aby to dokazoval pí(j) zodpovedá pi(j)G môžeme v protokole generovania polynómov vyčleniť veľmi dlhý časový úsek, počas ktorého všetci účastníci skontrolujú prijaté zašifrované pí(j), a ak dešifrovaná správa nezodpovedá verejnej správe pi(j)G, zverejnia kryptografický dôkaz, že zašifrovaná správa, ktorú dostali, je nesprávna. Dokážte, že správa nie zodpovedá pí(G) Je to oveľa jednoduchšie ako dokázať, že sa to zhoduje. Stojí za zmienku, že to vyžaduje, aby sa každý účastník počas času vyhradeného na vytvorenie takýchto dôkazov objavil online aspoň raz a vychádza z predpokladu, že ak takýto dôkaz zverejnia, dostane sa ku všetkým ostatným účastníkom v rovnakom vyhradenom čase.
Ak sa účastník počas tohto obdobia nedostavil online a mal aspoň jednu neplatnú zložku, potom sa tento konkrétny účastník nebude môcť zúčastniť ďalšieho generovania čísel. Protokol však bude stále fungovať, ak existuje aspoň jedna neplatná zložka. k účastníci, ktorí buď práve dostali správne komponenty, alebo sa im podarilo zanechať dôkaz o nesprávnosti v stanovenom čase.
Dôkazy o správnosti H_i
Poslednou časťou, ktorú treba prediskutovať, je, ako dokázať správnosť publikovaného Hja, konkrétne to Hi = p(i)H, bez otvárania p(i).
Pripomeňme si, že hodnoty H, G, p(i)G verejne dostupné a známe každému. Operácia prijatia p(i) vedomie p(i)G и G sa nazýva diskrétny logaritmus alebo dlog, a chceme dokázať, že:
dlog(p(i)G, G) = dlog(Hi, H)
bez zverejnenia p(i)Konštrukcie pre takéto dôkazy existujú, napríklad.
S týmto dizajnom každý účastník spolu s Hi posiela dôkaz o správnosti podľa konštrukcie.
Keď je náhodné číslo vygenerované, často ho musia použiť aj iní účastníci, než tí, ktorí ho vygenerovali. Títo účastníci musia spolu s číslom poslať všetky potrebné informácie. Hi a sprievodné dôkazy.
Zvedavý čitateľ by sa mohol opýtať: keďže konečné náhodné číslo je H0 a p(0)G – Toto sú verejne dostupné informácie, prečo potrebujeme dôkazy pre každého jednotlivca? HPrečo namiesto toho neposlať dôkaz?
dlog(p(0)G, G) = dlog(H0, H)
Problém je v tom, že takýto dôkaz nemôžete vytvoriť pomocou Schnorrovho protokolu, pretože nikto nepozná hodnotu p(0), potrebné na vytvorenie dôkazu a navyše celý generátor náhodných čísel je založený na skutočnosti, že túto hodnotu nikto nepozná. Preto je potrebné mať všetky hodnoty Hi a ich individuálne dôkazy na preukázanie správnosti H0.
Ak by však existovala nejaká operácia na bodoch eliptických kriviek, ktorá by bola sémanticky podobná násobeniu, dôkaz správnosti H0 bolo by to triviálne, jednoducho by sme sa uistili, že
H0 × G = p(0)G × H
Ak vybraná krivka podporuje , tento dôkaz funguje. V tomto prípade H0 nie je len výstup generátora náhodných čísel, ktorý môže overiť každý účastník, ktorý vie G, H и p(0)G.H0 je tiež podpis správy, ktorý bol použitý ako seed, čo potvrdzuje, že k и n účastníci podpísali túto správu. Ak teda semeno – Toto je hash bloku v blockchainovom protokole, potom H0 – toto je viacnásobný podpis na bloku a zároveň veľmi dobré náhodné číslo.
na záver
Tento článok je súčasťou série technických blogov. NEAR je blockchainový protokol a platforma pre vývoj decentralizovaných aplikácií so zameraním na jednoduchosť vývoja a jednoduché používanie pre koncových používateľov.
Kód protokolu je otvorený, naša implementácia je napísaná v Ruste, dá sa nájsť .
Môžete vidieť, ako vyzerá vývoj pre NEAR a experimentovať v online IDE .
Všetky novinky v ruštine môžete sledovať na a a v oficiálnom jazyku v angličtine .
Uvidíme sa skoro!
Zdroj: hab.com
