Kas on võimalik genereerida juhuslikke numbreid, kui me ei usalda üksteist? Osa 2

Tere, Habr!

V esimeses osas Artiklis arutasime, miks võib olla vajalik genereerida juhuslikke numbreid osalejatele, kes ei usalda üksteist, millised nõuded sellistele juhuslike arvu generaatoritele esitakse, ja vaatasime kaht lähenemist nende rakendamiseks.

Selles artikli osas vaatame lähemalt veel üht lähenemist, mis kasutab piirsigneeringuid.

Veidi krüptograafiast

Kuna piirsigneeringute toimimise mõistmiseks on vajalik pisut põhiteadmisi krüptograafiast. Kasutame kahte kontseptsiooni: skalaare, ehk lihtsalt numbreid, mida tähistame väikeste tähtedega (x, y) ja punkte elliptilisel kõveral, mida tähistame suurte tähtedega.

Piirsigneeringute põhialuste mõistmiseks pole vaja teada, kuidas elliptilised kõverad töötavad, välja arvatud mõned põhiasjad:

1. Elliptilise kõvera punktide kokkulaskmine ja skalaari korrutamine on võimalik (skalaari korrutamist tähistame kui xG, kuigi notaatsioon Gx ka kasutatakse sageli ka kirjanduses). Skalaari liitmise ja korrutamise tulemus on punkt elliptilisel kõveral.

2. Teades ainult punkti G ja selle korrutist skalaari xG ei saa arvutada x.

Kasutame ka polünoomi kontseptsiooni p(x) aste k-1. Eelkõige kasutame järgmist polünoomide omadust: kui teame väärtust p(x) kõigile k erinevatele x (ja meil pole rohkem teavet p(x)), saame arvutada p(x) kõigile teistele x.

Huvitav, et iga polünoomi p(x) ja mingi punkt kõveral G, teades väärtust p(x)G kõigile k erinevate väärtuste x, saab samuti arvutada p(x)G kõigil x.

Seda teavet piisab, et süveneda detailidesse, kuidas töötavad läve allkirjad ja kuidas neid kasutada juhuslike arvude genereerimiseks.

Läve allkirjad põhinev juhuslike arvude generaator

Oletame, et n osalejad soovivad genereerida juhuslikku arvu, ja me tahame, et ükskõik milline k nendest oleks piisav, et genereerida number, kuid et pahatahtlikud isikud, kes kontrollivad k-1 või vähem osalejat, ei saa ennustada ega mõjutada genereeritud numbrit.

Oletame, et selline polünoom eksisteerib p(x) aste k-1, mis esimene osaleja teab p(1), teine teab p(2), ja nii edasi (n-ne teab p(n)). Samuti oletame, et mõnes eelnevalt määratud punktis G teavad kõik p(x)G kõigi väärtuste x. Me nimetame p(i) “privaatseks komponendiks” i-ndast osalejast (sest ainult i-ne osaleja teab seda), ja p(i)G “avalikuks komponendiks” i-ndast osalejast (sest kõik osalejad teavad seda). Nagu te mäletate, teadmine p(i)G ei ole piisav, et taastada p(i).

Sellise polünoomi loomine nii, et ainult i-ne osaleja ja keegi muu ei teaks oma privaatset komponenti – see on protokolli kõige keerulisem ja huvitavam osa, mida uurime allpool. Kui oletame, et selline polünoom meil on ja kõik osalejad teavad oma privaatseid komponente.

Kuidas me saame kasutada sellist polünoomi juhusliku numbri genereerimiseks? Esiteks vajame me mingit järjekorda, mis ei ole varem kasutatud sisendina genereerijale. Bloochain’i puhul on viimase bloki hash h – hea kandidaat selliseks järjekorraks. Oletame, et osalejad soovivad luua juhusliku numbri, kasutades h näiteks seemnena. Esmalt konverteerivad osalejad h punkt, kõveral kasutades mis tahes eelnevalt määratud funktsiooni:

H = skalaariPunkt(h)

Seejärel arvutab iga osaleja i välja ja avaldab Hi = p(i)H, mida nad saavad teha, sest nad teavad p(i) ja H. Paljastamine Hi ei luba teistel osalejatel taastada -nda osaleja privaatset komponenti, seega võib ühte komplekti privaatsetest komponentidest kasutada plokist plokki. Seetõttu tuleb allpool kirjeldatud keerukat polünoomide loomise algoritmi täita ainult üks kord. iosalejad paljastasid

Kui k kõik saavad arvutada Hi = p(i)H, x = Hp(x)H tänu polünoomide omadusele, millest me eelmisel jaosal rääkisime. Sel hetkel arvutavad kõik osalejad kõigile x H0 = p(0)H, ja see ongi tulemuseks olev juhuslik number. Pange tähele, et keegi ei tea p(0), ja seega on ainus viis arvutada p(0)H – see on interpoleerimine p(x)H, mis on võimalik ainult siis, kui värtused k p(i)H on tuntud. Iga väiksema hulga paljastamine ei anna mingit teavet on tuntud. Iga väiksema hulga paljastamine p(0)H. p(0)H.

Ülaltoodud generaatoril on kõik omadused, mida me soovime: säilitajad, kes kontrollivad ainult k-1 osalejat või vähem, ei oma mingit teavet ega mõju väljundile, samas kui igasugused k osalejad saavad arvutada tulemuse ning iga alamhulk k osalejad jõuavad alati sama tulemusele sama algväärtuse puhul.

On üks probleem, mida me eelnevalt ettevaatlikult mööda vaatasime. Et interpoleerimine toimiks, on oluline, et väärtus Hi, mille iga osaleja avaldas, i oleks tõepoolest võrdsed p(i)H. Kuna keegi peale i-nda osaleja ei tea p(i), ei saa keegi peale i--nda osaleja kinnitada, et Tere tõepoolest arvutatakse õigesti, ja ilma mingi krüptograafilise tõendita õigsusest Hi, võiks küberkurjategija avaldada mõnda väärtust kui Tere, ja juhuslikult mõjutada juhusliku arvu generaatori väljundit.:

Erinevad H_1 väärtused, mille esimene osaleja saadab, viivad erinevate tulemuste H_0-ni.

On vähemalt kaks viisi tõestada Hi korrektsust, vaatame neid hiljem, kui käsitleme polünoomi genereerimist.

Polünoomi genereerimine

Eelmises jaotises eeldasime, et meil on selline polünoom p(x) aste k-1, et osaleja i teab p(i), ja mitte keegi teine ei tea selle tähenduse kohta mingit teavet. Järgmises lõigus peame samuti tagama, et teatud eelnevalt määratletud punktile G kõik teavad p(x)G kõigile x.

Selles osas eeldame, et igal osalejal on kohalikult mingi privaatvõti xi, nii et vastav avalik võti on kõigile tuntud Xi.

Üks võimalik polünoomi genereerimise protokoll on järgmine:

1. Iga osaleja i loob kohalikult suvalise polünoomi pi(x) astme k-1. Seejärel saadavad nad igaühele osalejale j väärtus pi(j), krüpteerituna avaliku võtmega Xj. Nii teavad ainult i-j- ja osalejaidj- i(j). Osaleja pavalikult kuulutab samuti i pi(j)G kaasa arvatud. kõigile j alates 1 kuni k Kõik osalejad kasutavad teatud konsensust, et valida

2. osalejad, kelle polünoome kasutatakse. Kuna mõned osalejad võivad olla võrguühenduseta, ei saa me oodata, kuni kõik k osalejad avaldavad polünoome. Selle sammu tulemus on kogum n mille hulka kuulub vähemalt Z polünoome, mis loodi sammul (1) k Osalejad veenduvad, et neile tuntud väärtused.

3. i(j) vastavad avalikult kuulutatud ppi(j)G. Pärast seda sammu on Pärast seda sammu on Z peavad jääma ainult polünoomid, mille puhul on edastatud privaatsed ppi(j)G. Pärast seda sammu on

4. Iga osaleja j arvutab oma privaatkomponendi p(j) nagu summa pi(j) kõigi jaoks i ühes Z. Iga osaleja arvutab ka kõik väärtused p(x)G nagu summa pi(x)G kõigi i jaoks ühes Z.

Pange tähele, et p(x) – see on tõepoolest polünoom astmest k-1, sest see on eraldi osade summa pi(x), millest igaüks on polünoom astmest k-1. Siis, tähelepanu, et kuigi igal osalejal on j teab p(j), ei ole neil mingit teavet p(x) kuna x ≠ j. Tõepoolest, et seda väärtust arvutada, peavad nad teadma kõiki pi(x), ja seni, kuni osaleja j ei tea vähemalt ühte valitud polünoomi, ei ole neil piisavalt teavet p(x).

See on kogu polünoomi genereerimise protsess, mis oli vajalik eelnevates jaotistes. Sammud 1, 2 ja 4 on üsnagi ilmsed. Kuid samm 3 ei ole nii triviaalne.

Konkreetsemalt, peame suutma tõestada, et krüpteeritud pi(j) vastavad tõeliselt avaldatud Pärast seda sammu on Kui me ei saa seda tõestada, võib ründaja i saata prügi asemel pi(j) osalejale j, ja osaleja j ei saa tõelist väärtust pi(j), ja ei saa arvutada oma privaatkomponenti.

On olemas krüptograafiline protokoll, mis võimaldab luua täiendava sõnumi proofi(j), nii et iga osaleja, kellel on mingi väärtus e, ja samuti proofi(j) ja pi(j)G, võib kohapeal veenduda, et e – see on tõepoolest pi(j), osaleja võtmega krüptitud j. Kahjuks on sellise tõendi suurus uskumatult suur ja arvestades, et tuleb avaldada O(nk) selliseid tõendeid, pole neid selle eesmärgi saavutamiseks võimalik kasutada.

Kohas, et tõestada, et pi(j) vastab pi(j)G, saame polünoomi genereerimise protokollis eraldada väga pika ajavahemiku, mille jooksul kõik osalejad kontrollivad saadud krüptitud pi(j), ja kui dekrüpteeritud sõnum ei vasta avalikule pi(j)G, siis avaldavad nad krüptograafilise tõendi, et saadud krüptitud sõnum on vale. Tõestada, et sõnum ei vastab pi(G) kaugel lihtsam, kui tõestada, et see vastab. Tuleb märkida, et see nõuab, et iga osaleja ilmuks võrku vähemalt korra ajavahemiku jooksul, mis on ette nähtud selliste tõendite esitamiseks, ja põhineb eeldusega, et kui nad avaldasid sellise tõendi, saavutab see kõikidele teistele osalejatele sellel samal ajavahemikul.

Kui osaleja ei ilmu võrku selle ajavahemiku jooksul ja tal on tõepoolest vähemalt üks vale komponent, siis ei saa see konkreetne osaleja osaleda edasises numbrite genereerimises. Protokoll töötab siiski jätkuvalt, kui on vähemalt k osalejat, kes on saanud ainult õiged komponendid või on suutnud jätta vale tõendi ette nähtud ajavahemiku jooksul.

H_i õiguse tõendid

Viimane osa, mida on veel arutada, on see, kuidas tõestada avaldatud Hi, nimelt et Hi = p(i)H, ilma avamiseta p(i).

Käidame meeles, et väärtused H, G, p(i)G on avalikud ja kõigile teada. Saamisel operatsioon p(i) teades p(i)G ja G nimetatakse diskrreetseks logaritmiks või dlog, ja me tahame tõestada, et:

dlog(p(i)G, G) = dlog(Hi, H)

ilma avaldamiseta p(i). Tõestuskonstruktsioonid selliste tõendite jaoks eksisteerivad, näiteks Schnorr Protokoll.

Sellise konstruktsiooni korral saadab iga osaleja koos Tere tõendi korrektsuse kohta vastavalt konstruktsioonile.

Kui juhuslik number on genereeritud, peavad osalejad sageli seda kasutama, erinevalt neist, kes selle genereerisid. Sellistele osalejatele tuleb koos numbriga saata kõik Tere ja lisatõendid.

Uudishimulik lugeja võib küsida: kuna lõplik juhuslik number on H0, ja p(0)G – see on avalik teave, miks on iga eraldi jaoks tõend vajalik Hi, miks mitte saata tõend, et

dlog(p(0)G, G) = dlog(H0, H)

Probleem on selles, et Schnorr Protokolliga ei saa sellist tõendit luua, sest keegi ei tea väärtust p(0), mis on vajalik tõendi loomiseks, ja veelgi enam, kogu juhuslikkuse generaator põhineb hüpoteesil, et keegi ei tea seda väärtust. Seetõttu on vajalikud kõik väärtused Tere ja nende individuaalsed tõendid, et tõestada korrektsust. H0.

Kuid kui elliptiliste kõverate punktidel oleks mingisugune tehe, mis on semantilises mõttes sarnane korrutamisele, oleks tõestamine triviaalne. H0 me lihtsalt veenduksime, et

H0 × G = p(0)G × H

Kui valitud kõver toetab elliptilisi kõvera paaritusi, siis see tõestus toimib. Sel juhul H0 ei ole mitte ainult juhuslike arvude generaatori väljund, mida võib kontrollida iga osaleja, kes teab G, H ja p(0)G. H0 on ka allkiri sõnumil, mis kasutati seemnena, kinnitades, et k ja n osalejad on selle sõnumi allkirjastanud. Seega, kui seeme – see on ploki hash plokiahelas, siis H0 – on see samal ajal mitme allkiri plokil ja väga hea juhuslik number.

Kokkuvõtteks

See artikkel on osa tehniliste artiklite seeriast blogis NEAR. NEAR on plokiahela protokoll ja platvorm detsentraliseeritud rakenduste arendamiseks, millel on rõhk arendamise lihtsusele ja lõppkasutajate jaoks kasutamise lihtsusele.

Protokolli kood on avatud, meie teostus on kirjutatud Rustis, selle leiate siin.

Vaata, milline näeb välja NEAR-i arendamine, ja katseta online-IDE-s. siit.

Jälgi kõiki uudiseid eesti keeles Telegrami grupis ja VKontakte grupis., aga inglise keeles ametlikul Twitteris.

Kohtumiseni!

Allikas: habr.com