Dagger-Hashimoto

Dagger-Hashimoto, Ethereum'un madencilik algoritması için orijinal araştırma uygulaması ve şartnamesiydi. Dagger-Hashimoto'nun yerini Ethash aldı. 15 Eylül 2022'de gerçekleşen Birleşim'den sonra madencilik tamamen durdurulmuştur. O zamandan beri Ethereum hisse ispatı mekanizmasını kullanmaktadır. Bu sayfa sadece bilgilendirme içindir - burdaki bilgi Birleşim sonrası Ethereum için geçerli değildir.

Ön koşullar

Bu sayfayı daha iyi anlamak için önce iş kanıtı mutabakatı, madencilik ve >madencilik algoritmaları hakkında okumanızı öneririz.

Dagger-Hashimoto

Dagger-Hashimoto iki hedefi gerçekleştirmeyi amaçlar:

1. ASIC direnci: Algoritma için özel donanım oluşturmanın faydası mümkün olduğunca küçük olmalıdır
2. Hafif istemci doğrulanabilirliği: Bir blok, hafif bir istemci tarafından verimli bir şekilde doğrulanabilir olmalıdır.

Ek bir değişiklikle, istenirse, ancak ek karmaşıklık pahasına üçüncü bir hedefin nasıl yerine getirileceğini de belirtiyoruz:

Tam zincir depolama: madencilik, tam blok zinciri durumunun depolanmasını gerektirmelidir (Ethereum durum üçlüsünün düzensiz yapısı nedeniyle, özellikle sık kullanılan bazı sözleşmelerde bir miktar budamanın mümkün olacağını tahmin ediyoruz, ancak bunu en asgari seviyeye indirmek istiyoruz).

DAG Jenerasyonu

Algoritmanın kodu aşağıdaki Python'da tanımlanacaktır. İlk olarak belirlitilen kesinliklerin belirli olmayan tam sayılarını dizelere sıralamak için encode_int ile başlarız. Tersi de aşağıda verilmiştir:

1NUM_BITS = 512
2
3def encode_int(x):
4    "Encode an integer x as a string of 64 characters using a big-endian scheme"
5    o = ''
6    for _ in range(NUM_BITS / 8):
7        o = chr(x % 256) + o
8        x //= 256
9    return o
10
11def decode_int(s):
12    "Unencode an integer x from a string using a big-endian scheme"
13    x = 0
14    for c in s:
15        x *= 256
16        x += ord(c)
17    return x
Tümünü göster
 Kopyala

Daha sonra, sha3'ün bir tamsayı alan ve bir tamsayı veren bir işlev olduğunu ve dbl_sha3'ün bir double-sha3 işlevi olduğunu varsayacağız; bu referans kodunu bir uygulamaya dönüştürüyorsanız:

1from pyethereum import utils
2def sha3(x):
3    if isinstance(x, (int, long)):
4        x = encode_int(x)
5    return decode_int(utils.sha3(x))
6
7def dbl_sha3(x):
8    if isinstance(x, (int, long)):
9        x = encode_int(x)
10    return decode_int(utils.sha3(utils.sha3(x)))
Tümünü göster
 Kopyala

Parametreler

Algoritma için kullanılan parametreler şunlardır:

1SAFE_PRIME_512 = 2**512 - 38117 # En Büyük Güvenli Prime 2**512'den küçük
2
3parametreler = {
4      "n": 4000055296 * 8 // NUM_BITS, # Veri kümesinin boyutu (4 Gigabayt); 65536'NIN KATINDA OLMALIDIR
5      "n_inc": 65536, # Dönem başına n değerinde artış; 65536'NIN KATINDA OLMALIDIR
6                                        # epochtime ile=20000, yılda 882 MB büyüme sağlar
7      "cache_size": 2500, # Light istemcinin önbelleğinin boyutu (light ile seçilebilir
8                                        # istemci; algo spesifikasyonunun bir parçası değil)
9      "diff": 2**14, # Zorluk (blok değerlendirmesi sırasında ayarlanır)
10      "epochtime": 100000, # Bir dönemin blok cinsinden uzunluğu (veri kümesinin ne sıklıkta güncellendiği)
11      "k": 1, # Bir düğümün ebeveyn sayısı
12      "w": w, # Modüler üslü karma için kullanılır
13      "erişim": 200, # Hashimoto sırasında veri kümesi erişimlerinin sayısı
14      "P": SAFE_PRIME_512 # Karma ve rastgele sayı üretimi için Safe Prime
15}
Tümünü göster
 Kopyala

Bu durumda P, log₂(P)'nin 512'den biraz daha küçük olacağı şekilde seçilen bir asaldır ve bu, sayılarımızı temsil etmek için kullandığımız 512 bite karşılık gelir. DAG'nin yalnızca ikinci yarısının gerçekten depolanması gerektiğini unutmayın, bu nedenle RAM gereksinimi 1 GB'den başlar ve yılda 441 MB büyür.

Dagger grafiği inşa etmek

Dagger grafiği oluşturma ilkesi şu şekilde tanımlanır:

1def produce_dag(params, seed, length):
2    P = params["P"]
3    picker = init = pow(sha3(seed), params["w"], P)
4    o = [init]
5    for i in range(1, length):
6        x = picker = (picker * init) % P
7        for _ in range(params["k"]):
8            x ^= o[x % i]
9        o.append(pow(x, params["w"], P))
10    return o
Tümünü göster
 Kopyala

Esasen, bir grafikten tek bir düğüm, sha3(tohum) olarak başlar ve oradan, rastgele önceki düğümlere dayalı olarak diğer düğümlere sırayla eklemeye başlar. Yeni bir düğüm oluşturulduğunda, i'den küçük bazı indeksleri (yukarıdaki x % i kullanılarak) rastgele seçmek için çekirdeğin modüler bir gücü hesaplanır ve bu indekslerdeki düğümler, x için yeni bir değer oluşturmak üzere bir hesaplamada kullanılır, bu daha sonra küçük bir çalışma kanıtı işlevine (XOR'a dayalı olarak) beslenir ve sonuçta i dizininde grafiğin değerini oluşturur. Bu özel tasarımın arkasındaki mantık, DAG'nin sıralı erişimini zorlamak; DAG'ın erişilecek bir sonraki değeri, mevcut değer bilinene kadar belirlenemez. Son olarak, modüler üs alma sonucu daha da özetler.

Bu algoritma, sayı teorisinden elde edilen çeşitli sonuçlara dayanır. Bir tartışma için ek bölümü aşağıda görebilirsiniz.

Hafif istemci değerlendirmesi

Yukarıdaki grafik yapısı, grafikteki her bir düğümün, yalnızca az sayıda düğümden oluşan bir alt ağaç hesaplanarak ve yalnızca az miktarda yardımcı bellek gerektirerek yeniden oluşturulmasına izin vermeyi amaçlamaktadır. K=1 ile alt ağacın yalnızca DAG'deki ilk öğeye kadar giden bir değerler zinciri olduğuna dikkat edin.

DAG için hafif istemci hesaplama işlevi aşağıdaki gibi çalışır:

1def quick_calc(params, seed, p):
2    w, P = params["w"], params["P"]
3    cache = {}
4
5    def quick_calc_cached(p):
6        if p in cache:
7            pass
8        elif p == 0:
9            cache[p] = pow(sha3(seed), w, P)
10        else:
11            x = pow(sha3(seed), (p + 1) * w, P)
12            for _ in range(params["k"]):
13                x ^= quick_calc_cached(x % p)
14            cache[p] = pow(x, w, P)
15        return cache[p]
16
17    return quick_calc_cached(p)
Tümünü göster
 Kopyala

Esasen, tüm DAG için değerleri hesaplama döngüsünü ortadan kaldıran ve önceki düğüm aramasını özyinelemeli bir çağrı veya bir önbellek aramasıyla değiştiren, yukarıdaki algoritmanın basitçe yeniden yazılmasıdır. k=1 için önbelleğin gereksiz olduğunu unutmayın, ancak daha fazla optimizasyon aslında DAG'nin ilk birkaç bin değerini önceden hesaplar ve bunu, hesaplamalar için statik bir önbellek olarak tutar; bunun bir kod uygulaması için eke bakın.

DAG'ların duble destekçisi

Bir tam istemcide 2 DAG'ın çifte buffer(opens in a new tab)' yukarıda kullanılan formül ile üretilir. Burada düşünce, DAG'lar her blok sayısı döngü zamanı tarafından yukarıdaki parametrelere göre üretilir. Üretilen en son DAG'ı kullanan istemci yerine, öncekini kullanır. Bunun yararı, madencilerin tüm verileri aniden yeniden hesaplaması gereken bir adımın dahil edilmesine gerek kalmadan, DAG'lerin zaman içinde değiştirilmesine izin vermesidir. Aksi takdirde, düzenli aralıklarla zincir işlemede ani bir geçici yavaşlama ve merkezileşmeyi önemli ölçüde artırma potansiyeli vardır. Bu nedenle, tüm veriler yeniden hesaplanmadan önceki birkaç dakika içinde %51 saldırı riski vardır.

Bir blok için çalışmayı hesaplamak için kullanılan DAG setini oluşturmak için kullanılan algoritma aşağıdaki gibidir:

1def get_prevhash(n):
2    from pyethereum.blocks import GENESIS_PREVHASH
3    from pyethereum import chain_manager
4    if n <= 0:
5        return hash_to_int(GENESIS_PREVHASH)
6    else:
7        prevhash = chain_manager.index.get_block_by_number(n - 1)
8        return decode_int(prevhash)
9
10def get_seedset(params, block):
11    seedset = {}
12    seedset["back_number"] = block.number - (block.number % params["epochtime"])
13    seedset["back_hash"] = get_prevhash(seedset["back_number"])
14    seedset["front_number"] = max(seedset["back_number"] - params["epochtime"], 0)
15    seedset["front_hash"] = get_prevhash(seedset["front_number"])
16    return seedset
17
18def get_dagsize(params, block):
19    return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]
20
21def get_daggerset(params, block):
22    dagsz = get_dagsize(params, block)
23    seedset = get_seedset(params, block)
24    if seedset["front_hash"] <= 0:
25        # No back buffer is possible, just make front buffer
26        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
27                          "block_number": 0}}
28    else:
29        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
30                          "block_number": seedset["front_number"]},
31                "back": {"dag": produce_dag(params, seedset["back_hash"], dagsz),
32                         "block_number": seedset["back_number"]}}
Tümünü göster
 Kopyala

Hashimoto

Orijinal Hashimoto'nun arkasındaki fikir, blok zincirini bir veri seti olarak kullanmak, blok zincirinden N indeks seçen, bu indekslerdeki işlemleri toplayan, bu verilerin bir XOR'sini gerçekleştiren ve sonucun karmasını döndüren bir hesaplama yapmaktır. Thaddeus Dryja'nın tutarlılık için Python'a çevrilmiş orijinal algoritması aşağıdaki gibidir:

1def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
2    hash_output_A = sha256(prev_hash + merkle_root + nonce)
3    txid_mix = 0
4    for i in range(64):
5        shifted_A = hash_output_A >> i
6        transaction = shifted_A % len(list_of_transactions)
7        txid_mix ^= list_of_transactions[transaction] << i
8    return txid_mix ^ (nonce << 192)
 Kopyala

Ne yazık ki, Hashimoto RAM zor olarak kabul edilirken, önemli hesaplama yükü olan 256-bit aritmetik kullanır. Ancak Dagger-Hashimoto, bu sorunu çözmek için veri kümesini indekslerken yalnızca en az önemli 64 biti kullanır.

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

Çift SHA3'ün kullanımı, yalnızca doğru bir ara değerin sağlandığını doğrulayan, neredeyse anında ön doğrulama olan bir sıfır veri biçimine olanak tanır. Çalışma kanıtının bu dış katmanı oldukça ASIC dostudur ve oldukça zayıftır, ancak hemen reddedilmeyecek bir blok oluşturmak için bu küçük miktarda işin yapılması gerektiğinden DDoS'u daha da zor hale getirmek için vardır. Hafif-istemci versiyonu aşağıdaki gibidir:

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

Madencilik ve doğrulama

Şimdi hepsini madencilik algoritmasında bir araya getirelim:

1def mine(daggerset, params, block):
2    from random import randint
3    nonce = randint(0, 2**64)
4    while 1:
5        result = hashimoto(daggerset, get_dagsize(params, block),
6                           params, decode_int(block.prevhash), nonce)
7        if result * params["diff"] < 2**256:
8            break
9        nonce += 1
10        if nonce >= 2**64:
11            nonce = 0
12    return nonce
Tümünü göster
 Kopyala

Doğrulama algoritması aşağıdadır:

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

Hafif-istemci dostu doğrulama:

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

Ayrıca, Dagger-Hashimoto'nun blok başlığına ek gereksinimler getirdiğini unutmayın:

• İki katmanlı doğrulamanın çalışması için, bir blok başlığı hem nonce hem de orta değer pre-sha3'e sahip olmalıdır
• Bir yerde, bir blok başlığı mevcut tohum setinin sha3'ünü depolamalıdır

Daha fazla okuma

Size yardımcı olan bir topluluk kaynağı biliyor musunuz? Bu sayfayı düzenleyin ve onu ekleyin!

Ek

Yukarıda belirtildiği gibi, DAG üretimi için kullanılan RNG, sayı teorisinden elde edilen bazı sonuçlara dayanır. İlk olarak, picker değişkeninin temeli olan Lehmer RNG'nin geniş bir periyoda sahip olduğuna dair güvence veriyoruz. İkinci olarak, P-1'in başlamak için x ∈ [2,P-2]'i sağladığını ya da pow(x,3,P)'un x'i 1'e adreslemeyeceğini gösteriyoruz. Son olarak, pow(x,3,P) öğesinin bir karma işlevi olarak ele alındığında düşük bir çarpışma oranına sahip olduğunu gösteriyoruz.

Lehmer rastgele sayı üreticisi

produce_dag işlevinin tarafsız rastgele sayılar üretmesi gerekmese de, potansiyel bir tehdit, seed**i % P'nin yalnızca bir avuç değer almasıdır. Bu, modeli tanımayanlara kıyasla madencilere bir avantaj sağlayabilir.

Bundan kaçınmak için sayı teorisinden bir sonuca başvurulur. Bir güvenli asal(opens in a new tab) olan P, (P-1)/2'nin asal olduğu yerde asal olarak kabul edilir. Bir x üyenin çarpımsal grup(opens in a new tab) sıralaması ℤ/nℤ, minimum m olarak tanımlanır, öyle ki

1xᵐ mod P ≡ 1

Gözlem 1. x, güvenli bir asal P için ℤ/Pℤ çarpımsal grubunun bir üyesi olsun. x mod P ≠ 1 mod P ve x mod P ≠ P-1 mod P ise, x'in sırası ya P-1 ya da (P-1)/2'dir.

Kanıt. P güvenli bir asal olduğundan, [Lagrange Teoremi][lagrange] ile x sırası ya 1, 2, (P-1)/2 veya P-1 olur.

x'in sırası 1 olamaz, çünkü Fermat'ın Küçük Teoremi'ne göre:

1xP-1 mod P ≡ 1

Bu nedenle x, benzersiz olan ℤ/nℤ'nin çarpımsal kimliği olmalıdır. x ≠ 1 olduğunu varsaydığımız için bu mümkün değildir.

x dizisi, x = P-1 olmadıkça 2 olamaz, çünkü bu, P'nin asal olması gerektiği kuralını ihlal eder.

Yukarıdaki önermeden, (picker * init) % P yinelemesinin en az (P-1)/2 döngü uzunluğuna sahip olacağını görebiliriz. Bunun nedeni, P'yi ikinin daha yüksek kuvvetine yaklaşık olarak eşit olan güvenli bir asal sayı olarak seçmemiz ve init'in [2,2**256+1] aralığında olmasıdır. P'nin büyüklüğü göz önüne alındığında, modüler üstelleştirmeden asla bir döngü beklememeliyiz.

DAG'daki ilk hücreyi (init etiketli değişken) atadığımızda, iş kanıtı (sha3 (tohum) + 2, 3, P) olarak hesaplarız. İlk bakışta bu, sonucun ne 1 ne de P-1 olduğunu garanti etmez. Ancak, P-1 güvenli bir asal olduğundan, Gözlem 1'in bir sonucu olan aşağıdaki ek güvenceye sahibiz:

Gözlem 2. x, güvenli bir asal P için ℤ/Pℤ çarpımsal grubunun bir üyesi olsun ve w bir doğal sayı olsun. x mod P ≠ 1 mod P ve x mod P ≠ P-1 mod P ve ayrıca w mod P ≠ P-1 mod P ve w mod P ≠ 0 mod P ise, ardından xʷ mod P ≠ 1 mod P ve xʷ mod P ≠ P-1 mod P

Karma işlevi olarak modüler üstel alma

Belirli P ve w değerleri için, pow(x, w, P) işlevinin birçok çakışması olabilir. Örneğin, pow(x,9,19) yalnızca {1,18} değerlerini alır.

P asal sayı olarak kabul edildiğinde, modüler üs alma karma fonksiyonu için uygun w aşağıdaki sonucu kullanarak seçilebilir:

Gözlem 3. P asal olsun; w ve P-1, ancak ve ancak tüm a ve b, ℤ/Pℤ içinde ise nispeten asaldır:

`aʷ mod P ≡ bʷ mod P` if and only if `a mod P ≡ b mod P`

Bu nedenle, P'nin asal olduğu ve w'un P-1'e görece asal olduğu göz önüne alındığında, şu |{pow(x, w, P) : x ∈ ℤ}| = P, hash fonksiyonunun mümkün olan minimum çarpışma oranına sahip olduğunu ima eder.

P'nin seçtiğimiz gibi güvenli bir asal olması özel durumunda, o zaman P-1'in sadece 1, 2, (P-1)/2 ve P-1 faktörleri vardır. P'den beri > 7'de, 3'ün P-1'e göre asal olduğunu biliyoruz, dolayısıyla w=3 yukarıdaki önermeyi karşılıyor.

Daha verimli önbellek tabanlı değerlendirme algoritması

1def quick_calc(params, seed, p):
2    cache = produce_dag(params, seed, params["cache_size"])
3    return quick_calc_cached(cache, params, p)
4
5def quick_calc_cached(cache, params, p):
6    P = params["P"]
7    if p < len(cache):
8        return cache[p]
9    else:
10        x = pow(cache[0], p + 1, P)
11        for _ in range(params["k"]):
12            x ^= quick_calc_cached(cache, params, x % p)
13        return pow(x, params["w"], P)
14
15def quick_hashimoto(seed, dagsize, params, header, nonce):
16    cache = produce_dag(params, seed, params["cache_size"])
17    return quick_hashimoto_cached(cache, dagsize, params, header, nonce)
18
19def quick_hashimoto_cached(cache, dagsize, params, header, nonce):
20    m = dagsize // 2
21    mask = 2**64 - 1
22    mix = sha3(encode_int(nonce) + header)
23    for _ in range(params["accesses"]):
24        mix ^= quick_calc_cached(cache, params, m + (mix & mask) % m)
25    return dbl_sha3(mix)
Tümünü göster
 Kopyala