SHPLONK

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=∪ik​Si​， 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≥0​ai​[α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∈Si​​fi​(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 G2​points，计算： [ 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=1k​e(γ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