# SIPP in SNARKs によるpairingの集約 pairingをSNARK回路内で実行することは、SNARKの集約や、trustless bridgeやERC4337の署名集約、light　clientなど様々な約束された応用があります。この投稿ではSIPPと呼ばれる、複数のpairingの積を効率的に計算するスキームを紹介し、それをplonky2で実装したベンチマークを示します。 ## SIPP SIPPは[BMMTV18](https://eprint.iacr.org/2019/1177)で導入されたpairingを集約する手法です。 SIPPの目的は、Verifierが$\vec{A} \in \mathbb{G}_1^n$, $\vec{B} \in \mathbb{G}_2^n$のペアリング$Z: = \vec{A}*\vec{B} = \prod_{i=0}^{n-1} e(A_i, B_i)$を効率的に計算することです。 ### 手順 1. Proverは$Z = A*B$を計算し、Verifierに渡す。 ProverとVerifierは次の手順を繰り返す 1. Proverは$Z_L = A_{[n/2:]} * B_{[:n/2]}$, $Z_R = A_{[:n/2]} * B_{[n/2:]}$を計算してVerifierに渡す。 2. Verifierは$x \in \mathbb{F}_r$をランダムにサンプリングし、Proverに渡す。 3. VerfierとProverは$A' = A_{[:n/2]} + x A_{[n/2:]}$, $B' = B_{[:n/2]} + x^{-1} B_{[n/2:]}$を計算する 4. Verifierは$Z' = Z_L^x Z Z_R^{x^{-1}}$を計算する 5. $A\leftarrow A'$, $B\leftarrow B'$, $Z \leftarrow Z'$, $n \leftarrow n/2$ $n = 1$になったら、Verfierは$e(A, B) \overset{?}{=} Z$を検証し、そうであれば受理する。 # Plonky2による実装 SIPPのVerifierの手順をplonky2で実装しました。$\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{F}_{q^{12}}$のexponentiationはsnarkのコストが高いので、単独の回路に切り出し、最後にaggregationしています。特に$\mathbb{G}_2$や$\mathbb{F}_{q^{12}}$のexponentiationはそれ単体でも非常にコストが高いので、指数をそれぞれ6bit, 5bitずつに分解し、最後にrecursive proofによってaggregationする方針を取りました。 EC2のc6a.32xlargeインスタンスにおいて、BN254上のexponentiationのproof生成には次の実行時間が必要でした。 G1 exponentiaion: 12s G2 exponentiaion: 6bitのproofsの合計生成時間13s + aggregation 10s = 23s Fq12 exponentiaion: 6bitのproofsの合計生成時間118s +aggregation 20s = 138s $n$個のpairingに対してSIPPを適用すると、G1 exponentiaionとG2 exponentiaionは各$n-1$回、Fq12 exponentiationは$2 \log_2 n$回必要になります。従ってトータルの時間は`35 * (n-1) + 276 * log n` secsと、それらのproofをaggregationするのに必要な時間となります。 ただし、全てのproofは完全に並列に実行することができ、マシンのthread数に反比例して実行時間が小さくなることに注意してください。 以下は`n`を変えたときのベンチマークです。 [このテスト](https://github.com/qope/SIPP/blob/96b520ff11fe9cd0f5d169c1fbde7f74927ad859/src/verifier_circuit.rs#L709-L755)を`LOG_N`の値を変えながら実行しました。 - `n = 2`のとき、proofs `507s` + aggregation `2s` = `509s` - `n = 4`のとき、proofs `776 s` + aggregation `5s` = `781s` - `n = 32`のとき、proofs `776 s` + aggregation `5s` = `781s` ERC4337の署名集約に利用するなどの用途では、まだ非常にコストが高いです。しかしながら、同一の回路に対する証明を何度も繰り返す、高度に並列化可能な処理のために、マシンの数を多くすると現実的な処理時間になることが予想されます。Novaなどの、一様な回路の再帰証明スキームは、plonky2の代替になる可能性があります。