Kryptografické triedenie v blockchainoch: význam VRF

Kedy kryptom môže byť systémový hráč

Keď čítam a čoraz viac chápem technológie blockchainu ako súčasť svojej výskumnej práce v Witnet, začínam si uvedomovať dôležitosť kryptografických protokolov a schém pri ich navrhovaní. Je úžasné, ako malé konštrukčné rozhodnutie môže ovplyvniť spôsob, akým používatelia interagujú so systémom, a prípadne ho využiť.

V tomto príspevku by som sa chcel podeliť o interný výskum, ktorý sme uskutočnili v spoločnosti Witnet, ao tom, ako sme si uvedomili, že naše kryptografické predpoklady neboli dosť silné na naše počiatočné účely.

PoE ako súčasť blockchainových protokolov

Dôkaz spôsobilosti (PoEs) sa v technológii Blockchain stáva čoraz obľúbenejším. Dokumenty o oprávnění (Proof of Entitlement) nám v skutočnosti dávajú možnosť rozhodnúť sa, kto je zodpovedný za vykonanie akcie. Keď každý partner zistí spôsobilosť jednotlivo, zvyčajne to označujeme ako schému kryptografického usporiadania, t. J. Schopnosť zistiť, či ste sami víťazom „lotérie“.

Existuje niekoľko vlastností, ktoré musí kryptografické usporiadanie vyplniť. Po prvé, uzly by mali byť individuálne schopné určiť, či sú spôsobilé na vykonanie určitej akcie. Po druhé, oprávnenosť by mala byť kryptograficky overiteľná inými rovesníkmi. Po tretie, kryptografické triedenie je spojené s jedinou identitou, t.j. rovesníci si musia byť istí, že dôkaz bol vygenerovaný rovesníkom, ktorý oň tvrdí. Ďalej by sme si tiež želali, aby bol dôkaz nerozoznateľný od náhodného.

Pozorovali sme niekoľko schém kryptografických tried, ktoré sa navrhujú ako súčasť návrhu blockchainu, od dobre známeho dokladu o práci v bitcoíne po nové návrhy, ako napríklad: Algorand, Filecoin alebo Witnet. V tomto príspevku sa zameriam na kryptografické usporiadanie opísané v Witnet a jeho možné vylepšenia. Dúfam, že tu zverejnené informácie sú užitočné pre ďalšie blockchainy s rovnakým účelom.

Kryptografické triedenie založené na digitálnych podpisoch

Schémy kryptografického triedenia zvyčajne zakladajú svoju spôsobilosť na šťastí, že dostanú náhodné číslo, ktoré klesne pod danú cieľovú hodnotu. Obtiažnosť samozrejme závisí od cieľovej hodnoty; čím vyššia je táto hodnota, tým väčšia je šanca, že sa na ňu môžu vzťahovať aj rovesníci. Cieľová hodnota sa môže skutočne líšiť pre rôznych rovesníkov, pravdepodobne v závislosti od toho, ako sa správali pri predchádzajúcich úlohách. Toto je presne ten prístup, ktorý opísal Witnet. Kryptografická klasifikácia v Witnet je definovaná ako:

Kryptografické triedenie vo Witnete

Kde <> označuje podpis cez kľúč M a I sa týka vplyvu rovesníka i v čase t. Vplyv sa týka reputácie uzla, t. J. Toho, ako dobre sa správal pri predchádzajúcich úlohách. Ak hash podpisu úlohy, ktorú chce partner vykonať, klesne pod cieľovú hodnotu, stane sa oprávnenou na vykonanie úlohy. Pozeráme sa, ako môže každý peer samostatne zistiť svoju klasifikáciu bez interakcie s iným peerom v sieti. Náhodná hodnota je porovnateľná so všetkými rovesníkmi (môže ísť o hash predchádzajúceho bloku).

Aby sa overila spôsobilosť uzla, zvyšok uzlov najskôr skontroluje, či bol podpis vygenerovaný s príslušnými parametrami (náhodná hodnota priradená k aktuálnej epoche a úlohe, pre ktorú sa uzol rozhoduje). Potom hash podpisu, aby zistili, či klesne pod cieľovú hodnotu. Ak áno, overí sa spôsobilosť partnera na danú úlohu.

Kryptografické klasifikácie, ktoré sú založené na digitálnych podpisoch (t. J. Podpis danej správy), plnia vyššie definované príkazy: sú generované daným peerom, sú overiteľné prostredníctvom verejného kľúča a ich výstup sa javí náhodne bez verejného kľúča.

Schémy kryptografického triedenia založené na digitálnom podpise však majú tendenciu naplniť (ako v prípade Witnetu) ďalšiu požiadavku, ktorú som nespomenul: každý partner by mal mať pre vstupnú správu jedinú šancu na získanie oprávnenosti. V opačnom prípade by rovesníci mohli lotériu prevádzkovať toľkokrát, koľkokrát chceli, kým sa stanú oprávnenými. Otázka, ktorú sme si položili vo Witneti, znie: plnia digitálne podpisy túto vlastnosť?

Problém: nejedinečný výstup pre ECDSA

Skôr ako odpoviem na predchádzajúcu otázku, dovoľte mi stručne predstaviť, ako funguje kryptografia Elliptic Curve Cryptography.

Stručne povedané, eliptická krivka kryptografie (ECC) je kryptosystém s verejným kľúčom, v ktorom každý partner má dvojicu súkromných a verejných kľúčov. Súkromný kľúč pozná iba vlastník, zatiaľ čo verejný kľúč je známy všetkým rovesníkom. Komunikační rovesníci sa najprv musia dohodnúť na krivke ECC, ktorú majú
budú využívať. Krivka je iba súbor bodov definovaných rovnicou,
napr. y ^ 2 = x ^ 3 + ax + b. Krivka je definovaná, okrem iných parametrov, generátorovým bodom, vďaka ktorému môžeme dosiahnuť akýkoľvek iný bod v krivke. Aby bolo možné zostaviť takýto systém, ECC vytvára nasledujúcu aritmetiku:

  • ak P je bod v krivke, -P je jeho odraz nad osou x
  • ak sú dva body P a Q zreteľné, výsledok sčítania P a Q je
    vypočítané nakreslením čiary prechádzajúcej cez P a Q, ktorá sa pretína v a
    tretí bod - R v krivke. R sa vypočíta na základe odrazu -R
    vzhľadom na os x.
  • P + P sa vypočíta nakreslením dotyčnice k krivke na P, ktorá
    opäť sa pretína v treťom bode v krivke −2P. 2P je iba
    odraz nad osou x
Príklad pridania eliptickej krivky

Všimnite si, že pomocou tejto aritmetiky už môžeme pridať body a následne vynásobiť body eskalátormi (5P je iba 2P + 2P + P). Dvojica súkromných a verejných kľúčov je vytvorená tak, že najprv vyberie náhodné celé číslo, ktoré nám bude slúžiť ako súkromný kľúč. Verejný kľúč je iba násobením celého čísla bodom generátora. Bezpečnosť schémy spočíva v ťažkostiach alebo načítaní celého čísla, ktoré má pôvod v kľúči verejného kľúča. Toto je vzhľadom na verejný kľúč Q problém nájsť celé číslo k, ktoré vynásobilo generátor na dosiahnutie Q, ekvivalent problému diskrétneho logaritmu.

S takýmto systémom je už možné vykonať niekoľko kryptografických prístupov. Jednou z nich je schopnosť vytvárať digitálne podpisy. Celkový obrázok generovania sigantúr ECDSA je možné vidieť na nasledujúcom obrázku

Generovanie podpisov ECDSA

V zásade je vstupná správa m najprv hashovaná. Neskôr sa náhodné číslo u vyberie tak, že keď sa vynásobí bodom G generátora, mapuje sa na bod v krivke, ktorého súradnica x je 0. Ak táto podmienka nie je splnená, hodnota u sa vyberie znova. Ak je, potom sa inverzia u vynásobí (e + dr), kým nie je hodnota nula. Podpisom je n-tica (r, s).

V skutočnosti nemusíme úplne porozumieť algoritmu, aby sme si uvedomili, že podpis (r, s) vo veľkej miere závisí od náhodnej hodnoty u vybranej v riadku 5. To znamená, že hodnota podpisu bude závisieť od náhodnej hodnoty, a preto daná správa môže mapovať na niekoľko rôznych podpisov.

To je už v rozpore s tým, čo sme v ideálnom prípade opísali pre kryptografickú klasifikáciu. Ak spôsobilosť partnera bude závisieť od hašovania podpisu, ktorý môže mať rôzne hodnoty v závislosti od vybranej náhodnej hodnoty u, môžeme očakávať, že rovnocenní budú priebežne počítať podpisy, až kým nenájdu ten, pre ktorý je hash dostatočne nízky, a teda stať sa oprávneným. Zaujímavé je, že použitá kryptogramová schéma dáva rovesníkom možnosť zahrať si systém.

Riešenie: VRF ako kryptografické usporiadanie

Napriek uvedenému problému by sme sa nechceli vzdať všetkých výhod, ktoré nášmu digitálnemu podpisu ponúka. Preto musíme do našej kryptografickej klasifikácie pridať vlastnosť jedinečnosti, akoby to bola „verzia verejného kľúča HMAC s kľúčom“. Zdá sa, že overiteľné náhodné funkcie (VRF) robia trik (a v skutočnosti sa používajú v Algorande). VRF prvýkrát predstavil Silvio Micali v roku [1]. VRF generujú dva výstupy: tzv. „Jedinečný podpis“ β a dôkaz π. Okrem toho, že sú kryptosystémom s verejným kľúčom, majú tieto vlastnosti:

  • Odolnosť proti kolízii, t. J. Je ťažké nájsť dva vstupy, ktoré mapujú rovnaký výstup.
  • Pseudonáhodnosť, t. J. Výstup je nerozoznateľný od náhodného ktokoľvek, kto nepozná tajný kľúč.
  • Dôveryhodná jedinečnosť, ktorá si vyžaduje, aby vzhľadom na verejný kľúč vstup m VRF zodpovedal jedinečnému výstupu β.

Posledné vyhlásenie je dosť dôležité. To znamená, že β bude vždy jedinečný pre danú vstupnú správu a verejný kľúč, zatiaľ čo dôkaz môže byť náhodný. Partneri teda nemôžu generovať niekoľko podpisov, kým nedosiahnu dostatočne nízku hodnotu, pretože pri rovnakom vstupe vždy dostanú rovnakú hodnotu. To znamená, že v každej vstupnej správe spustia lotériu iba raz.

Príklad VRF

Otázkou je samozrejme, ako tieto systémy zostaviť. Sledujeme schému navrhnutú v [2], ktorá opisuje konštrukcie VRF pre RSA aj ECC. Kvôli stručnosti vynecháme konštrukčný popis RSA. ECC skutočne ponúka výhody kryptografických schém, pokiaľ ide o veľkosť kľúča a podpisu v porovnaní s RSA, aby sa dosiahla rovnaká úroveň bezpečnosti.

Algoritmus overenia podpisu ECC-VRF je uvedený nižšie. ECVRF_hash_to_curve je funkcia, ktorá hashuje celé číslo do bodu v krivke. Naopak, ECVRF_hash_points je funkcia, ktorá hashuje niekoľko bodov v krivke celému číslu. S týmito dvoma pomocnými funkciami môžeme skonštruovať nasledujúcu schému generovania podpisu:

Generovanie dôkazov ECC-VRF

Výstup ß sa neskôr hashuje, aby sa skontrolovalo, či je výťah pod cieľovou hodnotou, zatiaľ čo dôkaz π sa používa na overenie, či sa výstup skutočne vypočítal s pridruženým verejným kľúčom a pre danú správu nasledujúcim spôsobom:

Overenie ECC-VRF

Ak sa pozrieme na algoritmus, overí sa, či a iba ak sa c 'rovná c. Ak porovnáme krok 15 z overenia a krok 4 z generovania podpisu, môžeme vidieť, že rovnosť bude platiť tak dlho, kým u = Gt a v = Ht. Môže to overovateľ overiť bez znalosti tajného kľúča k? V nasledujúcom texte demonštrujeme správnosť rovnosti:

  • Hodnota u = Qc + Gs = Qc + G (t-kc) = Qc + Gt-Gkc = Qc + Gt -Qc = Gt
  • Hodnota v = βc + Hs = βc + H (t-kc) = βc + Ht-Hkc = βc + Ht-βc = Ht

Môže sa overiť, že rovnosť platí bez toho, aby bolo potrebné poznať tajnú hodnotu k.

závery

V tomto príspevku som zdieľal, prečo môžu systémy kryptografického triedenia založené na digitálnom podpise predstavovať veľkú motiváciu pre kolegov, aby hrali systém, najmä ak od nich závisí spôsobilosť na úlohu. V prípade siete Witnet závisia úlohy ťažby aj požiadavky na údaje od výkonu triedenia, a preto nemôžeme pre takúto motiváciu pre kolegov predstavovať. Môžeme dosiahnuť situáciu, keď je odmena za požiadavku na údaje dostatočne vysoká na to, aby motivovala rovesníkov, aby pre ňu neustále generovali podpisy, kým hodnota hash nie je dostatočne nízka, a tak vykonávame určitý druh dôkazu o práci, ktorý nie je možné pre žiadosti o údaje vykonať. V skutočnosti, ak uzly umiestnia všetky zdroje na veľkorysú požiadavku na údaje, zvyšok sa zabudne a výkon systému by bol vážne ovplyvnený.

Zdá sa, že vyššie uvedené problémy riešia overiteľné náhodné funkcie. V skutočnosti si zachovávajú všetky výhody digitálnych podpisov s ďalšou skutočnosťou: „podpis“ je jedinečný pre daný verejný kľúč a správu. VRF navyše vygenerujú dôkaz, vďaka ktorému môže overovateľ skontrolovať platnosť transakcie. VRF sa teda javia ako správny prístup pre systémy ako Witnet.

Referencie

  • https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
  • https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/Verifiable_Random_Functions.pdf
  • https://filecoin.io/filecoin.pdf
  • https://witnet.io/static/witnet-whitepaper.pdf
  • https://eprint.iacr.org/2017/099.pdf
  • https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03