Je li moguće generirati nasumične brojeve ako ne vjerujemo jedni drugima? Dio 2

Hej Habr!

В prvi deo U ovom članku smo raspravljali zašto bi moglo biti potrebno generirati slučajne brojeve za učesnike koji ne vjeruju jedni drugima, koji zahtjevi se postavljaju za takve generatore slučajnih brojeva i razmotrili dva pristupa njihovoj implementaciji.

U ovom dijelu članka detaljnije ćemo pogledati još jedan pristup koji koristi potpise praga.

Malo kriptografije

Da biste razumjeli kako funkcionišu potpisi praga, morate razumjeti malo osnovne kriptografije. Koristit ćemo dva koncepta: skalare ili jednostavno brojeve, koje ćemo označavati malim slovima (x, y) i tačke na eliptičnoj krivoj, koje ćemo označiti velikim slovima.

Da biste razumjeli osnove graničnih potpisa, ne morate razumjeti kako funkcionišu eliptične krive, osim nekoliko osnovnih stvari:

1. Tačke na eliptičnoj krivulji mogu se zbrajati i množiti skalarom (množenje skalarom ćemo označiti kao xG, iako je notacija Gx takođe se često koristi u literaturi). Rezultat sabiranja i množenja skalarom je tačka na eliptičnoj krivulji.

2. Znajući samo poentu G i njegov proizvod sa skalarom xG ne može se izračunati x.

Koristićemo i koncept polinoma p(x) stupanj k-1. Posebno ćemo koristiti sljedeće svojstvo polinoma: ako znamo vrijednost p(x) za bilo koji k drugačiji x (i nemamo više informacija o p(x)), možemo izračunati p(x) za bilo koga drugog x.

Zanimljivo je da za bilo koji polinom p(x) i neka tačka na krivulji Gznajući značenje p(x)G za bilo koji k različita značenja x, možemo i izračunati p(x)G za bilo koji x.

Ovo je dovoljno informacija da se kopa u detalje o tome kako funkcionišu granični potpisi i kako ih koristiti za generisanje slučajnih brojeva.

Generator slučajnih brojeva na graničnim potpisima

Recimo to n učesnici žele da generišu nasumični broj, a mi želimo da bilo ko učestvuje k bilo ih je dovoljno da se generiše broj, ali tako da napadači koji kontrolišu k-1 ili manje učesnika nije moglo predvideti ili uticati na generisani broj.

Pretpostavimo da postoji takav polinom p(x) stupanj k-1 šta prvi učesnik zna p (1), drugi zna p(2), i tako dalje (n-th zna p(n)). Pretpostavljamo i to za neku unaprijed određenu tačku G svi znaju p(x)G za sve vrednosti x. Nazvat ćemo p(i) “privatna komponenta” iučesnika (jer samo ith učesnik je poznaje), i p(i)G "javna komponenta" i-ti učesnik (jer je svi učesnici poznaju). Kao što se sećate, znanje p(i)G nije dovoljno za obnavljanje p(i).

Kreiranje takvog polinoma tako da samo i-Prvi učesnik i niko drugi nije znao njegovu privatnu komponentu - ovo je najsloženiji i najzanimljiviji dio protokola, a mi ćemo ga analizirati u nastavku. Za sada, pretpostavimo da imamo takav polinom i da svi učesnici znaju svoje privatne komponente.

Kako možemo koristiti takav polinom za generiranje slučajnog broja? Za početak nam je potreban neki niz koji ranije nije korišten kao ulaz u generator. U slučaju blockchaina, heš posljednjeg bloka h je dobar kandidat za takvu liniju. Neka učesnici žele da kreiraju nasumični broj koristeći h kao seme. Učesnici se prvo pretvaraju h do tačke na krivulji koristeći bilo koju unaprijed definiranu funkciju:

H = scalarToPoint(h)

Zatim svaki učesnik i izračunava i objavljuje Hi = p(i)H, šta mogu da urade jer znaju p(i) i H. Disclosure Hne dozvoljavam drugim učesnicima da vrate privatnu komponentu iučesnika, pa se stoga jedan skup privatnih komponenti može koristiti od bloka do bloka. Stoga, skupi algoritam za generiranje polinoma opisan u nastavku treba izvršiti samo jednom.

Kada k učesnici su obducirani Hi = p(i)H, svako može da izračuna Hx = p(x)H za sve x zahvaljujući svojstvu polinoma o kojem smo raspravljali u prošlom dijelu. U ovom trenutku svi učesnici računaju H0 = p(0)H, a ovo je rezultirajući slučajni broj. Imajte na umu da niko ne zna p(0), i stoga jedini način izračunavanja p(0)H – ovo je interpolacija p(x)H, što je moguće samo kada k vrijednosti p(i)H poznato. Otvaranje bilo koje manje količine p(i)H ne daje nikakve informacije o p(0)H.

Generator iznad ima sva svojstva koja želimo: samo napadači kontroliraju k-1 učesnik ili manje nema informacija ili uticaja na zaključak, dok bilo koji k učesnici mogu izračunati rezultirajući broj i bilo koji podskup od k učesnici će uvijek doći do istog rezultata za isto sjeme.

Postoji jedan problem koji smo gore pažljivo izbjegli. Da bi interpolacija funkcionirala, važno je da vrijednost Hi koji je objavio svaki učesnik i zaista je bilo isto p(i)H. Pošto niko osim i-ti učesnik ne zna p(i), niko osim i-učesnik to ne može potvrditi Hi stvarno izračunato ispravno, i bez ikakvog kriptografskog dokaza ispravnosti Hi napadač može objaviti bilo koju vrijednost kao Hi, i proizvoljno utiču na izlaz generatora slučajnih brojeva:

Različite vrijednosti H_1 koje šalje prvi učesnik dovode do različitih rezultirajućih H_0

Postoje najmanje dva načina da se dokaže tačnost Hi, razmotrićemo ih nakon što analiziramo generisanje polinoma.

Generacija polinoma

U prošlom dijelu pretpostavili smo da imamo takav polinom p(x) stupanj k-1 da je učesnik i zna p(i), i niko drugi nema nikakve informacije o ovoj vrijednosti. U sljedećem odjeljku to će nam također trebati za neku unaprijed određenu tačku G svi su znali p(x)G za sve x.

U ovom dijelu ćemo pretpostaviti da svaki sudionik lokalno ima neki privatni ključ xi, tako da svi znaju odgovarajući javni ključ Xi.

Jedan mogući protokol generiranja polinoma je sljedeći:

1. Svaki učesnik i lokalno stvara proizvoljan polinom pi(x) stepen k-1. Zatim šalju svakog učesnika j značenje pi(j), šifriran javnim ključem Xj. Samo tako i-th и j-th učesnik zna pi(j). Učesnik i takođe javno saopštava pi(j)G za sve j iz 1 do k inclusive.

2. Svi učesnici koriste određeni konsenzus da biraju k učesnici čiji će se polinomi koristiti. Budući da su neki učesnici možda van mreže, ne možemo čekati da svi n učesnici će objaviti polinome. Rezultat ovog koraka je skup Z koji se sastoji od najmanje k polinomi kreirani u koraku (1).

3. Učesnici se uvjeravaju da vrijednosti koje poznaju pi(j) odgovara javno objavljenom pi(j)G. Nakon ovog koraka Z samo polinomi za koje se privatno prenose pi(j) odgovara javno objavljenom pi(j)G.

4. Svaki učesnik j izračunava svoju privatnu komponentu p(j) kao suma pi(j) za sve i в Z. Svaki učesnik također izračunava sve vrijednosti p(x)G kao suma pi(x)G za sve i в Z.

Zapiši to p(x) – to je zaista polinom k-1, jer je to zbir pojedinca pi(x), od kojih je svaki polinom stepena k-1. Zatim, imajte na umu da dok svaki učesnik j zna p(j), nemaju informacije o tome p(x) do x ≠ j. Zaista, da bi izračunali ovu vrijednost, oni moraju znati sve pi(x), i sve dok učesnik j ne poznaje barem jedan od odabranih polinoma, o njima nema dovoljno informacija p(x).

Ovo je cijeli proces generiranja polinoma koji je bio potreban u prošlom dijelu. Koraci 1, 2 i 4 iznad imaju prilično očiglednu implementaciju. Ali korak 3 nije tako trivijalan.

Konkretno, moramo biti u mogućnosti to dokazati šifrirano pi(j) zaista odgovaraju objavljenim pi(j)G. Ako to ne možemo dokazati, napadač i umjesto toga može poslati smeće pi(j) učesniku j, i učesnik j neće moći da shvati pravo značenje pi(j), i neće moći izračunati svoju privatnu komponentu.

Postoji kriptografski protokol koji vam omogućava da kreirate dodatnu poruku Dokazi(j), tako da svaki učesnik ima neku vrijednost e, a takže dokaz(j) и pi(j)G, to može lokalno provjeriti e - stvarno je pi(j), šifriran ključem učesnika j. Nažalost, veličina takvih dokaza je nevjerovatno velika, a s obzirom na to da ih je potrebno objaviti O(nk) Takvi dokazi se ne mogu koristiti u tu svrhu.

Umesto da to dokažem pi(j) odgovara pi(j)G možemo izdvojiti veoma dug vremenski period u protokolu generisanja polinoma, tokom kojeg svi učesnici provjeravaju primljene šifrirane pi(j), i ako dešifrovana poruka ne odgovara javnosti pi(j)G, objavljuju kriptografski dokaz da je šifrovana poruka koju su primili netačna. Dokažite da je poruka ne odgovara pi(G) mnogo lakše nego dokazati da se poklapa. Treba napomenuti da ovo zahtijeva da se svaki učesnik pojavi na mreži barem jednom u vremenu predviđenom za kreiranje takvog dokaza, i oslanja se na pretpostavku da će, ako objavi takav dokaz, on stići do svih ostalih sudionika u istom zadanom vremenu.

Ako se učesnik nije pojavio na mreži tokom ovog vremenskog perioda, a imao je barem jednu pogrešnu komponentu, tada taj određeni učesnik neće moći da učestvuje u daljem generisanju brojeva. Protokol će, međutim, i dalje funkcionirati ako postoji barem k učesnike koji su ili samo primili ispravne komponente ili su uspjeli da ostave dokaz o netačnosti u predviđenom vremenu.

Dokazi o ispravnosti H_i

Posljednji dio o kojem ostaje da se raspravlja je kako dokazati ispravnost objavljenog Hja, naime to Hi = p(i)H, bez otvaranja p(i).

Podsjetimo da su vrijednosti H, G, p(i)G javno i svima poznato. Operacija prijema p(i) znajući p(i)G и G naziva se diskretni logaritam, ili dlog, i želimo da dokažemo da:

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

bez otkrivanja p(i). Na primjer, postoje konstrukcije za takve dokaze Schnorr Protocol.

Sa ovim dizajnom, svaki učesnik, zajedno sa Hi šalje dokaz o ispravnosti prema projektu.

Jednom kada se generira nasumični broj, često ga moraju koristiti sudionici koji nisu oni koji su ga generirali. Takvi učesnici, zajedno sa brojem, moraju poslati sve Hi i povezani dokazi.

Radoznali čitalac može se zapitati: budući da je konačni slučajni broj H0, i p(0)G – Ovo je javna informacija, zašto nam treba dokaz za svakog pojedinca Hja, zašto ne poslati dokaz da umjesto toga

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

Problem je u tome što se takav dokaz ne može stvoriti korištenjem Schnorr protokola jer niko ne zna vrijednost p (0), neophodan za kreiranje dokaza, i štaviše, ceo generator slučajnih brojeva je zasnovan na činjenici da niko ne zna ovu vrednost. Stoga je neophodno imati sve vrijednosti Hi i njihove pojedinačne dokaze koji dokazuju tačnost H0.

Međutim, ako je postojala neka operacija na tačkama na eliptičnim krivuljama koja je semantički slična množenju, dokaz ispravnosti H0 bilo bi trivijalno, jednostavno bismo se u to uverili

H0 × G = p(0)G × H

Ako odabrana kriva podržava uparivanja eliptičkih krivulja, ovaj dokaz radi. U ovom slučaju H0 nije samo izlaz generatora slučajnih brojeva, što može provjeriti svaki učesnik koji zna G, H и p(0)G. H0 je također potpis na poruci koja je korištena kao seme, što potvrđuje to k и n učesnici su potpisali ovu poruku. Dakle, ako sjeme - je onda heš bloka u blockchain protokolu H0 je i višestruki potpis na bloku i vrlo dobar slučajni broj.

U zaključku

Ovaj članak je dio serije tehničkih blogova U BLIZINI. NEAR je blockchain protokol i platforma za razvoj decentraliziranih aplikacija s naglaskom na jednostavnost razvoja i jednostavnost korištenja za krajnje korisnike.

Kod protokola je otvoren, naša implementacija je napisana u Rustu, može se pronaći ovdje.

Možete vidjeti kako izgleda razvoj za NEAR i eksperimentirati u online IDE-u ovdje.

Sve vijesti na ruskom možete pratiti na telegram grupa i unutra grupa na VKontakteu, i na engleskom u službenom twitter.

Do skoryh vstreč!

izvor: www.habr.com