Develop with pleasure!

福岡でCloudとかBlockchainとか。

Vault用のopcodeの導入を提案するBIP-345

少し前に、BitcoinでVaultを実現するために2つのopcodeを導入するソフトフォークの提案がBIP-345として登録された↓

https://github.com/bitcoin/bips/blob/master/bip-0345.mediawiki

Vaultとは?

Vault(金庫)は、その名前から分かるようにビットコインを安全に保管するための仕組み。

Bitcoinのような暗号通貨の場合、秘密鍵が漏洩/盗難にあうと、それは資金の損失につながる。金額が大きくなるほど、秘密鍵漏洩のリスクが大きくなる。自分が知らない間に盗まれた秘密鍵によって資金が勝手に使われることがないように、より堅牢な資金保護の仕組みを提供するのがVaultの目的。

flowchart LR
  A[UTXOをVaultへデポジット] -.-> C[保管されたコインを事前に指定したリカバリーパスに移動]
  A ---> B[引き出しをトリガー] 
  B -.-> C
  B --タイムロック期限後--> D[引き出しの完了]

具体的には、資金を以下の機能を持つVault(スクリプト)に預ける:

  • 預けた資金を引き出す場合、引き出しを申請してから資金を実際に手に入れるまで一定の待機期間がかかる。
  • 待機期間の間であれば、申請した引き出しを取りやめ資金をリカバリーすることができる*1

つまり、攻撃者に秘密鍵を奪われ、攻撃者がその資金を引き出そうとしても、そこには遅延時間が設けられ、それに気づいた所有者がその間に資金を取り戻せるようにしようというもの。

このようなVaultの提案は、

などがある。

BIP-345 Vault

BIP-345の提案はこれまでの汎用的なCovenantsを使用したVaultの構成ではなく、Vault専用の2つの新しいopcodeをソフトフォークで導入し遅延時間とリカバリーを可能にする特殊なCovenantsを可能にしてVaultを構成できるようにしようというもの。2つの新しいopcodeは、いずれも、Tapscriptで予約されているOP_SUCCESS系のopcodeを再定義することで導入される(witness version 1=Taprootを使用した構成になる)。

上記のVaultの操作をサポートするのに、以下の4種類のトランザクションが登場する:

Vaultへのデポジット

VaultトランザクションでVaultに資金をデポジットするには、少なくとも2つのリーフ(トリガー用、リカバリー用)を持つTaptreeを使って以下のようなTaprootのscriptPubkeyを構成する。

graph BT
  A[トリガーリーフ] --> B[Taptree]
  C[リカバリーリーフ] --> B
  D[Internal key] --> E[Vault P2TR]
  B --> E

このP2TRアドレスに送られたコインを使用する方法は、各リーフを使ってアンロックする方法と、内部鍵(Internal key)を使ってSchnorr署名を作成する方法*4の3通り。2つのリーフのスクリプトのは以下のような構成になる:

トリガーリーフ

トリガーリーフは新しく導入されるOP_VAULT opcodeを使った以下のようなスクリプトになる。OP_VAULTは、OP_SUCCESS1870xbc)を再定義する形で導入される。

[trigger-auth] <遅延時間> 2 <leaf-update-script-body> OP_VAULT

trigger-authの部分は、この条件を使ってVaultからの引き出しをトリガーするための認可条件で、ウォレットの設計者が任意の条件を設定できる。例えばある公開鍵の秘密鍵を持つものに対して認可する場合は、trigger-authは以下のスクリプトになる。

<trigger-auth-pubkey> OP_CHECKSIGVERIFY

つまり、公開鍵trigger-auth-pubkey対して有効な署名を作れる人のみがこれをトリガーできる。

残りの部分は、OP_VAULTによって評価されるものなので、OP_VAULTの挙動と合わせてみていく。

OP_VAULTはスタックに以下の項目がある前提で実行される:

<leaf-update-script-body>
<push-count>
[ <push-count> leaf-update script 用のデータ項目の数 ]
<trigger-vout-idx> 
<revault-vout-idx>
<revault-amount>

leaf-update-script-bodyは、OP_VAULTによって更新されるリーフスクリプトの断片。サンプルとして以下のスクリプトが掲載されている。

OP_CHECKSEQUENCEVERIFY OP_DROP OP_CHECKTEMPLATEVERIFY

OP_CHECKTEMPLATEVERIFYは未導入なので、導入されていない場合は以下のようなスクリプトになる。

OP_CHECKSEQUENCEVERIFY OP_DROP OP_CHECKSIG

いずれにせよ、相対的なタイムロック(OP_CSV)が付与され、これが引き出しのトリガーに対して遅延時間を設定する。

OP_VAULTの動作は↓

  1. スタックからleaf-update-script-bodyをポップし、
  2. スタックからpush-countをポップする。
  3. push-count個分の要素をスタックからポップする。
  4. 3の要素をプレフィックスとして1のスクリプトと結合し、leaf-update-scriptを完成させる。
  5. スタックから、trigger-vout-idxrevault-vout-idxrevault-amountをポップする。
  6. スクリプトのsigopsバジェットを60デクリメント*5
  7. trigger-vout-idxがwitness v1 program(Taproot)かチェック
  8. 現在評価中のリーフスクリプトを4のleaf-update-scriptと置き換えてTaptreeを更新し、そから導出したscriptPubkey(P2TR)と、triggerOutのscriptPubkeyが合致するかチェック
  9. revaultOutのscriptPubkeyが現在評価中のscriptPubkey(P2TR)と合致するかチェック
  10. triggerOutの金額とrevaultOutの金額が現在評価中のインプットの金額以上であることをチェック
  11. インプットの金額からrevaultOutの金額を差し引いた金額がtriggerOutの金額になっていることをチェック
  12. すべての検証をパスしたらスタックにTrueをプッシュ

というもの。つまり、OP_VAULTは、

  • Taptree内のトリガーリーフのスクリプトを、leaf-update-script-bodypush-count個分のデータで構成されるスクリプトに更新した新しいP2TRスクリプトトランザクションアウトプットに作られるように強制する。
    • これにより、Vault作成時の条件の内部鍵とリカバリーリーフは同じまま、トリガーリーフのみが遅延時間を設けたスクリプトに更新された宛先宛にVaultの資金を移動する。
    • リカバリーリーフは同じままなので、移動した資金はリカバリー条件を使っていつでも回収できる。
  • Vaultから資金を引き出す際に、全額引き出すのでなく、一部だけ引き出せるように、残しておく資金は元のVaultと同じ宛先に移動するRevault機能をサポートしている。
    • 全額引き出す場合はrevault-vout-idx-1を設定し、revault-amountは0
トリガートランザクション

先程のトリガーリーフのスクリプト

[trigger-auth] <遅延時間> 2 <leaf-update-script-body> OP_VAULT

について、leaf-update-script-bodyOP_CHECKSEQUENCEVERIFY OP_DROP OP_CHECKTEMPLATEVERIFYとした場合、トリガートランザクションでこの条件をアンロックするためにwitnessとして提供される項目をスタックに入れると↓

<Taprootのcontrol block(トリガーリーフへのマークルパスを含む)>
<トリガーリーフスクリプトのペイロード>
<trigger-auth-pubkey-signature>
<target-CTV-hash>
<trigger-vout-idx>
<revault-vout-idx> (Revaultしない場合は-1)
<revault-amount>

となり、このスタックに対してTaprootのscript-pathの検証が行われ、トリガーリーフの認可条件(trigger-auth)が実行され、その後OP_VAULTを実行する際のスタックの状態は↓

<leaf-update-script-body>
2
<遅延時間>
<target-CTV-hash>
<trigger-vout-idx>
<revault-vout-idx>
<revault-amount>

ここでは、push-count = 2であるため、遅延時間target-CTV-hashがスタックからポップされ、それをleaf-update-script-bodyと結合したスクリプトが更新用のスクリプトになり、triggerOutのP2TRの構成要素になる。

leaf-update-script-bodyOP_CHECKSEQUENCEVERIFY OP_DROP OP_CHECKSIGの場合は、target-CTV-hashの代わりに公開鍵をwitnessで提供する形になると思われる。

トリガートランザクションでは、リカバリーリーフと、↑で更新された遅延付きスクリプトleaf-update-script)で構成されるP2TR宛にVaultの資金が移動されるので、遅延期間が終われば、leaf-update-scriptを満たせす引き出し用のトランザクションを完成させ、資金の引き出しが完了する。

target-CTV-hashや、Revaultの情報はトランザクションのwitnessで提供されるため、Vaultから資金を引き出す際に、引き出し先や金額を決めればいいようになっている。これまでのCovenantsではこれらはVaultにデポジットする段階で決めておく必要があった。

リカバリーリーフ

リカバリー用のリカバリーリーフは新しく導入されるOP_VAULT_RECOVER opcodeを使った以下のようなスクリプトになる。OP_VAULT_RECOVERは、OP_SUCCESS1880xbd)を再定義する形で導入される。

[recovery auth] <recovery-sPK-hash> OP_VAULT_RECOVER

recovery authはオプションで、この条件でリカバリーをするための認可条件で、trigger-authと同様ウォレットの設計者が任意の条件を設定できる。

OP_VAULT_RECOVERはスタックに以下の項目がある前提で実行される:

<recovery-sPK-hash>
<recovery-vout-idx>

recovery-sPK-hashは元々リーフスクリプト内にあるデータで、32バイトのハッシュ値

OP_VAULT_RECOVERの動作は↓

  1. スタックからrecovery-sPK-hashをポップし、32バイトかチェック
  2. スタックからrecovery-vout-idxをポップする。
  3. recoverOutのscriptPubkeyについてタグ付きハッシュtagged_hash("VaultRecoverySPK", recoveryOut.scriptPubKey)を計算し、その値がrecovery-sPK-hashと一致するかチェック
  4. recoverOutの金額がインプットの金額以上であるかをチェック
  5. すべての検証をパスしたらスタックにTrueをプッシュ

というもの。つまり、OP_VAULT_RECOVERは、リーフスクリプトでコミットされている宛先(recovery-sPK)にVaultのコインが全額送られることを強制する。

RBFのシグナリング

また、コンセンサスルールではないけどBitcoin Coreのポリシーとして、Pinning攻撃を防ぐため、リカバリーリーフを使用するリカバリトランザクションは、RBFによるトランザクションの置換可能性をシグナリングする必要がある。

具体的には、リカバリトランザクションnVersionが3ではない場合*6OP_VAULT_RECOVERインプットのnSequence0xffffffff - 1未満でなければならない。

OP_CTVとの関係

↑のトリガーリーフ内のleaf-update-script-bodyでは、BIP-119のOP_CHECKTEMPLATEVERIFY(Covenants)を使って、引き出し先を指定する方法が推奨されている。また、このソフトフォークの展開も、BIP-119と同時であることが望ましいとされている。

BIP-345は厳密にBIP-119に依存しているわけではないものの、OP_VAULTによる指定されたTapleafの更新とOP_VAULT_RECOVER自体には、遅延時間の設定や送付先のアドレスの強制は機能として含まれない(外だしされている)ので、OP_CSVによる遅延やOP_CTVによって最終的な宛先を強制する仕組みとの組み合わせが必要になる。

ただ、トリガートランザクションで指定するtarget-CTV-hashで、引き出し先をOP_CTVでコミットしたいケースってどんなケースなんだろう?

*1:よりセキュアに管理さているオフラインの鍵を利用するなど

*2:安全な一時鍵の削除や、金額と引き出しのパターンに事前コミットする必要があるなど、いくつかの制約がある

*3:金額、宛先手数料の管理はすべて事前に決めたものになる

*4:内部鍵はリカバリーパスで使用する鍵と同等のセキュリティが必要になる。内部鍵によりこのP2TRがVaultであったことが開示されなくなるというメリットはあるもの、セキュリティ上の懸念がある場合は内部鍵を使用不可能なNUMSポイントにするのも可。

*5:8のtrrigerOutの有効性チェックの際に、TaprootのControl blockの長さに比例する楕円曲線スカラー乗算とハッシュ計算の実行が必要になるため、そのコストをsigopsのカウントに加味する

*6:v3トランザクションリレーが導入されると、バージョン3のトランザクションはすべて置換可能性のシグナルになるため。

Bitcoin Coreに実装された変異ブロックの早期検証

最近Bitcoin Coreにマージされた変異ブロックに対する早期検証ロジック↓

github.com

変異ブロックとは?

変異ブロック(Muted Block)とは、新しく生成された有効なブロックの一部を変更した無効なブロックではあるけど、ハッシュ値が元のブロックと同じブロック。こういった変異ブロックを作成する方法は、いくつかある。

1.マークルツリーの曖昧さを利用する

Bitcoinでブロックを作成する際、ブロック内の全トランザクションのハッシュをリーフノードとしたマークルツリーを構成し、そのルートハッシュをブロックヘッダーにセットするようになっている。

ただ、このトランザクションのコミット方法とルートハッシュの計算方法には、同じマークルルートを導出可能なハッシュのリストを簡単に構築できるという欠陥がある。トランザクションの数が奇数個の場合、不足する最後の要素はその前の要素のハッシュをコピーして偶数にしてツリーの親ノードを計算するようになっている。

例えば、リーフノードの値がa, b, cの3つのリストにコミットするマークルツリーのルートハッシュと、リーフノードがa, b, c, cの4つのリストにコミットするマークルツリーのルートハッシュは同じ値になる。

つまり、トランザクションが奇数個のブロックについて、最後のトランザクションをコピーしてそれを追加したブロックを作れば無効な変異ブロックを作成することができる。最後に追加したトランザクションは1つ前のトランザクションと同じであるため(同じUTXOを二重使用しようとするトランザクションなので)コンセンサスルール上無効なトランザクションになる。

ちなみに、こうった曖昧さの問題もあり、Taprootのスクリプトツリーを構成する際は、タグ付きのハッシュを利用するようになっている。

2.トランザクションのwitnessデータを変更する

Bitcoinのブロックヘッダーは上記のようにトランザクションのデータから作成される値にコミットするようになっているけど、この時segwit系のトランザクションのwitnessデータは、このハッシュには含まれていない。ただ、ブロックヘッダーにはコミットされないけど、代わりにブロック内のコインベーストランザクション内にコミットされる。witnessを含むトランザクションのハッシュについて、上記と同様にマークルツリーを構成し、そのルートハッシュをコインベーストランザクションのアウトプットにセットする必要がある。

ただ、ブロックヘッダーにはコミットされないので、ブロック内のsegwitトランザクションのwitnessデータを変更し(無効なものにし)ても、ブロックヘッダーのハッシュ値は変わらないため、これを利用して無効な変異ブロックを作成することができる。

3.2つのトランザクションハッシュ値と合致する無効なトランザクションを作成する

方法は1と似ているけど少しだけ複雑。2つの有効なトランザクションのハッシュ(それぞれ32バイト)を連結した値が(無効だけど)トランザクションとしてパースできるような値になるような、2つのトランザクションを生成する。

たとえば、2つのトランザクションTx1とTx2を持つブロックを考える。この場合のマークルルートは、以下のようになる。

graph BT;
    A[Tx1] --DSHA256--> B["H(Tx1)"]
    C[Tx2] --DSHA256--> D["H(Tx2)"]
    B --> E["Root Hash<br>DSHA256(H(Tx1) || H(Tx2))"]
    D --> E

ここで、H(Tx1) || H(Tx2))の値がトランザクションとしてパース可能なデータである場合(Tx3 = H(Tx1) || H(Tx2)))、Tx3のみを含むブロックのマークルルートは、

graph BT;
    A[Tx3] --DSHA256--> B["Root Hash"]

となり、この2つのマークルルートの値は一致し、無効な変異ブロックを作成することができる。

Tx3はTx1とTx2のハッシュの連結値で構成されるため、64バイトのトランザクション。このようなトランザクションを作成する方法については、以下のペーパーで解説されてる↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190225/a27d8837/attachment-0001.pdf

Bitcoinトランザクションは、

フィールド サイズ
version 4 byte
インプットのリスト 可変長
アウトプットのリスト 可変長
locktime 4 byte

で構成されている。インプットとアウトプットのリストの先頭には、その個数がCompactSizeエンコードされている。各インプットは、

フィールド サイズ
OutPoint 36 byte
scriptSig 可変長
sequence 4 byte

各アウトプットは、

フィールド サイズ
value 8 byte
scriptPubkey 可変長

という構成になる。scriptSigとscriptPubkeyは、その先頭にCompactSizeエンコードされたそれぞれのサイズが付与される。

64バイトのパース可能なトランザクションになるためには、

  • インプットとアウトプットの数は1つだけ。つまり、それぞれのリストのサイズは1 byteの0x01でエンコードされなければならない。
  • scriptSigとscriptPubkeyの合計サイズが4 byteでなければならない。

という制約がある。scirptSigが空でscriptPubkeyを4 byteとした場合、トランザクションのデータは以下のように制約される(xは任意の値でOK)↓

xxxxxxxx01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx00xxxxxxxx01xxxxxxxxxxxxxxxx04xxxxxxxxxxxxxxxx

Tx1のハッシュが上記の前半32 byte中1 byte衝突し、Tx2のハッシュが後半32 byte中3 byteと衝突するような2つのトランザクションを用意できればいい。このような衝突は、少ない計算量の総当りで見つけることができる。

一方、無効ではない有効なトランザクションを見つけるのは、制約されるデータ長が増加するため計算上実行不可能な作業になる。

CVE-2012-2459

上記のような無効な変異ブロックは当然ながらコンセンサスルールに合致しないのでリジェクトされる。ただ、昔のBitcoin Coreの実装では、このリジェクトしたブロックのハンドリング方法に問題があった(2012年に開示されたCVE-2012-2459)。

新しく生成されたブロックについて、攻撃者が上記のような変異ブロックを生成し、変異ブロックの方を先に受信したノードは、そのブロックを無効なブロックとしてマーキングする。そのノードはそのブロックハッシュを無効なものとしてマーキングしているため、その後再起動するまで、同じブロックハッシュを持つ有効なブロックを再度受け入れなくなり、最長チェーンから分離されてしまう。つまり、エクリプス攻撃の一種が実行されてしまう。

この脆弱性は、変異ブロックについてはそれを拒否しても無効なブロックハッシュとしてキャッシュしないようにすることで修正された。

ただその後、2017年にBitcoin Core v0.13.0に加えられた最適化により、このキャッシュの問題が再度発生し、v0.14.0で修正されるということもあった。

検証ロジック

今回のPR#29412では、BLOCKメッセージでブロックを受信した際、そのブロックを処理する前に、それが変異ブロックかどうかを先に検証するロジックを追加している。

具体的には、validatoin.cppにブロックが変異ブロックかどうかを検証するIsBlockMutated関数が追加され、新しく受信したブロックを処理する前に変異ブロックかどうかチェックし、変異ブロックだった場合はそれを送信したピアのスコアを下げ、その後の処理を行わない。

IsBlockMutated関数は、ブロックに対して以下の検証が行う。

  • ブロック内のトランザクションリストからマークルルートを計算し、ブロックヘッダーのマークルルートと一致するか検証
  • 上記マークルルートの計算中に、ツリー内の兄弟ノードのハッシュ値が同じ値のものがないかチェック(作成方法1のチェック)
  • ブロック内の先頭のトランザクション(コインベーストランザクション)のprevoutが空かチェックする。
    • 空でない場合、ブロック内のトランザクションでサイズが64バイトのものがないかチェックする(作成方法3のチェック)
  • コインベーストランザクションのインプットのwitnessを検証。要素数は1つのみで、そのサイズは32バイトでなければならない。
  • ブロック内のトランザクションのリストからwitnessマークルルートを計算し、コインベーストランザクションのアウトプット内にあるwitness commitmentと一致するか検証(作成方法2のチェック)
  • Segwitアクティベート前のブロックのトランザクションについて、witnessデータが含まれていないこと。

Ristretto Group

最近、よく見かけるRistrettoについて調べてみた↓

https://ristretto.group/

Ristrettoが解決すること

Ristrettoは、楕円曲線の内、曲線上の有効な点の総数(位数)が素数ではない楕円曲線から、位数が素数となる群を構築する抽象化レイヤーを提供するための手法。

位数が素数だと何が嬉しいのか?

  • 楕円曲線暗号の安全性は、楕円曲線上の離散対数問題(ECDLP)の困難さに基づいており、この難易度は曲線の計算に使用する群の位数が素数である場合に最大になる。
  • 単位元を除く群内のすべての点が生成元になり得る。
  • 群の演算(点の加算や、スカラー乗算)が比較的単純になる。
  • 安全な楕円曲線のパラメーターを選択するのが比較的単純になる。
  • 部分群(サブグループ)が存在しないので、t小さな部分群を利用した攻撃を回避できる。

最後の部分群を利用した攻撃について、暗号通貨で有名なのはMoneroに存在した脆弱性(実際に悪用されてはいない)↓

techmedia-think.hatenablog.com

といったことから、素数位数を持つ楕円曲線が多くの暗号プロトコルなどで推奨されている。Bitcoinで使用されている楕円曲線secp256k1も、位数は素数

素数位数でない曲線

一方で最近の楕円曲線の実装では、位数が素数ではないことが多い(MoneroのCurve25519もそう)。なぜ位数が素数ではない曲線を使うのか?というと、演算がとても高速に行えるから。

これらの楕円曲線の位数Nは、素数位数の部分群の位数を {l}とした場合、 {N = h \cdot l}となる。hは余因子(cofactor)と呼ばれる値で、部分群と曲線全体の群の比率を表す値。 {l}が巨大な素数であるのに対して、hは通常1とか4とか8とか小さな値になる。secp256k1など素数位数の曲線の場合、h = 1となる(つまり曲線の群=部分群)。

このような曲線上で暗号学的な演算を行う場合、それらの演算は基本的に素数位数 {l}の部分群において行われる必要がある。通常、群内の点に対する演算(スカラー乗算や、点の加算など)は、その結果得られる点も同じ群内に留まる(つまり群の演算は閉じている)。ただ、外部から不正な入力が与えられるような場合(例えば他のユーザーの公開鍵とか署名など)、与えられた点が期待する部分群内に属さない点であることがあり得る。

たとえば、↑のMoneroの件では、素数位数の部分群に属さない点をキーイメージとして提供することで不正を行う。この件ではキーイメージが素数位数の部分群内の点か検証する追加チェックを導入して対応しているけど、どのプロトコルでも単に位数lの乗算チェックを適用すればいい(適用できる)とは限らず、複雑なプロトコルの場合に元の安全性の証明が適用されなくなってしまう可能性もある。

上位プロトコルにおいて、このような脆弱性が発生しないように適切に余因子を処理していくのは、難易度の高いものになる。そこで、高速な演算の恩恵を受けつつ、余因子による煩雑さを考慮しなくても済むようにしようというのがRistrettoの目的。

Ristretto

RistrettoはMike HamburgのDecafという提案がベースになっている。Decafは、余因子 = 4のエドワーズ曲線とモンゴメリ曲線について、曲線上の点を特定の方法でエンコード/デコードすることで余因子の影響を受けない安全な素数位数の部分群を提供する。そしてDecafをベースとして余因子が8の曲線(Curve25519とか)をサポートしたのがRistretto。

Ristrettoが提供する機能は↓

  • 元の曲線の点を含む素数位数群の提供:
    これは、元の楕円曲線上の点に対して同じ暗号学的情報を持つ点を等価性クラスとして分類し、各等価性クラス内の1つの点を代表点として選択し、その代表点を使って素数位数の群を形成する。構成される素数位数群の位数は、元の曲線の素数位数の部分群の位数と一致する。
  • 点の等価性チェック:
    Ristrettoでは点の情報は内部的に元の曲線の点を使用している。この等価性チェックでは、内部表現の異なる2つの点の等価性をチェックする(内部表現が違っても同じ等価性クラスに分類されていれば等価とみなされる)。
  • エンコード関数:
    内部表現が等価な点についてはすべて同じビット列としてエンコードするエンコード関数
  • デコード関数:
    有効な点の正規のエンコードのみが受け入れられるよう、検証処理が組み込まれたデコード関数
  • Hash to Point演算に適したビット文字列からRistrettoの点へのマッピング

点の演算に関しては、内部表現を利用して高速な既存の曲線の計算をそのまま利用する。

既存の曲線の実装に対して、新しい型と上記関数を追加する薄い抽象化レイヤーによって必要な抽象化を利用者に提供している。

↑の関数の具体的な群の演算については、RFC9496に記載されているristretto255(Curve25519)とdecaf448(edwards448)の疑似コードが参考になる↓

RFC 9496: The ristretto255 and decaf448 Groups

また、エンコード/デコードについては、最初のサイトにそれぞれアフィン座標で行う方法と拡張座標で行う方法の説明がある↓

等価性の検証方法は↓

Hash to Pointの演算は、それぞれアフィン座標と拡張座標用に↓

この曲線上の点へのハッシュは、以前書いたHash to Curveなんかでも使用されているElligator 2を使ってまず要素をヤコビ四次曲線*1マッピングして、同種写像を使ってエドワーズ/モンゴメリ曲線の点にマッピングするらしい。だから同種写像を用いた変換の説明がサイトの最初にあったのか。

間にこの曲線を挟むのは、直接マッピングするより特定の攻撃ベクトル(サイドチャネル攻撃や、点の判別攻撃、特定の数学的構造を利用した攻撃など)に対する耐性が上がりより安全性が高まるためとか。また、同種写像による変換も計算効率が良いので、コストも高くないそうな。

*1:方程式y2 = x4 + ax2 + bで定義される曲線。

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を共有するようなプロトコルでも、活用できるかも?