Develop with pleasure!

福岡でCloudとかBlockchainとか。

v3トランザクションリレー

最近Bitcoin Coreにv3トランザクションリレーポリシーのPRがマージされたので↓

github.com

v3トランザクションリレーについてまとめてみた。

トランザクションの手数料引き上げ方法と課題

Bitcoinでブロードキャスト済みのトランザクションの手数料を引き上げる方法は、主に以下の2つ。

制限とPinning攻撃

RBFやCPFPのような手数料を引き上げる仕組みは用意されているものの、無条件に実行できるとネットワークに対するDoS攻撃が可能になるため、それぞれ制限が設けられている。主な制限は、

  • BIP125 RBFルール:
  • 最大パッケージサイズの制限:
    CPFPを行う場合、mempool内に101KvBを超える子孫持つ場合、または25個を超える子孫/祖先を持つようなトランザクションはCPFPできない。

LNなどのマルチパーティコントラクトでは、上記の制限を悪用して低手数料のトランザクションをずっとmempoolに留めさせようとするPinning攻撃が問題になる。

RBFのルール3については、攻撃者は高手数料だがサイズが大きく手数料率は低い置換トランザクションを作成する。この場合、手数料率は低いのでマイニングされづらいが、誠実な相手がさらにそのトランザクションを置換しようとすると、高額な手数料の支払いが必要になる。誠実なユーザーのトランザクションがマイニングされると置換により攻撃者のコスト負担はゼロになり、誠実なユーザーのみが高額な手数料を負担した結果だけが残る。

ルール5については、子孫トランザクションも含まれるため、Pinningしたいトランザクションに多数の子トランザクションを作成することで、置換を困難にする。

CPFPの場合は、攻撃者が先に制限に達する大量の子トランザクションを作成することで(もしくはサイズ制限を超えるような)、それ以上CPFPできなくする。

このようなPinning攻撃は、タイムロックなどの条件が設定されているマルチパーティプロトコルにとっては厄介な問題になる。LNのような二者間のプロトコルにおいては、Bitcoin Core v0.19.0で追加されたCPFP carve outというポリシーによって、CPFPにおいて上記制限を超える場合も例外的に子の追加が可能になり、これを利用してPinning攻撃への対策を行ったアンカーアウトプットを導入している*1

techmedia-think.hatenablog.com

このような状況から、マルチパーティプロトコルではRBFではなくCPFP carve outベースの手数料の引き上げを採用している。

v3トランザクション

上記のようなPinning攻撃を回避して手数料の引き上げをより堅牢にするために提案されているのがv3トランザクションリレー。

これまでトランザクションのバージョンは、デフォルトのバージョン1と、OP_CSVのタイムロック機能を利用可能にするバージョン2が利用可能だったけど、今回導入した新しいリレーポリシーを利用可能にするのがバージョン3になる。

ただ、v3はトランザクションのあくまでBitcoin Coreのリレーポリシーに関する仕様であって、コンセンサスルールではない。v3トランザクションは、v2トランザクションと同じコンセンサスルールで評価される。

v3ルール

具体的には、バージョン3のトランザクションには以下のルールが適用される。

  1. BIP-125の置換可能性のシグナリングをしていない場合でも置換可能なトランザクションとして扱われる。
  2. 未承認のv3トランザクションの子孫について、子孫もv3トランザクションである必要がある(承認済みのv3トランザクションの子はv3でなくても良い)。
  3. v3トランザクションは未承認の祖先はすべてv3トランザクションである必要がある。
  4. v3トランザクションは複数の未承認の子孫を持つことはできない。なお、CPFP carve outポリシーはv3トランザクションには適用されない。
  5. v3トランザクションは複数の未承認の祖先を持つことはできない。
  6. 未承認のv3の祖先を持つv3トランザクションは、sigops調整後のトランザクションサイズが1000vB以下であること。
  7. 個々のv3トランザクションについて、パッケージ*2としての手数料率の要件を満たす場合、最小リレー手数料率を下回ることができる。

この結果、mempool内にあるv3トランザクションは子トランザクションを1つだけ持つことができ、v3子トランザクションは未承認の親を1つだけ持つことできる。そして、親子トランザクションはいずれもRBFによる置換が可能。その際、親子トランザクションの数の制限と、子トランザクションのサイズ制限により、RBFのルール3,5を悪用したPinning攻撃を回避できる。

v3リレーが可能になると、マルチパーティプロトコルでもRBFが利用可能になるため、LNの仕様変更も検討されている↓

https://bitcoinops.org/ja/newsletters/2024/01/24/#v3-ln

*1:carve outの例外は、参加者が2人より多いマルチパーティプロトコルでは機能しない。

*2:親子関係のあるトランザクションの順序付きリスト。通常は、トランザクション単体をネットワークにブロードキャストするけど、未承認の親子トランザクションを一緒にブロードキャストしたい場合に、それらをパッケージとしてブロードキャストできるようにしようという現在開発中の機能。どうしてパッケージが必要になるかというと、たとえばLNで、チャネルを閉鎖するのにコミットメントトランザクションをブロードキャストしようとするものの、手数料率が向上し、コミットメントトランザクション作成時の手数料ではmempoolに入らないような場合。CPFPで手数料上げようにも対象の親がmempoolに入らないことには使えないといった状況が起こる。そのため、高手数料な子と親を一緒にリレーできるパッケージのような仕組みが必要になる。

FROSTを利用したマルチシグの設定変更

FROSTはSchnorrベースの閾値署名方式で、プロトコルの内容については過去の記事↓やGBEC動画参照。

techmedia-think.hatenablog.com

このFROSTを利用してBitcoinでマルチシグウォレットの開発を進めているFrostsnapというプロジェクト↓

https://frostsnap.com/introducing-frostsnap.html

の説明の中で、

With FROST you can add or remove signers after key generation while keeping the key the same. FROSTを利用すると、鍵生成後に同じ鍵のまま署名者の追加/削除ができる。

とあったので、具体的にどうやるのか調べてみた。

FROST

マルチシグの参加者数をn、閾値をtとして↑の記事に書いた分散鍵生成を実行すると、各参加者 {P_i}は、秘密鍵のシェア(定数項 {a_{i, 0}})が含まれる多項式

 {f(x)_i = a_{i, t-1}x^{t-1} + a_{i, t-2}x^{t-2} + ... + a_{i, 0}}

を保持し、各係数に対して楕円曲線上のベースポイントを乗算したコミットメント {a_{i, j}G}のリストを他の参加者と共有している状態になる。

また、他の参加者向けに、各参加者のIDで多項式を評価した結果 {(ID, f(ID)_i)}をシェアとして送信し、各参加者は他の全参加者の多項式のシェアを保持している状態になる。

マルチシグの公開鍵は、全参加者の秘密鍵のシェア {a_{i, 0}G}を合算した点= {P = \sum_{i=1}^{n}a_{i, 0}G}になる。

署名生成フェーズでは、↑のシェアを利用して多項式補間を実行して最終的に有効なSchnorr署名を生成する(詳細なプロトコルについては、↑の記事or動画参照)。

FROSTを利用したダイナミックなマルチシグ設定

Frostsnapのリポジトリをみたところ、それっぽいプロトコルの説明はなかったけど、FrostsnapチームのNickのGistにそれっぽい説明があった↓

https://gist.github.com/nickfarrow/64c2e65191cde6a1a47bbd4572bf8cf8

署名者の削除

n人のマルチシグ参加者から、1人削減する(t of nからt of n - 1に変更する)場合。削除されるユーザーがその後の署名プロセスに関与できないようにする必要がある。

この場合、n - 1人で再度シェアを生成し直す。この時、各参加者が保持する元のマルチシグの公開鍵Pに対して有効なシークレットシェアは変わらないようにする必要がある。これは分散鍵生成において、各参加者が再生成する多項式の定数項( {a_{i, 0}})については元の値を使用し、それ以外の項の係数は新たに生成しなおし、更新した多項式で生成したシェアを他の参加者に配布することで実現できる。

この場合、n - 1人の参加者が保持する各参加者のコミットメント値およびシェアの値は異なるものになるが、元の公開鍵Pに対して有効なシークレットシェアは有効なままになる。

上記のようにシェアを定期的に再生成するようなプロアクティブな秘密分散法を用いると、シェア更新後は古いシェアを攻撃に使うことはできなくなる。

閾値の削減

続いて、閾値tを削減する(t of nからt - 1 of n - 1に変更する)場合。

この場合は、削除する参加者のシークレットシェアを他の全参加者に開示する。各参加者はそのシェアを使って署名シェアを作成する。

nを減らさずにtだけ減らす場合、つまりt - 1 of n - 1ではなくt - 1 of nにする場合は、後述する方法で署名者を新たに追加する必要がある。

この方法の場合、削除対象の参加者のシークレットシェアが必要になるため、デバイスの紛失などでシークレットシェア自体にアクセスできないようなケースでは機能しない。

署名者の追加

署名者を追加して、n + 1にする(t of nからt of n + 1に変更する)場合は、削除より少し複雑になる。↑のGistでは、二通りの方法が説明されている:

Repairable Threshold Scheme

1つめは、シェアの修復を可能にする修復可能な閾値スキーム(Repairable Threshold SchemeRTS)の一種を利用するアプローチ↓

techmedia-think.hatenablog.com

フラグメントの共有

もう1つの方法は、予め決めた数(kとする)だけ後から署名者を追加するアプローチ。

  1. 鍵生成プロセスにおいて、各参加者は生成した多項式を使って、通常n個のインデックスに対してn個をシェアを作成する代わりに、n + k個のシェアを作成する。つまりk個の追加のシェアを計算する。このk個の追加シェアは後から署名者を追加するのに使用される。
  2. 各参加者はk個の追加シェアに対して、閾値tでシャミアの秘密分散法を用いて、n個のフラグメントを生成する。つまり、k × n個のフラグメントが生成される。そして生成したフラグメントを他の参加者と共有する。
  3. 新しい参加者(インデックスをn + 1とする)を追加する場合、t人の参加者が対象のインデックス(n + 1)に属するすべてのフラグメント送信する必要がる。結果、n × t個のフラグメントが集められたら、それらから新しい参加者用のシークレットシェアが作成できる。

閾値tを増やす

閾値tを増やす場合は、各参加者が生成する多項式の次数を増やし、全員が古い多項式を削除することを信頼する必要がある。次数を増やした多項式を生成するのは↑の署名者の削除と同様のアプローチでできそうだけど、後者のトラストポイントは残ってしまう。

というのが、FROSTを利用したマルチシグの設定変更の概要みたい。まだ実装や安全性の評価は行われていないようなので、利用可能になるまではまだ時間がかかると思われるけど、暗号技術だけでマルチシグの設定が変更できるというのは、おもしろい技術だ。マルチパーティでUTXOを共有するようなプロトコルでも、活用できるかも?

Bitcoin Core v22.0未満に存在したブロック遅延バグの開示

Optechのニュースレターに掲載されていた、Delving Bitcoinフォーラムで開示されたBitcoin Core v22.0より前のバージョンに存在したブロック遅延攻撃を可能にする脆弱性

https://delvingbitcoin.org/t/block-stalling-issue-in-core-prior-to-v22-0/499

脆弱性自体は3年前に責任ある開示が行われv22で修正されているけど、まだv22未満のノードを実行しているユーザーがいることから開示されたみたい。

脆弱性を悪用するとLNなどのタイムロック系コントラクトを狙った攻撃を行えるが、↓の攻撃内容を見る限り攻撃を成功させるのもハードル高そう。

ブロック受信の遅延

まず攻撃をするためには、コンパクトブロックリレーを最初に無効化する必要がある。

Bitcoin Coreはマイニングされたブロックの受信にBIP-152で定義されているコンパクトブロックリレーを使用している。BIP-152については、↓

techmedia-think.hatenablog.com

BIP-152には実装に関して以下の記述がある:

充分なインバウンドの帯域幅は持つノードの場合、3つまでのピアに対して最初の引数に1をセットしたsendcmpctメッセージを送信する(=high-bandwidthモードで動作させる)ことを推奨する。可能であれば、ここで選択する3つのピアは過去の実績において素早くブロック情報を返すピアを選択することが推奨され、ノードはそれらのピアからほんの0.5*RTTでブロックを受信することが可能になる。

ノードは(アウトバウンドの帯域幅をムダに使用することになるため)3つ以上のピアにhigh-bandwidthモードのsendcmpctメッセージを送ってはならない。

この結果、Bitcoin Coredeha高帯域幅のコンパクトブロックリレーを行う対象として、ノードに迅速にブロックの情報を提供するピアを3つ選択するようになっていた。

つまり、攻撃者が誠実なノードよりも速くブロックを提供できれば、このコンパクトブロックリレーのスロットを占有できる。攻撃にあたっては、まずはこれを占有して、コンパクトブロックリレー経由のブロックの通知を実質無効にする。コンパクトブロックリレーが有効に機能しないと、他のピアから新しいブロックのアナウンスを受け取り、従来のBLOCKメッセージを使って新しいブロックを受け取るしかない。

攻撃手順

  1. 攻撃者は、被害者のノードに対して、他のピアよりも速く新しいブロックを提供することで、ノードのコンパクトブロックリレーの3つの接続スロットをすべて占有する。
  2. 被害ノードとの間に1とは別にN個の異なる接続を開く。LNを対象として攻撃する場合、LNノードのCLTV deltaが40の場合はN = 50。※ ただし、このN個の接続は被害者ノードのコネクションマネージャーのvNodesベクトル内で連続している必要がある。
  3. 新しいブロックがマイニングされたら、N個の接続の内、先頭の接続が、他の誠実なピアと競争して、新しいブロックを被害ノードにヘッダーファーストで通知する。成功したら、被害ノードのmapBlocksInFlightにエントリーが追加される。その後、BLOCKメッセージを使って新しいブロックを送信する必要があるが、ここでその送信を遅延させて対象ブロックを配信しない。この時、被害ノードがブロックを待つのは10分まで。
  4. その間、1で設定したコンパクトブロックリレーの接続は新しいブロックについて何もアナウンスしない。
  5. 10分経過する手前で、先頭の接続は、無効なブロックをBLOCK`メッセージで送信する or 接続を単に切断する。
  6. そうなると、被害ノードはvNodes内の次の接続を選択して、遅延しているブロックを要求する。
  7. この次の接続でも攻撃者は同様の振る舞いを行い、ブロックの送信を遅延させる。
  8. これを繰り返すことで、N×10分間(N = 50の場合は約500分)被害ノードには新しいブロックがリレーされなくなる。

LNでの影響

↑の攻撃では、攻撃者によりコンパクトブロックリレーが実質無効化され、さらにN個の接続が連続して被害ノードのvNodesに挿入される必要がある。

もしそういう状況になると、LNで支払いを転送している場合に、そのHTLCの金額を盗む攻撃が可能になる可能性がある。具体的には、被害者BのLNノードに対して、攻撃者のノードM1とM2がそれぞれチャネルを開いている状態で、以下の経路で支払いが転送されるケースが対象になる。

M1 -> 被害者B -> M2

各LNノードのHTLC deltaの設定値を40と仮定した場合、攻撃のシナリオは以下のようになる:

  1. M1が上記の経路でM2に支払いを送信する。現在のブロック高をTとした場合、B→M2のHTLCはT + 40でタイムアウトし、M1→BのHTLCはT + 80でタイムアウトする。
  2. T + 38くらいで(もっと前でもいい)M1とM2が上記のブロック遅延攻撃を開始する。
  3. まずM2がBとのチャネルを強制クローズするTxをブロードキャストし、それがT + 39で承認される。
  4. 続いて、M2はプリイメージを使ってHTLCを請求するTxをブロードキャストし、それがT + 40で承認される。
  5. 今度はM1はT + 40でBとのチャネルを強制クローズし、それがT + 41で承認される。
  6. M1はT + 80まで待って、HTLCのタイムアウトTxをブロードキャストし、それがT + 81で承認される。
  7. M1とM2がそれぞれHTLCの金額を入手したので攻撃を止める。

この攻撃でも、Bのノードがmempoolを監視していれば、4の後でプリイメージをmempoolから抽出してM1のHTLCを回収できる。ただ、攻撃者がマイナーと協力して4のトランザクションP2Pネットワークにブロードキャストせずに直接ブロックに格納してもらって配信すると、Bにはブロックが届かないためプリイメージを知ることができず攻撃の影響を受ける。

修正内容

この問題に対する修正のPRは以下の2つ。

ということで、攻撃が成功する可能性は低いと思うけど、まだアップデートしていない場合は要アップデート。

Repairable Threshold Scheme

最近、Schnorrベースの閾値署名スキームFROSTをベースにして、暗号技術だけでt-of-nのマルチシグの設定を動的に調整可能にする提案が行われている。その中で、母数nの数を増やす際に利用されているのが、RTS(Repairable Threshold Scheme)。

RTSは、シャミアの秘密分散法などを使って、複数のパーティでシェアを分散して保持するスキームにおいて、後から参加者のシェアを復元できるようにするスキーム。↑の提案では、既存のシェアの復元ではなく、新しい参加者用に新しいシェアを作るのにRTSを利用することで、母数を増やす。

今回は、↓サーベイ論文に掲載されている内の1つEnrollementスキームについて調べてみた。

https://eprint.iacr.org/2017/1155.pdf

RTS

論文は、ディーラーがいるモデルで書かれており、参加者の母数をn、閾値をtとした場合、ディーラーはシークレット値を含むt-1次の多項式f(x)を生成し、n人の参加者に対して、割り当てられたインデックス {ID_i}多項式を評価した結果 {(ID_i, f(ID_i))}をシェアとして配布する。

この場合、多項式を知っているディーラーがいればシェアの復元は可能だが、ディーラーが利用できない場合でも、閾値数分の参加者がいればシェアを復元できるようにするのがこのスキームの目標。

RTSをt - 1人で実行できると追加のシェアが作成され閾値tを超えるシェアを入手できてしまうため、必ずt人以上で実行しないと再構築できないようなプロトコルになっている必要がある。

※ また、閾値分のシェアが集まれば多項式補間で多項式が復元できシェアを計算できるようになるが、シェアを集める参加者が登場することになり実質ディーラーとなれるので、そういうアプローチではない。

シェアの復元

シェアを復元したい参加者を {P_r}、復元を支援するt人の参加者を {P_1, ..., P_t}とする。各参加者が保持しているシェアを {\phi_i = f(ID_i)}とした場合、 {\phi_r = f(ID_r)}を求めるのが目標。

ラグランジュ補間公式を利用すると {f(ID_r)}は以下を計算することで入手できる。

 {f(ID_r) = \lambda_1(ID_r)\phi_1 + ... + \lambda_t(ID_r)\phi_t}

ここで、各ラグランジュ係数 {\lambda_j(ID_r)}(1≦ j ≦ t)は、

 {\displaystyle \lambda_j(ID_r) = \Pi_{0 \leq m \leq t, (m \neq j)} \frac{ID_r - ID_m}{ID_j - ID_m} =  \frac{(ID_r - ID_1) \cdot \cdot \cdot (ID_r - ID_t)}{(ID_j - ID_1)\cdot \cdot \cdot (ID_j - ID_t)}}

であり、各参加者の識別子( {ID_1, ..., ID_t})が分かっていれば計算できる。

Enrollementプロトコルでは以下の手順で、 {P_r} {\phi_r}の値を計算できるようにする。

  1. t人の各参加者 {P_i}は、 {\lambda_i(ID_r)\phi_i = \sum_{j=1}^{t}\delta_{i, j}}となるようなt個のランダム値 {\delta_{i, j}}(1≦ j ≦t )を生成する。各参加者は自分のシェアと上記のラグランジュ係数から {\lambda_i(ID_r)\phi_i}を計算できるので、t - 1個の {\delta_{i, j}}をランダムに生成して、最後の値は {\lambda_i(ID_r)\phi_i - \sum_{j=1}^{t-1}\delta_{i, j}}で計算すればいい。
  2. 各参加者 {P_i}は、計算した {\delta_{i, j}}を他の支援者 {P_j}に送信する。
  3. 各参加者 {P_j}は、 {\sigma_{j} = \sum_{i=1}^{t}\delta_{i, j}}を計算し、 {\sigma_{j}}を新しい参加者 {P_r}に送信する。
  4.  {P_r}は、 {\phi_r = \sum_{j=1}^{t}\sigma_j}を計算し、シェア {\phi_r}を入手する。

1〜4の計算結果は、求めたかった最初の {\displaystyle \phi_r = \sum_{i=1}^{t}\lambda_i(ID_r) \phi_i}と同じになる。

各参加者は自分のシェア(正確にはラグランジュ係数を掛けた {\lambda_i(ID_r)\phi_i})をt個分割して、他の参加者に配布し、それを全参加者分集めたら {P_r}が自身のシェアを計算できるようにしてるっぽい。

btcdで発見された相対的タイムロックのコンセンサスバグ

先日、Delving Bitcoinで開示された、btcdで発見された相対的タイムロックのコンセンサスバグについて↓

https://delvingbitcoin.org/t/disclosure-btcd-consensus-bugs-due-to-usage-of-signed-transaction-version/455

相対的タイムロック

トランザクションの相対的なタイムロック機能は以下の2つのBIPで定義されている。

これらの仕様はソフトフォークとして2016年6月にBitcoinに導入された。

今では、ライトニングネットワークなどさまざまなコントラクトプロトコルの構成要素の1つとして利用されている。

BIPにも記載されているように、この機能をトランザクションで有効にするためには、トランザクションのバージョンを2以上に設定する必要がある(ソフトフォーク前に事前署名したトランザクションが無効にならないようにするための措置)。

バグの内容

問題はトランザクションのバージョンの型。元々Bitcoinの実装では、このバージョンは符号付き整数で管理されている。バージョンを負の値として解釈することができる。

ただ、BIP-68の参照実装のセクションのコード内には、

tx.nVersion is signed integer so requires cast to unsigned otherwise we would be doing a signed comparison and half the range of nVersion wouldn't support BIP 68.

と、符号付き整数(int32)から符号なし整数(uint32)へのキャストするよう記載されている。符号付き整数のまま比較すると、バージョンのとり得る値の半分がBIP 68をサポートできなくなるため。

Bitcoin Coreではこのキャストを行っているが、btcdではこのキャストが行われていなかったというのがバグの内容。

バグの影響

btcdでは上記のキャストが行われないため、符号付き整数として解釈した場合に、負の値のバージョンを持つトランザクションを構築することが可能になる。

そのようなトランザクションがあると、

  • Bitcoin Coreでは相対的タイムロックのルールを強制する。
  • btcdから見ると負の値で2未満なので相対的タイムロックの適用対象外とみなされる。
    たとえば、OP_CSVロックされているUTXOを使用するトランザクションを構成し、事前署名していても、OP_CSVの評価時にTxのバージョンが2未満であると解釈され無効なトランザクションとして判定される。

ただ、負の値にするためには最上位bitが1になる必要があるので、符号なし整数としては、2147483648以上の値をバージョンとして指定する必要があるけど、

  • そういったバージョンを設定したトランザクションを作成する一般的なウォレットは無いだろうし、
  • Bitcoin Coreのリレーポリシーで現在許可されているバージョンは最小値が1、最大値が2なので、負の値のバージョンを持つトランザクションは拒否される(マイナーの協力でもない限りそういったトランザクションをブロックに含めるのもハードル高い)。

ただ、実際に発生するとチェーン分岐が発生する可能性があり、

  • btcdを使用しているライトニングノードは、正しいチェーンの更新を受信できず、資金を失うリスク
  • 悪意あるマイナーが(実質競合がいない)btcdチェーンでマイニングを続け、ユーザーに無効な支払いを受け入れさせる可能性
  • マイナー自体がbtcdを使用している場合、無効なチェーンのマイニングを継続してリソースを無駄に消費する

といった影響が考えられるので、btcd使っている場合はv0.24.0へのアップグレードは必須。

バグの修正

修正はシンプルで、上記のキャストをするようにするというもの。修正のPR自体は、gofmtを適用するPRで、その中にuint32へのキャスト処理を入れ込んだみたい。

また、btcd以外にbitcoin-sでも修正が行われている↓

https://github.com/bitcoin-s/bitcoin-s/pull/5346

今回影響なかった、Bitcoin Coreにも符号付き整数として解釈した場合に負の値になるバージョン(0xffffffff)のテストデータが新しく追加されてる↓

https://github.com/bitcoin/bitcoin/pull/29291

タイムライン

開示までのタイムラインは↓

  • 2023-05-22 Lightning Labsへの最初の開示
  • 2023-06-21 修正PRがbtcdにマージ
  • 2023-12-31 btcd v0.24.0リリース
  • 2024-01-22 開示

修正からリリースまでは結構あいてる。標準のリリースサイクルに含めたということなのかな?