EthashのPoWとLight Clientの検証コスト

最近、Geth v1.9.0で導入されたUltra Light ClientがブロックヘッダーのPoWの検証をスキップしているのを知った。Bitcoinとかだと軽量ノードはブロックヘッダーのみダウンロードし有効なPoWのチェックはしてるから何故そういうアプローチなのか、EthereumのPoWアルゴリズムであるDagger-HashimotoをベースにしたEthash↓の仕組みと検証アルゴリズムについて調べてみた。

https://eth.wiki/en/concepts/ethash/ethash

EthashのPoWの仕組み

EthashのPoWは大きく分けて初期化、マイニング、検証の３つの段階がある。

初期化

Ethereumでは30,000ブロック = 1エポックとして、エポック毎にマイニングに使用するためのデータセットを初期化する必要がある。初期化のステップは↓

まずseedハッシュを計算する。これは32バイトの00をエポックの数分のKeccak-256ハッシュを計算することで得られる。つまり、あるエポックのseed値はその前のエポックのseed値のKeccak-256ハッシュ値になる。これによりエポック毎にseed値が変わる。
続いて計算したseedを使ってキャッシュを生成する（擬似コードはこちら）。
1. 各エポック毎のキャッシュサイズは2,048エポック分（＝61,440,000ブロック）までハードコードされており、キャッシュサイズ / 64を計算する。
2. seedのKeccak-512ハッシュ値を計算し、それをキャッシュサイズ/64回繰り返す。計算したハッシュ値は64バイトでそれぞれ配列に格納される。これでキャッシュサイズ分のメモリを埋める。
3. 続いて2を初期キャッシュとしてSergio Demian LernerのRandMemoHashアルゴリズムを実行する。実行結果を初期キャッシュとしてこれを合計３回実行する。
生成したキャッシュからデータセットを生成する。データセットのサイズもキャッシュのサイズと同様エポック毎に線形に増えていく。またキャッシュサイズと同様2,048エポック分（＝61,440,000ブロック）までハードコードされている。具体的にはデータサイズ / 64回ループを実行して、以下の手順でデータセット内のデータアイテムを生成する（ループのインデックスをiとし、生成するデータ変数をmixとする）。
1. キャッシュデータのリストのi % ハッシュデータのサイズ 番目のデータをmixの初期値とする。
2. mixの先頭バイトを先頭バイトとインデックスiのXOR値にする。
3. mixを値をKeccak-512ハッシュした値にする。
4. キャッシュデータからデータを擬似ランダムに選択し、それとmixを結合してFNVハッシュを計算し、それをmixとする。これを256回繰り返す。
5. 最後にmixをKeccak-512ハッシュした値がデータアイテムになる。

データアイテムは要約すると、キャッシュデータから擬似ランダム（決定論的）に選択した値を結合してそのハッシュを256回計算してできたもの。キャッシュサイズよりデータセットの方が要素の数は多いので、↑のようにインデックスiをキャッシュデータのサイズでmodしてる。Ethereum wikiで公開されているPythonの擬似コードが参考になる。

こうやってエポック毎にマイニングに使用するデータセットを作成する必要がある。なお、データセットを必要とするのは、マイナーとfull syncをするフルノードのみ。Light Client（LESプロトコル）やフルノードでもfast syncの場合、キャッシュのみ保持していればいい。

キャッシュとデータセットのサイズについて

キャッシュサイズとデータセットサイズは厳密に線形増加せず、周期的に増加していくとそれに伴う偶発的な規則性のリスクを排除するため、線形増加する閾値を下回る１番近い素数が採用されるようになっている。
最初のエポックのキャッシュサイズが16,776,896なので、初期のキャッシュサイズは約16MB。それが線形に増えていき、現在10671299ブロックのエポックは355なので、そのハッシュサイズは63,307,072で約60MBほど。
データサイズは最初のエポックで1,073,739,904で約1GBで、現在10671299ブロックのエポックは355なので、そのデータセットサイズは、4051695488で約3.7GBほどになる。

マイニング

マイニングは、生成したデータセットから以下の計算をして、目標のターゲット値を下回るハッシュ値を計算すること。

新しいブロックヘッダーについて、mixHashフィールドとnonceフィールド（8バイトの符号なし整数）を除いたRLP表現のヘッダーのKeccak-256ハッシュを計算する。
1のブロックヘッダーのハッシュとnonceを結合してKeccak-512ハッシュを計算する。これが64バイトのシード。
128バイトのデータmixを初期化する。具体的には128バイト満たすまで、2のシードデータを追加し、128バイトになるよう切り捨てる。
データセットから順次128バイト読み出して、mixに結合してfnvハッシュ値を計算し、その値でmixを更新する。これを64回繰り返す。
mixを圧縮して（この圧縮した値がブロックヘッダーにセットされるmixHash）、2のシードと結合してKeccak-256ハッシュ値を計算する。
5の値が目標のターゲット値を下回っていた場合、2で使ったnonceは有効と判断されPoWは成功する。ターゲット値を下回っていない場合、2のnonceをインクリメントして再度計算を実行する。

↑の擬似コードがこちら。

4のデータセットからのフェッチがシーケンシャルに実行されるため、データ・セットは基本的にRAMに配置する必要があり、これを持ってASIC耐性としている。

PoWの検証

EthashはのPoWの検証は、ターゲット値を下回るブロックヘッダーのハッシュが、正しいデータセットから生成されたものであることを証明することで、この証明の方法、具体的には検証に必要なデータセットのデータの取得方法が、Full ClientとLight Clientで異なる。

Full Clientの検証方法

Full Clientはデータセットを保持しているので、オンメモリに展開しているデータセットを使って検証を行う。つまり↑と同じ計算を実行する。

※ ただFull Clientといってもこれを実行してるのはfll syncの場合で、fast syncの場合はLight Clientと同様の検証をしてるっぽい。

Light Clientの検証方法

Light Clientの場合、キャッシュは持っているがデータセットは持っていない。そのためオンメモリのキャッシュデータを使って、必要となるデータセットのデータを都度計算するという方法を採っている。Gethのコードだとconsensus/ethash/algorithm.goの↓

// hashimotoLight aggregates data from the full dataset (using only a small
// in-memory cache) in order to produce our final value for a particular header
// hash and nonce.
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    keccak512 := makeHasher(sha3.NewLegacyKeccak512())

    lookup := func(index uint32) []uint32 {
        rawData := generateDatasetItem(cache, index, keccak512)

        data := make([]uint32, len(rawData)/4)
        for i := 0; i < len(data); i++ {
            data[i] = binary.LittleEndian.Uint32(rawData[i*4:])
        }
        return data
    }
    return hashimoto(hash, nonce, size, lookup)
}

この違いのため、PoWの検証はFull Clientの方が高速で、Light Clientの検証はそれに比べて遅くなる。

Light Clientの検証コスト

Light Clientは巨大なデータセットを持たなくて済む反面、検証時に必要なデータセット内のアイテムを都度計算しないといけないトレードオフがあるのは分かった。Light Clientにとって具体的なPoWの検証コストは、以下のようになる。

初期化コスト

初期化はエポック毎に発生するので毎ブロックではないが、ブロックチェーンの成長と共にキャッシュサイズも成長する。初期16MBだったキャッシュのサイズは現在約60MBだ。

前述したキャッシュ計算の仕組みにより、線形に増加するキャッシュサイズと共に、Keccak-512のハッシュ計算の回数も増え計算コストが増加する。具体的には、エポック毎に(増加したキャッシュサイズ / 64) ✕ 2回の計算コストが増える。

PoWの検証コスト

Light Clientの検証方法では、１回のPoW検証につき

256回のKeccak-256ハッシュ計算
65664回のFNVハッシュ計算

のコストが発生する。こちらはキャッシュサイズやデータセットのサイズに関係なく一定だ。

Ultra Light Client

Bitcoinの場合PoWの検証はSHA-256ハッシュ計算を２回だけすれば済むのに比べると結構コスト高だ。このコストを削減するのに、Geth v1.9.0で導入されたUltra Light Clientでは（LESプロトコルのオプションという位置付けだが）、↑のPoWの検証ステップが削除され、代わりにTrusted LES Serverによる署名付き通知とCHTを利用したブロックヘッダーの有効性の検証に切り替わっている↓

hackmd.io

オプションだからというのもあるかもしれないけど、思い切ってPoW検証捨てるのは意外だった。まぁ信頼点ある方が効率的にはなる。

最初に成功し現在も攻撃コストが最も高くASIC耐性の無いBitcoinはともかく、後発のブロックチェーンにとってどういうPoWアルゴリズムを採用するかは悩みどころだと思う。ASIC耐性をどう捉えるか？PoWにおけるハッシュパワーの移動をどう考慮するか？検証コストが与える軽量ノードへの影響は？など現状を踏まえて考慮すべきことが増えてるなーという印象。