Je možné generovat náhodná čísla, když si nevěříme? Část 2

Čau Habr!

В první část V tomto článku jsme se zabývali tím, proč by mohlo být nutné generovat náhodná čísla pro účastníky, kteří si navzájem nedůvěřují, jaké požadavky jsou kladeny na takové generátory náhodných čísel a zvážili jsme dva přístupy k jejich implementaci.

V této části článku se blíže podíváme na jiný přístup, který využívá prahové signatury.

Trochu kryptografie

Abyste pochopili, jak prahové podpisy fungují, musíte porozumět trochu základní kryptografii. Použijeme dva pojmy: skaláry nebo jednoduše čísla, která budeme označovat malými písmeny (x, y) a body na eliptické křivce, které budeme označovat velkými písmeny.

Abyste pochopili základy prahových signatur, nepotřebujete kromě několika základních věcí rozumět tomu, jak eliptické křivky fungují:

1. Body na eliptické křivce lze sčítat a násobit skalárem (násobení skalárem budeme označovat jako xG, i když notace Gx také často používaný v literatuře). Výsledkem sčítání a násobení skalárem je bod na eliptické křivce.

2. Znát pouze pointu G a jeho součin se skalárem xG nelze vypočítat x.

Použijeme také pojem polynom p (x) stupně k-1. Využijeme zejména následující vlastnost polynomů: známe-li hodnotu p (x) pro všechny k rozdílný x (a nemáme žádné další informace p (x)), můžeme počítat p (x) pro kohokoli jiného x.

Je zajímavé, že pro jakýkoli polynom p (x) a nějaký bod na křivce Gznát význam p(x)G pro všechny k různé významy x, můžeme také vypočítat p(x)G pro jakékoli x.

To je dostatek informací k tomu, abyste se mohli ponořit do podrobností o tom, jak prahové signatury fungují a jak je používat ke generování náhodných čísel.

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

Řekněme to n účastníci chtějí vygenerovat náhodné číslo a my chceme, aby se účastnil kdokoli k bylo jich dost na to, aby vygenerovali číslo, ale aby útočníci, kteří ovládají k-1 nebo méně účastníků nemohlo předvídat nebo ovlivnit generovaný počet.

Předpokládejme, že takový polynom existuje p (x) stupně k-1 co ví první účastník p (1), ten druhý ví p(2), a tak dále (n-th ví p(n)). Předpokládáme také, že pro nějaký předem stanovený bod G každý ví p(x)G pro všechny hodnoty x. zavoláme p(i) "soukromá složka" iúčastník (protože pouze itý účastník ji zná) a prase "veřejná složka" i-tá účastnice (protože ji všichni účastníci znají). Jak si vzpomínáte, znalosti prase nestačí obnovit p(i).

Vytvoření takového polynomu tak, že pouze i-Třetí účastník a nikdo jiný neznal jeho soukromou složku – to je nejsložitější a nejzajímavější část protokolu a níže ji rozebereme. Prozatím předpokládejme, že máme takový polynom a všichni účastníci znají své soukromé komponenty.

Jak můžeme takový polynom použít ke generování náhodného čísla? Pro začátek potřebujeme nějaký řetězec, který předtím nebyl použit jako vstup do generátoru. V případě blockchainu hash posledního bloku h je dobrým kandidátem na takovou linku. Umožněte účastníkům vytvořit náhodné číslo pomocí h jako semeno. Účastníci konvertují jako první h do bodu na křivce pomocí libovolné předdefinované funkce:

H = skalární bod(h)

Poté každý účastník i vypočítává a publikuje Ahoj = p(i)H, co mohou dělat, protože vědí p(i) a H. Zveřejnění HNepovoluji ostatním účastníkům obnovit soukromou komponentu iúčastníka, a proto lze blok od bloku používat jednu sadu privátních komponent. Nákladný algoritmus generování polynomu popsaný níže tedy stačí provést pouze jednou.

Kdy k účastníci byli pitváni Ahoj = p(i)H, každý umí počítat Hx = p(x)H pro všechny x díky vlastnosti polynomů, o které jsme hovořili v minulé části. V tuto chvíli všichni účastníci počítají H0 = p(0)H, a toto je výsledné náhodné číslo. Upozorňujeme, že nikdo neví p(0), a tedy jediný způsob výpočtu p(0)H – toto je interpolace p(x)H, což je možné pouze tehdy k hodnoty p(i)H známý. Otevírání jakéhokoli menšího množství p(i)H neposkytuje žádné informace o p(0)H.

Generátor výše má všechny vlastnosti, které chceme: pouze ovládání útočníků k-1 nebo méně účastníků nemá žádné informace ani vliv na závěr, zatímco jakékoli k účastníci mohou vypočítat výsledné číslo a jakoukoli jeho podmnožinu k účastníci vždy dojdou ke stejnému výsledku pro stejné semeno.

Existuje jeden problém, kterému jsme se pečlivě vyhnuli výše. Aby interpolace fungovala, je důležité, aby hodnota Hi, kterou zveřejnil každý účastník i opravdu to bylo stejné p(i)H. Protože nikdo kromě i-tý účastník neví p(i), nikdo kromě i-účastník to nemůže ověřit Hi skutečně vypočítal správně a bez jakéhokoli kryptografického důkazu správnosti HÚtočník může publikovat jakoukoli hodnotu jako Dobrý den, a libovolně ovlivňovat výstup generátoru náhodných čísel:

Různé hodnoty H_1 zaslané prvním účastníkem vedou k různým výsledným H_0

Existují minimálně dva způsoby, jak prokázat správnost Hi, budeme je uvažovat po analýze generování polynomu.

Generování polynomu

V poslední části jsme předpokládali, že takový polynom máme p (x) stupně k-1 že účastník i ví p(i)a nikdo jiný o této hodnotě nemá žádné informace. V další části to budeme také potřebovat pro nějaký předem určený bod G všichni věděli p(x)G pro všechny x.

V této části budeme předpokládat, že každý účastník má lokálně nějaký soukromý klíč xi, tak, aby každý znal odpovídající veřejný klíč Xi.

Jeden možný protokol generování polynomu je následující:

1. Každý účastník i lokálně vytvoří libovolný polynom pi(x) stupeň k-1. Poté pošlou každého účastníka j hodnota pi(j), zašifrované veřejným klíčem Xj. Takto jedině i-th и j-th účastník vědět pi(j). Účastník i také veřejně oznamuje pi(j)G pro všechny j z 1 na k včetně.

2. Všichni účastníci používají určitý konsensus k výběru k účastníky, jejichž polynomy budou použity. Protože někteří účastníci mohou být offline, nemůžeme čekat, až všichni n účastníci zveřejní polynomy. Výsledkem tohoto kroku je sada Z skládající se z nejméně k polynomy vytvořené v kroku (1).

3. Účastníci se ujistí, že hodnoty, které znají pi(j) odpovídají veřejně oznámeným pi(j)G. Po tomto kroku dovnitř Z pouze polynomy, pro které jsou soukromě přenášeny pi(j) odpovídají veřejně oznámeným pi(j)G.

4. Každý účastník j vypočítá jeho privátní složku p(j) jako součet pi(j) pro všechny i в Z. Každý účastník také vypočítá všechny hodnoty p(x)G jako součet pi(x)G pro všechna i в Z.

Vezměte prosím na vědomí, že p(x) – je to opravdu polynom k-1, protože je součtem jednotlivce pi(x), z nichž každý je polynom stupně k-1. Pak si všimněte, že zatímco každý účastník j ví p(j), nemají žádné informace p (x) pro x ≠ j. K výpočtu této hodnoty totiž potřebují vědět všechno pi(x), a dokud účastník j nezná alespoň jeden z vybraných polynomů, nemá o něm dostatečné informace p(x).

Toto je celý proces generování polynomu, který byl potřeba v minulé sekci. Kroky 1, 2 a 4 výše mají poměrně zřejmou implementaci. Krok 3 ale není tak triviální.

Konkrétně musíme být schopni dokázat, že je to šifrované pi(j) skutečně odpovídají publikovaným pi(j)G. Pokud to nemůžeme dokázat, útočník i může místo toho posílat odpadky pi(j) účastníkovi ja účastník j nebude schopen získat skutečnou hodnotu pí(j), a nebude schopen vypočítat jeho soukromou složku.

Existuje kryptografický protokol, který umožňuje vytvořit další zprávu důkazi(j), takže každý účastník má nějakou hodnotu e, jakož i důkaz (j) и pi(j)G, to může místně ověřit e - je to opravdu pí(j), zašifrované klíčem účastníka j. Bohužel velikost takových důkazů je neuvěřitelně velká a vzhledem k tomu je nutné je zveřejňovat O(nk) Takový důkaz nelze k tomuto účelu použít.

Místo toho, aby to dokázal pi(j) odpovídá pi(j)G můžeme v protokolu generování polynomu alokovat velmi dlouhé časové období, během kterého všichni účastníci kontrolují přijaté šifrované pí(j), a pokud dešifrovaná zpráva neodpovídá veřejnosti pi(j)G, zveřejňují kryptografický důkaz, že zašifrovaná zpráva, kterou obdrželi, je nesprávná. Dokažte, že zpráva ne odpovídá prase) mnohem jednodušší než dokázat, že se to shoduje. Je třeba poznamenat, že to vyžaduje, aby se každý účastník objevil online alespoň jednou během doby vyhrazené k vytvoření takového důkazu, a spoléhá se na předpoklad, že pokud takový důkaz zveřejní, dostane se ke všem ostatním účastníkům ve stejnou stanovenou dobu.

Pokud se účastník během této doby neobjevil online a měl alespoň jednu nesprávnou komponentu, pak se tento konkrétní účastník nebude moci zúčastnit dalšího generování čísel. Protokol však bude stále fungovat, pokud existuje alespoň k účastníci, kteří buď právě obdrželi správné součásti, nebo dokázali zanechat důkaz o nesprávnosti ve stanoveném čase.

Důkazy správnosti H_i

Poslední částí, kterou je třeba projednat, je, jak prokázat správnost zveřejnění Hjá, totiž to Ahoj = p(i)H, bez otevírání p(i).

Mějme na paměti, že hodnoty H, G, p(i)G veřejné a všem známé. Operace příjmu p(i) vědět prase и G tzv. diskrétní logaritmus, popř dlog, a chceme dokázat, že:

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

bez prozrazení p(i). Existují například konstrukce pro takové důkazy Schnorrův protokol.

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

Jakmile je vygenerováno náhodné číslo, často jej musí použít jiní účastníci než ti, kteří je vygenerovali. Takoví účastníci spolu s číslem musí poslat všechny Hi a související důkazy.

Zvídavý čtenář se může zeptat: protože konečné náhodné číslo je H0 a p(0)G – Toto je veřejná informace, proč potřebujeme důkaz pro každého jednotlivce HProč místo toho neposlat důkaz

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

Problém je v tom, že takový důkaz nelze vytvořit pomocí protokolu Schnorr, protože nikdo nezná hodnotu p (0), nutný k vytvoření důkazu, a co víc, celý generátor náhodných čísel je založen na tom, že tuto hodnotu nikdo nezná. Proto je nutné mít všechny hodnoty Hi a jejich individuální důkazy k prokázání správnosti H0.

Pokud však došlo k nějaké operaci s body na eliptických křivkách, která je sémanticky podobná násobení, důkaz správnosti H0 by bylo triviální, jednoduše bychom to zajistili

H0 × G = p(0)G × H

Pokud vybraná křivka podporuje páry eliptických křivek, tento důkaz funguje. V tomto případě H0 není pouze výstupem generátoru náhodných čísel, který může ověřit každý, kdo ví G,H и p(0)G. H0 je také podpis na zprávě, která byla použita jako zdroj, což potvrzuje k и n účastníci podepsali tuto zprávu. Pokud tedy semeno – je tedy hash bloku v blockchainovém protokolu H0 je jak multi-podpis na bloku, tak velmi dobré náhodné číslo.

Konečně,

Tento článek je součástí série technických blogů NEAR. NEAR je blockchain protokol a platforma pro vývoj decentralizovaných aplikací s důrazem na snadnost vývoje a snadné použití pro koncové uživatele.

Kód protokolu je otevřený, naše implementace je napsána v Rustu, lze jej najít zde.

Můžete se podívat, jak vývoj pro NEAR vypadá a experimentovat v online IDE zde.

Všechny novinky v ruštině můžete sledovat na telegramová skupina a skupina na VKontaktea v angličtině v oficiálním twitter.

Brzy se uvidíme!

Zdroj: www.habr.com