Dagger-Hashimoto

Dagger-Hashimoto, Ethereum'un madencilik algoritması için orijinal araştırma uygulaması ve şartnamesiydi. Dagger-Hashimoto'nun yerini Ethash almıştır. 15 Eylül 2022'deki Birleşim ile madencilik tamamen durduruldu. O zamandan beri Ethereum, bunun yerine bir hisse ispatı mekanizması kullanılarak güvence altına alınmıştı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ş ispatı mutabakatı, madencilik ve madencilik algoritmaları hakkında bilgi edinmenizi öneririz.

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

ASIC direnci: algoritma için özel donanım oluşturmanın faydası mümkün olduğunca az olmalıdır
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, tüm blokzincir durumunun depolanmasını gerektirmelidir (Ethereum durum ağacı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 aza indirmek istiyoruz).

DAG Üretimi

Algoritmanın kodu aşağıdaki Python'da tanımlanacaktır. İlk olarak, belirtilen hassasiyetteki işaretsiz tam sayıları dizelere sıralamak için encode_int veriyoruz. Tersi de aşağıda verilmiştir:

1NUM_BITS = 512
2
3def encode_int(x):
4    "Bir tamsayı x'i büyük endian şeması kullanarak 64 karakterlik bir dize olarak kodlayın"
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    "Büyük endian şeması kullanarak bir dizeden bir x tamsayısının kodunu çözün"
13    x = 0
14    for c in s:
15        x *= 256
16        x += ord(c)
17    return x
Tümünü göster

Ardından, sha3'ün bir tam sayı alıp bir tam sayı çıktısı veren bir işlev ve dbl_sha3'ün bir çift sha3 işlevi olduğunu varsayıyoruz; bu referans kodu bir uygulamaya dönüştürüyorsanız, şunu kullanın:

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

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

Bu durumda P, log₂(P)'nin 512'den biraz daha küçük olacak şekilde seçilmiş bir asal sayıdır, bu da 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 oluşturma

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

Esasen, bir grafiği tek bir düğüm olan sha3(seed) olarak başlatır ve oradan rastgele önceki düğümlere dayalı olarak diğer düğümleri sırayla eklemeye başlar. Yeni bir düğüm oluşturulduğunda, i'den küçük bazı dizinleri rastgele seçmek için tohumun modüler bir gücü hesaplanır (yukarıdaki x % i kullanılarak) ve bu dizinlerdeki düğümlerin değerleri, x için yeni bir değer oluşturmak üzere bir hesaplamada kullanılır, bu da nihai olarak i dizinindeki grafiğin değerini oluşturmak için küçük bir iş ispatı fonksiyonuna (XOR tabanlı) beslenir. 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

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, ancak daha ileri bir optimizasyonun aslında DAG'nin ilk birkaç bin değerini önceden hesapladığını ve bunu hesaplamalar için statik bir önbellek olarak tuttuğunu unutmayın; bunun bir kod uygulaması için eke bakın.

DAG'lerin çift arabelleği

Tam bir istemcide, yukarıdaki formülle üretilen 2 DAG'den oluşan bir çift arabellekopens in a new tab kullanılır. Buradaki fikir, DAG'lerin yukarıdaki parametrelere göre her epochtime blok sayısında üretilmesidir. Ü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

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)

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)

Ç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)

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

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

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

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 kaynak

Size yardımcı olan bir topluluk kaynağı mı biliyorsunuz? 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, başlangıç için x ∈ [2,P-2] sağlandığında pow(x,3,P)'nin x'i 1'e veya P-1'e eşlemeyeceğini gösteriyoruz. Son olarak, pow(x,3,P)'nin bir karma işlevi olarak ele alındığında düşük bir çarpışma oranına sahip olduğunu gösteriyoruz.

Lehmer rastgele sayı üreteci

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. Güvenli Asalopens in a new tab, (P-1)/2 de asal olacak şekilde bir P asalı olarak tanımlanır. Çarpımsal grupopens in a new tab ℤ/nℤ'nin bir x üyesinin mertebesi,

xᵐ mod P ≡ 1

olacak şekildeki minimum m olarak tanımlanır. Bu tanımlar göz önüne alındığında, elimizde şunlar vardır:

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

Kanıt. P güvenli bir asal olduğundan, [Lagrange Teoremi][lagrange] gereğince x'in mertebesinin 1, 2, (P-1)/2 veya P-1 olduğunu söyleyebiliriz.

x'in mertebesi 1 olamaz, çünkü Fermat'nın Küçük Teoremi'ne göre elimizde şu vardır:

x^P-1 mod P ≡ 1

Dolayısıyla x, benzersiz olan ℤ/nℤ'nin bir çarpımsal birimi olmalıdır. Varsayım gereği x ≠ 1 olduğunu varsaydığımız için bu mümkün değildir.

x'in mertebesi x = P-1 olmadıkça 2 olamaz, çünkü bu P'nin asal olması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 bir kuvvetine yaklaşık olarak eşit olan güvenli bir asal 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 üs almadan asla bir döngü beklememeliyiz.

DAG'deki ilk hücreyi (etiketi init olan değişken) atarken, pow(sha3(seed) + 2, 3, P) 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 P asalı için ℤ/Pℤ çarpımsal grubunun bir üyesi ve w bir doğal sayı olsun. Eğer x mod P ≠ 1 mod P ve x mod P ≠ P-1 mod P ise, ayrıca w mod P ≠ P-1 mod P ve w mod P ≠ 0 mod P ise, o zaman xʷ mod P ≠ 1 mod P ve xʷ mod P ≠ P-1 mod P olur.

Karma işlevi olarak modüler üs 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 olduğundan, modüler üs alma karma işlevi için uygun bir w, aşağıdaki sonuç kullanılarak seçilebilir:

Gözlem 3. P bir asal sayı olsun; w ve P-1'in aralarında asal olması için gerek ve yeter koşul, ℤ/Pℤ'deki tüm a ve b için şudur:
aʷ mod P ≡ bʷ mod P olması için gerek ve yeter koşul a mod P ≡ b mod P olmasıdır

Dolayısıyla, P asal ve w, P-1 ile aralarında asal olduğunda, |{pow(x, w, P) : x ∈ ℤ}| = P olur, bu da karma işlevinin mümkün olan en düşük çarpışma oranına sahip olduğu anlamına gelir.

P'nin seçtiğimiz gibi güvenli bir asal olduğu özel durumda, P-1 yalnızca 1, 2, (P-1)/2 ve P-1 çarpanlarına sahiptir. P > 7 olduğundan, 3'ün P-1 ile aralarında asal olduğunu biliyoruz, dolayısıyla w=3 yukarıdaki önermeyi sağlar.

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

Dagger-Hashimoto

Ön Koşullar