Dagger-Hashimoto

Dagger-Hashimoto adalah implementasi riset dan spesifikasi asli untuk algoritma penambangan Ethereum. Dagger-Hashimoto digantikan oleh Ethash. Penambangan dimatikan sepenuhnya pada The Merge tanggal 15 September 2022. Sejak saat itu, Ethereum diamankan menggunakan mekanisme Bukti Kepemilikan (PoS) 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 membaca terlebih dahulu tentang konsensus Bukti Kerja (PoW), penambangan, dan algoritma penambangan.

Dagger-Hashimoto

Dagger-Hashimoto bertujuan untuk memenuhi dua tujuan:

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

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

Penyimpanan rantai penuh: penambangan harus mewajibkan penyimpanan state rantai blok yang lengkap (karena struktur trie keadaan Ethereum yang tidak teratur, kami mengantisipasi bahwa beberapa pemangkasan akan dimungkinkan, terutama pada 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 (marshaling) unsigned int dengan presisi tertentu menjadi string. Kebalikannya juga diberikan:

NUM_BITS = 512

def encode_int(x):
    "Encode an integer x as a string of 64 characters using a big-endian scheme"
    o = ''
    for _ in range(NUM_BITS / 8):
        o = chr(x % 256) + o
        x //= 256
    return o

def decode_int(s):
    "Unencode an integer x from a string using a big-endian scheme"
    x = 0
    for c in s:
        x *= 256
        x += ord(c)
    return x

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:

from pyethereum import utils
def sha3(x):
    if isinstance(x, (int, long)):
        x = encode_int(x)
    return decode_int(utils.sha3(x))

def dbl_sha3(x):
    if isinstance(x, (int, long)):
        x = encode_int(x)
    return decode_int(utils.sha3(utils.sha3(x)))

Parameter

Parameter yang digunakan untuk algoritma ini adalah:

SAFE_PRIME_512 = 2**512 - 38117     # Bilangan Prima Aman Terbesar yang kurang dari 2**512

params = {
      "n": 4000055296 * 8 // NUM_BITS,  # Ukuran dataset (4 Gigabyte); WAJIB KELIPATAN DARI 65536
      "n_inc": 65536,                   # Peningkatan nilai n per periode; WAJIB KELIPATAN DARI 65536
                                        # dengan epochtime=20000 memberikan pertumbuhan 882 MB per tahun
      "cache_size": 2500,               # Ukuran cache klien ringan (dapat dipilih oleh klien
                                        # ringan; bukan bagian dari spesifikasi algoritma)
      "diff": 2**14,                    # Tingkat kesulitan (disesuaikan selama evaluasi blok)
      "epochtime": 100000,              # Panjang epoch dalam blok (seberapa sering dataset diperbarui)
      "k": 1,                           # Jumlah induk dari sebuah node
      "w": w,                          # Digunakan untuk proses hash eksponensial modular
      "accesses": 200,                  # Jumlah akses dataset selama hashimoto
      "P": SAFE_PRIME_512               # Bilangan Prima Aman untuk proses hash dan pembuatan angka acak
}

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 dari 1 GB dan bertambah sebesar 441 MB per tahun.

Pembuatan grafik Dagger

Primitif pembuatan grafik Dagger didefinisikan sebagai berikut:

def produce_dag(params, seed, length):
    P = params["P"]
    picker = init = pow(sha3(seed), params["w"], P)
    o = [init]
    for i in range(1, length):
        x = picker = (picker * init) % P
        for _ in range(params["k"]):
            x ^= o[x % i]
        o.append(pow(x, params["w"], P))
    return o

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 bagi x, yang kemudian dimasukkan ke dalam fungsi bukti kerja 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 proses 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:

def quick_calc(params, seed, p):
    w, P = params["w"], params["P"]
    cache = {}

    def quick_calc_cached(p):
        if p in cache:
            pass
        elif p == 0:
            cache[p] = pow(sha3(seed), w, P)
        else:
            x = pow(sha3(seed), (p + 1) * w, P)
            for _ in range(params["k"]):
                x ^= quick_calc_cached(x % p)
            cache[p] = pow(x, w, P)
        return cache[p]

    return quick_calc_cached(p)

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 sejumlah epochtime blok sesuai dengan parameter di atas. Alih-alih klien menggunakan DAG terbaru yang diproduksi, klien menggunakan DAG 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% muncul dalam beberapa menit tersebut sebelum semua data dihitung ulang.

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

def get_prevhash(n):
    from pyethereum.blocks import GENESIS_PREVHASH
    from pyethereum import chain_manager
    if n <= 0:
        return hash_to_int(GENESIS_PREVHASH)
    else:
        prevhash = chain_manager.index.get_block_by_number(n - 1)
        return decode_int(prevhash)

def get_seedset(params, block):
    seedset = {}
    seedset["back_number"] = block.number - (block.number % params["epochtime"])
    seedset["back_hash"] = get_prevhash(seedset["back_number"])
    seedset["front_number"] = max(seedset["back_number"] - params["epochtime"], 0)
    seedset["front_hash"] = get_prevhash(seedset["front_number"])
    return seedset

def get_dagsize(params, block):
    return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]

def get_daggerset(params, block):
    dagsz = get_dagsize(params, block)
    seedset = get_seedset(params, block)
    if seedset["front_hash"] <= 0:
        # Tidak memungkinkan adanya back buffer, cukup buat front buffer
        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
                          "block_number": 0}}
    else:
        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
                          "block_number": seedset["front_number"]},
                "back": {"dag": produce_dag(params, seedset["back_hash"], dagsz),
                         "block_number": seedset["back_number"]}}

Hashimoto

Ide di balik Hashimoto asli adalah menggunakan rantai blok sebagai kumpulan data, melakukan komputasi yang memilih N indeks dari rantai blok, 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:

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)

Sayangnya, meskipun Hashimoto dianggap sulit secara RAM (RAM hard), 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.

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)

Penggunaan double SHA3 memungkinkan bentuk pra-verifikasi tanpa data yang hampir instan, hanya memverifikasi bahwa nilai perantara yang benar telah diberikan. Lapisan luar dari bukti kerja 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 ringannya:

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)

Penambangan dan verifikasi

Sekarang, mari kita gabungkan semuanya ke dalam algoritma penambangan:

def mine(daggerset, params, block):
    from random import randint
    nonce = randint(0, 2**64)
    while 1:
        result = hashimoto(daggerset, get_dagsize(params, block),
                           params, decode_int(block.prevhash), nonce)
        if result * params["diff"] < 2**256:
            break
        nonce += 1
        if nonce >= 2**64:
            nonce = 0
    return nonce

Berikut adalah algoritma verifikasinya:

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

Verifikasi yang ramah klien ringan:

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

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 kumpulan seed (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 (collision rate) yang rendah ketika diperlakukan sebagai fungsi hash.

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. 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

Pengamatan 1. Misalkan x adalah anggota dari 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:

xP-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 mengiterasi (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.

Saat 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 adalah anggota dari grup perkalian ℤ/Pℤ untuk safe prime P, dan misalkan w adalah 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 hash 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 hash memiliki tingkat tabrakan minimal yang mungkin.

Dalam kasus khusus di mana 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

def quick_calc(params, seed, p):
    cache = produce_dag(params, seed, params["cache_size"])
    return quick_calc_cached(cache, params, p)

def quick_calc_cached(cache, params, p):
    P = params["P"]
    if p < len(cache):
        return cache[p]
    else:
        x = pow(cache[0], p + 1, P)
        for _ in range(params["k"]):
            x ^= quick_calc_cached(cache, params, x % p)
        return pow(x, params["w"], P)

def quick_hashimoto(seed, dagsize, params, header, nonce):
    cache = produce_dag(params, seed, params["cache_size"])
    return quick_hashimoto_cached(cache, dagsize, params, header, nonce)

def quick_hashimoto_cached(cache, dagsize, params, header, nonce):
    m = dagsize // 2
    mask = 2**64 - 1
    mix = sha3(encode_int(nonce) + header)
    for _ in range(params["accesses"]):
        mix ^= quick_calc_cached(cache, params, m + (mix & mask) % m)
    return dbl_sha3(mix)

Pembaruan terakhir halaman: 3 April 2026

l (opens in a new tab)

j (opens in a new tab)

c (opens in a new tab)

+2

Lihat kontributor