在Plonk协议中，多项式承诺是非常重要的一个环节，协议中的多项式承诺实现了多个多项式在两个点上的open。但是在实际的应用场景下，有可能会出现需要多个多项式在多个不同点处open的场景，如果能通过改进多项式承诺协议来使得plonk支持多个多项式在不同的子集点处的open。
若 $ z \in S $，那么 $Z_S(x) = \prod_{z \in S} (X-z)$。
假设有一个数据集$T = {z_1, z_2, …, z_t}$，并且它的子集$S_1,S_2,…,S_k \subset T$。如果有k个多项式$f_1(x), f_2(x),…,f_k(x)$，它们的承诺分别为$cm_1, cm_2,…,cm_k$，要分别在$S_1,S_2,…,S_k $上open。
首先若要使用KZG10对一个多项式做验证的话，那么
prover计算多项式 $$ h(x) = \frac{f_i(x) - r_i(x)}{Z_{S_i}(x)} $$
其中$r_i(x)$ 是一个$|s_i|$ 阶的多项式，且满足再$f_i(x) = r_i(x), x \in S_i$。
再使用srs参数计算证明$W =[h(x)]_1 = g^{h(x)}$，发送给verifier。
Verifier 拿到证明W后进行验证，这里需要两次pairing运算。
$$ e(cm_i - [r_i(x)]_1, g_2) = e(W,g_2 ^ {k}) $$
其中 $k = Z_{S_i}(x)$
如果要一次性得对这k个多项式进行验证，只需要引入一个随机数
verifier 生成一个随机数$\gamma$，并发送给prover
prover 拿着随机数将k组多项式的证明计算 $$ h_i(x) = \frac{f_i(x) - r_i(x)}{Z_{S_i}(x)} $$
再使用srs参数计算证明$W_i =[h(x)_i]_1 = g^{h_i(x)}$，发送给verifier。
verifier拿到证明W后进行验证
$ \prod_{i \in [k]} e(\gamma^{i-1} (cm_i-[r_i(x)]_1), g_2) $
$ = \prod_{i \in [k]}e(W_i,g_2^{Z_{S_i}(x)})$
这个合并尚还不能降低计算量，需要2k次pairing运算。SHPlonk 中在验证步骤做了一个优化
首先verifier先计算一组
$$ Z_i = g_2^{Z_{T/S_i}(x)},i \in [k] $$
其中$Z_{T/S_i}(x) = \frac{Z_T(x)}{Z_{S_i(x)}}$
prover 拿着随机数将k组多项式的证明计算合并起来
$$ h(x) = \sum_{i \in [k]}\gamma^{i-1} \cdot \frac{f_i(x) - r_i(x)}{Z_{S_i}(x)} \ = \sum_{i \in [k]}\gamma^{i-1} \cdot \frac{(f_i(x) - r_i(x)) \cdot Z_{T/S_i}(x)}{Z_{T}(x)} \ = \frac{\sum_{i \in [k]}\gamma^{i-1} \cdot(f_i(x) - r_i(x)) \cdot Z_{T/S_i}(x)}{Z_{T}(x)} $$
再使用srs参数计算证明$W =[h(x)]_1 = g^{h(x)}$，发送给verifier。
那么验证步骤就被改造为
$$ \prod_{i \in [k]} e(\gamma^{i-1} (cm_i-[r_i(x)]_1), Z_i) =e(W,g_2^{Z_T(x)}) $$
这样pairing运算的数量就降低到了k+1次。
这里右侧已经不能合并了，未来进一步优化计算量
首先令 $$ f_Z(X) = \sum_{i \in [k]}\gamma^{i-1} \cdot Z_{T/S_i}(X)\cdot(f_i(X) - r_i(X)) $$ 那么 $$ h(X) = \frac{f_Z(X)}{Z_T(X)} $$ 再使用srs参数计算证明$W =[h(x)]_1 = g^{h(x)}$，发送给verifier。
verifier 产生一个随机数$z$，并发送给prover。
再继续变换多项式的形式 $$ L(x) = f_Z(X) - h(X)\cdot Z_T(z) $$ 其中 $$ f_Z(X) = \sum_{i \in [k]}\gamma^{i-1} \cdot Z_{T/S_i}(z)\cdot(f_i(X) - r_i(z)) $$ 显然$L(z) = 0$。所以L(x)必然能被$(x-z)$整除。
所以prover可以继续构造证明 $$ h’(x) = \frac{L(x)}{x-z} $$ 再使用srs参数计算证明$W’ =[h’(x)]_1 = g^{h’(x)}$，发送给verifier。这里就相当于把再S个点处opening的问题转换到了在一个点open的问题上了。
Verifier 首先去计算
$F = [f_Z(x)]1 = \sum_{i \in [k]}\gamma^{i-1} \cdot Z_{T/S_i(z)}(cm_i - [r_i(z)]_1) - Z_T(z)\cdot W$
再继续验证 $$ e(F,[1]_2) = e(W’,[x-z]_2) $$ 只剩下两个pairing 和k+1次的椭圆曲线上的乘法运算，这远远小于k+1次的计算消耗。
原本的方案中，右侧的pairing已经不能合并了，所以这里优化的关键就是将$Z_{T/S}(x)$ 和 $Z_{Y}(x)$ 的计算变换成了在一个已知点处的计算，即$Z_{T/S}(z)$ 和 $Z_{Y}(z)$，因为$Z_{T/S}(x)$ 和 $Z_{Y}(x)$ 多项式是公开的，z是公开的，那么计算就可以只能在有限域上进行了，而不必管srs，因此原本pairing运算中在g2上算的这两项都可以直接乘到g1上了，这样也就合并了原来的多个pairing。
fflonk也是一种新的优化方案，它在SHPlonk的基础之上设计的优化方案，它继续沿用了SHPlonk的验证步骤，并结合了一种新的类似FFT运算的方法。fflonk的验证步骤中仅需要3次椭圆曲线上的运算，及2次pairing，与SHPlonk相比，又进一步优化了计算步骤。
