Je li moguće generirati slučajne brojeve ako ne vjerujemo jedni drugima? 2. dio

Hej Habr!

В prvi dio U ovom smo članku raspravljali o tome zašto bi moglo biti potrebno generirati nasumične brojeve za sudionike koji ne vjeruju jedni drugima, koji su zahtjevi postavljeni za takve generatore nasumičnih brojeva i razmotrili dva pristupa njihovoj implementaciji.

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

Malo kriptografije

Da biste razumjeli kako funkcioniraju potpisi praga, morate razumjeti malo osnove kriptografije. Koristit ćemo dva pojma: skalare, ili jednostavno brojeve, koje ćemo označavati malim slovima (x, y) i točke na eliptičkoj krivulji koje ćemo označiti velikim slovima.

Da biste razumjeli osnove potpisa praga, ne morate razumjeti kako eliptičke krivulje funkcioniraju, osim nekoliko osnovnih stvari:

1. Točke na eliptičkoj krivulji mogu se zbrajati i množiti skalarom (množenje skalarom ćemo označiti kao xG, iako notacija Gx također često korišten u literaturi). Rezultat zbrajanja i množenja skalarom je točka na eliptičkoj krivulji.

2. Znajući samo bit G a njegov umnožak sa skalarom xG ne može se izračunati x.

Također ćemo koristiti pojam polinoma p (x) stupnjeva 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 svaki polinom p (x) i neka toč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 istražimo pojedinosti o tome kako funkcioniraju potpisi pragova i kako ih koristiti za generiranje nasumičnih brojeva.

Generator slučajnih brojeva na potpisima praga

Recimo to n sudionici žele generirati nasumični broj, a mi želimo da bilo tko sudjeluje k bilo ih je dovoljno za generiranje broja, ali tako da napadači koji kontroliraju k-1 ili manje sudionika nije moglo predvidjeti niti utjecati na generirani broj.

Pretpostavimo da postoji takav polinom p (x) stupnjeva k-1 što prvi sudionik zna p (1), drugi zna p(2), i tako dalje (n-th zna p(n)). Također pretpostavljamo da za neku unaprijed određenu točku G svi znaju p(x)G za sve vrijednosti x. Nazvat ćemo p(i) “privatna komponenta” isudionik (jer samo iti je sudionik poznaje), i svinja “javna komponenta” i-ta sudionica (jer je svi sudionici poznaju). Kao što se sjećate, znanje svinja nedovoljno za obnovu p(i).

Stvaranje takvog polinoma tako da samo i-Prvi sudionik i nitko 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 sudionici znaju svoje privatne komponente.

Kako možemo koristiti takav polinom za generiranje slučajnog broja? Za početak, trebamo neki string koji prethodno nije korišten kao ulaz u generator. U slučaju blockchaina, hash posljednjeg bloka h je dobar kandidat za takvu liniju. Neka sudionici žele stvoriti slučajni broj pomoću h poput sjemena. Sudionici se prvi pretvaraju h do točke na krivulji koristeći bilo koju unaprijed definiranu funkciju:

H = skalarToPoint(h)

Zatim svaki sudionik i izračunava i objavljuje Hi = p(i)H, što mogu jer znaju p(i) i H. otkriće Hne dopuštam drugim sudionicima da obnove privatnu komponentu isudionika, pa se stoga jedan skup privatnih komponenti može koristiti od bloka do bloka. Stoga se skupi algoritam za generiranje polinoma opisan u nastavku treba izvršiti samo jednom.

Kada k sudionici su obducirani Hi = p(i)H, svatko može izračunati Hx = p(x)H za sve x zahvaljujući svojstvu polinoma o kojem smo govorili u prošlom odjeljku. U ovom trenutku svi sudionici izračunavaju H0 = p(0)H, a ovo je rezultirajući slučajni broj. Imajte na umu da nitko ne zna p(0), i stoga jedini način izračunavanja p(0)H – ovo je interpolacija p(x)H, što je jedino moguće kada k vrijednosti p(i)H znan. Otvaranje bilo koje manje količine p(i)H ne daje nikakve informacije o p(0)H.

Gornji generator ima sva svojstva koja želimo: napadači samo kontroliraju k-1 sudionika ili manje nema informacija niti utjecaja na zaključak, dok bilo koji k sudionici mogu izračunati rezultirajući broj i bilo koji podskup k sudionici će uvijek doći do istog rezultata za isto sjeme.

Postoji jedan problem koji smo gore pažljivo izbjegli. Da bi interpolacija radila, važno je da vrijednost Hi koji je objavio svaki sudionik i stvarno je bilo isto p(i)H. Budući da nitko osim i-ti sudionik ne zna p(i), nitko osim i-sudionik to ne može potvrditi Hi zapravo točno izračunati i bez ikakvog kriptografskog dokaza ispravnosti Hja napadač može objaviti bilo koju vrijednost kao Bok, i proizvoljno utjecati na izlaz generatora slučajnih brojeva:

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

Postoje najmanje dva načina da se dokaže ispravnost Hi, razmotrit ćemo ih nakon što analiziramo generiranje polinoma.

Generacija polinoma

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

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

Jedan mogući protokol za generiranje polinoma je sljedeći:

1. Svaki sudionik i lokalno stvara proizvoljni polinom pi(x) stupanj k-1. Zatim šalju svakog sudionika j vrijednost pi(j), šifriran javnim ključem Xj. Samo tako i-th и j-th sudionik znati pi J). sudionik i također javno objavljuje pi(j)G za sve j iz 1 na k inclusive.

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

3. Sudionici se uvjeravaju u vrijednosti koje poznaju pi(j) odgovaraju javno objavljenim pi(j)G. Nakon ovog koraka u Z samo polinomi za koje se privatno prenosi pi(j) odgovaraju javno objavljenim pi(j)G.

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

Imajte na umu da p(x) – to je stvarno polinom k-1, jer je zbroj individualnog pi(x), od kojih je svaki polinom stupnja k-1. Zatim, imajte na umu da dok svaki sudionik j zna p(j), nemaju informacija o p (x) za x ≠ j. Doista, da bi izračunali ovu vrijednost, moraju znati sve pi(x), a sve dok sudionik j ne poznaje barem jedan od odabranih polinoma, o kojem nemaju dovoljno informacija p(x).

Ovo je cijeli proces generiranja polinoma koji je bio potreban u prošlom odjeljku. Gore navedeni koraci 1, 2 i 4 imaju prilično očitu implementaciju. Ali korak 3 nije tako trivijalan.

Točnije, moramo moći dokazati da je šifrirano pi(j) doista odgovaraju objavljenima pi(j)G. Ako to ne možemo dokazati, napadač i umjesto toga može poslati smeće pi(j) sudioniku j, i sudionik j neće moći dobiti pravu vrijednost pi(j), i neće moći izračunati njegovu privatnu komponentu.

Postoji kriptografski protokol koji vam omogućuje stvaranje dodatne poruke dokazi(j), tako da bilo koji sudionik, ima neku vrijednost e, kao i proofi(j) и pi(j)G, može to lokalno potvrditi e - stvarno je pi(j), šifriran ključem sudionika j. Nažalost, veličina takvih dokaza je nevjerojatno velika, a s obzirom na to da ih je potrebno objaviti O(nk) Takvi se dokazi ne mogu koristiti u tu svrhu.

Umjesto da to dokaže pi(j) odgovara pi(j)G možemo dodijeliti vrlo dugo vremensko razdoblje u protokolu generiranja polinoma, tijekom kojeg svi sudionici provjeravaju primljene šifrirane pi(j), a ako dekriptirana poruka ne odgovara javnosti pi(j)G, objavljuju kriptografski dokaz da je šifrirana poruka koju su primili netočna. Dokažite da poruka ne odgovara svinja) puno lakše nego dokazati da se podudara. Treba napomenuti da to zahtijeva da se svaki sudionik pojavi na mreži barem jednom tijekom vremena dodijeljenog za stvaranje takvog dokaza, a oslanja se na pretpostavku da će, ako objavi takav dokaz, on doći do svih ostalih sudionika u istom dodijeljenom vremenu.

Ako se sudionik u tom vremenskom razdoblju nije pojavio online, a imao je barem jednu netočnu komponentu, tada taj određeni sudionik neće moći sudjelovati u daljnjem generiranju broja. Protokol će, međutim, i dalje funkcionirati ako postoji barem k sudionici koji su ili samo primili ispravne komponente ili su uspjeli ostaviti dokaz o netočnosti unutar dodijeljenog vremena.

Dokazi ispravnosti H_i

Posljednji dio koji ostaje za raspravu je kako dokazati ispravnost objavljenog Hja, naime to Hi = p(i)H, bez otvaranja p(i).

Prisjetimo se da vrijednosti H, G, p(i)G javno i svima poznato. Operacija primanja p(i) znajući svinja и G naziva se diskretni logaritam, ili dlog, i to želimo dokazati:

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

bez razotkrivanja p(i). Konstrukcije za takve dokaze postoje, na primjer Schnorrov protokol.

S ovim dizajnom, svaki sudionik, zajedno sa Hi šalje dokaz o ispravnosti prema projektu.

Nakon što se generira nasumični broj, često ga moraju koristiti sudionici koji nisu oni koji su ga generirali. Takvi sudionici, uz broj, moraju poslati sve Hi i povezani dokazi.

Znatiželjni čitatelj može se upitati: budući da je konačni slučajni broj H0, i p(0)G – Ovo je javna informacija, zašto nam trebaju dokazi 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 nitko ne zna vrijednost p (0), potrebno za izradu dokaza, i štoviše, cijeli generator slučajnih brojeva temelji se na činjenici da nitko ne zna ovu vrijednost. Stoga je potrebno imati sve vrijednosti Hi i njihove pojedinačne dokaze koji dokazuju ispravnost H0.

Međutim, ako postoji neka operacija na točkama na eliptičnim krivuljama koja je semantički slična množenju, dokaz točnosti H0 bilo trivijalno, jednostavno bismo se u to uvjerili

H0 × G = p(0)G × H

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

U zaključku

Ovaj je članak dio tehničke serije blogova NEAR. 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 mrežnom IDE-u здесь.

Sve vijesti na ruskom možete pratiti na brzojavna grupa i grupa na VKontakteu, a na engleskom u službenom cvrkut.

Vidimo se uskoro!

Izvor: www.habr.com