Ahoj, Habr!
V V článku jsme prodiskutovali, proč může být nezbytné generovat náhodná čísla pro účastníky, kteří si vzájemně nedůvěřují, jaké požadavky jsou kladeny na takové generátory náhodných čísel, a prozkoumali jsme dva přístupy k jejich realizaci.
V této části článku podrobně prozkoumáme další přístup, který využívá prahové podpisy.
Trocha kryptografie
Abychom pochopili, jak fungují prahové podpisy, musíme mít nějaké základní znalosti o kryptografii. Použijeme dvě koncepce: scalá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.
Pro pochopení základů prahových podpisů není třeba rozumět tomu, jak fungují eliptické křivky, kromě několika základních věcí:
Body na eliptické křivce lze sčítat a násobit scalárem (násobení scalárem budeme označovat jako xG, i když notace Gx se také často používá v literatuře). Výsledek sčítání a násobení scalárem je bod na eliptické křivce.
Známe-li pouze bod G a jeho násobek s scalárem xG nelze vypočítat x.
Budeme také používat koncept polynomu p(x) stupně k-1. Konkrétně budeme využívat následující vlastnost polynomů: pokud známe hodnotu p(x) pro jakékoli k různé x (a nemáme žádné jiné informace o p(x)), můžeme vypočítat p(x) pro jakékoli jiné x.
Je zajímavé, že pro jakýkoli polynom p(x) a nějaký bod na křivce G, známe-li hodnotu p(x)G pro jakékoli k různých hodnot x, lze také vypočítat p(x)G pro jakýkoli x.
Tyto informace stačí k tomu, abychom se ponořili do detailů o tom, jak fungují prahové podpisy a jak je použít k generování náhodných čísel.
Generátor náhodných čísel na prahových podpisech
Představme si, že n účastníků chce vygenerovat náhodné číslo, a chceme, aby účast jakéhokoli z nich byl dostatečný k vygenerování čísla, ale aby útočníci, kteří kontrolují k -1 nebo méně účastníků, nemohli předpovědět nebo ovlivnit vygenerované číslo. kPředstavme si, že existuje takový polynom
-1, že první účastník ví p(x) stupně kp(1) , druhý víp(2), a tak dále ( -ý vínp(n) ). Také předpokládejme, že pro nějaký předem určený bodvšichni vědí G pro všechny hodnoty p(x)G . Budeme to nazývat x. Budeme to nazývat p(i) "privátní komponenta“ i-í účastníka (protože pouze i-ý účastník to ví), a p(i)G "veřejná komponenta“ i-í účastníka (protože všichni účastníci to znají). Jak si pamatujete, znalost p(i)G není dostatečná pro obnovení p(i).
Vytvoření takového polynomu tak, aby pouze i--ý účastník a nikdo jiný znal svou privátní komponentu – to je nejtěžší a nejzajímavější část protokolu, a to si podrobně rozebereme níže. Zatím předpokládejme, že takový polynom máme a všichni účastníci znají své privátní komponenty.
Jak můžeme použít takový polynom k vygenerování náhodného čísla? Nejprve potřebujeme nějaký řetězec, který dosud nebyl použit jako vstup pro generátor. V případě blockchainu je hash posledního bloku h — dobrý kandidát na takový řetězec. Předpokládejme, že účastníci chtějí vytvořit náhodné číslo, pomocí h jako seed. Nejprve účastníci převedou h na bod na křivce pomocí jakékoli předem definované funkce:
H = scalarToPoint(h)
Poté každý účastník i vypočítá a zveřejní Hi = p(i)H, což mohou udělat, protože znají p(i) a H. Odhalení Hi neumožňuje ostatním účastníkům obnovit privátní komponentu i-í účastníka, a proto jeden soubor privátních komponent lze použít od bloku k bloku. Takže drahý algoritmus pro tvorbu polynomu, který je popsán níže, je třeba provést pouze jednou.
Když k účastníci odhalí Hi = p(i)H, všichni mohou vypočítat Hx = p(x)H pro všechny x díky vlastnosti polynomů, které jsme probírali v předchozí části. V tuto chvíli všichni účastníci vypočítají H0 = p(0)H, a to je výsledné náhodné číslo. Všimněte si, že nikdo neví p(0), a tudíž jediný způsob, jak spočítat p(0)H – je interpolace p(x)H, což je možné pouze tehdy, když k hodnoty p(i)H jsou známy. Odhalení jakéhokoliv menšího počtu p(i)H nedává žádné informace o p(0)H.
Výše uvedený generátor má všechny vlastnosti, které chceme: útočníci, kteří kontrolují pouze k-1 účastníků, nebo méně, nemají žádné informace a vliv na výstup, zatímco jakýkoli k účastníků může vypočítat výsledné číslo, a jakýkoli podmnožina z k účastníků vždy dosáhne stejného výsledku pro stejný seed.
Existuje jeden problém, kterému jsme se shodou okolností vyhnuli dříve. Aby interpolace fungovala, je důležité, aby hodnota Hi, kterou zveřejnil každý účastník, i skutečně byla rovna p(i)H. Jelikož nikdo kromě i-ého účastníka neví p(i), nikdo kromě i-ého účastníka nemůže ověřit, že Ahoj, skutečně bylo správně spočítáno, a bez nějakého kryptografického důkazu správnosti, Hi útočník může zveřejnit jakoukoli hodnotu jako Ahoj, a libovolně ovlivnit 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í alespoň dva způsoby, jak prokázat správnost Hi, které probereme poté, co se budeme věnovat generaci polynomu.
Generace polynomu
V předchozím oddíle jsme předpokládali, že máme takový polynom p(x) stupně k-1, který účastník i zná, p(i)a nikdo jiný nemá žádné informace o této hodnotě. V následujícím oddíle bude také nutné, aby pro nějaký předem stanovený bod G všichni věděli p(x)G pro všechny x.
V tomto oddíle budeme předpokládat, že každý účastník má lokálně nějaký soukromý klíč xi, tak, že všem je znám odpovídající veřejný klíč Xi.
Jeden možný protokol generace polynomu je následující:
Každý účastník i lokálně vytvoří libovolný polynom pi(x) stupně k-1. Poté každý z nich zašle každému účastníkovi j hodnotu pi(j), zašifrovanou veřejným klíčem Xj. Tímto způsobem pouze i-ý a j-ý účastník víý i(j). Účastník ptaké veřejně oznámí i pi(j)G včetně. pro všechny j od 1 do k Všichni účastníci používají nějaký konsensus, aby vybrali
účastníky, jejichž polynomy budou použity. Jelikož někteří účastníci mohou být offline, nemůžeme čekat, až všichni k účastníci zveřejní polynomy. Výsledek tohoto kroku je množina n skládající se alespoň Z polynomů vytvořených v kroku (1) k Účastníci se ujistí, že jimi známé hodnoty.
i(j) odpovídají veřejně oznámeným ppi(j)G. Po tomto kroku by měly zůstat pouze polynomy, pro které soukromě předané vypočítává svou soukromou komponentu Z p(j) ppi(j)G. Po tomto kroku by měly zůstat pouze polynomy, pro které soukromě předané
Každý účastník j jako součet i(j) pro všechny . Každý účastník také vypočítá všechny hodnoty ppi(x)G pro všechny i, i v Zp(x) – p(x)G . Každý účastník také vypočítá všechny hodnoty to je skutečně polynom stupně v Z.
Všimněte si, že k-1, protože je to součet jednotlivých i(x), přičemž každý z nich je polynom stupně. protože to je součet jednotlivých pi(x), přičemž každý z nich je polynom stupně k-1. Poté si uvědomte, že zatímco každý účastník j zná, p(j), nemají žádné informace o p(x) pro x ≠ j. Skutečně, aby tento hodnotu spočítali, musí vědět všechny pi(x), a dokud účastník j nezná alespoň jeden z vybraných polynomů, nemají dostatek informací o p(x).
To je celý proces generování polynomu, který byl potřebný v předchozí části. Krok 1, 2 a 4 výše mají dostatečně zjevnou realizaci. Krok 3 však není tak triviální.
Konkrétně, potřebujeme být schopni dokázat, že zašifrované pi(j) skutečně odpovídají publikovaným Po tomto kroku by měly zůstat pouze polynomy, pro které soukromě předané Pokud to nedokážeme, útočník i může poslat odpad místo pi(j) účastníkovi j, a účastník j nebude schopen získat skutečnou hodnotu pi(j), a nebude schopen vypočítat svou soukromou komponentu.
Existuje kryptografický protokol, který umožňuje vytvořit další zprávu proofi(j), takže každý účastník, mající určitou hodnotu e, a také proofi(j) a pi(j)G, může lokálně ověřit, že e – je skutečně pi(j), zašifrované klíčem účastníka j. Bohužel, velikost takového důkazu je neuvěřitelně velká, a vzhledem k tomu, že je třeba publikovat O(nk) takových důkazů, nelze je pro tento účel použít.
Místo toho, abychom dokázali, že pi(j) odpovídá pi(j)G můžeme v protokolu generování polynomu vyčlenit velmi dlouhou dobu, během níž všichni účastníci kontrolují obdržené zašifrované pi(j), a pokud dešifrovaná zpráva neodpovídá veřejnému pi(j)G, publikují kryptografický důkaz, že obdržená zašifrovaná zpráva je chybná. Dokázat, že zpráva ne odpovídá pi(G) je mnohem jednodušší, než dokázat, že odpovídá. Je třeba poznamenat, že to vyžaduje, aby se každý účastník objevil v síti alespoň jednou během času přiděleného k vytváření takových důkazů, a spoléhat se na předpoklad, že pokud takový důkaz publikovali, dorazí ke všem ostatním účastníkům do stejného přiděleného času.
Pokud se účastník v tomto období v síti neobjevil a opravdu měl alespoň jednu nesprávnou komponentu, pak tento konkrétní účastník nebude moci účastnit další generace čísel. Protokol však bude stále fungovat, pokud existuje alespoň k účastníků, kteří buď právě obdrželi správné komponenty, nebo stihli poskytnout důkaz nesprávnosti v přiděleném čase.
Důkazy správnosti H_i
Poslední část, kterou je třeba prodiskutovat, je, jak prokázat správnost publikovaných Hi, konkrétně že Hi = p(i)H, bez odhalení p(i).
Vzpomeňme, že hodnoty H, G, p(i)G jsou veřejné a známé všem. Operace získávání p(i) znaje p(i)G a G se nazývá diskrétní logarithmus nebo dlog, a chceme prokázat, že:
dlog(p(i)G, G) = dlog(Hi, H)
bez zveřejnění p(i). Konstrukce pro takové důkazy existují, například.
S takovou konstrukcí každý účastník společně s Ahoj, odesílá důkaz správnosti podle konstrukce.
Když je náhodné číslo generováno, často je třeba použít ho účastníkům, kteří se liší od těch, kdo ho vygenerovali. Těmto účastníkům je třeba spolu s číslem posílat všechny Ahoj, a související důkazy.
Zvídavý čtenář se může zeptat: protože finální náhodné číslo je H0, a p(0)G – je to veřejná informace, proč je potřeba důkaz pro každé jednotlivé Hi, proč místo toho neodeslat důkaz, že
dlog(p(0)G, G) = dlog(H0, H)
Problémem je, že s pomocí Schnorr Protocol nelze vytvořit takový důkaz, protože nikdo nezná hodnotu p(0), potřebnou k vytvoření důkazu, a navíc celý generátor náhodných čísel je založen na tom, že nikdo nezná tuto hodnotu. Proto je nutné mít všechny hodnoty Ahoj, a jejich individuální důkazy, aby bylo možné prokázat správnost. H0.
Pokud by však na bodech eliptických křivin byla nějaká operace, která je sémanticky podobná násobení, prokázání správnosti H0 by bylo triviální, prostě bychom se ujistili, že
H0 × G = p(0)G × H
Pokud vybraná křivka podporuje , takový důkaz funguje. V takovém případě H0 – to není jen výstup generátoru náhodných čísel, který může zkontrolovat každý účastník, jenž zná G, H a p(0)G. H0 – to je také podpis na zprávě, která byla použita jako seed, potvrzující, že k a n účastníci podepsali tuto zprávu. Tím pádem, pokud seed – je to hash bloku v protokolu blockchainu, pak H0 – to je zároveň multi-podpis na bloku a velmi dobré náhodné číslo.
Na závěr
Tento článek je součástí série technických článků na blogu. . NEAR je blokchain protokol a platforma pro vývoj decentralizovaných aplikací se zaměřením na snadnost vývoje a uživatelskou přívětivost pro koncové uživatele.
Kód protokolu je otevřený, naše implementace je napsána v jazyce Rust, lze ji nalézt. .
Podívat se, jak vypadá vývoj na NEAR a vyzkoušet si to v online IDE, lze. .
Sledovat všechny novinky v ruštině lze v a v , a anglicky na oficiálním .
Na shledanou!
Zdroj: habr.com
