ビットコインがチューリング完全に対応！？任意のプログラムを実行検証するBitVMとは

2023-10-20T03:51:46Z

BitVMはビットコイン上で任意のプログラムを実行したかを検証するプロトコル。現状のビットコインは限られたプログラムしか実行できないが、BitVMを使うことで任意のプログラムを実行できる。ただし、このプログラムが実行されるのはビットコイン上ではなく、オフチェーン上で実行される。その実行結果が正しいかの検証をビットコイン上で行う。もし実行結果が間違っている場合、Fraud Proofを使って資金を没収することができる、というのがBitVMの仕組み。

BitVMの提案書はページ数も少なく内容も難しくないのでこちらの原文を読むのがおすすめ。日本語での解説記事はこちら。

論理回路コミットメントという発明

BitVMではBit Value Commitmentという0または1を出力するためのプリイメジハッシュをそれぞれ構成する。これをOP_BITCOMMITMENTと呼ぶ。

#Bit Value Commitment
OP_IF
  OP_HASH160
  <hash1>
  OP_EUALVERIFY
  <1>
OP_ELSE
  OP_HASH160
  <hash0>
  OP_EUALVERIFY
  <0>
OP_ENDIF

次に、NAND回路を構成するが、これは既存のビットコインスクリプトであるOP_BOOLAND, OP_NOTを使うことで簡単に構成できる。これをOP_NANDと呼ぶ。

#OP_NAND
OP_BOOLAND
OP_NOT

OP_BITCOMMITMENTとOP_NANDを使ってLogic Gate Commitment（論理回路コミットメント）を構成する。これもプリイメジハッシュをセットすることで論理回路にコミットする。0または1に対応するプリイメジを公開することで論理回路の出力を制御することができる。

//Cのビット値をALTSTACKへ退避
OP_BITCOMMITMENT
OP_TOALTSTACK

//Bのビット値をALTSTACKへ退避
OP_BITCOMMITMENT
OP_TOALTSTACK

//Aのビット値をSTACKへセット
OP_BITCOMMITMENT

//Bのビット値をSTACKへセット
OP_FROMALTSTACK

//( A NAND B)値をSTACKへセット
OP_NAND

//Cのビット値をSTACKへセット
OP_FROMALTSTACK

//(A NAND B == C)かのチェック
OP_EQUALVERIFY

この論理回路コミットメントを1つのNAND回路として見立て、以下のような回路を作る。以下の例では8つの論理回路コミットメントがある。

この論理回路をTaprootのリーフとして構成したものが以下。(8)がTrueになるようにA,B,C,Dのインプットを正しく与える必要がある。

論理回路の実行と検証

上記で構成した論理回路をオフライン上で実行する。この論理回路を正しく実行したかを検証するために、チャレンジ＆レスポンス方式を使う。そのために、以下のように事前に証明者と検証者が協調してプレ署名による一連のトランザクション（TX1～TX4...）を構成する。

その後、証明者が正しく論理回路を実行したかを検証者が検証する。その際のチャレンジ＆レスポンスの流れは以下となる。

検証者はチャレンジをするためにプリイメジを公開する(TX1)。
証明者はそのチャレンジに対応するレスポンスをする。上図の例では証明者はNAND7の値、J NAND A = L となるようなプリイメジを公開する(TX2)。
- もし証明者が一定期間レスポンスしない場合、検証者は資金を没収できる。
検証者は次のチャレンジをするためにプリイメジを公開する(TX3)。
証明者はそのチャレンジに対応するレスポンスをする(TX4)。
- もし証明者が間違ったレスポンスをした場合、検証者はそれをFraud Proofとして提出することで資金を没収できる（Fraud Proofの仕組みは後述）。

Fraud Proofの構成

証明者が不正等による誤ったレスポンスをした場合、検証者はFraud Proofを提出することで資金没収を可能にするために、以下のようなTaprootアドレスを構成する。ここでいうFraud Proofは、あるビットを出力するために必要なプリイメジが複数公開されたもの。例えばAのビットを0とするためにはA0に対応するプリイメジのみ証明者は公開する。もし証明者がA1のプリイメジも公開すれば、検証者はA0とA1のプリイメジを使うことで、このアドレスの資金を没収することができる。