Ħej Habr!
В F'dan l-artikolu, iddiskutejna għaliex jista 'jkun meħtieġ li jiġu ġġenerati numri każwali għal parteċipanti li ma jafdawx lil xulxin, liema rekwiżiti huma mressqa għal ġeneraturi ta' numri każwali bħal dawn, u kkunsidrat żewġ approċċi għall-implimentazzjoni tagħhom.
F'din il-parti tal-artikolu, se nagħtu ħarsa aktar mill-qrib lejn approċċ ieħor li juża firem limitu.
Daqsxejn kriptografija
Sabiex tifhem kif jaħdmu l-firem tal-limitu, trid tifhem ftit kriptografija bażika. Se nużaw żewġ kunċetti: skalar, jew sempliċiment numri, li se nindikaw b'ittri żgħar (x, y) u punti fuq il-kurva ellittika, li aħna se nindikaw b'ittri kbar.
Biex tifhem il-baŜi tal-firem tal-limitu, m'għandekx bżonn tifhem kif jaħdmu l-kurvi ellittiċi, minbarra ftit affarijiet bażiċi:
-
Il-punti fuq kurva ellittika jistgħu jiġu miżjuda u mmultiplikati bi skalar (se nindikaw multiplikazzjoni bi skalar bħala xG, għalkemm in-notazzjoni Gx użata ħafna drabi wkoll fil-letteratura). Ir-riżultat taż-żieda u l-multiplikazzjoni bi skalar huwa punt fuq kurva ellittika.
-
Jafu biss il-punt G u l-prodott tiegħu bi skalar xG ma jistax jiġi kkalkulat x.
Aħna se nużaw ukoll il-kunċett ta 'polinomjali p(x) gradi k-1. B'mod partikolari, se nużaw il-proprjetà li ġejja tal-polinomji: jekk nafu l-valur p(x) għal kwalunkwe k differenti x (u m'għandniex aktar informazzjoni dwar p(x)), nistgħu nikkalkulaw p(x) għal ħaddieħor x.
Interessanti, għal kull polinomjali p(x) u xi punt fuq il-kurva Gjafu t-tifsira p(x)G għal kwalunkwe k tifsiriet differenti x, nistgħu wkoll nikkalkulaw p(x)G għal kwalunkwe x.
Din hija informazzjoni biżżejjed biex tħaffer fid-dettalji ta’ kif jaħdmu l-firem tal-limitu u kif tużahom biex tiġġenera numri każwali.
Ġeneratur ta' numri każwali fuq firem ta' limitu
Ejja ngħidu li n il-parteċipanti jridu jiġġeneraw numru każwali, u rridu li xi ħadd jipparteċipa k kien hemm biżżejjed minnhom biex jiġġeneraw numru, iżda sabiex l-attakkanti li jikkontrollaw k-1 jew inqas parteċipant ma setgħux ibassru jew jinfluwenzaw in-numru ġġenerat.
Ejja ngħidu li hemm tali polinomjali p(x) gradi k-1 dak li jaf l-ewwel parteċipant p (1), it-tieni wieħed jaf p(2), u l-bqija (n-th jaf p(n)). Nassumu wkoll li għal xi punt predeterminat G kulħadd jaf p(x)G għall-valuri kollha x. Aħna se nsejħu p(i) "komponent privat" il-parteċipant (għax biss iit-th parteċipant jafha), u p(i)G "komponent pubbliku" i-th parteċipant (għax il-parteċipanti kollha jafuha). Kif tiftakar, għarfien p(i)G mhux biżżejjed biex tirrestawra p(i).
Ħolqien ta 'tali polinomju sabiex biss i-L-ewwel parteċipant u ħaddieħor ma kien jaf il-komponent privat tiegħu - din hija l-aktar parti kumplessa u interessanti tal-protokoll, u aħna se tanalizzaha hawn taħt. Għalissa, ejja nassumu li għandna tali polinomju u l-parteċipanti kollha jafu l-komponenti privati tagħhom.
Kif nistgħu nużaw tali polinomju biex niġġeneraw numru każwali? Biex tibda, neħtieġu xi string li qabel ma ntużatx bħala input għall-ġeneratur. Fil-każ ta 'blockchain, il-hash tal-aħħar blokk h huwa kandidat tajjeb għal linja bħal din. Ħalli lill-parteċipanti jridu joħolqu numru bl-addoċċ bl-użu h bħal żerriegħa. Il-parteċipanti jikkonvertu l-ewwel h għal punt fuq il-kurva billi tuża kwalunkwe funzjoni predefinita:
H = scalarToPoint(h)
Imbagħad kull parteċipant i tikkalkula u tippubblika Hi = p(i)H, x'jistgħu jagħmlu għax jafu p(i) u H. Żvelar Hi ma tippermettix parteċipanti oħra biex jirrestawraw il-komponent privat ith parteċipant, u għalhekk sett wieħed ta 'komponenti privati jistgħu jintużaw minn blokk għal blokk. Għalhekk, l-algoritmu għali ta 'ġenerazzjoni polinomjali deskritt hawn taħt jeħtieġ li jiġi esegwit darba biss.
Meta k il-parteċipanti ġew awtopsjati Hi = p(i)H, kulħadd jista 'jikkalkula Hx = p(x)H għal kulħadd x grazzi għall-proprjetà tal-polinomji li ddiskutejna fl-aħħar taqsima. F'dan il-mument, il-parteċipanti kollha jikkalkulaw H0 = p(0)H, u dan huwa n-numru każwali li jirriżulta. Jekk jogħġbok innota li ħadd ma jaf p(0), u għalhekk l-uniku mod biex tikkalkula p(0)H – din hija interpolazzjoni p(x)H, li huwa possibbli biss meta k valuri p(i)H magħrufa. Ftuħ kwalunkwe kwantità iżgħar p(i)H ma jipprovdi ebda informazzjoni dwar p(0)H.
Il-ġeneratur ta 'hawn fuq għandu l-proprjetajiet kollha li rridu: attakkanti jikkontrollaw biss k-1 parteċipant jew inqas m'għandhom l-ebda informazzjoni jew influwenza fuq il-konklużjoni, filwaqt li hemm k parteċipanti jistgħu jikkalkulaw in-numru li jirriżulta, u kwalunkwe subsett ta k il-parteċipanti dejjem jaslu għall-istess riżultat għall-istess żerriegħa.
Hemm problema waħda li evitajna bir-reqqa hawn fuq. Biex l-interpolazzjoni taħdem, huwa importanti li l-valur Hi li kienet ippubblikata minn kull parteċipant i kien verament l-istess p(i)H. Peress li ħadd ħlief i-th parteċipant ma jafx p(i), ħadd ħlief i-th parteċipant ma jistax jivverifika dan Hi fil-fatt ikkalkulat b'mod korrett, u mingħajr ebda prova kriptografika tal-korrettezza Hi attakkant jista 'jippubblika kwalunkwe valur bħala Hi, u jinfluwenzaw b'mod arbitrarju l-output tal-ġeneratur tan-numru każwali:
Valuri differenti ta 'H_1 mibgħuta mill-ewwel parteċipant iwasslu għal H_0 li jirriżulta differenti
Hemm mill-inqas żewġ modi biex tipprova l-korrettezza Hi, se nqisuhom wara li nanalizzaw il-ġenerazzjoni tal-polinomjali.
Ġenerazzjoni polinomjali
Fl-aħħar taqsima aħna assumejna li għandna tali polinomjali p(x) gradi k-1 li l-parteċipant i jaf p(i), u ħadd ieħor ma għandu xi informazzjoni dwar dan il-valur. Fit-taqsima li jmiss ser ikollna bżonn ukoll dak għal xi punt predeterminat G kulħadd kien jaf p(x)G għal kulħadd x.
F'din it-taqsima ser nassumu li kull parteċipant lokalment għandu xi ċavetta privata xi, tali li kulħadd ikun jaf iċ-ċavetta pubblika korrispondenti Xi.
Protokoll ta' ġenerazzjoni polinomjali possibbli huwa kif ġej:
-
Kull parteċipant i lokalment joħloq polinomjali arbitrarju pi(x) grad k-1. Imbagħad jibagħtu lil kull parteċipant j tifsira pi(j), encrypted b'ċavetta pubblika Xj. Għalhekk biss i-th и j-th parteċipant jafu pi(j). Parteċipant i tħabbar ukoll pubblikament pi(j)G għal kulħadd j minn 1 li k inklużiv.
-
Il-parteċipanti kollha jużaw xi kunsens biex jagħżlu k parteċipanti li l-polinomji tagħhom se jintużaw. Peress li xi parteċipanti jistgħu jkunu offline, ma nistgħux nistennew sa kulħadd n il-parteċipanti se jippubblikaw polinomji. Ir-riżultat ta 'dan il-pass huwa sett Z li jikkonsisti mill-inqas k polinomji maħluqa fil-pass (1).
-
Il-parteċipanti jiżguraw li l-valuri li jafu pi(j) jikkorrispondu ma' mħabbra pubblikament pi(j)G. Wara dan il-pass Z polinomji biss li għalihom trażmessi privatament pi(j) jikkorrispondu ma' mħabbra pubblikament pi(j)G.
-
Kull parteċipant j tikkalkula l-komponent privat tagħha p(j) bħala somma pi(j) għal kulħadd i в Z. Kull parteċipant jikkalkula wkoll il-valuri kollha p(x)G bħala somma pi(x)G għall-i kollha в Z.
innota li p(x) – huwa verament polinomjali k-1, għax hija s-somma tal-individwu pi(x), li kull wieħed minnhom huwa polinomju ta' grad k-1. Imbagħad, innota li filwaqt li kull parteċipant j jaf p(j), m'għandhom l-ebda informazzjoni dwar p(x) għall- x ≠ j. Tabilħaqq, biex jikkalkulaw dan il-valur, jeħtieġ li jkunu jafu kollox pi(x), u sakemm il-parteċipant j ma jafx mill-inqas wieħed mill-polinomji magħżula, ma jkollhomx biżżejjed informazzjoni dwar p(x).
Dan huwa l-proċess kollu tal-ġenerazzjoni tal-polinomjali li kien meħtieġ fl-aħħar taqsima. Il-passi 1, 2 u 4 hawn fuq għandhom implimentazzjoni pjuttost ovvja. Iżda l-pass 3 mhuwiex daqshekk trivjali.
Speċifikament, irridu nkunu kapaċi nippruvaw li kkodifikat pi(j) verament jikkorrispondu għal dawk ippubblikati pi(j)G. Jekk ma nistgħux nippruvaw dan, l-attakkant i jistgħu jibagħtu żibel minflok pi(j) lill-parteċipant j, u parteċipant j mhux se jkunu jistgħu jiksbu l-valur reali pi(j), u mhux se tkun kapaċi tikkalkula l-komponent privat tagħha.
Hemm protokoll kriptografiku li jippermettilek toħloq messaġġ addizzjonali provai(j), b'tali mod li kull parteċipant, li jkollu xi valur e, kif ukoll prova(j) и pi(j)G, jistgħu jivverifikaw li lokalment e - huwa verament pi(j), encrypted biċ-ċavetta tal-parteċipant j. Sfortunatament, id-daqs ta 'evidenza bħal din huwa oerhört kbir, u peress li huwa meħtieġ li tiġi ppubblikata O(nk) Tali evidenza ma tistax tintuża għal dan il-għan.
Minflok jipprova li pi(j) соответствует pi(j)G nistgħu nallokaw perjodu twil ħafna ta 'żmien fil-protokoll ta' ġenerazzjoni polinomjali, li matulu l-parteċipanti kollha jiċċekkjaw il-kriptaġġ riċevut pi(j), u jekk il-messaġġ decrypted ma jikkorrispondix għall-pubbliku pi(j)G, huma jippubblikaw prova kriptografika li l-messaġġ kriptat li rċevew huwa żbaljat. Jipprova li l-messaġġ ebda соответствует pi(G) ħafna aktar faċli milli tipprova li jaqbel. Ta’ min jinnota li dan jirrikjedi li kull parteċipant jidher online mill-inqas darba matul iż-żmien allokat biex joħloq tali evidenza, u jiddependi fuq is-suppożizzjoni li jekk jippubblikaw prova bħal din, din tilħaq il-parteċipanti l-oħra kollha fl-istess ħin allokat.
Jekk parteċipant ma deherx onlajn matul dan il-perjodu ta 'żmien, u kellu mill-inqas komponent wieħed mhux korrett, allura dak il-parteċipant partikolari ma jkunx jista' jipparteċipa f'ġenerazzjoni ulterjuri tan-numri. Il-protokoll, madankollu, xorta se jiffunzjona jekk ikun hemm mill-inqas k parteċipanti li jew irċevew il-komponenti t-tajba jew irnexxielhom iħallu prova ta’ żball fiż-żmien allokat.
Provi ta' korrettezza ta' H_i
L-aħħar parti li għad trid tiġi diskussa hija kif tipprova l-korrettezza tal-pubblikazzjoni Hi, jiġifieri li Hi = p(i)H, mingħajr ftuħ p(i).
Ejja niftakru li l-valuri H, G, p(i)G pubbliku u magħruf minn kulħadd. Irċievi operazzjoni p(i) jafu p(i)G и G imsejħa logaritmu diskreti, jew dlog, u rridu nippruvaw li:
dlog(p(i)G, G) = dlog(Hi, H)
mingħajr żvelar p(i). Kostruzzjonijiet għal provi bħal dawn jeżistu, pereżempju.
B'dan id-disinn, kull parteċipant, flimkien ma Hi jibgħat prova ta 'korrettezza skond id-disinn.
Ladarba jiġi ġġenerat numru bl-addoċċ, ħafna drabi jeħtieġ li jintuża minn parteċipanti minbarra dawk li ġġenerawh. Parteċipanti bħal dawn, flimkien man-numru, għandhom jibagħtu kollha Hi u evidenza relatata.
Qarrej kurżiv jista 'jistaqsi: peress li n-numru każwali finali huwa H0, u p(0)G – Din hija informazzjoni pubblika, għaliex għandna bżonn prova għal kull individwu Hi, għaliex ma tibgħatx prova li minflok
dlog(p(0)G, G) = dlog(H0, H)
Il-problema hija li prova bħal din ma tistax tinħoloq bl-użu tal-Protokoll Schnorr għax ħadd ma jaf il-valur p (0), meħtieġ biex tinħoloq il-prova, u barra minn hekk, il-ġeneratur kollu tan-numru każwali huwa bbażat fuq il-fatt li ħadd ma jaf dan il-valur. Għalhekk huwa meħtieġ li jkun hemm il-valuri kollha Hi u l-evidenza individwali tagħhom biex tipprova l-korrettezza H0.
Madankollu, jekk kien hemm xi operazzjoni fuq punti fuq kurvi ellittiċi li hija semantikament simili għall-multiplikazzjoni, il-prova tal-korrettezza H0 ikun trivjali, aħna sempliċement niżguraw li
H0 × G = p(0)G × H
Jekk il-kurva magħżula tappoġġja , din il-prova taħdem. F'dan il-każ H0 mhuwiex biss l-output ta 'ġeneratur ta' numru każwali, li jista 'jiġi vverifikat minn kwalunkwe parteċipant li jaf G, H и p(0)G. H0 hija wkoll firma fuq il-messaġġ li ntuża bħala żerriegħa, li tikkonferma dan k и n il-parteċipanti ffirmaw dan il-messaġġ. Għalhekk, jekk żerriegħa - huwa l-hash tal-blokk fil-protokoll blockchain, allura H0 hija kemm multi-firma fuq blokka kif ukoll numru każwali tajjeb ħafna.
Bħala konklużjoni
Dan l-artikolu huwa parti minn serje ta 'blogs tekniċi . NEAR huwa protokoll u pjattaforma blockchain għall-iżvilupp ta 'applikazzjonijiet deċentralizzati b'enfasi fuq il-faċilità ta' żvilupp u l-faċilità ta 'użu għall-utenti finali.
Il-kodiċi tal-protokoll huwa miftuħ, l-implimentazzjoni tagħna hija miktuba f'Rut, tista 'tinstab .
Tista 'tara kif jidher l-iżvilupp għal NEAR u tesperimenta fl-IDE onlajn .
Tista' ssegwi l-aħbarijiet kollha bir-Russu fuq u , u bl-Ingliż fl-uffiċjal .
Narak dalwaqt!
Sors: www.habr.com