Kriptografska razvrstavanje u blockchainsu: važnost VRF-a

Kad kripto može biti igrač sustava

Dok čitam i razumijem sve više i više o blockchain tehnologijama kao dijelu svog istraživačkog posla u Witnetu, počinjem shvaćati važnost kriptografskih protokola i shema na svoj dizajn. Nevjerojatno je kako mala dizajnerska odluka može utjecati na način na koji korisnici komuniciraju sa sustavom i, potencijalno, iskoristiti ga.

U ovom postu želim podijeliti neka interna istraživanja koja smo proveli u Witnetu i kako smo shvatili da naše kriptografske pretpostavke nisu dovoljno jake za naše početne svrhe.

PoE kao dio Blockchain protokola

Dokaz o podobnosti (PoE) postaju sve popularniji u Blockchain tehnologiji. Zapravo nam PoE daju priliku da odlučimo tko je odgovoran za izvršavanje neke akcije. Kad svaki vršnjak pojedinačno otkrije prihvatljivost, obično ga nazivamo kriptografskom shemom razvrstavanja, tj. Sposobnošću da sami otkrijete da li ste pobjednik “lutrije”.

Postoji nekoliko svojstava koja kriptografsko razvrstavanje treba da bi se ispunilo. Prvo, čvorovi pojedinačno trebaju biti u mogućnosti odrediti ispunjavaju li uvjete za obavljanje određene radnje. Drugo, prihvatljivost bi trebala biti kriptografski provjerena od strane ostalih kolega. Treće, kriptografska sortiranje povezana je s jednim identitetom, tj. Vršnjaci moraju biti sigurni da je dokaz generirao vršnjak koji to tvrdi. Uz to, također bi željeli da se dokaz ne razlikuje od slučajnog.

Primijetili smo nekoliko shema kriptografskog razvrstavanja koje su predložene kao dio blockchain dizajna, od dobro poznatog Dokazivanja rada u Bitcoin-u do novih prijedloga poput, npr .: Algorand, Filecoin ili Witnet. U ovom postu usredotočit ću se na kriptografsku razvrstavanje opisanu u Witnetu i moguća poboljšanja. Nadam se da su ovdje objavljene informacije korisne za ostale blockchaine s istom svrhom.

Kriptografska razvrstavanje na temelju digitalnog potpisa

Obično sheme kriptografskih razvrstavanja svoju prihvatljivost temelje na sreći dobivanja slučajnog broja koji padne ispod određene ciljne vrijednosti. Poteškoća očito ovisi o ciljanoj vrijednosti; što je veća vrijednost, to je veća vjerojatnost da vršnjaci moraju ispunjavati uvjete. Ciljna vrijednost zaista može varirati za različite vršnjake, možda ovisno o tome koliko su se dobro ponašali u prethodnim zadacima. To je upravo pristup koji je opisao Witnet. Kriptografska razvrstavanja u Witnetu definirana je kao:

Kriptografska razvrstavanje u Witnetu

Gdje <> označava potpis preko tipke M, a ja se odnosi na utjecaj vršnjaka i na vrijeme t. Utjecaj se odnosi na reputaciju čvora, tj. Koliko se dobro ponašao u prethodnim zadacima. U osnovi, ako hash potpisa zadatka koji vršnjak želi obaviti padne ispod ciljane vrijednosti, tada ona postaje prihvatljiva za izvršavanje zadatka. Promatramo kako svaki vršnjak može pojedinačno shvatiti svoju razvrstavanje bez interakcije s bilo kojim drugim vršnjakom u mreži. Slučajna vrijednost je zajednička za sve vršnjake (možda bi mogao biti hash prethodnog bloka).

Da bi se provjerila podobnost čvora, ostali čvorovi prvo provjere da je potpis generiran s odgovarajućim parametrima (slučajna vrijednost povezana s trenutnom epohom i zadatkom za koji se čvor bira). Potom oni stavljaju potpis da vide padne li ispod ciljane vrijednosti. Ako je to slučaj, provjerava se podobnost vršnjaka za zadatak.

Kriptografske razvrstavanja koje se temelje na digitalnim potpisima (tj. Potpisu određene poruke) ispunjavaju gore definirane izjave: generira ih određeni kolega, mogu se provjeriti javnim ključem i njihov se izlaz pojavljuje nasumično bez javnog ključa.

Ali sheme kriptografskog razvrstavanja zasnovane na digitalnom potpisu imaju tendenciju da se ispuni (kao u Witnetu) još jedan zahtjev koji nisam spomenuo: svaki bi vršnjak trebao imati jedan snimak podobnosti za ulaznu poruku. Inače, vršnjaci bi mogli samo voditi lutriju onoliko puta koliko su htjeli dok ne postanu podobni. Pitanje koje smo se postavili u Witnetu bilo je: da li digitalni potpisi ispunjavaju tu nekretninu?

Problem: ne jedinstven izlaz za ECDSA

Prije nego što dam odgovor na prethodno pitanje, dopustite mi da vam ukratko predstavim kako djeluje kriptografija Elliptic Curve.

Ukratko, kriptografija Elliptic Curve (ECC) je kriptosistem s javnim ključem u kojem svaki vršnjak ima par privatnih i javnih ključeva. Privatni ključ zna samo vlasnik, dok je javni ključ poznat svima. Vršnjaci u komunikaciji prvo se moraju složiti s krivuljom ECC-a koju oni
iskoristiti će. Krivulja je samo skup točaka definiran jednadžbom,
npr. y ^ 2 = x ^ 3 + ax + b. Krivulja je, između ostalih parametara, definirana generacijskom točkom zahvaljujući kojoj možemo doći do bilo koje druge točke krivulje. Da bi se konstruirao takav sustav, ECC konstruira sljedeću aritmetiku:

  • ako je P točka krivulje, -P je njezin odraz preko osi x
  • ako su dvije točke P i Q različite, rezultat je dodavanja P i Q
    izračunava se crtanjem linije koja presijeca P i Q, koja će se presijecati u a
    treća točka −R u krivulji. R izračunava se uzimajući odraz −R
    s obzirom na os x.
  • P + P izračunava se crtanjem tangencijalne crte na krivulju na P, koja
    opet će se presijecati u trećoj točki krivulje −P. 2P je samo
    odraz preko osi x
Primjer dodavanja eliptičke krivulje

Imajte na umu da ovom aritmetikom već možemo dodavati bodove i, prema tome, množiti točke s eskalarima (5P je samo 2P + 2P + P). Par privatnih i javnih ključeva konstruira se odabirom najprije slučajnog cijelog broja koji će nam poslužiti privatni ključ. Javni ključ je samo množenje cijelog broja s generatorskom točkom. Sigurnost sheme temelji se na poteškoći ili preuzimanju cijelog broja koji potiče iz točke javnog ključa. Ovo je, s obzirom na javni ključ Q, problem pronaći cijeli broj k koji je umnožio generator da bi postigao Q ekvivalentan je problemu diskretnog logaritma.

S takvim sustavom se već može izvesti nekoliko kriptografskih pristupa. Jedna od njih je mogućnost generiranja digitalnog potpisa. Cjelokupna slika generacije ECDSA signala može se vidjeti na sljedećoj slici

Generacija potpisa ECDSA

U osnovi, ulazna poruka m prvo se hashe. Kasnije je izabran slučajni broj u takav da se, množeći se s generatorom točke G, preslikava u točku krivulje čija je x-koordinata 0. Ako ovaj uvjet nije zadovoljen, vrijednost u se ponovno bira. Ako jest, tada se inverza u množi s (e + dr) dok vrijednost ne bude jednaka nuli. Potpis je tuple (r, s).

U stvari, ne trebamo u potpunosti razumjeti algoritam da bismo shvatili da potpis (r, s) uvelike ovisi o slučajnoj vrijednosti u odabranoj liniji 5. To jest, vrijednost potpisa ovisit će o slučajnoj vrijednosti, i stoga dana poruka može preslikati na nekoliko različitih potpisa.

To je već u sukobu s onim što smo idealno opisali za kriptografsku razvrstavanje. Ako će prihvatljivost vršnjaka ovisiti o hashu potpisa koji može uzeti različite vrijednosti ovisno o izabranoj slučajnoj vrijednosti u, možemo očekivati ​​da će vršnjaci kontinuirano računati potpise dok ne pronađu onu za koju je hash dovoljno nizak, a samim tim postanu podobni. Zanimljivo je da kripto shema koja se koristi pruža vršnjacima priliku da se igraju u sustavu.

Rješenje: VRF-ovi kao kriptografska razvrstavanje

Unatoč spomenutom problemu, ne bismo se htjeli odreći svih prednosti koje digitalni potpis nudi u našoj shemi. Stoga, našoj kriptografskoj razvrstavanju moramo dodati svojstvo jedinstvenosti, kao da je riječ o „verziji s javnim ključem ključa HMAC“. Čini se da provjerljive slučajne funkcije (VRF-ovi) čine trik (i u stvari se koriste u Algorandu). VRF-ove prvi je put uveo Silvio Micali u [1]. VRF generiraju dva izlaza: takozvani "jedinstveni potpis" β i dokaz π. Osim što je kriptosistem s javnim ključem, imaju i sljedeća svojstva:

  • Otpor kolizije, tj. Teško je pronaći dva ulaza koja se preslikavaju na isti izlaz.
  • Pseudo slučajnost, tj. Izlaz ne razlikuje slučajno od strane bilo koga tko ne zna tajni ključ.
  • Pouzdana jedinstvenost, koja zahtijeva da, s obzirom na javni ključ, VRF ulaz m odgovara jedinstvenom izlazu β.

Posljednja je izjava prilično važna. To znači da će β uvijek biti jedinstven za datu ulaznu poruku i javni ključ, a dokaz može biti nasumičan. Dakle, vršnjaci ne mogu generirati nekoliko potpisa dok ne postignu dovoljno nisku vrijednost, jer će za isti unos uvijek dobiti istu vrijednost. Ovo je, oni lutriju pokreću samo jednom po ulaznoj poruci.

VRF primjer

Pitanje je naravno kako konstruirati te sheme. Slijedimo shemu predloženu u [2], koja opisuje VRF konstrukcije i za RSA i za ECC. Radi kratkoće izostavljamo RSA opis konstrukcije. Zaista, ECC nudi prednosti kripto shema u pogledu veličine ključa i potpisa u odnosu na RSA kako bi se postigla ista razina sigurnosti.

Algoritam za provjeru potpisa ECC-VRF može se vidjeti dolje. ECVRF_hash_to_curve je funkcija koja hashera cijeli broj do točke u krivulji. Suprotno tome, ECVRF_hash_points je funkcija koja ima nekoliko točaka u krivulji s cijelim brojem. S ove dvije pomoćne funkcije možemo konstruirati sljedeću shemu generiranja potpisa:

ECC-VRF generacija dokaza

Izlaz β se kasnije hashe radi provjere je li probavljeni ispod ciljane vrijednosti, dok dokaz π verifikator koristi za provjeru da li je izlaz doista izračunavan s pripadajućim javnim ključem i za datu poruku na sljedeći način:

Provjera dokaza ECC-VRF

Ako pogledamo algoritam, ako i samo ako je c 'jednak c dokaz je provjeren. Uspoređujući korak 15 iz provjere i korak 4 iz generacije potpisa, možemo vidjeti da će jednakost biti sve dok su u = Gt i v = Ht. Može li provjerivač to potvrditi bez poznavanja tajnog ključa k? U nastavku pokazujemo korektnost jednakosti:

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

Može se provjeriti da vrijedi jednakost bez da se mora znati tajna vrijednost k.

Zaključci

U ovom postu sam podijelio zašto sheme kriptografskog razvrstavanja zasnovane na digitalnom potpisu mogu predstavljati veliki poticaj vršnjacima za igru ​​u sustavu, posebno kada o njima ovisi podobnost zadatka. U slučaju Witneta, i rudarski i zahtjevi za zahtjevanjem podataka ovise o rezultatu sortiranja, pa stoga ne možemo predstavljati takav poticaj vršnjacima. Možemo doći do situacije u kojoj je nagrada za zahtjev za podacima dovoljno visoka da potakne vršnjake da uporno generiraju potpise za njega sve dok hash nije dovoljno nizak, a na taj način izvodi se vrsta dokaza o radu nedostupnog za zahtjeve za podacima. U stvari, ako čvorovi stave sve resurse na velikodušan zahtjev za podacima, tada će se ostali zaboraviti i na performanse sustava ozbiljno utjecati.

Čini se da provjerljive slučajne funkcije rješavaju gore opisan problem. Uistinu, zadržavaju sve prednosti digitalnog potpisa s dodatnom činjenicom: „potpis“ je jedinstven za dani javni ključ i poruku. Dodatno VRF generiraju dokaz zahvaljujući kojem verifikator može provjeriti valjanost transakcije. Stoga se čini da su VRF-ovi pravi pristup za sustave poput Witneta.

Reference

  • 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