Develop with pleasure!

福岡でCloudとかBlockchainとか。

Lightning Networkの新しいチャネルコントラクトの提案「Generalized Channels」

Bitcoin Lightning network Payment Channel

少し前に発表されたLightning Networkの改善提案のペーパー「Generalized Bitcoin-Compatible Channels」↓

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

簡単に言うと↓の特性を持つ、現在のLightning NetworkのPoon-DryjaスタイルのPayment Channelの改良

  • 共通のコミットメントトランザクションを構成する。
    Poon-DryjaスタイルのPayment Channelでは、チャネル参加者が保持するコミットメントトランザクションは非対称なもので、それぞれ異なるコミットメントトランザクションを管理するが、Generalized Channelsでは、両者が保持するコミットメントトランザクショントランザクションは同じものになる。これには以下のようなメリットがある。
    • チャネル更新の通信量がより小さくなり、シンプルになる。
    • コミットメントトランザクションがブロードキャストされた場合のオンチェーンフットプリントも小さくなる。
  • 現時点でデプロイ可能である。
    Generalized ChannelsはECDSA + Adaptor Signatureで構成可能なので、現時点でもデプロイが可能である。

相手が古いチャネル状態を公開しようとした場合、チャネル資金が全額没収されるペナルティタイプのPayment Channelである点はPoon-DryjaスタイルのPayment Channelと同じだ。一方で、eltooのように共通のコミットメントトランザクションを構成するようになっている。ただ、eltooの場合、新しいSIGHASH_TYPEの導入が必要で、それにはBitcoinのソフトフォークが必要になるが、Generalized Channelsは、既存のプロトコルで利用可能だ。eltooについて知りたい場合は↓参照。

goblockchain.network

Poon-DryjaスタイルのPayment Channel

Payment Channelを構成する際に登場する主なトランザクションは以下の2種類。

  1. ファンディングトランザクション
    チャネルを構成する際に、チャネル参加者の2-of-2マルチシグアウトプットにコインをロックするためのトランザクションで、オンチェーントランザクション
  2. コミットメントトランザクション
    ファンディングトランザクションのアウトプットを使用するトランザクションで、オフチェーンで支払いをするたびに更新される。基本的にはオフチェーントランザクションだが、相手が応答しないなどでチャネルの協調クローズができない場合に、チェーン上にブロードキャストされる。

2のコミットメントトランザクションは（HTLCを除いた場合、）チャネル参加者のそれぞれの残高を持つ２つのアウトプットを持つ。そのうち自分の残高のアウトプットは以下の２つのいずれかの条件でアンロックされる。

  • タイムロック期間が過ぎれば自分で使用できる。
  • あるシークレット値（per_commitment_secret）を知っていれば相手が使用できる。

オフチェーン支払いをする場合、残高を更新した新しいコミットメントトランザクションを作成し、前のコミットメントトランザクションのシークレット（per_commitment_secret）をお互い相手に通知する。

Generalized Channels

↑の構成だと、参加者はそれぞれ異なるコミットメントトランザクションを持つが、Generalized Channelsでは、両者が同じコミットメントトランザクションを持つ。このコミットメントトランザクションが持つアウトプットは１つのみで、チャネルの資金を全て保持している。このコミットメントトランザクションはタイムロックの後、後続のスプリットトランザクションで使用でき、このスプリットトランザクションは参加者のその時点の残高をそれぞれ保持する複数のアウトプットを持つ。

f:id:techmedia-think:20200807212037p:plain
Generalized Channelsの構成

チャネルのセットアップ

アリスとボブがGeneralized Channelsをセットアップする手順は以下の通り。

アリスの鍵ペアを {P_{A} = x_{A} G}、ボブの鍵ペアを {P_{B} = x_{B} G}とする。

  1. 両者は最初にファンディングトランザクションを作成する。このトランザクションは、これまでと同様、チャネル資金を {P_{A}, P_{B}}の2-of-2のマルチシグアウトプットにロックするオンチェーントランザクション。
  2. 続いてチャネルの初期状態にコミットするコミットメントトランザクションを構成する。
    1. 両者は取り消し用の鍵ペアを作成し、その公開鍵を相手に伝える。
      • アリスは {R_{A} = r_{A} G}を計算し、 {R_{A}}をボブに伝える。
      • ボブは {R_{B} = r_{B} G}を計算し、 {R_{B}}をアリスに伝える。
    2. 両者は公開用の鍵ペアを作成し、その公開鍵を相手に伝える。
      • アリスは {Y_{A} = y_{A} G}を計算し、 {Y_{A}}をボブに伝える。
      • ボブは {Y_{B} = y_{B} G}を計算し、 {Y_{B}}をアリスに伝える。
    3. ファンディングトランザクションをマルチシグアウトプットを使用するコミットメントトランザクションを作成する。アウトプットは１つのみで、このアウトプットを使用できる条件は以下の３つのいずれか。
      • タイムロック期間Δが経過したら、公開鍵 {P_{A}}と {P_{B}}に対して有効な署名があれば使用可能（後続のスプリットトランザクション用のアンロック条件）
      • {r_{A}}と {y_{A}}が分かれば、公開鍵 {P_{B}}に対して有効な署名があれば使用可能（アリスが不正をした場合のペナルティ用）。
      • {r_{B}}と {y_{B}}が分かれば、公開鍵 {P_{A}}に対して有効な署名があれば使用可能（ボブが不正をした場合のペナルティ用）。
  3. コミットメントトランザクションのアウトプットを使用するスプリットトランザクションを作成する。
    • このトランザクションは、アリスの残高とボブの残高をそれぞれに送金する２つのアウトプットを持つ（一方の残高が０であれば１つになる）。
    • コミットメントトランザクションのアンロック条件はタイムロック＋公開鍵 {P_{A}}と {P_{B}}に対して有効な署名。
  4. スプリットトランザクションに対して、アリスは {x_{A}}を使って、ボブは {x_{B}}を使って署名を計算し、お互い交換する。
  5. アリスとボブはコミットメントトランザクションについてAdaptor Signatureをそれぞれ作成し、交換する。
    • アリスは秘密鍵 {x_{A}}とボブから受け取った {Y_{B}}を使ってAdaptor Signatureを作成し、ボブに送信する。この署名を完成させるためにはボブは {y_{B}}を加算する必要がある。
    • ボブは秘密鍵 {x_{B}}とアリスから受け取った {Y_{A}}を使ってAdaptor Signatureを作成し、アリスに送信する。この署名を完成させるためにはアリスは {y_{A}}を加算する必要がある。
  6. 最後に両者はファンディングトランザクションに署名し、ブロックチェーンネットワークにブロードキャストする。

チャネルの更新

チャネルを更新する（オフチェーン支払いを行う）際の手順は、

  1. ↑のように新しいコミットメントトランザクションを作成する。それぞれYとRの鍵は新しく生成したものになる。
  2. さらに新しいコミットメントトランザクションのコインを使用するスプリットトランザクションを作成する。アウトプットはそれぞれ支払いにより更新した残高を持つ。
  3. ↑と同様スプリットトランザクションの署名と、コミットメントトランザクションのAdaptor Signautreを交換する。
  4. 最後に古いコミットメントトランザクションを無効にするため、両者ともに前のコミットメントトランザクションの取り消し用のシークレット {r_{A}, r_{B}}を交換する。

チャネルのクローズ

チャネルのクローズは、既存のPayment Channelの実装と同様、２つの方法がある。

  • 協調クローズ
    両者が協力し、ファンディングトランザクションのアウトプットをチャネルの最終残高に応じてそれぞれに分配するクロージングトランザクションを作成し、ブロードキャストする。
  • 一方的なクローズ
    最新のコミットメントトランザクションをブロードキャストする。この場合コミットメントトランザクションがブロックに格納されてから指定されたタイムロック期間経過すればそれぞれチャネルの最終残高が手に入る。

不正をした場合の動作

どちらかが古いコミットメントトランザクショントランザクションをブロードキャストした場合（アリスが不正したと仮定すると）、その状態の残高が配分されるスプリットトランザクションをブロードキャストできるようになるまでタイムロックが設定されているので、その間に不正をされたボブは、

  • チャネル更新時に交換したそのコミットメントトランザクションの取消用の鍵 {r_{A}}
  • アリスがブロードキャストしたコミットメントトランザクションと、事前に受け取ったAdaptor Signatureの差分を計算し {y_{A}}を入手する。

の２つのデータ（ {r_{A}, y_{A}}）と自身の {x_{B}}を使って、ブロードキャストされたコミットメントトランザクションのアウトプットの資金＝チャネルの全資金を自身に送金するパニッシュメントトランザクションを作成しブロードキャストする。

ポイント

Generalized Channelsのポイントはコミットメントトランザクショントランザクションの構成方法で、このアウトプットの使用条件に

  • 取消用のシークレットを組み入れる
  • コミットメントトランザクションが公開された時に初めて明らかになるシークレットを組み入れる

この２つの条件を組み入れたことだろう。これにより

  • 単純に最新のコミットメントトランザクションをブロードキャストする分には、取消用のシークレットは交換されていない＝相手のシークレットを知らない状態なので、コミットメントトランザクションのペナルティ条件は使えない。
  • 古いコミットメントトランザクションをブロードキャストする＝自身のが不正した証拠（ {y_{A} もしくは y_{B}}）を提供することになり、それを使ってペナルティ条件が利用可能になる。

を実現できる。

Generalized Channelsだと、冒頭に書いたように既存のコミットメントトランザクションの複雑さとトランザクションサイズも削減されるし、ペナルティをトランザクションを発行する際のトランザクションサイズも削減できメリットは大きい。Bitcoinの次のソフトフォーク（Schnorr + Taproot）にはSIGHASH_NOINPUTは導入されないので、当分eltooも導入できないだろうし。

実装方法と今後

↑のコミットメントトランザクションのアウトプットのスクリプトを実装する方法はいくつかあるが、すぐにデプロイするのであればECDSAのAdaptor Signatureに限定される。この場合、Lindellの２P-ECDSAをスクリプトレスに行うことも考えられるけど、Paillier暗号などの追加の暗号仮定の導入とかを考慮すると、少し前に提案されたOP_CHECKMULTISIGを使ったAdaptor Signature↓が現実的だと思う。

techmedia-think.hatenablog.com

もちろんSchnorrベースのAdaptor Sinatureの方が効率的ではあるので、実際のデプロイはSchnorrのアクティベートを待つという選択肢もある。

GrinのPoWアルゴリズムCuckoo cycleとその実装の脆弱性CVE-2020-15899

Grin Cryptography vulnerability

最近公開されたGrinの脆弱性CVE-2020-15899↓について見てみる。

https://github.com/mimblewimble/grin-security/blob/master/CVEs/CVE-2020-15899.md

Cuckoo cycle

GrinはDual Proof of Workという仕組みを採用している。これは１つはASICフレンドリーなPoWアルゴリズム、もう１つはASIC耐性があるPoWアルゴリズムの２つのアルゴリズムを採用したPoW。後者のASIC耐性のあるPoWアルゴリズムとしてGrinが採用しているのがCuckoo cycleで、今回その実装に脆弱性が発見された。※ ちなみにCuckoo cycle自体に脆弱性があるという訳ではない。現に、C++のGrinの実装であるGrin++にはこの脆弱性は無い。

https://github.com/mimblewimble/grin/blob/master/doc/pow/pow.md

折角なのでまずCuckoo cycleがどんなアルゴリズムなのか↑見てみよう。

Cuckoo cycleは与えられたメッセージに対して、ランダムな2部グラフを生成する。2つの部分集合の中にはそれぞれN個のノードがあり、一方のノードからもう一方のノードを結ぶ線をM個のエッジで構成される（同じ部分集合内のノード間を結ぶエッジは存在しない）。

例えば以下のグラフは上半分の偶数を持つ部分集合と、下半分の奇数を持つ分集合の2部グラフになる。

https://github.com/mimblewimble/grin/raw/master/doc/pow/images/cuckoo_base_numbered_minimal.png

これにランダムにエッジを追加したものが↓

https://github.com/mimblewimble/grin/raw/master/doc/pow/images/cuckoo_base_numbered_few_edges.png

この2部グラフは8個のノードと4個のエッジを持っている。つまりN = 8およびM = 4で、8✕4のグラフ。

サイクル（cycle）というのは、2部グラフにおいてあるノードから始まったエッジを辿っていきそのノードで終了するような循環するノードとエッジの関係で、↑のグラフには存在しない。サイクルが発見できるグラフは以下のようなグラフで、以下では赤線が長さ４のサイクルになる。

https://github.com/mimblewimble/grin/raw/master/doc/pow/images/cuckoo_base_numbered_more_edges_cycle.png

このグラフには以下の特徴がある。

  • ↑のようにノードの数Nに対して、エッジの数Mを調整することで、サイクルを見つける難しさや、グラフにサイクルが存在する確率が変動する。ノード数Nに対してエッジ数Mを増やせば、つまりM/Nの値が大きいほど、サイクルが存在する確率が高くなる。
  • ↑のような小さなグラフであれば、ある長さのサイクルが存在するかどうvか判断するのは簡単だが、グラフが大きくなるにつれて、サイクルの検出は難しくなる。

Cuckoo cycleのパズルは↑の2部グラフを使って長さ42のサイクルを見つけることにある。このサイクルを見つけるためには、2部グラフの要素を全て保持するメモリが必要になるので、これがASIC耐性になっている。マイニングにおいては、具体的に以下の計算を行う↓

  1. 新しいブロックのブロックヘッダーを生成する。
  2. ブロックヘッダーのハッシュ値を計算する。
  3. 以下のパラメータを使って、Cuckoo graphジェネレーターを初期化する。
    • ブロックヘッダーのハッシュ値をSIPHASH関数のキーとして使って、エッジを生成するため、各ノードの位置のペア＝エッジインデックスのペアを生成する。
    • コンセンサスルールで決められているグラフのサイズ（↑のNの数）
    • コンセンサスルールで決められている↑のM / N比（グラフに解が存在する確率）を表す値（この値はM = N/2で固定されている）。
  4. Cuckoo Cycle検出アルゴリズムがグラフ内で長さ42のサイクルを見つける。
    1. サイクルが見つかると、proofのBlake2bハッシュが作成され、現在の難易度のターゲットと比較する。
      1. Blake2bハッシュ値の難易度がターゲットの難易度以上の場合、ブロックはトランザクションプールに送信され、ピア間に伝播され、次のブロックの処理に進む。
      2. Blake2bハッシュ値の難易度がターゲットの難易度より小さい場合、無効なので、別のサイクルを見つける。
    2. サイクルが見つからない場合、ブロックヘッダーのnonceをインクリメントし、タイムスタンプを更新し、新しいブロックヘッダーのハッシュ値を計算し、↑の反復を続ける。
    3. サイクルが見つからず、ループがタイムアウトすると最初からやり直して新しいトランザクションを収集し新しいブロックヘッダーを作り直す。

サイクルを見つける難易度を調整するのに、グラフのサイズNと解の存在確率M / Nはコンセンサスルールにより固定されているので、同じルールで動作している限り、難易度の調整はBlake2bハッシュ値のターゲット難易度を使って行われるだろう。

CVE-2020-15899の内容

Grinはこれまで6ヶ月毎に3回のHFを行っており、都度Cuckoo cycleのパラメータが変更されている。ちなみに3回目のHF3はつい最近2020年7月16日にアクティベートされたばかりだ。

脆弱性はHF2を行った際のCuckaroom29で導入された。Cuckaroom29のグラフは {2^{29}}のノードと {2^{29}}のエッジを持つ。エッジインデックスの生成処理は↑と少し違ってて、ペアを作るのに2回SIPHASH関数を実行するのではなく、エッジインデックスに対してSIPHASH関数を実行し、上位32bitおよび下位32bitのワードをそれぞれマスクして生成している。これを導入したPRが#3136で、問題のソースがcore/src/pow/cuckaroom.rs。

このソースは、実は前のCuckarood29の実装core/src/pow/cuckarood.rsから作られたもの。前のCuckarood29のグラフは2部構成で、 {2^{29}}個のノードを {2^{28}}個の２つのグループに分割しているが、Cuckaroom29のグラフは {2^{29}}個のノードが単一のグループ構成になる。この設定の調整を忘れたため、Cuckaroom29の実装はノード数が {2^{28}}に制限されてしまった。つまりノード数が本来意図した数の半分になり、実質ハーフCuckaroom29パズルになる。そしてこれに気付いたのが、HF3の準備で新しい実装Cuckarooz29を用意してたタイミング。

ノード数が半分ではあるが、一応動作はする。28番目のビットが存在するかしないかで。このため、おそらく28番目のノードへのエッジが作られるプルーフを持つブロックは、これまで作られてなかったんだろう。マイナーはちゃんとCuckaroom29として計算していたんだろうけど、Cuckaroom28のグラフとして計算すれば2倍のスピードで計算が可能になる。さらに、上記の下、1,000倍を超える大幅な高速化手法も提案されている。

修正

気付いたのがHF3を控えたタイミングであったため、HF3で新しいCuckarooz29に切り替われば問題無いように思われたが、攻撃者が効率的なHalfCuckaroom29パズルのソルバーを開発し、HF2がアクティベートされたタイミングからのチェーンの履歴を書き換え、HF2〜HF3がアクティベートされるまでの間の累積の難易度が既存のチェーンより高いチェーンを構成すると、期間6ヶ月という大規模なチェーンの再編成が発生する可能性があるため修正された。

修正はHF3のリリースまでの間に、PoWコードの大規模なリファクタリングに紛れるよう偽装されて行われた。以下発見から修正、展開までの流れ。

  • 2020年6月6日：Grinセキュリティチームに脆弱性が通知され、暗号化されたチャットグループがJohn Trompで作成される。
    • この脆弱性は悪用されていないことが確認されている。
    • 展開計画が合意され修正の準備ができる。
    • ネットワークへの攻撃を検出し、keybaseおよびローカルコンソールにアラートを送信するよう構成されたモニターノードがセットアップされる。
    • 現在のCuckarooz verifierにも同じバグがあり、リファクタリング/コード簡略化のPRで直ちに対処する必要があると判断される。
  • 2020年6月7日：Cuckaroozのバグ修正がPR https://github.com/mimblewimble/grin/pull/3343 で導入された。これによりCuckaroomのバグはプロダクションでもそのまま残っている。
  • 2020年6月10日：監視ノードによってプロダクション環境で悪用が検出された場合の緊急行動計画に合意。
  • 2020年6月17日：プランAとしてどのアプローチを取るか合意。修正はHF3を対象とする。@tromp は最終的な4.0.0バイナリがリリースされる少し前に、全ての検証コードのリファクタリングに修正を組み込む。
  • 2020年6月24日：全ての検証コードの大幅なリファクタリングで偽装されたバグ修正がPR https://github.com/mimblewimble/grin/pull/3365 で導入される。
  • 2020年6月26日：@antiochpと@quentinlesceller はPRとそのタイミングについてプライベートで質問し、PRの背景にセキュリティ関連の課題があることを認識するが、詳細は知らせられない。PRがマージされ、修正は同日リリースされたv4.0.0-rc1に含まれる。
  • 2020年7月16日：ブロック高786,240で、ネットワークがv4.0.0に正常にアップグレードされCuckaroomの脆弱性を修正するコンセンサスルールが適用される。
  • 2020年7月24日：Grinコアチームは、修正されたGrinのPoWの重大な脆弱性が間もなく公開されることを通知する。
  • 2020年7月27日：ドキュメントの公開による脆弱性の開示。

Grinにおけるリプレイアタックとその対策

Grin Mimblewimble

リプレイアタックというと、チェーンがハードフォークした際に、片方のチェーンで発生した送金Txが、もう一方のチェーンで意図せずブロードキャストされる＝リプレイされる問題として2017年のフォークコイン誕生の際によく話題に挙がった。

ハードフォークとは関係なく、そんなリプレイアタックがGrinで可能であるとして今ホットなトピックになっている↓

forum.grin.mw

Grinにおけるリプレイアタック

GrinなどのMimmblewimbleを採用したブロックチェーンでは、UTXOは量を秘匿した以下のようなPedersen Commitmentとして認識される。

C = rG + vH

Gはベースポイント、Hは誰もその離散対数を知らない２つめのベースポイントで、rがブラインドファクター、vがコインの量。

Bitcoinの場合、使用するUTXOを指定する際はTXIDとアウトプットのインデックスを結合した36バイトのOutPointが使われるが、Mimblewimbleの場合は単純に↑のコミットメントCが使われる。どのTxの何番目のアウトプットという指定の方法ではない。そのような指定方法をするとMimblewimbleの特徴の１つでもあるトランザクションカットスルーが行えなくなる。

リプレイアタックのシナリオ

↑の特性を悪用し、アリスとチャーリーと共謀して（チャーリーはアリス自身でもOK）、ボブを騙すケースを考える。

  1. アリスはボブが提供する商品を購入するため、自身のUTXO Aをボブに送金する（送金先のアウトプットをBとする）トランザクション Tx1（A→B）をボブと協力して作成し、ブロードキャストする。
  2. ボブはアウトプットBを使ってチャーリーに支払いをするトランザクションTx2（B→C）をチャーリーと協力して作成し、ブロードキャストする。
  3. アリスは再度ボブから商品を購入するため、Tx3をボブと協力して作成するが、アリスはこの時Tx3をブロードキャストすることなく、代わりにTx1をリプレイする。
  4. ボブのウォレットは再度Bを受け取り残高として認識する。この時Tx3がウォレットで保留中などと表示されない場合、ボブは支払いを受け入れる。
  5. アリスは3で注文した長品が届いたら、今度はTx2をリプレイすることで3で支払った料金を回収する。

リプレイアタックの要因

↑のリプレイアタックが成功するのは以下の要因による：

  • GrinではUTXOの重複は許可していない（許可しようという提案はあるが）が、使用済みになれば同じコミットメントのUTXOを作ることができる。そのため、Tx1をブロードキャストした後であればUTXO Aを再度作れるし、Tx2をブロードキャストした後であれば、Tx1をリプレイできる（＝UTXO Bを再度作れる）。
  • トランザクションカーネルの再利用
    トランザクションカーネルは、インプットのコミットメントの合計とアウトプットのコミットメントの合計の差分の公開鍵と、その公開鍵に対して有効な署名で構成される。つまりインプットのコミットメントの合計とアウトプットのコミットメントの合計の差分が同じトランザクションを構成することができれば、その署名は前のトランザクションカーネルにセットされている署名をそのまま利用することができる。これによりボブの協力なくBを使用するTx2をリプレイできる。

また、リプレイTxのインプットは必ずしも同じインプットでなければならないということもない。例えば↑のAのコミットメントがC = 3G + 5Hとかだった場合（実際にはもっと大きな数値だけど）、C1 = G + 2HとC2 = 2G + 3Hとかにすることもできる（もちろんそういったUTXOを予め作っておく必要はあるけど）。

リプレイアタックへの対策

↑のリプレイアタックが発生した場合、ボブのウォレットが3でアリスとボブが新しい支払い用のTx3を共同で作っているので、それがブロードキャストされていない＝ペンディング状態にあることをボブにちゃんと表示できていれば、Tx3が確認できるまで、商品を提供しないという選択をボブはすることができる。とはいえ、これはウォレットの実装によるし、ウォレットが破損したりリストアするような状況においては難しい。

プロトコルレベルで保護しようとするのであれば、最近提案もされているが、カーネルの重複を許可しない＝一意なカーネル（この結果署名の流用はできなくなる）のルールをコンセンサスルールに組み込むというもの。ただこれを組み入れると、カーネルが重複していないかどうかのチェックのコストが追加で発生する。

その他、既存のコンセンサスルールの下で、仕組み的に↑のリプレイアタックを防ぐために以下のような方法が提案されている。

Anchorアウトプットの利用

PayJoins for Replay Protection · GitHub

リプレイアタックを防ぐために、使用することのないNS（Never-Spend）アウトプット＝Anchorアウトプットを利用する。Anchorアウトプットは使用することがなくUTXOのまま存在するアウトプットなのでコインの量は0（コミットメントのv値がゼロ）でいい。

Anchorアウトプットの作成方法は単純で、例えばボブが作るのであれば、以下のような構成のトランザクションTを作ってブロードキャストすればいい。

inputs = [I_Bob]
outputs = [
  Bob_anchor,
  Bob_01,
]

ここでBob_anchorがAnchorアウトプットで、Bob_01は通常のMWアウトプット。このようなUTXOを予め作っておく。

PayJoinトランザクションの構築

リプレイアタックを防ぐために、支払いを受け取る際PayJoinトランザクションを構成する。PayJoinトランザクションはBitcoinで「common input ownership」ヒューリスティックを崩しプライバシーを向上させるために提案されたトランザクションの構成方法で、送金の際に受信者のUTXOもインプットに含める方法（以前はP2EP言われてたもの）。

この時、ボブは↑のTで作成したBob_01をインプットとして提供し、支払いを受け取るためアリスと以下のようなTxを作成する。

inputs = [
  Alice_01,
  Bob_01
]
outputs = [
  Alice_output,
  Bob_output
]

支払いを受ける際、Anchorアウトプットと一緒に作成されたUTXO（↑ではBob_01）をインプットとして提供することで、アリスはこのTxをリプレイできなくなる。また、送信者であるアリスも同様にTのようなトランザクションを使ってAnchorアウトプットを作成し、一緒に作成したAlice_01をインプットとすることで、送信者側にもリプレイ保護を与えることができる。

Anchorアウトプットを生成したトランザクションTからのトランザクショングラフを使ってインプットを提供する限り、リプレイのリスクはなくなる。

なぜリプレイできないのか？

MWトランザクションをリプレイするためには、そのインプットとなるコミットメントを再作成できなければならない。つまりアリスの場合、Alice_01とBob_01を再作成しなければならない。Alice_01は自身が秘密鍵を知っているので再作成することができるが、Bob_01を再作成するためには、ボブが作ったTをリプレイしないといけない。ただ、Bob_anchorがUTXOとして存在しているのでTをリプレイすることはできない。

Bitcoinの開発者からすると、Bob_01は単なるアウトプットなので、同じアウトプットにアリスが送金するトランザクション作ればいいんじゃないか？と思うかもしれないが、Mimblewimbleではそういったことはできない。前述したように、MWのトランザクションの署名は、「インプットのコミットメントの合計とアウトプットのコミットメントの合計の差分の公開鍵と、その公開鍵に対して有効な署名で構成される」ため、Bob_01の秘密鍵の知識なくBob_01へ送金するトランザクションの署名は作れない。

※ Mimblewimbleトランザクションの署名の仕組みについては↓のGBEC解説動画参照。

goblockchain.network

PayJoinトランザクションを使わない場合

↑のPayJoinトランザクションの構成は必ずしも必須条件ではない。ボブは支払いを受け際に、以下のトランザクションのように自身のAnchorアウトプットを追加するのでも良い。

inputs = [Alice_input]
outputs = [
  Alice_output,
  Bob_output,
  Bob_anchor
]

Bob_anchorは使用されないままUTXOとして残るので、UTXOの重複を許可しないGrinの場合、このトランザクションをリプレイすることはできない。

EthereumのDNSを利用したブートストラップノードの探索

Ethereum EIP

EthereumでもEIP-1469によりノード探索プロトコルでDNSがサポートされたので、内容見てみる↓

arachnid.github.io

↓で解説したように、ノードを起動するとハードコードされたブートストラップノードを使って、アウトバウンドピアの接続対象を検索する。

techmedia-think.hatenablog.com

現状ハードコードされているmainnetのブートストラップノードの数は8個で、その中からノードと距離の近い上位３つを選択してノート探索を始めることになる。EIP-1469は、このハードコードされているブートストラップノードリストに代わって、DNSを使ってブートストラップノードリストを入手するための仕組みを定義したEIP。ブートストラップノードがハードコードされていると、ブートストラップノードリストが固定されてしまうし、現在8個とその選択肢が少ないので、それをDNSを使って改善するもの。また、ネットワークの制限とかで、KadmliaベースのDHTが使用できないような環境においては代替手段となる。

DNSレコードの構造

Bitcoin CoreでもソースコードにハードコードされているのはDNSシードなので、↑の導入により似たような仕組みの選択肢が増える。Bitcoinの場合、DNSシードは有効なフルノードのIPを直接DNSのAレコードで返すが、EIP-1469が返すのはTXTレコードになる。これはノードの探索がBitcoinの場合は直接IPアドレスを使うが、Ethreumの場合はノードIDを使って距離の近いノードを探索するためであるのと、TXTレコードで返されるのはノード単体に限らず構造化されたノードリストであるからだ。ここでいうノードリストはEIP-778で定義されたEthereum Node Records（ENR）のこと。

レコードツリーを参照する際のURL

DNSを使ってレコードツリーを参照する際、URL形式で対象のドメインがエンコードされる。現在公開されているmainnetのDNSドメインのURLは↓

enrtree://AKA3AM6LPBYEUDMVNU3BSVQJ5AD45Y7YPOHJLEF6W26QOE4VTUDPE@all.mainnet.ethdisco.net

all.mainnet.ethdisco.netの部分がDNSに問い合わせをするドメインで、@より前のユーザー名の部分はbase32文字列としてエンコードされた33バイトの圧縮公開鍵だ。↑をデコードすると0281b033cb78704a0d956d36195609e807cee3f87b8e9590beb6bd0713959d06f2となる。ノードツリーを参照する際、ルートレコードには署名が付与されており、この署名を作成した秘密鍵に対応するのがこの公開鍵になる。つまり、ルートツリーのデータが正しいことをこの公開鍵を使って検証することになる。

実際に↑のドメインに対してクエリを投げると以下のようにTXTレコードが取得できる。

$ dig -t TXT all.mainnet.ethdisco.net
...
all.mainnet.ethdisco.net. 1799  IN  TXT "enrtree-root:v1 e=XTLPTO7P7CR2V7W2PUJD5QKHMQ l=FDXN3SN67NA5DKA4J2GOK7BVQI seq=1217 sig=iEZZblnqsUvW98vZuhoVswKBM4RKLCVPnIFIfddhYQRjIpO7IVCzJd1v54ezhBUJHCC2sXIWnltosqG1J-LzyAA"

enrtree-rootは、これがツリーのルートであることを示し、v1はバージョンで現在有効なのはv1のみ。

  • e： enr-rootの略でノードを含むサブツリーのルートハッシュでBase32エンコードされている（↑をデコードするとbcd6f9bbeff8a3aafeda7d123ec14764）。
  • l： link-rootの略でリンクサブツリーを含むルートハッシュでBase32エンコードされている（↑をデコードすると28eeddc9befb41d1a81c4e8ce57c3582）。
  • seq： ツリーのシーケンス番号（↑では1217）。
  • sig： TXTレコード内容（この署名を除く）のkeccak256ハッシュに対する65バイトのsecp256k1楕円曲線の署名をURLセーフなBase64エンコードしたもの。

ルートツリーのレコードを取得すると、データの正しさを↑の公開鍵とレコード内容とレコード内の署名値のデータを使って署名検証をして確かめる。

ツリーの探索

↑のルートツリー自体にはノード情報は含まれていないので、enr-rootの値をサブドメインの値として再度DNSへ問い合わせる。

↑の場合だとXTLPTO7P7CR2V7W2PUJD5QKHMQ.all.mainnet.ethdisco.netが次のクエリになる。

$ dig -t TXT XTLPTO7P7CR2V7W2PUJD5QKHMQ.all.mainnet.ethdisco.net
...
XTLPTO7P7CR2V7W2PUJD5QKHMQ.all.mainnet.ethdisco.net. 21599 IN TXT "enrtree-branch:J2QOVIR4UJAYFY7KARSVB4TL7E,SDGK5C4FNX73SNHVQ3VHVLJZHU,FEQ5LEGY3HXJ6JFSPQFTQO6LA4,LE2HQXFZBRNWQBMAVDZ5DH2QBU"
...

と今度はenrtree-branchのTXTレコードが返ってきた。このデータは

  • J2QOVIR4UJAYFY7KARSVB4TL7E
  • SDGK5C4FNX73SNHVQ3VHVLJZHU
  • FEQ5LEGY3HXJ6JFSPQFTQO6LA4
  • LE2HQXFZBRNWQBMAVDZ5DH2QBU

の4つのブランチの情報を表している。この場合さらに、サブドメインの値を上記の値に置換して再度DNSにクエリを発行する（J2QOVIR4UJAYFY7KARSVB4TL7Eであれば、J2QOVIR4UJAYFY7KARSVB4TL7E.all.mainnet.ethdisco.net）。

これを繰り返していくと、最終的に以下のようなenrレコード、つまりノードレコードが返ってくる。

$ dig -t TXT DTLXHBXBBTRK3PIDC6MS5TC3EU.all.mainnet.ethdisco.net
...
DTLXHBXBBTRK3PIDC6MS5TC3EU.all.mainnet.ethdisco.net. 21599 IN TXT "enr:-Je4QGH3fRF3gwheutnIJjnb_gsrmZ1Ww0yHgt4d3K65M0ahUbKLz6y6fI_1REOUTuElodemxwsKgYkUt70DoCbYlasNg2V0aMfGhOAp6ZGAgmlkgnY0gmlwhMOwtZSJc2VjcDI1NmsxoQP1j8zSY7oyJBL_NyRGa713TTAYt_oAyIdQtZwn5geYhYN0Y3CCdl-DdWRwgnZf"
...

このレコードをEIP-778のルールに従ってデコードすればノードの情報が得られる。

まとめるとクライアントが行うノード探索のステップは以下のようになる。

  1. レコードツリーを表すURLのドメイン名に対してTXTレコードをクエリする。
  2. 返ってきたTXTレコードの内容がenrtree-root=v1を含むか検証し、レコードツリーURL内の公開鍵とレコード内容とレコード内の署名を使ってデータの正しさを検証する。
  3. enr-rootの値をサブドメインにしてDNSに対してTXTレコードをクエリする。
  4. クエリの応答値によって処理が別れる。
    • enrtree-branchが返ってきた場合は、そのレコード内のハッシュをサブドメインとして手順3を続ける。
    • enrが返ってきた場合、デコードしノードレコードを検証しローカルのノードストレージにインポートする。

↑を全てのブランチに対して実行すると、最終的に各リーフノードに設定されているノード情報を全て取得できるようになる。

link-root

↑ではenr-rootを探索したが、link-rootは別のドメイン名にある別のリストをリンクするために使用するものとされており、こちらのツリーはリンクのみでノード情報は含まれてなさそう。

既知のDNS

各環境毎のDNSのノードリストは以下のリポジトリで公開されている。

https://github.com/ethereum/discv4-dns-lists

ちなみに↑のいずれの環境のドメインでもlink-rootにサブツリーが設定されているものは無かった。

Ethereumのノード探索の仕組みとエクリプス攻撃とその対策

Ethereum Geth vulnerability

EthereumのP2Pネットワークまわりの仕様について、まずノード探索の仕組みについて理解する。

Ethereumのノード探索の仕組み

Ethereumは分散ハッシュテーブル（DHT）の一種であるKademliaをベースにしたノード検出プロトコルを実装している（Kademlia自体は分散ノードがデータを取得・保存するためのUDPベースのプロトコルだが、Ethereumではノードの検出とルーティングのみに利用している）。

Ethereumのノードが最初にEthereumネットワークに参加する際は、まずソースコードにハードコードされているブートストラップノードにアクセスする。現時点でgethに登録されているmainnetのブートストラップノードは以下の8個で、いずれもAWSもしくはAzureの各地のリージョンでホストされてる。

"enode://d860a01f9722d78051619d1e2351aba3f43f943f6f00718d1b9baa4101932a1f5011f16bb2b1bb35db20d6fe28fa0bf09636d26a87d31de9ec6203eeedb1f666@18.138.108.67:30303",   // bootnode-aws-ap-southeast-1-001
"enode://22a8232c3abc76a16ae9d6c3b164f98775fe226f0917b0ca871128a74a8e9630b458460865bab457221f1d448dd9791d24c4e5d88786180ac185df813a68d4de@3.209.45.79:30303",     // bootnode-aws-us-east-1-001
"enode://ca6de62fce278f96aea6ec5a2daadb877e51651247cb96ee310a318def462913b653963c155a0ef6c7d50048bba6e6cea881130857413d9f50a621546b590758@34.255.23.113:30303",   // bootnode-aws-eu-west-1-001
"enode://279944d8dcd428dffaa7436f25ca0ca43ae19e7bcf94a8fb7d1641651f92d121e972ac2e8f381414b80cc8e5555811c2ec6e1a99bb009b3f53c4c69923e11bd8@35.158.244.151:30303",  // bootnode-aws-eu-central-1-001
"enode://8499da03c47d637b20eee24eec3c356c9a2e6148d6fe25ca195c7949ab8ec2c03e3556126b0d7ed644675e78c4318b08691b7b57de10e5f0d40d05b09238fa0a@52.187.207.27:30303",   // bootnode-azure-australiaeast-001
"enode://103858bdb88756c71f15e9b5e09b56dc1be52f0a5021d46301dbbfb7e130029cc9d0d6f73f693bc29b665770fff7da4d34f3c6379fe12721b5d7a0bcb5ca1fc1@191.234.162.198:30303", // bootnode-azure-brazilsouth-001
"enode://715171f50508aba88aecd1250af392a45a330af91d7b90701c436b618c86aaa1589c9184561907bebbb56439b8f8787bc01f49a7c77276c58c1b09822d75e8e8@52.231.165.108:30303",  // bootnode-azure-koreasouth-001
"enode://5d6d7cd20d6da4bb83a1d28cadb5d409b64edf314c0335df658c1a54e32c7c4a7ab7823d57c39b6a757556e68ff1df17c748b698544a55cb488b52479a92b60f@104.42.217.25:30303",   // bootnode-azure-westus-001

Ethereumのノードを初めて起動するとまず↑のブートストラップノードのノードIDを、自身のルーティングテーブルに追加する。

ノードIDとノード間の距離

ノードIDはノードを識別するためのIDで、↑の値からも分かるように512 bitの楕円曲線secp256k1の公開鍵でもある。つまり楕円曲線の公開鍵のX座標、Y座（各32バイト）のhex値を連結したものがノードID。でも圧縮公開鍵フォーマットにすれば33バイトにできるけど、何で64バイトにしてるんだろう？

ノードが別のノードと接続することでネットワークが形成されていく訳だが、Kademliaでは接続対象のノードを選択する際に、自分との距離が近いノードを選択する仕組みになっている。そのため、各ノードはそれぞれピアのリストを保持しているが、各ノードが全く同じピアリストを保持する訳ではなく、各ノードが保持するピアのリストには距離による偏りがある。この距離は、ノードIDをそれぞれa, bとすると、Ethereumの場合*1それぞれのKeccak-256ハッシュ値を計算し、そのハッシュ値のビット単位のXORを計算し数値にしたものである。つまり↓

ノードa,b間の距離 = Keccak-256(a) XOR Keccak-256(b)

ルーティングテーブル

↑でブートストラップノードのノードIDを、自身のルーティングテーブルに追加すると書いたが、このルーティングテーブルによりピアのリストを管理する。このテーブルのピアリストが、自身がアウトバウンドピアの選択に使われる。ルーティングテーブルは要素を最大k個保持できる複数のbucketで構成されることからk-bucketと呼ばれる。Ethereumの場合、k = 16で、bucketの数は256個（bucketのインデックスをiとすると0 ≦ i < 256）*2。※ 上位のbucketはずっと空のままであることが分かり、Geth 1.8.0以降はbucketの数は17個まで減っている。

発見したノードの情報は、ノード間の距離に応じて各bucketに挿入される。bucket iに格納されるノード情報は、ノード間の距離が {2^{i}〜2^{i+1}}までの範囲のノードの情報になる。そのため、どのbucketに挿入するかは↑の距離の対数を計算すればいい。

ノードa,b間の対数距離 = floor( log2( Keccak-256(a) XOR Keccak-256(b) ) )

新しいノードが見つかると、↑の距離に基づき対象のbucketに挿入されるが、既にbucket内にk個のノードが存在する場合は、bucket内でもっとも長い期間応答が確認されていないノードをピックアップし、PINGパケットを送信する。ノードから応答がない=PONGが返ってこない場合、無効と判断され、そのノードはbucketから削除され、新しいノードのノード情報が追加される。

※ このルーティングテーブルの情報は永続化されないため、ノードが再起動と通常空になる。

初期のノード探索

  1. ノードは↑のルーティングテーブルからターゲット（自分のノードID）と最も近いα個*3のピアをピックアップする。初回起動時は最初に追加したブートストラップノードがあるだけだと思うので、その中から距離の近いものをα個選ぶ形になる。
  2. 選択したα個のノードに対して、ターゲットノードID（自分のノードID）を指定してFindNodeパケットを送信する。
  3. FindNodeを受信したノードは、自身のルーティングテーブルから指定されたターゲットノードIDに最も近いk個のノードリストをピックアップし、それらをセットしたNeighborsメッセージで応答する*4。
  4. k個のノードリストを受け取ったら、このプロセスで新しく発見したノード情報（ノードID、IPアドレス、TCPポート、UDPポート）を自分のルーティングテーブルに追加する。

まだ問い合わせをしていないノードについて↑のプロセスを繰り返す。問い合わせの結果、既に確認済みの最も近いノードよりも近いノードを返さなくなったら（把握している最も近いk個のノードにFIND_NODEを再送信し、応答を得た結果、最も近いk個のノードが変わらなければ）、初期のノード探索は終了する。

ノード探索後

上記のようなノード探索にはUDPが使われ、現在以下の６個のメッセージが定義されている。近隣ノードの探索が終わったら、検出したノードに接続し、ハンドシェイク、チェーンの同期を開始するが、これらはRLPxやDEVp2pプロトコルで行われる。RLPx以降の通信はTCP接続。

UDPメッセージ

現在サポートされているUDPメッセージは↓

  • Ping：ピアに定期的に送られる接続の有効性を確認するためのメッセージ。
  • Pong：Pingメッセージへの応答。
  • FindNode：ピアにターゲットIDの近隣のピアリストを要求するためのメッセージ。
  • Neighbors：FindNodeメッセージへの応答で、ターゲットIDの近隣のピアリストが含まれる。
  • ENRRequest：ピアにノードのレコード情報（ENR）を要求するためのメッセージ。
  • ENRResponse：ENRRequestメッセージへの応答で、現在のバージョンのノードのレコード情報（ENR）が含まれる。

エクリプス攻撃への対応

KademliaベースのEthereumのノード探索の仕組みをみてきたが、この仕組みについて、これまでいくつかのエクリプス攻撃に対する脆弱性が報告されている。

Low-Resource Eclipse Attacks on Ethereum’s Peer-to-Peer Network

この攻撃では、攻撃者が単一のIPアドレスと２台のマシンだけあれば攻撃可能になるという低コストの攻撃方法のペーパー。

https://eprint.iacr.org/2018/236.pdf

ピア接続スロットを独占する攻撃

攻撃方法はシンプルで、ノードが起動して近隣ノードを見つけアウトバウンドピアの接続を確立するまでの間に、攻撃者がターゲットノードに多数の接続を作成し、ノードのTCP接続ピアの最大数maxpeersを独占する。こうなるとノードは新たなピアの接続ができなくなり、エクリプス攻撃が成立するというもの。つまり、一方的なインバウンド接続でノードが接続可能なピアのスロットを独占する攻撃。

攻撃への対策

この攻撃を無効化する方法は簡単で、インバウンドピアの接続数を制限すればいい。Geth v1.8.0ではインバウンドのピア数はmaxpeers数の1/3に制限する実装がされている。

ルーティングテーブルのノード情報を独占する攻撃

上記の対策がされた場合でも可能な攻撃として、↑のペーパーでは、ノードIDを細工して攻撃するアプローチも挙げられている。ノード情報をbucketにマッピングするルールは↑のように明示的に決まっているので、攻撃者は自身が作成したノードIDが標的となるノードのルーティングテーブルのどのbucketに入るか簡単に予測できる。これを利用して、攻撃者はターゲットのルーティングテーブル内のbucketを満たすようなノードIDを多数生成し、ターゲットのルーティングテーブルを埋めることでアウトバウンドピアスロットを独占し、↑と同じ攻撃でインバウンドのピアスロットも独占すればエクリプス攻撃が成功する。

攻撃への対策

Geth 1.8.0では上記の攻撃に対して以下の対策が取られてる。

  • IPアドレスの制限
    ルーティングテーブルにノードを追加する際にIPアドレスの制限を加える。１つのbucketにつき、/24サブネットが同じIPアドレスのノードは2つまでしか許可されず、テーブル全体では/24サブネットが同じIPアドレスのノードは最大10個までに制限される。この対策により、攻撃を可能にするためにはより広い範囲のIPが必要になるので、これにより攻撃のハードルを上げるのが狙い。この制限はBitcoin Coreの/16プレフィックスルールと似ている。
  • シードプロセスを常に実行
    ルーティングテーブルが空でない場合もシードプロセスを常に実行する。こうすることで正直なアウトバウンドピアへの接続をする機会を増やす。
  • リブート時の悪用時間枠の排除
    ↑の攻撃はターゲットに再起動させ、その間にDNSを使った探索（シードプロセス）が終わる前にUDPリスナーに対してPingメッセージを送信することでアウトバウンドのスロットを独占するものになるが、これをノードのシードプロセスが完了してからPingメッセージを処理するようにすることで、攻撃のハードルを上げる。
ネットワークからターゲットを消去する攻撃

これはNTPの攻撃が含まれるので難易度は上がる。↑のUDPメッセージには全てタイムスタンプが付与されていて、UDPメッセージを受信したノードは（リプレイ攻撃への対策として）そのタイムスタンプがローカルの時刻と比較し、20秒以上古かったらUDPメッセージをすべてドロップするようになっている。この振る舞いを悪用し、NTPを攻撃するなどしてターゲットノードのクロックに偽の時刻を設定する。具体的には20秒以上未来の時刻を設定する。すると、

  • ターゲットノードが他のノードから受け取るUDPメッセージは全てドロップされるため、ターゲットは正直なノードを認識しなくなる。
  • 結果、他の正直なノードは（ターゲットノードがレスポンスを返さないので）ターゲットノードを認識しなくなる。

このような状況ができると、攻撃者が自身のクロックをターゲットに合わせた上で接続すればエクリプス攻撃は成功する。

攻撃への対策

ペーパーではタイムスタンプの代わりにnonceを使う方法を提案しているが、現状のパケットフォーマットと互換性がないので採用されなかったみたい。

Eclipsing Ethereum Peers with False Friends

https://arxiv.org/pdf/1908.10141.pdf

これは↑の対策がされた中で、/24サブネットの異なる2つのホストのみで攻撃を可能とする攻撃方法のペーパー。

エクリプス攻撃のためには↑で出てきたように、アウトバウンドとインバウンドのピアを独占すればいい。

Geth 1.8.0でインバウンド接続の上限は制限されたが、インバウンドについてはIPアドレスの制限はないので、1つのIPを使ってターゲットノードのインバウンドスロットを埋める攻撃は可能。

アウトバウンドスロットを埋めるには必ずしも、これまでの攻撃のようにルーティングテーブルを全て埋める必要は実はない。アウトバウンド接続の候補を選択する際、ReadRandomNodes関数でルーティングテーブルから対象ノードを選択するようになっているが、この関数はランダムに選択されたbucketの先頭のみを返すという挙動をしている。これはbucketの先頭のピアが他のプアよりもアクティブであるかレイテンシーが優れているため。ただアクティブかどうかは敵対者がPingをよく送ればいいだけなので悪用される可能性が高い。そのため攻撃者はルーティングテーブル全体を自分のピアで埋める必要はなく各バケットに１つだけノードを挿入できればいい。ルーティングテーブルのbucket数は現在17個なので、各bucketに１つずつ17個のbucketに挿入できればいい。Gethの/24サブネットのルール上、bucket全体で/24サブネットが同じIPは10個まで許可されるので、攻撃には/24サブネットが異なる2つのIPがあれば済む。

攻撃への対策

上記の対策としてGeth 1.9.0から

  • Gethが接続するピアの総数を25から50に倍増。
  • ReadRandomNodes関数がbucketの先頭ではなく、ランダムにノードを選択するよう変更。
  • 同じIPからのインバウンド接続に対しては30秒待機するよう変更。

という変更が加えられ↑の攻撃を不可能にする対策が取られている。

ただペーパーでは、Kademliaベースのノード探索より、Bitcoinで採用しているAddrmanのようなアプローチへの切り替えを推奨している。この点については、確かにノード探索のためにだけであればKademliaベースの仕組みを採用する必要もないようにも思える。

*1:KademliaではノードIDはランダムに生成した160 bitのデータで、ハッシュなどせずそのまま距離の計算に使用する。

*2:bucketの数はおそらく距離の取りうる値によって決まるのだろう。Kademliaではノードの距離は160 bitのノードIDで計算されるのでbucketは0〜160。Ethereumの場合は、ノードの距離はノードIDのKeccak-256ハッシュ値で計算されるので0〜256。

*3: αはシステムの同時実行性パラメータでデフォルト値は3

*4:FindNode要求に4回以上応答できない場合、そのノードはルーティングテーブルから削除される。