ダガーハシモト

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

前提知識

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

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

ASIC耐性: アルゴリズム専用ハードウェアの製作によって得られる利益を、最小限にすること。
ライトクライアントの検証可能性: ライトクライアントがブロックを効率的に検証可能であること。

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

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

有向非巡回グラフ(DAG)の生成

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

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
すべて表示
 コピー

次にsha3は、整数を引数に取り、整数を出力する関数とします。dbl_sha3は、倍精度浮動小数点数型のsha3関数とします。このレファレンスのコードを、実装する場合は次のように使います。

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)))
すべて表示
 コピー

パラメータ

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

1SAFE_PRIME_512 = 2**512 - 38117     # Largest Safe Prime less than 2**512
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS,  # Size of the dataset (4 Gigabytes); MUST BE MULTIPLE OF 65536
5      "n_inc": 65536,                   # Increment in value of n per period; MUST BE MULTIPLE OF 65536
6                                        # with epochtime=20000 gives 882 MB growth per year
7      "cache_size": 2500,               # Size of the light client's cache (can be chosen by light
8                                        # client; not part of the algo spec)
9      "diff": 2**14,                    # Difficulty (adjusted during block evaluation)
10      "epochtime": 100000,              # Length of an epoch in blocks (how often the dataset is updated)
11      "k": 1,                           # Number of parents of a node
12      "w": w,                          # Used for modular exponentiation hashing
13      "accesses": 200,                  # Number of dataset accesses during hashimoto
14      "P": SAFE_PRIME_512               # Safe Prime for hashing and random number generation
15}
すべて表示
 コピー

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

ダガーグラフの構築

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

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
すべて表示
 コピー

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

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

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

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

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

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)
すべて表示
 コピー

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

有向非巡回グラフ(DAG)のダブルバッファ

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

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

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"]}}
すべて表示
 コピー

ハシモト

オリジナルのハシモトの背景にあるアイデアは、ブロックチェーンをデータセットとして使用することです。ブロックチェーンからN個のインデックスを選択して計算を実行し、これらのインデックスでトランザクションを収集し、このデータの排他的論理和(XOR)を実行して、結果のハッシュ値を返します。 Thaddeus Dryjaのオリジナルのアルゴリズムは、次のように一貫性のためにPythonでも書かれています。

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)
 コピー

残念ながら、ハシモトはRAMの消費が多いとみなされています。256ビット演算に依存しており、計算にかなりのオーバーヘッドがあります。しかし、ダガーハシモトでは、この問題に対処するため、最下位64ビットのみを使用してデータセットのインデックスを作成します。

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)
 コピー

倍精度浮動小数点数型(double) SHA3を使用して、ゼロデータ形式、ほぼ即時の事前検証、提供された正しい中間値のみの検証などが可能です。このプルーフ・オブ・ワークの外側のレイヤーは、ASICと相性が非常に良く、かなり脆弱になってます。しかし、すぐに拒否されないブロックを生成するには、少量のワークをしなければならないため、DDoS攻撃をさらに困難にします。以下は、ライトクライアントのバージョンです。

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)
 コピー

マイニングと検証

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

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
すべて表示
 コピー

以下は、検証アルゴリズムです。

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
 コピー

以下は、ライトクライアントフレンドリーな検証です。

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
 コピー

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

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

参考文献

役に立つコミュニティリソースをご存知の場合は、このページを編集して追加してください。

付録

前述のように、DAGの生成で使われる乱数発生器(RNG)は、数論から得られた次の結果に依存しています。最初にpicker変数のもととなるレーマー乱数発生器の周期が広いことを断言しておきます。次に、pow(x,3,P)は、 x ∈ [2,P-2]を開始条件として、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)のメンバー xの次数 ℤ/nℤは、次の公式にある小さい字のmで定義されています。

1xᵐ 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になることはできません。フェルマーの小定理により、次を満たすためです。

1xP-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を素数とし、ℤ/Pℤのすべてのaかつbにおいて、そのときに限りwかつP-1が互いに素であることが成り立ち、これは次のようになります。
`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は、上記の命題を満たします。

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

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)
すべて表示
 コピー

ダガーハシモト

前提知識