BitVM: Compute Anything on Bitcoin

# はじめに（Introduction）

最近、私の周りで流行りだした？、以下のBitVM論文を[Google翻訳](https://translate.google.co.jp/)などで翻訳してみます。

https://bitvm.org/bitvm.pdf

# BitVM: Compute Anything on Bitcoin

Robin Linus
robin@zerosync.org
October 9, 2023

## 要旨（Abstract）

BitVM は、チューリング完全なビットコイン コントラクトを表現するためのコンピューティング パラダイムです。
これには、ネットワークのコンセンサス ルールを変更する必要はありません。
ビットコインで計算を実行するのではなく、楽観的ロールアップと同様に、単に検証されるだけです。
証明者は、特定の関数が特定の出力に対する特定の入力を評価すると主張します。
その主張が偽りであれば、検証者は簡潔な不正証明を実行して証明者を罰することができます。
このメカニズムを使用すると、あらゆる計算可能な関数をビットコイン上で検証できます。
Taproot アドレスで大規模なプログラムにコミットするには、大量のオフチェーンの計算と通信が必要ですが、結果として生じるオンチェーンのフットプリントは最小限に抑えられます。
両者が協力している限り、チェーンに痕跡を残さずに、任意の複雑でステートフルなオフチェーン計算を実行できます。
オンチェーンでの実行は紛争が発生した場合にのみ必要です。

## 1 序論（Introduction）

設計上、ビットコインのスマート コントラクト機能は、署名、タイムロック、ハッシュロックなどの基本的な操作に限定されています。
BitVM は、より表現力豊かなビットコイン コントラクトとオフチェーン計算のための新しい設計空間を作成します。
潜在的な用途には、チェス、囲碁、ポーカーなどのゲーム、特にビットコイン契約の有効性証明の検証が含まれます。
さらに、BTC を外部のチェーンに橋渡ししたり、予測市場を構築したり、新しいオペコードをエミュレートしたりできる可能性があります。
ここで提案されたモデルの主な欠点は、証明者と検証者の 2 者間設定に限定されていることです。
もう 1 つの制限は、証明者と検証者の両方にとって、プログラムを実行するために大量のオフチェーンの計算と通信が必要になることです。
ただし、これらの問題はさらなる研究によって解決される可能性があります。
この作業では、ツーパーティ BitVM の主要コンポーネントのみに焦点を当てます。

## 2 アーキテクチャ（Architecture）

Optimistic Rollups[1] や MATT 提案 (Merkelize All The Things)[2] と同様に、このシステムは不正行為の証明とチャレンジ/レスポンス プロトコルに基づいています。
ただし、BitVM ではビットコインのコンセンサス ルールを変更する必要はありません。
基礎となるプリミティブは比較的単純です。 これは主にハッシュロック、タイムロック、および大きな Taproot ツリーに基づいています。
証明者は文字通り少しずつプログラムにコミットしますが、そのすべてをオンチェーンで検証すると計算コストが高すぎるため、検証者は慎重に作成された一連のチャレンジを実行して、証明者の誤った主張を簡潔に反証します。
証明者と検証者は共同で一連のチャレンジアンドレスポンストランザクションに事前署名し、後でそれを使用して紛争を解決できます。
このモデルは、このアプローチによりビットコインの普遍的な計算が可能になることを単純に示すために設計されています。
実際のアプリケーションでは、より効率的なモデルを検討する必要があります。

プロトコルは単純です。まず、証明者と検証者がプログラムを巨大なバイナリ回路にコンパイルします。
証明者は、回路内のすべての論理ゲートのリーフ スクリプトを持つタップルート アドレスでその回路にコミットします。
さらに、一連のトランザクションに事前署名し、証明者と検証者の間でチャレンジとレスポンスのゲームを可能にします。
これで、必要なデータがすべて交換されたので、結果として得られた Taproot アドレスにオンチェーン デポジットを行うことができます。
これによりコントラクトが有効になり、オフチェーン データの交換を開始して回線内の状態変更をトリガーできるようになります。
証明者が誤った主張をした場合、検証者は保証金を受け取ることができます。
これにより、攻撃者は常にデポジットを失うことが保証されます。

## 3 ビット値のコミットメント（Bit Value Commitment）

ビット値のコミットメントは、システムの最も基本的なコンポーネントです。
これにより、証明者は特定のビットの値を「0」または「1」に設定できます。
特に、証明者はさまざまなスクリプトや UTXO にわたって変数の値を設定できます。
これは、ビットコインの VM を複数のトランザクションに分割することで実行ランタイムを延長するため、重要です。

コミットメントには 2 つのハッシュ、hash0 と hash1 が含まれています。
後の時点で、証明者は、hash0 のプリイメージである preimage0 を公開することでビットの値を「0」に設定するか、hash1 のプリイメージである preimage1 を公開することによってビットの値を「1」に設定します。
ある時点で、プリイメージ preimage0 と preimage1 の両方が明らかになった場合、検証者はそれらを不正の証拠として使用し、証明者の保証金を受け取ることができます。
それを曖昧といいます。
あいまいな発言を罰することができるということは、コミットメントに拘束力を与えるものであり、それは「インセンティブに基づくコミットメント」です。

ビット値のコミットメントとタイムロックを組み合わせると、検証者は証明者に特定の時間枠内で特定のビットの値を強制的に決定させることができます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/cae56cf6-04bb-e897-8fd8-bc489c4501d1.png)

図 1: 1 ビット コミットメントの具体的な実装。
このスクリプトのロックを解除するには、証明者は hash0 または hash1 のプリイメージを明らかにする必要があります。
この実行例では、証明者は hash1 を明らかにし、ビットの値を「1」に設定します。
このコミットメントのコピーを保持して、さまざまなスクリプト間で特定の値を強制できます。

わかりやすくするために、ここからは、上記のスクリプトの短縮形であるオペコード OP_BITCOMMITMENT があると仮定します。
オペコードは 2 つのハッシュと、そのうちの 1 つのハッシュのプリイメージを消費します。
どのハッシュがプリイメージと一致するかに応じて、ビット値をスタックに置きます。

## 4 ロジックゲートのコミットメント（Logic Gate Commitment）

計算可能な関数はすべてブール回路として表現できます。
NAND ゲートは汎用論理ゲートであるため、任意のブール関数を NAND ゲートから構成できます。
モデルを単純にするために、この方法が単純な NAND ゲートに対して機能することを示します。
さらに、ゲートを任意に構成する方法も示します。
これは、BitVM があらゆる回路を表現できることを示しています。
NAND ゲート コミットメントの実装は簡単です。
これには、2 つの入力を表す 2 ビットのコミットメントと、出力を表す 3 番目のビットのコミットメントが含まれています。
スクリプトは 2 つの入力の NAND 値を計算し、コミットされた出力ビットと一致することを確認します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/858c4c37-4c94-8859-3610-5c59d2ba830f.png)

図 2: NAND 操作の論理ゲートのコミットメント。 このスクリプトを実行するには、A NAND B = C が成り立つような、ビット コミットメント A、B、および C の値を明らかにする必要があります。

(ここでは、簡単にするために、OP_NAND のオペコードが存在すると仮定します。実際には存在しませんが、OP_BOOLAND と OP_NOT を使用して簡単に実装できます。)

## 5 バイナリ回路のコミットメント（Binary Circuit Commitment）

前のセクションでは、NAND ゲートのコミットメントを定義しました。
ゲートコミットメントを構成することで任意の回路を表現できます。
実行のすべてのステップは Tapleaf でコミットされます。
それらはすべて同じタップルート アドレスに結合され、証明者が回路内の任意のゲートを実行できるようになります。
ゲートを実行するには、証明者が対応するゲート コミットメントを開き、その入力ビットと出力ビットの値を設定する必要があります。
Taptree は巨大になり、10 億の Tapleaf スクリプトが存在する可能性がありますが、そのオンチェーン上のフットプリントは最小限です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/ec1786f5-21f7-f949-4e56-fa97d70a6062.png)

図 3: 8 つの異なる NAND ゲートと 4 つの入力 A、B、C、D を持つランダムな回路例。
数十億のゲートを使用すると、基本的にあらゆる関数を定義できるようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/853c3deb-f678-7fbc-d29c-7ced7ae8f531.png)

図 4: 各ゲートについて、証明者のタップルート アドレスには、対応するゲート コミットメントを含むリーフ スクリプトが含まれています。
これにより、証明者は後の任意の時点で回路の入力値 (ここでは A、B、C、D) を設定できるようになります。

## 6 チャレンジとレスポンス（Challenges and Responses）

回路にコミットするだけでは十分ではありません。
不正確な主張を反証するには、検証者は証明者の発言に異議を唱えることができなければなりません。
これは、セットアップ中に一連のトランザクションに事前署名することによって可能になります。
トランザクションは、チャレンジ → レスポンス → チャレンジ → レスポンス → ... のようにリンクされます。
どちらかの当事者が関与をやめた場合、一定のタイムアウトの後、もう一方の当事者がチャレンジに勝ち、両方のデポジットを受け取ることができます。
両当事者が協力的である限り、 2-of-2 の署名で任意の契約を共同で解決できます。
次のメカニズムは、詐欺の場合にのみ必要です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/dcff1093-0ba1-1a81-062d-162c76d7cac1.png)

図 5: 複数ラウンドのチャレンジ アンド レスポンスを実行するための、事前に署名されたトランザクションのシーケンス。
このシーケンスはセットアップ中に生成されます。
Vicky は、Tapscript リーフにあるハッシュロックの 1 つを開いてチャレンジを選択します。
これにより、Paul は特定の Tapscript のロックを解除され、それを強制的に実行されます。
脚本はポールに、ヴィッキーが異議を申し立てたゲートの約束を明らかにするよう強制する。
この手順を数ラウンドのクエリで繰り返すことで、矛盾した主張はすぐに反証できます。

証明者がオフチェーンでの検証者との共同作業を停止した場合、検証者は自分の手を強制的にオンチェーンに戻す方法が必要になります。
検証者は、ハッシュロックのロックを解除することでこれを行います。証明者の UTXO 内の各 NAND タップリーブは、検証者が保持するプリイメージを証明者が知っている場合にのみ使用できます。
したがって、証明者は、その入力と出力を明らかにすることによって、特定の Tapleaf が正しく実行されることを証明できますが、それは検証者がその Tapleaf を保護するハッシュのプリイメージを明らかにすることによってその Tapleaf を「ロック解除（unlocks）」した場合に限ります。
二分探索を適用すると、検証者はわずか数ラウンドのチャレンジアンドレスポンスの後、証明者の誤りを迅速に特定できます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/b699aad5-9360-1a1e-2a07-e25b9184128e.png)

図 6: 各レスポンスの後、Vicky は曖昧さを罰することができます。
Paul が変数の 2 つの矛盾する値を明らかにした場合、Vicky は即座にチャレンジに勝ち、デポジットを受け取ることが許可されます。
Vicky は、Paul のちょっとした約束について、両方のプリイメージを明らかにすることで、Paul の曖昧さを証明します。

## 7 入力と出力（Inputs and Outputs）

証明者は、対応するビットコミットメントを明らかにすることで入力を設定できます。
理想的には、オフチェーンでのコミットメントを明らかにして、オンチェーンのフットプリントを最小限に抑えます。
非協力的なケースでは、検証者は証明者にオンチェーンでの入力を明らかにするよう強制できます。
大量のデータを事前に交換することで処理できますが、暗号化されます。
このようにして、証明者は後の時点で復号キーを明らかにできます。
マルチパーティ入力も可能です。 ゲートには、双方からのビットコミットメントを含めることができます。

## 8 制限と見通し（Limitations and Outlook）

単純な NAND 回路で機能を表現するのは非効率です。
より高レベルのオペコードを使用すると、プログラムをより効率的に表現できます。 たとえば、ビットコイン スクリプトは 32 ビット数値の追加をサポートしているため、そのためのバイナリ回路は必要ありません。
また、より大きなビットコミットメントを持つこともできます。 単一のハッシュで 32 ビットにコミットすることが可能です。
さらに、スクリプトのサイズは最大約 4 MB になることがあります。
したがって、リーフ スクリプトごとに実質的に 1 つ以上の NAND 命令を実装できます。

ここで提案されているモデルは 2 つの当事者に限定されています。
ただし、双方向チャネルを用意し、それらをチェーンして Lightning のようなネットワークを形成することは可能かもしれません。
二者関係の設定を調査すると、一般化のための興味深い可能性が得られるかもしれません。
たとえば、ネットワークの 1 対 n のスター トポロジを調査できます。
もう 1 つの研究課題は、モデルを n-of-n 設定に適用して、より洗練されたチャネル ファクトリを作成できるかどうかです。
さらに、システムをライトニングネットワークやロールアップなどのさまざまなオフチェーンプロトコルと組み合わせることができます。
他の研究方向には、クロスアプリケーション メモリ、チェーンに組み込まれた任意のデータに関するステートメントの作成方法、またはオフチェーン プログラマブル回路、つまりオフチェーン VM が含まれます。
また、STARK と同様の、より洗練されたサンプリング技術を適用して、1 回のラウンドで回路をチェックすることも可能かもしれません。
次の主要なマイルストーンは、具体的な BitVM と、ビットコイン コントラクトを作成およびデバッグするための高級言語である Tree++ の設計と実装を完了することです。

## 9 まとめ（Conclusion）

ビットコインは、不正行為の証拠を大規模な Taptree にエンコードすることで、あらゆるプログラムの実行を検証できるという意味でチューリング完全です。
ここで概説したモデルの主な制約は、それが 2 者間設定に限定されていることです。
うまくいけば、これは今後の作品で一般化できるでしょう。

## 謝辞（Acknowledgments）

Super Testnet と、ビットコインがチューリング完全ではないということを常に信じようとしなかった Sam Parker に特に感謝します。

## 参照（References）

[1] Ethereum Research. Optimistic rollups. https://ethereum.org/en/developers/docs/scaling/optimistic-rollups/, 2022.

[2] Salvatore Ingala. Merkleize all the things. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html, 2022.

Sponsor BitVM developers: bc1qf5g6z0py2t3t49gupeqrlewga0qz2etalu4xf9

# まとめ（Conclusion）

本論文に加え、[@techmedia_think](https://twitter.com/techmedia_think)の記事と[@1_LOW_0219](https://twitter.com/1_LOW_0219)のXを参照したことで、仕組みはなんとなくだが理解できました。

一点気になることが、これ膨大なデータ量になるはずで、ハッシュ値の算出はなんとかなるかもしれませんが、署名がどのくらいいるのかによっては膨大な時間がかかってしまうのではないかと思いました。

対ロジック比でどれだけ、時間がかかるのかが気になりました。

# 参考（References）

https://techmedia-think.hatenablog.com/entry/2023/10/19/195132

https://twitter.com/1_LOW_0219/status/1717811587430617594