Dagger-Hashimoto

Dagger-Hashimotoは、イーサリアムのマイニング・アルゴリズムの初期の研究実装および仕様でした。Dagger-Hashimotoはイーサッシュに取って代わられました。2022年9月15日のマージにより、マイニングは完全に停止されました。それ以降、イーサリアムは代わりにプルーフ・オブ・ステーク (PoS)メカニズムを使用して保護されています。このページは歴史的な関心のために残されており、ここにある情報はマージ後のイーサリアムにはもはや関連していません。

前提条件

このページをよりよく理解するために、まずはプルーフ・オブ・ワーク (PoW) コンセンサス、マイニング、およびマイニング・アルゴリズムについて読むことをお勧めします。

Dagger-Hashimoto

Dagger-Hashimotoは、次の2つの目標を満たすことを目指しています。

ASIC耐性: アルゴリズムに特化したハードウェアを作成することによる利益を可能な限り小さくすること。
ライト・クライアントの検証可能性: ブロックがライト・クライアントによって効率的に検証可能であること。

追加の変更を加えることで、必要に応じて3つ目の目標を達成する方法も指定しますが、複雑さが増すという代償が伴います。

完全なチェーン・ストレージ: マイニングには完全なブロックチェーンの状態の保存が必要であること (イーサリアムのステート・トライの不規則な構造のため、特によく使用される一部のコントラクトについてはある程度のプルーニングが可能であると予想されますが、これを最小限に抑えたいと考えています)。

DAGの生成

アルゴリズムのコードは、以下でPythonを使用して定義されます。まず、指定された精度の符号なし整数を文字列にマーシャリングするためのencode_intを示します。その逆も示します。

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

次に、sha3は整数を受け取って整数を出力する関数であり、dbl_sha3はダブルSHA-3関数であると仮定します。このリファレンス・コードを実装に変換する場合は、次を使用します。

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

パラメーター

アルゴリズムで使用されるパラメーターは次のとおりです。

SAFE_PRIME_512 = 2**512 - 38117     # 2**512未満の最大の安全素数

params = {
      "n": 4000055296 * 8 // NUM_BITS,  # データセットのサイズ（4ギガバイト）。65536の倍数でなければならない
      "n_inc": 65536,                   # 期間ごとのnの値の増分。65536の倍数でなければならない
                                        # epochtime=20000の場合、年間882MBの増加となる
      "cache_size": 2500,               # ライト・クライアントのキャッシュのサイズ（ライト・
                                        # クライアントが選択可能。アルゴリズム仕様の一部ではない）
      "diff": 2**14,                    # 難易度（ブロック評価中に調整される）
      "epochtime": 100000,              # ブロック単位でのエポックの長さ（データセットが更新される頻度）
      "k": 1,                           # ノードの親の数
      "w": w,                          # べき剰余のハッシュ化に使用される
      "accesses": 200,                  # hashimoto実行中のデータセットへのアクセス数
      "P": SAFE_PRIME_512               # ハッシュ化と乱数生成のための安全素数
}

この場合のPは、log₂(P)が512よりわずかに小さくなるように選ばれた素数であり、これは数値を表現するために使用してきた512ビットに対応します。実際に保存する必要があるのはDAGの後半部分のみであるため、事実上のRAM要件は1 GBから始まり、年間441 MBずつ増加することに注意してください。

Daggerグラフの構築

Daggerグラフ構築のプリミティブは次のように定義されます。

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

基本的に、グラフは単一のノードsha3(seed)として開始され、そこからランダムな以前のノードに基づいて他のノードを順次追加し始めます。新しいノードが作成されると、シードのモジュラー累乗が計算され、i未満のいくつかのインデックスがランダムに選択されます (上記のx % iを使用)。そして、それらのインデックスにあるノードの値が計算に使用されてxの新しい値が生成され、それが小さなプルーフ・オブ・ワーク関数 (XORに基づく) に入力されて、最終的にインデックスiでのグラフの値が生成されます。この特定の設計の背後にある理論的根拠は、DAGへのシーケンシャル・アクセスを強制することです。アクセスされるDAGの次の値は、現在の値がわかるまで決定できません。最後に、モジュラーべき乗によって結果がさらにハッシュ化されます。

このアルゴリズムは、数論のいくつかの結果に依存しています。詳細については、以下の付録を参照してください。

ライト・クライアントの評価

上記のグラフ構築は、少数のノードのサブツリーのみを計算し、少量の補助メモリのみを必要とすることで、グラフ内の各ノードを再構築できるようにすることを意図しています。k=1の場合、サブツリーはDAGの最初の要素まで遡る値のチェーンにすぎないことに注意してください。

DAGのライト・クライアント計算関数は次のように機能します。

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)

基本的に、これは上記のアルゴリズムを書き直したものであり、DAG全体の値を計算するループを削除し、以前のノードのルックアップを再帰呼び出しまたはキャッシュ・ルックアップに置き換えただけです。k=1の場合、キャッシュは不要であることに注意してください。ただし、さらなる最適化として、実際にはDAGの最初の数千の値を事前計算し、それを計算用の静的キャッシュとして保持します。これのコード実装については付録を参照してください。

DAGのダブル・バッファ

フル・クライアントでは、上記の式によって生成された2つのDAGのダブル・バッファ (opens in a new tab)が使用されます。その考え方は、上記のパラメーターに従って、epochtimeブロックごとにDAGが生成されるというものです。クライアントは生成された最新のDAGを使用するのではなく、1つ前のDAGを使用します。これの利点は、マイナーが突然すべてのデータを再計算しなければならないステップを組み込むことなく、時間の経過とともにDAGを置き換えることができることです。そうしないと、一定の間隔でチェーン処理が突然一時的に遅くなり、中央集権化が劇的に進む可能性があります。したがって、すべてのデータが再計算されるまでの数分間に51%攻撃のリスクが生じます。

ブロックの作業を計算するために使用されるDAGのセットを生成するアルゴリズムは次のとおりです。

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:
        # バックバッファは不可能であり、フロントバッファのみを作成する
        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

元のHashimotoの背後にある考え方は、ブロックチェーンをデータセットとして使用し、ブロックチェーンからN個のインデックスを選択し、それらのインデックスにあるトランザクションを収集し、このデータのXORを実行して、結果のハッシュを返す計算を実行することです。Thaddeus Dryjaの元のアルゴリズムを、一貫性のためにPythonに翻訳したものは次のとおりです。

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)

残念ながら、HashimotoはRAMハードであると考えられていますが、256ビットの演算に依存しているため、かなりの計算オーバーヘッドがあります。ただし、Dagger-Hashimotoは、この問題に対処するために、データセットのインデックスを作成する際に最下位の64ビットのみを使用します。

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)

ダブルSHA-3を使用することで、正しい中間値が提供されたことのみを検証する、ゼロデータでほぼ瞬時の事前検証の形式が可能になります。このプルーフ・オブ・ワークの外側のレイヤーは、非常にASICフレンドリーでかなり弱いですが、すぐに拒否されないブロックを生成するためにはその少量の作業を行う必要があるため、DDoS攻撃をさらに困難にするために存在します。ライト・クライアント版は次のとおりです。

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)

マイニングと検証

では、これらすべてをマイニング・アルゴリズムにまとめてみましょう。

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

検証アルゴリズムは次のとおりです。

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

ライト・クライアント向けの検証:

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

また、Dagger-Hashimotoはブロック・ヘッダーに追加の要件を課すことに注意してください。

2層の検証が機能するためには、ブロック・ヘッダーにナンスとSHA-3適用前の中間値の両方が含まれている必要があります。
ブロック・ヘッダーのどこかに、現在のシードセットのSHA-3を保存する必要があります。

参考文献

役に立ったコミュニティ・リソースをご存知ですか？このページを編集して追加してください！

付録

上記のように、DAGの生成に使用されるRNG (乱数生成器) は、数論のいくつかの結果に依存しています。まず、picker変数の基礎となるLehmer RNGが広い周期を持つことを保証します。次に、開始時にx ∈ [2,P-2]が与えられた場合、pow(x,3,P)がxを1またはP-1にマッピングしないことを示します。最後に、pow(x,3,P)をハッシュ関数として扱った場合、衝突率が低いことを示します。

Lehmer乱数生成器

produce_dag関数は偏りのない乱数を生成する必要はありませんが、潜在的な脅威として、seed**i % Pがごくわずかな値しか取らないことが挙げられます。これにより、パターンを認識しているマイナーが、そうでないマイナーよりも有利になる可能性があります。

これを回避するために、数論の結果を利用します。安全素数 (Safe Prime) (opens in a new tab)は、(P-1)/2も素数となるような素数Pとして定義されます。乗法群 (opens in a new tab)ℤ/nℤの要素xの_位数 (order)_ は、次を満たす最小のmとして定義されます。

xᵐ mod P ≡ 1

これらの定義に基づき、次のことが成り立ちます。

観察1. xを安全素数Pの乗法群ℤ/Pℤの要素とします。x mod P ≠ 1 mod Pかつx mod P ≠ P-1 mod Pである場合、xの位数はP-1または(P-1)/2のいずれかになります。

証明。Pは安全素数であるため、[ラグランジュの定理][lagrange]により、xの位数は1、2、(P-1)/2、またはP-1のいずれかになります。

フェルマーの小定理により次が成り立つため、xの位数は1にはなり得ません。

x^P-1 mod P ≡ 1

したがって、xはℤ/nℤの乗法単位元でなければならず、これは一意です。仮定によりx ≠ 1としているため、これは不可能です。

x = P-1でない限り、xの位数は2にはなり得ません。そうでないと、Pが素数であることに反するからです。

上記の命題から、(picker * init) % Pを反復すると、少なくとも(P-1)/2のサイクル長を持つことがわかります。これは、Pを2のより高い累乗にほぼ等しい安全素数として選択し、initが区間[2,2**256+1]にあるためです。Pの大きさを考慮すると、モジュラーべき乗によるサイクルは決して予想されません。

DAGの最初のセル (initというラベルの変数) を割り当てる際、pow(sha3(seed) + 2, 3, P)を計算します。一見すると、これは結果が1でもP-1でもないことを保証するものではありません。しかし、P-1は安全素数であるため、観察1の系として、次の追加の保証が得られます。

観察2. xを安全素数Pの乗法群ℤ/Pℤの要素とし、wを自然数とします。x mod P ≠ 1 mod Pかつx mod P ≠ P-1 mod Pであり、さらにw mod P ≠ P-1 mod Pかつw mod P ≠ 0 mod Pである場合、xʷ mod P ≠ 1 mod Pかつxʷ mod P ≠ P-1 mod Pとなります。

ハッシュ関数としてのモジュラーべき乗

Pとwの特定の値に対して、関数pow(x, w, P)は多くの衝突を持つ可能性があります。たとえば、pow(x,9,19)は{1,18}の値のみを取ります。

Pが素数であるとすると、モジュラーべき乗ハッシュ関数に適切なwは、次の結果を使用して選択できます。

観察3. Pを素数とします。wとP-1が互いに素であるのは、ℤ/Pℤ内のすべてのaおよびbに対して次が成り立つ場合であり、かつその場合に限ります。
aʷ mod P ≡ bʷ mod Pであるのは、a mod P ≡ b mod Pである場合であり、かつその場合に限ります。

したがって、Pが素数であり、wがP-1と互いに素であるとすると、|{pow(x, w, P) : x ∈ ℤ}| = Pとなり、ハッシュ関数が可能な限り最小の衝突率を持つことを意味します。

選択したようにPが安全素数である特別なケースでは、P-1は1、2、(P-1)/2、およびP-1のみを因数として持ちます。P > 7であるため、3はP-1と互いに素であることがわかります。したがって、w=3は上記の命題を満たします。

より効率的なキャッシュベースの評価アルゴリズム

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)