Develop with pleasure!

福岡でCloudとかBlockchainとか。

lndが公開した2つの脆弱性CVE-2020-26895とCVE-2020-26896

先日lndに脆弱性が含まれているということで修正版のアナウンスがされていたけど、その内容が公開された↓

CVE-2020-26895

影響あるバージョン

影響を受けるのはv0.10.0-betaより前のバージョンのlnd。

脆弱性の内容

オフチェーン支払いにより状態を更新する際に、lndノードに対してhigh-ECDSA署名の受け入れが可能であるという内容。Bitcoin Coreのポリシーには、ECDSA署名値(r, s)の内、sの値が曲線の位数の半分以下の値でないといけないというルール(LOW_Sルール)があり、ECDSA署名固有のmalleabilityを解消するためのもの。high-ECDSA署名自体は有効なECDSA署名でコンセンサスルールでは受け入れられるが、Bitcoin Coreのリレーポリシーではhigh-ECDSAを受け入れていないのでトランザクションをリレーする際にはリジェクトされる。

これを悪用すると、例えばタイムロックが設定されているコントラクトを含んでいると、実際にそのトランザクションをブロードキャストしようても、接続先のノードからポリシー違反でリジェクトされ、資金の損失に繋がる可能性がある。

lndの以前のバージョンでは、LOW_Sへの変換がされていなかったため、生成された署名値sがhigh-sになっていてもそのまま受け入れていたという問題。

攻撃内容

チャネルの一方的クローズ中に、攻撃者が↑を悪用して、被害者のHTLC-successトランザクションがリレーされず、攻撃者によるHTLC-timeoutトランザクションがブロードキャストされると、HTLCにロックされている資金が攻撃者によって回収されるという攻撃が考えられる。

尚、強調クローズの場合作成されるトランザクションの署名はポリシー検証もされてるので、この問題は発生しない。

修正

ECDSA署名のLOW_Sルールがv0.10.0-betaで適用されている。ただLNの仕様を定義しているlightning-rfcで、ノードがオフチェーンで受け入れる署名の検証方法の指定が欠けているので、仕様の更新も計画されてる模様。

CVE-2020-26896

影響あるバージョン

影響を受けるのはv0.11.0-betaより前のバージョンのlnd。

脆弱性の内容

衝突するペイメントハッシュを使って転送されたHTLCインボイスのプリイメージが強制的に明かされるという脆弱性で、攻撃者に悪用されると、特定の状況下において、HTLC支払いが行われたと信じて資金を失う可能性がある。

HTLCの受信をオフチェーンではなくオンチェーンで解決する場合、転送ノードでは、HTLCを請求するためにwitnessを介して有効なプリイメージを提供することが期待される。

このプリイメージを知る方法は主に以下の2つ↓

  • 自分がインボイスを発行してプリイメージを生成する側である。
  • HTLCにより正常に支払いが転送された結果としてプリイメージを受信する。

lndではこれらを、インボイスデータベースとプリイメージデータベースの異なる2つのDBで管理している。

ノードがオフチェーンでHTLCを受信すると、ノードは自身が中間ホップか最終ホップかを判断する必要があり、

  • 最終ホップであればインボイスデータベースに対してプリイメージを照会
  • 中間ホップであればプリイメージデータベースに対してプリイメージを照会

する。

問題となったlndの挙動は、プリイメージデータベースにプリイメージが含まれていない場合、誤ってインボイスデータベースに対してもプリイメージを照会しにいくようになっていたというもの。この結果、ノードが支払い経路の最終ホップでない場合も、インボイスのプリイメージ明かす状況というのが発生する。

攻撃内容

↑の挙動を悪用すると以下のようにして、HTLCの資金を盗む攻撃が可能になる。

A -> M -> Bのような経路(Bがコインの受信者でMが攻撃者)のマルチホップ支払いのケースにおいて。

  1. BがAにインボイスを発行する。
  2. AがMを経由してBに支払う経路を選択しHTLCをオファーする。
  3. MはAのHTLC内のペイメントハッシュと同じ値のペイメントハッシュを持つM -> B -> M'の別のHTLCをBにオファーする。
  4. 3のHTLCを含むコミットメントトランザクションをオンチェーンにブロードキャストして、一方的にチャネルをクローズする。
  5. Bが4のブロードキャストを検知するとHTLC-successをブロードキャストを試みる。この時点で↑のバグのため、本来プリイメージデータベースからこのプリイメージを取得する必要があり、実際このプリイメージはそのDBには存在しないのだけど、フォールバックされインボイスデータベースへの照会が発生し、実際にオンチェーン上にプリイメージが公開され、A -> M -> Bのインボイスは既に決済済みとマークされる。
  6. Mは2と3の2つのHTLCを解決して資金を入手し、結果的にBがインボイスで請求していたコインは盗まれる。

尚、MPPを使ってる場合、他の並行MPPのHTLCがBに届いている場合は、安全チェックにより攻撃は失敗する。

修正

修正内容は、↑のインボイスデータベースとプリイメージデータベースの適切な分離で、v0.11.0-betaにおいて修正されている。

Dual_EC_DRBGのバックドアの仕組み

japan.zdnet.com

こんなニュースもあり、バックドアと言えばエドワード・スノーデンの告発でも話題になったNSA(米国家安全保障局)のバックドアを思い出した。当時は仕組みについて調べてなかったけど、どんな仕組みのバックドアだったのか今になって気になったので調べてみた。

Dual_EC_DRBG

バックドアが仕込まれていたのは、NSAの推奨により一度は標準として採用された擬似乱数生成器のアルゴリズムDual Elliptic Curve Deterministic Random Bit Generator(Dual_EC_DRBG)。で、2006年にNIST SP800-90Aに組み込まれ、2013年に利用すべきではないと勧告されている。

Dual_EC_DRBGの仕様

Dual_EC_DRBGは、生成したシード値から、2つの楕円曲線上の点を使って、多数の乱数を生成する擬似乱数生成器で、楕円曲線上の離散対数問題の困難性がベースになっている。アルゴリズム自体はそんなに複雑ではない。

Dual_EC_DRBGでサポートされている楕円曲線は、NIST-p256およびNIST-p384とNIST-p521で、曲線の式はy2 = x3 - 3x + b (mod p)。

Dual_EC_DRBGでは、楕円曲線上の2つの点PとQを使用する。この内Pは楕円曲線のジェネレーターGと同じ点で、例えばNIST-p256であればそれぞれ以下のように定義されている。

P.x = 6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
P.y = 4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5

Q.x = c97445f4 5cdef9f0 d3e05e1e 585fc297 235b82b5 be8ff3ef ca67c598 52018192
Q.y = b28ef557 ba31dfcb dd21ac46 e2a91e3c 304f44cb 87058ada 2cb81515 1e610046

そして、Dual_EC_DRBGは初期シードを使って、PとQの点を使ってスカラー倍算を実行して乱数を生成する。

  1. エントロピーソースから初期シード {s_0}を生成する。
  2.  {s_0}スカラー値として {s_0P}を計算し、そのx座標を {s_1}とする(つまり {s_1 = (s_0P).x})。
  3.  {s_1}スカラー値として {s_1Q}を計算し、そのx座標を {r_1}とする(つまり {r_0 = (s_1Q).x})。
  4. (NIST-p256の場合) {r_1}は32バイトであり、その内の上位16bitを削除した30バイトのデータが出力される。

データがさらに必要な場合、↑の計算値を使って次の乱数が生成される。次の乱数は、

  1.  {s_1}スカラー値として {s_1P}を計算し、そのx座標を {s_2}とする(つまり {s_2 = (s_1P).x})。
  2.  {s_2}スカラー値として {s_2Q}を計算し、そのx座標を {r_2}とする(つまり {r_1 = (s_2Q).x})。
  3.  {r_2}の下位30バイトが次の出力値。

これを要求されたビット数まで繰り返し、出力値を連結して返す(余ったバイトは破棄される)。つまり内部状態 {s_{i-1}}を使って次の内部状態を {s_i}を更新し、出力を生成している。

  •  {s_i = (s_{i-1}P).x}
  •  {r_i = (s_iQ).x}

このPRNGが安全であるためには、内部状態 {s_i}を誰も知り得ないことが重要で、 {s_i}が分かると、それ以降の全ての内部状態および出力を計算することができる。

バックドアの内容

Dual_EC_DRBGは上記のように2つの楕円曲線上の点を使って、決定論的に乱数を生成する仕組みだが、問題となるのはPとQの点の算出根拠が無い点にある。つまりNSAはPやQの離散対数を知っているのではないかということ。

攻撃者がP = dQとなるようなスカラー値を知っていて、(Public Nonceなどで)上記の {r_1}を知っていると仮定した場合、攻撃者は以下の計算が行える。

  1.  {r_1}楕円曲線上の点のx座標なので、楕円曲線の式を使えばy座標が計算でき点 {R = (r_1, y)}を復元できる。
  2. Rが復元できると、 {R = s_1Q}である。
  3. 両辺にdをスカラー倍算すると、 {dR = d s_1 Q = s_1P}が成立する。
  4.  {s_1P}のx座標は次の内部状態 {s_2}を計算する入力値であるため、攻撃者これ以降の内部状態および出力値を知ることができる。

つまり、P = dQスカラー値dの知識は攻撃者にとってバックドアになる。

 {r_1}は上位16 bitが削除されているので、厳密には欠落しているbitを復元するのに攻撃者は最大 {2^{16}}回の計算が必要。

↑のように、たった32バイト(正確には30バイト)の出力を入手すれば、NSAは完全な内部状態を学習できるというのがこのバックドアの怖いところ(実際に攻撃が適用できるかどうか、その難易度はこれが組み込まれているプロトコルや実装に依存する)。

参考

DoS攻撃を可能にする脆弱性CVE-2018-17145とBitcoin Coreの脆弱性の内容と対応

最近公開された、2018年のBitcoin Coreに存在していた脆弱性に関するペーパー↓

https://invdos.net/paper/CVE-2018-17145.pdf

この脆弱性はもともとJavaScriptで実装されたBitcoinのノード実装の1つであるBcoinで発見されたもので、攻撃方法は同じでも、BcoinとBitcoin Coreで脆弱性が現れるコードには違いがある。またホワイトペーパーの説明にも一部間違いがあるようなので、その辺りも含めてみてみよう。

尚、Bitcoin Coreの場合、脆弱性の影響を受けるのはv0.16.0とv0.16.1とされている。

CVE-2018-17145の内容

CVE-2018-17145はBitcoinP2Pメッセージの1つであるinvメッセージを使った攻撃になる。

invメッセージ

invメッセージは新しいブロックやトランザクションの存在を接続中のピアに通知する際に使用される。invメッセージにはブロックやトランザクションのハッシュのリストが含まれており、invを受信したノードは自身が対象のハッシュ値を持つブロックやトランザクションを持っていない場合、それをgetdataメッセージを使って要求する。

invメッセージは最大50,000個のアイテム(トランザクションハッシュ or ブロックハッシュ)を一度に送信できる。

攻撃方法

攻撃方法はシンプルで、インバウンド接続を許可しているノードに接続し、49,999個(ペーパーに49,999と書いてあるけど、上限が50,000なので別に50,000でも良いはず)のランダムなハッシュを生成し、それをinvメッセージにセットして送信し、getdata要求が来ても対応するトランザクションデータを返さない(元々ランダムに生成したハッシュなので、その元となる有効なトランザクションなど存在しない)。これを繰り返す。

ただ、この攻撃が成功するには、攻撃対象のノードがinvメッセージで受信したハッシュリストの内、未確認のハッシュをトラッキングしているノードである必要がある。未確認のトランザクションのハッシュをメモリ上に保持しているノード実装であれば、この攻撃の影響を受ける。1 Gbpsのネットワーク帯域を持つ環境であれば、125MB/秒のデータ送信が可能なため、49,999個の32バイトのハッシュ値を持つinvメッセージを秒間約83回送信できる。するとすぐにノードのメモリは膨れ上がり、Out-of-Memoryを引き起こさせノードを応答不能にすることができる。

ノードは対応するTxが確認されていない状態で受信したinvのTxのリストを他のピアにリレーすることはないので、この攻撃はターゲットノードを絞った上で個別に実行する必要がある。

Bcoinの脆弱性の原因

Bcoinでは、↑のように受信したinvのアイテムをトラッキングしていたため、この攻撃の影響を受ける。

このinvのアイテムをトラッキングしている理由は、未確認のトランザクションハッシュのトランザクションについてgetdataメッセージでデータを要求する際、既にgetdataを送信済みのデータについて再度getdataを送信しないために送信済みかどうかのチェックをするためで、BcoinではハッシュリストをMapで管理していた。

修正のコミットは↓で、

github.com

1つのピアからの未確認トランザクションハッシュの上限を10000とし、それを超えたらそのピアとの接続を切断するという対策を採っている。

Bitcoin Coreの脆弱性の原因

Bitcoin Coreの場合、Bcoinのように単純にトラッキングしているという訳ではなく、正確にはinvで受信したアイテムをウォレットに通知するためのコードが対象になる。

↑のペーパーで、Bitcoin Coreでもinvメッセージを処理する際の機能していない制限のチェックとして以下のsrc/net_processing.cppのコードをリストアップしているが、これは正しくない。このコードはinvメッセージ内のハッシュの数が50,000より大きくないかチェックしてるだけであって、invのトラッキングをするためのコードではない。

if (vInv.size() > MAX_INV_SZ)
{
  LOCK(cs_main);
  Misbehaving(pfrom->GetId(), 20,
  strprintf("message inv size() = %u",
  vInv.size()));
  return false;
}

実際にBitcoin Coreでチェックが動作しているのは、src/net.cppの以下のコードだ

if (mapAskFor.size() > MAPASKFOR_MAX_SZ || setAskFor.size() > SETASKFOR_MAX_SZ)
   return;

mapAskForは、未確認のトランザクションハッシュについて、getdataを要求するために確保されるMapで、MAPASKFOR_MAX_SZinvの上限となじ50,000なので、Bcoinと同じトラッキングの意味としては、対応がされている。

Bitcoin Coreで実際に問題となるのは、トラッキングではなくinvで受信したアイテムをウォレットに通知するためのコードになる。そのコードが、src/net_processing.cppinvメッセージを処理の最後の以下のコード↓

// Track requests for our stuff
GetMainSignals().Inventory(inv.hash);

ペーパーでは、その中身(src/validationinterface.cpp)がリストアップされている↓

void CMainSignals::Inventory(const uint256 &hash) {
    m_internals->m_schedulerClient.AddToProcessQueue([hash, this] {
        m_internals->Inventory(hash);
    });
}

このコードが導入されたのが↓のコミットで、

github.com

ウォレットへのinvのアイテムの通知処理を、バックグラウンドスレッドで動作するようキュー化したもの。この場合、攻撃はバックグラウンドで動作する通知処理のスピードを、invで送られてくるアイテムによるキューの成長が上回る場合に成功する。実際にどういうマシンスペック、ネットワーク帯域の下で成功するかについては、シミュレーション結果などはホワイトペーパーでは提供されていない。

問題のコードは以下のコミットで修正されている。

github.com

修正方法としては、Inventoryの通知自体を削除している。これはバックグラウンドのキュー化以前に戻してもmainスレッドでの処理は発生するからか?まぁ未確認のハッシュをそもそもウォレットに通知する必要もないのだろうけど。

Bitcoin Core以外にもLitecoinやbtcdなどにも影響があったようだが、↑でも分かるよう実装によって脆弱性のポイントは違う可能性はある。

決定性nonceを利用したMuSigの脆弱性に対処したMuSig-DN

Blockstreamは以前、Schnorr署名を利用したマルチシグを構成する際にKey-Rogue攻撃への耐性を持たせる署名スキームMuSigを発表していた。Key-Rogue攻撃やMuSigの内容について以前解説した↓を参照。

goblockchain.network

techmedia-think.hatenablog.com

そんなMuSigについて、決定性nonceを利用できるようにしたMuSigの変形であるMuSig-DN(MuSig with Deerministice Nonces)というSchnorr署名スキームをBlockstreamおよびYannick Seurinが発表した↓

medium.com

ペーパーは↓

https://eprint.iacr.org/2020/1057.pdf

決定性nonceの役割

Schnorr署名やECDSAでは、署名作成時に選択するnonceの値のランダム性がとても重要になる。例えば同じnonceを使って異なる2つのメッセージに署名すると、秘密鍵が漏洩してしまう。

具体的には、メッセージm1およびm2について、同じnonce kを使ってそれぞれ下記のデータを使って署名を生成すると、

Schnorr署名の署名値sの値は、それぞれ

  • s1 = k + H(P || R || m1) x
  • s2 = k + H(P || R || m2) x

となり、署名データは(R.x, s1)と(R.x, s2)となる。nonceが同じ値であることはR.xから分かる。この場合s1 - s2を計算すると、

s1 - s2 = (H(P || R || m1) - H(P || R || m2)) x

となり、P, R, m1, m2は公知であるため、

x = (s1 - s2) / (H(P || R || m1) - H(P || R || m2))

秘密鍵xを計算できる。

このようなことが起きないよう、RFC6979などでnonceを秘密鍵と署名対象のメッセージから決定論的に導出する仕様が定義され、決定性nonceを使用するのが主流になっている。この場合、署名対象のメッセージが異なれば必ず異なるnonceが導出されるため上記のような攻撃から保護される。

決定性nonceを利用したMuSig脆弱性とは?

単一の鍵を使ったSchnorrであれば決定性nonceを使用するのは特に問題ないが、MuSigのようにマルチシグを構成する場合、逆に秘密鍵漏洩のリスクになる。

  • 被害者の鍵ペア: P1 = x1G
  • 攻撃者の鍵ペア: P2 = x2G
  • 署名対象のメッセージ: m
  • 被害者のnonce: R1 = k1G
  • 被害者のnonce:
    • R2 = k2G(1回目のセッションで使用するnonce)
    • R3 = k2G(2回目のセッションで使用するnonce)

として、攻撃者が同じメッセージで2回署名セッションを実行した場合、MuSigスキームを実行すると、

  1. L = H(P1 || P2)を計算する。
  2. X = H(L || P1)P1 + H(L || P2)P2を計算する。
  3. Public nonceは
    • 1つめのセッションではR = R1 + R2
    • 2つめのセッションではR' = R1 + R3
  4. 署名値sを計算する。
    • 被害者の1つめのセッションではs1 = k1 + H(P || R || m) * H(L || P1)x1
    • 被害者の2つめのセッションでははs3 = k1 + H(P || R' || m) * H(L || P1)x1
    • 攻撃者の1つめのセッションでははs2 = k2 + H(P || R || m) * H(L || P2)x2
    • 攻撃者の2つめのセッションでははs4 = k3 + H(P || R' || m) * H(L || P2)x2

最終的な2つの署名値は(R.x, s1 + s2)と(R'.x, s3 + s4)になる。この内、被害者が計算したs1とs3について、s1 - s3を計算すると、

s1 - s3 = (H(P || R || m) - H(P || R' || m)) * H(L || P1)x1

となり、H(P || R || m)およびH(P || R' || m)H(L || P1)は攻撃者も知る値であるため、

x1 = (s1 - s3) / ((H(P || R || m) - H(P || R' || m)) * H(L || P1))

と被害者の秘密鍵x1を計算することができる。nonce kは署名値から秘密鍵を逆算できないようにするためのものなので、↑のように(異なるメッセージのパターンでも同様に)nonceを消せる計算が出来てしまうとまずい。

MuSigにおける決定性nonceの使用の問題は自分が決定性nonceを使っていても、他の参加者が同様の導出ルールで決定性nonceを導出しているか分からない点にある。RFC6979では秘密鍵と署名対象のメッセージからnonceを導出するが、相手の秘密鍵を知り得ないため、同じルールで導出されたかをプロトコルで検出することができない。そのため逆に決定性nonceを使わずに毎回ランダムに生成する方が安全になる。

MuSig-DNのアプローチ

MuSigでも決定性nonceを安全に利用するためMuSig-DNでは、nonceが決まったルールの下で導出された値であることをゼロ知識証明を使って検証できるようにしている。

  • 各署名者はnonce keyとよばれる秘密鍵を使って署名対象のメッセージと全署名者の公開鍵のセットを入力として擬似ランダム関数Fを実行してnonce kiを導出する。
  • Public nonce Ri = kiGとそれがFで指定通りに計算されたことを示す非対話型のゼロ知識証明を生成し、他の参加者に送信する。
  • ↑のゼロ知識証明はhost keyとよばれる公開鍵を使って他の署名者が検証できるようになっている。
  • もし署名者の誰かが2つの異なるnonceを送信しチートしようとした場合、その内の1つのゼロ知識証明は無効と判定される。
  • 無効なゼロ知識証明を持つnonceに対しては自身が担当する署名値sの計算はせずプロトコルを中止する。

↑のnonceを導出するために使われる関数FがPurifyという特殊関数で、SHA256などのハッシュ関数と比べてゼロ知識証明用に最適化されている模様。Purifyは演算回路で、secp256k1のような256 bitの楕円曲線に対応したものでは2030個の乗算ゲートを持つ。

MuSig2?

↑のブログだと現在ゼロ知識証明を必要とせず2ラウンドで実行可能、また最初のラウンドの前処理により1ラウンドの最適化も可能という後継のMuSig2に取り組んでいるようなので、その発表も期待したい。

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は大きく分けて初期化、マイニング、検証の3つの段階がある。

初期化

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

  1. まずseedハッシュを計算する。これは32バイトの00をエポックの数分のKeccak-256ハッシュを計算することで得られる。つまり、あるエポックのseed値はその前のエポックのseed値のKeccak-256ハッシュ値になる。これによりエポック毎にseed値が変わる。
  2. 続いて計算したseedを使ってキャッシュを生成する(擬似コードこちら)。
    1. 各エポック毎のキャッシュサイズは2,048エポック分(=61,440,000ブロック)までハードコードされており、キャッシュサイズ / 64を計算する。
    2. seedのKeccak-512ハッシュ値を計算し、それをキャッシュサイズ/64回繰り返す。計算したハッシュ値は64バイトでそれぞれ配列に格納される。これでキャッシュサイズ分のメモリを埋める。
    3. 続いて2を初期キャッシュとしてSergio Demian LernerのRandMemoHashアルゴリズムを実行する。実行結果を初期キャッシュとしてこれを合計3回実行する。
  3. 生成したキャッシュからデータセットを生成する。データセットのサイズもキャッシュのサイズと同様エポック毎に線形に増えていく。またキャッシュサイズと同様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の場合、キャッシュのみ保持していればいい。

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

マイニング

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

  1. 新しいブロックヘッダーについて、mixHashフィールドとnonceフィールド(8バイトの符号なし整数)を除いたRLP表現のヘッダーのKeccak-256ハッシュを計算する。
  2. 1のブロックヘッダーのハッシュとnonceを結合してKeccak-512ハッシュを計算する。これが64バイトのシード。
  3. 128バイトのデータmixを初期化する。具体的には128バイト満たすまで、2のシードデータを追加し、128バイトになるよう切り捨てる。
  4. データセットから順次128バイト読み出して、mixに結合してfnvハッシュ値を計算し、その値でmixを更新する。これを64回繰り返す。
  5. mixを圧縮して(この圧縮した値がブロックヘッダーにセットされるmixHash)、2のシードと結合してKeccak-256ハッシュ値を計算する。
  6. 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の検証方法では、1回のPoW検証につき

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

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

Ultra Light Client

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

hackmd.io

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

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