← Cloudflare Randomness Beacon / randomness-beacon / cryptographic-background

Fáze nastavení

Ve fázi nastavení drand vytvoříte kolektivní pár soukromého a veřejného klíče sdílený mezi 𝑛 účastníků. To se provádí pomocí 𝑡-of-𝑛 proces distribuovaného generování klíčů (DKG), jehož výsledkem je, že každý účastník obdrží kopii kolektivního veřejného klíče a podíl soukromého klíče z kolektivního soukromého klíče: žádný jednotlivý uzel nezná kolektivní privátní klíč. Každý podíl soukromého klíče lze poté použít k provádění kryptografických prahových výpočtů, například k generování prahových podpisů, kde je zapotřebí alespoň 𝑡 příspěvků vytvořených pomocí jednotlivých podílů soukromého klíče, aby bylo možné kolektivní operaci úspěšně dokončit.

DKG probíhá zcela distribuovaným způsobem, čímž se vyhýbá jakýmkoli jednotlivým bodům selhání. Toto je přehled jednotlivých dílčích komponent implementace DKG v drand.

Sdílení tajemství je důležitá technika, na které stojí řada pokročilých mechanismů prahové kryptografie.

Sdílení tajemství umožňuje rozdělit tajnou hodnotu 𝑠 do 𝑛 podílů 𝑠1,…,𝑠𝑛 tak, aby 𝑠 lze zrekonstruovat pouze tehdy, pokud je k dispozici prahový počet 𝑡 podílů je k dispozici.

Schéma SSS patří mezi nejznámější a nejrozšířenější přístupy ke sdílení tajemství a je klíčovou součástí drand. SSS funguje nad libovolným konečným tělesem, jednodušší přístup však používá celá čísla modulo 𝑝, označované jako ℤ𝑝. Nechť 𝑠∈ℤ𝑝 označuje tajemství, které se má sdílet.

Chcete-li sdílet 𝑠, distributor nejprve vytvoří polynom, 𝑞(𝑥)=𝑎0+𝑎1𝑥+⋯+𝑎𝑡−1𝑥𝑡−1 hodnotou 𝑎0=𝑠 a (náhodné) 𝑎𝑖∈ℤ𝑝 pro 𝑖=1,…,𝑡−1 a poté vytvoří jeden podíl 𝑠𝑖 pro každého účastníka 𝑖 vyhodnocením 𝑞(𝑥) v celém čísle 𝑖 a nastavením 𝑠𝑖=(𝑖,𝑞(𝑖)).

Chcete-li obnovit tajemství 𝑠, shromáždí alespoň 𝑡 podílů, pak jednoznačně zrekonstruovat 𝑞(𝑥) pomocí Lagrangeovy interpolace a získat 𝑠 jako 𝑠=𝑎0=𝑞(0).

Všimněte si, že můžete použít libovolnou podmnožinu 𝑡-of-𝑛 podílů k provedení Lagrangeovy interpolace a jednoznačnému určení 𝑠; mít však podmnožinu menší než 𝑡 podílů neumožňuje zjistit nic o 𝑠.

Schéma SSS předpokládá, že dealer je čestný, což však v praxi nemusí vždy platit. Schéma Verifiable Secret Sharing (VSS) chrání proti škodlivým dealerům tím, že umožňuje účastníkům ověřit, že jejich podíly jsou konzistentní s podíly rozdanými ostatním uzlům, což zajišťuje, že sdílené tajemství lze později správně rekonstruovat.

drand využívá Feldmanovo schéma VSS, rozšíření SSS. Nechť 𝔾 označuje cyklickou grupu prvočíselného řádu 𝑝 ve kterém je výpočet diskrétních logaritmů neřešitelný. cyklická grupa znamená, že existuje generátor, 𝑔, takže libovolný prvek 𝑥∈𝔾 lze zapsat jako 𝑥=𝑔𝑎 pro nějaké 𝑎∈{0,…,𝑝−1}.

Kromě distribuce podílů tajemství účastníkům dealer také rozesílá závazky ke koeficientům polynomu 𝑞(𝑥) ve tvaru (𝐴0,𝐴1,…,𝐴𝑡−1)=(𝑔𝑠,𝑔𝑎1,…,𝑔𝑎𝑡−1). Tyto závazky umožňují jednotlivým účastníkům, 𝑖, aby ověřili, že jejich podíl 𝑠𝑖=(𝑖,𝑞(𝑖)) je konzistentní vzhledem k polynomu 𝑞(𝑥) kontrolou, že 𝑔𝑞(𝑖)=∏𝑡−1𝑗=0(𝐴𝑗)𝑖𝑗 platí.

Obnovení tajemství 𝑠 funguje stejně jako běžné SSS, s tím rozdílem, že se používají podíly ověřené jako platné.

Ačkoli schémata VSS chrání proti škodlivému dealerovi, dealer stále zná tajemství. Pro vytvoření kolektivně sdíleného tajemství 𝑠 aby žádný jednotlivý uzel nezískal žádnou informaci, mohou účastníci použít protokol DKG. drand používá Pedersenovo schéma DKG, které spouští 𝑛 instancí Feldmanova VSS paralelně a navíc s dalšími ověřovacími kroky.

Jednotliví účastníci, 𝑖, vytvoří (náhodné) tajemství, 𝑠𝑖∈ℤ𝑝, a rozdělí jej mezi všechny účastníky pomocí VSS tím, že každému pošle podíl, 𝑠𝑖,𝑗 ke každému 𝑗 a rozešle seznam závazků (𝐴𝑖,0,𝐴𝑖,1,…,𝐴𝑖,𝑡−1) všem.

𝑗 ověří obdržené podíly podle schématu Feldmanova VSS. Pokud 𝑗 obdrží neplatný podíl, 𝑠𝑖,𝑗, z 𝑖, poté 𝑗 rozešle stížnost. 𝑖 musí odhalit správný podíl 𝑠𝑖,𝑗 nebo jsou považováni za neplatného distributora.

Na konci protokolu je konečný podíl 𝑖 je 𝑠𝑖=∑𝑗𝑠𝑗,𝑖 pro všechny platné účastníky 𝑗 , to znamená, pro všechny 𝑗není vyloučeno z ověřovací fáze.

Kolektivní veřejný klíč odpovídající platným podílům lze vypočítat jako 𝑆=∑𝑗𝐴𝑗,0 pro všechny platné 𝑗s.

Poznámka: Přestože tajemství vytvořené pomocí Pedersenova DKG může být zkreslené, je bezpečné jej použít pro prahové podepisování, jak ukázali Rabin a kol.