Garbled Circuitを利用してBitVMのオンチェーンゲート実行をオフロードするDelbrag

最近公開されたBitVM 3のヒントとなったJeremy Rubinによるドラフト論文Delbrag↓

https://rubin.io/public/pdfs/delbrag.pdf

この論文では、Garbled Circuitを利用して、Bitcoin上で任意の計算の検証を可能にするBitVMを効率的に実現する方法を提案している。

YaoのGarbled Circuit

Garbled Circuitは1982年にAndrew Yaoによって考案された、2者間でそれぞれ秘密の情報を明かすことなく、共同で計算をできるようにする仕組み。

アリスとボブでこのMPCを実行するステップは↓

1. 計算内容を論理回路として表現する。この回路の構造は両者にとって既知。
2. 次にアリス（ガーブラーと呼ばれる）が、この回路をカーブル化（後述）する。
3. アリスはガーブル化した回路の情報と、自分の入力値に対応する鍵をボブに送信する。
4. ボブは、回路を評価するため、自分の入力値に対応する鍵を得るのに紛失通信*1を使って、入力値を明らかにすることなくアリスから対応する鍵を受け取る。
5. ボブは4を得て回路を評価し、最終出力を得る。
6. ボブはアリスと計算結果を共有する。

ガーブル化

この仕組みの肝となるのがガーブル化。

ガーブラーは、それぞれ1 bitの２つの入力と1つの出力を持つ以下のような回路内のゲート（以下はANDゲート）に対し、それぞれのとり得る値に対して128 bitの鍵（ラベル）を割当てる。

• については、
• については、
• については、

のように。真理値表で表現すると、

次に、2つの入力の鍵を使って出力値の鍵を暗号化する。その結果の表をガーブルド・テーブルと呼ぶ↓

ガーブルド・テーブル

最後に、ガーブルド・テーブルのデータをランダムに並べ替える。

なお、出力の鍵は、次のゲートの入力の鍵になる。

回路内の全ゲートに対して上記の暗号化を行い、ガーブル化した値を相手に共有する。この時、自分の秘密の入力値に対応する鍵（ラベル）も共有するが、その実際の値（0 or 1）について相手は分からない。

相手側は、自分の秘密情報に対応するデータを紛失通信を使って入手すれば回路を評価可能になる。これにより、お互いの秘密情報を明らかにすることなく計算を行うことができるようになる。

Delbrag

BitVMには、任意の計算の結果の検証をFraud Proofベースだけどオンチェーンで行うことから、オンチェーンフットプリントがとても大きくなるという問題がある。

Delbragでは、

1. 任意の計算を↑のGarbled Circuitで表現する。
2. 1の構築時に使った各ゲートの鍵（ラベル）のハッシュ値をそれぞれ計算し、
3. 2のハッシュ値を使ってFraud Proof用のTaptreeを構築する。
   • 不正が発生した場合の条件：1つのNANDゲート*2に付き以下の4つの条件（本来の入力に対する出力でない場合）のTapleafを作る。
     • 入力が両方0なのに、出力が0の場合
     • 入力が両方1なのに、出力が1の場合
     • 入力が0, 1なのに、出力が0の場合
     • 入力が1, 0なのに、出力が0の場合
   • タイムアウト条件：
     • 期限までにビットが公開されない場合、検証者は資金を回収するか、事前署名されたトランザクションを用意しておいて返金できるようにする。
   • 両者が協力的に合意した場合の条件。これはマルチシグなので、Taprootの内部鍵でMuSig2するのでも良さそう。

証明者は、

• ↑で構築したP2TRに資金をロックし、
• タイムアウトの期限を迎える前に回路の入力値のコミットメントを（別のデリゲートインプットを使用して）を開示し、
• コミットメントに対応する回路の鍵（ラベル）を検証者に開示する
• 検証者は受け取ったラベルを元に回路を評価する。
• 結果について、
  • 両者が合意したら、資金を適切に分配する。
  • 結果が割れた場合、回路に不正がある場合、不正のあったゲートを特定し、Fraud Proofを提供して検証者は資金を没収するなりする。

オンチェーンで提供されるのは回路の入力に対するコミットメント（ハッシュ値）のみで、実際の回路の評価はすべてオフチェーンで行われ、不正があった場合のみ、対応するゲートについて対応するTapleefを使ってFraud proofを提供する。

このようにGarbled Circuitを利用することで、計算をオフチェーンにオフロードすることができるようになり、BitVMのオンチェーンフットプリントを大幅に削減する。

回路の正しさの証明

↑で回路をセットアップする際、回路が正しくセットアップされているのか、つまり、

• 各ゲートの出力は、対応する2つの入力でゲートを評価した結果に対応するラベルになっているか。
• 各ゲートの出力は、対応する2つの入力の鍵を使って暗号化されているか。

について、Delbragの論文では、セットアップ時にこれらを別途zk-SNARK回路を使って証明するとある。Tapleafを構成する際のハッシュ値が、正しいラベルのハッシュ値なのかをチェックする仕組みも必要に思えるけど、そこは触れられていない。

そして、このDelbragから着想を得て、Garbled Circuitの正しさをコストのかかるゼロ知識証明ではなく別の方法で証明しているのが新しいBitVM 3。これについては、また別の記事で。

*1:https://techmedia-think.hatenablog.com/entry/2025/06/17/231835#%E7%B4%9B%E5%A4%B1%E9%80%9A%E4%BF%A1

*2:もともとBitVMではNANDゲートを複数組み合わせると、他の論理ゲートを構築できるという理由でNANDゲートを採用している。NANDゲート以外を使っても別に問題はなく、その場合リーフのFraud Proofの条件が変わるだけ