# BLS署名集約

BLS署名集約には、主に２種類ある。

1. 同一のメッセージに対し、複数人が署名する場合
2. 各人がそれぞれのメッセージに署名する場合

しばしば1はmultisignature、2はaggregate signatureと呼ばれる[[BGLS03](https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf)]

Intmaxにおいてaggregatorが実行する各ブロックごとのBLS署名集約は1に相当する。finalizeの際にはそれら複数ブロックのBLS署名を更に集約する必要があり、これが2に相当する。

# multisignature
ユーザーの秘密鍵を$\mathrm{sk}_i \in \mathbb{F}_r$, 公開鍵を$\mathrm{pk}_i = \mathrm{sk}_i G \in \mathbb{G}_1$とする。ここで$G \in \mathbb{G}_1$はジェネレーター。

署名するべきメッセージ(トランザクションツリーのルート)を$m$とする。MapToCurveを用いて、$m$を$M \in \mathbb{G}_2$にマップする。

署名は$\sigma_i = \mathrm{sk}_i M \in \mathbb{G}_2$であり、各署名は

$$e(\mathrm{pk}_i, M) \overset{?}{=} e(G, \sigma_i) $$

によって検証することができる。

これは公開鍵の集約$P = \prod_i \mathrm{pk}_i$と、署名の集約$S = \prod_i \sigma_i$を用いて

$$e(P, M) \overset{?}{=} e(G, S) $$

とすることで１回のペアリングでまとめて検証することができる。ただし、$P$の計算は別途SNARK内で実行することで正しさを証明する必要がある。

$S$の計算はSNARK回路内で実行する必要はないが、Rogue key攻撃を防ぐために、各ユーザーが$\mathrm{pk}_i$に対応する$\mathrm{sk}_i$を知っていることの証明(PoP; Proof of Possession)を事前に行う必要がある。

Intmaxでは、ユーザー登録フェーズで所定のメッセージに対し署名を要求し、それが通った場合のみマークルツリーに公開鍵を登録し、署名集約時にはマークルツリーに公開鍵が登録されていることを合わせて確認することでRogue key攻撃を防いでいる。

なお、PoPしなくてもRogue key攻撃がないmultisignatureスキームとして[[BDN18](https://eprint.iacr.org/2018/483.pdf)]がある。しかしながら、これは各署名者が他の署名者の公開鍵を予め知っている必要があり、Intmaxの用途には不向きであると考えられる。

# aggregate signature
$k$番目のブロックのaggregated signatureを$S_k$, aggregated public keyを$P_k$, メッセージハッシュを$M_k$とする。

複数のブロックのBLS署名は、aggregated signature $S = \prod_k S_k$を用いて

$$e(G, S) \overset{?}{=} \prod_k e(P_k, M_k)$$

を検証すれば良い[[BGLS03](https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf)]。ここではRogue key攻撃は発生せず、また$S$はSNARKの中で計算する必要もない。

バッチ検証するブロックの個数を$n$とする場合、この検証に`34000*(n+1) + 45000`のgas costが必要になる[[EIP1108](https://eips.ethereum.org/EIPS/eip-1108)]。

このコストを更に抑える場合は、右辺のpairingをSNARK回路で検証する必要がある。

### SNARK検証のコスト

plonky2の実装では、１回のmiller-loopとfinal-exponentiationがともに`d=21`で10分程度。`n+1`回のmiller-loopと1回のfinal-exponentiationが必要なので`10(n+2)`分ほどが必要になる。

ただし、`n+1`回miller-loopは並列化が可能

# SnarkPack

[SnarkPack](https://eprint.iacr.org/2021/529)は多くのpairingを数個のpairingへaggregationする手法。

基本的なアイデアはBulletProofsと同じ。BulletProofsではPedersen Hashを加法準同型コミットメントとして利用し、ベクトルを半分のサイズに分け、乱数結合をとることで長さを半分にするが、SnarkPackの場合はpairingそのものをcommitmentとして利用する。

Verifierが選んだ乱数$r \in \mathbb{F}_r$を用いて

$$e\left(\left(\sum_i r^i \right)G, S \right)^{ } \overset{?}{=} \prod_k e(r_k P_k, M_k)$$

のようにbatch検証する。

$$\vec{v}_j = (H, a_j H, \ldots , a_j^{n-1} H) \in \mathbb{G}_1^n$$

$$\vec{w}_j = (a_j ^{n}G, \ldots, a_j^{2n -1} G) \in \mathbb{G}_2^n$$

とする($j = 1,2$)。

ただし、$a$, $b$はtrusted setupで生成された秘密の値。

$T_{j} = (\vec{A} * \vec{v}_j) (\vec{w}_j * \vec{B})$ ($j=1,2$)

$Z = \vec{A} * \vec{B}^{\vec{r}}$

を計算しておく。

また$\vec{B}' =\vec{r} \circ \vec{B}$, $\vec{w}_j' = \vec{r}^{-1} \circ \vec{w}_j$ ($j=1,2$)とする。

Proverは次のループを実行する。

1. $n' = n_{i-1}/2$
2. $Z_L = \vec{A}_{[n':]} * \vec{B}_{[:n']}' \in \mathbb{G}_t$, $Z_R = \vec{A}_{[:n']} * \vec{B}_{[n':]}'\in \mathbb{G}_t$
3. $T_{jL} = (\vec{A}_{[n':]} * \vec{v}_{j[:n']}) (\vec{w}_{j[:n']}' * \vec{B}_{j[n':]}') \in \mathbb{G}_t$ ($j=1,2$)
4. $T_{jR} = (\vec{A}_{[:n']} * \vec{v}_{j[n':]}) (\vec{w}_{j[n':]}' * \vec{B}_{j[:n']}') \in \mathbb{G}_t$ ($j=1,2$)
5. $h_{com} = hash(T_{1}, T_{2})$
6. $x_{i} = hash(x_{i-1}, Z_L, Z_R, T_{jL}, T_{jR})$
7. $\vec{A} \leftarrow \vec{A}_{[:n']} + x_i \vec{A}_{[n':]}$, $\vec{B} \leftarrow \vec{B}_{[:n']}' + x_i^{-1} \vec{B}_{[n':]}'$
8. $\vec{v}_j \leftarrow \vec{v}_{j[:n']} + x_i^{-1} \vec{v}_{j[n':]}$, $\vec{w}_j' \leftarrow \vec{w}_{j[:n']}' + x_i \vec{w}_{[n':]}'$
9. $n_{i} = n'$

$n_{i} = 1$となったとき、次の手順に移る

1. $f_v(X)=\prod_{j=0}^{\ell-1}\left(1+x_{\ell-j}^{-1} X^{2^j}\right)$, $f_w(X)=X^n \prod_{j=0}^{\ell-1}\left(1+x_{\ell-j} r^{-2^j} X^{2^j}\right)$
2. $z = hash(x_l, v_j, w_j')$
3. $v_j = f_v(a_j) H \in \mathbb{G}_1$, $w_j = f_w(a_j) G \in \mathbb{G}_2$を証明するために、

$v_j$に関して、

$$q_v(X) = \frac{f_v(X) - f_v(z)}{X - z}$$を計算し、

$$C_{j, q}^v = q_v(a_j) H \in \mathbb{G}_1$$を計算する。

$w_j$に関して、

$$q_w(X) = \frac{f_w(X) - f_w(z)}{X - z}$$を計算し、

$$C_{j, q}^w = q_w(a_j) G \in \mathbb{G}_2$$を計算する。

これらはKZG commitmentになっている。

Verifierは次のように検証を行う

1. $h_{com} = hash(T_j)$
2. $x_0 = hash(r, h_{com}, Z)$, $x_{i} = hash(x_{i-1}, Z_L, Z_R, T_{jL}, T_{jR})$を計算する。
3. $Z_i = Z_{iL}^{x_i} Z_{i-1} Z_{iR}^{x_i^{-1}}$, $T_{j, i} = T_{jL, i}^{x_i} T_{i-1} T_{jR, i}^{x_i^{-1}}$ ($j = 1,2$)を再帰的に計算し、最終的に$Z_l$, $T_{j, l}$を得る。
4. $z = hash(x_l, v_j, w_j)$を計算し、$f_v(z)=\prod_{j=0}^{\ell-1}\left(1+x_{\ell-j}^{-1} z^{2^j}\right)$, $f_w(z)=z^n \prod_{j=0}^{\ell-1}\left(1+x_{\ell-j} r^{-2^j} z^{2^j}\right)$を求める。
5. 次のペアリングを検証する

$$
\begin{align}
& Z_{l} = e(A, B')\\
& T_{j, l} = e(A, v_j)e(w_j', B')\\
& e(v_j - f_v(z)H, G) = e(C_{j, q}^v, a_j G - zG)\\
& e(H, w_j - f_w(z)G) = e(a_j H - zH, C_{j, q}^w)
\end{align}
$$

## Verfierのコスト

Verfierは$6\log n$ 回の$\mathbb{G}_t$上のexponentiation,1回の$Z$に関するpairing, 4回の$T_j$に関するpairing, 8回のKZG commitmentに関するpairingが必要である。

このうち、KZG commitmentに関しては、precompile contractで実行可能であるが、一方で$T$と$Z$に関するpairingは$\mathbb{G}_{t}$上での比較であるのでそれが使えない。

Verifierをplonky2で実装した場合、KZG commitmentを外に出した場合`20*log n + 100`分程度の時間が掛かる。

# SIPP

https://eprint.iacr.org/2019/1177.pdf

SIPPの目的は、$\vec{A} \in \mathbb{G}_1^n$, $\vec{B} \in \mathbb{G}_2^n$のペアリング$\vec{A}*\vec{B} := \prod_i 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$を検証し、そうであれば受理する。