BitVM 2

Bitcoin上で任意のプログラムの検証を可能にするBitVMについて↓

techmedia-think.hatenablog.com

この提案では、チャレンジ＆レスポンスを行えるのはコントラクトに参加する二者に限定されていたけど、これを

マルチパーティ構成に拡張し、
さらに一連のチャレンジ＆レスポンスのトランザクションチェーンを2ラウンドに短縮する

BitVM 2という新たな提案が公開された↓のでざっくり見てみる。

BitVM 2: Permissionless Verification on Bitcoin | BitVM

BitVMでは任意の計算ロジックを回路に変換し、回路の各NANDゲートをそれぞれTapleafにエンコードし、チャレンジ&レスポンスで、そのゲートを１つずつ実行していく構成になっていたが、BitVM 2ではその構成が大きく変わっている。Tapleafのスクリプトを任意の回路の各NANDゲートではなくSNARK検証器となり、単一のゲートに対するチャレンジ＆レスポンスではなくSNARK検証器のサブ関数に対するチャレンジ＆レスポンスになった。

検証器のプログラムをfとし、入力（プルーフ）をx、そして出力をyとした場合、f(x) = yを検証できれば、オペレーターが正しい計算を行っていることをSNARK検証器を使って検証することができる。

ただ、単純にGroth16などの検証器を実装しようとするとスクリプトが20MBくらいになり、（ブロックサイズが最大でも4MBの）現在のBitcoinではブロックに格納できるサイズのトランザクションではなくなる。

そこで、ランポート署名を利用してf(x) = yを複数のステップに分割する*1。ステップの数を42とした場合、

 f1(x)  = z1
 f2(z1) = z2
 f3(z2) = z3
 ...
 f42(z41) = z42
 f43(z42) = y

のように分割する。するとfの計算をブロックをまたいで43個のトランザクションのシーケンスにする。このアプローチであれば、現状のBitcoinのルールでも一応は動作する。ただ、オンチェーンフットプリントは巨大なままだし、複数のトランザクションに渡って状態遷移をするというオーバーヘッドも発生してしまう。つまり、検証器のプログラムをオンチェーンでそのまま実行するというのは好ましくない。

そこで証明者はSNARK検証器の実行をそのままするのではなく、プルーフxと出力yと各中間状態（z1, z2, ..., z42）にコミットする。たとえば↑のf1〜f43の34個のスクリプトをリーフとしたTaptreeを構成する。そして証明者がコミットしたいずれかの中間状態 ${z_i}$ において ${f_i(z_{i-1}) == z_i}$ が満たされない場合は、ペナルティを与えるようにする。こうすると検証者がFraud Proofにより反証する際に必要なのは、いずれかの ${f_i}$ の不正を証明するだけになる。

これが実際にどうブリッジに適用されるのか見ていく。

パーミッションレスブリッジ

BitVM 2の主な用途は、Bitcoinとロールアップやサイドチェーン間でのブリッジで、そのトラストを最小限に抑えるというもの。Liquidなどのサイドチェーンを利用する場合、現状だとチェーン間の資金の移動時にフェデレーションを信頼する必要があるが、BitVMを利用するとこのトラストを1-of-nまで削減できるということらしい。

Peg Inトランザクション

BitVMにコインをデポジットするトランザクションで、ユーザー（アリス）の資金はn-of-nのマルチシグに送金される。ただし、ユーザーがこのトランザクションに署名する前に、Take 1、Take 2、Kick Off、Challenge、Assert、Burnトランザクションが作成され、それぞれのトランザクションについてn-of-nの鍵の所有者とオペレーターが事前署名する。

Kick Offトランザクション

Kick Offトランザクションは、このペグインによるBitVMの状態にコミットする（オペレーターが計算によって生成された出力値yにコミットする）トランザクション。このトランザクションの構成は、

インプット：
- オペレーターの資金が原資でペグインの状態yにコミットする
アウトプット：
- タイムロックされたアウトプット（図では2週間）
- コネクターアウトプットA：検証者がチャレンジする際に使用する
- コネクターアウトプットB：インプットの資金をn-of-nのマルチシグに送金し、オペレーターがチャレンジに対する応答として使用するか、応答しない場合は焼却される。

Take 1トランザクション

オペレーターがKick Offトランザクションでコミットした状態に対して、タイムロック期間を過ぎても誰もチャレンジしない場合、その3つのアウトプットとPeg Inトランザクションの資金をインプットにし、それをすべてオペレーターに預け入れるトランザクション。

もし誰かがチャレンジを行うと、コネクターアウトプットAがChallengeトランザクションで使用されるため、それに伴いTake 1トランザクションは無効になる。

Challengeトランザクション

オペレーターが主張する値yについて、コネクターアウトプットAを使ってチャレンジを行うトリガーとなるトランザクション。Challengeトランザクションは予めオペレーターによって作成されており、その構成は、

インプット：
- Kick OffトランザクションのコネクターアウトプットA
アウトプット：
- オペレーターに支払われる保証金

となっており、SIGHASH_SINGLE|ANYONECANPAYで署名されている（つまり誰でも他のインプットを追加できる状態）。この段階で保証金に足りる金額はコネクターアウトプットAには無いので、チャレンジするユーザーが自分のUTXOをインプットに追加し、保証金を支払えるようトランザクションを完成させる必要がある。つまり検証者がお金を払ってチャレンジする。

Assertトランザクション

Assertトランザクションは、検証者のチャレンジに対するオペレーターによるレスポンス。Challengeトランザクションが承認されるとTake 1トランザクションはもう使えないので、オペレーターはAssertトランザクションでレスポンスする必要がある。タイムロック期間内（図では4週間）にレスポンスしない場合はBurnトランザクションが実行される。

トランザクションの構成は、

インプット：
- Kick OffトランザクションのコネクターアウトプットB：オペレーターが中間状態（ ${x, z_1, ..., z_{42}}$ ）にコミットする。
アウトプット：
- タイムロックされた（図では2週間）オペレーター宛のアウトプット*2
- コネクターアウトプットC：検証者によって不正が証明されるか、証明されずにオペレーターが入手する際に使用される。

Take 2トランザクション

検証者がAssertトランザクションのオペレーターのレスポンスに不正を証明しない場合は、タイムロック後にPeg Inトランザクションの資金とAssertトランザクションのアウトプットをインプットにし、それをすべてオペレーターに預け入れるトランザクション。つまり、チャレンジ＆レスポンスを経由して、ペグインされる場合に使用されるトランザクション。

Disproveトランザクション

Assertトランザクションでコミットされた中間状態のいずれか（ ${z_i}$ ）の誤りを検証者が指摘できた場合に、検証者がコネクターアウトプットBの資金を没収するトランザクション。

Burnトランザクション

Challengeトランザクションによりチャレンジがトリガーされたにも関わらず、オペレーターが何も応答しない場合、コネクターアウトプットBの資金を焼却するトランザクション *3。

1-of-nトラスト

最後に制限としても挙げられているけど、これをワークさせるにはn人の内少なくとも１人は正直に動作するオペレーターが必要になる。

ただ、以下の疑問が残る。

n人の内１人でも悪意あるメンバーがいると、Assertトランザクションで偽の中間状態にコミットできてしまうのでは？その場合、失われるのはオペレーターの資金になって自分を攻撃するようなものかもしれないけど、自分がVerifierになってしまえばDisproveトランザクションでその資金を手に入れられるのでは？
Disprove / Burnになった場合、ペグインの資金はn-of-nにロックされたままになってしまうので、Peg Inトランザクションのアウトプットにはタイムロック条件が必要なのでは？