オンチェーンフットプリントを劇的に削減するBitVM 3

BitVM 0、BitVM 1、BitVM 2、BitVM Xに続いて、最近新たにBitVM 3が提案された↓

https://bitvm.org/bitvm3-rsa.pdf

（2025.07.17追記：その後、セキュリティ仮定に誤りがあることが報告され、この論文は廃止され、RSAベースのガーブリングに代わる新たなBitVM 3sが公開された。）

このBitVM 3は↓のDelbragから着想を得た提案で

techmedia-think.hatenablog.com

BitVMのオンチェーンフットプリントを大幅に削減する。

BitVM 3

オリジナルのBitVMでは任意の計算の検証だったけど、BitVM 2からは以下のようなトランザクションチェーンでSNARK証明の検証をオンチェーンのチャレンジ＆レスポンスで行うようになった。

Claim Tx：証明者がSNARK証明の有効性を主張するトランザクション。
Challenge Tx：証明者の主張に対して挑戦者が異議を申し立てるトランザクション。
Assert Tx：2に対して証明者がSNARK検証の各ステップの中間結果を公開するトランザクション。
Disprove Tx：3に対して挑戦者が、特定の中間値の誤りを証明するトランザクション。

↑のAssert TxとDisprove Txのサイズはそれぞれ2〜4MBになる。

このオンチェーンフットプリントを、Assert Tx→約56KB、Disprove Tx→200Bまで削減しようというのがBitVM 3の提案。

BitVM 3では、SNARK検証器を↑のGarbled Circuitベースの回路で実装する（Groth16ベースで約50億個のゲートで構成されるみたい）。挑戦者がGarbled Circuitを評価して、SNARK証明が正しい場合は「1」に対応するラベルを出力、無効な場合は「0」に対応するラベルを出力し、これがDisprove Txで提出するFraud Proofになる。

RSAベースのガーブル化

従来のガーブル化の際は、出力のラベルを暗号化する際にAESやハッシュベースのXORなどが用いられているけど、BitVM 3ではRSAベースのアプローチを採っている。

ガーブラーは、2つの安全素数P = 2p + 1とQ = 2q + 1を選択しモジュラスN = P・Q = (2p + 1)(2q + 1)を計算し、 5つの公開指数 ${e, e_1, e_2, e_3, e_4}$ を選択する。これらの指数値はpqと互いに素である必要があり、またパフォーマンスの観点から小さな素数（3, 5, 7, 11, 13など）が推奨されている。そしてNと公開指数を公開パラメーターとする。なお、各指数値の逆元を ${d, d_1, d_2, d_3, d_5}$ とし、導出指数を ${h \equiv (e_1 e_4 d_2 - e_3) (\mod pq)}$ とする。
続いて、ガーブラーはトラップドアφ(N)を使って、ランダムに選択した出力ラベルから以下を満たす入力ラベルを計算する。通常は入力値を使って出力ラベルを暗号化していたけど、このアプローチはその逆。
- ${a_0^{e} \cdot b_0^{e_1} \equiv c_0 (\mod N)}$
- ${a_0^{e} \cdot b_1^{e_2} \equiv c_0 (\mod N)}$
- ${a_1^{e} \cdot b_0^{e_3} \equiv c_0 (\mod N)}$
- ${a_1^{e} \cdot b_1^{e_4} \equiv c_1 (\mod N)}$
  ガーブラーは、pqを知っているので、以下により↑を満たす入力ラベルを計算できる。
- ${b_0 \equiv (c_1c_0^{-1})^{h^{-1}}(\mod N)}$
- ${b_1 \equiv b_0^{e_1d_2}(\mod N)}$
- ${a_0 \equiv c_0^{d}\cdot b_0^{-e_1d}(\mod N)}$
- ${a_1 \equiv c_0^{d}\cdot b_0^{-e_3d}(\mod N)}$
上記を、ガーブラーは回路の最終出力ゲートから逆向きに実行していく。

アダプター要素

上記の逆向きのラベル生成では、回路の各ゲートの出力は必ず次の１つのゲートにのみ接続されるという制限（ファンアウト＝１の回路）が必要になるが、BitVM 3ではこの制限を回避するためにアダプター要素を導入している。

たとえば、ゲートGの出力値（ラベルを ${l_0}$ or ${l_1}$ とする）がゲート ${G_A, G_B}$ という２つのゲートの入力値（それぞれラベルを ${(l_{A, 0}, l_{A, 1})}$ および ${(l_{B, 0}, l_{B, 1})}$ とする）となる場合、逆向きにラベル生成されたゲート ${G_A, G_B}$ の入力値のラベルは同じ値にはならない。

そこで予め、以下のようなアダプターを計算して、公開パラメーターとする。

${T_{A, 0} \equiv l_{A, 0} \cdot (l_0)^{-1} (\mod N)}$
${T_{A, 1} \equiv l_{A, 1} \cdot (l_1)^{-1} (\mod N)}$
${T_{B, 0} \equiv l_{B, 0} \cdot (l_0)^{-1} (\mod N)}$
${T_{B, 1} \equiv l_{B, 1} \cdot (l_1)^{-1} (\mod N)}$

このアダプター要素を利用することでファンアウトが１より大きい回路も構築可能になる。

回路の検証と再ブラインド

Delbragでは回路の正しさは別途zk-SNARK回路を作って証明するようになっていたけど、BitVM 3では上記のように構築した回路をそのまま検証者と共有することで、回路の正しさをチェックできるようにする。

ただ、このままだとすべてのラベル値を検証者が知っているのでFraud Proofが機能しなくなるので、以下の手順で回路を再ブラインドする。

ガーブラーは、k個*1のPairwise Coprime*2な公開指数 ${u_1, ..., u_k}$ を公開し、
トラップドア情報を使って秘密の値 ${s = \Pi_i u_i^{-1} (mod \phi(N))}$ を計算する。
元のラベル ${a_0}$ に対して、i回目の再ブラインドは ${a_-^{(1/u_i) (\mod N)}}$ を計算することで行われる。
また↑の各アダプター要素についてはガーブラーが ${T^{s}_{i, k} = T_{i, k}^{u_1^{-1} \cdot u_2^{-1} \cdot ... \cdot u_k^{-1}}}$ を公開することで、検証者は非対話的にk回分のアダプター要素を計算することができる。