Ngaba kunokwenzeka ukwenza amanani angaqhelekanga ukuba asithembani? Icandelo loku-1

Hayi Habr!

Kule nqaku ndiza kuthetha ngesizukulwana samanani angama-pseudo-random ngabathathi-nxaxheba abangathembani. Njengoko siza kubona ngezantsi, ukuphumeza "phantse" ijeneretha elungileyo ilula kakhulu, kodwa eyona ilunge kakhulu inzima.

Kutheni kuya kuba yimfuneko ukuvelisa amanani angaqhelekanga phakathi kwabathathi-nxaxheba abangathembaniyo? Enye indawo yesicelo kukwabela abantu izicelo. Umzekelo, isicelo esamkela ubhejo oluvela kumthathi-nxaxheba kwaye mhlawumbi siphinda-phinda imali nge-49% enokwenzeka okanye ithatha i-51% enokwenzeka iya kusebenza kuphela ukuba inokufumana inani elingenamkhethe. Ukuba umhlaseli unokuphembelela isiphumo se-random number generator, kwaye nokuba andise kancinane ithuba lakhe lokufumana intlawulo kwisicelo, uya kuyitshabalalisa ngokulula.

Xa siyila iprotocol yokuvelisa amanani ngokungakhethiyo, sifuna ukuba ibeneempawu ezintathu:

1. Makangabi namkhethe. Ngamanye amazwi, akukho mthathi-nxaxheba kufuneka nangayiphi na indlela abe nefuthe kwisiphumo se-random number generator.

2. Umele ukuba akaqikeleleki. Ngamanye amazwi, akukho mthathi-nxaxheba onokuthi akwazi ukuqikelela ukuba leliphi inani eliya kwenziwa (okanye ukuqikelela nayiphi na impahla yalo) phambi kokuba iveliswe.

3. Iprotocol kufuneka isebenze, oko kukuthi, ukuchasana nento yokuba ipesenti ethile yabathathi-nxaxheba baqhawula kwinethiwekhi okanye bazame ngabom ukumisa iprotocol.

Kweli nqaku siza kujonga iindlela ezimbini: I-RANDAO + VDF kunye neendlela zokucima iikhowudi. Kwicandelo elilandelayo, siza kuphonononga ngokweenkcukacha indlela esekelwe kwiisignesha zomda.

Kodwa kuqala, makhe sijonge i-algorithm elula neqhele ukusetyenziswa esebenzayo, engalindelekanga, kodwa enomkhethe.

RANDAO

I-RANDAO ilula kakhulu kwaye ke ngoko isetyenziswa ngokuxhaphakileyo indlela yokuvelisa okungakhethiyo. Bonke abathathi-nxaxheba bothungelwano kuqala bakhethe kwalapha inombolo yepseudorandom, emva koko umthathi-nxaxheba ngamnye athumele i-hash yenani elikhethiweyo. Emva koko, abathathi-nxaxheba batshintshana ngokutyhila amanani abo akhethiweyo kwaye benze umsebenzi we-XOR kumanani atyhiliweyo, kwaye umphumo walo msebenzi uba ngumphumo weprotocol.

Isinyathelo sokupapasha i-hashes ngaphambi kokutyhila amanani ayimfuneko ukwenzela ukuba umhlaseli angakwazi ukukhetha inombolo yakhe emva kokuba ebone amanani abanye abathathi-nxaxheba. Oku kuya kumvumela ukuba aqinisekise ngesandla esinye isiphumo se-random ye-generator.

Ngethuba lomgaqo-nkqubo, abathathi-nxaxheba kufuneka beze kwisigqibo esiqhelekileyo (esibizwa ngokuba yimvumelwano) kabini: ukuqala nini ukutyhila amanani akhethiweyo, kwaye ngoko ke uyeke ukwamkela i-hashes, kwaye nini ukuyeka ukwamkela amanani akhethiweyo kunye nokubala okungahleliwe okubangelwayo. inani. Ukwenza izigqibo ezinjalo phakathi kwabathathi-nxaxheba abangathembaniyo akuwona umsebenzi olula ngokwawo, kwaye siya kubuyela kuwo kumanqaku azayo; kweli nqaku siza kucinga ukuba i-algorithm yokuvumelana enjalo iyafumaneka kuthi.

Zeziphi kwezi propati sizichazileyo ngasentla enazo i-RANDAO? Ayinakuqikelelwa, inamandla afanayo njengeprothokholi yemvumelwano esisiseko, kodwa inomkhethe. Ngokukodwa, umhlaseli unokuqwalasela inethiwekhi, kwaye emva kokuba abanye abathathi-nxaxheba baveze amanani abo, unako ukubala i-XOR yabo, kwaye anqume ukuba okanye akayi kutyhila inombolo yakhe ukuchaphazela umphumo. Ngelixa oku kuthintela umhlaseli ekubeni amisele ngesandla esinye isiphumo se-random ye-generator, isamnika i-1 bit yempembelelo. Kwaye ukuba abahlaseli balawula abathathi-nxaxheba abaninzi, ngoko inani leebhithi abazilawulayo liyakulingana nenani labathathi-nxaxheba phantsi kolawulo lwabo.

Impembelelo yabahlaseli inokuncitshiswa kakhulu ngokufuna ukuba abathathi-nxaxheba baveze amanani ngokulandelelana. Emva koko umhlaseli uya kuba nako ukuchaphazela umphumo kuphela ukuba uvulwe ekugqibeleni. Ngelixa impembelelo incinci kakhulu, i-algorithm isacalanye.

RANDAO+VDF

Enye indlela yokwenza i-RANDAO ingakhethi cala yile: emva kokuba onke amanani atyhiliwe kwaye i-XOR ibalwe, umphumo wayo wondliwa kwigalelo lomsebenzi, othatha ixesha elide ukubala, kodwa ikuvumela ukuba ukhangele ukuchaneka kwe ukubala ngokukhawuleza okukhulu.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Lo msebenzi ubizwa ngokuba yi-Verrifiable Delay Function, okanye iVDF. Ukuba ukubala umphumo wokugqibela kuthatha ixesha elide kunenqanaba lokuvezwa kwenombolo, ngoko umhlaseli akayi kukwazi ukuqikelela umphumo wokubonisa okanye ukufihla inombolo yakhe, ngoko ke uya kulahlekelwa ithuba lokuchaphazela umphumo.

Ukuphuhlisa ii-VDF ezilungileyo kunzima kakhulu. Kukho iimpumelelo ezininzi mva nje, umz. oku и oku, eyenza i-VDF isebenze ngakumbi ekusebenzeni, kwaye i-Ethereum 2.0 iceba ukusebenzisa i-RANDAO kunye ne-VDF njengomthombo wenombolo engahleliweyo kwixesha elide. Ngaphandle kwento yokuba le ndlela ayinakuqikelelwa kwaye ingenamkhethe, inenzuzo eyongeziweyo yokuba inokwenzeka ukuba ubuncinci abathathi-nxaxheba ababini bafumaneka kwinethiwekhi (kucingelwa ukuba i-protocol yokuvumelana esetyenzisiweyo iyasebenza xa ujongene nenani elincinci labathathi-nxaxheba).

Owona mceli mngeni mkhulu wale ndlela kukuseta i-VDF kangangokuba nomthathi-nxaxheba onezixhobo ezikhethekileyo ezibiza kakhulu akanakukwazi ukubala i-VDF ngaphambi kokuphela kwesigaba sokufumanisa. Ngokufanelekileyo, i-algorithm kufuneka ibe nomda obalulekileyo wokhuseleko, yithi 10x. Umfanekiso ongezantsi ubonisa ukuhlaselwa ngumdlali one-ASIC ekhethekileyo evumela ukuba aqhube i-VDF ngokukhawuleza kunexesha elibekelwe ukutyhila ukuqinisekiswa kwe-RANDAO. Umthathi-nxaxheba onjalo usenako ukubala umphumo wokugqibela esebenzisa okanye engasebenzisi inombolo yakhe, kwaye ke, ngokusekelwe ekubaleni, khetha ukuba uyayibonisa okanye ungayibonisi.

Kwintsapho ye-VDF ekhankanywe ngasentla, ukusebenza kwe-ASIC ezinikeleyo kunokuba ngamaxesha angama-100 + aphezulu kune-hardware eqhelekileyo. Ngoko ukuba isigaba sokubhengeza sithatha imizuzwana ye-10, ngoko i-VDF ibalwa kwi-ASIC enjalo kufuneka ithathe ngaphezu kwemizuzwana ye-100 ukuba ibe nomda wokhuseleko we-10x, kwaye ngoko ke i-VDF efanayo ekhompyutheni kwi-hardware yempahla kufuneka ithathe i-100x imizuzwana ye-100 = ~ iiyure ze-3.

I-Ethereum Foundation iceba ukusombulula le ngxaki ngokudala eyakhe ifumaneka esidlangalaleni, ii-ASIC zamahhala. Emva kokuba oku kwenzekile, zonke ezinye iiprotocol nazo zingasebenzisa le teknoloji, kodwa kude kube ngoko indlela ye-RANDAO + VDF ayiyi kuba yinto esebenzayo kwiiprotocol ezingenako ukutshala imali ekuphuhliseni ii-ASIC zabo.

Amanqaku amaninzi, iividiyo kunye nolunye ulwazi malunga ne-VDF ziqokelelwe kule ndawo.

Sisebenzisa iikhowudi zokucima

Kweli candelo, siza kujonga iprotocol yokuvelisa amanani ngokungakhethiyo esebenzisayo iikhowudi zokucima. Inokunyamezela ukuya kuthi ga kwi-⅓ abahlaseli ngelixa ihlala isebenza, kwaye ivumele ukuya kuthi ga kwi-⅔ abahlaseli ukuba babekhona ngaphambi kokuba baqikelele okanye baphembelele iziphumo.

Ingcamango ephambili yeprotocol yile ilandelayo. Ukwenza lula, makhe sicinge ukuba kukho ngqo abathathi-nxaxheba abali-100. Masicinge kwakhona ukuba bonke abathathi-nxaxheba banesitshixo sabucala, kwaye izitshixo zoluntu zabo bonke abathathi-nxaxheba zaziwa kubo bonke abathathi-nxaxheba:

1. Umthathi-nxaxheba ngamnye ekuhlaleni uza nomtya omde, awuqhawule abe ngamacandelo angama-67, enze iikhowudi zokucima ukuze afumane izabelo ezingama-100 kangangokuba naziphi na ezingama-67 zanele ukubuyisela umtya, zabela isabelo ngasinye kwezili-100 komnye wabathathi-nxaxheba, kwaye zifihlwe ngentsomi. iqhosha likawonke-wonke lomthathi-nxaxheba elifanayo. Zonke izabelo ezinekhowudi zipapashwa.

2. Abathathi-nxaxheba basebenzisa uhlobo oluthile lwemvumelwano ukufikelela kwisivumelwano kwiiseti ezinekhowudi ezivela kubathathi-nxaxheba abathile abangama-67.

3. Nje ukuba imvumelwano ifikelelwe, umthathi-nxaxheba ngamnye uthatha izabelo ezikhowudiweyo kwiseti nganye kwezingama-67 ezifihliweyo ngesitshixo sikawonke-wonke, akhuphe zonke ezo zabelo, aze apapashe zonke ezo zabelo zikhutshiweyo.

4. Emva kokuba abathathi-nxaxheba be-67 begqibe inyathelo (3), zonke iiseti ezivunyelweneyo zinokuthi zihlanjululwe ngokupheleleyo kwaye zakhiwe ngokutsha ngenxa yeempawu zeekhowudi zokucima, kwaye inombolo yokugqibela inokufumaneka njenge-XOR yemigca yokuqala abathathi-nxaxheba baqala ngayo (1) .

Le protocol inokuboniswa ingathathi cala kwaye ayiqikeleleki. Isiphumo senani elingenamkhethe limiselwa emva kokuba kufikelelwe kwimvumelwano, kodwa akwaziwa nakubani na de kube ⅔ yabathathi-nxaxheba bagqibe iikhowuwudi zamalungu afihliweyo ngesitshixo sikawonke-wonke. Ke, inani elingenamkhethe limiselwa phambi kokuba kupapashwe ulwazi olwaneleyo lokuyakha kwakhona.

Kwenzeka ntoni ukuba kwinyathelo (1) omnye wabathathi-nxaxheba uthumele izabelo ezikhowudiweyo kwabanye abathathi-nxaxheba ezingeyiyo ikhowudi yokucima echanekileyo kumtya othile? Ngaphandle kweenguqu ezongezelelweyo, abathathi-nxaxheba abahlukeneyo abayi kukwazi ukubuyisela umtya konke konke, okanye baya kuphinda bafumane iintambo ezahlukeneyo, okuya kubangela ukuba abathathi-nxaxheba abahlukeneyo bafumane inombolo eyahlukileyo. Ukuthintela oku, unokwenza oku kulandelayo: umthathi-nxaxheba ngamnye, ukongeza kwizabelo ezikhowudiweyo, kwakhona ubala. Umthi weMerkla zonke izabelo ezinjalo, kwaye ithumela umthathi-nxaxheba ngamnye zombini i-encoded share ngokwayo kunye nengcambu yomthi we-merkle, kunye nobungqina bokufakwa kwesabelo kwi-merkle tree. Kwimvumelwano kwinyathelo (2), abathathi-nxaxheba ke bengavumelani nje kwiseti yeeseti, kodwa kwiseti yeengcambu ezithile zemithi enjalo (ukuba umthathi-nxaxheba othile utenxile kwiprotocol, kwaye wathumela iingcambu zomthi we-merkle ezahlukeneyo kubathathi-nxaxheba abahlukeneyo, kunye neengcambu ezimbini ezinjalo ziboniswa ngexesha lokuvumelana, umqolo wakhe awufakwanga kwiseti yesiphumo). Ngenxa yemvumelwano, siya kuba nemigca ekhowudiweyo engama-67 kunye neengcambu ezihambelanayo zomthi we-merkle kangangokuba kukho ubuncinane abathathi-nxaxheba be-67 (kungekhona abafane bacebise imigca ehambelanayo), ngubani ngamnye kwimigca engama-67. umyalezo onesabelo sekhowudi yokucima, kunye nobungqina bokwenzeka kwesabelo sabo kumthi ohambelana nawo.

Xa kwinyathelo (4) umthathi-nxaxheba echaza iibhithi ezingama-67 kumtya othile kwaye ezama ukuphinda awakhe kwakhona umtya woqobo ukusuka kuwo, enye yeendlela ezikhethiweyo inokwenzeka:

1. Umtya ubuyiselwe, kwaye ukuba emva koko u-erasure-encoded kwakhona, kwaye umthi we-Merkle ubalwa kwizabelo ezibalwe ekuhlaleni, ingcambu ihambelana naleyo ekufikelelwe kuyo ukuvumelana.

2. Umqolo ubuyiselwe, kodwa ingcambu ebalwe endaweni ayifani naleyo ekufikelelwe kuyo kwimvumelwano.

3. Umqolo awubuyiselwa.

Kulula ukubonisa ukuba ukhetho (1) lwenzekile ubuncinane kumthathi-nxaxheba omnye ngasentla, ngoko ke ukhetho (1) lwenzekile kubo bonke abathathi-nxaxheba, kwaye ngokuphendlelwayo, ukuba ukhetho (2) okanye (3) lwenzekile ubuncinane kumthathi-nxaxheba omnye, emva koko. kubo bonke abathathi-nxaxheba ukhetho (2) okanye (3) luya kwenzeka. Ngaloo ndlela, kumqolo ngamnye kwiseti, mhlawumbi bonke abathathi-nxaxheba baya kuyifumana ngempumelelo, okanye bonke abathathi-nxaxheba baya kusilela ukuyibuyisela. Isiphumo senani le-random ke yi-XOR yemiqolo kuphela abathathi-nxaxheba abakwaziyo ukuyifumana.

Imisayino yomqobo

Enye indlela yokungakhethi kukusebenzisa oko kubizwa ngokuba yi-BLS threshold signatures. I-random generator inombolo esekelwe kwiisignesha ze-threshold ineziqinisekiso ezifanayo kunye ne-algorithm yokucima ikhowudi echazwe ngasentla, kodwa inenani eliphantsi kakhulu le-asymptotic yemiyalezo ethunyelwe ngenethiwekhi ngenani ngalinye elenziwe.

Utyikityo lwe-BLS luyilo oluvumela abathathi-nxaxheba abaninzi ukuba benze umsayino omnye oqhelekileyo womyalezo. Ezi zisayino zihlala zisetyenziselwa ukugcina indawo kunye ne-bandwidth ngokungafuni utyikityo oluninzi ukuba luthunyelwe. 

Isicelo esiqhelekileyo sokutyikitya kwe-BLS kwiiprothokholi ze-blockchain, ukongeza ekuveliseni amanani angaqhelekanga, kukusayinwa kwebhloko kwiiprothokholi ze-BFT. Masithi i-100 labathathi-nxaxheba benza iibhloko, kwaye ibhloko ithathwa njengeyokugqibela ukuba i-67 kubo bayisayine. Bonke banokungenisa iinxalenye zabo zesiginitsha ye-BLS kwaye basebenzise i-algorithm ethile yokuvumelana ukuze bavumelane ngama-67 kubo kwaye badibanise kwisiginitsha ye-BLS enye. Naziphi na iinxalenye ezingama-67 (okanye ngaphezulu) zingasetyenziselwa ukwenza utyikityo lokugqibela, oluya kuxhomekeka ekubeni yeyiphi na imisayino engama-67 edityanisiweyo kwaye ke ngoko inokwahluka, nangona ukhetho olwahlukileyo lwabathathi-nxaxheba abangama-67 luya kudala utyikityo olwahlukileyo, naluphi na utyikityo olunjalo luya kuba lusemthethweni. utyikityo lwebhloko. Abathathi-nxaxheba abaseleyo ke kufuneka bafumane kuphela kwaye baqinisekise isiginitsha enye kuphela kwibhloko nganye, endaweni ye-67, phezu kwenethiwekhi, enciphisa kakhulu umthwalo kwinethiwekhi.

Kuvela ukuba ukuba izitshixo zangasese ezisetyenziswa ngabathathi-nxaxheba ziveliswa ngendlela ethile, ngoko kungakhathaliseki ukuba yiyiphi i-67 signatures (okanye ngaphezulu, kodwa ingekho ngaphantsi) ihlanganiswe, isiginesha esisiphumo siya kufana. Oku kunokusetyenziswa njengomthombo wokungakhethi: abathathi-nxaxheba bavuma kuqala ngomyalezo othile abaya kuwutyikitya (oku kunokuba yimveliso ye-RANDAO okanye i-hash yebhloko yokugqibela, ayinamsebenzi ukuba nje itshintsha lonke ixesha. kwaye iyahambelana) kwaye yenze umsayino we-BLS wayo. Isiphumo sesizukulwana asiyi kuqikelelwa de kube ngabathathi-nxaxheba abangama-67 babonelele ngamacandelo abo, kwaye emva koko umphumo sele umiselwe kwangaphambili kwaye awukwazi ukuxhomekeka kwizenzo zanoma yimuphi umthathi-nxaxheba.

Le ndlela yokungakhethi buso iyasebenza okoko nje ⅔ yabathathi-nxaxheba kwi-intanethi bobabini balandela iprotocol, kwaye ayikhethi cala kwaye ayiqikeleleki ukuba nje ⅓ yabathathi-nxaxheba balandela iprotocol. Kubalulekile ukuqaphela ukuba umhlaseli olawula ngaphezulu kwe-⅓ kodwa ngaphantsi kwe-⅔ yabathathi-nxaxheba unokumisa iprothokholi, kodwa akakwazi ukuqikelela okanye ukuphembelela imveliso yayo.

Imisayino yeThreshold ngokwayo sisihloko esinomdla kakhulu. Kwinxalenye yesibini yenqaku, siya kuhlalutya ngokweenkcukacha indlela abasebenza ngayo, kunye nendlela echanekileyo ngayo ukuvelisa izitshixo zabathathi-nxaxheba ukwenzela ukuba iisignesha ze-threshold zingasetyenziswa njenge-random number generator.

Ekugqibeleni

Eli nqaku lelokuqala kuluhlu lwamanqaku eblogi yobugcisa NGOKU. KUFUTSHANE iprotocol yebhlokhi kunye neqonga lokuphuhlisa izicelo ezinikezelweyo kunye nogxininiso ekuphuhliseni lula kunye nokusebenziseka ngokulula kubasebenzisi bokugqibela.

Ikhowudi yeprotocol ivuliwe, ukuphunyezwa kwethu kubhalwe kwi-Rust, inokufumaneka apha.

Ungalubona ukuba uphuhliso lwe-KUFUTSHANE lujongeka njani kwaye ulinge kwi-IDE ekwi-intanethi apha.

Ungalandela zonke iindaba ngesiRashiya iqela letelegram kunye iqela kwiVKontakte, nangesiNgesi kwigosa twitter.

Ndizokubona ngokukhawuleza!

umthombo: www.habr.com