Abstract

本文提出了KZG多项式承诺的一个变体，该变体可以将$d$个多项式的承诺在$d$次幂处揭示，且Verifier的群操作次数与$d$无关，主要方法是在单个点$x$上揭示多个多项式，并通过类似于FFT恒等式的方式来在多个点上揭示同一个多项式来达到这个目的

本文将这个一新变体运用于Plonk，测试表明新变体显著提高了Verifier的时间开销，但是代价是Prover的时间开销会大约增加至原来的3倍（优化版本中Verifier只需要5次标量乘法，Plonk中需要至少16次）

1 Introduction

多项式承诺（Poly. Commitment Scheme，PSC)方案是现代zk-SNARK方案的一个非常关键的组件，尤其是方案中希望实现通用可更新性时，这个组件非常重要，利用PSC，可以迫使Prover响应Verifier的一个有界次数的多项式的查询

比如以太坊上面，zk-SNARK的验证开销与zk-rollup等应用的开销息息相关，而PSC又占据了验证开销中的很大一部分，本文的目的是进一步降低PSC的开销，从而降低zk-SNARK的验证开销

在原始的KZG承诺中，检查多项式$f$在点$x$处的揭示需要两次配对，如果需要检查$t$个多项式$f_0,\dots,f_{t-1}$，则传统方法需要$2t$次配对，一个简单的改进方法时选择一个随机的域元素$\gamma\in \mathbb F$，计算一个大的多项式$f(x)=\sum^{t-1}_{i=0}\gamma^i \cdot f_i(x)$并验证即可，此时验证过程仍然只需要两次配对，但这么做的代价是需要计算$t-1$次标量乘法和加法

$[BDFG20]$给了一个方案，该方案中Verifier群操作的仅取决于多项式的数量，与揭示的点的数量无关，但是Verifier域运算的次数仍然与其相关，只不过数量没这么高而已，如果有一种方法可以在多个点处揭示一个多项式，则利用$[BDFG20]$的方案可以达到我们想要的优化结果

以两个多项式$f_0,f_1$举例，如果我们希望在点$x$处揭示这两个多项式，通过揭示$f(x)=f_0(x)+f_1(x)$的方式可以无需引入标量乘法的操作，但是这个揭示的过程并没有对这两个承诺值进行约束

记$f_0(x)=a,f_1(x)=b$，上述方式揭示的结果就是$f(x)=a+b=c$，但是显然存在某一对值$(a',b')$，也满足$a'+b'=c$，因此需要在$a,b$之间构造某个线性约束

主要思想是快速傅氏变换FFT，构造一个多项式$f(X)=f_0(X^2)+X\cdot f_1(X^2)$，这里我们需要反向利用这个等式，也即从右至左，利用$f_0,f_1$来构造$f$

假设$x$为一平方数，也即$x=z^2$，则我们可以利用这一点来构造$a,b$之间的约束，此时我们可以在点$\{z,-z\}$处揭示$f$，得到下列两个结果

$$ b_0=f(z)=f_0(x)+z\cdot f_1(x)=a+zb\\ b_1=f(-z)=f_0(x)-z\cdot f_1(x)=a-zb $$

从而我们得到了$a,b$之间，这一方法可以扩展到$t$个多项式（本文的方法是考虑一个$t$次幂的点$x=z^t\in \mathbb F$，且满足$t|(|\mathbb F|-1)$）

表1给出了几个方案的效率和证明长度的比较


表2给出了Plonk的原始方案和利用本文方案优化的结果，不难看出本文的方案可以显著减少Veriifer进行群操作的次数，但是代价是SRS的大小和Prover需要的群操作数量会激增

zk-rollup致力于平衡Prover和Verifier之间的计算开销，由于方案的证明通常会由算力较弱的系统生成，证明不会发布到链上，但是证明会由另一个SNARK递归验证，此类情况下可以牺牲Verifier的效率来换取Prover效率

但是最终的证明需要发布到链上，最终证明通常会由一个强算力的系统生成，后续的验证开销也会很大（因为需要全网节点验证），因此本文的方案适用于后者，牺牲Prover的效率来提高Verifier的效率

2 Preliminaries

2.1 Terminology and conventions

  • $\mathbb F$：阶为素数$p$的域
  • $\mathbb F_{<d}[X]$：度小于$d$的单变量多项式集合
  • $f\in \mathbb F_{<d}[X]$：度小于$d$的单变量多项式
  • $\lambda$：安全参数，所有算法的隐式输入
  • $\mathcal O(\lambda)=(\mathbb F,\mathbb G_1,\mathbb G_2,\mathbb G_t,e,g_1,g_2,g_t)$：$\mathcal O$为生成算法，用于生成本文方案中所用到的域和群，以及对应的群生成元和双线性配对
  • $[x]_1,[x]_2$：分别表示$\mathbb G_1,\mathbb G_2$中的乘法，$[x]_1,=x\cdot g_1,[x]_2=x\cdot g_2$
  • $[n]=\{1,\dots,n\}$：表示小于$n$的正整数集合

本文的方案需要访问SRS，SRS可以从URS中导出，SRS的格式如下

$$ \Big \{ [x^i]_1 \Big \}_{a\leq i\leq b},\Big \{ [x^i]_2 \Big \}_{c\leq i\leq d} $$

其中$x\in \mathbb F$，$a,b,c,d$为整数（其绝对值与$poly(\lambda)$相关）

2.2 Notation, definitions and operations on vectors and polynomials

介绍一下向量和多项式承诺的一些符号记法和定义

  • $[<t]$：表示非负整数集合$\{0,\dots,t-1\}$，在求和符号中用记法$i<t$表示$\sum_{i\in [<t]}$
  • $D^{(i)}$：$D$为某一域，$i$表示嵌套的层数，比如$D^{(1)}$表示域$D$上的向量集合，$D^{(2)}=(D^{(1)})^{(1)}$表示向量的向量构成的集合，依此类推
  • $\bar S\in \mathbb F^{(1)}$：一杠表示元素来自于$\mathbb F^{(1)}$，同理，两杠和三杠$\overset{=}{S} ,\overset{\equiv}{S}$分别表示来自$\mathbb F^{(2)},\mathbb F^{(3)}$
  • $\bar f\in D^t$：表示长度为$t$的向量，元素$f_i\in D,0\leq i<t$，同理$\overset{=}{f}\in D^{(2)}$表示向量的向量，每个向量都来自于$D^{(1)}$
  • $\bar f(x)=(f_0(x),\dots,f_{t-1}(x))$，其中$\bar f\in \mathbb F[X]^t$为多项式向量，$X=x\in \mathbb F$
  • $\bar f(\bar Z)\in \mathbb F^{(2)}$：对于向量$\bar f$确定的多项式和一个点集向量$\bar Z\in \mathbb F^l$，$\bar f(\bar Z)=(\bar f(Z_j))_{j<l}$，大小为$t\cdot l$
  • $\overset{=}{f}(\overset{=}{Z} )\in\mathbb F^{(3)}$：和上面定义类似，用点集向量$\overset{=}{Z}$给向量多项式向量$\overset{=}{f}$赋值

2.3 Polynomial Commitment schemes

多项式承诺方案和$[GWC19,BDFG20]$类似，但是需要做一些小的修改来实现本文的优化

  • 本文允许承诺阶段输入一个多项式向量，而非只输入一个多项式，并允许揭示的点集仅取决于被承诺的多项式的向量
  • 本文允许用一个子集$\mathbf{S} \subset \mathbb F$进行参数化，揭示阶段只需要在集合$\mathbf{S}$中完成

这里给出一个定义

Def 1：给定有限正整数集合$T$及其子集$\mathbf{S} \subset \mathbb F$，定义$(T,\mathbf S)$多项式承诺方案为一个算法三元组$(gen,com,open)$，如下

  • $srs\larr gen(d)$：参数生成算法，给定正整数$d$，输出算法所使用的SRS
  • $cm \larr com(t,\bar f,srs)$：承诺算法，给定$t\in T$，多项式向量$\bar f$，输出承诺值$cm$​
  • $open$：揭示算法为Prover和Verifier之间的公共掷币协议，Prover输入为$\overset {=}{f}\in (\mathbb F_{<d}[X])^{(2)}$，双方的公共输入如下：$srs=gen(d)$（对应于正整数$d$），正整数$r$和承诺值$\overline {cm}\in \mathbb G^r_1$（对应于$\{\bar f_i\}$的承诺），向量$\bar t\in T^r$（对应于$\{\bar f_i\}$的长度），$\overset{=}{Z}\in \mathbf S^{(2)}$和$\overset{\equiv}{S}\in \mathbb F^{(3)}$（对应于$\overset{=}{f}(\overset{=}{Z} )$的值）

方案满足完备性和代数群模型中的知识合理性

2.4 shplonk

引用一下$[BDFG20]$中的承诺方案shplonk，承诺过程与KZG相同，但是Verifier的群操作次数不会随着揭示的点的数量增加而增加

根据$[BDFG20]$中的引理4.1，可以得到下面这个引理

Lemma 1：存在一个$\{1,\mathbb F\}$多项式承诺方案$S_{shplonk}=(gen_{shplonk},com_{shplonk},open_{shplonk})$如下

  • $gen_{shplonk}$算法随机选择$x\in \mathbb F$，输出$([1]_1,[x]_1,\dots,[x^{d-1}]_1)$
  • 对于给定的整数$n\leq d$和多项式$f\in \mathbb F_{<n}[X]$，$com_{shplonk}$算法需要$n$次$\mathbb G_1$中的标量乘法
  • 记$n=\max_i[def(f_i)],k=|\bar f|$，在$open_{shplonk}$算法中，Prover需要向Verifier发送2个$\mathbb G_1$元素，Prover需要至多$2n+1$次$\mathbb G_1$中的标量乘法，Veriifer需要$k+2$次$\mathbb G_1$中的标量乘法和两次配对

该引理表明，可以通过除以一个常量$Z_{T\backslash S_1(z)}$来节约一次Verifier的标量乘法（$[BDFG20]$需要$k+3$次），优化方式如下图所示

注意到第5步的最后一个方程中，$cm_i$的系数为1，从而可以节约一次标量乘法，由于过程中引入的为常数，因此不会改变原有承诺方案的知识合理性

3 FFT-like operations on vectors and polynomials

接下来介绍一下与FFT操作相关的记法和符号

首先是两个算法$combine_t(\bar f)$和$decomposet_t(g)$，给定$t$个多项式$\bar f\in \mathbb F[X]^t$，combine算法将其组合成一个大的多项式，也即算法计算一个多项式$g(X)$如下

$$ g(X)=\sum_{i<t}X^i\cdot f_i(X^t) $$

由于$\bar f$中的每个多项式的度均小于$d$，因此组合后的多项式$g$的度小于$dt$

解组合算法将$g$恢复为$t$个多项式$\bar f\in \mathbb F[X]^t$，也即组合和解组合算法互为逆运算

之后是关于根和幂的一些记法，记$p=|\mathbb F|$表示域的大小，对于正整数$t|(p-1)$，令$\omega_t\in \mathbb F$表示$t$次根，也即$\omega^t_t=1,\omega^i_t\neq 1(i\neq t)$

对于$t$次幂，令$x,z\in \mathbb F$，满足$x=z^t,z^i\neq x(i<t)$，然后记一个向量$roots_t(x)=(z\omega^i_t)_{i<t}$

最后是关于向量和多项式的一些记法：对于向量$v\in \mathbb F^t$和点$x\in \mathbb F$，多项式求值表示为$v(x)=\sum_i v_i\cdot x^i$，多项式在点集$S\in \mathbb F^{(1)}$上的求值表示为$v(S)=(v(x))_{x\in S}$

然后接下来介绍一个引理

Lemma 2：对于给定的$x\in \mathbb F ,\bar S\in \mathbb F,\bar f\in \mathbb F[X]^t$，定义$\bar Z=roots_t(x),g=combine_t(\bar f) ,\bar S'=\bar S(\bar Z)$，则当且仅当$g(\bar Z)=\bar S'$时，有$\bar f(x)=\bar S$

证明如下：对于$z\in \bar Z$，不难得出

$$ g(z)=\sum_{i<t}z^i\cdot f_i(z^t)=\sum_{i<t}z^i\cdot f_i(x)=z\cdot \bar f(x) $$

因此有$g(\bar Z)=\bar S'$

根据SZ定理，度数小于$t$的两个不同的多项式至多在$t-1$个点上相等，因此有$\bar f(x)=\bar S$，引理得证

3.1The new scheme

选择一个正常数$A$，满足$A|(p-1)$，记集合$T=\{0<t\leq A| t|A\}$，集合$\mathbf S$表示域$\mathbb F$中$A$的幂，$(T,\mathbf S)$多项式承诺方案如下

$gen(d)$：随机选择$x\in \mathbb F$，生成$srs=([1]_1,[x]_1,\dots,[x^{A(d-1)}]_1,[1]_2,[x]_2)$

$com(t,\bar f,srs)$：给定$t\in T,\bar f\in (\mathbb F_{<d}[X])^t$，利用组合算法计算多项式$g$并输出承诺值$[g(x)]_1$

$open$：首先介绍单承诺和在单点揭示承诺的情况$open(t,cm,x,\bar S,\bar f)$

  1. Prover计算$g=combine_t(\bar f)$（实际上承诺阶段已经计算过了，只需要从内存里面读出来就行）
  2. Prover和Verifier计算$\bar Z'=roots_t(x),\bar S'=\bar S(\bar Z')$
  3. Prover和Verifier调用$open_{shplonk}(1,cm,\bar Z',\bar S',g)$进行验证

之后将其扩展到每个求值点$open(\bar t,\overline{cm},\overset{=}{Z},\overset{\equiv }{S},\bar f)$

  1. Prover对所有的$i<r$，计算$g_i=combine_{t_i}(\bar f_i)$，记$\bar g=(g_i)_{i<r}$
  2. Prover和Verifier计算$\overset{=}{Z'}$和$\overset{=}{S'}$，如下
  3. Prover和Verifier调用$open_{shplonk}(1^r,\overline{cm},\overset{=}{Z'},\overset{=}{S'},\bar g)$进行验证

对于方案的知识合理性分析如下，首先分析一下单点揭示的情况，此时敌手$\mathcal A$承诺方案输出一个整数$t$，$\mathbb G_1$中的承诺元素$cm$

$$ cm=\Big[ \sum_{i<A(d-1)} a_i\cdot x^i \Big ]_1 $$

令$g(X)=\sum_{i<A(d-1)}a_i\cdot X^i$，定义一个抽取器$\mathcal E$，输出$\bar f=decompose_t(g)$，由于$[BDFG20]$中知识合理性用到的的抽取器$\mathcal E_{shplonk}$在敌手给定$(1,cm,\{a_i\})$时会输出多项式$g$，因此本文的知识合理性分析需要证明敌手赢得知识合理性游戏的概率为$nelg(\lambda)$

首先为$open_{shplonk}$构造一个敌手$\mathcal A'$，其执行下列步骤

  1. $\mathcal A'$运行$open$的知识合理性游戏中的敌手$\mathcal A$，模拟对应的Verifier和抽取器E
  2. 当$\mathcal A$输出$(t,cm,\{a_i\})$时，$\mathcal A'$输出$(1,cm,\{a_i\})$
  3. 根据引理1，此时$open_{shplonk}$知识合理性游戏中的抽取器$\mathcal E_{shplonk}$此时会输出$g$，而$open$的知识合理性游戏中的抽取器$\mathcal E$会输出$\bar f=decompose_t(g)$
  4. 若此时$\mathcal A$输出了$(x,\bar S)$，则$\mathcal A'$输出$(\bar Z',\bar S')=(roots_t(x),S(Z'))$
  5. 最后，$\mathcal A'$在$open_{shplonk}$知识合理性游戏中的行为与$\mathcal A$在$open$中的行为一致

根据$open_{shplonk}$知识合理性游戏的定义，$\mathcal A'$获胜的条件为

  1. $V_{shplonk}$接受
  2. $g(\bar S')\neq \bar Z'$

根据引理2，这两个获胜条件等价于

  1. $V$接受
  2. 对于$\mathcal E$输出的$\bar f$，有$f(x)\neq \bar Z$

因此$\mathcal A,\mathcal A'$在各自的安全游戏中获胜的概率是一致的，故知识合理性可以归结于$open_{shplonk}$的知识合理性

多个承诺和评估点的分析类似，不再展开

这里原文给了一个定理，如下

References

$[1]$ Ariel Gabizon, Zachary J. Williamson:fflonk: a Fast-Fourier inspired verifier efficient version of PlonK. IACR Cryptol. ePrint Arch. 2021: 1167 (2021)