Ruka hadi kwenye maudhui makuu
Change page

Dagger-Hashimoto

Dagger-Hashimoto ilikuwa utekelezaji na vipimo vya utafiti wa asili kwa algoriti ya uchimbaji ya Ethereum. Dagger-Hashimoto ilibadilishwa na Ethash. Uchimbaji ulizimwa kabisa kwenye Unganisho mnamo tarehe 15 Septemba 2022. Tangu wakati huo, Ethereum imelindwa kwa kutumia utaratibu wa Uthibitisho wa Dau (PoS) badala yake. Ukurasa huu ni kwa ajili ya maslahi ya kihistoria - maelezo hapa hayana umuhimu tena kwa Ethereum ya baada ya Unganisho.

Mahitaji ya awali

Ili kuelewa vyema ukurasa huu, tunapendekeza kwanza usome kuhusu mwafaka wa Uthibitisho wa Kazi (PoW), uchimbaji, na algoriti za uchimbaji.

Dagger-Hashimoto

Dagger-Hashimoto inalenga kutimiza malengo mawili:

  1. Ukinzani wa ASIC: faida inayotokana na kuunda maunzi maalum kwa ajili ya algoriti inapaswa kuwa ndogo iwezekanavyo
  2. Uthibitishaji wa kiteja chepesi: kitalu kinapaswa kuthibitishwa kwa ufanisi na kiteja chepesi.

Kwa marekebisho ya ziada, pia tunabainisha jinsi ya kutimiza lengo la tatu ikihitajika, lakini kwa gharama ya utata wa ziada:

Hifadhi kamili ya mnyororo: uchimbaji unapaswa kuhitaji uhifadhi wa hali kamili ya mnyororo wa vitalu (kutokana na muundo usio wa kawaida wa trie ya hali ya Ethereum, tunatarajia kwamba upunguzaji fulani utawezekana, hasa wa baadhi ya mikataba inayotumiwa mara kwa mara, lakini tunataka kupunguza hili).

Uzalishaji wa DAG

Msimbo wa algoriti utafafanuliwa katika Python hapa chini. Kwanza, tunatoa encode_int kwa ajili ya kupanga nambari kamili zisizo na saini za usahihi uliobainishwa kuwa mifuatano. Kinyume chake pia kinatolewa:

Kisha tunachukulia kwamba sha3 ni kazi inayochukua nambari kamili na kutoa nambari kamili, na dbl_sha3 ni kazi ya double-sha3; ikiwa unabadilisha msimbo huu wa marejeleo kuwa utekelezaji tumia:

Vigezo

Vigezo vinavyotumika kwa algoriti ni:

P katika kesi hii ni nambari tasa iliyochaguliwa ili log₂(P) iwe chini kidogo ya 512, ambayo inalingana na biti 512 ambazo tumekuwa tukitumia kuwakilisha nambari zetu. Kumbuka kwamba ni nusu ya mwisho tu ya DAG ndiyo inayohitaji kuhifadhiwa, kwa hivyo hitaji halisi la RAM linaanza kwa GB 1 na kukua kwa MB 441 kwa mwaka.

Ujenzi wa grafu ya Dagger

Msingi wa ujenzi wa grafu ya dagger unafafanuliwa kama ifuatavyo:

Kimsingi, inaanza grafu kama nodi moja, sha3(seed), na kutoka hapo inaanza kuongeza nodi zingine kwa mfuatano kulingana na nodi za awali za nasibu. Wakati nodi mpya inapoundwa, nguvu ya msimu ya mbegu inakokotolewa ili kuchagua kwa nasibu baadhi ya faharisi zilizo chini ya i (kwa kutumia x % i hapo juu), na thamani za nodi kwenye faharisi hizo zinatumika katika ukokotoaji ili kuzalisha thamani mpya ya x, ambayo kisha inaingizwa kwenye kazi ndogo ya uthibitisho wa kazi (kulingana na XOR) ili hatimaye kuzalisha thamani ya grafu kwenye faharisi i. Mantiki nyuma ya muundo huu mahususi ni kulazimisha ufikiaji wa mfuatano wa DAG; thamani inayofuata ya DAG itakayofikiwa haiwezi kubainishwa hadi thamani ya sasa ijulikane. Hatimaye, upeo wa msimu unaheshi matokeo zaidi.

Algoriti hii inategemea matokeo kadhaa kutoka kwa nadharia ya nambari. Tazama kiambatisho hapa chini kwa mjadala.

Tathmini ya kiteja chepesi

Ujenzi wa grafu hapo juu unakusudia kuruhusu kila nodi katika grafu kujengwa upya kwa kukokotoa mti mdogo wa idadi ndogo tu ya nodi na kuhitaji kiasi kidogo tu cha kumbukumbu ya ziada. Kumbuka kwamba kwa k=1, mti mdogo ni mnyororo tu wa thamani zinazopanda hadi kipengele cha kwanza katika DAG.

Kazi ya ukokotoaji ya kiteja chepesi kwa DAG inafanya kazi kama ifuatavyo:

Kimsingi, ni uandishi upya tu wa algoriti iliyo hapo juu ambayo inaondoa kitanzi cha kukokotoa thamani za DAG nzima na kubadilisha utafutaji wa nodi wa awali na wito wa kujirudia au utafutaji wa kache. Kumbuka kwamba kwa k=1 kache sio lazima, ingawa uboreshaji zaidi kwa kweli hukokotoa mapema thamani elfu chache za kwanza za DAG na kuiweka kama kache tuli kwa ukokotoaji; tazama kiambatisho kwa utekelezaji wa msimbo wa hili.

Bafa mbili za DAG

Katika kiteja kamili, bafa mbili (opens in a new tab) za DAG 2 zinazozalishwa na fomula iliyo hapo juu zinatumika. Wazo ni kwamba DAG zinazalishwa kila idadi ya epochtime ya vitalu kulingana na vigezo hapo juu. Badala ya kiteja kutumia DAG ya hivi punde iliyozalishwa, kinatumia ile ya awali. Faida ya hili ni kwamba inaruhusu DAG kubadilishwa kwa muda bila kuhitaji kujumuisha hatua ambapo wachimbaji lazima wakokotoe upya data yote ghafla. Vinginevyo, kuna uwezekano wa kupungua kwa kasi kwa muda kwa ghafla katika usindikaji wa mnyororo kwa vipindi vya kawaida na kuongeza kwa kiasi kikubwa uwekaji kati. Hivyo hatari za shambulio la asilimia 51 ndani ya dakika hizo chache kabla ya data yote kukokotolewa upya.

Algoriti inayotumika kuzalisha seti ya DAG zinazotumika kukokotoa kazi kwa kitalu ni kama ifuatavyo:

Hashimoto

Wazo nyuma ya Hashimoto ya asili ni kutumia mnyororo wa vitalu kama seti ya data, kufanya ukokotoaji unaochagua faharisi N kutoka kwenye mnyororo wa vitalu, kukusanya miamala kwenye faharisi hizo, kufanya XOR ya data hii, na kurudisha heshi ya matokeo. Algoriti ya asili ya Thaddeus Dryja, iliyotafsiriwa kwa Python kwa uthabiti, ni kama ifuatavyo:

def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
    hash_output_A = sha256(prev_hash + merkle_root + nonce)
    txid_mix = 0
    for i in range(64):
        shifted_A = hash_output_A >> i
        transaction = shifted_A % len(list_of_transactions)
        txid_mix ^= list_of_transactions[transaction] << i
    return txid_mix ^ (nonce << 192)

Kwa bahati mbaya, ingawa Hashimoto inachukuliwa kuwa ngumu kwa RAM, inategemea hesabu ya biti 256, ambayo ina mzigo mkubwa wa ukokotoaji. Hata hivyo, Dagger-Hashimoto inatumia tu biti 64 zenye umuhimu mdogo zaidi wakati wa kuweka faharisi seti yake ya data ili kushughulikia suala hili.

def hashimoto(dag, dagsize, params, header, nonce):
    m = dagsize / 2
    mix = sha3(encode_int(nonce) + header)
    for _ in range(params["accesses"]):
        mix ^= dag[m + (mix % 2**64) % m]
    return dbl_sha3(mix)

Matumizi ya SHA3 mbili yanaruhusu aina ya uthibitishaji wa awali wa data sifuri, unaokaribia papo hapo, kuthibitisha tu kwamba thamani sahihi ya kati ilitolewa. Safu hii ya nje ya uthibitisho wa kazi ni rafiki sana kwa ASIC na ni dhaifu kiasi, lakini ipo ili kufanya DDoS kuwa ngumu zaidi kwa kuwa kiasi hicho kidogo cha kazi lazima kifanyike ili kuzalisha kitalu ambacho hakitakataliwa mara moja. Hapa kuna toleo la kiteja chepesi:

def quick_hashimoto(seed, dagsize, params, header, nonce):
    m = dagsize // 2
    mix = sha3(nonce + header)
    for _ in range(params["accesses"]):
        mix ^= quick_calc(params, seed, m + (mix % 2**64) % m)
    return dbl_sha3(mix)

Uchimbaji na uthibitishaji

Sasa, hebu tuweke yote pamoja katika algoriti ya uchimbaji:

Hapa kuna algoriti ya uthibitishaji:

def verify(daggerset, params, block, nonce):
    result = hashimoto(daggerset, get_dagsize(params, block),
                       params, decode_int(block.prevhash), nonce)
    return result * params["diff"] < 2**256

Uthibitishaji rafiki kwa kiteja chepesi:

def light_verify(params, header, nonce):
    seedset = get_seedset(params, block)
    result = quick_hashimoto(seedset["front_hash"], get_dagsize(params, block),
                             params, decode_int(block.prevhash), nonce)
    return result * params["diff"] < 2**256

Pia, kumbuka kwamba Dagger-Hashimoto inaweka mahitaji ya ziada kwenye kichwa cha kizuizi:

  • Ili uthibitishaji wa tabaka mbili ufanye kazi, kichwa cha kizuizi lazima kiwe na nonsi na thamani ya kati kabla ya sha3
  • Mahali fulani, kichwa cha kizuizi lazima kihifadhi sha3 ya seti ya mbegu ya sasa

Usomaji zaidi

Unajua rasilimali ya jamii iliyokusaidia? Hariri ukurasa huu na uiongeze!

Kiambatisho

Kama ilivyoelezwa hapo juu, RNG inayotumika kwa uzalishaji wa DAG inategemea baadhi ya matokeo kutoka kwa nadharia ya nambari. Kwanza, tunatoa hakikisho kwamba Lehmer RNG ambayo ni msingi wa kigezo cha picker ina kipindi kipana. Pili, tunaonyesha kwamba pow(x,3,P) haitapanga x kwa 1 au P-1 mradi x ∈ [2,P-2] kuanza. Hatimaye, tunaonyesha kwamba pow(x,3,P) ina kiwango cha chini cha mgongano inapotibiwa kama kazi ya heshi.

Jenereta ya nambari nasibu ya Lehmer

Ingawa kazi ya produce_dag haihitaji kuzalisha nambari nasibu zisizo na upendeleo, tishio linalowezekana ni kwamba seed**i % P inachukua tu thamani chache. Hili linaweza kutoa faida kwa wachimbaji wanaotambua muundo huo dhidi ya wale wasiotambua.

Ili kuepuka hili, matokeo kutoka kwa nadharia ya nambari yanatumika. Nambari Tasa Salama (opens in a new tab) inafafanuliwa kuwa nambari tasa P ili (P-1)/2 pia iwe nambari tasa. Mpangilio wa mwanachama x wa kikundi cha kuzidisha (opens in a new tab) ℤ/nℤ unafafanuliwa kuwa m ya chini zaidi ili 

xᵐ mod P ≡ 1
Kwa kuzingatia ufafanuzi huu, tuna:

Uchunguzi 1. Acha x iwe mwanachama wa kikundi cha kuzidisha ℤ/Pℤ kwa nambari tasa salama P. Ikiwa x mod P ≠ 1 mod P na x mod P ≠ P-1 mod P, basi mpangilio wa x ni ama P-1 au (P-1)/2.

Uthibitisho. Kwa kuwa P ni nambari tasa salama, basi kwa [Nadharia ya Lagrange][lagrange] tuna kwamba mpangilio wa x ni ama 1, 2, (P-1)/2, au P-1.

Mpangilio wa x hauwezi kuwa 1, kwa kuwa kwa Nadharia Ndogo ya Fermat tuna:

xP-1 mod P ≡ 1

Kwa hivyo x lazima iwe utambulisho wa kuzidisha wa ℤ/nℤ, ambao ni wa kipekee. Kwa kuwa tulichukulia kwamba x ≠ 1 kwa dhana, hili haliwezekani.

Mpangilio wa x hauwezi kuwa 2 isipokuwa x = P-1, kwa kuwa hii ingekiuka kwamba P ni nambari tasa.

Kutoka kwa pendekezo hapo juu, tunaweza kutambua kwamba kurudia (picker * init) % P kutakuwa na urefu wa mzunguko wa angalau (P-1)/2. Hii ni kwa sababu tulichagua P kuwa nambari tasa salama inayokaribia kuwa sawa na nguvu ya juu ya mbili, na init iko katika muda wa [2,2**256+1]. Kwa kuzingatia ukubwa wa P, hatupaswi kamwe kutarajia mzunguko kutoka kwa upeo wa msimu.

Tunapokabidhi seli ya kwanza katika DAG (kigezo kilichoitwa init), tunakokotoa pow(sha3(seed) + 2, 3, P). Kwa mtazamo wa kwanza, hii haihakikishi kwamba matokeo sio 1 wala P-1. Hata hivyo, kwa kuwa P-1 ni nambari tasa salama, tuna hakikisho la ziada lifuatalo, ambalo ni tokeo la Uchunguzi 1:

Uchunguzi 2. Acha x iwe mwanachama wa kikundi cha kuzidisha ℤ/Pℤ kwa nambari tasa salama P, na acha w iwe nambari asilia. Ikiwa x mod P ≠ 1 mod P na x mod P ≠ P-1 mod P, pamoja na w mod P ≠ P-1 mod P na w mod P ≠ 0 mod P, basi xʷ mod P ≠ 1 mod P na xʷ mod P ≠ P-1 mod P

Upeo wa msimu kama kazi ya heshi

Kwa thamani fulani za P na w, kazi ya pow(x, w, P) inaweza kuwa na migongano mingi. Kwa mfano, pow(x,9,19) inachukua tu thamani za {1,18}.

Kwa kuwa P ni nambari tasa, basi w inayofaa kwa kazi ya uheshiji ya upeo wa msimu inaweza kuchaguliwa kwa kutumia matokeo yafuatayo:

Uchunguzi 3. Acha P iwe nambari tasa; w na P-1 ni nambari tasa kiasi ikiwa na tu ikiwa kwa a na b zote katika ℤ/Pℤ:

aʷ mod P ≡ bʷ mod P ikiwa na tu ikiwa a mod P ≡ b mod P

Hivyo, kwa kuwa P ni nambari tasa na w ni nambari tasa kiasi kwa P-1, tuna kwamba |{pow(x, w, P) : x ∈ ℤ}| = P, ikimaanisha kwamba kazi ya uheshiji ina kiwango cha chini zaidi cha mgongano kinachowezekana.

Katika kesi maalum kwamba P ni nambari tasa salama kama tulivyochagua, basi P-1 ina vigawo 1, 2, (P-1)/2 na P-1 pekee. Kwa kuwa P > 7, tunajua kwamba 3 ni nambari tasa kiasi kwa P-1, kwa hivyo w=3 inakidhi pendekezo hapo juu.

Algoriti ya tathmini inayotegemea kache yenye ufanisi zaidi