ProHoster > Blogs > Administrācija > Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

Čau Habr!

Š’ pirmā daļa Å ajā rakstā mēs apspriedām, kāpēc varētu bÅ«t nepiecieÅ”ams Ä£enerēt nejauÅ”us skaitļus dalÄ«bniekiem, kuri neuzticas viens otram, kādas prasÄ«bas tiek izvirzÄ«tas Ŕādiem nejauÅ”o skaitļu Ä£eneratoriem, un aplÅ«kojām divas pieejas to ievieÅ”anai.

Å ajā raksta daļā mēs sÄ«kāk aplÅ«kosim citu pieeju, kas izmanto sliekŔņa parakstus.

Mazliet kriptogrāfijas

Lai saprastu, kā darbojas sliekŔņa paraksti, jums ir jāsaprot nedaudz pamata kriptogrāfija. Mēs izmantosim divus jēdzienus: skalāri vai vienkārÅ”i skaitļus, kurus apzÄ«mēsim ar mazajiem burtiem (x, y) un eliptiskās lÄ«knes punkti, kurus apzÄ«mēsim ar lielajiem burtiem.

Lai saprastu sliekŔņa parakstu pamatus, jums nav jāsaprot, kā darbojas eliptiskās lÄ«knes, izņemot dažas pamata lietas.

  1. Punktus uz eliptiskās lÄ«knes var pievienot un reizināt ar skalāru (reizināŔanu ar skalāru mēs apzÄ«mēsim kā xG, lai gan apzÄ«mējums Gx arÄ« bieži lietots literatÅ«rā). SaskaitÄ«Å”anas un reizināŔanas ar skalāru rezultāts ir eliptiskās lÄ«knes punkts.

  2. Zinot tikai būtību G un tā reizinājums ar skalāru xG nevar aprēķināt x.

Mēs izmantosim arÄ« polinoma jēdzienu p(x) grāds k-1. Jo Ä«paÅ”i mēs izmantosim Ŕādu polinomu Ä«paŔību: ja mēs zinām vērtÄ«bu p(x) jebkuram k atŔķirÄ«gs x (un mums nav vairāk informācijas par p(x)), mēs varam aprēķināt p(x) kādam citam x.

Interesanti, ka jebkuram polinomam p(x) un kādu punktu uz līknes Gzinot nozīmi p(x)G jebkuram k dažādas nozīmes x, mēs varam arī aprēķināt p(x)G jebkuram x.

Å Ä« ir pietiekami daudz informācijas, lai izpētÄ«tu, kā darbojas sliekŔņa paraksti un kā tos izmantot nejauÅ”u skaitļu Ä£enerÄ“Å”anai.

NejauÅ”o skaitļu Ä£enerators uz sliekŔņa parakstiem

Teiksim tā n dalÄ«bnieki vēlas Ä£enerēt nejauÅ”u skaitu, un mēs vēlamies, lai tajā piedalās ikviens k viņu bija pietiekami daudz, lai Ä£enerētu numuru, bet tā, lai uzbrucēji, kas kontrolē k-1 vai mazāk dalÄ«bnieku nevarēja paredzēt vai ietekmēt Ä£enerēto skaitu.

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

Pieņemsim, ka pastāv Ŕāds polinoms p(x) grāds k-1, ko zina pirmais dalÄ«bnieks p (1), otrs zina p(2), un tā tālāk (n- tas zina p(n)). Mēs arÄ« pieņemam, ka kādam iepriekÅ” noteiktam punktam G visi zina p(x)G visām vērtÄ«bām x. Mēs piezvanÄ«sim p(i) "privātā sastāvdaļa" idalÄ«bnieks (jo tikai idalÄ«bnieks viņu pazÄ«st), un p(i)G "publiskais komponents" i-tā dalÄ«bniece (jo visi dalÄ«bnieki viņu pazÄ«st). Kā jÅ«s atceraties, zināŔanas p(i)G nepietiek, lai atjaunotu p(i).

Izveidojot Ŕādu polinomu, lai tikai i-Pirmais dalÄ«bnieks un neviens cits nezināja viņa privāto komponentu - Ŕī ir vissarežģītākā un interesantākā protokola daļa, un mēs to analizēsim tālāk. Pagaidām pieņemsim, ka mums ir Ŕāds polinoms un visi dalÄ«bnieki zina savus privātos komponentus.

Kā mēs varam izmantot Ŕādu polinomu, lai Ä£enerētu nejauÅ”u skaitli? Vispirms mums ir nepiecieÅ”ama virkne, kas iepriekÅ” nav izmantota kā Ä£eneratora ievade. Blokķēdes gadÄ«jumā pēdējā bloka hash h ir labs kandidāts Ŕādai lÄ«nijai. Ä»aujiet dalÄ«bniekiem izveidot nejauÅ”u skaitli, izmantojot h kā sēklas. DalÄ«bnieki vispirms konvertē h uz punktu uz lÄ«knes, izmantojot jebkuru iepriekÅ” definētu funkciju:

H = skalārs uz punktu(h)

Pēc tam katrs dalÄ«bnieks i aprēķina un publicē Hi = p(i)H, ko viņi var darÄ«t, jo viņi zina p(i) un H. Informācijas atklāŔana Hes neļauju citiem dalÄ«bniekiem atjaunot privāto komponentu ith dalÄ«bnieks, un tāpēc vienu privāto komponentu komplektu var izmantot no bloka uz bloku. Tādējādi tālāk aprakstÄ«tais dārgais polinomu Ä£enerÄ“Å”anas algoritms ir jāizpilda tikai vienu reizi.

Kad k dalÄ«bniekiem tika veikta autopsija Hi = p(i)H, katrs var izskaitļot Hx = p(x)H visiem x pateicoties polinomu Ä«paŔībām, par kurām mēs runājām pēdējā sadaļā. Å obrÄ«d visi dalÄ«bnieki aprēķina H0 = p(0)H, un Å”is ir iegÅ«tais nejauÅ”ais skaitlis. LÅ«dzu, ņemiet vērā, ka neviens to nezina p(0), un tāpēc vienÄ«gais veids, kā aprēķināt p(0)H ā€“ tā ir interpolācija p(x)H, kas ir iespējams tikai tad, kad k vērtÄ«bas p(i)H zināms. Atverot jebkuru mazāku daudzumu p(i)H nesniedz nekādu informāciju par p(0)H.

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

IepriekÅ” minētajam Ä£eneratoram ir visas vēlamās Ä«paŔības: tikai uzbrucēji kontrolē k-1 vai mazāk dalÄ«bniekiem nav informācijas vai ietekmes uz secinājumu, savukārt jebkura k dalÄ«bnieki var aprēķināt iegÅ«to skaitli un jebkuru tā apakÅ”kopu k dalÄ«bnieki vienmēr sasniegs vienu un to paÅ”u rezultātu ar vienu un to paÅ”u sēklu.

Ir viena problēma, no kuras mēs iepriekÅ” rÅ«pÄ«gi izvairÄ«jāmies. Lai interpolācija darbotos, ir svarÄ«gi, lai vērtÄ«ba Hi, kuru publicēja katrs dalÄ«bnieks i tas tieŔām bija tas pats p(i)H. Tā kā neviens, izņemot i-th dalÄ«bnieks nezina p(i), neviens, izņemot i-dalÄ«bnieks to nevar pārbaudÄ«t Hi faktiski aprēķināts pareizi un bez kriptogrāfiska pareizÄ«bas pierādÄ«juma Hes uzbrucējs var publicēt jebkuru vērtÄ«bu kā Sveiki, un patvaļīgi ietekmēt nejauÅ”o skaitļu Ä£eneratora izvadi:

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļaDažādas H_1 vērtÄ«bas, ko nosÅ«tÄ«jis pirmais dalÄ«bnieks, rada atŔķirÄ«gu rezultātu H_0

Ir vismaz divi veidi, kā pierādÄ«t pareizÄ«bu Hi, mēs tos apsvērsim pēc polinoma Ä£enerÄ“Å”anas analÄ«zes.

Polinomu paaudze

Pēdējā sadaļā mēs pieņēmām, ka mums ir Ŕāds polinoms p(x) grāds k-1 ka dalÄ«bnieks i zina p(i), un nevienam citam nav nekādas informācijas par Å”o vērtÄ«bu. Nākamajā sadaļā mums tas bÅ«s vajadzÄ«gs arÄ« kādam iepriekÅ” noteiktam punktam G visi zināja p(x)G visiem x.

Å ajā sadaļā mēs pieņemsim, ka katram dalÄ«bniekam lokāli ir kāda privātā atslēga xi, tā, lai visi zinātu atbilstoÅ”o publisko atslēgu Xi.

Viens no iespējamiem polinoma Ä£enerÄ“Å”anas protokoliem ir Ŕāds:

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

  1. Katrs dalÄ«bnieks i lokāli izveido patvaļīgu polinomu pi(x) pakāpe k-1. Pēc tam viņi nosÅ«ta katru dalÄ«bnieku j vērtÄ«ba pi(j), Å”ifrēts ar publisko atslēgu Xj. Tādējādi tikai i-th Šø j-th dalÄ«bnieks zina pi(j). DalÄ«bnieks i arÄ« publiski paziņo pi(j)G visiem j no 1 lÄ«dz k iekļaujoÅ”s.

  2. Visi dalÄ«bnieki izmanto zināmu vienprātÄ«bu, lai izvēlētos k dalÄ«bnieki, kuru polinomi tiks izmantoti. Tā kā daži dalÄ«bnieki var bÅ«t bezsaistē, mēs nevaram gaidÄ«t, lÄ«dz visi n dalÄ«bnieki publicēs polinomus. Å Ä«s darbÄ«bas rezultāts ir komplekts Z kas sastāv vismaz no k 1. solÄ« izveidotie polinomi.

  3. DalÄ«bnieki pārliecinās, ka vērtÄ«bas viņi zina pi(j) atbilst publiski paziņotajam pi(j)G. Pēc Ŕīs darbÄ«bas Z tikai polinomi, par kuriem nosÅ«tÄ«ti privāti pi(j) atbilst publiski paziņotajam pi(j)G.

  4. Katrs dalÄ«bnieks j aprēķina savu privāto komponentu p(j) kā summa pi(j) visiem i Š² Z. Katrs dalÄ«bnieks arÄ« aprēķina visas vērtÄ«bas p(x)G kā summa pi(x)G visiem i Š² Z.

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

LÅ«dzu, ņemiet vērā, ka p(x) ā€“ tas tieŔām ir polinoms k-1, jo tā ir indivÄ«da summa pi(x), no kuriem katrs ir pakāpes polinoms k-1. Pēc tam ņemiet vērā, ka, kamēr katrs dalÄ«bnieks j zina p(j), viņiem nav informācijas par p(x) par x ā‰  j. PatieŔām, lai aprēķinātu Å”o vērtÄ«bu, viņiem ir jāzina viss pi(x), un tik ilgi, kamēr dalÄ«bnieks j nezina vismaz vienu no atlasÄ«tajiem polinomiem, viņiem nav pietiekamas informācijas par p(x).

Å is ir viss polinoma Ä£enerÄ“Å”anas process, kas bija nepiecieÅ”ams pēdējā sadaļā. IepriekÅ” minētā 1., 2. un 4. darbÄ«ba ir diezgan acÄ«mredzama. Bet 3. solis nav tik triviāls.

Konkrēti, mums ir jāspēj pierādÄ«t, ka tas ir Å”ifrēts pi(j) tieŔām atbilst publicētajiem pi(j)G. Ja nevaram pierādÄ«t, uzbrucējs i tā vietā var nosÅ«tÄ«t atkritumus pi(j) dalÄ«bniekam j, un dalÄ«bnieks j nevarēs iegÅ«t Ä«sto nozÄ«mi pi(j), un nevarēs aprēķināt savu privāto komponentu.

Ir kriptogrāfijas protokols, kas ļauj izveidot papildu ziņojumu pierādÄ«jumsi(j), tā, ka jebkurÅ” dalÄ«bnieks, kam ir kāda vērtÄ«ba e, kā arÄ« pierādÄ«jums(j) Šø pi(j)G, var to lokāli pārbaudÄ«t e - tas tieŔām ir pi(j), Å”ifrēts ar dalÄ«bnieka atslēgu j. Diemžēl Ŕādu pierādÄ«jumu apjoms ir neticami liels, un, ņemot vērā to, ka tas ir jāpublicē O(nk) Šādus pierādÄ«jumus nevar izmantot Å”im nolÅ«kam.

Tā vietā, lai to pierādÄ«tu pi(j) atbilst pi(j)G polinomu Ä£enerÄ“Å”anas protokolā varam atvēlēt ļoti ilgu laika periodu, kura laikā visi dalÄ«bnieki pārbauda saņemto Å”ifrēto pi(j), un ja atÅ”ifrētais ziņojums neatbilst sabiedrÄ«bai pi(j)G, viņi publicē kriptogrāfisku pierādÄ«jumu tam, ka saņemtais Å”ifrētais ziņojums ir nepareizs. Pierādiet, ka ziņa nē atbilst pi(G) daudz vieglāk, nekā pierādÄ«t, ka tas atbilst. Jāņem vērā, ka tas paredz, ka katram dalÄ«bniekam vismaz vienu reizi ir jāparādās tieÅ”saistē laikā, kas atvēlēts Ŕādu pierādÄ«jumu izveidei, un paļaujas uz pieņēmumu, ka, publicējot Ŕādu pierādÄ«jumu, tas sasniegs visus pārējos dalÄ«bniekus tajā paŔā atvēlētajā laikā.

Vai ir iespējams Ä£enerēt nejauÅ”us skaitļus, ja mēs viens otram neuzticamies? 2. daļa

Ja dalÄ«bnieks Å”ajā laika periodā nav ieradies tieÅ”saistē un viņam ir bijis vismaz viens nepareizs komponents, tad konkrētais dalÄ«bnieks nevarēs piedalÄ«ties turpmākajā numuru Ä£enerÄ“Å”anā. Tomēr protokols joprojām darbosies, ja tāds bÅ«s k dalÄ«bnieki, kuri vai nu tikko saņēma pareizās sastāvdaļas, vai arÄ« spēja atstāt pierādÄ«jumus par nepareizÄ«bu noteiktajā laikā.

H_i pareizības pierādījumi

Pēdējā daļa, kas vēl jāapspriež, ir tas, kā pierādÄ«t publicētā pareizÄ«bu Hes, proti, tas Hi = p(i)H, bez atvērÅ”anas p(i).

Atcerēsimies, ka vērtÄ«bas H, G, p(i)G publiski un visiem zināmi. SaņemÅ”anas darbÄ«ba p(i) zinot p(i)G Šø G sauc par diskrēto logaritmu vai dlog, un mēs vēlamies pierādÄ«t, ka:

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

bez izpauÅ”anas p(i). Piemēram, pastāv konstrukcijas Ŕādiem pierādÄ«jumiem Å nores protokols.

Ar Ŕo dizainu katrs dalībnieks kopā ar Hi nosūta pareizības apliecinājumu atbilstoŔi projektam.

Kad nejauÅ”s skaitlis ir Ä£enerēts, tas bieži ir jāizmanto citiem dalÄ«bniekiem, nevis tiem, kas to Ä£enerēja. Šādiem dalÄ«bniekiem kopā ar numuru jānosÅ«ta visi Hi un saistÄ«tie pierādÄ«jumi.

ZiņkārÄ«gs lasÄ«tājs var jautāt: tā kā galÄ«gais nejauÅ”ais skaitlis ir H0 un p(0)G ā€“ Tā ir publiska informācija, kāpēc mums vajag pierādÄ«jumus katram atseviŔķi Hes, kāpēc gan tā vietā nenosÅ«tÄ«t pierādÄ«jumus

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

Problēma ir tāda, ka Ŕādu pierādÄ«jumu nevar izveidot, izmantojot Schnorr protokolu, jo neviens nezina vērtÄ«bu p (0), kas nepiecieÅ”ams, lai izveidotu pierādÄ«jumu, un vēl jo vairāk, viss nejauÅ”o skaitļu Ä£enerators ir balstÄ«ts uz faktu, ka neviens nezina Å”o vērtÄ«bu. Tāpēc ir vajadzÄ«gas visas vērtÄ«bas Hi un viņu individuālie pierādÄ«jumi, lai pierādÄ«tu pareizÄ«bu H0.

Tomēr, ja ar eliptisku lÄ«kņu punktiem tika veikta darbÄ«ba, kas semantiski ir lÄ«dzÄ«ga reizināŔanai, pareizÄ«bas pierādÄ«jums H0 tas bÅ«tu triviāli, mēs vienkārÅ”i par to pārliecinātos

H0 Ɨ G = p(0)G Ɨ H

Ja izvēlētā lÄ«kne atbalsta eliptiskās lÄ«knes pāri, Å”is pierādÄ«jums darbojas. Å ajā gadÄ«jumā H0 ir ne tikai nejauÅ”u skaitļu Ä£eneratora izvade, ko var pārbaudÄ«t jebkurÅ” zinoÅ”s dalÄ«bnieks G, H Šø p(0)G. H0 ir arÄ« paraksts uz ziņojuma, kas tika izmantots kā sēkla, kas to apstiprina k Šø n dalÄ«bnieki parakstÄ«ja Å”o ziņojumu. Tādējādi, ja sēklas - ir bloka jaucējvērtÄ«ba blokķēdes protokolā, tad H0 ir gan daudzparaksts uz bloka, gan ļoti labs nejauÅ”s skaitlis.

Noslēgumā

Å is raksts ir daļa no tehnisko emuāru sērijas NEAR. NEAR ir blokķēdes protokols un platforma decentralizētu lietojumprogrammu izstrādei ar uzsvaru uz izstrādes un lietoÅ”anas ērtumu galalietotājiem.

Protokola kods ir atvērts, mÅ«su realizācija ir rakstÄ«ta Rustā, to var atrast Å”eit.

JÅ«s varat redzēt, kā izskatās NEAR izstrāde, un eksperimentēt tieÅ”saistes IDE Å”eit.

Visiem jaunumiem krievu valodā var sekot līdzi plkst telegrammu grupa un grupa vietnē VKontakte, un angļu valodā oficiālajā twitter.

Uz drīzu redzēŔanos!

Avots: www.habr.com

Pievieno komentāru