BitVMの解説
BitVMとは?
BitVMはRobin Linusにより提案されたチューリング完全なビットコイン契約を実現するコンピューティング・パラダイムです。
Bitcoinはスクリプト言語をチューリング不完全にしており、VMベースのチェーンで実装されているような任意のチューリング完全なコントラクトを実装するのが難しいとされていました。
過去にもチューリング完全なコントラクトをBitcoin上で実現する提案は、Bitcoinに新たなオペコードをアクティベートする（つまりソフトフォークする）必要がありましたがBitVMはソフトフォークを必要としない点が今までの提案と異なる点です。
ただし、現状VMベースのチェーンで実装されている様々な契約をすぐにBitcoin上で実現するような特効薬（a silver bullet solution）ではないことは強調されています。理由としては以下の通りです。
・契約は2-party間に限られる
・２partyには多くの計算量およびインタラクションを要する（1つの契約を実行するにあたりお互いが交換および保持する情報は数百MB〜数GBになる）
このような制約はあるものの、ソフトフォークが不要な提案として開発者の注目を集めています。
以降は、とある任意の式を満たす解を知っていると主張するProverと、その主張の真偽について検証するVerifier間で資金をお互いに供託し、その資金の取り分についての契約をする方法について記述します。
両者が協力的である限りにおいては、どんな契約内容でも実行可能ですが、Proverの主張が正しくないとVerifierが判断した場合には「Challenge and Response」（のちに詳しく触れます）が開始され、主張が正しくないことが判明した場合はVerifierがProverの資金を没収するような仕組みです。
まずはそのBitVMの仕組みを理解する上での予備知識について解説します。
予備知識
⚫論理回路(Logic Circuits)
プログラミング言語で記述されたコードはコンパイラやインタープリンタなどを使用してバイナリコード（0と1の羅列）に変換されます。バイナリコードはプロセッサによって解読され論理回路を使用して命令が実行されます。論理回路の代表例としてはANDゲート、ORゲート、NOTゲート、NANDゲートなどがあります。
中でもNANDゲートはそのほかのゲートを全て表現できるので「万能ゲート」と呼ばれています。つまり任意の計算式は理論的に全てNAND回路のみで表現が可能です。
論文の中では、便宜上NANDゲートのみが使用されています。（以下この回路を「バイナリ回路」と呼びます）以下の図はA,B,C,Dをinputとするバイナリ回路です。Proverは、全てのinputを知っていることを証明し、Verifierが検証します。
⚫️OP_NAND
NANDゲートはBitcoinですでに実装されているOpcode、OP_BOOLANDおよびOP_NOTをセットで使用することで実現可能です。簡略化のためにこれをOP_NANDとして記述します。
⚫️Bit Value Commitment
以下はProverが各NANDゲートのinput,outputの値（0 or 1）にコミットするためのスクリプトです。hash1のPreimageを提供すればスタックには1がプッシュされ、hash0のPreimageを提供すればスタックに0がプッシュされます。以下簡略化のためにこれをOP_BITCOMMITMENTと記述します。
OP_IF
OP_HASH160
<hash1>
OP_EQUALVERIFY
<1>
OP_ELSE
OP_HASH160
<hash0>
OP_EQUALVERIFY
<0>
OP_ENDIF⚫️Binary Gate Commitment
Proverは上記OP_NANDとOP_BITCOMMITMENTを組み合わせることでBinary Gateにコミットするスクリプトを構築します。以下はNAND1にコミットするスクリプトの例です。
// Reveal Preimage of hashE0 or hashE1
<hashE0/1>
OP_BITCOMMITMENT
OP_TOALTSTACK
// Now the bit value of "E" is on the stack
// Reveal Preimage of hashB0 or hashB1
<hashB0/1>
OP_BITCOMMITMENT
OP_TOALTSTACK
// Now the bit value of "B" is on the stack
// Reveal Preimage of hashA0 or hashA1
<hashA0/1>
OP_BITCOMMITMENT
OP_TOALTSTACK
// Now the bit value of "A" is on the stack
//
// Verify that "A NAND B == E"
//
// Read "B" from alt stack
OP_FROMALTSTACK
#compute A NAND B
OP_NAND
# Read "E" from alt stack
OP_FROMALTSTACK
#Check A NAND B == E
OP_EQUALVERIFY以下3つの値が提供されると、A、B、Eの3組の値（それぞれ0か1）がスタックにプッシュされ、A NAND B == E が成り立つ場合、アンロックが可能となります。
・Preimage of HashA0 or HashA1
・Preimage of HashB0 or HashB1
・Preimage of HashE0 or HashE1⚫️Challenge and Response
Challenge and ResponseはVerifierがProverの主張が正しいことに同意しない場合に 開始されます。主張の矛盾が確認された場合、Verifierは Prover の資金を差し押さえることができます。
Verifierはバイナリ回路から1つのゲートを選択し、Proverはそのinputとoutputを公開します（これを「ゲートを開く」と呼びます）。
両者は、Proverの主張の矛盾が明らかになるか、Verifierが可能な数のChallengeをやり尽くすまで、このプロセスを数回繰り返します。
あるゲートが開かれたときに「D=1」と主張したProverが、後で別のゲートが開かれたときに「D=0」と主張した場合、そのProverは「曖昧な供述」をしたことになり、VerifierはProverの資金を差し押さえることができます。
またゲートを開く要求された際に、Proverが過去の主張と矛盾した回答をせざるを得なくなり、ゲートを開くことを拒否した場合もVerifierはProverの資金を差し押さえることができます。
なお、Proverはすべてのゲートを開く必要はありません。以下の例では、VerifierはProverにNAND7、NAND1、NAND3、NAND6、NAND5を順番に開くように要求しています。
最初にNAND6を開くように要求されたとき、Proverは「I=1」と主張したとします。しかし、その後、NAND1、NAND3、NAND6、NAND5を開くように要求されると、Proverは「I=0」という矛盾した回答をせざるを得なくなります。
このようにVerifierはProverの回答に応じて戦略的にゲートを選択することで効率的に主張を検証することができます。
⚫️Challenge Taptree and Response Taptree
Taptreeは、両パーティがChallenge and Responseスキームにコミットするために使用されます。Taptreeは、スクリプトをleafとして構成されるMerkletreeであり、ルート(Taproot)を鍵のtweakに使用することで、Taptree inner key(キーパス)またはスクリプト(スクリプトパス)のいずれかを使用して出力をアンロックできます。
以下の例では、VerifierはChallenge Taptreeのアンロック条件を公開することでGate7を選択し、VerifierはResponse Taptreeのアンロック条件を公開することでGate7を開いています。
Verifierが同じ変数に対して異なる値を公開した場合（例：E=0 && E=1 ）、Verifierの主張は偽と判明し、Verifierはすべての資金を得ることができます。このモデルは、以下のEquivocations Taptreeによって実現されています。
以上で予備知識の説明は終了です。
ここまでで私たちは、契約者はビットコインのスクリプトを組み合わせてバイナリ回路にコミットし、Taptreesを用いてChallenge and Responseにコミットすることを学びました。
次のセクションでは、BitVMプロトコルの詳細を説明します。
BitVMプロトコル詳細
以降で、とある任意の式を満たす解を知っていると主張するProverと、その主張の真偽について検証するVerifier間でBitVMを用いて契約をする方法について記述します。
1. バイナリ回路構築
契約内容をプログラミング言語で実装、コンパイルし、巨大なバイナリ回路にします。Proverはoutputがtrueとなるようなinputを知っていることを主張しています。
2.トランザクション構築、事前署名
ProverとVerifier間で、1.で構築したバイナリ回路およびChallenge and Responseにコミットするトランザクションを構築し事前署名を行います。
3.契約履行
両者は下図 Tx1 に署名し、ブロードキャストして資金をロックします。
Tx1は既にブロックに取り込まれていますが、Tx2～Tx4はまだブロードキャストされていません。Tx2とTx4はVerifierが保持し、Tx3はProverが保持しています。
上の図は論文に記載されているオリジナルの提案とは異なることは要注意です。上図では、最初のトランザクションの出力は2つに分割され、sighasg_allが事前署名に使用されています。
出力が分割されない場合、使用される可能性のあるすべてのタップリーフが事前署名されなければなりません。詳しくはこちらをご覧ください。
VerifierがProverの主張を正しいと認めた場合、Verifierは「4.Challenge & Response」ステップをスキップし、「5. 決済」ステップに進みます。VerifierがProverの主張を正しくないと考える場合、「4.Challenge & Response」ステップに進みます。
4.Challenge & Response
VerifierはChallenge Taptreeのアンロック条件を公開することでゲートを選択し、 ProverはResponse Taptreeのアンロック条件を公開することで、選択されたゲートを開きます。
このやりとりはオフチェーンで実行されるのが理想的です（オンチェーンで実行することも可能です）。
両者は、Proverの主張の矛盾が明らかになるか、Verifierが可能な数だけチャレンジをやり尽くすまで、このプロセスを数回繰り返します。
以下は、両者がチャレンジとレスポンスをオフチェーンで2回繰り返し、矛盾が発覚した例です。
最初のチャレンジでは、VerifierはNAND1ゲートを選択し、Proverはその入力と出力(A=1, B=1, E=0)を公開しています。2番目のチャレンジでは、VerifierはNAND4ゲートを選択し、Proverはその入力と出力(E=1,F=1,H=0)を公開しています。
Proverは、1回目はE=0、2回目はE=1という一貫性のない応答をしていることにに注意してください。Verifierは、Proverが矛盾した回答をしたため、「5. 決済」ステップに進み、Proverの資金を差し押さえます。
5.決済
Verifierは、「3.契約履行」ステップでProverの主張が正しいと認めた場合、「4.Challenge & Response」をスキップします。両者が協力的であり契約内容に合意する限り、2 of 2の署名でどのような内容でも決済は可能です。
「4.Challenge & Response」ステップで、例えば1度目はE=0、2度目はE=1のようにProverが矛盾した応答をした場合、Verifierは、Equivocations Taprootアドレスのアンロック条件であるpreimage(E=0)とpreimage(E=1)を取得します。
Verifierは、これらを用いて以下の通りTx6をブロードキャストすることで、Proverの資金を取得します。
更なる発展について
・効率を重視したより高度なOpcode
Robin Linusは、論文では議論を簡潔にするためにNANDのみを使用しており、より効率を重視したOpcodeについて以下のように述べています。
実際には、利用可能なビットコインスクリプトのオペコードをすべて使用することで、NANDのみを使用する場合よりもオンチェーンTXを10倍～100倍小さくできる。
In practice using all the available bitcoin script opcodes makes onchain TXs 10x — 100x smaller than when using only NANDs.
現状、 u32 addition、u32 xor、u32 rotationsなどの高レベルなOpcodeが作成されていいます。
・より一般的な契約の実現
提案されたモデルは2つのパーティーに限定されており、このモデルをN:Nまで発展させるには、さらなる研究が必要です。
・Scriptless Script BitVM
ZmnSCPxjは、HashとPreimageをポイントとスカラーに置き換えることで、「Scriptless Script BitVM」が実現可能かもしれないと述べています。このトリックを使うと、Txサイズとオンチェーン・フットプリントを更に減らすこと可能です。
最後に
BitVMはソフトフォークなしでチューリング完全なビットコイン契約を可能にするプロジェクトです。
このプロジェクトに貢献したい方はRepoがこちらにあります。また、Telegramグループもありますので興味のある方は参加してみてください。
