Kriptografska razvrstitev v Blockchains: pomen VRF

Ko je kriptovalut lahko sistemski igralec

Ko berem in razumem vedno več o tehnologijah blockchain v okviru mojega raziskovalnega dela v Witnetu, se zavedam pomena kriptografskih protokolov in shem pri njihovi zasnovi. Neverjetno je, kako majhna oblikovalska odločitev lahko vpliva na način, kako uporabniki komunicirajo s sistemom in ga potencialno izkoristijo.

V tej objavi bi rad delil nekaj notranjih raziskav, ki smo jih izvedli v Witnetu, in kako smo ugotovili, da naše kriptografske predpostavke niso dovolj močne za naše začetne namene.

PoE kot del Blockchain protokolov

Dokazila o upravičenosti (PoE) postajajo vse bolj priljubljena v tehnologiji Blockchain. Dejansko nam PoE zagotavljajo priložnost, da se odločimo, kdo je odgovoren za izvedbo dejanja. Ko upravičenost odkrije vsak vrstnik posebej, jo ponavadi označimo kot kriptografsko shemo razvrščanja, tj. Zmožnost, da sami odkrijete, ali ste zmagovalec loterije.

Obstaja več lastnosti, ki jih mora izpolniti kriptografska razvrstitev. Najprej bi morala vozlišča posamično imeti možnost, da ugotovijo, ali so primerna za izvedbo določenega dejanja. Drugič, upravičenost bi morali kriptografsko preveriti drugi kolegi. Tretjič, kriptografska razvrstitev je povezana z eno samo identiteto, to pomeni, da morajo biti vrstniki prepričani, da je dokaz ustvaril vrstnik, ki ga je zahteval. Poleg tega bi želeli, da se dokaz ne loči od naključnega.

Opazili smo več shem kriptografskih razvrstitev, ki so bile predlagane kot del zasnove blockchain, od dobro znanega Proof of Work v Bitcoin-u do novih predlogov, na primer: Algorand, Filecoin ali Witnet. V tej objavi se bom osredotočil na kriptografsko razvrščanje, opisano v Witnetu, in njegove možne izboljšave. Upam, da so tukaj objavljene informacije koristne za druge blockchaine z istim namenom.

Kriptografska razvrstitev na podlagi digitalnih podpisov

Ponavadi sheme kriptografskih razvrščanja temeljijo na njihovi upravičenosti na sreči, da dobijo naključno število, ki pade pod dano ciljno vrednost. Težavnost je očitno odvisna od ciljne vrednosti; višja kot je vrednost, več možnosti je, da bodo vrstniki postali upravičeni. Ciljna vrednost se lahko res razlikuje pri različnih vrstnikih, morda odvisno od tega, kako dobro so se obnašali v prejšnjih nalogah. Prav to je pristop, ki ga je opisal Witnet. Kriptografska razvrstitev v Witnetu je opredeljena kot:

Kriptografska razvrstitev v Witnetu

Kjer <> označuje podpis nad tipko M in se nanaša na vpliv vrstnika i na čas t. Vpliv se nanaša na ugled vozlišča, tj. Kako dobro se je obnašal pri prejšnjih nalogah. V bistvu, če hash podpisa naloge, ki ga želi opraviti vrstnik, pade pod ciljno vrednost, potem postane upravičena do opravljanja naloge. Opažamo, kako lahko vsak vrstnik posamezno ugotovi svojo razvrstitev, ne da bi sodeloval z drugimi vrstniki v omrežju. Naključna vrednost je skupna vsem vrstnikom (morda bi bila mešavina prejšnjega bloka).

Da bi preverili ustreznost vozlišča, preostala vozlišča najprej preverijo, ali je bil podpis ustvarjen z ustreznimi parametri (naključna vrednost, povezana s trenutnim obdobjem in nalogo, za katero se vozlišče odloči). Nato imajo podpis, da vidijo, ali pade pod ciljno vrednost. V tem primeru je preverjena ustreznost vrstnika za nalogo.

Kriptografske razvrstitve, ki temeljijo na digitalnih podpisih (tj. Podpisu določenega sporočila), izpolnjujejo zgoraj opredeljene izjave: generira jih določen vrstnik, preverjajo jih prek javnega ključa in njihov izhod je naključen brez javnega ključa.

Toda kriptografske sheme razvrščanja na podlagi digitalnega podpisa ponavadi izpolnijo (kot v Witnetu) še eno zahtevo, ki je nisem omenil: vsak vrstnik bi moral imeti en vpogled v upravičenost za vhodno sporočilo. V nasprotnem primeru bi lahko vrstniki le lotili tolikokrat, kot bi želeli, dokler ne postanejo upravičeni. Vprašanje, ki smo si ga zastavili v Witnetu, je bilo: ali digitalni podpisi izpolnjujejo to lastnost?

Težava: edinstven izhod za ECDSA

Preden odgovorim na prejšnje vprašanje, naj na kratko predstavim, kako deluje kriptografija Elliptic Curve.

Na kratko, kriptografija Elliptic Curve (ECC) je kriptosistem z javnim ključem, v katerem ima vsak vrstnik par zasebnih in javnih ključev. Zasebni ključ pozna samo lastnik, medtem ko je javni ključ znan vsakemu vrstniku. Vrstniki komunikacije se morajo najprej strinjati z krivuljo ECC, ki jo imajo
bodo izkoristili. Krivulja je le množica točk, definiranih z enačbo,
npr. y ^ 2 = x ^ 3 + ax + b. Krivulja je med drugimi parametri določena s točko generatorja, s pomočjo katere lahko dosežemo katero koli drugo točko krivulje. Za izgradnjo takšnega sistema ECC konstruira naslednjo aritmetiko:

  • če je P točka krivulje, je -P njen odsev nad osjo x
  • če sta dve točki P in Q ločeni, je rezultat seštevanja P in Q enak
    izračunano z risanjem črte, ki prečkata P in Q, ki se bo presekala v a
    tretja točka –R v krivulji. R izračunamo z odsevom −R
    glede na os x.
  • P + P izračunamo tako, da na krivuljo pri P narišemo tangentno črto, ki
    se bo spet sekalo v tretji točki krivulje -2P. 2P je samo tisto
    odboj nad osjo x
Primer dodatka eliptične krivulje

Upoštevajte, da lahko s to aritmetiko že dodamo točke in posledično množimo točke s stopnicami (5P je le 2P + 2P + P). Par zasebnih in javnih ključev je sestavljen tako, da najprej izberemo naključno celo število, ki nam bo služilo zasebni ključ. Javni ključ je samo množenje celih števil s točko generatorja. Varnost sheme temelji na težavnosti ali pridobivanju celega števila, ki izvira iz točke javnega ključa. To je glede na javni ključ Q problem najti celo število k, ki je pomnožil generator, da bi dosegel Q, enakovredno problemu diskretnega logaritma.

S takim sistemom je že mogoče izvesti več kriptografskih pristopov. Ena izmed njih je možnost generiranja digitalnih podpisov. Celotno sliko generacije znakov ECDSA lahko vidite na naslednji sliki

Generacija podpisov ECDSA

V bistvu je vhodno sporočilo m najprej razstavljeno. Pozneje je izbrano naključno število u, ki se, pomnoženo z generatorjevo točko G, preslika v točko v krivulji, katere x-koordinata je 0. Če ta pogoj ni izpolnjen, se vrednost u ponovno izbere. Če je, potem je inverzno u pomnoženo s (e + dr), dokler vrednost ni nič. Podpis je tuple (r, s).

Pravzaprav ni treba popolnoma razumeti algoritma, da spoznamo, da je podpis (r, s) močno odvisen od naključne vrednosti u, izbrane v vrstici 5. To je, vrednost podpisa bo odvisna od naključne vrednosti, in zato dano sporočilo se lahko preslika na več različnih podpisov.

To je že v nasprotju s tistim, kar smo idealno opisali za kriptografsko razvrščanje. Če bo primernost vrstnika odvisna od mešanice podpisa, ki lahko sprejme različne vrednosti, odvisno od izbrane naključne vrednosti u, lahko pričakujemo, da bodo vrstniki nenehno izračunavali podpise, dokler ne bodo našli tistega, za katerega je hash dovolj nizek, in s tem postanejo upravičeni. Zanimivo je, da uporabljena kripto-shema omogoča vrstnikom možnost igre v sistem.

Rešitev: VRF-ji kot kriptografska razvrstitev

Kljub omenjeni težavi se ne bi radi odrekli vsem prednostim, ki jih digitalni podpisi ponujajo naši shemi. Zato moramo svoji kriptografski razvrstitvi dodati lastnost edinstvenosti, kot da gre za "različico z javnim ključem zaklenjenega HMAC". Zdi se, da preverljive naključne funkcije (VRF) naredijo trik (in v resnici se uporabljajo v Algorandu). VRF je prvič predstavil Silvio Micali v [1]. VRF ustvarjajo dva izhoda: tako imenovani „edinstveni podpis“ β in dokaz π. Poleg tega, da so kriptosistem z javnim ključem, imajo naslednje lastnosti:

  • Upornost proti trčenju, tj. Težko je najti dva vhoda, ki se preslikata na isti izhod.
  • Psevdonamernost, to je, da izhod ni ločen od naključnega, če kdo ne pozna skrivnega ključa.
  • Zaupanja edinstvenost, ki zahteva, da pod javno oznako vhod VRF m ustreza edinstvenemu izhodu β.

Zadnja izjava je precej pomembna. To pomeni, da bo β vedno enkraten za dano vhodno sporočilo in javni ključ, dokaz pa je morda naključen. Tako vrstniki ne morejo ustvariti več podpisov, dokler ne dosežejo dovolj nizke vrednosti, saj bodo za isti vložek vedno dobili isto vrednost. To je, loterijo izvedejo samo enkrat na vhodno sporočilo.

Primer VRF

Seveda je vprašanje, kako sestaviti te sheme. Sledimo shemi, predlagani v [2], ki opisuje konstrukcije VRF za RSA in ECC. Zaradi kratkosti izpustimo opis konstrukcije RSA. ECC ponuja kriptovalute v primerjavi z velikostmi ključev in podpisov v primerjavi z RSA za doseganje enake stopnje varnosti.

Algoritem za preverjanje podpisa ECC-VRF si lahko ogledate spodaj. ECVRF_hash_to_curve je funkcija, ki ima celo število do točke v krivulji. Nasprotno, ECVRF_hash_points je funkcija, ki ima več točk v krivulji na celo število. S pomočjo teh dveh pomožnih funkcij lahko sestavimo naslednjo shemo generiranja podpisov:

ECC-VRF dokaz generacije

Izhod β pozneje naključno preveri, ali je prebavo pod ciljno vrednostjo, dokaz π pa preveritelj preveri, ali je bil rezultat res izračunan s pripadajočim javnim ključem in za dano sporočilo na naslednji način:

Preverjanje dokaza ECC-VRF

Če pogledamo algoritem, če in samo, če je c 'enak c, je dokaz preverjen. Če primerjamo korak 15 iz preverjanja in korak 4 iz generacije podpisov, lahko vidimo, da bo enakost veljala tako dolgo, kot u = Gt in v = Ht. Lahko preveritelj to potrdi, ne da bi vedel skrivni ključ k? V nadaljevanju pokažemo korektnost enakosti:

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

Preverimo lahko, da velja enakost, ne da bi vedeli skrivno vrednost k.

Sklepi

V tej objavi sem delil, zakaj lahko sheme kriptografskih razvrščanja na podlagi digitalnega podpisa predstavljajo veliko spodbudo za vrstnike za igranje sistema, še posebej, če je upravičenost do naloge odvisna od njih. V primeru Witneta so tako rudarske kot zahteve za zahtevo podatkov odvisne od izida razvrščanja, zato ne moremo predstavljati takšne spodbude za vrstnike. Lahko pridemo do situacije, ko je nagrada za zahtevo za podatke dovolj visoka, da spodbudimo vrstnike, da vztrajno generirajo podpise zanj, dokler ne bo dovolj nizko, in s tem izvedemo nekakšno dokazilo o delu, ki ni mogoče za zahteve po podatkih. Dejansko če vozlišča vse vire dajo velikodušni zahtevi po podatkih, bodo ostali pozabljeni in delovanje sistema bi močno vplivalo.

Zdi se, da preverljive naključne funkcije rešujejo zgoraj opisano težavo. Dejansko ohranjajo vse prednosti digitalnega podpisa z dodatnim dejstvom: „podpis“ je edinstven za dani javni ključ in sporočilo. VRF-ji poleg tega ustvarijo dokaz, s katerim preveritelj lahko preveri veljavnost transakcije. Zato se zdi, da so VRF-ji pravi pristop za sisteme, kot je Witnet.

Reference

  • https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
  • https://people.csail.mit.edu/silvio/Selected%20Scientist%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