Ka taea te whakaputa tau matapōkere ki te kore tatou e whakawhirinaki tetahi ki tetahi? Wāhanga 1

Hei Habr!

I roto i tenei tuhinga ka korero ahau mo te whakatipuranga o nga nama pseudo-tupurangi a nga kaiuru kaore e whakawhirinaki tetahi ki tetahi. Ka kite tatou i raro nei, he tino ngawari te whakatinana i te "tata" pai, engari he uaua te mea tino pai.

He aha i tika ai te whakaputa i nga tau matapōkere i waenga i nga kaiuru karekau e whakawhirinaki tetahi ki tetahi? Ko tetahi waahanga tono ko nga tono kua wehea. Hei tauira, ko te tono e whakaae ana ki te peti mai i tetahi kaiuru me te whakarua i te moni me te 49% te tupono, te tango ranei me te 51% te tupono ka mahi noa mena ka taea e ia te whiwhi i tetahi nama matapōkere. Mena ka taea e te kaitukino te awe i te huanga o te kaihanga tau matapōkere, me te whakanui ake i te tupono ki te whiwhi utu i roto i te tono, ka ngawari te whakangaro i a ia.

Ina hoahoatia he kawa whakangao tau matapōkere kua tohatohahia, ka hiahia kia toru nga ahuatanga:

1. E tika ana kia kore e whai whakaaro. Arā, kia kaua rawa te kaiuru e whakaawe i te hua o te kaihanga tau matapōkere.

2. Me noho ohorere ia. Arā, kia kaua e taea e te kaiuru te matapae he aha te tau ka puta (ka whakatauhia ranei etahi o ana taonga) i mua i te whakaputanga.

3. Me whai oranga te kawa, ara, te aukati i te ahua o etahi paheketanga o nga kaiuru ka momotu mai i te whatunga, ka ngana ranei ki te aukati i te kawa.

I roto i tenei tuhinga ka titiro tatou ki nga huarahi e rua: RANDAO + VDF me nga tikanga whakakore. I te waahanga e whai ake nei, ka tirotirohia e tatou te huarahi i runga i nga hainatanga paepae.

Engari ko te tuatahi, me titiro tatou ki tetahi algorithm ngawari me te whakamahia noa e kaha ana, e kore e taea te matapae, engari he pai.

RANDAO

Ko te RANDAO he huarahi tino ngawari, na reira ka whakamahia noa ki te whakaputa matapōkeretia. Ko nga kaiuru whatunga katoa i te tuatahi ka kowhiri i tetahi tau pseudorandom, katahi ka tukuna e ia kaiuru he hash o te tau kua tohua. Whai muri, ka huri haere nga kaiuru ki te whakaatu i a ratou tau i whiriwhiria me te mahi XOR i runga i nga tau kua kitea, a ko te hua o tenei mahi ko te hua o te kawa.

Ko te taahiraa o te whakaputa i nga tohu i mua i te whakaatu i nga nama e tika ana kia kore ai e taea e te kaitukino te whiriwhiri i tana nama i muri i tana kitenga i nga nama o era atu kaiuru. Ma tenei ka taea e ia te whakatau i te putanga o te kaihanga tau matapōkere.

I te wa o te kawa, me tae mai nga kaiuru ki te whakatau noa (e kiia nei ko te whakaaetanga) kia rua nga wa: ka timata te whakaatu i nga tau kua tohua, na reira ka mutu te whakaae ki nga tohu, me te wa ka mutu te whakaae ki nga tau kua tohua me te tatau i te hua matapōkere. tau. Ko te whakatau i enei whakatau i waenga i nga kaiuru kaore i te whakawhirinaki tetahi ki tetahi ehara i te mahi ngawari, a ka hoki ano tatou ki nga tuhinga a muri ake nei; i roto i tenei tuhinga ka kii tatou kei te waatea mai taua algorithm ki a tatou.

Ko wai o nga taonga i whakaahuatia i runga ake nei kei a RANDAO? Kare e taea te matapae, he rite tonu te kaha ki te kawa whakaae o raro, engari he rītaha. Inaa, ka taea e te kaitukino te mataki i te whatunga, a, i muri i te whakaatu a etahi atu kaiuru i o raatau nama, ka taea e ia te tatau i a raatau XOR, me te whakatau mena ka whakaatu mai ranei i tana nama hei awe i te putanga. Ahakoa e aukati ana tenei i te kaitukino ki te whakatau takitahi i te putanga o te kaihanga tau matapōkere, ka hoatu tonu ki a ia kia 1 te awe. A, ki te whakahaerea e nga kaiwhaiwhai he maha nga kaiuru, ka rite te maha o nga moka ka whakahaerea e ratou ki te maha o nga kaiuru kei raro i o raatau mana whakahaere.

Ka tino whakaitihia te awe o te hunga whakaeke ma te tono kia whakaatu nga kaiuru i nga nama kia raupapa. Na ka taea e te kaitukino te whakaawe i te putanga mena ka whakatuwherahia te mutunga. Ahakoa he iti rawa te awe, he rītaha tonu te algorithm.

RANDAO+VDF

Ko tetahi o nga huarahi e kore ai e taurite a RANDAO ko tenei: i muri i te whakaaturanga o nga tau katoa me te tatau i te XOR, ka tukuna tona hua ki roto i te whakaurunga o tetahi mahi, he roa rawa te waa ki te tatau, engari ka taea e koe te tirotiro i te tika o te tere rawa te tatauranga.

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

Ko tenei mahi ka kiia ko te Mahi Whakaroa Manatoko, ko VDF ranei. Mēnā he roa ake te tātai i te hua whakamutunga i te wā whakaatu tau, karekau e taea e te kaitukino te matapae i te hua o te whakaatu, huna ranei i tana nama, na reira ka ngaro te whai waahi ki te whakaawe i te hua.

He tino uaua te whakawhanake i nga VDF pai. He maha nga waahanga kua puta tata nei, hei tauira. tenei и tenei, i pai ake ai te mahi a te VDF i roto i nga mahi, me te whakamahere a Ethereum 2.0 ki te whakamahi i te RANDAO me te VDF hei puna nama matapōkere i te wa roa. I tua atu i te mea ko tenei huarahi kaore e taea te whakaaro me te kore whakaaro, he painga taapiri mo te kaha ki te mea e rua nga kaiuru e waatea ana i runga i te whatunga (mehemea ka taea te kawa whakaaro i whakamahia i te wa e pa ana ki te iti o nga kaiuru).

Ko te wero nui rawa atu o tenei huarahi ko te whakatu i te VDF kia kore ai e taea e te kaiuru he taputapu motuhake te utu nui te tatau i te VDF i mua i te mutunga o te wahanga kitenga. Ko te tikanga, me whai waahi haumaru nui te algorithm, me kii 10x. Ko te ahua i raro nei e whakaatu ana i te whakaeke a tetahi kaiwhakaari he ASIC motuhake e taea ai e ia te whakahaere i te VDF tere atu i te wa i whakaritea hei whakaatu i te whakapumautanga RANDAO. Ka taea tonu e taua kaiuru te tatau i te hua whakamutunga ma te whakamahi, kaore ranei i te whakamahi i tana nama, katahi, i runga i te tatauranga, whiriwhiri me whakaatu, kaore ranei.

Mo te whanau VDF kua whakahuahia i runga ake nei, ko te mahinga o te ASIC whakatapua ka 100+ nga wa teitei ake i nga taputapu tikanga. Na, ki te 10 hēkona te roa o te wahanga tuku, me neke ake i te 100 hēkona te VDF kua oti te tatau i runga i taua ASIC kia 10x te tawhē haumaru, no reira me 100x 100 hēkona te VDF i whakatauhia ki runga taputapu taonga = ~3 haora.

Kei te whakamahere te Ethereum Foundation ki te whakaoti i tenei raruraru ma te hanga i ana ake ASICs e waatea ana mo te iwi whanui. Kia puta mai tenei, ka taea hoki e etahi atu tikanga katoa te whakamahi i tenei hangarau, engari tae noa ki tera wa ka kore te huarahi RANDAO+VDF e rite mo nga tikanga kaore e taea te haumi ki te whakawhanake i o raatau ake ASIC.

He maha nga tuhinga, ataata me etahi atu korero mo VDF kua kohia ki runga tenei pae.

Ka whakamahia e matou nga waehere muru

I tenei wahanga, ka titiro tatou ki tetahi kawa whakangao tau matapōkere e whakamahi ana te whakakore i nga waehere. Ka taea e ia ki te ⅓ te hunga whakaeke i te wa e ora tonu ana, ka taea ki te ⅔ te hunga whakaeke kia noho i mua i te matapae, te awe ranei i te putanga.

Ko te whakaaro matua o te kawa e whai ake nei. Mo te ngawari, me whakaaro he 100 nga kaiuru. Me whakaaro ano tatou kei nga kaiuru katoa o te rohe etahi kii motuhake, a ko nga ki a te iwi o nga kaiuru katoa e mohiotia ana e nga kaiuru katoa:

1. Ka puta mai he aho roa mo ia kaiuru, ka wehe kia 67 nga wahanga, ka waihanga i nga waehere muru kia 100 nga hea ka nui te 67 ki te whakahoki mai i te aho, ka toha ia o nga hea 100 ki tetahi o nga kaiuru, ka whakamuna ki te te kī tūmatanui o taua kaiuru. Ka whakaputaina nga hea kua whakawaeheretia.

2. Ka whakamahi nga kaiuru i etahi momo whakaaro kia tae ki te whakaaetanga mo nga huinga tohu mai i nga kaiuru e 67.

3. Kia tae ki te whakaaetanga, ka tangohia e ia kaiuru nga hea kua whakawaeheretia i ia huinga 67 kua whakamunatia me o raatau matua whanui, ka wetewete i aua hea katoa, ka whakaputa i aua hea wetemuna katoa.

4. Kia 67 nga kaiuru kua oti te taahiraa (3), ka taea te wetewete me te hanga ano nga huinga katoa i whakaae na runga i nga ahuatanga o nga waehere muru, a ka taea te whiwhi i te nama whakamutunga hei XOR o nga rarangi tuatahi i timata ai nga kaiuru i te (1) .

Ka taea te whakaatu i tenei kawa he kore noa iho, he kore matapae. Ka whakatauhia te tau matapōkere i muri i te tutukitanga o te whakaaetanga, engari kaore e mohiotia e tetahi kia ⅔ o nga kaiuru te wetewete i nga waahanga kua whakamunatia me o raatau matua whanui. No reira, ka whakatauhia te tau matapōkere i mua i te whakaputanga o nga korero hei hanga ano.

Ka aha mehemea i te taahiraa (1) ka tukuna e tetahi o nga kaiuru nga hea kua whakawaeheretia ki era atu kaiuru ehara i te waehere muru tika mo etahi aho? Ki te kore he huringa taapiri, ka kore e taea e nga kaiuru rereke te whakahoki mai i te aho, ka whakahoki mai ranei i nga aho rereke, ka puta he tau matapōkere rerekee nga kaiuru. Hei aukati i tenei, ka taea e koe te mahi i enei e whai ake nei: ia kaiuru, i tua atu i nga hea kua whakawaeheretia, ka tatau ano hoki. rakau Merkla nga hea katoa, a ka tukuna e ia kaiuru te hea kua oti te whakawaehere me te putake o te rakau merkle, me te tohu o te whakaurunga o te hea ki te rakau merkle. I roto i te whakaaetanga i te taahiraa (2), kaore nga kaiuru e whakaae noa mo te huinga huinga, engari mo te huinga o nga pakiaka motuhake o aua rakau (mehemea ka kotiti kee etahi o nga kaiuru i te kawa, ka tukuna nga pakiaka rakau merkle ki nga kaiuru rereke. a e rua nga putake penei ka whakaatuhia i te wa e whakaae ana, ko tana rarangi kaore i uru ki te huinga hua). Ko te hua o te whakaaetanga, ka 67 nga rarangi whakawaehere me nga pakiaka o te rakau merkle e rite ana kia 67 neke atu nga kaiuru (ehara i te mea he rite tonu nga mea i whakatakoto i nga rarangi e rite ana), ko wai mo ia rarangi 67 he karere me tetahi wahanga o te waehere muru, me te tohu kua memeha haere o ratou wahanga ki te rakau e rite ana.

I te taahiraa (4) ka wetewete te kaiuru i te 67 pao mo tetahi aho ka ngana ki te hanga ano i te aho taketake mai i a raatau, ka taea tetahi o nga whiringa:

1. Ka whakahokia mai te aho, a, ki te murua ano te whakawaehere, ka tatauhia te rakau Merkle mo nga hea kua tatauhia e te rohe, ka rite te pakiaka ki te mea i tutuki te whakaaro.

2. Ka whakahokia mai te haupae, engari karekau te putake i tatau i te rohe i te rite ki te mea i tutuki te whakaaro.

3. Ko te rarangi kaore i whakahokia.

He ngawari ki te whakaatu mena ka pa te whiringa (1) mo tetahi kaiuru i runga ake nei, katahi ka puta te whiringa (1) mo nga kaiuru katoa, me te rereke, mena ko te whiringa (2) ranei (3) i pa ki tetahi kaiuru, katahi ka mo nga kaiuru katoa ka puta te whiringa (2) ranei (3). No reira, mo ia rarangi o te huinga, ka taea e nga kaiuru katoa te whakaora, ka kore ranei nga kaiuru katoa e whakaora. Ko te tau matapōkere ka puta he XOR o nga rarangi anake i taea e nga kaiuru te whakaora.

Nga hainatanga paepae

Ko tetahi atu huarahi ki te matapōkeretia ko te whakamahi i nga mea e kiia ana ko nga hainatanga paepae BLS. He rite tonu te whakapumautanga o te kaihanga tau matapōkere i runga i nga hainatanga paepae ki te algorithm e ahu mai ana i te waehere muru i whakaahuatia i runga ake nei, engari he iti ake te maha o nga karere asymptotic ka tukuna ma te whatunga mo ia tau kua hangaia.

Ko nga waitohu BLS he hoahoa e taea ai e nga kaiuru maha te hanga i tetahi waitohu noa mo tetahi karere. He maha nga wa ka whakamahia enei waitohu ki te tiaki i te waahi me te bandwidth ma te kore e tono kia maha nga waitohu kia tukuna atu. 

He tono noa mo nga hainatanga BLS i roto i nga kawa poraka, i tua atu i te whakaputa tau matapōkere, ko te hainatanga poraka i roto i nga tikanga BFT. Me kii he 100 nga kaiuru ka waihanga poraka, ka kiia he poraka he whakamutunga mena ka hainatia e te 67 o ratou. Ka taea e ratou katoa te tuku i o raatau waahanga o te hainatanga BLS me te whakamahi i etahi algorithm whakaaetanga kia whakaae ki te 67 o ratou ka whakakotahi ki te hainatanga BLS kotahi. Ka taea te whakamahi i nga waahanga 67 (neke atu ranei) ki te hanga i te hainatanga whakamutunga, ka whakawhirinaki ki nga waitohu 67 i whakakotahihia, na reira ka rereke pea, ahakoa ko nga whiringa rereke a nga kaiuru 67 ka waihanga i tetahi waitohu rereke, ko enei waitohu ka whai mana. hainatanga mo te poraka. Ko nga kaiuru e toe ana me whiwhi me te manatoko kotahi anake te hainatanga mo ia poraka, kaua ki te 67, i runga i te whatunga, e tino whakaiti ana i te kawenga i runga i te whatunga.

Te ahua nei mena ka hangaia nga taviri motuhake e whakamahia ana e nga kaiuru i runga i tetahi huarahi, ahakoa he aha nga hainatanga 67 (he nui ake ranei, engari kaua e iti ake) ka whakahiatohia, ka rite tonu te hainatanga ka puta. Ka taea te whakamahi hei puna moorangi: i te tuatahi ka whakaae nga kaiuru ki etahi karere ka hainatia (he hua pea tenei na RANDAO, ko te hash noa ranei o te poraka whakamutunga, kare he mea nui mena ka huri i nga wa katoa. a he rite tonu) ka hangaia he waitohu BLS mo taua mea. Ko te hua o te reanga kare e matapae tae noa ki te 67 nga kaiuru ki te whakarato i o raatau waahanga, a muri iho kua whakatauhia kee te whakaputanga kaore e taea te whakawhirinaki ki nga mahi a tetahi kaiuru.

Ka taea tenei huarahi ki te matapōkeretia mena ka whai i te kawa neke atu i te ⅔ o nga kaiuru i runga ipurangi, karekau he whakaaro me te kore matapae i te mea ko te ⅓ o nga kaiuru e whai ana i te kawa. He mea nui kia mahara ko te kaitukino e whakahaere ana neke atu i te ⅓ engari iti iho i te ⅔ o nga kaiuru ka taea te aukati i te kawa, engari kaore e taea te matapae, te awe ranei i tana putanga.

Ko nga hainatanga paepae he kaupapa tino whakamere. I te wahanga tuarua o te tuhinga, ka whakamaaramahia e matou te ahua o te mahi, me te pehea e tika ai te whakaputa i nga taviri kaiuru kia taea ai te whakamahi i nga hainatanga paepae hei kaihanga tau matapōkere.

I te mutunga

Ko tenei tuhinga te tuatahi i roto i te raupapa o nga tuhinga rangitaki hangarau NEI. Ko te NEAR he kawa poraka me te papa mo te whakawhanake i nga tono whakaheke me te aro ki te ngawari o te whakawhanaketanga me te ngawari ki te whakamahi mo nga kaiwhakamahi mutunga.

Kua tuwhera te waehere kawa, kua tuhia to tatou whakatinanatanga ki Rust, ka kitea konei.

Ka kite koe he aha te ahua o te whanaketanga mo NEAR me te whakamatautau i te IDE ipurangi konei.

Ka taea e koe te whai i nga korero katoa i roto i te reo Russian i roopu waea Tuhinga o mua rōpū i runga i VKontakte, me te reo Ingarihi i roto i te mana puninga.

Ka kite ano!

Source: will.com