Abstract

Bulletproof于2018年提出，是一种新的非交互式零知识证明方案，证明长度很小，且无需可信设置，证明大小为witness的对数阶

Bulletproof适用于对承诺值的高效的范围证明，且只需要$2\log n+9$个群和域元素，其中$n$为范围长度的二进制表示，证明的生成和验证时间均为$n$的线性阶

Bulletproof改进了现有Bitcoin和其他加密货币机密交易方案中线性大小的范围证明，且Bulletproof支持范围证明的聚合，也即参与方对于给定范围的$m$个承诺，只需要$O(\log m)$个群元素就可以生成一个证明

Bulletproof还可以用于聚合多个参与方的证明，此时由没个参与方生成一个单一的证明，在不泄露各自输出的情况下，通过一个简单的MPC协议来构建Bulletproof，这里仅要求使用的MPC协议包含常数轮交互和线性阶的通信开销（或者对数阶交互轮数和对数阶通信开销）

1 Introduction

基于BlockChain的加密货币通过维持一个全局的分布式账本来支持点对点的电子转账，转账后需要同步账本，任何独立的观察者可以验证当前区块链状态，也即验证账本上的所有交易

一般而言，可以将隐私划分为两个性质：匿名性和机密性，匿名性指的是在交易中隐藏Sender和Receiver的实体，机密性表示隐藏交易的金额

比特币可以提供较弱的匿名性，可以使用户无法通过交易地址和现实生活中的人联系起来，但是Bitcoin的缺陷在于没有确保机密性

Mexwell等人提出了机密交易（Confidential Transaction，CT）的概念来解决机密性，每笔交易通过承诺的方式来隐藏，但是这样的话验证账本的结点无法确保输入与输出金额相等，解决的办法是引入ZKP来实现CT的验证

但是现有的基于ZKP的CT，要么像zkSNARK一样需要可信设置，要么像zkSTARK一样太重，这两个问题都对分布式系统的网络传输和存储都不友好

因此本文提出了一种新的ZKP Argument of Knowledge，称为Bulletproof，用于证明一个秘密的承诺值在给定的区间内，方案基于DLOG假设，无需可信设置

此外本文还给出了如何对Bulletproof进行批处理，从而进一步降低每个证明的验证开销

Bulletproof的应用范围很广，包括但不限于下列几个

  • Confidential Transactions：所有现有的CT实现均对承诺的值使用范围证明，CT可以在侧链、私有链和流行的专注于隐私的加密货币Monero中实现，均基于Bulletproof
  • Mimblewimble：一种对保密交易的改进方案，允许将交易发送到BLockChain之前对其进行聚合，Mimblewimble Blockchain会随着UTXO集的大小而增长，利用Bulletproof可以使得区块的大小比之前的更小
  • Provisions：Provisions协议允许Bitcoin交易所证明其具有偿付能力而不暴露任何信息，该协议及其依赖于范围证明，以防止交易所插入具有负余额的假帐户，利用Bulletproof，可以将范围证明的大小减少至小于2KB
  • Verifiable Shuffles：可验证洗牌在许多领域均有应用，包括投票、混合网络（Mix-Nets）、偿付能力证明等等，使用Bulletproof的可验证洗牌在实践中很有效，构造证明和验证的时间开销都为$n$的线性阶
  • NIZK Proofs for Smart Contracts：以太坊通过高效的智能合约来实现复杂的交易，但是智能合约本身不提供隐私，利用NIZK，可以实现不泄露用户输入的智能合约，但是NIZK本身不适合通过智能合约验证，Bulletproof通过无需可信设置的小型证明来改进这个点（尽管Bulletproof的Verifier开销很大，但是有方案可以解决）
  • Short Non-Interactive Protocols for ArithmeticCircuits without a Trusted Setup：如果不采用CRS，则无法证明一般的NIZK Statement，而CRS又必须是Prover和Verifier都可见的，此类情况下Bulletproof或许很有用

2 Perliminaries

  • $\mathbb G$：阶为$p$的循环群
  • $\mathbb Z_p$：模$p$下的整数环
  • $\mathbb G^n,\mathbb Z_p^n$：$\mathbb G$和$\mathbb Z_p$下的$n$维向量空间
  • $\mathbb Z_p^*$：$\mathbb Z_p\backslash\{0\}$
  • $g,h,v,u\in \mathbb G$：$\mathbb G$中的生成元
  • $\alpha$：一系列希腊字母，表示盲因子
  • $a$：小写英文字母，表示要承诺的值，比如Pedersen承诺$C=g^ah^\alpha\in \mathbb G$，表示对$a$的承诺
  • $\boldsymbol a$：加粗小写英文字母，表示$n$维向量，比如$\boldsymbol a\in \mathbb F^n$表示$(a_1,a_2,...,a_n),a_i\in\mathbb F$
  • $\boldsymbol A\in\mathbb F^{n\times m}$：加粗大写英文字母，表示$n$行$m$列的矩阵
  • $\cdot$：表示标量乘法，适用于$n$维向量或矩阵
  • $\langle \boldsymbol a,\boldsymbol b\rangle$：表示向量内积，$<\boldsymbol a,\boldsymbol b>=\sum_{i=1}^na_i\cdot b_i$
  • $\boldsymbol a \circ\boldsymbol b$：表示向量的哈达玛积，结果仍然为一个向量，$\boldsymbol c=\boldsymbol a \circ\boldsymbol b=(a_1\cdot b_1,...,a_n\cdot b_n)$
  • $\boldsymbol A \cdot \boldsymbol b=\boldsymbol c$：矩阵与向量的乘法，结果为一个向量
  • $C=\boldsymbol g^{\boldsymbol a}$：表示Pederesen向量承诺，$\boldsymbol g=(g_1,...,g_n),\boldsymbol a=(a_1,...,a_n)$，$C=\boldsymbol g^{\boldsymbol a}=\prod_{i=1}^ng_i^{a_i}$，该方式是绑定的，但不是隐藏的

此外，对于给定的承诺值$C$和向量$\boldsymbol b\in \mathbb Z^n_p$，可将承诺值视为对$\boldsymbol a \circ\boldsymbol b$的承诺，定义$g_i'=g_i^{b_i^{-1}}$，此时$C=\boldsymbol g^{\boldsymbol a}=\prod_{i=1}^ng_i^{a_i}=\prod_{i=1}^ng_i'^{a_i\cdot b_i}$，这个方式特点是只要$C$对向量$\boldsymbol a$的承诺是绑定的，则对向量$\boldsymbol a \circ\boldsymbol b$的承诺也是绑定的

  • $\boldsymbol a||\boldsymbol b$：表示两个向量的拼接
  • $\boldsymbol a_{[:k]}$：Python记法，表示$(a_1,...,a_k)$，$\boldsymbol a_{[k:]}$表示$(a_k,...,a_n)$
  • $\boldsymbol k^n$：对于$k\in\mathbb Z^*_p$，$\boldsymbol k^n$表示$k$的所有次幂，也即$\boldsymbol k^n=(1,k,k^2,...,k^{n-1})$，同理$\boldsymbol k^{-n=}(1,k^{-1},k^{-2},...,k^{1-n})$
  • $\{(Public Input;Witness):Relation\}$：表示公共输入和证据的关系

本文采用Pedersen承诺及其向量承诺版本，如下

  • 承诺单个元素：$Com(x;r)=g^x\cdot h^r$
  • 承诺向量：$\boldsymbol x=(x_1,x_2,...,x_n),Com(\boldsymbol x;r)=g^{\boldsymbol x}h^r=h^r\prod_ig_i^{x_i}\in \mathbb G$

Bootle等人引入了通信效率很高的内积Argument，同时展示了如何利用它来构造算术电路可满足性的ZKP，通信复杂度也很低，且是一个Proof of Knowledge，Prover可以揭示满足给定内积关系的两个约束的Pedersen向量承诺

本文将该方案的复杂度降低为原来的1/3（原来是$6\log n$），其中$n$表示向量的维度，同构修改被证明的关系来实现这种优化

本文的方法是PoK，但是不是ZK，本文还证明了该协议在一组承诺值上提供了基于公开掷币的高效通信ZKP范围证明，并为算术电路提供了一个ZKP证明系统（第4，5节），通过应用FS变换可以转化为非交互式的证明（4.4节）

Overview

先从一个简单的例子讲起

对于两个向量$\boldsymbol a,\boldsymbol b$，Prover需要证明$\boldsymbol P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b}$和$c=\langle \boldsymbol a,\boldsymbol b\rangle$，也即证明下面这个关系

$$ \{(\boldsymbol g,\boldsymbol h\in \mathbb G^n,P\in \mathbb G,c\in \Z_p,\boldsymbol a,\boldsymbol b\in\mathbb Z^n_p):P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b}\wedge c=\langle \boldsymbol a,\boldsymbol b\rangle \} \tag 1 $$

最简单的方法是Prover直接把两个$n$维向量$\boldsymbol a,\boldsymbol b$发送给Verifier，但是此时通信量为$2n$个元素，有一种方法可以做到$2\log n$个元素

首先修改一下需要证明的关系，将向量承诺$\boldsymbol P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b}$修改为$\boldsymbol P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b}\cdot u^{<\boldsymbol a,\boldsymbol b>}$，也即将原来需要证明的关系修改为下面这个

$$ \{(\boldsymbol g,\boldsymbol h\in \mathbb G^n,u,P\in \mathbb G,\boldsymbol a,\boldsymbol b\in\mathbb Z^n_p):P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b} \cdot u^{\langle \boldsymbol a,\boldsymbol b\rangle}\} \tag 2 $$

利用下面提到的Protocol 1，可以做到证明关系2具有和证明关系1相同的复杂度

不过这里需要一个Hash函数$H:\Z^{2n+1}_p\rightarrow \mathbb G$该Hash函数输入四个长度为$n'=\frac{n}{2}$的向量和一个$c\in \Z^n_p$，输出一个群元素，Hash函数具体如下

$$ H(\boldsymbol a,\boldsymbol a',\boldsymbol b,\boldsymbol b',c)=\boldsymbol g^{\boldsymbol a}_{[:n']}\cdot \boldsymbol g^{\boldsymbol a'}_{[n':]}\cdot\boldsymbol h^{\boldsymbol b}_{[:n']}\cdot\boldsymbol h^{\boldsymbol b'}_{[n':]}\cdot u^c \in \mathbb G $$

利用这个Hash函数，关系2中的承诺可以写为$P=H(\boldsymbol a_{[:n']},\boldsymbol a'_{[n':]},\boldsymbol b_{[:n']},\boldsymbol b'_{[n':]},\langle \boldsymbol a,\boldsymbol b\rangle)$​

此外还有一个要求：这个Hash函数满足加法同态，也即满足

$$ H(\boldsymbol a_1,\boldsymbol a'_1,\boldsymbol b_1,\boldsymbol b'_1,c_1)\cdot H(\boldsymbol a_2,\boldsymbol a'_2,\boldsymbol b_2,\boldsymbol b'_2,c_2)=H(\boldsymbol a_1+\boldsymbol a_2,\boldsymbol a'_1+\boldsymbol a_2',\boldsymbol b_1+\boldsymbol b_1,\boldsymbol b'_1+\boldsymbol b'_2,c_1+c_2) $$

此时Prover计算两个元素$L,R\in\mathbb G$并发送给Verifier，具体如下

$$ \begin{aligned}L&=H(\boldsymbol 0^{n'},\boldsymbol a_{[:n']},\boldsymbol b_{[n':]} \boldsymbol 0^{n'},\langle\boldsymbol a_{[:n']},\boldsymbol b_{[n':]}\rangle)\\R&=H(\boldsymbol a_{[n':]},\boldsymbol 0^{n'},,\boldsymbol 0^{n'},\boldsymbol b_{[:n']} ,\langle\boldsymbol a_{[n':]},\boldsymbol b_{[:n']}\rangle) \end{aligned} $$

然后Verifier随机选择$x\stackrel{\$}{leftarrow} mathbb Z_p$并发送给Prover，然后Prover计算两个$n'$维的向量并发送给Verifier

$$ \begin{aligned} \boldsymbol a'=x\boldsymbol a_{[:n']}+x^{-1}\boldsymbol a_{[n':]}\\ \boldsymbol b'=x\boldsymbol b_{[:n']}+x^{-1}\boldsymbol b_{[n':]} \end{aligned} $$

Verifier根据$\boldsymbol a',\boldsymbol b'$，计算$P'=L^{x^2}\cdot P\cdot R^{x^{-2}}$

$$ P'=H(\boldsymbol a_{[:n']}+x^{-2}\boldsymbol a_{[n':]},x^2\boldsymbol a_{[:n']}+\boldsymbol a_{[n':]},x^2\boldsymbol b_{[n':]}+\boldsymbol b_{[:n']},\boldsymbol b_{[n':]}+x^{-2}\boldsymbol b_{[:n']},\langle\boldsymbol a',\boldsymbol b' \rangle)=H(x^{-1}\boldsymbol a',x\boldsymbol a',x\boldsymbol b',x^{-1}\boldsymbol b',\langle\boldsymbol a',\boldsymbol b'\rangle) \tag 3 $$

Verifier当且仅当$P'=P$时接收Prover

不难看出，$\boldsymbol a',\boldsymbol b'$都是$n'$维向量，此时需要发送的元素为$\boldsymbol a',\boldsymbol b'$，以及两个用于验证的元素$L,R$，这样就可以将通信量由$2n$个元素降低至$n+2$个元素了

这里还有一个点，式3实际上等价于下面这个等式

$$ P'=(\boldsymbol g^{x^{-1}}_{[:n']}\circ \boldsymbol g^{x^{}}_{[n':]})^{\mathbf a'}\cdot (\boldsymbol h^{x^{-1}}_{[:n']}\circ \boldsymbol h^x_{[n':]})^{\mathbf b'} \cdot u^{\langle\boldsymbol a',\boldsymbol b'\rangle} $$

此时的生成元就由原来的两个$n$维向量$\boldsymbol g,\boldsymbol h$和一个群元素$u$变为了两个$n'=\frac{n}{2}$维向量$(\boldsymbol g^{x^{-1}}_{[:n']}\circ \boldsymbol g^{x^{}}_{[n':]}),(\boldsymbol h^{x^{-1}}_{[:n']}\circ \boldsymbol h^x_{[n':]})$和一个群元素，这样y依赖，通过分治的思想，以递归的方式继续处理这两个$n'$维的向量

不难看出这个过程的递归深度为$\log n$（详见下面的Protocol 2），利用FS启发式可将该协议转化为非交互式的，整个协议的的通信量为$2 \lceil \log n\rceil$个$\mathbb G$中元素和两个$\Z_p$中的元素，也即Prover需要发送的是下面这一堆

$$ (L_1,R_1),...,(L_{\log n },R_{\log n}),a,b $$

其中$a,b$会在递归完成后再发送

整个过程Prover需要$8n$次群指数运算，Verifier需要$4n$次

基于上面这个例子，接下来看一下内积论证

The Inner-Product Argument

内积论证的输入为两个生成元向量$\boldsymbol g,\boldsymbol h\in \mathbb G^n$，一个标量$c\in \mathbb Z_p$和一个绑定性承诺$P\in \mathbb G$，满足$P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b}$，假设$n$为2的幂次，该argument说明了内积$c=\langle \boldsymbol a,\boldsymbol b\rangle$给出了计算$\boldsymbol g,\boldsymbol h$中每对不同群元素之间离散对数之间的困难性

通过上述设置，Protocol 1中描述的内积协议为关系1的有效证明系统


‍

3.1 Inner-Product Verification through Multi-Exponentiation

注意到Protocol 2中，Prover和Verifier每一轮需要计算一个新的生成元向量$\mathbf g',\mathbf h'$，双方总的指数运算次数为$4n$，这里有一个办法，将所有的计算放到最后一轮交互

这个方法可能对交互式协议的提升不大，但是如果用FS编译协议的话还是很有用的，因为同时进行多次幂运算比$n$次独立幂运算要快得多，从而提高协议效率

记$g,h$分别表示最后一轮使用的生成元，$x_j$为第$j$轮的挑战，最后一轮中Verifier需要验证等式$g^a\cdot h^b\cdot u^{a\cdot b}=P$，此时可以把递归展开，用$g,h$表示最终的生成元向量$\mathbf g,\mathbf h$

$$ g=\prod^n_{i=1}g_i^{s_i},h=\prod^n_{i=1}h_i^{1/s_i} $$

其中$\mathbf s=(s_1,\dots,s_n)$取决于每轮的挑战$(x_1,\dots,x_{\log n})$，计算方式如下

$$ i=i,\dots,n:\qquad s_i\prod^{\log n}_{j=1} x_j^{b(i,j)} \qquad b(i,j)=\left\{\begin{matrix} 1,&the\ jth\ bit\ of\ i-1\ is\ 1 \\ -1,&otherwise \end{matrix}\right. $$

此时协议中每一轮的验证等式可以整合成下面这个

$$ \mathbf g^{a\cdot \mathbf s}\cdot \mathbf h^{b\cdot \mathbf s^{-1}}\cdot u^{a\cdot b}=P\cdot \prod^{\log n}_{j=1}L_j{(x^2_j)}\cdot R_j^{(x_j^{-2})} $$

4 Range Proof Protocol with Logarithmic Size

本节介绍一个新的协议，可以用于执行短证明和可聚合的范围证明，该协议使用Protocol 1中改进的内积Argument

4.1 Inner-Product Range Proof

本文提出了一个新的协议，使用改进的内积Argument来构造范围证明，该证明使得Verifier确信承诺值$V$包含一定范围内的数字$v$且不暴露$v$

Bootle等人提出了一个任意算术电路的证明系统，第五节中证明了本文的内积Argument的改进可以归约到该证明系统，也可以使用算术电路证明承诺在给定范围内，且可用于构造对数大小的范围证明

然而上述电路需要实现承诺函数，比如对Pedersen承诺进行多次幂运算，这会导致产生大型复杂电路，本文以一种更直接的方法构造范围证明

范围证明利用了这样一个点：Pedersen承诺值$V$为内积论证所使用的群中的一个群元素，原文第五节扩展了这个思路，从而本文的电路可以接受任意数量的承诺作为输入

接下来看一下范围承诺的关系，记$v$为$[0,2^n-1]$范围内的一个整数，$n=O(\lambda)$，$V$为$v$在随机性$\gamma$下的向量承诺，记$\mathbf a_L=(a_1,...,a_n)$为表示$v$的比特的向量，也即$v=\langle \mathbf a_L,\mathbf 2^n\rangle$，对应的范围关系如下

$$ \{(g,h\in\mathbb G,V,n;,v,\gamma\in\Z_p):V=h^\gamma\cdot g^v\wedge v\in[0,2^n-1]\} \tag 1 $$

Prover对$\mathbf a_L$进行承诺，得到承诺元素$A\in\mathbb G$，此时上述范围关系等价于下列三个等式

$$ \begin{aligned} \langle \mathbf a_L,\mathbf 2^n\rangle=v \\ \mathbf a_R=\mathbf a_L-\mathbf 1^n\\ \mathbf a_L\circ \mathbf a_R=\mathbf 0^n \end{aligned}\tag 2 $$

这里$\mathbf a_R=\mathbf a_L-\mathbf 1^n$的意思是将$\mathbf a_L$按位取反

看一下如何证明这三个等式，首先Verifier发送随机性$y$，Prover利用$y$对一个零向量$\mathbf b=\mathbf 0^n$进行承诺，若$\mathbf b\neq \mathbf 0^n$，根据SZ引理，等式$\langle \mathbf b,\mathbf y^n\rangle=0$成立的概率至多为$n/p$

此时式2中的三个等式可以转换为下列形式

$$ \begin{aligned} \langle \mathbf a_L,\mathbf 2^n\rangle=v \\ \langle \mathbf a_L-\mathbf 1^n-\mathbf a_R,\mathbf y^n\rangle=0\\ \langle \mathbf a_L,\mathbf a_R\circ \mathbf y^n\rangle =0 \end{aligned}\tag 3 $$

式3中的第二个等式相当于把式2中的第二个等式移项成了$\mathbf a_L-\mathbf 1^n-\mathbf a_R=0$，第三个等式加上了随机性$\mathbf y^n$

三个等式还是太复杂了，这里让Verifier再选择一个随机性$z$，将式3中的三个等式整合成一个

$$ z^2\cdot \langle \mathbf a_L,\mathbf 2^n\rangle +z\cdot \langle \mathbf a_L-\mathbf 1^n-\mathbf a_R,\mathbf y^n\rangle +\langle \mathbf a_L,\mathbf a_R\circ \mathbf y^n\rangle =z^2\cdot v $$

这个不难理解，后两个等式都是0，所以结果为$z^2\cdot v$

再进一步，将式4整合成一个向量内积的形式

$$ <\mathbf a_L-z\cdot \mathbf 1^n,\mathbf y^n\circ(\mathbf a_R+z\cdot \mathbf 1^n)+z^2\cdot 2^n>=z^2\cdot v+\delta(y,z)\tag 4 $$

其中$\delta (y,z)$如下

$$ \delta(y,z)=(z-z^2)\cdot <\boldsymbol 1^n,\boldsymbol y^n>-z^3<\boldsymbol 1^n,\boldsymbol 2^n> $$

这里把式4展开，$\langle \mathbf a_L,z^2\cdot \mathbf 2^n \rangle$那一项为$z^2\cdot v$，剩下的就是$\delta$

由于$\delta$可以由Verifier计算，因此Prvoer只需要将式4中的两个向量发送给Verifier，然后Verifier用$v$的承诺值$V$进行验证即可

但是这个过程会泄露$\mathbf a_L$的信息，因此需要引入两个盲向量$\mathbf s_L,\mathbf s_R$来对式4中的两个向量进行盲化

引入盲向量后，结合上面的步骤，此时式1的关系就可以转换为下面这个图

图1
图1

这里定义两个与内积向量相关的多项式$l(X),r(X)$，以及一个二次多项式$t(X)$，如下

$$ \begin{aligned} l(X)&=(\mathbf a_L-z\cdot \mathbf 1^n)+\mathbf s_L\cdot X\\ r(X)&=\mathbf y^n\circ(\mathbf a_R+z\cdot \mathbf1^n+\mathbf s_R\cdot X)+z^2\cdot \mathbf 2^n\\ t(X)&=\langle l(X),r(X) \rangle=t_0+t_1\cdot x+t_2\cdot X^2 \end{aligned} $$

利用盲向量$\mathbf s_L,\mathbf s_R$，Prover可以在一个随机点$x$处公开两个多项式$l(x),r(x)$，且不会泄露关于$\mathbf a_L,\mathbf a_R$的相关信息

这里观察一下多项式$t$，其中的常数$t_0$表示式4等式的右侧，也即Prover需要向Verifier证明$t_0=z^2\cdot v+\delta(y,z)$​

证明的方式也很简单，Prover首先对$t_1,t_2$进行承诺，然后Prover选择一个随机点$x$，双方执行下列协议

Verifier通过检查内积$\langle \mathbf l,\mathbf r \rangle$来验证$t(x)$

不过还有一个点：这里需要构建对$\mathbf a_R\circ \mathbf y^n$的承诺，Verifier需要把生成元由$\mathbf h$修改为$\mathbf h'=\mathbf h^{(\mathbf y^{-n})}$，这样一来，承诺值$A$就是以$(\mathbf g,\mathbf h',h)$为生成元，对向量$(\mathbf a_L,\mathbf a_R\circ \mathbf y^n)$的承诺，类似的，$S$为$(\mathbf s_L,\mathbf s_R\circ \mathbf y^n)$的承诺，因此协议剩余的验证工作如下

图3
图3

4.2 Logarithmic Range Proof

对于上一节提到的协议，注意到一个问题，Prover给Verifier发送的多项式$\mathbf l,\mathbf r$的大小均与范围$n$呈线性关系，通信量和证明大小是个问题，这里介绍一下如何将大小降低至对数阶

回顾一下之前的关系2

$$ \{(\boldsymbol g,\boldsymbol h\in \mathbb G^n,u,P\in \mathbb G,\boldsymbol a,\boldsymbol b\in\mathbb Z^n_p):P=\boldsymbol g^{\boldsymbol a}\boldsymbol h^{\boldsymbol b} \cdot u^{\langle \boldsymbol a,\boldsymbol b\rangle}\} $$

这里观察上一节中的式67和式68，相当于是验证了多项式$\mathbf l,\mathbf r$是否满足上述关系2，若验证通过，则表明承诺值$P$所对应的多项式$\mathbf l,\mathbf r$满足内积关系$\hat t=\langle \mathbf l,\mathbf r\rangle$

因此这里可以用内积关系来替换上述协议中需要内积的部分，此时需要将式63中发送的元素修改为$(\tau_x,\mu,\hat t)$，然后根据上一篇博客的内容，走一个内积论证即可，此时的通信量可以由原来的$2n$个元素降低为$2\lceil \log n \rceil+2$，Prover的总通信量为$2\lceil \log n \rceil+4$个群元素和5个域元素

4.3 Aggregating Logarithmic Proofs

至此，论文介绍了如何构建范围证明，但是许多证明系统中，Prover往往需要同时执行多个证明，比如CT中的一笔交易通常会包含不止一笔输出，因此本节介绍如何在上面的协议的基础上，聚合多个证明

聚合证明的关系如下

$$ \big\{ (g,h\in\mathbb G,\mathbf V\in\mathbb G^m;\quad\mathbf v,\mathbf \gamma\in \Z_p^m):\forall j\in[m],V_j=h^{\gamma_j}\cdot g^{v_j} \wedge v_j\in[0,2^n-1] \big\} $$

不难看出，上述就是将4.1节中关系1重复$m$次

对于聚合的范围证明，需要修改4.1中图1的式41，具体而言，Prover需要计算一个长度为$n\cdot m$的$\mathbf a_L$如下（单个范围证明的$\mathbf a_L$度为$n$）

$$ \langle \mathbf 2^n,\mathbf a_L[(j-1)\cdot n:j\cdot n-1] \rangle=v_j\quad \forall j\in[m] $$

不难看出，新的$\mathbf a_L$就是$m$个独立的$\mathbf a_L$的拼接

然后还需要修改多项式$\mathbf l,\mathbf r$如下

$$ \begin{aligned} l(X)&=(\mathbf a_L-z\cdot \mathbf 1^{n\cdot m})+\mathbf s_L\cdot X\\ r(X)&=\mathbf y^{n\cdot m}\circ(\mathbf a_R+z\cdot \mathbf1^{n\cdot m}+\mathbf s_R\cdot X)+\sum_{j=1}^mz^{1+j}\cdot \big( \mathbf 0^{(j-1)\cdot n} ||\mathbf 2^n||\mathbf 0^{(m-j)\cdot n}\big)\\ \end{aligned} $$

对应的承诺值$P$修改为

$$ P=AS^x\cdot \mathbf g^{-z}\cdot \mathbf h'^{z\cdot \mathbf y^{n\cdot m}}\cdot \prod ^m_{j=1}\cdot \mathbf h'^{z^{j+1}\cdot \mathbf 2^n}_{[(j-1)\cdot n:j\cdot n-1]} $$

对应的$\delta$修改也要修改

$$ \delta(y,z)=(z-z^2)\cdot \lang \mathbf 1^{n\cdot m} ,\mathbf y^{n\cdot m}\rang-\sum^m_{j=1}z^{j+2}\cdot \lang \mathbf 1^n,\mathbf 2^n \rang $$

因为需要聚合$m$个证明，因此需要将原来的$\tau_x$修改为$\tau_x=\tau_1\cdot x+\tau_2\cdot x_2+\sum^m_{j=1}z^{1+j}\cdot \gamma_j$

此时图3中的验证等式（式65）修改为

$$ g^{\hat t}\cdot h^{\tau_x}=g^{\delta(y,z)}\cdot \mathbf V^{z^2\cdot \mathbf z^m}\cdot T_1^x\cdot T_2^{x^2} $$

4.4 Non-Interactive Proof through Fiat-Shamir

注意到上面的协议中的Verifier是公共掷币的，所有诚实Verifier的消息均来自于$\Z^*_p$中的随机元素，因此可以利用FS变换将其转变为随机预言机模型中的非交互式零知识方案

如果说希望实现无需可信设置的方案，则可以用Hash函数$H:\{0,1\}^*\rarr\mathbb G$来生成公共参数$\mathbf g,\mathbf h,g,h$

4.5 A Simple MPC Protocol for Bulletproofs

这里介绍一个简单的MPC协议

考虑一个场景，Prover可能包含多个参与方，没个参与方都希望构造一个范围证明，比如CoinJoin等应用，如果采用传统的MPC协议，每个参与方的计算卡小都不小，而且通信开销也会很大

这里可以考虑采用Bulletproof来构造一个简单的MPC协议，且几乎不需要对Prover进行什么修改

前面提到了，聚合的范围证明中，每个范围证明相互独立，互相之间的输出不受影响，这意味着$m$个参与方中，没个参与方都可以构造一个对应于承诺值$V_k$的Bulletproof，此时协议的轮数为常数，但是通信量仍然与$m$和范围的大小有关，或者可以做一些权衡，让协议执行对数轮数，但是通信量仅与$m$有关

相关的MPC方案思路可以看原文

4.6 Perfectly Binding Commitments and Proofs

Bulletproof和现有的用于CT的范围证明一样都是计算绑定的，可攻破DLOG假设的敌手也可以伪造一个可通过验证的范围证明，此外承诺是完美隐藏的，因此Bulletproof是完美零知识的，敌手无法知道承诺值

已知承诺方案不可能同时是完美绑定和完美隐藏的，因此设计承诺方案和证明系统时，需要权衡两者的重要性，对于加密货币而言，绑定性比隐藏性更重要，可攻破绑定性或证明系统合理性的敌手意味着其可以凭空创造币，导致加密货币系统失效，因此放弃交易的隐私性带来的危害要相对小一些，因为交易的发送方或账户的持有者在最坏情况下也会遭殃

高效的系统依赖于一个由单一群元素生成的向量承诺，根据定义，完美绑定的承诺方案的大小至少和消息长度相当，这意味着无法压缩，$[GH98,GVW02]$表示通常而言，除非复杂性理论取得突破性进展，否则交互式证明系统的通信量不可能小于证据长度

对于经典计算机而言，DLOG假设仍然成立，但是对量算不成立，这意味着敌手可以利用量算随意创造一个完美隐藏的UTXO，为了防止此类攻击，可以利用$[RM]$的方案确保证明只是计算绑定的，随后在转换到一个完美绑定的系统来抵抗量子敌手

为了做到这点，Prover只需要公开$g^\gamma$，此时Pedersen承诺退化为ElGamal承诺，R和M同时证明了对于小的消息空间无法使得计算有界的Prover构造一个承诺，使得计算无界的敌手将该承诺揭示为小空间内不同的消息

注意到目前为止提到的承诺方案都是计算隐藏的，但是还是可以用于抗量子的范围证明，简洁的抗量子范围证明目前仍然是开放问题，但是只需要一点小小的更改就可，$[PBF+]$可以做到统计合理性，本文建议利用ElGamal承诺替代原来协议中每个步骤采用的Pedersen承诺，ElGamal承诺实际上只是将Pedersen承诺中的随机性替换为$g^r$，若同一个$g^r$用于多个范围证明，则还有优化空间，为了确保隐藏性，不同的证明必须采用不同的$h$

5 Zero-Knowledge Proof for Arithmetic Circuits

本文基于$[BCC+16]$的方案提出了对哈达玛积关系的证明，扇入为2的乘法门分为左右两个输入导线，用向量$\boldsymbol a_L$标记每个乘法门的左输入，$\boldsymbol a_R$为右输入向量，$\boldsymbol a_O=\boldsymbol a_L\circ \boldsymbol a_R$为输出向量（这里的$\mathbf a_L,\mathbf a_R$和上面的$\mathbf a_L$的含义不同，注意区分）

$[BCC+16]$展示了如何将具有$n$个乘法门的任意算术电路转换为包含上述哈达玛积的关系，且约数个数$Q\leq 2n$，形式如下

$$ <\boldsymbol W_{L,q},\boldsymbol a_L>+<\boldsymbol W_{R,q},\boldsymbol a_R>+<\boldsymbol W_{O,q},\boldsymbol a_O>=c_q $$

本文将承诺值$V_i$作为statement的一部分，并赋予协议更一般的关系，其中线性一致性约束表示$V_j$揭示的承诺值$v_j$​

出于方便，记$V_i$为Pedersen承诺，可将方案修改为$t(X)$并根据下列协议中的式90来验证，可适用于其他加法同态的方案

5.1 Inner-Product Proof for Arithmetic Circuits

利用内积证明来证明算术电路的主要思想是将哈达玛积关系和线性约束转换为单个内积关系

与范围证明类似，Prover可验证的生成哈达玛积和线性约束的随即线性组合，从而形成单个内积约束，若组合是由Verifier随机选择的，则本文的协议中内积约束以极高概率隐含其他的约束

5.2节中展示了内积关系可被高效的内积argument代替，其可以得到一个对任意电路的证明，其中输入导线可来自于Pedersen承诺，具体而言是下面这个关系

记$\boldsymbol W_V\in\mathbb Z_p^{Q\times m}$为承诺$V_j$的权重，现有的证明系统只针对哪些$\boldsymbol W_V$是列线性无关的（rank m的矩阵），这种限制很弱，因此可以将满足这些线性相关的约束的承诺构造为其他承诺的同态组合

比如考虑向量$\boldsymbol w'_V=\boldsymbol a\cdot \boldsymbol W_V\in \mathbb Z^m_p$，我们想构造承诺$V'=v^{\boldsymbol a\cdot \boldsymbol W_v}$，注意到如果关系成立，我们可以得到$<\boldsymbol w_{L,j},\boldsymbol a_L>+<\boldsymbol w_{R,j},\boldsymbol a_R>+<\boldsymbol w_{O,j},\boldsymbol a_O>=<\boldsymbol w'_{V},\boldsymbol v>+\boldsymbol c$，具体可以看Protocol 3，该协议分为两部分，Prover先对$l(X),r(X),t(X)$承诺，之后第二部分中Prover使Verifier相信这些多项式正确且满足$<l(X),r(X)>=t(X)$

  • Theorem 4：Protocol 3的证明系统有完美完备性，完美诚实验证者零知识性和计算证据扩展评估

5.2 Logarithmic-Sized Protocol

对于范围证明，我们可采用内积Argument来降低协议的通信量，具体而言是将(82)中修改为简单的$\tau_x,\mu,.\hat t$，然后让Prover和Verifier在公共输入$(\boldsymbol g,\boldsymbol h',P\cdot h^{-\mu},\hat t)$上执行一个内积Argument，注意到statemen的证明当嫁与验证等式(88)和(92)，内积Argument只有对数阶通信复杂度，因此其是高效的

Protocol 3第一部分：计算l,r,t的承诺
Protocol 3第一部分：计算l,r,t的承诺

Protocol 3第二部分：检查t=<l,r>
Protocol 3第二部分：检查t=<l,r>

注意到传输$\boldsymbol l,\boldsymbol r$只需要$2\lceil \log n\rceil+2$的通信量，此时协议中Prover总共需要发送$2\lceil \log n\rceil+8$个群元素和5个$\mathbb Z_p$上元素

利用FS启发式可以将协议转换为高效非交互式的，具体可以看原文的第六节

总结

论文提出 Bul­let­proof 协议，一种新的 ZKP-Ar­gu­ment of Knowl­edge，用于证明一个秘密承诺值在一个给定的区间内，BUl­let­proof 无需可信设置，且仅依赖于离散对数假设，利用 Fiat-Shamir 启发式来消除交互性

Bul­let­proof 基于 Boo­tle 等人的工作$[4]$，该工作提出了一个通信高效的 ZKP，本文对该工作进行了优化，将通信效率减少为原来的 1/​3，同时我们让 Bul­let­proof 适用于关于承诺值的陈述，包括范围证明，可验证的洗牌（shuf­fle）和其他一些应用

该方案的优点有很多，首先是需要的群或域元素的数量是对数阶，即便是对于证明的聚合也是对数阶，此外方案仅依赖于离散对数假设，且无需可信设置，这对去中心化系统和加密货币很友好

Bul­let­proof 协议还可以结合一个简单的 MPC 协议来实现证明的聚合，简单来说就是允许多个拥有秘密承诺值的参与方共同给生成一个小的范围证明来证明他们的秘密承诺值且不会泄露这个秘密值，利用 MPC 协议可以做到常数轮的交互和线性阶的通信量，或者是将通信量降低至对数阶，但是需要对数阶的交互轮次，且当 CT 读取多个参与方的输入时，MPC 协议可用于将构造事务所需要的所有证明聚合为一个短证明

总的来说 Bul­let­proof 可以用于解决加密货币中敏感信息的保密性，比如对 Sender、Re­ceiver 和交易金额等信息的隐藏

References

$[1]$ Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Gregory Maxwell: Bulletproofs: Short Proofs for Confidential Transactions and More. IEEE Symposium on Security and Privacy 2018: 315-334

$[2]$ Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Gregory Maxwell: Bulletproofs: Short Proofs for Confidential Transactions and More. IACR Cryptol. ePrint Arch. 2017: 1066
2017

$[3]$ 关于 bulletproof 中的范围证明的一些整理和思考_jzchu 的博客 - CSDN 博客_范围证明

$[4]$ Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 327–357. Springer, 2016.

$[5]$ 零知识证明比较

$[6]$ 比较零知识证明算法 zkSNARK,zkSTARKs,zkBoo,Sonic,BulletProofs