ZeroSyncのRobin Linusが、先日、Bitcoinで（現状opcodeとして存在しないような計算を含む）任意のロジックのコントラクトを表現できるようにする提案BitVMを発表した↓
BitVMの仕組み
世の中にはたくさんのプログラムが存在するけど、これらのプログラムは、
つまり、あらゆる計算は何らかの回路の形で表現できる。
最近のゼロ知識証明プロトコルとかでも、プログラムを算術回路に変換し、その計算に含まれる値が回路を満たしていることを証明することで、実際にプログラムを実行することなく、その実行が正しいことを証明するアプローチが増えてる。
任意の計算を回路にコンパイル
BitVMも同様に、任意の計算をBitcoinのオンチェーンで実行するのではなく、任意の計算の結果が正しいことを検証できるようにしようというもの。証明者は任意のプログラムに対して、入力を与え評価した結果の出力を提示し、その結果に誤りがある場合、検証者はFraud Proofを提供することで、証明者にペナルティを与えることができるようになる。これにより任意の計算の検証をBitcoin上で検証できるようになる。それも、現在のBitcoinのコンセンサスルールに変更を加えることなく。
まず、最初に、プログラムを巨大なBinary Circuit（2進回路）にコンパイルする。この回路は多数の論理ゲートで構成される。論理ゲートは、
- 入力としてビット（0 or 1）を受け取り
- 受け取ったデータを使って操作を実行し、
- 新しいビット（0 or 1）を出力する
もの。論理ゲートには、ANDゲート、ORゲート、XORゲート、NOTゲートなどいろいろ種類があるけれど、BitVMで提案されているのはNANDゲート。NANDゲートは、2つのビットを入力として、両方1の場合のみ0を出力し、それ以外の場合はすべて1を出力するゲート（出力がANDの反対の結果になるNOT AND = NAND）↓
| 入力A | 入力B | 出力 |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
NANDゲートには、NANDゲートを複数組み合わせると、他の論理ゲートを構築できるという特徴がある。
Bitcoin Scriptを使ったNANDゲート
BitVMではこのNANDゲートを使った回路を作成することになる。Bitcoin ScriptでこのNANDゲートの機能を作る場合、以下の2つのopcodeを使って実現できる。
OP_BOOLAND：スタックから2つの要素を取得し、両方とも非0であれば1を、それ以外の場合は0をスタックにプッシュする。OP_NOT：スタックから１つ要素を取得し、要素が0か1の場合、それを反転してスタックにプッシュする（0、1以外の場合は0がプッシュされる）。
OP_BOOLANDはANDゲートと同じ機能なので、この2つをセットで使えばNANDゲートの機能になる。
Bit Value Commitment
続いて、このNANDゲートに対するコミットメントを作成する。2つのビット（0 or 1）を入力として与えた場合、NANDゲートとして1つのbitが出力されることにコミットする。
まず、特定のビットの値を0 or 1に設定するのにハッシュロックを利用する。具体的には、2つのハッシュ値hash0とhash1を用意して、以下のようなスクリプトを構成する。
OP_IF OP_HASH160 <hash1> OP_EUALVERIFY <1> OP_ELSE OP_HASH160 <hash0> OP_EUALVERIFY <0> OP_ENDIF
hash1のプリイメージを提供すればスタックには1がプッシュされ、hash0のプリイメージを提供すればスタックに0がプッシュされるというスクリプト。ペーパーではこの仕組みをBit Value Commitmentと呼んでいる。
このBit Value Commitmentを2つ用意すれば１つのNANDゲートへの入力になる。
実際に入力A、BについてA NAND B = Cであることを検証するNANDゲート機能のコミットメントは、以下のスクリプトで実装できる。表記を簡単にするために↑のBit Value Commitmentの機能を実行するopcodeをOP_BITCOMMITMENTとする。
# 出力Cの提供 <Cのhash0 or hash1のプリイメージ> <hash1の場合はOP_TRUE、hash2の場合はOP_FALSE> OP_BITCOMMITMENT OP_TOALTSTACK # 出力値をアルトスタックに移動 # 入力Bの提供 <Bのhash0 or hash1のプリイメージ> <hash1の場合はOP_TRUE、hash2の場合はOP_FALSE> OP_BITCOMMITMENT OP_TOALTSTACK # 入力値となる結果をアルトスタックに移動 # 入力Aの提供 <Aのhash0 or hash1のプリイメージ> <hash1の場合はOP_TRUE、hash2の場合はOP_FALSE> OP_BITCOMMITMENT # 入力Bの値をメインスタックに移動 OP_FROMALTSTACK OP_BOOLAND OP_NOT # A NAND Bの結果がスタックにプッシュされる # アルトスタックからCを読み込み OP_FROMALTSTACK # A NAND B = Cかどうかチェックする OP_EQUALVERIFY
これをLogic Gate Commitmentと呼んでる。実際は、C、A、Bのハッシュのデータについてはwitnessとして提供されるようになると思われる。
Binary Circuit Commitment
論理ゲートのコミットメントが実装できたら、それらを組み合わせることで任意の回路を表現することができる。たとえば、ペーパーに挙がってる4つの入力（A, B, C, D）と8つのNANDゲートを持つ小さな回路みたいな↓
ただ、実際に任意の計算をしようとすると、数十億個のゲートからなる巨大な回路を作る必要がある。なので、オフチェーンで交換、保持するデータはかなり大きくなる。
回路を構成すると、回路内の各ゲートのGate Commitmentをリーフノードとして配置するTaptreeを構成する↓
つまり、回路内の各実行ステップはTapleafにコミットされる。
証明者が各ゲートの入力と出力（いずれもハッシュロックをアンロック可能なプリイメージ）を提供すれば、Taptree内の任意のゲートを実行することができる。
チャレンジ＆レスポンス
↑で任意の計算を論理回路としてコミットするところまでは出来たので、続いてコントラクトの決済について。
証明者がオフチェーンで正しく計算を行えば、証明者はその対価として報酬が得られる。一方、計算が最後まで行われなかったり、誤った結果が提供された場合は、証明者にペナルティ（デポジットした資金の没収）を課すなど調停の仕組みが必要になる。BitVMでは、検証者が証明者に対して特定のゲートの実行の要求（チャレンジ）を行い、証明者がそれを実行して回答するチャレンジ＆レスポンスの仕組みを採用している。
これは、以下のような事前署名済みのトランザクションチェーンをセットアップ時に構築することで実現する。
↑のTx1を見てみよう。証明者が正しく協力するなど検証者がチャレンジしない場合Tx1の一番下のアンロック条件（一週間後のタイムロック）で証明者は報酬を得ることができる。他の2つのアンロック条件は、
- 検証者によるチャレンジ：検証者は↑のようにチャレンジ用のTaptreeを持っており、このツリーはハッシュロックのリーフで構成される。このツリーの各リーフのハッシュは、回路の各Gate Commitmentと対応している（Bit commitmentのハッシュのプリイメージとはまた別で、検証者のみがそのプリイメージを知っている）。検証者は、このツリーの中から任意のハッシュをアンロック（対応するプリイメージを公開）して、証明者にチャレンジを要求する。このチャレンジは、アンロックしたハッシュが対応するNANDゲートを実行せよというもの。↑の図では
hash7をアンロック。 - 検証者がFraud Proofを提供し、即座に資金を没収する（後述）。
続くTx2のアウトプットをアンロックする条件は以下の2つ
- 証明者が検証者のチャレンジに対して、対応するプリイメージとNANDゲートを使って、NANDゲートのコミットメントをアンロックする。つまり対象のNANDゲートを実行する（↑の図では
NAND7を実行）。そしてこの場合、最初のTx1の条件と同様の条件のアウトプットに資金は移動することになる。 - タイムロック（一週間）経過したら、検証者が入手可能。これは、証明者がチャレンジに対応しなくなった場合の処理。
証明者がレスポンスを返すということは、実行したゲートの入力2つと出力1つの各値（ビット）に対応するハッシュ値のプリイメージを公開することになる。各ビットのBit commitmentには、hash0とhash1がそれぞれ存在するが、基本的にゲートを実行する際に証明者によって公開されるプリイメージは、hash0かhash1かどちらか一方に対応する値になる。不正をしようとして正しい計算とは逆のビットを公開した場合、チャレンジ＆レスポンスを繰り返す過程で、本来どちらか一方しか公開されないはずのものが両方とも公開されてしまうような事態が発生する。
そこで、以下のようにすべてのNANDゲートに対して、入力値のプリイメージが両方揃った場合に、その両方のハッシュロックが解ければ検証者がデポジットした資金をすべて獲得できるようなTaptreeを形成する。
これが、Fraud Proofによって資金を回収するアンロック条件になる。
検証者は、上記のようなチャレンジ＆レスポンスを数ラウンド繰り返すことで、証明者の不正を検知することができるという仕組みみたい。
現状の制限
発表と同時に結構盛り上がっているけど、BitVMはまだ初期提案の段階で、以下のようの制限がある。
2者間のコントラクトに限定
現状のプロトコルは、2者間のコントラクトに限定されているので、多数の参加者が参加可能なプロトコルにはなっておらず、3者以上のマルチパーティプロトコルとして機能させるためにはプロトコルの改善が必要。
また、必ずしも計算が正しく行われたことを保証するものではない。証明者がレスポンスに反応しない場合、資金は没収されるのであって、証明者によって計算自体が正しく行われることは保証されない。またすべての実行をチャレンジするというのもトランザクション数的に現実的ではない。
高級言語はまだない
早速、BitVMのアプローチを実証するPoCも公開されてる↓
https://github.com/supertestnet/tapleaf-circuits
けど、実際に構築しようとすると任意の計算を回路に変換し、回路の各実行ステップをGate CommitmentとしてTapleafに配置したTaptreeを構成する必要がある。現状高級言語はないので、これらをスクラッチで作る必要があり、コンパイラが出来るまでは構築のハードルが高い。
BitVMの次の大きなマイルストーンとして、コントラクトの記述とデバッグのための高級言語Tree++を完成させるみたいなことが書かれてあったので、容易に書けるようになるのはもう少し先っぽい。
データ量、計算量
任意の計算を実行しようとすると、そのゲートの数は膨大（数百MB〜数GB）になると思われる。（DLCで保持するデータとか、とても少なく思えてしまう）
