メインコンテンツへスキップ
Change page

ダガーハシモト

ページを編集 (opens in a new tab)

ダガーハシモト(Dagger-Hashimoto)は、イーサリアムのマイニングアルゴリズムの最初の研究実装と仕様でした。 Dagger-Hashimotoは、Ethashに取って代わられました。 2022年9月15日のThe Mergeで、マイニングは完全に停止されました。 それ以来、イーサリアムは代わりにプルーフ・オブ・ステークのメカニズムを使用して安全性が確保されています。 このページについては過去の流れを理解する目的でご覧ください。この情報は、マージ後のイーサリアムには該当しません。

前提条件

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

Dagger-Hashimoto

ダガーハシモトは、次の2つの目的を達成することを目指しています。

  1. ASIC耐性: アルゴリズム専用のハードウェアを作成することで得られるメリットを、可能な限り小さくすること。
  2. ライトクライアントの検証可能性: ライトクライアントがブロックを効率的に検証できること。

追加の修正により、ご希望に応じて、3つ目の目標を達成する方法も記載しますが、複雑になります。

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

DAGの生成

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

次に、sha3が整数を受け取って整数を出力する関数であり、dbl_sha3が2重のsha3関数であると仮定します。このリファレンスコードを実装に変換する場合は、以下を使用してください。

パラメータ

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

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

Daggerグラフの構築

原始的なダガーグラフの構築は、以下のように定義できます。

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

このアルゴリズムは、数論から得られたいくつかの結果に依存しています。 考察については、ページ下部にある付録を参照してください。

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

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

ライトクライアントのDAG計算関数は、次のように動作します。

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

DAGのダブルバッファ

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

ブロックのワークを計算するために使われるDAGセットを生成するために使用するアルゴリズムは、次のようになります。

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)

残念ながら、ハシモトはRAMの消費が多いとみなされています。256ビット演算に依存しており、計算にかなりのオーバーヘッドがあります。 しかし、ダガーハシモトでは、この問題に対処するため、最下位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)

倍精度浮動小数点数型(double) SHA3を使用して、ゼロデータ形式、ほぼ即時の事前検証、提供された正しい中間値のみの検証などが可能です。 このプルーフ・オブ・ワークの外側のレイヤーは、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 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

また、ダガーハシモトは、ブロックヘッダに次の追加の要件を課していることに注意してください。

  • 2層検証が機能するためには、ブロックヘッダーに、ノンス (nonce)と、前にsha3だった中間値の両方が含まれている必要がある。
  • ブロックヘッダーのどこかに、現在のシードセットのsha3が格納されている必要がある。

参考リンク

役に立つコミュニティリソースを知っていますか? Edit this page and add it!

付録

前述のように、DAGの生成で使われる乱数発生器(RNG)は、数論から得られた次の結果に依存しています。 まず、picker 変数の基礎となるレーマー乱数生成器が長い周期を持つことを保証します。 次に、x ∈ [2,P-2] で始まる場合、pow(x,3,P) が x を 1 または P-1 にマッピングしないことを示します。 最後に、pow(x,3,P) がハッシュ関数として扱われた場合に、低い衝突率を持つことを示します。

レーマー乱数生成器

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

これを避けるために、数論による結果を使う必要があります。 安全素数 (opens in a new tab)は、(P-1)/2 もまた素数であるような素数 P として定義されます。 乗法群 (opens in a new tab) ℤ/nℤ のメンバー x の_位数_は、

xᵐ mod P ≡ 1
となる最小の m として定義されます。 これらの定義を前提として、以下が成り立ちます。

見解1. 安全素数 P について、x を乗法群 ℤ/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 になることはありません。

xP-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. 安全素数 P について、x を乗法群 ℤ/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 は上記の命題を満たします。

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

ページの最終更新: 2026年4月3日

HiroyukiNaitoH (opens in a new tab)
_Sakura__ (opens in a new tab)
lukassiml (opens in a new tab)
+4

この記事は役に立ちましたか？