Krüptograafiline sortimine plokiahelates: VRFide tähtsus

Kui krüpto saab süsteemi mängija

Kui loen ja mõistan üha enam blockchain-tehnoloogiaid oma osana oma uurija tööst Witnetis, hakkan mõistma, kui olulised on krüptoprotokollid ja -skeemid nende kujundusel. On hämmastav, kuidas väike kujundusotsus võib mõjutada seda, kuidas kasutajad süsteemiga suhelda saavad ja seda potentsiaalselt ära kasutada.

Selles postituses tahaksin jagada mõnda siseuuringut, mille viisime läbi Witnetis, ja kuidas mõistsime, et meie krüptograafilised eeldused ei olnud meie esialgsetel eesmärkidel piisavalt tugevad.

PoE plokkkettide protokollide osana

Tõend abikõlblikkuse kohta on Blockchaini tehnoloogias muutumas üha populaarsemaks. Tegelikult annavad PoE-d meile võimaluse otsustada, kes vastutab toimingu eest. Kui abikõlblikkuse avastas iga eakaaslane eraldi, siis nimetame seda tavaliselt krüptograafiliseks sortimisskeemiks, s.o võimeks teada saada, kas olete ise „loterii” võitja.

Krüptograafilisel sortimisel tuleb täita mitmeid omadusi. Esiteks peaksid sõlmed eraldi suutma kindlaks teha, kas nad on sobilikud teatud toimingu tegemiseks. Teiseks peaksid abikõlblikkus olema krüptograafiliselt kontrollitav teiste kaaslaste poolt. Kolmandaks, krüptograafiline sortimine on seotud ühe identiteediga, s.t eakaaslased peavad olema kindlad, et tõendi genereeris seda nõudnud eakaaslane. Lisaks sooviksime, et tõendusmaterjal ei oleks juhuslik.

Vaatasime, et plokiahela kujunduse osana pakutaks välja mitmeid krüptograafilisi sortimisskeeme, alates Bitcoini tuntud tööproovist kuni uute ettepanekuteni, näiteks Algorand, Filecoin või Witnet. Selles postituses keskendun meie Witnetis kirjeldatud krüptograafilisele jaotusele ja selle võimalikele täiustustele. Loodan, et siin postitatud teave on abiks teistele sama otstarbega blokeeringutele.

Krüptograafiline sortimine digitaalallkirjade alusel

Tavaliselt põhinevad krüptograafilised sortimisskeemid kõlblikkusel õnnel saada juhuslik arv, mis jääb alla etteantud sihtväärtuse. Ilmselt sõltub raskus sihtväärtusest; mida suurem väärtus, seda rohkem võimalusi peavad kaaslased abikõlblikuks saama. Sihtväärtus võib erinevate eakaaslaste puhul erineda, võib-olla sõltuvalt sellest, kui hästi nad eelmistes ülesannetes käitusid. See on täpselt Witneti kirjeldatud lähenemisviis. Krüptograafiline sortimine Witnetis on määratletud järgmiselt:

Krüptograafiline sortimine Witnetis

Kus <> tähistab allkirja M-klahvi kohal ja I viitab peer i mõjule ajahetkel t. Mõju viitab sõlme mainele, s.o sellele, kui hästi ta eelmistes ülesannetes käitus. Põhimõtteliselt, kui eakaaslane soovib täita ülesande allkirja räsi, jääb allapoole sihtväärtust, siis saab ta ülesande täita. Jälgime, kuidas iga eakaaslane saab oma sorteerimise individuaalselt välja mõelda ilma, et peaks suhtlema võrgus asuvate teiste eakaaslastega. Juhuslik väärtus on tavapärane kõigile eakaaslastele (võib olla ka eelmise ploki räsi).

Sõlme sobivuse kontrollimiseks kontrollivad ülejäänud sõlmed esmalt, kas allkiri on genereeritud sobivate parameetritega (juhuslik väärtus, mis on seotud praeguse ajastu ja ülesandega, mille jaoks sõlm valib). Seejärel räsivad nad allkirja, et näha, kas see jääb alla sihtväärtuse. Kui jah, siis kontrollitakse eksperdi sobivust ülesandeks.

Digitaalallkirjadel (s.o antud teate allkiri) põhinevad krüptograafilised sortimendid täidavad ülalnimetatud avaldusi: need genereeritakse antud eakaaslase poolt, neid saab kontrollida avaliku võtme kaudu ja nende väljund näib juhuslikult ilma avaliku võtmeta.

Kuid digitaalallkirjaga põhinevad krüptograafilised sortimisskeemid täidavad (nagu Witneti puhul) veel ühe nõude, mida ma ei maininud: igal eakaaslasel peaks olema üks sisendsõnumi sobivuskujutis. Muidu võiksid eakaaslased lihtsalt loteriit korraldada nii mitu korda kui soovisid, kuni nad saavad kõlblikuks. Witnetis endale küsisime järgmist: kas digitaalallkirjad täidavad seda omadust?

Probleem: ECDSA jaoks ainulaadne väljund

Enne eelmisele küsimusele vastuse andmist lubage mul lühidalt tutvustada, kuidas Elliptic Curve krüptograafia töötab.

Lühidalt öeldes on elliptiline kõvera krüptograafia (ECC) avaliku võtme krüptosüsteem, milles igal peeril on privaat-avaliku võtme paar. Privaatvõti tunneb ainult omanik, samas kui avalik võti on teada kõigile eakaaslastele. Suhtlemiskaaslased peavad kõigepealt leppima kokku ECC kõveras
hakkame ära kasutama. Kõver on lihtsalt võrrandiga määratletud punktide kogum,
nt y ^ 2 = x ^ 3 + kirves + b. Kõverat määratlevad muude parameetrite hulgas generaatori punkt, tänu millele võime jõuda kõvera ükskõik millisesse muusse punkti. Sellise süsteemi konstrueerimiseks konstrueerib ECC järgmise aritmeetika:

  • kui P on kõvera punkt, on P selle peegeldus x-telje kohal
  • kui kaks punkti P ja Q erinevad, siis P ja Q liitmise tulemus on
    arvutatakse joonestades sirge, mis ristub punktiga P ja Q, mis ristub a-ga
    kolmas punkt −R kõveras. R arvutamiseks võetakse −R peegeldus
    x-telje suhtes.
  • P + P arvutatakse nii, et tõmmatakse kõverale puutuja sirge P juures, mis
    jälle ristub kõvera −2P kolmandas punktis. 2P on lihtsalt
    peegeldus x-telje kohal
Elliptilise kõvera lisamise näide

Pange tähele, et selle aritmeetika abil saame juba punkte lisada ja sellest tulenevalt korrutada punkte eskalaatoritega (5P on lihtsalt 2P + 2P + P). Privaat-avaliku võtme paar ehitatakse, valides kõigepealt juhusliku täisarvu, mis teenib meile privaatset võtit. Avalik võti on lihtsalt täisarvu korrutamine generaatori punktiga. Skeemi turvalisus sõltub avaliku võtme kohast pärit raskuste leidmisel või täisarvu leidmisel. See tähendab, et arvestades avalikku võtit Q, on täisarv k leidmise probleem, mis korrutas generaatori Q jõudmiseks, samaväärsena diskreetse logaritmi probleemiga.

Sellise süsteemi abil saab juba teostada mitmeid krüptograafilisi lähenemisi. Üks neist on digitaalallkirjade genereerimise võimalus. ECDSA sigantureerimise üldpilt on näha järgmisel pildil

ECDSA allkirjade genereerimine

Sisuliselt sisendsõnum m on kõigepealt räsitud. Hiljem valitakse juhuslik arv u selliselt, et generaatori punktiga G korrutatuna kaardistub see kõvera punkti, mille x-koordinaat on 0. Kui see tingimus ei ole täidetud, valitakse väärtus u uuesti. Kui see on nii, siis korrutatakse u pöördvõrrand arvuga (e + dr), kuni väärtus on nullist erinev. Allkiri on kord (r, s).

Tegelikult ei pea me täielikult mõistma algoritmi, et mõista, et allkiri (r, s) sõltub suuresti real 5 valitud juhuslikust väärtusest u. See tähendab, et allkirja väärtus sõltub juhuslikust väärtusest ja seetõttu, antud teade võib olla seotud mitme erineva allkirjaga.

See on juba vastuolus sellega, mida me ideaalis krüptograafilise jaotuse jaoks kirjeldasime. Kui eakaaslase sobivus sõltub allkirja räsist, mille väärtus võib sõltuvalt valitud juhuslikust väärtusest u võtta erinevaid väärtusi, võime eeldada, et eakaaslased arvutavad pidevalt allkirju, kuni nad leiavad, mille räsi on piisavalt madal, ja seega saada kõlblikuks. Huvitav on see, et kasutatud krüptoskeem annab eakaaslastele võimaluse süsteemi mängida.

Lahendus: VRF-id krüptograafilises sortimises

Vaatamata mainitud probleemile ei tahaksime loobuda kõigist eelistest, mida digitaalallkirjad meie skeemile pakuvad. Seetõttu peame oma krüptograafilistesse sortimentidesse lisama ainulaadsuse atribuudi, justkui oleks see "võtmega HMAC-i avaliku võtme versioon". Kontrollitavad juhuslikud funktsioonid (VRF-id) näivad trikki teevat (ja tegelikult kasutatakse neid Algorandis). VRF-id tutvustas Silvio Micali esmalt [1]. VRF-id genereerivad kahte väljundit: niinimetatud unikaalse allkirjaga β ja tõendiga π. Lisaks avaliku võtme krüptosüsteemile on neil ka järgmised omadused:

  • Kokkupõrketakistus, s.o on raske leida kahte sisendit, mis kaardistavad sama väljundi.
  • Pseudorandomness, st väljundit ei saa juhuslikust eristada kellelgi, kes salajast võtit ei tea.
  • Usaldusväärne unikaalsus, mis eeldab, et avaliku võtme korral vastab VRF sisend m ainulaadsele väljundile β.

Viimane väide on üsna oluline. See tähendab, et β on antud sisendteate ja avaliku võtme puhul alati ainulaadne, samas kui tõendusmaterjal võib olla juhuslik. Seega ei saa eakaaslased luua mitu allkirja enne, kui nad on saavutanud piisavalt madala väärtuse, kuna sama sisendi jaoks saavad nad alati sama väärtuse. See tähendab, et nad korraldavad loterii ainult üks kord sisestussõnumi kohta.

VRF-i näide

Muidugi on küsimus, kuidas neid skeeme üles ehitada. Järgime skeemi, mis on välja pakutud artiklis [2], mis kirjeldab VRF-i konstruktsioone nii RSA kui ka ECC jaoks. Lühiduse huvides jätame ära RSA ehituse kirjelduse. Tõepoolest pakub ECC krüptoskeemidele võtme- ja allkirja suuruse osas eeliseid võrreldes RSA-ga, et saavutada sama turvatase.

ECC-VRF allkirja kontrollimise algoritmi saab näha allpool. ECVRF_hash_to_curve on funktsioon, mis sirutab täisarvu kõvera punkti. Vastupidi, ECVRF_hash_points on funktsioon, mis riivab mitu punkti kõveras täisarvuni. Nende kahe abifunktsiooni abil saame luua järgmise allkirjade genereerimise skeemi:

ECC-VRF tõendite genereerimine

Väljund β on hiljem räsitud, et kontrollida, kas kokkuvõte on alla sihtväärtuse, samas kui kontrollija kasutab tõendit π, et kontrollida, kas väljund arvutati tõepoolest seotud avaliku võtmega ja antud teate jaoks järgmisel viisil:

ECC-VRF-i tõestamine

Kui vaatame algoritmi, siis ainult siis, kui c 'on võrdne c-ga, siis tõendust kontrollitakse. Kui võrrelda etappi 15 kontrollimise ja sammu 4 allkirjade genereerimisel, näeme, et võrdsus püsib nii kaua, kui u = Gt ja v = Ht. Kas kontrollija saab seda salajast võtit k tundmata kinnitada? Järgnevalt demonstreerime võrdsuse õigsust:

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

Võib kontrollida, kas võrdsus kehtib ka ilma salaväärtust k teadmata.

Järeldused

Selles postituses jagasin, miks võivad digitaalallkirjaga seotud krüptograafilised sortimisskeemid eakaaslastele süsteemi mängimiseks suurt ajendit pakkuda, eriti kui tööülesannete täitmine sõltub neist. Witneti puhul sõltuvad nii kaevandamise kui ka andmete päringu ülesanded sortimise väljundist ja seetõttu ei saa me eakaaslastele sellist stiimulit luua. Võime jõuda olukorrani, kus andmesidetaotluse tasu on piisavalt kõrge, et stimuleerida eakaaslasi selle eest püsivalt allkirju genereerima, kuni räsi on piisavalt madal, viies seega läbi andmetöötlustes alahinnatava teatud tüüpi töötagatise. Tegelikult, kui sõlmed seavad kõik ressursid helde andmetaotluse alla, siis ülejäänud ununevad ja süsteemi toimimine kahjustatakse tõsiselt.

Kontrollitavad juhuslikud funktsioonid näivad lahendavat ülalkirjeldatud probleemi. Nad säilitavad kõik digitaalallkirjade eelised koos lisaküsimusega: allkiri on antud avaliku võtme ja sõnumi jaoks ainulaadne. Lisaks loovad VRF-id tõendi, tänu millele saab kontrollija kontrollida tehingu õigsust. Seega näivad VRF-id õige lähenemisviis selliste süsteemide jaoks nagu Witnet.

Viited

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