BitVMのストレージ要件を劇的に改善する提案Argo

先日書いたBitVM 3sは↓

techmedia-think.hatenablog.com

SNARK証明の検証をFraud proofベースで行う仕組み。

SNARKの検証というのは、具体的にはGroth16とかであれば楕円曲線を用いたペアリングの演算を行うことになる。EthereumではBN254やBLS12-381で動作するペアリング演算のプリコンパイルドコントラクトを導入しているけど、当然Bitcoinにはそのような計算をするopcodeは存在しないので、BitVMではこのペアリングの演算をGarbled Circuitで表現している。Groth16と同様の検証を行う場合、この回路は約100億個のゲート（77億のフリーゲート + 27億の非フリーゲート）で構成される。

検証者はこの回路のデータをFraud proofのチャレンジに備えて保持しておく必要がある。回路の構成情報（数十GBくらい？）に加えて、非フリーゲート*1あたり

• ガーブルド・テーブル：4行×16 byte = 64 byte
• ハッシュコミットメント：2×20 byte = 40 byte

のデータを保持する必要があるため、合計104バイト × 27億ゲート ≈ 280GBのストレージが必要になる。

Argo

そんな中、最近この回路のサイズを劇的に小さくするアイディア（厳密には回路ではなくなる）が発表された↓

eprint.iacr.org

従来のGarbled Circuitでは、回路内の各ワイヤのbit値 にそれぞれランダムなラベル（128ビットの乱数）を割り当て、各ゲートについて「入力ラベルの組み合わせに対して、どの出力ラベルが得られるか」を暗号化した対応表＝ガーブルド・テーブルを作成する。

この方式だと、256 bitの有限体上の乗算も1 bit単位のゲートに分解する必要があり、SNARK検証器のようなものを作ろうとするとゲート数が爆発的に増える。これは回路全体がずっとbitの世界で処理されるのが根本的な問題。

Argo MACは、演算を回路に変換することなく、

1. 入力値（曲線上の点のbit分解）を準同型MACに変換し、
2. 準同型MAC上で楕円曲線の演算を直接実行する

2により楕円曲線上の演算をネイティブに実行できるので、フリーゲートのようにガーブルド・テーブルのデータを必要とせずに演算ができる。

ITPG

Argo MACでは、1の変換にITPG（Information Theoretic Partial Garbling）という手法を用いる。ITPGは、「秘密の係数を持つ多項式を、秘密を漏らすことなく相手に評価させる」仕組みで、以下のように動作する。

楕円曲線上の点P = (x, y)の準同型MACはという形で表される。ここでφは楕円曲線の自己準同型写像で、Kはランダムな点。このMAC値の計算をする関数は、各座標が入力座標に対する2次の多項式になり、多項式の係数にはMACの鍵（φ、K）の情報が含まれる。これらの情報は検証者に知られてはいけない。φを恒等写像とした場合、この計算は、単純な楕円曲線上の点の加算P + Kなので、とした場合、加算結果のヤコビアン座標は以下のように計算される。

• 
• 
• 

この式においては、Pの座標は公開される変数、Kの座標はは秘密の係数として機能する（Bは曲線のパラメーター）。各式はに関して2次の多項式であり、かつ秘密の係数に関しては線形となる。

ITPGでは、この多項式の係数をとして、各係数をランダムなノイズで隠した状態で検証者に渡す。入力座標xをρ bitに分解すると、となるので、各に対して、

を計算する。ここで、は多項式の秘密係数からくる値で、はランダムなノイズ。bit値によりこれは、

• b = 0の場合、（ランダム値のみ）
• b = 1の場合、（秘密係数＋ランダム値）

となる。どちらの場合もは隠される。

各bitのを検証者に渡すため、ガーブラーはラベルで暗号化してアダプターテーブルに格納する：

検証者は、自分のビット値に対応するいずれかのラベルしか知らないため、2つのうち1つしか復号できない。これによりが検証者に漏れることはない。

ただ、このままだとノイズが入ったままなので、ノイズ除去をする必要がある。たとえば、で考える場合（は秘密係数、xは公開入力）、ガーブラーがノイズを含めて計算した値を

• 
• 

とした場合、そのまま計算すると

となる。ノイズが残った状態なので、ガーブラーはを渡す。ガーブラーはすべての値を知ってるのでこの計算は可能。検証者はをさらに加算することでノイズを除去できる。このデータはアダプターテーブルに追加フィールド要素として含まれるみたい。

Half Gate

↑のアダプターテーブルは、Half Gate手法を適用することでサイズを半分にできる。具体的には、b = 0の方の出力の値をラベルのハッシュ値とし、テーブルに格納するのをのみとする。こうすると、

• b = 0の場合は、を計算するだけ
• b = 1の場合は、テーブルの内容をで復号する

と計算できる。

再構成

検証者は全bit分のを入手すると、bit位置に応じたを乗算して合算し、ノイズ除去を行い、MAC値を計算できる。こうして得られたMAC値は準同型性を持つため、2つのMAC値を以下のように加算すると

P + Qに対するMAC値が得られる。この特性により、フリーゲートと同様、ガーブルド・テーブルを必要とせずに楕円曲線上の点の加算ができる。論文では、

In forthcoming work, we will show how to build a garbling scheme for pairing-based SNARK verifiers that respects this MAC structure. In different forthcoming work, Babylon Labs [27] will use our technique in a different way to build a SNARK verifier based on linear pairing witness encryption [28]. In both cases, the key enabling technology that makes these schemes over 1000× more efficient than existing approaches is Argo MAC.

とあり、SNARK検証器全体のガーブリングスキームは後続の論文で公開されるらしい。そのスキームにおいてArgo MACがテーブルサイズの支配的コストとなるため、Groth16検証器全体で約25MBと推定されていて、BitVM 3sの約280GBと比較すると約10,000倍の削減になると。

あと、↑にも書いてあるけどBabylon LabsもArgo MACベースのSNARK検証器の構築を予定しているらしい。