Dagger-Hashimoto

Dagger-Hashimoto adalah implementasi penelitian dan spesifikasi asli untuk algoritma penambangan Ethereum. Dagger-Hashimoto digantikan oleh Ethash. Penambangan dimatikan sepenuhnya pada The Merge pada tanggal 15 September 2022. Sejak saat itu, Ethereum telah diamankan menggunakan mekanisme proof-of-stake sebagai gantinya. Halaman ini ditujukan untuk kepentingan sejarah - informasi di sini tidak lagi relevan untuk Ethereum pasca-Merge.

Prasyarat

Untuk lebih memahami halaman ini, kami sarankan Anda terlebih dahulu membaca tentang konsensus proof-of-work, penambangan, dan algoritma penambangan.

Dagger-Hashimoto bertujuan untuk memenuhi dua tujuan:

Tahan ASIC: keuntungan dari membuat perangkat keras khusus untuk algoritma ini harus sekecil mungkin
Verifiabilitas klien ringan: sebuah blok harus dapat diverifikasi secara efisien oleh klien ringan.

Dengan modifikasi tambahan, kami juga menentukan cara untuk memenuhi tujuan ketiga jika diinginkan, tetapi dengan mengorbankan kompleksitas tambahan:

Penyimpanan rantai penuh: penambangan harus memerlukan penyimpanan status blockchain yang lengkap (karena struktur trie status Ethereum yang tidak teratur, kami mengantisipasi bahwa beberapa pemangkasan akan dimungkinkan, terutama dari beberapa kontrak yang sering digunakan, tetapi kami ingin meminimalkan hal ini).

Pembuatan DAG

Kode untuk algoritma ini akan didefinisikan dalam Python di bawah ini. Pertama, kami memberikan encode_int untuk menyusun int tak bertanda (unsigned int) dengan presisi tertentu menjadi string. Kebalikannya juga diberikan:

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
Tampilkan semua

Selanjutnya kami mengasumsikan bahwa sha3 adalah fungsi yang mengambil bilangan bulat dan menghasilkan bilangan bulat, dan dbl_sha3 adalah fungsi double-sha3; jika mengonversi kode referensi ini menjadi implementasi, gunakan:

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)))
Tampilkan semua

Parameter

Parameter yang digunakan untuk algoritma ini adalah:

1SAFE_PRIME_512 = 2**512 - 38117     # Largest Safe Prime less than 2**512 # Bilangan prima aman terbesar yang kurang dari 2**512
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS,  # Size of the dataset (4 Gigabytes); MUST BE MULTIPLE OF 65536 # Ukuran dataset (4 Gigabita); HARUS KELIPATAN 65536
5      "n_inc": 65536,                   # Increment in value of n per period; MUST BE MULTIPLE OF 65536 # Peningkatan nilai n per periode; HARUS KELIPATAN 65536
6                                        # with epochtime=20000 gives 882 MB growth per year # dengan epochtime=20000 memberikan pertumbuhan 882 MB per tahun
7      "cache_size": 2500,               # Size of the light client's cache (can be chosen by light # Ukuran cache klien ringan (dapat dipilih oleh klien
8                                        # client; not part of the algo spec) # ringan; bukan bagian dari spesifikasi algoritma)
9      "diff": 2**14,                    # Difficulty (adjusted during block evaluation) # Tingkat kesulitan (disesuaikan selama evaluasi blok)
10      "epochtime": 100000,              # Length of an epoch in blocks (how often the dataset is updated) # Panjang epoch dalam blok (seberapa sering dataset diperbarui)
11      "k": 1,                           # Number of parents of a node # Jumlah induk dari sebuah node
12      "w": w,                          # Used for modular exponentiation hashing # Digunakan untuk hash eksponensiasi modular
13      "accesses": 200,                  # Number of dataset accesses during hashimoto # Jumlah akses dataset selama hashimoto
14      "P": SAFE_PRIME_512               # Safe Prime for hashing and random number generation # Bilangan prima aman untuk hash dan pembuatan angka acak
15}
Tampilkan semua

P dalam hal ini adalah bilangan prima yang dipilih sedemikian rupa sehingga log₂(P) hanya sedikit kurang dari 512, yang sesuai dengan 512 bit yang telah kami gunakan untuk merepresentasikan angka-angka kami. Perhatikan bahwa hanya paruh kedua dari DAG yang sebenarnya perlu disimpan, sehingga kebutuhan RAM de-facto dimulai pada 1 GB dan tumbuh sebesar 441 MB per tahun.

Pembuatan grafik Dagger

Primitif pembuatan grafik dagger didefinisikan sebagai berikut:

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
Tampilkan semua

Pada dasarnya, ini memulai grafik sebagai node tunggal, sha3(seed), dan dari sana mulai menambahkan node lain secara berurutan berdasarkan node sebelumnya yang acak. Ketika node baru dibuat, pangkat modular dari seed dihitung untuk memilih secara acak beberapa indeks yang kurang dari i (menggunakan x % i di atas), dan nilai node pada indeks tersebut digunakan dalam perhitungan untuk menghasilkan nilai baru untuk x, yang kemudian dimasukkan ke dalam fungsi proof-of-work kecil (berdasarkan XOR) untuk pada akhirnya menghasilkan nilai grafik pada indeks i. Alasan di balik desain khusus ini adalah untuk memaksa akses berurutan dari DAG; nilai DAG berikutnya yang akan diakses tidak dapat ditentukan sampai nilai saat ini diketahui. Terakhir, eksponensiasi modular melakukan hash pada hasilnya lebih lanjut.

Algoritma ini bergantung pada beberapa hasil dari teori bilangan. Lihat lampiran di bawah ini untuk pembahasannya.

Evaluasi klien ringan

Konstruksi grafik di atas bermaksud untuk memungkinkan setiap node dalam grafik direkonstruksi dengan menghitung sub-pohon yang hanya terdiri dari sejumlah kecil node dan hanya membutuhkan sejumlah kecil memori tambahan. Perhatikan bahwa dengan k=1, sub-pohon tersebut hanyalah rantai nilai yang naik ke elemen pertama dalam DAG.

Fungsi komputasi klien ringan untuk DAG bekerja sebagai berikut:

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)
Tampilkan semua

Pada dasarnya, ini hanyalah penulisan ulang dari algoritma di atas yang menghapus perulangan komputasi nilai untuk seluruh DAG dan mengganti pencarian node sebelumnya dengan panggilan rekursif atau pencarian cache. Perhatikan bahwa untuk k=1 cache tidak diperlukan, meskipun pengoptimalan lebih lanjut sebenarnya melakukan prakomputasi beberapa ribu nilai pertama dari DAG dan menyimpannya sebagai cache statis untuk komputasi; lihat lampiran untuk implementasi kode dari hal ini.

Buffer ganda DAG

Dalam klien penuh, buffer ganda (opens in a new tab) dari 2 DAG yang dihasilkan oleh rumus di atas digunakan. Idenya adalah bahwa DAG diproduksi setiap jumlah blok epochtime sesuai dengan parameter di atas. Alih-alih klien menggunakan DAG terbaru yang diproduksi, klien menggunakan yang sebelumnya. Manfaat dari hal ini adalah memungkinkan DAG diganti seiring waktu tanpa perlu memasukkan langkah di mana penambang harus tiba-tiba menghitung ulang semua data. Jika tidak, ada potensi perlambatan sementara yang tiba-tiba dalam pemrosesan rantai pada interval reguler dan secara dramatis meningkatkan sentralisasi. Dengan demikian, risiko serangan 51% dalam beberapa menit sebelum semua data dihitung ulang.

Algoritma yang digunakan untuk menghasilkan kumpulan DAG yang digunakan untuk menghitung pekerjaan untuk sebuah blok adalah sebagai berikut:

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 # Tidak memungkinkan adanya back buffer, cukup buat 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"]}}
Tampilkan semua

Hashimoto

Ide di balik Hashimoto asli adalah menggunakan blockchain sebagai kumpulan data, melakukan komputasi yang memilih N indeks dari blockchain, mengumpulkan transaksi pada indeks tersebut, melakukan XOR dari data ini, dan mengembalikan hash dari hasilnya. Algoritma asli Thaddeus Dryja, yang diterjemahkan ke Python untuk konsistensi, adalah sebagai berikut:

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)

Sayangnya, meskipun Hashimoto dianggap sulit secara RAM, ia bergantung pada aritmatika 256-bit, yang memiliki overhead komputasi yang cukup besar. Namun, Dagger-Hashimoto hanya menggunakan 64 bit paling tidak signifikan saat mengindeks kumpulan datanya untuk mengatasi masalah ini.

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)

Penggunaan SHA3 ganda memungkinkan bentuk pra-verifikasi tanpa data yang hampir instan, hanya memverifikasi bahwa nilai perantara yang benar telah diberikan. Lapisan luar proof-of-work ini sangat ramah ASIC dan cukup lemah, tetapi ada untuk membuat DDoS menjadi lebih sulit karena sejumlah kecil pekerjaan tersebut harus dilakukan untuk menghasilkan blok yang tidak akan langsung ditolak. Berikut adalah versi klien ringan:

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)

Penambangan dan verifikasi

Sekarang, mari kita gabungkan semuanya ke dalam algoritma penambangan:

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
Tampilkan semua

Berikut adalah algoritma verifikasinya:

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

Verifikasi yang ramah klien ringan:

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

Selain itu, perhatikan bahwa Dagger-Hashimoto memberlakukan persyaratan tambahan pada header blok:

Agar verifikasi dua lapis berfungsi, header blok harus memiliki nonce dan nilai tengah pra-sha3
Di suatu tempat, header blok harus menyimpan sha3 dari seedset saat ini

Bacaan lebih lanjut

Tahu tentang sumber daya komunitas yang membantu Anda? Edit halaman ini dan tambahkan!

Lampiran

Seperti yang dicatat di atas, RNG yang digunakan untuk pembuatan DAG bergantung pada beberapa hasil dari teori bilangan. Pertama, kami memberikan jaminan bahwa Lehmer RNG yang menjadi dasar untuk variabel picker memiliki periode yang luas. Kedua, kami menunjukkan bahwa pow(x,3,P) tidak akan memetakan x ke 1 atau P-1 asalkan x ∈ [2,P-2] untuk memulai. Terakhir, kami menunjukkan bahwa pow(x,3,P) memiliki tingkat tabrakan yang rendah ketika diperlakukan sebagai fungsi hashing.

Generator angka acak Lehmer

Meskipun fungsi produce_dag tidak perlu menghasilkan angka acak yang tidak bias, potensi ancamannya adalah bahwa seed**i % P hanya mengambil segelintir nilai. Hal ini dapat memberikan keuntungan bagi penambang yang mengenali pola tersebut dibandingkan dengan mereka yang tidak.

Untuk menghindari hal ini, hasil dari teori bilangan digunakan. Sebuah Safe Prime (opens in a new tab) didefinisikan sebagai bilangan prima P sedemikian rupa sehingga (P-1)/2 juga merupakan bilangan prima. Orde dari anggota x dari grup perkalian (opens in a new tab) ℤ/nℤ didefinisikan sebagai m minimal sedemikian rupa sehingga

xᵐ mod P ≡ 1

Mengingat definisi ini, kita memiliki:

Pengamatan 1. Misalkan x menjadi anggota grup perkalian ℤ/Pℤ untuk safe prime P. Jika x mod P ≠ 1 mod P dan x mod P ≠ P-1 mod P, maka orde dari x adalah P-1 atau (P-1)/2.

Bukti. Karena P adalah safe prime, maka berdasarkan [Teorema Lagrange][lagrange] kita memiliki bahwa orde dari x adalah 1, 2, (P-1)/2, atau P-1.

Orde dari x tidak bisa 1, karena berdasarkan Teorema Kecil Fermat kita memiliki:

x^P-1 mod P ≡ 1

Oleh karena itu x harus menjadi identitas perkalian dari ℤ/nℤ, yang mana unik. Karena kita mengasumsikan bahwa x ≠ 1 berdasarkan asumsi, hal ini tidak mungkin.

Orde dari x tidak bisa 2 kecuali x = P-1, karena ini akan melanggar bahwa P adalah bilangan prima.

Dari proposisi di atas, kita dapat mengenali bahwa mengulangi (picker * init) % P akan memiliki panjang siklus setidaknya (P-1)/2. Ini karena kita memilih P sebagai safe prime yang kira-kira sama dengan pangkat dua yang lebih tinggi, dan init berada dalam interval [2,2**256+1]. Mengingat besarnya P, kita seharusnya tidak pernah mengharapkan siklus dari eksponensiasi modular.

Ketika kita menetapkan sel pertama dalam DAG (variabel berlabel init), kita menghitung pow(sha3(seed) + 2, 3, P). Sekilas, ini tidak menjamin bahwa hasilnya bukan 1 maupun P-1. Namun, karena P-1 adalah safe prime, kita memiliki jaminan tambahan berikut, yang merupakan akibat wajar dari Pengamatan 1:

Pengamatan 2. Misalkan x menjadi anggota grup perkalian ℤ/Pℤ untuk safe prime P, dan misalkan w menjadi bilangan asli. Jika x mod P ≠ 1 mod P dan x mod P ≠ P-1 mod P, serta w mod P ≠ P-1 mod P dan w mod P ≠ 0 mod P, maka xʷ mod P ≠ 1 mod P dan xʷ mod P ≠ P-1 mod P

Eksponensiasi modular sebagai fungsi hash

Untuk nilai P dan w tertentu, fungsi pow(x, w, P) mungkin memiliki banyak tabrakan. Misalnya, pow(x,9,19) hanya mengambil nilai {1,18}.

Mengingat bahwa P adalah bilangan prima, maka w yang sesuai untuk fungsi hashing eksponensiasi modular dapat dipilih menggunakan hasil berikut:

Pengamatan 3. Misalkan P adalah bilangan prima; w dan P-1 relatif prima jika dan hanya jika untuk semua a dan b dalam ℤ/Pℤ:
aʷ mod P ≡ bʷ mod P jika dan hanya jika a mod P ≡ b mod P

Dengan demikian, mengingat bahwa P adalah bilangan prima dan w relatif prima terhadap P-1, kita memiliki bahwa |{pow(x, w, P) : x ∈ ℤ}| = P, yang menyiratkan bahwa fungsi hashing memiliki tingkat tabrakan minimal yang mungkin.

Dalam kasus khusus bahwa P adalah safe prime seperti yang telah kita pilih, maka P-1 hanya memiliki faktor 1, 2, (P-1)/2 dan P-1. Karena P > 7, kita tahu bahwa 3 relatif prima terhadap P-1, oleh karena itu w=3 memenuhi proposisi di atas.

Algoritma evaluasi berbasis cache yang lebih efisien

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)
Tampilkan semua

Dagger-Hashimoto

Prasyarat