Shin zai yiwu a samar da lambobi bazuwar idan ba mu amince da juna ba? Kashi na 1

Hai Habr!

A cikin wannan labarin zan yi magana game da ƙarni na pseudo-random lambobin da mahalarta waɗanda ba su amince da juna. Kamar yadda za mu gani a kasa, aiwatar da "kusan" kyakkyawan janareta abu ne mai sauƙi, amma mai kyau yana da wahala.

Me yasa ya zama dole a samar da lambobi bazuwar tsakanin mahalarta waɗanda ba su amince da juna ba? Ɗayan yankin aikace-aikace shine ƙaddamar da aikace-aikace. Misali, aikace-aikacen da ke karɓar fare daga ɗan takara kuma ko dai ya ninka adadin tare da yuwuwar 49% ko kuma ya ɗauke da yuwuwar 51% zai yi aiki ne kawai idan zai iya karɓar lambar bazuwar ba tare da son zuciya ba. Idan maharin zai iya yin tasiri ga sakamakon janareta na lambar bazuwar, har ma da ɗan ƙara damar samun kuɗi a cikin aikace-aikacen, zai lalata shi cikin sauƙi.

Lokacin da muka tsara ƙa'idar tsara lambar bazuwar rarraba, muna son ta sami kaddarori uku:

1. Dole ne ya kasance mara son zuciya. A wasu kalmomi, babu wani ɗan takara da ya kamata ta kowace hanya ya yi tasiri a sakamakon janareta na lambar bazuwar.

2. Dole ne ya kasance mara tabbas. A takaice dai, babu wani ɗan takara da zai iya yin hasashen adadin adadin da za a ƙirƙira (ko in faɗi duk wani kaddarorinsa) kafin a samar da shi.

3. Dole ne ƙa'idar ta kasance mai ƙarfi, wato, mai juriya ga gaskiyar cewa wasu kaso na mahalarta sun katse haɗin yanar gizo ko kuma da gangan suka yi ƙoƙarin dakatar da yarjejeniya.

A cikin wannan labarin za mu dubi hanyoyi guda biyu: RNDAO + VDF da tsarin lambobi masu gogewa. A kashi na gaba, za mu bincika dalla-dalla yadda ake bi bisa sa hannun bakin kofa.

Amma da farko, bari mu kalli algorithm mai sauƙi kuma wanda aka saba amfani da shi wanda yake da yuwuwa, wanda ba shi da tabbas, amma mai son zuciya.

RNDAO

RNDAO hanya ce mai sauqi qwarai don haka ana amfani da ita sosai wajen haifar da bazuwar. Duk mahalarta cibiyar sadarwa sun fara zaɓar lambar ƙirƙira, sannan kowane ɗan takara ya aika da zanta na lambar da aka zaɓa. Bayan haka, mahalarta suna bi da bi suna bayyana lambobin da suka zaɓa tare da yin aikin XOR akan lambobin da aka bayyana, kuma sakamakon wannan aiki ya zama sakamakon ƙa'idar.

Matakin buga hashes kafin bayyana lambobin ya zama dole ta yadda maharin ba zai iya zabar lambarsa ba bayan ya ga lambobin sauran mahalarta. Wannan zai ba shi damar kusan da hannu guda ya tantance fitar da janareta na lambar bazuwar.

A yayin aiwatar da yarjejeniya, mahalarta suna buƙatar yanke shawara na gama gari (wanda ake kira yarjejeniya) sau biyu: lokacin da za a fara bayyana lambobin da aka zaɓa, don haka dakatar da karɓar hashes, da lokacin daina karɓar lambobin da aka zaɓa da ƙididdige sakamakon bazuwar. lamba. Yin irin wannan yanke shawara tsakanin mahalarta waɗanda ba su amince da juna ba abu ne mai sauƙi a kansa ba, kuma za mu koma gare shi a cikin labaran da ke gaba; a cikin wannan labarin za mu ɗauka cewa irin wannan algorithm na yarjejeniya yana samuwa a gare mu.

Wanne daga cikin kadarorin da muka bayyana a sama RNDAO ke da shi? Ba shi da tabbas, yana da kuzari iri ɗaya da ƙa'idar yarjejeniya ta asali, amma tana da son zuciya. Musamman, maharin zai iya lura da hanyar sadarwar, kuma bayan sauran mahalarta sun bayyana lambobin su, zai iya ƙididdige XOR ɗin su, kuma ya yanke shawarar ko zai bayyana lambarsa ko a'a don tasiri sakamakon. Duk da yake wannan yana hana maharin yin ƙayyadaddun kayan aikin janareta na lambar bazuwar da hannu ɗaya, har yanzu yana ba shi 1 bit na tasiri. Kuma idan maharan sun mallaki mahalarta da yawa, to adadin raƙuman da suke sarrafawa zai yi daidai da adadin mahalarta da ke ƙarƙashin ikonsu.

Ana iya rage tasirin maharan sosai ta hanyar buƙatar mahalarta su bayyana lambobin cikin tsari. Sa'an nan kuma maharin zai iya rinjayar sakamakon kawai idan an bude shi a karshe. Duk da yake tasirin ya ragu sosai, algorithm har yanzu yana da son zuciya.

RNDAO+VDF

Hanya daya da za a mayar da RNDAO ba ta da son zuciya ita ce: bayan an bayyana dukkan lambobi kuma an lissafta XOR, za a shigar da sakamakonsa a cikin shigar da wani aiki, wanda ke daukar lokaci mai tsawo kafin a kirga, amma yana ba ka damar duba daidaicin aikin. lissafi da sauri.

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

Ana kiran wannan aikin Verifiable Delay Function, ko VDF. Idan ƙididdige sakamakon ƙarshe ya ɗauki tsawon lokaci fiye da matakin bayyana lambar, to maharin ba zai iya yin hasashen tasirin nunawa ko ɓoye lambarsa ba, don haka zai rasa damar yin tasiri ga sakamakon.

Haɓaka kyawawan VDFs yana da matuƙar wahala. An sami ci gaba da yawa kwanan nan, misali. wannan и wannan, wanda ya sa VDF ya fi dacewa a aikace, kuma Ethereum 2.0 yana shirin amfani da RNDAO tare da VDF a matsayin tushen lambar bazuwar a cikin dogon lokaci. Baya ga gaskiyar cewa wannan hanyar ba ta da tsinkaya kuma ba ta da son zuciya, tana da ƙarin fa'ida ta kasancewa mai yuwuwa idan aƙalla mahalarta biyu suna samuwa akan hanyar sadarwar (idan an yi la'akari da ƙa'idar yarjejeniya da aka yi amfani da ita a yayin da ake mu'amala da ƙananan adadin mahalarta).

Babban ƙalubale na wannan hanya shine kafa VDF kamar yadda ko da ɗan takara da kayan masarufi na musamman masu tsada ba zai iya lissafin VDF ba kafin ƙarshen lokacin ganowa. Mahimmanci, algorithm ya kamata ma yana da babban gefen aminci, in ji 10x. Hoton da ke ƙasa yana nuna harin da wani ɗan wasan kwaikwayo wanda ke da ASIC na musamman wanda ke ba shi damar gudanar da VDF da sauri fiye da lokacin da aka ware don bayyana tabbacin RNDAO. Irin wannan ɗan takara har yanzu yana iya ƙididdige sakamakon ƙarshe ta amfani da lambarsa ko a'a, sannan, bisa lissafin, zaɓi ko ya nuna ko a'a.

Ga dangin VDF da aka ambata a sama, aikin ASIC da aka keɓe zai iya zama sau 100+ sama da na'ura na al'ada. Don haka idan lokacin ƙaddamarwa ya ɗauki daƙiƙa 10, to, VDF ɗin da aka lissafta akan irin wannan ASIC dole ne ya ɗauki fiye da daƙiƙa 100 don samun gefen aminci na 10x, don haka VDF ɗin da aka lissafta akan kayan masarufi dole ne ya ɗauki 100x 100 seconds = ~ 3 hours.

Gidauniyar Ethereum tana shirin magance wannan matsala ta hanyar ƙirƙirar nata na jama'a, ASICs kyauta. Da zarar wannan ya faru, duk sauran ka'idoji kuma za su iya cin gajiyar wannan fasaha, amma har sai lokacin tsarin RNDAO+VDF ba zai zama mai amfani ga ka'idojin da ba za su iya saka hannun jari don haɓaka nasu ASICs ba.

An tattara labarai da yawa, bidiyoyi da sauran bayanai game da VDF akan su wannan shafin.

Muna amfani da lambobin gogewa

A cikin wannan sashe, za mu dubi ƙa'idar tsara lambar bazuwar da ke amfani da ita goge lambobin. Yana iya jurewa har zuwa ⅓ maharan yayin da suke ci gaba da wanzuwa, kuma yana ba da damar har zuwa ⅔ maharan su wanzu kafin su iya hasashen ko tasiri sakamakon.

Babban ra'ayi na yarjejeniya shine kamar haka. Don sauƙi, bari mu ɗauka cewa akwai daidaitattun mahalarta 100. Bari mu kuma ɗauka cewa duk mahalarta a gida suna da wasu maɓalli na sirri, kuma maɓallan jama'a na duk mahalarta an san su ga duk mahalarta:

1. Kowane ɗan takara a cikin gida ya zo da dogon kirtani, ya karya shi zuwa sassa 67, ya ƙirƙiri lambobin gogewa don samun hannun jari 100 wanda kowane 67 ya isa ya dawo da kirtani, ya ba kowane ɗayan hannun jari 100 ga ɗaya daga cikin mahalarta, sannan ya rufa musu asiri da su. mabuɗin jama'a na mahalarta ɗaya. Ana buga duk rufaffiyar hannun jari.

2. Mahalarta suna amfani da wani nau'i na ijma'i don cimma yarjejeniya kan saiti daga takamaiman mahalarta 67.

3. Da zarar an cimma matsaya, kowane ɗan takara ya ɗauki rufaffen hannun jari a cikin kowane saiti 67 da aka rufaffen rufaffen maɓalli na jama'a, yana ɓoye duk irin waɗannan hannun jari, kuma yana buga duk irin waɗannan hannun jarin da aka ɓoye.

4. Da zarar mahalarta 67 sun kammala mataki (3), duk saitin da aka amince da shi za a iya canza su gaba ɗaya kuma a sake gina su saboda kaddarorin lambobin gogewa, kuma ana iya samun lambar ƙarshe azaman XOR na layuka na farko waɗanda mahalarta suka fara da su a cikin (1) .

Ana iya nuna wannan ƙa'idar ba ta da son zuciya kuma ba ta da tabbas. Ana ƙayyade lambar bazuwar sakamakon bayan an cimma yarjejeniya, amma kowa bai san shi ba har sai ⅔ na mahalarta sun yanke ɓoyayyen ɓoyayyen ɓoyayyen ɓoyayyen maɓalli na jama'a. Don haka, ana ƙididdige lambar bazuwar kafin a buga bayanin da ya isa sake gina shi.

Me zai faru idan a mataki (1) ɗaya daga cikin mahalarta ya aika da rufaffiyar hannun jari ga sauran mahalarta waɗanda ba daidai ba ne lambar gogewa na wasu kirtani? Idan ba tare da ƙarin canje-canje ba, mahalarta daban-daban ba za su iya ko dai ba za su iya dawo da igiyar kwata-kwata ba, ko kuma za su dawo da igiyoyi daban-daban, wanda zai haifar da mahalarta daban-daban suna karɓar lambar bazuwar daban. Don hana wannan, zaku iya yin waɗannan abubuwa masu zuwa: kowane ɗan takara, ban da hannun jarin da aka sanya, shima yana ƙididdigewa. Itacen Merkla duk irin wannan hannun jari, kuma yana aika kowane ɗan takara duka biyun da aka ɓoye rabon kansa da tushen bishiyar merkle, da tabbacin haɗa rabon a cikin bishiyar merkle. A cikin ijma'i a mataki na (2), mahalarta to ba kawai yarda a kan wani sa na sets, amma a kan wani sa na takamaiman tushen irin bishiyoyi (idan wasu mahalarta sun kauce daga yarjejeniya, kuma aika daban-daban merkle itace tushen ga daban-daban mahalarta. kuma ana nuna tushen guda biyu a lokacin yarjejeniya, ba a haɗa layinsa a cikin sakamakon sakamakon). A sakamakon yarjejeniya, za mu sami 67 encoded Lines da kuma daidai tushen bishiyar merkle kamar yadda akwai a kalla 67 mahalarta (ba dole ba ne daya wadanda suka gabatar da m Lines), wanda ga kowane daga cikin 67 Lines. sakon da ke da rabon lambar gogewa, da kuma tabbacin faruwar rabonsu a cikin bishiyar da ta dace ta dushe.

Lokacin cikin mataki (4) ɗan takara ya yanke 67 ya buga ga wani kirtani kuma yayi ƙoƙarin sake gina asalin kirtani daga gare su, ɗayan zaɓuɓɓukan yana yiwuwa:

1. An dawo da kirtani, kuma idan an sake sharewa, kuma aka ƙididdige bishiyar Merkle don hannun jarin da aka ƙididdige su, tushen ya zo daidai da wanda aka cimma yarjejeniya akai.

2. An dawo da layin, amma tushen da aka ƙididdige shi bai dace da wanda aka cimma yarjejeniya ba.

3. Ba a maido da layin ba.

Yana da sauƙi a nuna cewa idan zaɓi (1) ya faru ga aƙalla ɗan takara ɗaya a sama, to zaɓi (1) ya faru ga duk mahalarta, kuma akasin haka, idan zaɓi (2) ko (3) ya faru ga aƙalla ɗan takara ɗaya, to. don duk zaɓin mahalarta (2) ko (3) zai faru. Don haka, ga kowane layi a cikin saitin, ko dai duk mahalarta zasu sami nasarar dawo da shi, ko kuma duk mahalarta zasu kasa dawo da shi. Sakamakon lambar bazuwar shine XOR na layuka kawai waɗanda mahalarta suka iya murmurewa.

Sa hannun bakin kofa

Wata hanyar zuwa ga bazuwar ita ce amfani da abin da ake kira sa hannun ƙofar BLS. Generator na lamba bazuwar bisa sa hannu na bakin kofa yana da ainihin garanti iri ɗaya kamar na tushen lambar gogewa da aka kwatanta a sama, amma yana da ƙarancin adadin saƙonnin asymptotic da aka aika akan hanyar sadarwa don kowace lamba da aka ƙirƙira.

Sa hannu na BLS ƙira ce da ke ba da damar mahalarta da yawa su ƙirƙiri sa hannun gama gari ɗaya don saƙo. Ana amfani da waɗannan sa hannu sau da yawa don adana sarari da bandwidth ta hanyar rashin buƙatar sa hannu da yawa don aika. 

Aikace-aikacen gama gari don sa hannun BLS a cikin ka'idojin blockchain, ban da samar da lambobi bazuwar, shine toshe sa hannu a cikin ka'idojin BFT. Bari mu ce mahalarta 100 sun ƙirƙiri tubalan, kuma ana ɗaukar toshe a ƙarshe idan 67 daga cikinsu suka sanya hannu. Duk za su iya ƙaddamar da sassansu na sa hannun BLS kuma su yi amfani da wasu algorithm yarjejeniya don amincewa da 67 daga cikinsu sannan su haɗa su cikin sa hannun BLS ɗaya. Ana iya amfani da kowane 67 (ko fiye) sassa don ƙirƙirar sa hannu na ƙarshe, wanda zai dogara da abin da aka haɗa sa hannu 67 kuma sabili da haka na iya bambanta, kodayake zaɓuɓɓuka daban-daban ta mahalarta 67 za su haifar da sa hannu daban-daban , duk irin wannan sa hannu zai zama mai inganci. sa hannu don toshe. Sauran mahalarta sai kawai suna buƙatar karɓa da kuma tabbatar da sa hannu ɗaya kawai a kowace toshe, maimakon 67, akan hanyar sadarwar, wanda ke rage nauyi a kan hanyar sadarwa.

Ya bayyana cewa idan maɓallai masu zaman kansu waɗanda mahalarta ke amfani da su an ƙirƙira su ta wata hanya, to, komai sa hannu 67 (ko fiye, amma ba ƙasa ba) an haɗa su, sa hannun da aka samu zai kasance iri ɗaya. Ana iya amfani da wannan azaman tushen bazuwar: mahalarta sun fara yarda akan wasu saƙon da za su sa hannu (wannan na iya zama fitowar RNDAO ko kawai zanta na toshe na ƙarshe, ba lallai bane ya zama mahimmanci idan dai yana canzawa kowane lokaci. kuma yana da daidaito) kuma ƙirƙirar sa hannun BLS don shi. Sakamakon tsararrakin ba zai zama wanda ba a iya faɗi ba har sai mahalarta 67 sun ba da sassan su, kuma bayan haka an riga an ƙaddara fitarwa kuma ba zai iya dogara da ayyukan kowane ɗan takara ba.

Wannan hanyar bazuwar tana da amfani muddin aƙalla ⅔ na mahalarta kan layi duk sun bi ƙa'idar, kuma ba ta da son zuciya kuma ba za a iya faɗi ba muddin aƙalla ⅓ na mahalarta sun bi ƙa'idar. Yana da mahimmanci a lura cewa maharin da ke sarrafa fiye da ⅓ amma ƙasa da ⅔ na mahalarta zai iya dakatar da ƙa'idar, amma ba zai iya tsinkaya ko yin tasiri ga fitowar ta ba.

Sa hannun bakin kofa su kansu batu ne mai ban sha'awa. A kashi na biyu na labarin, za mu yi nazari dalla-dalla yadda suke aiki, da kuma yadda ya wajaba don samar da maɓallai masu shiga ta yadda za a iya amfani da sa hannun bakin kofa azaman janareta na bazuwar lamba.

A ƙarshe

Wannan labarin shine na farko a cikin jerin labaran fasahar fasaha KYAU. NEAR ƙa'idar blockchain ce da dandamali don haɓaka aikace-aikacen da ba a daidaita su tare da mai da hankali kan sauƙin haɓakawa da sauƙin amfani ga masu amfani da ƙarshe.

Lambar ka'ida tana buɗe, an rubuta aiwatar da mu a cikin Rust, ana iya samun shi a nan.

Kuna iya ganin yadda ci gaban NEAR yayi kama da gwaji a cikin IDE na kan layi a nan.

Kuna iya bin duk labarai cikin Rashanci a group telegram da kuma cikin kungiyar VKontakte, kuma a cikin Ingilishi a cikin hukuma twitter.

Sai anjima!

source: www.habr.com