Kungenzeka yini ukukhiqiza izinombolo ezingahleliwe uma singathembani? Ingxenye 1

Sawubona Habr!

Kulesi sihloko ngizokhuluma ngesizukulwane sezinombolo ezingahleliwe ngabahlanganyeli abangathembani. Njengoba sizobona ngezansi, ukusebenzisa i-generator "cishe" enhle kulula, kodwa enhle kakhulu kunzima.

Kungani kungadingeka ukukhiqiza izinombolo ezingahleliwe phakathi kwabahlanganyeli abangathembani? Indawo eyodwa yezicelo yizicelo ezihlukaniselwe izwe. Isibonelo, isicelo esamukela ukubheja okuvela kubahlanganyeli futhi siphindaphinde inani lemali ngamathuba angu-49% noma lisuse ngamathuba angu-51% lizosebenza kuphela uma lingathola inombolo engahleliwe ngokungachemi. Uma umhlaseli engaba nomthelela kumphumela wejeneretha yenombolo engahleliwe, futhi aze andise kancane ithuba lakhe lokuthola inkokhelo esicelweni, uzoyicekela phansi kalula.

Uma siklama iphrothokholi yokukhiqiza inombolo engahleliwe, sifuna ibe nezindawo ezintathu:

1. Kumele angachemi. Ngamanye amazwi, akekho umhlanganyeli okufanele nganoma iyiphi indlela abe nomthelela kumphumela wejeneretha yenombolo engahleliwe.

2. Kumele angabikezeli. Ngamanye amazwi, akekho umhlanganyeli okufanele akwazi ukubikezela ukuthi iyiphi inombolo ezokhiqizwa (noma acabangele noma yiziphi izici zayo) ngaphambi kokuthi yenziwe.

3. Iphrothokholi kufanele isebenze, okungukuthi, imelane neqiniso lokuthi iphesenti elithile labahlanganyeli linqamula kunethiwekhi noma lizame ngamabomu ukumisa umthetho olandelwayo.

Kulesi sihloko sizobheka izindlela ezimbili: i-RANDAO + VDF kanye nendlela yokusula amakhodi. Engxenyeni elandelayo, sizohlola ngokuningiliziwe indlela esekelwe kumasignesha e-threshold.

Kodwa okokuqala, ake sibheke i-algorithm elula nevame ukusetshenziswa esebenzayo, engalindeleki, kodwa echemile.

RANDAO

I-RANDAO iyindlela elula kakhulu futhi evame ukusetshenziswa kakhulu ekukhiqizeni okungahleliwe. Bonke abahlanganyeli benethiwekhi baqale bakhethe endaweni inombolo-mbumbulu, bese umhlanganyeli ngamunye ethumela i-hash yenombolo ekhethiwe. Okulandelayo, ababambiqhaza bayashintshana ngokudalula izinombolo abazikhethile futhi benze umsebenzi we-XOR ezinombolweni eziveziwe, futhi umphumela walo msebenzi uba umphumela wephrothokholi.

Isinyathelo sokushicilela ama-hashes ngaphambi kokudalula izinombolo siyadingeka ukuze umhlaseli angakwazi ukukhetha inombolo yakhe ngemuva kokubona izinombolo zabanye abahlanganyeli. Lokhu kuzomvumela ukuthi anqume ngesandla esisodwa ukuphuma kwejeneretha yenombolo engahleliwe.

Ngesikhathi sephrothokholi, ababambiqhaza badinga ukufika esinqumweni esivamile (okuthiwa ukuvumelana) kabili: ukuthi baqale nini ukudalula izinombolo ezikhethiwe, ngakho-ke bayeke ukwamukela ama-hashes, nokuthi kufanele bayeke nini ukwamukela izinombolo ezikhethiwe nokubala okungahleliwe okutholakele. inombolo. Ukwenza izinqumo ezinjalo phakathi kwabahlanganyeli abangathembani akuwona umsebenzi olula ngokwakho, futhi sizobuyela kuwo ezihlokweni ezizayo; kulesi sihloko sizothatha ngokuthi i-algorithm yokuvumelana enjalo iyatholakala kithi.

Yiziphi izici esizichaze ngenhla i-RANDAO enazo? Ayinakwenzeka, inamandla afanayo nephrothokholi yokuvumelana, kodwa ichemile. Ngokuqondile, umhlaseli angakwazi ukubona inethiwekhi, futhi ngemva kokuba abanye ababambiqhaza beveze izinombolo zabo, angakwazi ukubala i-XOR yabo, futhi anqume ukuthi aveze noma cha inombolo yakhe ukuze athonye umphumela. Nakuba lokhu kuvimbela umhlaseli ekunqumeni ngesandla esisodwa ukuphuma kwejeneretha yenombolo engahleliwe, kusamnika ibhithi elingu-1 lomthelela. Futhi uma abahlaseli belawula abahlanganyeli abambalwa, inani lamabhithi abawalawulayo lizolingana nenani labahlanganyeli abangaphansi kolawulo lwabo.

Umthelela wabahlaseli ungancishiswa kakhulu ngokudinga ukuthi ababambiqhaza baveze izinombolo ngokulandelana kwazo. Khona-ke umhlaseli uzokwazi ukuthonya umphumela kuphela uma evulwa ekugcineni. Nakuba ithonya lincane kakhulu, i-algorithm isachemile.

RANDAO+VDF

Enye indlela yokwenza i-RANDAO ingachemi yile: ngemuva kokuthi zonke izinombolo zembulwe futhi i-XOR ibalwe, umphumela wayo ufakwa ekufakweni komsebenzi, okuthatha isikhathi eside kakhulu ukubala, kodwa ikuvumela ukuthi uhlole ukufaneleka ukubala ngokushesha okukhulu.

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

Lo msebenzi ubizwa ngokuthi Verifiable Delay Function, noma i-VDF. Uma ukubala umphumela wokugcina kuthatha isikhathi eside kunesiteji sokudalulwa kwenombolo, khona-ke umhlaseli ngeke akwazi ukubikezela umphumela wokubonisa noma ukufihla inombolo yakhe, ngakho-ke uzolahlekelwa ithuba lokuthonya umphumela.

Ukwakha ama-VDF amahle kunzima kakhulu. Kube khona impumelelo eminingana muva nje, isb. lokhu и lokhu, okwenza i-VDF isebenze ngokwengeziwe ekusebenzeni, futhi i-Ethereum 2.0 ihlela ukusebenzisa i-RANDAO ne-VDF njengomthombo wenombolo engahleliwe esikhathini eside. Ngaphandle kweqiniso lokuthi le ndlela ayilindelekile futhi ayichemile, inenzuzo eyengeziwe yokuba nokwenzeka uma okungenani ababambiqhaza ababili betholakala kunethiwekhi (kucatshangwa ukuthi iphrothokholi yokuvumelana esetshenziswayo iyasebenza uma kubhekwana nenani elincane kangaka labahlanganyeli).

Inselele enkulu yale ndlela ukumisa i-VDF kangangokuthi ngisho nomuntu obambe iqhaza onezingxenyekazi zekhompyutha ezikhethekile ezibiza kakhulu ngeke akwazi ukubala i-VDF ngaphambi kokuphela kwesigaba sokutholwa. Ngokufanelekile, i-algorithm kufanele ibe nemajini yokuphepha ebalulekile, ithi 10x. Isibalo esingezansi sibonisa ukuhlasela komlingisi one-ASIC ekhethekile emvumela ukuthi aqhube i-VDF ngokushesha kunesikhathi esibekelwe ukuveza isiqinisekiso se-RANDAO. Umhlanganyeli onjalo usengakwazi ukubala umphumela wokugcina esebenzisa noma engasebenzisi inombolo yakhe, bese, ngokusekelwe esibalweni, akhethe ukuthi uyayibonisa noma cha.

Emndenini we-VDF okukhulunywe ngawo ngenhla, ukusebenza kwe-ASIC ezinikele kungaba ngaphezu kwezikhathi eziyi-100+ kunehardware evamile. Ngakho-ke uma isigaba sokuphakelwa sithatha imizuzwana eyi-10, i-VDF ebalwa ku-ASIC enjalo kufanele ithathe ngaphezu kwamasekhondi ayi-100 ukuze ibe nemajini yokuphepha eyi-10x, futhi ngaleyo ndlela i-VDF efanayo ebalwa ku-hardware yempahla kufanele ithathe imizuzwana engu-100x 100 = ~ amahora angu-3.

I-Ethereum Foundation ihlela ukuxazulula le nkinga ngokudala eyayo etholakala esidlangalaleni, ama-ASIC amahhala. Uma lokhu sekwenzekile, zonke ezinye izivumelwano nazo zingasebenzisa lobu buchwepheshe, kodwa kuze kube yileso sikhathi indlela ye-RANDAO+VDF ngeke isebenze njengezivumelwano ezingakwazi ukutshala imali ekuthuthukiseni ama-ASIC azo.

Izindatshana eziningi, amavidiyo kanye nolunye ulwazi mayelana ne-VDF kuqoqwe kuyo le sayithi.

Sisebenzisa amakhodi okusula

Kulesi sigaba, sizobheka iphrothokholi yokukhiqiza inombolo engahleliwe esebenzisa ukusula amakhodi. Ingakwazi ukubekezelela abahlaseli abafika ku-⅓ ngenkathi ihlala isebenza, futhi ivumele abahlaseli abangafika ku-⅔ ukuthi babe khona ngaphambi kokubikezela noma ukuthonya umphumela.

Umqondo oyinhloko wephrothokholi umi kanje. Ukwenza kube lula, ake sicabange ukuthi kunabahlanganyeli abayi-100 ncamashi. Masiphinde sicabange ukuthi bonke abahlanganyeli endaweni banokhiye othile oyimfihlo, futhi okhiye basesidlangalaleni babo bonke ababambiqhaza baziwa yibo bonke ababambiqhaza:

1. Umhlanganyeli ngamunye endaweni uqhamuka nentambo ende, ayihlephule ibe izingxenye ezingama-67, enze amakhodi okusula ukuze athole amasheya ayi-100 ngendlela yokuthi noma yimaphi angu-67 anele ukubuyisela uchungechunge, abele ingxenye ngayinye kweziyi-100 komunye wabahlanganyeli, futhi abhale ngemfihlo ngokuthi ukhiye osesidlangalaleni womhlanganyeli ofanayo. Konke ukwabelana okubhalwe ngekhodi kube sekushicilelwe.

2. Abahlanganyeli basebenzisa uhlobo oluthile lokuvumelana ukuze bafinyelele esivumelwaneni ngamasethi anekhodi avela kubahlanganyeli abathile abangama-67.

3. Uma kufinyelelwe esivumelwaneni, umhlanganyeli ngamunye uthatha amasheya afakwe ikhodi kusethi ngayinye kwangu-67 abethelwe ngokhiye wabo osesidlangalaleni, asuse ukubethela konke lokho kwabelana, futhi ashicilele wonke amasheya anjalo asusiwe.

4. Uma ababambiqhaza abangama-67 sebeqedile isinyathelo (3), wonke amasethi okuvunyelwene ngawo angaqoshwa ngokuphelele futhi akhiwe kabusha ngenxa yezakhiwo zamakhodi okusula, futhi inombolo yokugcina ingatholwa njenge-XOR yemigqa yokuqala ababambiqhaza abaqale ngayo (1) .

Le phrothokholi ingaboniswa ingachemi futhi ayibikezeli. Inombolo engahleliwe ewumphumela inqunywa ngemva kokuba kufinyelelwe esivumelwaneni, kodwa akwaziwa yinoma ubani kuze kube ⅔ babahlanganyeli bekhipha ikhodi izingxenye ezibethelwe ngokhiye wabo womphakathi. Ngakho, inombolo engahleliwe inqunywa ngaphambi kokuba ulwazi olwanele lokuyakha kabusha lushicilelwe.

Kwenzekani uma esinyathelweni (1) omunye wabahlanganyeli ethumele amasheya afakwe ikhodi kwabanye ababambi qhaza okungeyona ikhodi elungile yokusula yeyunithi yezinhlamvu? Ngaphandle kwezinguquko ezengeziwe, ababambiqhaza abahlukene ngeke bakwazi nhlobo ukubuyisela iyunithi yezinhlamvu, noma bazophinde babuyisele iyunithi yezinhlamvu ehlukile, okuzoholela ekutheni ababambiqhaza abahlukene bathole inombolo engahleliwe ehlukile. Ukuvimbela lokhu, ungenza lokhu okulandelayo: umhlanganyeli ngamunye, ngaphezu kwamasheya afakwe ikhodi, futhi ubala. Merkla umuthi wonke amasheya anjalo, futhi ithumela umhlanganyeli ngamunye kokubili isabelo esifakwe ikhodi ngokwaso kanye nempande yesihlahla se-merkle, kanye nobufakazi bokufakwa kwesabelo esihlahleni se-merkle. Ekuvumelaneni esinyathelweni (2), ababambiqhaza abavumelani nje ngeqoqo lamasethi, kodwa kusethi yezimpande ezithile zezihlahla ezinjalo (uma omunye wabahlanganyeli ephambukile esivumelwaneni, futhi wathumela izimpande zesihlahla se-merkle ezihlukene kubahlanganyeli abahlukene, futhi izimpande ezimbili ezinjalo ziboniswa ngesikhathi sokuvumelana, umugqa wakhe awufakiwe kusethi yomphumela). Njengomphumela wokuvumelana, sizoba nemigqa ekhodiwe engu-67 kanye nezimpande ezihambisanayo zesihlahla se-merkle kangangokuthi okungenani kube nabahlanganyeli abangu-67 (hhayi ngempela abafana abahlongoze imigqa ehambisanayo), okuthi ngomugqa ngamunye kwengama-67 umlayezo onengxenye yekhodi yokusula, kanye nobufakazi bokuthi ukwenzeka kwesabelo sabo esihlahleni esihambisanayo kwafiphala.

Uma esinyathelweni (4) umhlanganyeli echaza amabhithi angu-67 eyunithi yezinhlamvu ethile futhi ezama ukwakha kabusha iyunithi yezinhlamvu yoqobo esuka kuzo, enye yezinketho ingenzeka:

1. Iyunithi yezinhlamvu iyabuyiselwa, futhi uma ngabe isula-encoded futhi, futhi isihlahla se-Merkle sibalwa kumasheya abalwe endaweni, impande iqondana naleyo okufinyelelwe kuyo ukuvumelana.

2. Umugqa ubuyiselwe, kodwa impande ebalwe endaweni ayifani naleyo okufinyelelwe kuyo ukuvumelana.

3. Umugqa awubuyiselwe.

Kulula ukukhombisa ukuthi uma inketho (1) yenzeke okungenani kumhlanganyeli oyedwa ngenhla, khona-ke inketho (1) yenzeke kubo bonke ababambiqhaza, futhi okuphambene nalokho, uma inketho (2) noma (3) yenzeke okungenani kumhlanganyeli oyedwa, khona-ke. kubo bonke ababambiqhaza inketho (2) noma (3) izokwenzeka. Ngakho-ke, kumugqa ngamunye kusethi, kungenzeka ukuthi bonke ababambiqhaza bazowuthola ngempumelelo, noma bonke ababambiqhaza bazohluleka ukuwuthola. Inombolo engahleliwe ewumphumela iba yi-XOR yemigqa kuphela ababambiqhaza abakwazi ukuyibuyisela.

Amasignesha e-Threshold

Enye indlela yokwenza okungahleliwe ukusebenzisa lokho okubizwa ngokuthi amasignesha e-BLS threshold. Ijeneretha yenombolo engahleliwe esekelwe kumasiginesha emngceleni ineziqinisekiso ezifanayo ncamashi ne-algorithm esekelwe kukhodi yokusula echazwe ngenhla, kodwa inenombolo ephansi kakhulu ye-asymptotic ephansi kakhulu ethunyelwa ngenethiwekhi yenombolo ngayinye ekhiqiziwe.

Amasiginesha e-BLS awumklamo ovumela ababambiqhaza abaningi ukuthi bakhe isiginesha eyodwa evamile yomlayezo. Lezi ziginesha zivame ukusetshenziselwa ukonga isikhala nomkhawulokudonsa ngokungadingi ukuthi kuthunyelwe amasignesha amaningi. 

Isicelo esivamile samasiginesha e-BLS kumaphrothokholi e-blockchain, ngaphezu kokukhiqiza izinombolo ezingahleliwe, ukuvinjwa kokusayina kumaphrothokholi e-BFT. Ake sithi ababambiqhaza abayi-100 bakha amabhulokhi, futhi ibhulokhi ithathwa njengokugcina uma abangu-67 babo besayina. Bonke bangahambisa izingxenye zabo zesiginesha ye-BLS futhi basebenzise i-algorithm ethile yokuvumelana ukuze bavumelane ngama-67 wabo bese bewahlanganisa abe isiginesha eyodwa ye-BLS. Noma yiziphi izingxenye ezingama-67 (noma ngaphezulu) zingasetshenziselwa ukudala isiginesha yokugcina, okuzoncika ekutheni yiziphi izisayindo ezingama-67 ezihlanganiswe ngakho-ke zingahluka, nakuba ukukhetha okuhlukile kwabahlanganyeli abangu-67 kuzodala isiginesha ehlukile , noma iyiphi isignesha enjalo iyoba evumelekile. isignesha yebhulokhi. Abahlanganyeli abasele badinga kuphela ukuthola nokuqinisekisa isignesha eyodwa kuphela vimba, esikhundleni se-67, phezu kwenethiwekhi, okunciphisa kakhulu umthwalo kunethiwekhi.

Kuvela ukuthi uma okhiye abayimfihlo abasetshenziswa abahlanganyeli benziwa ngendlela ethile, ngakho-ke kungakhathaliseki ukuthi yimaphi amasiginesha angu-67 (noma ngaphezulu, kodwa hhayi ngaphansi) ahlanganisiwe, isiginesha ewumphumela izofana. Lokhu kungasetshenziswa njengomthombo wokungahleliwe: ababambiqhaza baqale bavumelane ngomyalezo othile abazowusayina (lokhu kungaba ukukhishwa kwe-RANDAO noma i-hashi yebhulokhi yokugcina, akunandaba ngempela inqobo nje uma ishintsha njalo futhi iyaguquguquka) bese udale isiginesha ye-BLS yayo. Umphumela wesizukulwane uzobe ungalindelekile kuze kube yilapho abahlanganyeli be-67 behlinzeka ngezingxenye zabo, futhi ngemva kwalokho okukhiphayo sekuvele kunqunywe kusengaphambili futhi akukwazi ukuncika ezenzweni zanoma yimuphi umhlanganyeli.

Le ndlela yokwenza okungahleliwe iyasebenza inqobo nje uma okungenani ⅔ wabahlanganyeli abaku-inthanethi bobabili belandela umthetho olandelwayo, futhi ayichemi futhi ayibikezeli inqobo nje uma okungenani u-⅓ wabahlanganyeli belandela umthetho olandelwayo. Kubalulekile ukuqaphela ukuthi umhlaseli olawula ngaphezu kuka-⅓ kodwa abangaphansi kuka-⅔ babahlanganyeli angakwazi ukumisa iphrothokholi, kodwa akakwazi ukubikezela noma ukuthonya ukuphuma kwayo.

Ama-Threshold signatures ngokwawo ayisihloko esijabulisa kakhulu. Engxenyeni yesibili ye-athikili, sizohlaziya ngokuningiliziwe ukuthi zisebenza kanjani, nokuthi kudingekile kangakanani ukukhiqiza okhiye ababambiqhaza ukuze amasignesha e-threshold asetshenziswe njengejeneretha yenombolo engahleliwe.

Ekuphethweni

Lesi sihloko singesokuqala ochungechungeni lwezihloko zebhulogi yezobuchwepheshe CISHE. I-NEAR iphrothokholi ye-blockchain kanye nenkundla yokuthuthukisa izinhlelo zokusebenza ezihlukaniselwe izindawo ngokugcizelela ekuthuthukisweni okulula kanye nokusebenziseka kalula kubasebenzisi bokugcina.

Ikhodi yephrothokholi ivuliwe, ukuqaliswa kwethu kubhalwe ku-Rust, ingatholakala lapha.

Ungabona ukuthi intuthuko ye-NEAR ibukeka kanjani futhi uzame ku-IDE eku-inthanethi lapha.

Ungakwazi ukulandela zonke izindaba in Russian at iqembu le-telegram futhi ku iqembu ku-VKontakte, nangesiNgisi esemthethweni twitter.

Sizobonana maduze!

Source: www.habr.com