Habari Habr!
Katika nakala hii nitazungumza juu ya kizazi cha nambari za bahati nasibu na washiriki ambao hawaaminiani. Kama tutakavyoona hapa chini, kutekeleza jenereta nzuri "karibu" ni rahisi sana, lakini nzuri sana ni ngumu.
Kwa nini itakuwa muhimu kutoa nambari nasibu kati ya washiriki ambao hawaaminiani? Eneo moja la maombi ni maombi yaliyogatuliwa. Kwa mfano, programu ambayo inakubali dau kutoka kwa mshiriki na ama kuongeza kiasi mara mbili kwa uwezekano wa 49% au kuondoa uwezekano wa 51% itafanya kazi tu ikiwa inaweza kupokea nambari nasibu bila upendeleo. Ikiwa mshambuliaji anaweza kuathiri matokeo ya jenereta ya nambari nasibu, na hata kuongeza kidogo nafasi yake ya kupokea malipo katika programu, ataiharibu kwa urahisi.
Tunapounda itifaki ya uzalishaji nambari nasibu iliyosambazwa, tunataka iwe na sifa tatu:
-
Lazima awe hana upendeleo. Kwa maneno mengine, hakuna mshiriki anayepaswa kuathiri kwa njia yoyote matokeo ya jenereta ya nambari isiyo ya kawaida.
-
Lazima awe haitabiriki. Kwa maneno mengine, hakuna mshiriki anayepaswa kuwa na uwezo wa kutabiri ni nambari gani itatolewa (au kukisia sifa zake zozote) kabla ya kuzalishwa.
-
Itifaki lazima ifanyike, ambayo ni, kupinga ukweli kwamba asilimia fulani ya washiriki hutenganisha kutoka kwa mtandao au kujaribu kwa makusudi kusimamisha itifaki.
Katika makala hii tutaangalia mbinu mbili: RANDAO + VDF na mbinu za kufuta kanuni. Katika sehemu inayofuata, tutachunguza kwa undani mbinu kulingana na saini za kizingiti.
Lakini kwanza, hebu tuangalie algorithm rahisi na ya kawaida inayotumika, haitabiriki, lakini yenye upendeleo.
RANDAO
RANDAO ni njia rahisi sana na kwa hivyo inatumika sana katika kuzalisha nasibu. Washiriki wote wa mtandao kwanza huchagua nambari ya uwongo ya ndani, kisha kila mshiriki atume heshi ya nambari iliyochaguliwa. Ifuatayo, washiriki huchukua zamu kufunua nambari zao zilizochaguliwa na kufanya operesheni ya XOR kwenye nambari zilizofunuliwa, na matokeo ya operesheni hii inakuwa matokeo ya itifaki.
Hatua ya kuchapisha heshi kabla ya kufichua nambari ni muhimu ili mshambuliaji asiweze kuchagua nambari yake baada ya kuona nambari za washiriki wengine. Hii ingemruhusu kuamua kwa mkono mmoja matokeo ya jenereta ya nambari nasibu.
Wakati wa itifaki, washiriki wanahitaji kufikia uamuzi wa kawaida (kinachojulikana kama makubaliano) mara mbili: wakati wa kuanza kufunua nambari zilizochaguliwa, na kwa hivyo kuacha kukubali heshi, na wakati wa kuacha kukubali nambari zilizochaguliwa na kuhesabu bahati nasibu inayosababishwa. nambari. Kufanya maamuzi kama haya kati ya washiriki ambao hawaaminiani sio kazi rahisi yenyewe, na tutairudia katika nakala zijazo; katika nakala hii tutafikiria kuwa algorithm kama hiyo ya makubaliano inapatikana kwetu.
Je, RANDAO ina mali gani kati ya hizi tulizoelezea hapo juu? Haitabiriki, ina nguvu sawa na itifaki ya makubaliano ya msingi, lakini ina upendeleo. Hasa, mshambuliaji anaweza kutazama mtandao, na baada ya washiriki wengine kufichua nambari zao, anaweza kuhesabu XOR yao, na kuamua ikiwa ataonyesha nambari yake au la ili kuathiri matokeo. Ingawa hii inamzuia mshambuliaji kuamua kwa mkono mmoja matokeo ya jenereta ya nambari bila mpangilio, bado inampa ushawishi 1. Na ikiwa washambuliaji watadhibiti washiriki kadhaa, basi idadi ya bits wanayodhibiti itakuwa sawa na idadi ya washiriki chini ya udhibiti wao.
Ushawishi wa washambuliaji unaweza kupunguzwa sana kwa kuhitaji washiriki kufichua nambari kwa mpangilio. Kisha mshambuliaji ataweza kushawishi matokeo tu ikiwa itafunguliwa mwisho. Ingawa ushawishi ni mdogo sana, algorithm bado ina upendeleo.
RANDAO+VDF
Njia moja ya kufanya RANDAO bila upendeleo ni hii: baada ya nambari zote kufunuliwa na XOR imehesabiwa, matokeo yake yanalishwa kwenye pembejeo ya kazi, ambayo inachukua muda mrefu sana kuhesabu, lakini inakuwezesha kuangalia usahihi wa hesabu haraka sana.
(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстроChaguo hili la kukokotoa linaitwa Verifiable Delay Function, au VDF. Ikiwa kuhesabu matokeo ya mwisho huchukua muda mrefu zaidi kuliko hatua ya kufichua nambari, basi mshambuliaji hataweza kutabiri athari ya kuonyesha au kuficha nambari yake, na kwa hiyo atapoteza fursa ya kushawishi matokeo.
Kutengeneza VDF nzuri ni ngumu sana. Kumekuwa na mafanikio kadhaa hivi karibuni, k.m. и ambayo ilifanya VDF kuwa ya vitendo zaidi, na Ethereum 2.0 inapanga kutumia RANDAO na VDF kama chanzo cha nambari bila mpangilio kwa muda mrefu. Mbali na ukweli kwamba mbinu hii haitabiriki na haina upendeleo, ina faida ya ziada ya kuwa na manufaa ikiwa angalau washiriki wawili wanapatikana kwenye mtandao (ikizingatiwa itifaki ya makubaliano iliyotumiwa inaweza kutumika wakati wa kushughulika na idadi ndogo ya washiriki).
Changamoto kubwa ya mbinu hii ni kusanidi VDF hivi kwamba hata mshiriki aliye na vifaa maalum vya gharama kubwa hataweza kukokotoa VDF kabla ya mwisho wa awamu ya ugunduzi. Kwa kweli, algorithm inapaswa kuwa na kiwango kikubwa cha usalama, sema 10x. Kielelezo hapa chini kinaonyesha shambulio la mwigizaji ambaye ana ASIC maalum ambayo inamruhusu kuendesha VDF haraka kuliko muda uliotengwa kufichua uthibitisho wa RANDAO. Mshiriki kama huyo bado anaweza kuhesabu matokeo ya mwisho kwa kutumia au kutotumia nambari yake, na kisha, kulingana na hesabu, chagua kuionyesha au la.
Kwa familia ya VDF iliyotajwa hapo juu, utendakazi wa ASIC uliojitolea unaweza kuwa mara 100+ zaidi kuliko maunzi ya kawaida. Kwa hivyo ikiwa awamu ya upelekaji huchukua sekunde 10, basi VDF iliyokokotwa kwenye ASIC kama hiyo lazima ichukue zaidi ya sekunde 100 ili kuwa na ukingo wa usalama wa 10x, na kwa hivyo VDF ile ile iliyokokotwa kwenye maunzi ya bidhaa lazima ichukue sekunde 100x 100 = ~ masaa 3.
Ethereum Foundation inapanga kutatua tatizo hili kwa kuunda ASIC zake zinazopatikana hadharani, zisizolipishwa. Hili likitokea, itifaki zingine zote pia zinaweza kuchukua fursa ya teknolojia hii, lakini hadi wakati huo mbinu ya RANDAO+VDF haitatumika kwa itifaki ambazo haziwezi kuwekeza katika kuunda ASIC zao wenyewe.
Nakala nyingi, video na habari zingine kuhusu VDF zimekusanywa .
Tunatumia misimbo ya kufuta
Katika sehemu hii, tutaangalia itifaki ya kizazi cha nambari bila mpangilio inayotumia . Inaweza kuvumilia hadi washambulizi ⅓ huku ikiendelea kutumika, na kuruhusu hadi washambulizi ⅔ kuwepo kabla ya kutabiri au kuathiri matokeo.
Wazo kuu la itifaki ni kama ifuatavyo. Kwa urahisi, wacha tuchukue kuwa kuna washiriki 100 haswa. Hebu pia tuchukulie kuwa washiriki wote ndani ya nchi wana ufunguo wa faragha, na funguo za umma za washiriki wote zinajulikana kwa washiriki wote:
-
Kila mshiriki ndani ya nchi anakuja na kamba ndefu, anaigawanya katika sehemu 67, huunda misimbo ya kufuta ili kupata hisa 100 hivi kwamba zozote 67 zinatosha kurejesha mfuatano huo, atagawia kila hisa 100 kwa mmoja wa washiriki, na kuzisimba kwa njia fiche kwa kutumia ufunguo huo wa umma wa mshiriki. Shiriki zote zilizosimbwa huchapishwa.
-
Washiriki hutumia aina fulani ya makubaliano kufikia makubaliano juu ya seti za msimbo kutoka kwa washiriki 67 mahususi.
-
Makubaliano yanapofikiwa, kila mshiriki huchukua hisa zilizosimbwa katika kila seti 67 zilizosimbwa kwa ufunguo wao wa umma, huondoa ushiriki wote kama huo, na kuchapisha hisa zote zilizosimbwa.
-
Mara tu washiriki 67 watakapokamilisha hatua ya (3), seti zote zilizokubaliwa zinaweza kuamuliwa kabisa na kujengwa upya kutokana na sifa za misimbo ya kufuta, na nambari ya mwisho inaweza kupatikana kama XOR ya safu mlalo za awali ambazo washiriki walianza nazo katika (1) .
Itifaki hii inaweza kuonyeshwa kuwa haina upendeleo na haitabiriki. Nambari ya nasibu inayotokana hubainishwa baada ya makubaliano kufikiwa, lakini haijulikani kwa mtu yeyote hadi ⅔ ya washiriki wasimbue sehemu zilizosimbwa kwa njia fiche kwa ufunguo wao wa umma. Kwa hivyo, nambari ya nasibu huamuliwa kabla ya habari ya kutosha kuijenga upya kuchapishwa.
Nini kitatokea ikiwa katika hatua (1) mmoja wa washiriki alituma hisa zilizosimbwa kwa washiriki wengine ambazo si msimbo sahihi wa kufuta kwa baadhi ya mfuatano? Bila mabadiliko ya ziada, washiriki tofauti hawataweza kurejesha kamba kabisa, au watapata mifuatano tofauti, ambayo itasababisha washiriki tofauti kupokea nambari tofauti ya nasibu. Ili kuzuia hili, unaweza kufanya yafuatayo: kila mshiriki, pamoja na hisa zilizosimbwa, pia huhesabu. hisa zote hizo, na hutuma kila mshiriki sehemu iliyosimbwa yenyewe na mzizi wa mti wa merkle, na uthibitisho wa kuingizwa kwa sehemu katika mti wa merkle. Katika makubaliano katika hatua (2), washiriki basi sio tu kukubaliana juu ya seti ya seti, lakini kwa seti ya mizizi maalum ya miti kama hiyo (ikiwa mshiriki fulani alijitenga na itifaki, na kutuma mizizi tofauti ya miti ya merkle kwa washiriki tofauti, na mizizi miwili kama hiyo inaonyeshwa wakati wa makubaliano, safu yake haijajumuishwa kwenye seti ya matokeo). Kama matokeo ya makubaliano hayo, tutakuwa na mistari 67 iliyosimbwa na mizizi inayolingana ya mti wa merkle hivi kwamba kuna angalau washiriki 67 (sio lazima wale wale ambao walipendekeza mistari inayolingana), ambao kwa kila moja ya mistari 67 wana. ujumbe wenye sehemu ya msimbo wa kufuta, na uthibitisho wa kutokea kwa sehemu yao kwenye mti unaolingana ulififia.
Wakati katika hatua (4) mshiriki anafafanua midundo 67 kwa kamba fulani na kujaribu kuunda tena kamba asili kutoka kwao, chaguo moja linawezekana:
-
Mfuatano umerejeshwa, na ikiwa utafutwa tena, na mti wa Merkle ukahesabiwa kwa hisa zilizokokotwa ndani, mzizi unapatana na ule ambao makubaliano yalifikiwa.
-
Safu mlalo imerejeshwa, lakini mzizi uliokokotolewa ndani ya nchi haulingani na ule ambao makubaliano yalifikiwa.
-
Safu mlalo haijarejeshwa.
Ni rahisi kuonyesha kwamba ikiwa chaguo (1) lilifanyika kwa angalau mshiriki mmoja hapo juu, basi chaguo (1) lilifanyika kwa washiriki wote, na kinyume chake, ikiwa chaguo (2) au (3) lilifanyika kwa angalau mshiriki mmoja, basi. kwa washiriki wote chaguo (2) au (3) litafanyika. Kwa hivyo, kwa kila safu kwenye seti, washiriki wote wataiokoa kwa mafanikio, au washiriki wote watashindwa kuirejesha. Nambari ya nasibu inayotokana basi ni XOR ya safu mlalo ambazo washiriki waliweza kurejesha.
Saini za kizingiti
Njia nyingine ya kubahatisha ni kutumia kile kinachoitwa saini za kizingiti cha BLS. Jenereta ya nambari nasibu kulingana na saini za kiwango cha juu ina hakikisho sawa na algoriti ya msingi ya ufutaji iliyofafanuliwa hapo juu, lakini ina idadi ndogo sana ya ujumbe unaotumwa kupitia mtandao kwa kila nambari inayozalishwa.
Sahihi za BLS ni muundo unaoruhusu washiriki wengi kuunda sahihi moja ya kawaida ya ujumbe. Sahihi hizi mara nyingi hutumiwa kuhifadhi nafasi na kipimo data kwa kutohitaji saini nyingi kutumwa nje.
Programu ya kawaida ya saini za BLS katika itifaki za blockchain, pamoja na kutoa nambari nasibu, ni kuzuia kutia saini katika itifaki za BFT. Wacha tuseme washiriki 100 huunda vizuizi, na kizuizi kinachukuliwa kuwa cha mwisho ikiwa 67 kati yao watasaini. Wote wanaweza kuwasilisha sehemu zao za sahihi ya BLS na kutumia algoriti ya makubaliano kukubaliana 67 kati yao na kisha kuziunganisha kuwa sahihi moja ya BLS. Sehemu zozote 67 (au zaidi) zinaweza kutumika kuunda saini ya mwisho, ambayo itategemea saini 67 ziliunganishwa na kwa hivyo zinaweza kutofautiana, ingawa chaguzi tofauti za washiriki 67 zitaunda saini tofauti, saini yoyote kama hiyo itakuwa halali. saini kwa block. Washiriki waliobaki basi wanahitaji tu kupokea na kuthibitisha saini moja tu kwa block, badala ya 67, juu ya mtandao, ambayo hupunguza kwa kiasi kikubwa mzigo kwenye mtandao.
Inabadilika kuwa ikiwa funguo za faragha ambazo washiriki hutumia zinazalishwa kwa njia fulani, basi bila kujali ni saini 67 (au zaidi, lakini si chini) zimeunganishwa, saini inayotokana itakuwa sawa. Hii inaweza kutumika kama chanzo cha kubahatisha: washiriki kwanza wanakubali ujumbe fulani ambao watatia saini (hili linaweza kuwa matokeo ya RANDAO au heshi ya kizuizi cha mwisho, haijalishi mradi tu inabadilika kila wakati. na ni thabiti) na uunde saini ya BLS kwa ajili yake. Matokeo ya kizazi hayatatabirika hadi washiriki 67 watoe sehemu zao, na baada ya hapo matokeo tayari yamepangwa na hayawezi kutegemea vitendo vya mshiriki yeyote.
Mbinu hii ya kubahatisha inaweza kutumika mradi angalau ⅔ ya washiriki mtandaoni wote wanafuata itifaki, na haina upendeleo na haitabiriki mradi angalau ⅓ ya washiriki wafuate itifaki. Ni muhimu kutambua kwamba mshambulizi anayedhibiti zaidi ya ⅓ lakini chini ya ⅔ ya washiriki anaweza kusimamisha itifaki, lakini hawezi kutabiri au kuathiri matokeo yake.
Saini za kizingiti zenyewe ni mada ya kuvutia sana. Katika sehemu ya pili ya kifungu, tutachambua kwa undani jinsi wanavyofanya kazi, na jinsi inavyohitajika kutoa funguo za washiriki ili saini za kizingiti zitumike kama jenereta ya nambari isiyo ya kawaida.
Kwa kumalizia
Makala hii ni ya kwanza katika mfululizo wa makala za blogu za kiufundi . KARIBU ni itifaki ya blockchain na jukwaa la kuunda programu zilizogatuliwa kwa msisitizo wa urahisi wa maendeleo na urahisi wa matumizi kwa watumiaji wa mwisho.
Nambari ya itifaki imefunguliwa, utekelezaji wetu umeandikwa katika Rust, inaweza kupatikana .
Unaweza kuona jinsi maendeleo ya NEAR yanavyoonekana na ujaribu katika IDE ya mtandaoni .
Unaweza kufuata habari zote kwa Kirusi na , na kwa Kiingereza katika rasmi .
Nitakuona hivi karibuni!
Chanzo: mapenzi.com