Garbled Circuitを利用した効率的なSNARK検証を提案するBitVM 3s

BitVM 3について、以前以下の記事を書いたけど↓

techmedia-think.hatenablog.com

このRSAベースのガーブリングスキームには安全性の仮定に誤りがあり取り下げられ、その後BitVM 3sという改訂版が公開された↓

https://bitvm.org/bitvm3.pdf

3sの名前は、Secure、Simple、Bitcoin Scriptベースというところから来てるらしい。

BitVM 3s

BitVM 3-RSAもBitVM 3sもいずれもJeremy Rubinが提案したDelbragのアイディアを元にしたもので、SNARK証明の検証をオンチェーントランザクションを用いたチャレンジ＆レスポンスで実行するBitVM 2のスキームをオフチェーンにオフロードするという点は変わらない。

BitVM 3sのシンプルなブリッジの構成は↓

BitVM 2よりシンプルになってる。

• DepositTx：ユーザーがBTCをn-of-nマルチシグにロック。全オペレーターの協力で作成・公開。
• WithdrawTx：オペレーターが引き出しを請求する際に公開。セットアップ時に事前署名によるコベナンツを使用。
• AssertTx：引き出しを請求するオペレーター自身が公開。担保を差し入れつつ、SNARK証明の入力ラベルをLamport署名で公開。
• DisproveTx：不正があった場合に誰でも（パーミッションレス）公開可能。セットアップ時にGarbled Circuitのデータを受け取っていれば、誰でも不正を検出してDisprove Scriptを実行できる。

セットアップ

ガーブラー（証明者、オペレーター）は、SNARK検証用のGarbled Circuitを生成する。Groth16検証回路は約100億ゲート（77億のフリーゲート＋27億の非フリーゲート）で構成される。*1

• フリーゲートとはXORゲートのことで、2つの入力ラベルのXOR値を使って出力ラベルを導出できるようにしているため（Free-XOR手法）、ガーブルド・テーブルが不要になる。つまり、出力ラベル = 入力ラベルA ⊕ 入力ラベルB
• 非フリーゲートはXOR以外のゲートで、（↑のDelbragの記事に書いたように）2つの入力ラベルで出力ラベルを暗号化したガーブルド・テーブルを必要とする。
  • ここでは、k = Hash(入力ラベルA ⊕ 入力ラベルB)を計算し、
  • kで出力ラベルを暗号化してガーブルド・テーブルのエントリーciphertext = 出力ラベル ⊕ kを導出する

ガーブラーは、各非フリーゲートについて、

• ワイヤーラベル：各ワイヤーの0と1の状態に対応する128bitのランダム値（ラベル）。このラベルをBitHash（後述）した値がDisprove Scriptにコミットされる。
• ガーブルド・テーブル：2つの入力値の組み合わせ分（合計4つ）、出力ラベルを暗号化したもの
• Taprootコミットメント：各ガーブルド・テーブルのエントリーを検証するためのDisprove Script（後述）を含む巨大なTaptree

を生成し、検証者にガーブルド・テーブルのデータと各ワイヤーラベルのハッシュ値を送る。検証者は、これらの情報からTaptree（各リーフがDisprove Scriptでそこに適切なハッシュ値が埋め込まれていること）が正しく構築されていることを検証する。

アサーション

ガーブラーはSNARK証明を公開する。↑のブリッジの例では、これでブリッジの清算をトリガーする。この時、担保として提供する金額はDisprove Scriptが約20KB未満とこれまでに比べて小さいので、$100未満くらい。

AssertTxのインプットのwitnessにはSNARK証明（128 byte）とSNARKの公開入力値（20 byte）に対応するラベルが含まれるため、予め担保UTXOは、これらのデータに対するランポートコミットメントが設定されたロックスクリプトに資金をロックしたものになると思われる。そしてAssertTxで実際のデータとそれに対するランポート署名が提供される。

どうしてランポート署名が必要かというと、ガーブラーはすべてのラベルの値を知っているけど、検証者は与えられたラベル値が0に対応するものか1に対応するものか知る術がない。そのためランポートコミットメントにより、各ビットが指すラベルの値がオンチェーンでコミットすることで、確定したビット列（SNARK証明と公開入力）を誰でもオンチェーンで確認できるようにしている。このラベルと実際のデータの紐付けがないと意味のあるSNARK検証を行っていることを確認できない。

チャレンジ

SNARK証明や回路が不正であれば、検証者はTaptreeのデータを使ってオンチェーンでFraud Proofを提供することで、ガーブラーのアサーションを無効化する。期間内にFraud proofが提供されなければタイムアウトにより証明は有効とみなされる。

Fraud proofには、

• 計算が不正なゲートの入力ワイヤーラベル
• Taptree内の該当ゲート（Tapleaf）のマークルパス
• TapleafのDisprove Script

が含まれ、Disprove Scriptでは以下がチェックされる

1. 入力ラベルがコミットされた値と一致するか検証
2. 復号鍵k = Hash(入力ラベルA ⊕ 入力ラベルB)を計算
3. 出力ラベルを復号：出力ラベル = ciphertext ⊕ k
4. Hash(出力ラベル)がコミットされた値と異なる場合、不正が証明される

BitHash

BitVM 3のコア機能の1つがBitcoin Script向けの新しいハッシュ関数BitHash。BitcoinにはOP_SHA256やOP_RIPEMD160などのハッシュ計算用のopcodeがあるけど、これらはすべて入力値をまるごとハッシュするので、入力の各ビットを個別に取り出して後続の計算に使うといったことができない。また算術系のopcodeも現状32 bit演算しかサポートしていない。*2

BitHashは、128 bitのプリイメージを1 bitずつ処理するハッシュ関数で、各bitの値に応じてRIPEMD160とOP_SHA256のいずれかを適用する。

<bit 127> <bit 126> . . . <bit 1> <bit 0> # 入力値
<初期値> # 0x00000000

128回繰り返し:
  OP_SWAP
  OP_DUP
  OP_TOALTSTACK    // 後で使うために保存
  OP_IF
    OP_RIPEMD160    // ビット = 1 の場合
  OP_ELSE
    OP_SHA256       // ビット = 0 の場合
  OP_ENDIF

OP_DUPとOP_TOALTSTACKは、プリイメージを検証後に再利用するためにアルトスタックに保存するための処理。

OP_XORの課題

↑のFraud proofの検証には１つ問題があって、BitcoinのOP_XOR opcodeは2010年に無効化されており、Great Script Restoration提案などによるソフトフォークでの有効化が必要になる。またその際に、32 bit制限も解除される必要がある。

リソース要件

Garbled Circuitを利用した仕組みにより、BitVM 2と比べてオンチェーントランザクション数が劇的に削減され（約 1,000倍）、担保要件も低下し、BitHashの導入によりBitcoin Scriptの制約下で効率的なハッシュコミットメントを実現し改善が進んできてる。

あとは、Garbled Circuitのデータ約280GBのオフチェーンストレージが大きめか*3。