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

Generování náhodnosti

V této části popisujeme, jak pomocí tohoto kolektivního páru klíčů generovat distribuovaným způsobem veřejně ověřitelnou, nezkreslitelnou a nepředvídatelnou náhodnost.

Nejprve vysvětlíme kryptografii založenou na párování (PBC), která si získala značnou oblibu a používá se v mnoha moderních konsenzuálních protokolech nebo důkazech s nulovou znalostí, jako jsou zk-SNARKs. Poté ukážeme, jak drand využívá PBC ve fázi generování majáku náhodnosti pro prahové podpisy Boneh-Lynn-Shacham (BLS). Nakonec probereme, jak drand propojuje vygenerované prahové BLS podpisy do řetězce náhodnosti.

Kryptografie založená na párování vychází z bilineárních grup (𝔾1,𝔾2,𝔾𝑡), kde 𝔾1, 𝔾2, a 𝔾𝑡 jsou cyklické grupy prvočíselného řádu 𝑝 s generátory 𝑔1, 𝑔2, a 𝑔𝑡, v uvedeném pořadí, a párovací operaci 𝑒:𝔾1×𝔾2→𝔾𝑡 s těmito vlastnostmi:

• Bilinearita: ∀𝑎,𝑏∈ℤ∗𝑝,∀𝑃∈𝔾1,∀𝑄∈𝔾2, máme 𝑒(𝑎𝑃,𝑏𝑄)=𝑒(𝑃,𝑄)𝑎𝑏

• Nedegenerovanost: 𝑒≠1

• Vypočitatelnost: Existuje efektivní algoritmus pro výpočet 𝑒. drand v současnosti používá křivku Barreto-Lynn-Scott BLS12-381.

K generování veřejně ověřitelné, nezkreslitelné a distribuované náhodnosti využívá drand prahové podpisy Boneh-Lynn-Shacham (BLS). Nejprve popíšeme běžné podpisy BLS a poté jejich prahovou variantu.

BLS podpisy jsou krátké podpisy, které se opírají o bilineární párování a sestávají pouze z jediného prvku v 𝔾1. Jsou deterministické v tom smyslu, že závisí pouze na zprávě a klíči podepisujícího, na rozdíl od jiných podpisových schémat, jako je ECDSA, která pro zajištění bezpečnosti vyžadují pro každou podepsanou zprávu novou náhodnou hodnotu. Jinými slovy, libovolné dva BLS podpisy na dané zprávě vytvořené stejným klíčem jsou identické. V drand tuto vlastnost využíváme k dosažení nezkreslitelnosti při generování náhodnosti.

Schéma podpisu BLS se skládá z následujících dílčích postupů.

Pro vygenerování páru klíčů si podepisující nejprve zvolí soukromý klíč, 𝑥∈ℤ∗𝑝, náhodně, a poté vypočítá odpovídající veřejný klíč jako 𝑋=𝑔𝑥2∈𝔾2.

Nechť 𝐻:{0,1}∗→𝔾1 označuje kryptografickou hashovací funkci, která mapuje libovolné bitové řetězce na prvky 𝔾1. Pro výpočet BLS podpisu 𝜎 na zprávě 𝑚, podepisující vypočítá 𝜎=𝑥𝐻(𝑚)∈𝔾1.

Chcete-li ověřit, že podpis BLS 𝜎 na zprávě 𝑚 je platný, ověřovatel zkontroluje, zda 𝑒(𝐻(𝑚),𝑋)=𝑒(𝜎,𝑔2) platí při použití veřejného klíče podepisujícího 𝑋.

Všimněte si, že tato rovnice platí pro platné podpisy, protože 𝑒(𝐻(𝑚),𝑋)=𝑒(𝐻(𝑚),𝑔𝑥2)=𝑒(𝐻(𝑚),𝑔2)𝑥=𝑒(𝑥𝐻(𝑚),𝑔2)=𝑒(𝜎,𝑔2).

Cílem prahového schématu podpisu je společně vypočítat podpis kombinací jednotlivých dílčích podpisů, které účastníci generují nezávisle na sobě. Prahové schéma podpisu BLS zahrnuje následující dílčí postupy.

𝑛 účastníků spustí 𝑡-of-𝑛 DKG pro nastavení kolektivního veřejného klíče, 𝑆∈𝔾2, a podíly soukromého klíče 𝑠𝑖∈ℤ∗𝑝 neznámého kolektivního soukromého klíče, 𝑠, jak je popsáno výše.

Chcete-li podepsat zprávu, 𝑚, každý 𝑖 použije svůj podíl soukromého klíče, 𝑠𝑖, aby vytvořil částečný BLS podpis, 𝜎𝑖=𝑠𝑖𝐻(𝑚).

Chcete-li ověřit správnost dílčího podpisu, 𝜎𝑖, na 𝑚, ověřovatel použije podíl veřejného klíče, 𝑆𝑖, vygenerovaný během DKG, a ověří, že 𝑒(𝐻(𝑚),𝑆𝑖)=𝑒(𝜎𝑖,𝑔2) platí.

Chcete-li rekonstruovat kolektivní podpis BLS, 𝜎 na 𝑚, ověřovatel nejprve shromáždí 𝑡 různých a platných částečných podpisů BLS, 𝜎𝑖, na 𝑚 následovaná Lagrangeovou interpolací.

Chcete-li ověřit kolektivní podpis BLS, 𝜎, ověřovatel zkontroluje, že 𝑒(𝐻(𝑚),𝑆)=𝑒(𝜎,𝑔2) platí, kde 𝑆 je kolektivní veřejný klíč.

Díky vlastnostem Lagrangeovy interpolace lze hodnotu 𝜎 nezávisí na podmnožině 𝑡 platných částečných podpisů, 𝜎𝑖, zvolených během rekonstrukce podpisu. Lagrangeova interpolace navíc zaručuje, že žádná množina obsahující méně než 𝑡 podepisujících může předvídat nebo zkreslit 𝜎.

Stručně řečeno, prahový BLS podpis, 𝜎, splňuje všechny vlastnosti požadované pro veřejně ověřitelnou, nezkreslitelnou, nepředvídatelnou a distribuovanou náhodnost.

Ve výše uvedeném, 𝔾1 a 𝔾2 by mohly být prohozeny. Důsledkem je vliv na relativní velikost veřejného klíče a podpisů. První řetězce drand jsou sestaveny tak, jak je popsáno výše, s podpisy na 𝔾2 a veřejné klíče na 𝔾1. Velikost podpisu je 96 bajtů a velikost veřejného klíče je 48 bajtů.

Některé aplikace preferují menší podpisy na úkor většího veřejného klíče. Proto mají některé majáky drand podpisy na 𝔾1 a veřejný klíč na 𝔾2. Taková změna se označuje jako 𝔾1/𝔾2 swap.

Maják náhodnosti drand pracuje v diskrétních kolech, 𝑟. V každém kole vygenerují majáky drand nakonfigurované pro řetězenou náhodnost novou náhodnou hodnotu pomocí prahových BLS podpisů propojených do řetězce náhodnosti. Aby tento řetězec náhodnosti prodloužil, každý účastník drand, 𝑖, vytvoří v kole 𝑟 částečný podpis BLS, 𝜎𝑟𝑖 na zprávě 𝑚=𝐻(𝑟∥𝜎𝑟−1) kde, 𝜎𝑟−1 označuje (úplný) prahový podpis BLS z kola 𝑟−1 a 𝐻, kryptografická hashovací funkce.

Jakmile alespoň 𝑡 účastníků rozeslalo své částečné podpisy, 𝜎𝑟𝑖, na 𝑚, může kdokoli obnovit úplný prahový podpis BLS, 𝜎𝑟 která odpovídá náhodné hodnotě kola 𝑟. Poté uzly drand přejdou do kola 𝑟+1 a proces zopakuje.

Pro kolo 𝑟=0, účastníci drand podepisují semínko pevně stanovené při nastavení drand. Tento proces zajišťuje, že každá nová náhodná hodnota závisí na všech dříve vygenerovaných podpisech. Jelikož je podpis deterministický, neexistuje ani možnost, aby útočník rozvětvil řetězec a předložil dva odlišné podpisy 𝜎𝑟 a 𝜎′𝑟 v daném kole 𝑟 k vytvoření nesrovnalostí v systémech, které se spoléhají na veřejnou náhodnost.

Majáky drand lze také nakonfigurovat tak, aby používaly nenavázanou náhodnost. Pro rozšíření tohoto řetězce náhodnosti každý účastník drand, 𝑖, vytvoří v kole 𝑟 částečný podpis BLS, 𝜎𝑟𝑖 na zprávě 𝑚=𝐻(𝑟) kde 𝐻 kryptografická hashovací funkce.

Tento proces umožňuje přímý předvýpočet zprávy 𝑚 pro kolo 𝑟=i.