1. 引言

所谓“SHPLONK”，是指：
“Kate” KZG10 scheme 的扩展版，实现了batch polynomial commitment scheme。

具体对应为：
Boneh等人2020年论文《Efficient polynomial commitment schemes for multiple points and polynomials》。

详细也可参见博客：
Efficient polynomial commitment schemes for multiple points and polynomials学习笔记

SHPLONK的主要作用是：
仅使用1个单独的group element，可证明多个多项式 { f i ( X ) ∈ F q : i ∈ [ k ] } \{f_i(X)\in\mathbb{F}_q: i\in [k]\} {fi(X)∈Fq:i∈[k]} evaluated over a set of points S i ⊂ F q S_i\subset \mathbb{F}_q Si⊂Fq。

即允许每个多项式有自己的‘evaluation set’。

开源代码实现见：

https://github.com/0xPolygonHermez/shplonkjs（Javascript）【Polygon zkEVM团队将SHPLONK多项式承诺方案与Fflonk协议集合使用，也可将SHPLONK多项式承诺方案独立使用。详情可参看博客 fflonK: a Fast-Fourier inspired verifier efficient version of PlonK。】

1.1 由symmetric pairing到asymmetric pairing

在Kate commitment 中使用的是symmetric pairing operation：
e : G × G → G T e:\mathbb{G}\times\mathbb{G}\rightarrow \mathbb{G}_T e:G×G→GT

而asymmetric pairing 格式为：
e : G 1 × G 2 → G T e:\mathbb{G}_1\times\mathbb{G}_2\rightarrow\mathbb{G}_T e:G1×G2→GT
其中 G 1 ≠ G 2 \mathbb{G}_1\neq\mathbb{G}_2 G1=G2，两者都为elliptic curve groups，且二者通常有相互关系。

1.2 将exponential表示为additive

g 1 ∈ G 1 g_1\in\mathbb{G}_1 g1∈G1为generator point，其5次方表示为 g 1 5 g_1^5 g15，将其转换为additive表示为： [ 5 ] 1 [5]_1 [5]1，这种表示方法由Jens Groth在其Groth16论文中提出。
同理，对于generator g 2 ∈ G 2 g_2\in\mathbb{G}_2 g2∈G2，其3次方表示为 [ 3 ] 2 [3]_2 [3]2，而不是 g 2 3 g_2^3 g23。

2. 构建SHPLONK

主要内容有：

k k k个多项式： { f i ( X ) ∈ F q : i ∈ [ k ] } \{f_i(X)\in\mathbb{F}_q: i\in [k]\} {fi(X)∈Fq:i∈[k]}
k k k个evaluation point sets： { S i ⊂ F q : i ∈ [ k ] } \{S_i\subset \mathbb{F}_q: i\in[k]\} {Si⊂Fq:i∈[k]}。对于每个 i i i， f i f_i fi将evaluate over the points in S i S_i Si。（ S i S_i Si中通常有1个或多个points）
将所有感兴趣的points收集表示为： T = ∪ i k S i T=\cup_i^k S_i T=∪ikSi， T T T为 F q \mathbb{F}_q Fq的一个tiny subset，同时可表示为 T = { t 1 , ⋯ , t m } T=\{t_1,\cdots,t_m\} T={t1,⋯,tm}。
构建 k k k个多项式： { r i ( X ) ∈ F < ∣ S i ∣ : i ∈ [ k ] } \{r_i(X)\in\mathbb{F}_{ t >>t >>t， t t t为the maximum number of evaluation points， S R S SRS SRS的格式为：
< [ 1 ] 1 , [ α ] 1 , [ α 2 ] 1 , ⋯ , [ α d ] 1 , [ 1 ] 2 , [ α ] 2 , [ α 2 ] 2 , ⋯ , [ α t ] 2 >

2.1 commit

对 k k k个多项式分别进行commit：
C i = [ f i ( α ) ] 1 = ∑ j ≥ 0 a i [ α i ] 1 C_i=[f_i(\alpha)]_1=\sum_{j\geq 0}a_i[\alpha^i]_1 Ci=[fi(α)]1=∑j≥0ai[αi]1
也可表示为：
C i = g 1 f i ( α ) = ∏ j ≥ 0 ( g α i ) a i C_i=g_1^{f_i(\alpha)}=\prod_{j\geq 0}(g^{\alpha^i})^{a_i} Ci=g1fi(α)=∏j≥0(gαi)ai
该commitment具有加法同态属性。

k k k个多项式的commitment表示为：
C o m = < C 1 , ⋯ , C k > Com= Com=

以一个多项式 f 1 ( X ) f_1(X) f1(X)为例：
与Kate commitment将evaluate at s 1 s_1 s1并证明可整除 X − s 1 X-s_1 X−s1的表示方法异曲同工，SHPLONK将 f 1 ( X ) f_1(X) f1(X)的evaluation set表示为 S 1 = { s 1 } S_1=\{s_1\} S1={s1}，引入多项式 r 1 ( X ) = f 1 ( s 1 ) r_1(X)=f_1(s_1) r1(X)=f1(s1)，因为仅固定了一个点，该多项式为常量多项式。若固定两个点，则该多项式为线性多项式。
若evaluation set为 S 1 = { s 1 , s 2 } S_1=\{s_1,s_2\} S1={s1,s2}，则 r 1 ( X ) r_1(X) r1(X)的degree为1，且有 f 1 ( X ) − r 1 ( X ) f_1(X)-r_1(X) f1(X)−r1(X)可整除 ( X − s 1 ) ( X − s 2 ) (X-s_1)(X-s_2) (X−s1)(X−s2)。

扩展为：
1）为每个 f i ( X ) f_i(X) fi(X)多项式引入相应的 r i ( X ) r_i(X) ri(X)多项式。
同时， r i ( X ) r_i(X) ri(X)基于Lagrange多项式构建，（Lagrange多项式为ugly-to-make, lovely-to-use），使得：
L s , S i ( X ) = { 1 : X = s 0 : X ∈ S i ∖ { s } L_{s,S_i}(X)=\begin{cases} 1 & :X=s \\ 0 & :X\in S_i\setminus \{s\} \end{cases} Ls,Si(X)={10:X=s:X∈Si∖{s}
从而将 r i ( X ) r_i(X) ri(X)表示为：
r i ( X ) = ∑ s ∈ S i f i ( s ) ⋅ L s , S i ( X ) r_i(X)=\sum_{s\in S_i}f_i(s)\cdot L_{s,S_i}(X) ri(X)=∑s∈Sifi(s)⋅Ls,Si(X)

2）将所有的多项式 f i ( X ) f_i(X) fi(X)合并为一个多项式 F ( X ) F(X) F(X)：
F ( X ) = ∑ i = 1 k γ i − 1 ⋅ f i ( X ) F(X)=\sum_{i=1}^k\gamma^{i-1}\cdot f_i(X) F(X)=∑i=1kγi−1⋅fi(X)
其中 γ \gamma γ值对Prover和Verifier双方均可知，同时，Prover无法控制 γ \gamma γ值。

2.2 prove

Prover和Verifier均很容易计算：
Z S i ( X ) = ∏ s ∈ S i ( X − s ) Z_{S_i}(X)=\prod_{s\in S_i}(X-s) ZSi(X)=∏s∈Si(X−s)

Prover需计算quotient多项式：
h ( X ) = ∑ i = 1 k γ i − 1 ⋅ f i ( X ) − r i ( X ) Z S i ( X ) h(X)=\sum_{i=1}^{k}\gamma^{i-1}\cdot \frac{f_i(X)-r_i(X)}{Z_{S_i}(X)} h(X)=∑i=1kγi−1⋅ZSi(X)fi(X)−ri(X)
对应每个 f i ( X ) f_i(X) fi(X)的quotient多项式 h i ( X ) h_i(X) hi(X)为：
h i ( X ) = f i ( X ) − r i ( X ) Z S i ( X ) h_i(X)=\frac{f_i(X)-r_i(X)}{Z_{S_i}(X)} hi(X)=ZSi(X)fi(X)−ri(X)

从而有an evaluation proof for all f i ( X ) f_i(X) fi(X) over their respective evaluation sets S i S_i Si表示为：
W = [ h ( α ) ] 1 = ∑ i = 1 k γ i − 1 ⋅ W i W=[h(\alpha)]_1=\sum_{i=1}^{k}\gamma^{i-1}\cdot W_i W=[h(α)]1=∑i=1kγi−1⋅Wi

2.3 verify

Verifier为每个set S i ⊂ T S_i\subset T Si⊂T（ T T T为所有 S i S_i Si set的集合）计算：
Z T ∖ S i ( X ) Z_{T\setminus S_i}(X) ZT∖Si(X)
T T T集合的个数表示为 t = ∣ T ∣ t=|T| t=∣T∣，可根据Reference String中的 G 2 \mathbb{G}_2 G2points，计算：
[ Z T ∖ S i ( X ) ] 2 [Z_{T\setminus S_i}(X)]_2 [ZT∖Si(X)]2

最终，Verifier仅需验证如下等式成立即可：
∏ i = 1 k e ( γ i − 1 ⋅ ( C i − [ r i ( α ) ] 1 ) , [ Z T ∖ S i ( α ) ] 2 ) = e ( W , [ Z T ( α ) ] 2 ) \prod_{i=1}^{k}e(\gamma^{i-1}\cdot (C_i-[r_i(\alpha)]_1), [Z_{T\setminus S_i(\alpha)}]_2)=e(W,[Z_T(\alpha)]_2) ∏i=1ke(γi−1⋅(Ci−[ri(α)]1),[ZT∖Si(α)]2)=e(W,[ZT(α)]2)
其中， W = ∑ i = 1 k γ i − 1 ⋅ W i W=\sum_{i=1}^{k}\gamma^{i-1}\cdot W_i W=∑i=1kγi−1⋅Wi。

相比于单独对每个 f i ( X ) f_i(X) fi(X)进行验证需要 2 k 2k 2k次pairing计算，此时仅需 k + 1 k+1 k+1次pairing计算。

3. SHPLONK应用

在 ZCash 的 Halo2算法之multipoint opening 中借鉴了SHPLONK算法。

参考资料

[1] tompocock的hackmd shplonk笔记
[2] tompocock的hackmd Kate Commitments: A Primer
[3] Boneh等人2020年论文 Efficient polynomial commitment schemes for multiple points and polynomials
[4] Aztec以及Geometry创始人 Walpo 2021年 hackmdSHPLONK

SHPLONK