Ethash - t10471/geth-memo GitHub Wiki

EthashはEthereum 1.0の為に作られたPoWのアルゴリズム.

Dagger-Hashimotoの最新バージョンではあるが、両方のアルゴリズムが大幅に進歩しているので、そのように呼ぶのは適切ではない。

大雑把なアルゴリムズは下記のようなものである

  1. その時点までブロックヘッダを走査することにより、各ブロックについて計算可能なシードが存在する。
  2. シードから16MBの疑似ランダムキャッシュを計算する。ライトクライアントはキャッシュを保存する。
  3. キャッシュからは、データセット内の各アイテムがキャッシュからの少数のアイテムのみに依存するという特性を持つ、1 GBのデータセットを生成することができる。フルクライアントとマイナーがデータセットを格納する。データセットは時間とともに線形増加する。
  4. マイニングでは、データセットのランダムなスライスとそれをハッシュ化したものを含める。キャッシュを使用して必要なデータセットの特定の部分を再生成することで、メモリを少なくして検証を行うことができるため、キャッシュだけが必要となる。

大規模なデータセットは30000ブロックごとに更新されるため、大多数のマイナーのやることはデータセットを読むことであり、変更することではない。

Ethashは以下の目標を達成することを意図している：

  • ASIC対策
  • GPUには優しい
  • 軽量クライアントでも検証可能
  • 軽量クライアントでも遅くアルゴリズムが動作する
  • 軽量クライアントでも検証が早く

FNV

FNVというハッシュ関数を使用。ばらつきやすいというメリットがある

// 0x01000193 = 16777619 32bit用の定数
// 
func fnv(a, b uint32) uint32 {
	return a*0x01000193 ^ b
}

各数字の根拠

  • 16MBキャッシュ: ASIC対策で軽量クライアントで検証可能なのがこのくらい
  • DAGが256先まで: 時間とメモリのトレードオフが最悪1:1になる位にするため
  • Datasizeが1GB: ASIC対策
  • ~0.73x/年の成長レベル: ムーアの法則
  • 64回アクセス: 軽量クライアントとASIC対策
  • エポックの長さ: データの再読込をへらしつつASIC対策　この値は変更する可能性がある

block numberごとの cacheサイズとdatasetサイズ

block:         10 cache: 16.0MB dataset: 1024.0MB
block:        100 cache: 16.0MB dataset: 1024.0MB
block:      1,000 cache: 16.0MB dataset: 1024.0MB
block:     10,000 cache: 16.0MB dataset: 1024.0MB
block:    100,000 cache: 16.4MB dataset:    1.0GB
block:  1,000,000 cache: 20.1MB dataset:    1.3GB
block: 10,000,000 cache: 57.6MB dataset:    3.6GB

周期性を作らないようにblockがすすむごとにcacheサイズとdatasetのサイズを線形増加させるようにしている