Bok, Habr!
U U članku smo raspravili zašto je možda potrebno generirati slučajne brojeve sudionicima koji si ne vjeruju, koje su zahtjeve postavljene pred takve generatore slučajnih brojeva i razmotrili dva pristupa njihovoj implementaciji.
U ovom dijelu članka detaljno ćemo razmotriti još jedan pristup koji koristi pragovne potpise.
Malo o kriptografiji
Da bismo razumjeli kako funkcioniraju pragovni potpisi, trebamo razumjeti malo osnovne kriptografije. Koristit ćemo dvije koncepcije: skalarne, ili jednostavno brojeve, koje ćemo označiti malim slovima (x, y) i točke na eliptičnoj krivulji, koje ćemo označiti velikim slovima.
Za razumijevanje osnova pragovnih potpisa nije potrebno razumjeti kako funkcioniraju eliptične krivulje, osim nekoliko osnovnih stvari:
Točke na eliptičnoj krivulji mogu se zbrajati i množiti sa skalarom (množenje sa skalarom označit ćemo kao xG, iako se notacija Gx također često koristi u literaturi). Rezultat zbrajanja i množenja sa skalarom je točka na eliptičnoj krivulji.
Znajući samo točku G i njen proizvod sa skalarom xG ne može se izračunati x.
Također ćemo koristiti koncept polinoma p(x) stepeni k-1. Konkretno, koristit ćemo svojstvo polinoma: ako znamo vrijednost p(x) za bilo koje k različite x (i nemamo više nikakve informacije o p(x)), možemo izračunati p(x) za bilo koji drugi x.
Zanimljivo je da, za bilo koji polinom p(x) i neku točku na krivulji G, znajući vrijednost p(x)G za bilo koje k različitih vrijednosti x, također možemo izračunati p(x)G za bilo koji x.
Ove informacije su dovoljne da se zagrebemo u detalje o tome kako funkcioniraju pragovni potpisi i kako ih koristiti za generiranje slučajnih brojeva.
Generator slučajnih brojeva na pragovnim potpisima
Pretpostavimo da n sudionici žele generirati slučajan broj, a mi želimo da sudjelovanje bilo kojih k od njih bude dovoljno da generiraju broj, ali da zlonamjerni akteri, koji kontroliraju k-1 ili manje sudionika, ne mogu predvidjeti ili utjecati na generirani broj.
Pretpostavimo da postoji takav polinom p(x) stepeni k-1, da prvi sudionik zna p(1), drugi zna p(2), i tako dalje (n-i zna p(n)). Također, pretpostavimo da za neku unaprijed određenu točku G svi znaju p(x)G za sve vrijednosti x. Nazvat ćemo p(i) “privatnom komponentom” i-og sudionika (jer samo i-i sudionik zna nju), i p(i)G “javnom komponentom” i-og sudionika (jer svi sudionici znaju nju). Kao što se sjećate, znanje p(i)G nije dovoljno za obnovu p(i).
Kreiranje takvog polinoma na način da samo i-i sudionik i nitko drugi zna svoju privatnu komponentu – to je najteži i najzanimljiviji dio protokola, i razmotrit ćemo ga u nastavku. Za sada pretpostavimo da imamo takav polinom, i da svi sudionici znaju svoje privatne komponente.
Kako možemo koristiti takav polinom za generiranje slučajnog broja? Prvo nam treba neka niz koja prije nije korištena kao ulaz za generator. U slučaju blockchaina, hash posljednje blokade h — dobar je kandidat za takvu niz. Pretpostavimo da sudionici žele stvoriti slučajan broj koristeći h kao seed. Prvo sudionici konvertiraju h u točku na krivulji koristeći bilo koju unaprijed određenu funkciju:
H = scalarToPoint(h)
Zatim svaki sudionik i izračunava i objavljuje Hi = p(i)H, što mogu učiniti jer znaju p(i) i H. Otkrivanje Hi ne omogućuje drugim sudionicima obnovu privatne komponente i-og sudionika, i stoga jedan skup privatnih komponenti može se koristiti od bloka do bloka. Dakle, skupi algoritam za stvaranje polinoma, opisan u nastavku, potrebno je izvršiti samo jednom.
Kada k sudionici su otkrili Hi = p(i)H, svi mogu izračunati Hx = p(x)H za sve x zahvaljujući svojstvu polinoma, koje smo raspravili u prethodnom odjeljku. U tom trenutku svi sudionici izračunavaju H0 = p(0)H, i to je rezultantni slučajni broj. Imajte na umu da nitko ne zna p(0), i stoga je jedini način da se izračuna p(0)H – to je interpolacija p(x)H, što je moguće samo kada k vrijednosti p(i)H su poznate. Otkrivanje bilo kojeg manjeg broja p(i)H ne daje nikakve informacije o p(0)H.
Generator iznad ima sve osobine koje želimo: zlonamjerni subjekti koji kontroliraju samo k-1 sudionika, ili manje, nemaju nikakve informacije i utjecaj na ishod, dok bilo koji k sudionici mogu izračunati rezultantni broj, i bilo koji podskup od k sudionici uvijek dolaze do istog rezultata za istu sjeme.
Postoji jedan problem koji smo pažljivo izbjegavali ranije. Da bi interpolacija radila, važno je da vrijednost Hi koju je objavio svaki sudionik i zapravo bude jednaka p(i)H. Budući da nitko osim i-og sudionika ne zna p(i), nitko osim i--og sudionika ne može provjeriti da Pozdrav zapravo je ispravno izračunato, i bez nekog kriptografskog dokaza o ispravnosti Hi zlonamjernik može objaviti bilo koju vrijednost kao Pozdrav, i proizvoljno utjecati na izlaz generatora slučajnih brojeva:
Različite vrijednosti H_1, poslane od prvog sudionika, dovode do različitih rezultantnih H_0
Postoje najmanje dva načina da se dokaže ispravnost Hi, razmotrit ćemo ih nakon što obradimo generaciju polinoma.
Generacija polinoma
U prethodnom odjeljku pretpostavili smo da imamo takav polinom p(x) stepeni k-1 koji sudionik i zna p(i), i nitko drugi nema nikakve informacije o toj vrijednosti. U sljedećem odjeljku također će nam biti potrebno da za neku unaprijed određenu točku G svi znaju p(x)G za sve x.
U ovom odjeljku smatrat ćemo da svaki sudionik lokalno ima neki privatni ključ xi, tako da je svima poznat odgovarajući javni ključ Xi.
Jedan mogući protokol generacije polinoma je sljedeći:
Svaki sudionik i lokalno stvara proizvoljni polinom pi(x) stupnja k-1. Oni zatim šalju svakom sudioniku j vrijednost pi(j), šifrirano javnim ključem Xj. Tako samo i-y i j-y sudionik zna pi(j). Sudionik i također javno objavljuje pi(j)G za sve j od 1 do k uključivo.
Svi sudionici koriste neki konsenzus kako bi odabrali k sudionike čiji će se polinomi koristiti. Budući da neki sudionici mogu biti izvan mreže, ne možemo čekati da svi n sudionici objave polinome. Rezultat ovog koraka je skup Z sastavljen od barem k polinoma stvorenih u koraku (1).
Sudionici se uvjeravaju da su poznate vrijednosti pi(j) u skladu s javno objavljenim pi(j)G. Nakon ovog koraka trebali bi ostati samo polinomi za koje privatno preneseni Z izračunava svoju privatnu komponentu pi(j) u skladu s javno objavljenim pi(j)G.
Svaki sudionik j p(j) kao zbroj i(j) za sve p. Svaki sudionik također izračunava sve vrijednosti i u Zpi(x)G za sve i p(x)G i(j) za sve p(x) – u Z.
Napomena, kada to je zapravo polinom stupnja k-1, . jer to je zbroj pojedinačnih pi(x), svaki od njih je polinom stupnja k-1. Zatim, obratite pažnju da dok svaki sudionik j zna p(j), nema nikakve informacije o p(x) za x ≠ j. Naime, da bi izračunali ovu vrijednost, moraju znati sve pi(x), i dok sudionik j ne zna barem jedan od odabranih polinoma, nemaju dovoljno informacija o p(x).
To je cijeli proces generiranja polinoma koji je bio potreban u prošlom odjeljku. Koraci 1, 2 i 4 iznad imaju dovoljno očiglednu implementaciju. Međutim, korak 3 nije tako trivijalan.
Specifično, trebamo biti u stanju dokazati da su šifrirani pi(j) zaista u skladu s objavljenim pi(j)G. Ako to ne možemo dokazati, napadač i može poslati smeće umjesto pi(j) sudioniku j, i sudionik j neće moći dobiti stvarnu vrijednost pi(j), i neće moći izračunati svoju privatnu komponentu.
Postoji kriptografski protokol koji omogućuje stvaranje dodatne poruke proofi(j), tako da bilo koji sudionik, imajući neku vrijednost e, a također proofi(j) i pi(j)G, može lokalno provjeriti da e – to je zaista pi(j), šifrirano ključem sudionika j. Nažalost, veličina takvog dokaza nevjerojatno je velika, i uzimajući u obzir da je potrebno objaviti O(nk) takvih dokaza, njihovo korištenje za ovu svrhu neće biti moguće.
Umjesto da dokazujemo da pi(j) odgovara pi(j)G, možemo u protokolu generiranja polinoma odvojiti vrlo dugo vremensko razdoblje, tijekom kojeg svi sudionici provjeravaju primljene šifrirane pi(j), i ako dešifrirana poruka ne odgovara javnom pi(j)G, objavljuju kriptografski dokaz da primljena šifrirana poruka nije ispravna. Dokazati da je poruka ne odgovara pi(G) mnogo je lakše nego dokazati da odgovara. Treba napomenuti da to zahtijeva da se svaki sudionik pojavi u mreži barem jednom tijekom vremena dodijeljenog za stvaranje takvih dokaza, i oslanja se na pretpostavku da ako su takav dokaz objavili, on će doći do svih drugih sudionika u to isto dodijeljeno vrijeme.
Ako se sudionik nije pojavio na mreži u tom razdoblju, a imao je barem jednu neispravnu komponentu, taj određeni sudionik neće moći sudjelovati u daljnjoj generaciji brojeva. Protokol će, međutim, i dalje funkcionirati ako postoji barem k sudionika koji su ili samo primili ispravne komponente ili su uspjeli ostaviti dokaze neispravnosti u zadanom vremenu.
Dokazi ispravnosti H_i
Posljednji dio koji treba raspraviti je kako dokazati ispravnost objavljenih Hi, to jest, što Hi = p(i)H, bez otkrivanja p(i).
Podsjetimo se da su vrijednosti H, G, p(i)G javne i poznate svima. Operacija dobivanja p(i) znajući p(i)G i G zove se diskretni logaritm, ili dlog, i želimo dokazati da:
dlog(p(i)G, G) = dlog(Hi, H)
bez otkrivanja p(i). Konstrukcije za takve dokaze postoje, na primjer,.
S tom konstrukcijom, svaki sudionik zajedno s Pozdrav šalje dokaz ispravnosti prema konstrukciji.
Kada se slučajni broj generira, često ga trebaju koristiti sudionici koji se razlikuju od onih koji su ga generirali. Tim sudionicima potrebno je poslati sve Pozdrav i prateće dokaze.
Radoznao čitatelj može pitati: budući da je konačni slučajni broj – to je H0, i p(0)G – to je javna informacija, zašto je potrebno dokazati za svaki pojedinačni Hi, zašto umjesto toga ne poslati dokaz da
dlog(p(0)G, G) = dlog(H0, H)
Problem je u tome što pomoću Schnorr Protocol-a nije moguće stvoriti takav dokaz, jer nitko ne zna vrijednost p(0), potrebnu za stvaranje dokaza, a štoviše, cijeli generator slučajnih brojeva temelji se na tome da nitko ne zna tu vrijednost. Stoga je potrebno imati sve vrijednosti Pozdrav i njihove individualne dokaze kako bi se dokazala ispravnost. H0.
Međutim, da je na točkama na eliptičnim krivuljama postojala neka operacija koja je semantički slična množenju, dokaz ispravnosti H0 bio bi trivijalan, jednostavno bismo provjerili da
H0 × G = p(0)G × H
Ako odabrana krivulja podržava , takav dokaz bi djelovao. U tom slučaju H0 nije samo ishod generatora slučajnih brojeva koji može provjeriti bilo koji sudionik koji zna G, H i p(0)G. H0 – to je također oznaka za poruku koja je korištena kao seed, potvrđujući da k i n učesnici potpisali tu poruku. Tako da, ako seed – je hash bloka u blockchain protokolu, tada H0 je to istovremeno multi-potpis na bloku, i veoma dobar slučajan broj.
Za kraj
Ovaj članak je deo serije tehničkih članaka na blogu . NEAR je blockchain protokol i platforma za razvoj decentralizovanih aplikacija sa naglaskom na jednostavnost razvoja i jednostavnost korišćenja za krajnje korisnike.
Kod protokola je otvoren, naša implementacija je napisana na Rust-u, a može se naći .
Pogledajte kako izgleda razvoj na NEAR-u i eksperimentirajte u online IDE-u .
Pratite sve vesti na ruskom jeziku u i u , a na engleskom u zvaničnom .
Vidimo se uskoro!
Izvor: habr.com
