Ar įmanoma generuoti atsitiktinius skaičius, jei nepasitikime vieni kitais? 2 dalis

Sveiki, Habr!

В pirmoji dalis Šiame straipsnyje aptarėme, kodėl gali prireikti generuoti atsitiktinius skaičius dalyviams, kurie nepasitiki vienas kitu, kokie reikalavimai keliami tokiems atsitiktinių skaičių generatoriams, svarstėme du jų įgyvendinimo būdus.

Šioje straipsnio dalyje atidžiau pažvelgsime į kitą metodą, kuriame naudojami slenksčio parašai.

Šiek tiek kriptografijos

Norėdami suprasti, kaip veikia slenkstiniai parašai, turite suprasti šiek tiek pagrindinio kriptografijos. Vartosime dvi sąvokas: skaliarus arba tiesiog skaičius, kuriuos žymėsime mažosiomis raidėmis (x, y) ir elipsės kreivės taškus, kuriuos žymėsime didžiosiomis raidėmis.

Norėdami suprasti slenksčio parašų pagrindus, jums nereikia suprasti, kaip veikia elipsinės kreivės, išskyrus kelis pagrindinius dalykus:

1. Elipsinės kreivės taškus galima sudėti ir padauginti iš skaliaro (daugybą iš skaliro žymėsime kaip xG, nors žymėjimas Gx taip pat dažnai naudojamas literatūroje). Sudėjimo ir daugybos iš skaliro rezultatas yra elipsės kreivės taškas.

2. Žinant tik esmę G o jo sandauga su skaliaru xG negalima apskaičiuoti x.

Taip pat naudosime daugianario sąvoką p(x) laipsnis k-1. Visų pirma naudosime tokią daugianario savybę: jei žinome reikšmę p(x) bet kuriam k kitoks x (ir mes neturime daugiau informacijos apie p(x)), galime apskaičiuoti p(x) kam nors kitam x.

Įdomu tai, kad bet kuriam daugianario p(x) ir tam tikras kreivės taškas Gžinant prasmę p(x)G bet kuriam k skirtingos reikšmės x, taip pat galime paskaičiuoti p(x)G bet kuriam x.

Tai pakankamai informacijos, kad būtų galima išsiaiškinti, kaip veikia slenkstiniai parašai ir kaip juos naudoti atsitiktiniams skaičiams generuoti.

Atsitiktinių skaičių generatorius ant slenksčio parašų

Sakykim taip n dalyviai nori sugeneruoti atsitiktinį skaičių, o mes norime, kad dalyvautų bet kas k jų buvo pakankamai, kad sugeneruotų skaičių, bet kad užpuolikai, kurie valdytų k-1 ar mažiau dalyvių negalėjo numatyti arba paveikti generuojamo skaičiaus.

Tarkime, kad yra toks daugianomas p(x) laipsnis k-1 ką žino pirmasis dalyvis p (1), antrasis žino p(2), ir taip toliau (n– žino p(n)). Taip pat manome, kad tam tikram iš anksto nustatytam taškui G Visi žino p(x)G visoms vertybėms x. Mes paskambinsime p(i) „privatus komponentas“ idalyvis (nes tik idalyvis ją pažįsta) ir p(i)G „viešasis komponentas“ i-oji dalyvė (nes ją pažįsta visi dalyviai). Kaip pamenate, žinios p(i)G neužtenka atkurti p(i).

Kuriant tokį daugianarį, kad tik i-Pirmasis dalyvis ir niekas kitas nežinojo jo privataus komponento - tai yra sudėtingiausia ir įdomiausia protokolo dalis, kurią mes analizuosime toliau. Kol kas darykime prielaidą, kad turime tokį daugianarį ir visi dalyviai žino savo privačius komponentus.

Kaip galime naudoti tokį daugianarį atsitiktiniam skaičiui generuoti? Pirmiausia mums reikia tam tikros eilutės, kuri anksčiau nebuvo naudojama kaip generatoriaus įvestis. Blokų grandinės atveju – paskutinio bloko maiša h yra geras kandidatas tokiai linijai. Leiskite dalyviams sukurti atsitiktinį skaičių naudodami h kaip sėkla. Dalyviai pirmiausia konvertuoja h iki kreivės taško naudojant bet kurią iš anksto nustatytą funkciją:

H = skaliarinis taškas (h)

Tada kiekvienas dalyvis i skaičiuoja ir skelbia Hi = p(i)H, ką jie gali padaryti, nes žino p(i) ir H. Atskleidimas HNeleidžiu kitiems dalyviams atkurti privataus komponento idalyvis, todėl vienas privačių komponentų rinkinys gali būti naudojamas nuo bloko iki bloko. Taigi toliau aprašytą brangų daugianario generavimo algoritmą reikia vykdyti tik vieną kartą.

Kai k dalyvių buvo atlikta skrodimas Hi = p(i)H, kiekvienas gali paskaičiuoti Hx = p(x)H visiems x dėl daugianario savybių, kurią aptarėme paskutiniame skyriuje. Šiuo metu visi dalyviai skaičiuoja H0 = p(0)H, ir tai yra gautas atsitiktinis skaičius. Atkreipkite dėmesį, kad niekas nežino p(0), ir todėl vienintelis būdas apskaičiuoti p(0)H – tai yra interpoliacija p(x)H, kuri įmanoma tik tada, kai k vertybes p(i)H žinomas. Atidaromas bet koks mažesnis kiekis p(i)H nepateikia jokios informacijos apie p(0)H.

Aukščiau pateiktas generatorius turi visas norimas savybes: tik užpuolikai kontroliuoja k-1 ar mažiau dalyvių neturi informacijos ar įtakos išvadai, o bet k dalyviai gali apskaičiuoti gautą skaičių ir bet kurį jo poaibį k Dalyviai visada pasieks tą patį rezultatą toje pačioje sėkloje.

Yra viena problema, kurios mes kruopščiai išvengėme aukščiau. Kad interpoliacija veiktų, svarbu, kad vertė Hi, kurią paskelbė kiekvienas dalyvis i tikrai buvo tas pats p(i)H. Kadangi niekas, išskyrus i– dalyvis nežino p(i), niekas, išskyrus i-dalyvis negali to patikrinti Hi iš tikrųjų apskaičiuotas teisingai ir be jokio kriptografinio teisingumo įrodymo Hi užpuolikas gali paskelbti bet kokią reikšmę kaip Sveiki, ir savavališkai paveikti atsitiktinių skaičių generatoriaus išvestį:

Skirtingos pirmojo dalyvio atsiųstos H_1 reikšmės lemia skirtingą rezultatą H_0

Yra bent du būdai įrodyti teisingumą Hi, mes juos apsvarstysime išanalizavę daugianario generavimą.

Polinomo generacija

Paskutiniame skyriuje manėme, kad turime tokį daugianarį p(x) laipsnis k-1, kad dalyvis i žino p(i), ir niekas kitas neturi informacijos apie šią vertę. Kitame skyriuje mums taip pat reikės tam tikram iš anksto nustatytam taškui G visi žinojo p(x)G visiems x.

Šiame skyriuje manysime, kad kiekvienas dalyvis turi tam tikrą privatų raktą xi, kad visi žinotų atitinkamą viešąjį raktą Xi.

Vienas iš galimų daugianario generavimo protokolų yra toks:

1. Kiekvienas dalyvis i lokaliai sukuria savavališką daugianarį pi(x) laipsnis k-1. Tada jie siunčia kiekvieną dalyvį j vertė pi(j), užšifruotas viešuoju raktu Xj. Taip tik i-ый и j-ый dalyvis žino pi(j). Dalyvis i taip pat viešai skelbia pi(j)G visiems j nuo 1 į k imtinai.

2. Visi dalyviai pasirenka tam tikrą sutarimą k dalyviai, kurių daugianariai bus naudojami. Kadangi kai kurie dalyviai gali būti neprisijungę, negalime laukti, kol visi n dalyviai skelbs daugianarius. Šio žingsnio rezultatas yra rinkinys Z susidedantis iš mažiausiai k daugianariai, sukurti (1) veiksme.

3. Dalyviai įsitikina, kad vertybes žino pi(j) atitinka viešai paskelbtą pi(j)G. Po šio žingsnio Z tik daugianariai, kurie perduodami privačiai pi(j) atitinka viešai paskelbtą pi(j)G.

4. Kiekvienas dalyvis j apskaičiuoja savo privatųjį komponentą p(j) kaip suma pi(j) visiems i в Z. Kiekvienas dalyvis taip pat apskaičiuoja visas reikšmes p(x)G kaip suma pi(x)G visiems i в Z.

Atkreipkite dėmesį, kad p(x) – tai tikrai daugianomas k-1, nes tai individo suma pi(x), kurių kiekvienas yra laipsnio daugianario k-1. Tada atkreipkite dėmesį, kad nors kiekvienas dalyvis j žino p(j), jie neturi informacijos apie p(x) už x ≠ j. Iš tiesų, norėdami apskaičiuoti šią vertę, jie turi žinoti viską pi(x), ir tol, kol dalyvis j nežino bent vieno iš pasirinktų daugianario, jie neturi pakankamai informacijos apie p(x).

Tai yra visas daugianario generavimo procesas, kurio reikėjo paskutiniame skyriuje. Aukščiau pateikti 1, 2 ir 4 veiksmai yra gana akivaizdūs. Tačiau 3 žingsnis nėra toks trivialus.

Tiksliau, turime sugebėti įrodyti, kad tai užšifruota pi(j) tikrai atitinka publikuotus pi(j)G. Jei negalime įrodyti, užpuolikas i vietoj to gali siųsti šiukšles pi(j) dalyviui j, ir dalyvis j negalės gauti tikrosios vertės pi(j), ir negalės apskaičiuoti savo privataus komponento.

Yra kriptografinis protokolas, leidžiantis sukurti papildomą pranešimą įrodymasi(j), kad bet kuris dalyvis, turintis tam tikrą vertę e, taip pat įrodymas(j) и pi(j)G, gali tai patikrinti vietoje e - tikrai pi(j), užšifruotas dalyvio raktu j. Deja, tokių įrodymų dydis yra neįtikėtinai didelis, ir atsižvelgiant į tai, kad juos būtina paskelbti O (nk) Tokie įrodymai negali būti naudojami šiam tikslui.

Užuot tai įrodęs pi(j) atitinka pi(j)G polinomo generavimo protokole galime skirti labai ilgą laiko tarpą, per kurį visi dalyviai tikrina gautą užšifruotą pi(j), o jei iššifruotas pranešimas neatitinka viešumo pi(j)G, jie paskelbia kriptografinį įrodymą, kad gautas užšifruotas pranešimas yra neteisingas. Įrodykite, kad pranešimas ne atitinka pi(G) daug lengviau nei įrodyti, kad jis atitinka. Pažymėtina, kad tai reikalauja, kad kiekvienas dalyvis bent kartą per tokį įrodymui parengti skirtą laiką būtų internete, ir remiamasi prielaida, kad paskelbus tokį įrodymą, per tą patį skirtą laiką jis pasieks ir visus kitus dalyvius.

Jei dalyvis per šį laikotarpį nepasirodė internete ir turėjo bent vieną neteisingą komponentą, tas konkretus dalyvis negalės dalyvauti tolesniame skaičių generavime. Tačiau protokolas vis tiek veiks, jei bus bent jau k dalyvių, kurie ką tik gavo teisingus komponentus arba sugebėjo per nustatytą laiką palikti klaidingumo įrodymą.

H_i teisingumo įrodymai

Paskutinė dalis, kurią dar reikia aptarti, yra tai, kaip įrodyti paskelbimo teisingumą Haš, būtent tai Hi = p(i)H, neatidarius p(i).

Prisiminkime, kad vertybės H, G, p(i)G viešas ir visiems žinomas. Priėmimo operacija p(i) žinant p(i)G и G vadinamas diskrečiuoju logaritmu, arba dlogas, ir mes norime įrodyti, kad:

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

neatskleidus p(i). Pavyzdžiui, egzistuoja tokių įrodymų konstrukcijos Schnorr protokolas.

Su šiuo dizainu kiekvienas dalyvis kartu su Hi siunčia teisingumo įrodymą pagal projektą.

Sugeneravus atsitiktinį skaičių, jį dažnai turi naudoti kiti dalyviai, o ne tie, kurie jį sugeneravo. Tokie dalyviai kartu su numeriu turi atsiųsti visus Hi ir susijusius įrodymus.

Smalsus skaitytojas gali paklausti: kadangi galutinis atsitiktinis skaičius yra H0 ir p(0)G – Tai vieša informacija, kodėl mums reikia įrodymų kiekvienam asmeniui Haš, kodėl gi ne atsiųus to įrodymą

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

Problema ta, kad tokio įrodymo negalima sukurti naudojant Schnorr protokolą, nes niekas nežino vertės p (0), reikalingas įrodymui sukurti, be to, visas atsitiktinių skaičių generatorius yra pagrįstas tuo, kad šios reikšmės niekas nežino. Todėl būtina turėti visas vertybes Hi ir jų individualūs įrodymai, patvirtinantys teisingumą H0.

Tačiau jei elipsinių kreivių taškais būtų atlikta kokia nors operacija, semantiškai panaši į daugybą, teisingumo įrodymas H0 būtų nereikšminga, tiesiog tuo įsitikintume

H0 × G = p(0)G × H

Jei pasirinkta kreivė palaiko elipsinių kreivių poros, šis įrodymas veikia. Tokiu atveju H0 yra ne tik atsitiktinių skaičių generatoriaus išvestis, kurią gali patikrinti bet kuris išmanantis dalyvis G, H и p(0)G. H0 taip pat yra parašas ant pranešimo, kuris buvo naudojamas kaip pradžia, tai patvirtinantis k и n dalyviai pasirašė šią žinutę. Taigi, jei sėkla - yra bloko maiša bloko grandinės protokole, tada H0 yra ir kelių parašų blokas, ir labai geras atsitiktinis skaičius.

užbaigiant

Šis straipsnis yra techninio tinklaraščio serijos dalis NEAR. NEAR yra blokų grandinės protokolas ir platforma, skirta decentralizuotoms programoms kurti, pabrėžiant kūrimo ir naudojimo paprastumą galutiniams vartotojams.

Protokolo kodas atviras, mūsų diegimas parašytas Rust, galima rasti čia.

Galite pamatyti, kaip atrodo NEAR plėtra, ir eksperimentuoti internetinėje IDE čia.

Visas naujienas rusų kalba galite sekti adresu telegramų grupė ir grupė „VKontakte“., o anglų kalba oficialioje „twitter“.

Greitai pasimatysime!

Šaltinis: www.habr.com