Abstract

Flashproofs是一种具有高效诚实Verifier的零知识论证，在基于DLOG假设的初始设置具有透明性

Flashproofs的范围证明的可做到gas-efficient（费用高效的）

Flashproofs通信开销为$O(N^{\frac{2}{3}})$，证明需要差不多亚线性次数的群幂，验证只需要$O(N^{\frac{2}{3}})$次群幂运算（证明范围为$[0, 2^N-1]$，其中$N$表示待证明范围的比特长度）

在支持智能合约的区块链平台上的机密交易，验证32（64）bit的Flashproofs的范围论证需要237K（318K）GAS，32bit的GAS开销和目前最高效的zkSNARK（EuroCrypto16）中差不多（多了17K）

其次本文提出了一个基于Bayer Groth技术的多项式求值论证，并给出了两个零知识论证，这两个论证对于阶数较低的多项式（$D \in [3, 2^9]$）和阶数较高的多项式（$D > 2^9$）都进行了优化，

本文提出的论证在整体效率上有许多优化，证明过程中的群幂次数从$8\log D$下降到$3(\log D+\sqrt{\log D} )$，验证的群幂次数和通信开销从从$7\log D$减少到$(\log D + 3\sqrt{\log D})$

本文的论证实例化了DLOG设置中无需可信设置的成员和非成员关系的最有效的通信开销

更重要的是，当多个论证具有相同阶数的多项式，且输入被聚合时，本文的通信与验证开销可从$O(\log D)$降低至$O(\sqrt{\log D})$

1 Introduction

本文重点讨论DLOG设置中两种特定语言的零知识证明：范围论证和多项式求值论证，范围证明旨在证明承诺值在特定范围内，一些零知识范围证明已应用于区块链平台上的机密交易（CT）

现有的CT零知识证明方案存在下列三个缺点

  • Trusted Setup：部分zk-SNARK方案需要可信设置，这要求部分可信的参与方使用他们各自的秘密参数来生成一个公共的参数，同时需要确保该秘密参数在不泄露的情况下被销毁
    可信设置实际上会一定程度上影响安全性，且与分布式设置冲突，这会导致恶意的Prover可能会创建或留下陷门，从而利用陷门来伪造虚假的证明
  • Imbalanced Overhead：最近的一些ZKP方案试图通过透明化来去掉可信设置，但是实现透明化会导致各种不平衡的开销（要么计算开销大，要么通信复杂度高）
    这些方案的效率问题违背了区块链的可扩展性（区块链需要在尽可能短的时间内处理事务）

举个例子，Buletproof的证明大小可以达到对数阶，但是在Prover和Verifier双方均需要线性次数的群幂，部分zk-SNARK的Verifier复杂度为对数多项式阶，但是证明大小很大，达到了45KB

  • Trade-off with Soundness：一种诸如$[CKLR21]$新的范围证明，其基于DLOG设置中的有界整数承诺，可以进一步降低计算复杂度和通信开销
    但是此类方案必须在给定的群内对范围大小和合理性误差之间进行权衡，使得该方案难以具有普适性

使用RSA或类群可以通过消除整数大小的限制来解决此类权衡问题，但是这一过程又引入了可信设置，或者需要在相当大的群上使用不同的安全假设

另一方面，多项式求值证明（polynomial evaluation proofs，PEP）被设计以用于证明两个承诺值$x,y$关于某个公共多项式$y=P(x;D)$的关系，其中$D$表示该多项式的度

PEP可作为构建ZKP的成员关系和非成员关系的构建块

  • 成员关系：例如多项式函数$y=P(x;D)=0$可用于构建一个成员关系证明，以证明承诺值$x$属于某个公共集合$X$，$X$中的值均为该多项式的根
  • 非成员关系：需要证明$y\neq 0$，此时Prover可以承诺一个值$z=y^{-1}$，并通过惩罚证明来声明$z\cdot y=1$

成员和非成员关系证明有广泛的应用，例如匿名凭证、群签名、白名单和黑名单，Bayer和Groth提出了基于DLOG假设的多项式求值论证，该方案Verifier需要的群幂次数为$O(\log D)$次，通信开销为$O(\log D)$，不过该方案在处理度很高的多项式时，计算开销和通信开销仍然很大

为了解决上述问题，本文提出了一种高效的特殊诚实Verifer，称为Flashproof，其范围和多项式求值的零知识论证具有透明性

Flashproof为Prover和Verifier之间的三轮公共掷币协议，Prover在第一轮中向Verifier发送消息，Verifier用一个均匀随机的挑战作为答复，然后Prover根据挑战进行响应

Flashproof在基于ECC群的经典DLOG假设下具有完美完备性，计算证据扩展仿真和完美特殊诚实Verifier零知识性

本文的方案遵循透明设置，无需具有ECC群的可信设置

此外本文的论证可利用FS变换转换为非交互式的，其中Prover需要利用CRHF生成随机挑战

Range Proof

图1给出了Flashproof的范围证明需要的群幂运算的次数

表1和表2展示了本文方案和Bulletproof的对比，对于$N=64$的情况，本文可以分别将Prover和Verifier效率提高6.6倍和11.4倍，同时只需要增加50%的通信开销

Table 1
Table 1

其中$F(N^{\frac{1}{3}})$是一个与$N^{\frac{1}{3}}$有关的常数，具体看后续的章节

Table 2
Table 2

观察表2，可以发现在$N<22$时，本文的方案更加简洁

此外，本文的方案对$N$更敏感（sensitive），这意味着可以在不同的场景中实现更细粒度的性能和更好的灵活性

DLOG设置中的另一个范围证明为$[CKLR21]$，该方案利用勒让德三平方定理，通过有界整数承诺方案来打到常数级的计算和通信的开销，但是该方案在部分群中需要在合理性误差和范围大小之间权衡，由于CT通常需要严格的安全要求，这意味需要可忽略的合理性误差，因此该方案的范围大小不可能做到太大

CKLR21在智能合约上存在一些合理性误差问题，导致CT平台必须增加迭代次数或使用一个更大的群来达到可忽略的合理性误差（后者的代价基本上相当于重做整个系统，因此只能选择前者），而且两种方案都会增加计算和通信开销

Polynomial Evaluation Arguments

多项式求值论证是基于$[BG13]$提出的技术，本文提出了两种零知识论证，可用于对多项式$y=P(x;D)$求值，本文的论证在$D\in[3,2^9]$和$D>2^9$的情况下都进行了优化

表3展示了DLOG中透明设置的各个方案的多项式求值论证的效率（表中的$N$表示多项式的阶，若$N$不为2的幂，则$\log D$向上取整）

Table 3
Table 3

相比于$[BG13]$，本文的方案有显著的优化

2 Perliminaries

  • $\lambda$：安全参数
  • PPT：概率多项式时间
  • $\mathbb G$：阶为素数$p$的循环群
  • $\Z_p$：模$p$环
  • $\Z_p^*=\Z_p\backslash \{0\}$：乘法群
  • $g,h\larr \mathbb G$
  • $\boldsymbol g\larr \mathbb G^n$
  • $x\larr \Z_p^*$

2.1 Homomorphic Commitment Schemes

满足同态的承诺方案记为$(\mathcal G,Cm)$，其中$\mathcal G$为初始化算法，用于生成承诺密钥$ck$，$Cm_{ck}:M_{ck}\times R_{ck}\rarr C_{ck}$为承诺算法，将消息空间$M_{ck}$内的消息和随机性$R_{ck}$映射至承诺空间$C_{ck}$

同态承诺方案具有下列性质

$$ Cm_{ck}(m_0;r_0)\cdot Cm_{ck}(m_1;r_1)=Cm_{ck}(m_0+m_1;r_0+r_1)\\Cm_{ck}(m_0;r_0)^{m_1}=Cm_{ck}(m_0\cdot m_1;r_0\cdot m_1) $$

同态承诺方案同样满足隐藏性（Hiding）和绑定性（Binding）

此外，本文还需要两个组件，为Pedersen承诺与Pedersen向量承诺

2.2 Zero-Knowledge Arguments of Knowledge

基于DLOG假设，Flashproof为公共掷币诚实Verifier的知识论证

ZKP论证为一个算法三元组$(G,P,V)$，其中$G$为初始化算法，返回CRS串$\sigma$

一个CRS相关语言（CRS-Dependent Lang）定义为$L_\sigma=\{u|\exist w:(\sigma,u,w)\in R\}$，其中$u$为statement，$w$为witness

若算法三元组满足完美完备性和计算证据扩展仿真，则称为知识论证

3 Range Arguments

3.1 Overview of Bit-Decomposition Apprach

比特分解是构造范围证明的一种普遍方法，关键点在于如何找到一种有效的方法来证明承诺值可以以二进制的形式表示

Bulletproof采用了基于内积论证来构造了一种比特分解的变体，Bulletproof中的做法如下（具体的方式可以看Bulletproof那篇博客$[2]$）

Prover首先准备向量承诺，分别为值为$y$的向量$\boldsymbol b$和另一个向量$\boldsymbol a=\boldsymbol b-\boldsymbol 1^N$，之后Prover构造下列三个约束

$$ \begin{aligned} \lang \boldsymbol b,\boldsymbol 2^N\rang=y\\ \lang\boldsymbol b-\boldsymbol 1^N-\boldsymbol a,\boldsymbol r\rang=0\\ \lang\boldsymbol b,\boldsymbol a\circ \boldsymbol r\rang=0 \end{aligned} $$

Prover通过$O(\log N)$次递归即可得到该承诺，尽管其通信复杂度可达到$O(\log N)$，但是存在两个问题

  • 计算开销很大，证明和验证均需要$O(N)$次群幂
  • 因为过程是递归计算的，很大程度上限制了算法的并行性

3.2 Our Techniques

为了解决上述两个问题，本文设计了一种新的比特分解方法，只需要三轮，优点在于计算非常轻量级，且无需配对

与Bulletproof相比，本文的论证在证明和验证中涉及的群幂次数要少得多，且还可以通过并行化来加速证明生成

本节先讨论一下Flashproof的核心技术，完整协议在第6.1节中给出

首先看一下Flashproof如何构造范围论证

  1. 给定一个承诺$c_y=g^yh^{r_y}$，将承诺值$y=\sum^{N-1}_{i=0}2^ib_i$表示为范围$[0,2^N-1]$中的一个序列$w=(w_0,...w_{N-1})$，其中$w_i=2^ib_i$
    然后将$w$折叠成一个$L$行$K$列的矩阵（如果$N$为素数，则需要添加$\gamma$个额外比特，满足$N+\gamma =L\cdot K$），矩阵如下列式2所示
  2. 对于矩阵中的每个元素，证明其系数$w_{lK+k}$为$0$或$2^{lK+k}$
  3. 将矩阵按列展开为一维向量，并证明$y$等于$K$个值的和，也即对于第$k$列的$L$个系数和$s_k=\sum^{L-1}_{l=0}w_{lK+k}$，证明$y=\sum^{K-1}_{k=0}s_k$

$$ \begin{pmatrix} 2^0& ... & 2^{K-1}b_{K-1} \\ 2^K& ...& 2^{K+K-1}b_{K+K-1}\\ \vdots& \ddots &\vdots \\ 2^{(L-1)K}b_{(L-1)K}& ... &2^{(L-1)K+K-1}b_{(L-1)K+K-1} \end{pmatrix} = \begin{pmatrix} w_0& ... & w_{K-1} \\ w_K& ...& w_{K+K-1}\\ \vdots& \ddots &\vdots \\ w_{(L-1)K}& ... &w_{(L-1)K+K-1} \end{pmatrix} \tag 2 $$

其中$k\in\{0,...,K-1\},l\in \{0,...,L-1\}$，第$i$项$w_i$在矩阵中表示为$w_{lK+k}$

区别于式1的Bulletproof，Flashproof的方案为证明步骤2，也即对于任意的$i=lK+k$，证明$w_{lK+k}\in \{0,2^{lK+k}\}$

在协议的第三轮，Prover需要计算并向Verifier发送$v_l=\sum^{K-1}_{k=0}w_{lK+k}\cdot e_k+r_l$，其中$e=(e_0,...,e_{K-1})$为Verifier的挑战向量，这里的$v_l$表示第$l$行与挑战的内积，并加入随机性$r_l$，随机性确保了不会泄露与系数相关的任何信息

可以看到，Bulletproof与Flashproof最大的区别是：前者需要构建一个复杂的等式来验证三个约束，后者的方法本质上是用$v_l$来高效验证$w_{lK+k}\in \{0,2^{lK+k}\}$

此外，本文设计的新方法可以进一步减少证明过程的计算开销：对于每个$l$，让Verifier计算一个基于$v_l$的值$f_l$如下

$$ f_l=\sum^{K-1}_{k=0}2^{lK+k}\cdot e_k-v_l=\sum^{K-1}_{k=0}(2^{lK+k}-w_{lK+k})\cdot e_k-r_l $$

若$N$为素数，则之前提到的填充可用$0$代替，而非填充$2^{lK+k}\cdot e_k$，然后对于每个$l$，计算$f_l\cdot v_l$，得到下列等式

$$ f_l \cdot v_l\overset{?}{=} \sum^{K-1}_{k=0}w_{lK+k}\cdot e^2_k\cdot (2^{lK+k}-w_{lK+k})+\sum^{k=K-2,j=K-1}_{k=0,j=1}t_{l,k,j} e_{k,j}+\sum^{K-1}_{k=0}q_{l,k}\cdot e_k+q_{l,k} \tag 3 $$

其中

$$ \begin{aligned} t_{l,k,j}&=w_{lK+k}\cdot (2^{lK+j}-w_{lK+k})+w_{lK+j}\cdot (2^{lK+k}-w_{lK+k}) \\ e_{k,j}&=e_k\cdot e_j (k,j\in \{0,...,K-1\} ,k\neq j) \\ q_{l,k}&=2r_l\cdot (2^{lK+k-1}-w_{lK+k}) (k\in \{0,...,K-1\})\\ q_{l,K}&=-r^2_l \end{aligned} $$

Verifier需要利用承诺来验证所有的二次项$e^2_k$均被消除，不过Prover会在生成式3之前先提供相关承诺（在协议的第一轮就提供承诺）

根据Pedersen承诺的绑定性和SZ引理，这$k$个二次项以极高概率满足下列约束

$$ w_{lK+k}\cdot (2^{lK+k}-w_{lK+k})=0 \Rarr w_{lK+k}\in \{0,2^{lK+k}\} $$

此外，Prover还需要在第一轮提供承诺值$(c_{s_k})_{k=0}^K$，然后Verifier可以根据$(s_k)^K_{k=0}$检查下列等式

$$ \sum^{L-1}_{l=0}v_l \overset{?}{=} \sum^{K-1}_{k=0}s_k\cdot e_k+s_K \tag 4 $$

其中$s_K=\sum^{L-1}_{l=0}r_l$

最后Verifier可通过计算$y\overset{?}{=} \sum^{K-1}_{k=0}s_k$来判断是否有$y\in [0,2^N-1]$

如果采用ECC实例化该论证，且群和域元素的大小大致相同，则总的元素个数为

$$ |\Pi|=L+2K+\frac{K(K-1)}{2}+4=\lceil \frac{N}{K} \rceil +\frac{K^2+3K}{2} +4 $$

验证需要的群幂次数为$|\Pi|-1$​

这里可以简单分析一下$|\Pi|$的变化趋势，对$|\Pi|$求导，可以得到$\Delta_{|\Pi|}=K-\frac{N}{K^2}+\frac{3}{2}$，意味着$K\approx \lceil N^{\frac{1}{3}} \rfloor$时$|\Pi|$和验证复杂度均达到最小值

表4a给出了$(L,K)$的一些参数

上述协议还可以进一步优化来提高整体效率

可以通过改变挑战向量的生成方式，来将合理性误差由$\frac{(p-K)!}{p!}$提高到$\frac{1}{p}$（$p$足够大时仍然可做到可忽略），更高级的方法是让Verifier先随机生成一个挑战$e$，然后其余的挑战为$e$的不同次幂，这一方法可以合并具有相同阶数的项，从而减少证明和验证过程中计算群幂的次数

举个例子，当$K=4$时，考虑下列4个挑战$(e_k)^3_{k=0}=(e^{-1},e,e^4,e^5)$，此时Verifier为了检查$y$是否为二进制的正确表示，Verifier需要确保式3的右侧不会出现$(e^{-2},e^2,e^8,e^{10})$的项

在上述例子中，利用这四个挑战计算$f_l\cdot v_l$时会产生8个项

$$ P(e)=w_9\cdot e^9+w_6\cdot e^6 +w_5\cdot e^5 +w_4\cdot e^4+w_3 \cdot e^3+w_1\cdot e+w_{-1}\cdot e^{-1}+w_0 $$

其中项$e\cdot e^{-1},e\cdot e^4,e^{-1}\cdot e^5$分别合并到了$w_0,w_5,w_4$中

经过分析可以得到表4b，在$K=4$的情况下，此类优化可以为证明和验证过程分别节省51次和3次群幂运算，同时减少通信过程中的3个群元素（此类情况中可以提高Prover大约26%的效率）

选择的$K$对应于计算$f_l\cdot v_l$时项的数量$F(K)$，原文提供了一些$F(K)$可能的组合，读者可以自行探讨更多可能的组合

3.3 Aggregate Range Arguments

由一个证明器创建的同一范围的多个论证可以聚合，以进一步提高效率

给定$M$个witness $(y_m)^{M-1}_{m=0}$，对于每个$m\in \{0,...,M-1\}$，Prover为每个$m$构建两个集合$(v_l^{(m)})^{L-1}_{l=0},(s_k^{(m)})^{K}_{k=0}$，然后Prover实例化$M\cdot L$个生成器，其中第$(m,l)$个生成器用于计算$f^{(m)}_l\cdot v^{(m)}_l$

这么一来，$M$在式3右侧的系数可以压缩至一个承诺中，然后再利用$[3]$中的批量验证技术来减少验证式4时需要的群幂的次数

这个方法的主要思路如下：若要证明$a=0\wedge b=0$，可以转化为证明$a+\rho b=0$，其中$\rho\in \Z_p^*$

接着上述证明，此时Verifier可以生成一个新的随机数$z\in \Z_p^*$，然后利用下列等式来验证$s_k^{(m)}$

$$ \sum^{M-1}_{m=0} (\sum^{L-1}_{l=0} v_l^{(m)})\cdot z^m \overset{?}{=} \sum^{K-1}_{k=0} (\sum^{M-1}_{m=0} s_k^{(m)}\cdot z^m)\cdot e^k+\sum_{m=0}^{M-1} s^{(m)}_K\cdot z^m $$

最后Verifier对于每个$m$，检查$y_m\overset{?}{=}\sum^{K-1}_{k=0}s_k^{(m)}$

上述过程中的总元素数量为$|\Pi_{total}|=M\cdot (\lceil \frac{N}{K} \rceil+K+1 )+\frac{K^2+K}{2} +3$，当$K\approx \lceil (MN)^{\frac{1}{3} } \rceil \wedge \frac{N}{K} \geq 1$时验证与通信复杂度达到最低（求导可知）

对于聚合$M$个论证的优化方式，可以用公式$\frac{F(K)+2}{M} + \lceil \frac{N}{K} \rceil +K+1$来计算通信所需的元素数量，或者验证过程中每个论证所需要的群幂数量

4 Polynomial Evaluation Argument

本文的多项式求值论证基于$[BG13]$的技术构建，多项式求值论证旨在证明两个承诺值$x,y$满足一个公开的多项式$y=P(x;D)$，其中$D$表示该多项式的阶

本文的核心思想是：利用二次项抵消技术来提高计算效率并降低通信开销

本文给出了两种协议，分别针对$D\in [3,2^9]$和$D>2^9$两种情况，完整协议于6.2和6.3节给出

4.1 Overview of BG13

首先来看一下$[BG13]$的多项式求值论证，考虑一个多项式$P(x;D)=\sum^D_{d=0}a_d\cdot x^d$，不失一般性，考虑其阶$D=2^{J+1}-1$的情况（$J\in \{1,2,...\}$）

对于多项式中每个项$x^d$的幂数$d$，将其分解为二进制的形式，也即将幂数$d$改写为$d=\sum_{j=0}^{J} 2^j b_d^{(j)}$，其中$b_d^{(j)}\in \{0,1\},J+1=\lceil \log D\rceil$

此时$x^d$可以改写为

$$ x^{\sum_{j=0}^{J} 2^j b_d^{(j)}}=\prod_{j=0}^{J}x^{2^jb_d^{(j)}} $$

对应的多项式$P$可以改写为

$$ P(x;D)=\sum_{d=0}^{D}a_d x^d =\sum_{d=0}^{D}a_d x^{\sum_{j=0}^{J} 2^j b_d^{(j)}} = \sum_{d=0}^{D}a_d \prod_{j=0}^{J} x^{2^jb_d^{(j)}} $$

$[BG13]$中定义了一个新的多项式$Q(e;J+1)$，并用一个掩码值$z_j=x^{2^j}e+m_j$来取代原来的$x^{2^j}$，除此之外，多项式$Q$的系数$e^{J+1}$为多项式，因此，得到的多项式$Q$如下

$$ Q(e;J+1)=\sum_{d=0}^{D} (a_d\prod_{j=0}^{J}e^{1-b_d^{(j)}}\cdot z_j^{b_d^{(j)}} )=P(x;D)\cdot e^{J+1}+\sum_{j=0}^{J} w_je^j \tag 5 $$

其中$m_j$为随机值，$e$为V的随机挑战，$w_j$为$e^j$的系数

此时Prover需要提供$P$的承诺，并在收到Verifier的挑战$e$之前发送系数$(w_j)^J_{j=0}$进行承诺，以证明多项式$Q$具有正确的形式，这个过程包含下列三个约束条件

  1. $P(x;D)$为$e^{J+1}$项的系数
  2. 对于所有的$j\in\{0,...,J\}$，$x^{2^j}$与$z_j$之间存在线性关系$z_j=x^{2^j}e+m_j$
  3. $x^{2^{j+1}}$与$z_{j+}$和$x^{2^j}$与$z_j$之间存在二次约束关系

为了验证者三个约束条件，$[BG13]$构造了三个群元素集合如下

$$ (c_{x^{2^j}})^J_{j=1},(c_{m_j})^J_{j=0},(c_{x^{2^j}m_j})^{J-1}_{j=0} $$

同时构造两个域元素集合

$$ (r_j)^J_{j=0},(\xi_j)^{J-1}_{j=0} $$

利用这些集合，可以通过两个等式来验证后两个约束

$$ \begin{aligned} z_j\overset{?}{=}&x^{2^j}\cdot e +m_j \Rightarrow \mathbf{Cm}(z_j;r_j)\overset{?}{=}c^e_{x^{2^j}}\cdot c_{m^j}\\ 0\overset{?}{=}&x^{2^{j+1}}\cdot e-x^{2^j}\cdot z_j+x^{2^j}\cdot m_j\Rightarrow \mathbf{Cm}(0;\xi_j)\overset{?}{=}c^e_{x^{2^{j+1}}} \cdot c^{-z_j}_{x^{2^j}}\cdot c_{(x^{2^j}m_j)} \end{aligned}\tag 6 $$

4.2 Techniques of Lower-Degree (LD) Protocol

观察一下上一节中的验证等式（式6），很复杂，因此需要优化这两个验证等式来降低计算和通信开销

方法是构建一个新的等式来有效的利用域元素$(z_j)^J_{j=0}$，而非像$[BG13]$中那样采用群元素完成验证（域上计算比群上快得多）

$$ \begin{aligned} z_0\overset{?}{=}&x\cdot e+m_0\\ z^2_j-z_{j+1}\cdot e\overset{?}{=}&(2x^{2^j}\cdot m_j-m_{j+1})\cdot e+m^2_j \end{aligned}\tag 7 $$

其中$j\in\{0,...,J-1\}$

在式7中，首先需要确保输入$x$和$z_0$之间的线性关系，然后对于$j\in\{0,...,J-1\}$，计算$z^2_j-z_{j+1}\cdot e$，此过程会消去二次项$e^2$，同时留下$e$的一次项和一个常数项$m^2_j$

本文的方式只需要Prover在收到Verifier挑战之前发送关于这两个项的系数向量承诺，这不仅确保了$x^{2^j}$和$x^{2^{j+1}}$之间的约束关系（约束3），还确保了$x^{2^j}$与$z_j$之间的线性关系（约束2），若这两个约束不成立，则$e^2$的项会以极高的概率出现在等式右侧

与$[BG13]$相比，本文的方案需要的群运算更少，通信开销方面减少了$5\log D$个元素，同时还有助于减小证明大小

4.3 Techniques of Higher-Degree (HD) Protocol

在较低阶协议之上，本文旨在进一步优化使得约束1成立的等式

本文的方式是尝试利用多项式承诺来减少式5中$\log D$个群元素和$3\sqrt{\log D}$个域元素，简单来说，可以先找出多项式中出现比较频繁的项$\sum^J_{j=0}w_j\cdot e^j$，将其改写为如下形式

$$ \sum_{l=0}^{L-1} e^{lK} \sum_{k=0}^{K-1} w_{lK+k}\cdot e^k $$

其中$l\in\{0,...,L-1\},k\in\{0,...,K-1\}$，不失一般性，若$J+1<L\cdot K$，则填充若干个零系数直到$J+1=L\cdot K$

这里关注第二个求和号，对于$L$个多项式$(\sum_{k=0}^{K-1} w_{lK+k}\cdot e^k)^{L-1}_{l=0}$，可以将其系数分解并构造一个矩阵，矩阵中的每一行均包含多项式分解后的系数，且每一列为$e$的同阶系数向量，如下

$$ \begin{pmatrix} w_0+\theta_0 & w_1 & ...& w_{K-1}\\ w_K+\theta_1 & w_{K+1} & ...& w_{2K-1}\\ \vdots & \vdots & \ddots &\vdots \\ w_{(L-1)K}+\theta_{L-1} & w_{(L-1)K+1} & ...& w_{LK-1} \end{pmatrix} $$

Prover需要利用向量承诺对所有的列承诺，得到$(c_{w_k})_{k=0}^{K-1}$，然后对于所有的$l$，计算第$l$行与挑战向量$e=(1,e,...,e^{K-1})$的随机化内积（$\theta_l\in \Z_p^*$用于确保不会泄露）

$$ f_l=\sum_{k=0}^{K-1} w_{lK+k}\cdot e^k+\theta_l $$

承诺计算方式如下

$$ c_{w_0}=\prod_{l=0}^{L-1} g_l^{w_{lK}+\theta_l} \cdot h^{r_{w_0}}\\ (c_{w_k}=\prod_{l=0}^{L-1} g_l^{w_{lK+k}} \cdot h^{r_{w_k}})^{K-1}_{k=0} $$

其中$g_l,h$均为群$\mathbb G$上互不相同的生成元，$r_{w_k}$为$\Z_p^*$中的随机值

Verifier需要计算下列等式来检查$(f_l)^{L-1}_{l=0}$的正确性，其中$s=\sum^{K-1}_{k=0}r_{w_k}\cdot e^k$

$$ \prod_{l=0}^{L-1}g_l^{f_l}\cdot h^s \overset{?}{=} \prod_{k=0}^{K-1}c_{w_k}^{e^k} $$

同时构建一个新的等式来代替式5对第一个约束的校验

$$ Q(e;J+1)-\sum_{l=0}^{L-1} f_l\cdot e^{lK} \overset{?}{=} P(x;D)\cdot e^{J+1}- \sum_{l=0}^{L-1} \theta_l\cdot e^{lK} \tag 7 $$

这里Prover需要在获得挑战向量$e$之前先对$(\theta_l)^{L-1}_{l=0}$进行承诺

上述方法不仅可以减小证明大小，还可以减少群幂的次数，从而降低通信和计算复杂度

4.4 Aggregate Polynomial Evaluation Arguments

多项式求值论证也可以聚合来提高效率

注意到本文的方法允许一个非平凡的将阶较高的多项式的通信开销降低至$\log D+3\sqrt{\log D}+7$，因此满足具有相同度的多项式和输入的不同都像是的多个自变量可以均摊论证过程中的通信开销

对于给定的$M$个度相同的多项式$(P(x;D)^{(m)})^{M-1}_{m=0}$，和之前一样，Prover首先实例化$M\cdot L$个生成器，将所有的$M$个论证的系数压缩，构造$K$个承诺$(c_{w_k})_{k=0}^{K-1}$

然后Prover对所有的$m\in\{0,...,M-1\}$，构造两个集合$(f_l^{(m)})^{L-1}_{l=0},(\theta_l^{(m)})^{L-1}_{l=0}$

类似于聚合范围论证，Verifier使用下面的等式来批量检查多个论证的第一个约束（其中$z\in \Z_p^*$为Verifier提供的新的挑战）

$$ \sum_{m=0}^{M-1}(Q(e;J+1)^{(m)} -\sum_{l=0}^{L-1}f_l^{(m)}\cdot e^{lK})\cdot z^m \overset{?}{=} \sum_{m=0}^{M-1} P(x;D)^{(m)}\cdot z^m\cdot e^{J+1}-\sum_{l=0}^{L-1} (\sum_{m=0}^{M-1} \theta_l^{(m)}\cdot z^m)\cdot e^{lK} $$

对于聚合的$M$个论证，可以用公式算出通信开销和平均每个论证验证过程中需要的群幂次数

4.5 Limitation & Extension

本文的技术旨在减少群幂次数和通信元素数量以提高协议的效率

然而局限性在于基于$[BG13]$技术，本文的协议仍然需要线性数量的域乘法，以在最坏情况下计算具有少量零项的多项式（多项式中的零项越多越好）

当多项式的阶很大时，域乘法的计算开销将超过群幂

不过本文的论证可以扩展到满足多变量多项式关系，例如两个向量的内积，此类情况下通信开销、计算效率与变量数量呈线性关系

5 Empirical Experiments

这没啥好看的，就是一些效率评估，具体可以看原文

6 Protocols & Security Proofs

6.1 Range Argument

这里的公式懒得打了，直接截图吧，简单说一下

式8就是之前的范围论证

上述协议满足完美完备性，计算证据扩展仿真，完美特殊城市Verifier的零知识性，证明可看原文

6.2 Polynimial Evaluation arguments ofr Lower Degree

上述协议满足完美完备性，计算证据扩展仿真，完美特殊城市Verifier的零知识性，证明可看原文

6.3 Polynomial Evaluation Arguments for Higher Degree

上述协议满足完美完备性，计算证据扩展仿真，完美特殊城市Verifier的零知识性，证明可看原文

References

$[1]$ Nan Wang, Sid Chi-Kin Chau:Flashproofs: Efficient Zero-Knowledge Arguments of Range and Polynomial Evaluation with Transparent Setup. IACR Cryptol. ePrint Arch. 2022: 1251 (2022)

$[2]$ Bulletproof论文精读 - 三两老友杂的小岛 (snowolf0620.xyz)

$[3]$ Mihir Bellare, Juan A. Garay, Tal Rabin:Fast Batch Verification for Modular Exponentiation and Digital Signatures. IACR Cryptol. ePrint Arch. 1998: 7 (1998)

‍