Ethash
最終編集者: , Invalid DateTime
Ethash(opens in a new tab)は、 ダガーハシモトアルゴリズムの改良版です。 Ethash プルーフ・オブ・ワークは、メモリハード(opens in a new tab)になっており、アルゴリズムで ASIC 耐性が高まると考えられました。 最終的には、Ethash ASIC が開発されましたが、GPU マイニングは、プルーフ・オブ・ワークが停止されるまでが実行可能なオプションでした。 Ethash は現在でも、イーサリアム以外のプルール・オブ・ワーク・ネットワークで他のコインのマイニングに使われています。
Ethash の仕組み
ノンス (nonce)とブロックヘッダーに依存する固定リソースのサブセットを選択する必要があるプルーフ・オブ・ワーク・アルゴリズムで、メモリハードを実現します。 この(数ギガバイトの大きさの)リソースは、DAG と呼ばれます。 DAG は、30000 ブロックごと、エポックと呼ばれる最大 125 時間(約 5.2 日)のウィンドウで、変更されます。また生成にはしばらく時間がかかります。 DAG はブロックの高さのみに依存するため、事前に生成はできますが、そうでない場合、クライアントはブロックの生成プロセスが終わるまで待つ必要があります。 クライアントが事前に DAG を生成してキャッシュしないと、各エポックの遷移で大規模なブロック遅延がネットワークに発生する可能性があります。 プルーフ・オブ・ワークを検証するために、DAG が生成される必要がないことに留意してください。基本的に低 CPU と小さなメモリ両方で検証できます。
アルゴリズムが取る一般的なルートは以下のとおりです。
- シードが存在し、その時点までブロックヘッダーをスキャンすることで、ブロックごとに計算できる。
- シードから16MB の疑似乱数キャッシュを計算できる。 ライトクライアントは、キャッシュを保存する。
- キャッシュから各アイテムがキャッシュの少数のアイテムのみに依存するプロパティを持つ1GB データセットを生成できる。 フルクライアントとマイナーは、データセットを保存する。 データセットは時間とともに線形的に増加する。
- マイニングは、データセットのランダムなスライスを取得し、それらを結 合してハッシュ化する。 検証はキャッシュを使用して必要なデータセットの特定の部分を再生成するため、少ないメモリで実行できる(そのためキャッシュの保存だけ必要)。
大きなデータセットでは、30000 ブロックごとに一度更新されます。マイナーの労力の大部分は、データセットを読み込むことであり、データセットに変更を加えることではありません。
定義
以下の定義を採用しています。
1WORD_BYTES = 4 # bytes in word2DATASET_BYTES_INIT = 2**30 # bytes in dataset at genesis3DATASET_BYTES_GROWTH = 2**23 # dataset growth per epoch4CACHE_BYTES_INIT = 2**24 # bytes in cache at genesis5CACHE_BYTES_GROWTH = 2**17 # cache growth per epoch6CACHE_MULTIPLIER=1024 # Size of the DAG relative to the cache7EPOCH_LENGTH = 30000 # blocks per epoch8MIX_BYTES = 128 # width of mix9HASH_BYTES = 64 # hash length in bytes10DATASET_PARENTS = 256 # number of parents of each dataset element11CACHE_ROUNDS = 3 # number of rounds in cache production12ACCESSES = 64 # number of accesses in hashimoto loop13すべて表示
「SHA3」の使用
イーサリアムの開発は、SHA3 標準の開発と同時期に起こりました。標準プロセスは、最終決定したハッシュアルゴリズムのパディングが遅れて変更されたため、イーサリアムの「sha3_256」および「sha3_512」ハッシュは、標準の sha3 ハッシュではありません。他の文脈の多くでは、変異型として「Keccak-256」および「Keccak-512」と呼ばれています。 この考察については、 こちら(opens in a new tab)、こちら(opens in a new tab)、またはこちら(opens in a new tab)を参照してください。
以下のアルゴリズムの説明では、「sha3」ハッシュが参照されることを覚えておいてください。
パラメータ
Ethash のキャッシュとデータセットのパラメータは、ブロック番号に依存します。 キャッシュサイズとデータセットサイズは、両方とも線形に増えていきます。しかし、周期的な動作につながる偶発的な規則性が発生するリスクを減らすために、線形的に増加するしきい値を下回る最大の素数を常に取ります。
1def get_cache_size(block_number):2 sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)3 sz -= HASH_BYTES4 while not isprime(sz / HASH_BYTES):5 sz -= 2 * HASH_BYTES6 return sz78def get_full_size(block_number):9 sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)10 sz -= MIX_BYTES11 while not isprime(sz / MIX_BYTES):12 sz -= 2 * MIX_BYTES13 return sz14すべて表示コピー
データセットとキャッシュサイズの値の表は、付録に記載されています。
キャッシュ生成
以下に、キャッシュを生成する関数を記述します。
1def mkcache(cache_size, seed):2 n = cache_size // HASH_BYTES34 # Sequentially produce the initial dataset5 o = [sha3_512(seed)]6 for i in range(1, n):7 o.append(sha3_512(o[-1]))89 # Use a low-round version of randmemohash10 for _ in range(CACHE_ROUNDS):11 for i in range(n):12 v = o[i][0] % n13 o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))1415 return o16すべて表示コピー
キャッシュ生成プロセスは、最初に 32MB のメモリを順番に埋め、次に、Strict Memory Hard Hashing Functions (2014)(opens in a new tab)に掲載されている Sergio Demian Lerner 氏のRandMemoHashアルゴリズムを 2 パス実行します。 出力は、524288 個の 64 バイトの値のセットです。
データ集約関数
いくつかのケースにおいて、排他的論理和の非結合的代替としてFNV hash(opens in a new tab)から発想を得たアルゴリズムを使用します。 素数を 1 バイト(オクテット)ずつ順番に乗算する FNV-1 の仕様ではなく、素数を全 32 ビットの入力で乗算することに注意してください。
1FNV_PRIME = 0x0100019323def fnv(v1, v2):4 return ((v1 * FNV_PRIME) ^ v2) % 2**325コピー
イエローペーパーでは、FNV を v1*(FNV_PRIME ^ v2)と指定していますが、現在の実装ではすべて上記の定義で統一しています。
フルデータセットの計算
1GB のフルデータセットの 64 バイトの各アイテムは、次のように計算されます。
1def calc_dataset_item(cache, i):2 n = len(cache)3 r = HASH_BYTES // WORD_BYTES4 # initialize the mix5 mix = copy.copy(cache[i % n])6 mix[0] ^= i7 mix = sha3_512(mix)8 # fnv it with a lot of random cache nodes based on i9 for j in range(DATASET_PARENTS):10 cache_index = fnv(i ^ j, mix[j % r])11 mix = map(fnv, mix, cache[cache_index % n])12 return sha3_512(mix)13すべて表示コピー
基本的に、疑似乱数で選ばれた 256 個のキャッシュノードからデータを結合し、データセットノードを計算するためにハッシュ化します。 そのあと、データセット全体が、次のように生成されます。
1def calc_dataset(full_size, cache):2 return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]3コピー
メインループ
ここでは、メインのハシモトに似たループを記述します。特定のヘッダーとノンス (nonce)の最終的な値を生成するために、フルデータセットからデータを集約します。 以下のコードでは、header
は切り捨てられたブロックヘッダー(すなわち、フィールドmixHashとnonceを除外したヘッダー)の RLP 表現の SHA3-256ハッシュを表します。 nonce
は、ビッグエンディアンオー ダーの 64 ビット符号なし整数 8 バイトです。 したがって、nonce[::-1]
は、その値の 8 バイトのリトルエンディアン表現です。
1def hashimoto(header, nonce, full_size, dataset_lookup):2 n = full_size / HASH_BYTES3 w = MIX_BYTES // WORD_BYTES4 mixhashes = MIX_BYTES / HASH_BYTES5 # combine header+nonce into a 64 byte seed6 s = sha3_512(header + nonce[::-1])7 # start the mix with replicated s8 mix = []9 for _ in range(MIX_BYTES / HASH_BYTES):10 mix.extend(s)11 # mix in random dataset nodes12 for i in range(ACCESSES):13 p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes14 newdata = []15 for j in range(MIX_BYTES / HASH_BYTES):16 newdata.extend(dataset_lookup(p + j))17 mix = map(fnv, mix, newdata)18 # compress mix19 cmix = []20 for i in range(0, len(mix), 4):21 cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))22 return {23 "mix digest": serialize_hash(cmix),24 "result": serialize_hash(sha3_256(s+cmix))25 }2627def hashimoto_light(full_size, cache, header, nonce):28 return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))2930def hashimoto_full(full_size, dataset, header, nonce):31 return hashimoto(header, nonce, full_size, lambda x: dataset[x])32すべて表示コピー
基本的に、128 バイト幅の「mix」を維持し、フルデータセットから 128 バイトを繰り返し順番にフェッチし、fnv
関数を使って、それを mix と結合します。 128 バイトのシーケンシャルアクセス が使用されており、アルゴリズムの各ラウンドは、常に RAM から完全なページをフェッチし、理論的に ASIC が回避できるトランスレーション・ルックアサイド・バッファのミスを最小限にします。
アルゴリズムの出力が目標値を下回っている場合は、ノンス (nonce)は有効で す。 sha3_256
を最後に追加適用することで、ノンス (nonce)が必ず存在することになります。これは、少なくとも少量のワークが行われたことを証明するために提供でき、このクイックアウタ・ープルーフ・オブ・ワーク(PoW)検証は、DDoS 対策に利用できます。 また、その結果が不偏の 256 ビットの数であることを統計的に保証する役割もあります。
マイニング
マイニングアルゴリズムは、以下のように定義されています。
1def mine(full_size, dataset, header, difficulty):2 # zero-pad target to compare with hash on the same digit3 target = zpad(encode_int(2**256 // difficulty), 64)[::-1]4 from random import randint5 nonce = randint(0, 2**64)6 while hashimoto_full(full_size, dataset, header, nonce) > target:7 nonce = (nonce + 1) % 2**648 return nonce9コピー
シードハッシュの定義
あるブロック上でマイニングをするために使うシードハッシュを計算するのに、以下のアルゴリズムを使っています。
1 def get_seedhash(block):2 s = '\x00' * 323 for i in range(block.number // EPOCH_LENGTH):4 s = serialize_hash(sha3_256(s))5 return s6コピー
スムーズなマイニングと検証のために、別々のスレッドで将来のシードハッシュとデータセットを事前計算することを推奨します。
参考文献
役に立つコミュニティリソースをご存知の場合は、 このページを編集して追加してください。
付録
上記の python で記述された仕様をコードとして実行する場合は、以下のコードを先頭に付け足してください。
1import sha3, copy23# Assumes little endian bit ordering (same as Intel architectures)4def decode_int(s):5 return int(s[::-1].encode('hex'), 16) if s else 067def encode_int(s):8 a = "%x" % s9 return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]1011def zpad(s, length):12 return s + '\x00' * max(0, length - len(s))1314def serialize_hash(h):15 return ''.join([zpad(encode_int(x), 4) for x in h])1617def deserialize_hash(h):18 return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]1920def hash_words(h, sz, x):21 if isinstance(x, list):22 x = serialize_hash(x)23 y = h(x)24 return deserialize_hash(y)2526def serialize_cache(ds):27 return ''.join([serialize_hash(h) for h in ds])2829serialize_dataset = serialize_cache3031# sha3 hash function, outputs 64 bytes32def sha3_512(x):33 return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)3435def sha3_256(x):36 return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)3738def xor(a, b):39 return a ^ b4041def isprime(x):42 for i in range(2, int(x**0.5)):43 if x % i == 0:44 return False45 return True46すべて表示![]()