Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger学习笔记

1. 引言

Chung等人2020年论文《Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger》，暂无收录信息。

代码实现参见：

• https://github.com/ZenGo-X/bulletproofs

要点：
1）实现了zero-knowledge inner product proof，proof size为$2\lceil {\log }_2(n)\rceil +2$ 个elements in $\mathbb{G}$和$3$个elements in ${\mathbb{Z}}_p$。Bulletproofs中的non-zero-knowledge inner product proof size为$2\lceil {\log }_2(n)\rceil$ 个elements in $\mathbb{G}$和$2$个elements in ${\mathbb{Z}}_p$。
2）Bulletproofs+ 构建的range proof size为$2{\log }_{2}n+3$个elements in $\mathbb{G}$和$3$个elements in ${\mathbb{Z}}_p$。而Bulletproofs中的range proof size为$2{\log }_{2}n+4$个elements in $\mathbb{G}$和$5$个elements in ${\mathbb{Z}}_p$。Bulletproofs+比Bulletproofs算法的communication cost节约$1$个$\mathbb{G}$和$2$个${\mathbb{Z}}_p$。
3）Bulletproofs+ 构建的aggregate range proof size为$2\lceil {\log }_2(n\cdot m)\rceil +3$个elements in $\mathbb{G}$和$3$个elements in ${\mathbb{Z}}_p$。而Bulletproofs中的range proof size为$2\lceil {\log }_2(n\cdot m)\rceil +4$个elements in $\mathbb{G}$和$5$个elements in ${\mathbb{Z}}_p$。Bulletproofs+比Bulletproofs算法的communication cost节约$1$个$\mathbb{G}$和$2$个${\mathbb{Z}}_p$。

本文为range proof和arithmetic circuit提供了无需trusted setup的zero-knowledge argument，proof size为当前最短的。以prove a committed values is positive integer less than 64 bits为例，128-bit security情形下，proof size为576 byte，大约为Bulletproofs的85.7%，而Prover 和 Verifier的计算开销与Bulletproofs相当。

Bulletproofs的精髓在于 logarithmic inner product argument with no zero-knowledge，本文重温了Groth 2009年论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》，对Bulletproofs进行了改进，形成了Bulletproofs+。Bulletproofs+中的核心元素为：zero-knowledge weighted inner product argument (zk-WIP)。借助zk-WIP，可减小range proof和arithmetic circuit proof的proof size，从而降低transmission cost。zk-WIP具有inner product argument的所有nice features，如支持aggregate range proof以及支持batch verification。

在分布式账本中，非常需要 short NIZK without a trusted setup。
2018年 B¨unz等人 在 2016年Bootle等人《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》论文的基础上 提出了《Bulletproofs: Short Proofs for Confidential Transactions and More》，基于Bulletproofs构建的range proof的proof size要远远短于其它需要trusted setup的range proof NIZK。

相关研究成果：

• 2009年Groth论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》为第一个sublinear zero-knowledge argument for linear algebra。（参见博客 Linear Algebra with Sub-linear Zero-Knowledge Arguments学习笔记）
• 2016年Bootle等人《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》是第一个实现了logarithmic communication complexity的（$O(4\log N+7)+O(2\log N+6)$）。（参见博客 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting 学习笔记）
• B¨unz等人2018年论文《Bulletproofs: Short Proofs for Confidential Transactions and More》在Bootle 2016基础上进行了改进，proof size缩短了3倍（$O(2\log N+9)$）。（参见博客 Bulletproofs: Short Proofs for Confidential Transactions and More 学习笔记）
• Hoffmann 等人 2019年论文 qesa《Efficient zero-knowledge arguments in the discrete log setting》 在Bulletproofs的基础上进行了改进，将inner product 理解为 vector-vector multiplication，从而扩展至了matrix-vector multiplication argument，使得R1CS表示可转换为quadratic equation，进而可借助inner product argument来实现R1CS证明。尽管Hoffmann在该论文中improves Bulletproofs to efficiently cover more expressive relations than R1CS，但是并没有降低range proof的proof size。【看Hoffmann论文中Table 3的话，aggregate range proof的prove time和verify time有所提升。】（参见博客 qesa Efficient zero-knowledge arguments in the discrete log setting 学习笔记）
• Bu¨nz等人2020年论文 Supersonic《Transparent SNARKs from DARK Compilers》 中基于unknown order group构建了一种无需trusted setup的polynomial commitment——DARK，核心思想是将$f(X)$表示为$f(X)=f_L(X)+X^{d’+1}{f}_R(X)$，其中$d’=\lfloor \frac{d}{2}\rfloor$，$d$为$f(X)$多项式的degree。并基于DARK提出了首个succinct NIZK without trusted setup——Supersonic。
  尽管Supersonic具有low verification cost和short proof size的优势，但是它需要的proof size至少为Bulletproofs的6倍（128-bit security level下），且随着security level的提升，proof size差距会更大。。
  （参见博客 Supersonic Transparent SNARKs from DARK Compilers学习笔记）

Bulletproofs具有 trustless feature和short proof size，目前有不同的代码实现：

• https://github.com/bbuenz/BulletProofLib （Java）
• https://github.com/dalek-cryptography/Bulletproofs （Rust）
• https://github.com/mimblewimble/rust-secp256k1-zkp （Rust）
• https://github.com/ing-bank/zkrp/tree/master/bulletproofs （Go）
• https://github.com/apoelstra/secp256k1-mw/tree/bulletproofs （C）
• https://github.com/monero-project/monero/tree/master/src/ringct （C++）

本文提出的Bulletproofs+，在Bulletproofs的基础上进行了改进，具有更短的proof size。当前NIZK without trusted setup中，Bulletproofs+实现的proof的size最短。
Bulletproofs+和Bulletproofs在不同bit range proof下的proof size对比如下图所示：（$\times 0.8\sim 0.857$）

Bulletproofs中的关键元素是inner product argument without zero-knowledge。
而2009年Groth论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》和Bulletproofs+ 的主要元素是 zero-knowledge weighted inner product argument (zk-WIP)，可用于减少range proof和arithmetic circuit proof的proof size。

• 2009年Groth论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中提出了efficient reductions from the advanced arguments to the inner product argument。
• 2016年Bootle等人《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》 和 B¨unz等人2018年论文《Bulletproofs: Short Proofs for Confidential Transactions and More》 在Groth 2009论文的基础上，以增加prover和verifier之间的交互次数为代价，降低了proof size。由于可基于Fiat-Shamir heuristic in the random oracle model实现non-interactive argument，所以交互次数的增加并不会称为负担。

2009年Groth论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中，关注bilinear map有2种：（参见博客 Linear Algebra with Sub-linear Zero-Knowledge Arguments学习笔记 第3节内容。）

• 标准的dot product of vectors (标准的inner product)为：$\vec{x}\ast \vec{y}=\vec{x}{\vec{y}}^T$。
• Weighted inner product (WIP) 为：$\vec{x}\ast \vec{y}=\vec{x}(\vec{y}\circ \vec{t}{)}^T$，其中$\vec{t}\in {\mathbb{Z}}_p^n$为由Verifier选择的public vector。

本文采用不同的符号${⨀}_c$来表示Weighted inner product (WIP)：（For a constant vector $\vec{c}\in {\mathbb{Z}}_p^n$）
${⨀}_c:{\mathbb{Z}}_p^n\times {\mathbb{Z}}_p^n\to {\mathbb{Z}}_p$
$(\vec{a},\vec{b})\to <\vec{a},<\vec{c}\circ \vec{b}>>$
其中$<,>$表示标准的inner product，$\circ$表示component-wise product （又称为Hadamard product）。

WIP (weighted inner product) argument 的一个核心作用是可用于batch several equations so that the communication overhead is reduced。如，Hadamard product $\vec{a}\circ \vec{b}=\vec{c}\in {\mathbb{Z}}_p^n$ 为a set of $n$个方程式，通过引入随机数$y$，可合成为一个方程式：
$<\vec{a},(y,y^2,\cdots ,y^n)\circ \vec{b}>=<\vec{c},(y,y^2,\cdots ,y^n)>\in {\mathbb{Z}}_p^n$ …… (1)

为了证明$\vec{a}\circ \vec{b}=\vec{c}\in {\mathbb{Z}}_p^n$成立，可转换为证明上述方程式（1）成立。方程式（1）的左右两侧可看成是对应coefficient vector $(y,y^2,\cdots ,y^n)$ 的WIP。此时需要一个高效的WIP argument算法。

• 2009年Groth论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中，其zero-knowledge argument for weighted inner product (zk-WIP)的communication cost为$O(2n)$，即具有linear communication overhead，该zk-WIP是其它linear algebra equations的advanced arguments的ingredient protocol。（参见博客 Linear Algebra with Sub-linear Zero-Knowledge Arguments学习笔记 第4.1节内容）

• 2016年Bootle等人《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》 和 B¨unz等人2018年论文《Bulletproofs: Short Proofs for Confidential Transactions and More》种，将inner product argument without zero-knowledge 作为ingredient protocol，通过将circuit satisfiability等advanced relation reduce为inner product argument，也可实现zero-knowledgeness。（尽管其inner product argument不具有zero-knowledge，但是可以在reduce之前添加hiding变量，实现总体argument的zero-knowledge。）

• 2018年Wahby等人论文《Doubly-efficient zkSNARKs without trusted setup》中，为inner product between a hidden vector and a public vector 实现了logarithmetic zero-knowledge argument。不同于2009年Groth论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中的（weighted） inner product between two hidden vectors。（参见博客 Hyrax: Doubly-efficient zkSNARKs without trusted setup学习笔记 第4节“Dot-prodcut proof protocol” 内容。）

• Hoffmann 等人 2019年论文 qesa《Efficient zero-knowledge arguments in the discrete log setting》中，借助kernel guideline来引入特定的随机变量$\vec{r}’,\vec{r}’’$来实现hiding，从而实现(almost) zero-knowledge inner product argument ——$IP{A}_{almZK}$协议。qesa中为了blind witness vectors，其所使用的random vectors需依赖于witness，从而bring some constraint for the witness。（参见博客 qesa Efficient zero-knowledge arguments in the discrete log setting 学习笔记 第5.4节内容“zero-knowledge inner product argument”）

目前来看，当WIP的两个input vectors都是hidden时，目前暂无concrete construction for logarithmic WIP proof protocol with full zero-knowledge。

Bootle 2016和B¨unz 2018 中可实现logarithmic inner product argument的核心是利用了inner product的bilinearity。
如，假设$n=2\hat{n}$为偶数，$\vec{a}=({\vec{a}}_1,{\vec{a}}_2),\vec{b}=({\vec{b}}_1,{\vec{b}}_2)\in {\mathbb{Z}}_p^{\hat{n}}\times {\mathbb{Z}}_p^{\hat{n}}$，则有：
$<\vec{a},\vec{b}>=<{\vec{a}}_1,{\vec{b}}_1>+<{\vec{a}}_2,{\vec{b}}_2>$ …… (2)
即inner product 可表示为2个half-length inner products之和。

WIP也是a bilinear map，具有类似的属性，当$\vec{c}=(y,y^2,\cdots ,y^n){\mathbb{Z}}_p^n$为Vandermonde vector时，有：
$\vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}={\vec{a}}_1{⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_1+(y^{\hat{n}}\overrightarrow{a_2}){⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_2$ …… (3)

引入random challenge $e$ 有：
$(e{\vec{a}}_1+e^{-1}{y}^{\hat{n}}\overrightarrow{a_2}){⨀}_{(y,\cdots ,y^{\hat{n}})}(e{\vec{b}}_2+e^{-1}{\vec{b}}_1)=e^2{\vec{a}}_1{⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_2+\vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}+e^{-2}(y^{\hat{n}}\overrightarrow{a_2}){⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_1$ …… (4)
即：
$c^{\prime }={\vec{a}}^{\prime }{⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}^{\prime }=e^2{c}_L+c+e^{-2}{c}_R$，其中$c=\vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}$，$c_L={\vec{a}}_1{⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_2\in {\mathbb{Z}}_p$，$c_R=(y^{\hat{n}}\overrightarrow{a_2}){⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_1\in {\mathbb{Z}}_p$，${\vec{a}}^{\prime }=(e{\vec{a}}_1+e^{-1}{y}^{\hat{n}}\overrightarrow{a_2})\in {\mathbb{Z}}_p^{\hat{n}}$，${\vec{b}}^{\prime }=(e{\vec{b}}_2+e^{-1}{\vec{b}}_1)\in {\mathbb{Z}}_p^{\hat{n}}$。

使用$\vec{g},\vec{h}\in {\mathbb{G}}^n$对$\vec{a},\vec{b},c=\vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}$进行commit有：
$P={\vec{g}}^{\vec{a}}{\vec{h}}^{\vec{b}}{u}^c$
使用${\vec{g}}^{\prime },{\vec{h}}^{\prime }\in {\mathbb{G}}^{\hat{n}}$对$c’$进行commit，应保持与上述类似的结构：
$P^{\prime }={\vec{g}}^{\prime {\vec{a}}^{\prime }}{\vec{h}}^{\prime {\vec{b}}^{\prime }}{u}^{c^{\prime }}={\vec{g}}^{\prime (e{\vec{a}}_1+e^{-1}{y}^{\hat{n}}\overrightarrow{a_2})}{\vec{h}}^{\prime (e{\vec{b}}_2+e^{-1}{\vec{b}}_1)}{u}^{e^2{c}_L+c+e^{-2}{c}_R}$
在上述$P’$的计算公式中，结合commitment的同态属性，可设置：
${\vec{g}}^{\prime }={\vec{g}}_1^{e^{-1}}{\vec{g}}_2^{e{y}^{-\hat{n}}}\in {\mathbb{G}}^{\hat{n}}$
${\vec{h}}^{\prime }={\vec{h}}_1^e{\vec{h}}_2^{e^{-1}}\in {\mathbb{G}}^{\hat{n}}$
从而有：
$P^{\prime }=L^{e^2}P{R}^{e^{-2}}\in \mathbb{G}$，其中$L={\vec{g}}_2^{-y^{\hat{n}}{\vec{a}}_1}{\vec{h}}_1^{{\vec{b}}_2}{u}^{c_L}\in \mathbb{G}$，$R={\vec{g}}_1^{y^{\hat{n}}{\vec{a}}_2}{\vec{h}}_2^{{\vec{b}}_1}{u}^{c_R}\in \mathbb{G}$。

2. 基于Bulletproofs 构建的weighted inner product argument (不具有zero-knowledge)

WIP信息可由：

• public info: $y,c\in {\mathbb{Z}}_p,A,B\in \mathbb{G},\vec{g},\vec{h}\in {\mathbb{G}}^n$
• private info：$\vec{a},\vec{b}\in {\mathbb{Z}}_p^n$
• relation：$A={\vec{g}}^{\vec{a}}\wedge B={\vec{h}}^{\vec{b}}\wedge \vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}=c$

进一步等价表示为：

• public info: $y\in {\mathbb{Z}}_p,u,P\in \mathbb{G},\vec{g},\vec{h}\in {\mathbb{G}}^n$
• private info：$\vec{a},\vec{b}\in {\mathbb{Z}}_p^n$
• relation：$P={\vec{g}}^{\vec{a}}{\vec{h}}^{\vec{b}}{u}^{\vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}}$

与Bulletproofs中的inner product argument类似，在不考虑zero-knowledge的情况下， 构建logarithmic WIP argument w.r.t. $(y,\cdots ,y^n)\in {\mathbb{Z}}_p^n$的直观思路为：
– 1. 若$n=1$：

• Prover：将$a,b\in {\mathbb{Z}}_p$ 发送给Verifier；
• Verifier：计算$c=a\cdot b\cdot y$，然后验证$P=g^a{h}^b{u}^c$成立即可。

– 2. 若$n>1$：【主要为公式（4）服务。】

• Prover：
  a) 计算$\hat{n}=\frac{n}{2}$，$\vec{a}=({\vec{a}}_1,{\vec{a}}_2),\vec{b}=({\vec{b}}_1,{\vec{b}}_2),\vec{g}=({\vec{g}}_1,{\vec{g}}_2),\vec{h}=({\vec{h}}_1,{\vec{h}}_2)\in {\mathbb{Z}}_p^{\hat{n}}\times {\mathbb{Z}}_p^{\hat{n}}$。
  b）计算$c_L={\vec{a}}_1{⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_2\in {\mathbb{Z}}_p$，$c_R=(y^{\hat{n}}\overrightarrow{a_2}){⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_1\in {\mathbb{Z}}_p$。
  c）计算$L={\vec{g}}_2^{{\vec{a}}_1}{\vec{h}}_1^{{\vec{b}}_2}{u}^{c_L}\in \mathbb{G}$，$R={\vec{g}}_1^{y^{\hat{n}}\overrightarrow{a_2}}{\vec{h}}_2^{{\vec{b}}_1}{u}^{c_R}\in \mathbb{G}$。
  d）Prover将$L,R\in \mathbb{G}$发送给Verifier。
• Verifier：生成随机数$e\in {\mathbb{Z}}_p^{\ast }$，将随机数$e\in {\mathbb{Z}}_p^{\ast }$发送给Prover。
• Prover和Verifier：两者都计算：
  ${\vec{g}}^{\prime }={\vec{g}}_1^{e^{-1}}{\vec{g}}_2^{e{y}^{-\hat{n}}}\in {\mathbb{G}}^{\hat{n}}$
  ${\vec{h}}^{\prime }={\vec{h}}_1^e{\vec{h}}_2^{e^{-1}}\in {\mathbb{G}}^{\hat{n}}$
  $P^{\prime }=L^{e^2}P{R}^{e^{-2}}\in \mathbb{G}$
• Prover计算：
  ${\vec{a}}^{\prime }=(e{\vec{a}}_1+e^{-1}{y}^{\hat{n}}\overrightarrow{a_2})\in {\mathbb{Z}}_p^{\hat{n}}$
  ${\vec{b}}^{\prime }=(e{\vec{b}}_2+e^{-1}{\vec{b}}_1)\in {\mathbb{Z}}_p^{\hat{n}}$

– 3. 设置$\vec{g}=\vec{g}’,\vec{h}=\vec{h}’,u=u,P=P’,\vec{a}=\vec{a}’,\vec{b}=\vec{b}’,n=\hat{n}$，然后继续调用步骤1.。

3. zero-knowledge weighted inner product argument (具有zero-knowledge)

在本博文第2节 “基于Bulletproofs 构建的weighted inner product argument (不具有zero-knowledge)” 的基础上，Prover引入了随机数$\alpha \in {\mathbb{Z}}_p$和commitment key $v\in \mathbb{G}$来对$P$进行hiding。

zero-knowledge weighted inner product 基本信息为：

• public info: $y\in {\mathbb{Z}}_p,u,v,P\in \mathbb{G},\vec{g},\vec{h}\in {\mathbb{G}}^n$
• private info：$\vec{a},\vec{b}\in {\mathbb{Z}}_p^n,\alpha \in {\mathbb{Z}}_p$
• relation：$P={\vec{g}}^{\vec{a}}{\vec{h}}^{\vec{b}}{u}^{\vec{a}{⨀}_{(y,\cdots ,y^n)}\vec{b}}{v}^{\alpha }$

借鉴sigma protocol思想来证明：（可参见博客 基于Sigma protocol实现的零知识证明protocol集锦 2.4节“Protocol 4. Knowledge of the opening of Pedersen commitment”）
注意，巧妙之处在于仅在最后一轮（$n=1$时）借鉴sigma protocol引入了$A,B\in \mathbb{G}$来证明，其它阶段都是Prover自身在每轮中引入随机数$d_L,d_R\in {\mathbb{Z}}_p$来实现$L,R$的hiding。

详细的zk-WIP argument思路为：【总的proof size为$2{\log }_2(n)+5$ field or group elements。】
– 1. 若$n=1$：【2个group elements和3个field elements】
此时的基本信息为：
public info：$g,h,u,v,P\in \mathbb{G},P\in \mathbb{G},y\in {\mathbb{Z}}_p$
private info：$a,b,\alpha \in {\mathbb{Z}}_p$
relation：$P=g^a{h}^b{u}^{a\cdot b\cdot y}{v}^{\alpha }$
* Prover：将$a,b\in {\mathbb{Z}}_p$ 发送给Verifier；
* Verifier：计算$c=a\cdot b\cdot y$，然后验证$P=g^a{h}^b{u}^c$成立即可。

借鉴sigma protocol思想，实现可为：

• Prover：引入私有随机数$r,s,\delta ,\eta \in {\mathbb{Z}}_p$，其中$\eta$用于hiding $r,s$。
  计算$A=g^r{h}^s{u}^{(rb+sa)y}{h}^{\delta }\in \mathbb{G},B=g^{rsy}{h}^{\eta }\in \mathbb{G}$。
  将$A,B\in \mathbb{G}$ 发送给Verifier。
• Verifier：生成随机数$e\in {\mathbb{Z}}_p^{\ast }$，将随机数$e\in {\mathbb{Z}}_p^{\ast }$发送给Prover。
• Prover：计算
  $r^{\prime }=r+a\cdot e\in {\mathbb{Z}}_p$
  $s^{\prime }=s+b\cdot e\in {\mathbb{Z}}_p$
  ${\delta }^{\prime }=\eta +\delta \cdot e+\alpha \cdot e^2\in {\mathbb{Z}}_p$
  将$r^{\prime },s^{\prime },{\delta }^{\prime }\in {\mathbb{Z}}_p$ 发送给Verifier。
• Verifier：验证 $P^{e^2}{A}^{e}B=g^{r^{\prime }\cdot e}{h}^{s^{\prime }\cdot e}{u}^{r^{\prime }{s}^{\prime }y}{v}^{{\delta }^{\prime }}$是否成立即可。

– 2. 若$n>1$：【主要为公式（4）服务。】

• Prover：
  a) 计算$\hat{n}=\frac{n}{2}$，$\vec{a}=({\vec{a}}_1,{\vec{a}}_2),\vec{b}=({\vec{b}}_1,{\vec{b}}_2),\vec{g}=({\vec{g}}_1,{\vec{g}}_2),\vec{h}=({\vec{h}}_1,{\vec{h}}_2)\in {\mathbb{Z}}_p^{\hat{n}}\times {\mathbb{Z}}_p^{\hat{n}}$。
  b）计算$c_L={\vec{a}}_1{⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_2\in {\mathbb{Z}}_p$，$c_R=(y^{\hat{n}}\overrightarrow{a_2}){⨀}_{(y,\cdots ,y^{\hat{n}})}{\vec{b}}_1\in {\mathbb{Z}}_p$。
  c）引入Prover私有随机数$d_L,d_R\in {\mathbb{Z}}_p$， 计算$L={\vec{g}}_2^{{\vec{a}}_1}{\vec{h}}_1^{{\vec{b}}_2}{u}^{c_L}{v}^{d_L}\in \mathbb{G}$，$R={\vec{g}}_1^{y^{\hat{n}}\overrightarrow{a_2}}{\vec{h}}_2^{{\vec{b}}_1}{u}^{c_R}{v}^{d_R}\in \mathbb{G}$。
  d）Prover将$L,R\in \mathbb{G}$发送给Verifier。
• Verifier：生成随机数$e\in {\mathbb{Z}}_p^{\ast }$，将随机数$e\in {\mathbb{Z}}_p^{\ast }$发送给Prover。
• Prover和Verifier：两者都计算：
  ${\vec{g}}^{\prime }={\vec{g}}_1^{e^{-1}}{\vec{g}}_2^{e{y}^{-\hat{n}}}\in {\mathbb{G}}^{\hat{n}}$
  ${\vec{h}}^{\prime }={\vec{h}}_1^e{\vec{h}}_2^{e^{-1}}\in {\mathbb{G}}^{\hat{n}}$
  $P^{\prime }=L^{e^2}P{R}^{e^{-2}}\in \mathbb{G}$
• Prover计算：
  ${\vec{a}}^{\prime }=(e{\vec{a}}_1+e^{-1}{y}^{\hat{n}}\overrightarrow{a_2})\in {\mathbb{Z}}_p^{\hat{n}}$
  ${\vec{b}}^{\prime }=(e{\vec{b}}_2+e^{-1}{\vec{b}}_1)\in {\mathbb{Z}}_p^{\hat{n}}$
  ${\alpha }^{\prime }=d_L\cdot e^2+\alpha +d_R\cdot e^{-2}$

– 3. 设置$\vec{g}={\vec{g}}^{\prime },\vec{h}={\vec{h}}^{\prime },u=u,P=P^{\prime },\vec{a}={\vec{a}}^{\prime },\vec{b}={\vec{b}}^{\prime },n=\hat{n}$，设置$\alpha ={\alpha }^{\prime }$ ，然后继续调用步骤1.。

4. 基于zk-WIP argument构建的range proof

参看博客 Bulletproofs: Short Proofs for Confidential Transactions and More学习笔记 第4.1节 “将range proof转换为inner product between two vectors” 内容，Bulletproofs通过在vector polynomials inner product $\vec{l}(X),\vec{r}(X)\in {\mathbb{Z}}_p^n[X]$ 中引入随机变量${\vec{s}}_L,{\vec{s}}_R\in {\mathbb{Z}}_p^n$来实现hiding，从而实现zero knowledge range proof。

range proof的基本信息为：

• public info：$g,h\in \mathbb{G},V\in \mathbb{G},n$
• private info：$v,\gamma \in {\mathbb{Z}}_p$
• relation：$V=h^{\gamma }{g}^v\wedge v\in [0,2^n-1]$

将数值$v$以二进制位表示为 a ⃗ L = ( a 1 , ⋯ , a n ) ∈ { 0 , 1 } n \vec{a}_L=(a_1,\cdots,a_n)\in\{0,1\}^n a L​=(a1​,⋯,an​)∈{0,1}n，则有$<{\vec{a}}_L,{\vec{2}}^n>=v$，其中${\vec{2}}^n=(1,2,4,\cdots ,2^{n-1})$。同时也得保证${\vec{a}}_L$中的每个元素值均只能位0或者1，可表示为：
${\vec{a}}_L-{\vec{a}}_R={\vec{1}}^n\in {\mathbb{Z}}_p^n\wedge {\vec{a}}_L\circ {\vec{a}}_R={\vec{0}}^n\in {\mathbb{Z}}_p^n\wedge <{\vec{a}}_L,{\vec{2}}^n>=v\in {\mathbb{Z}}_p$

以上对应为$2n+1$个方程式，可引入random challenge $y,z\in {\mathbb{Z}}_p$，将这$2n+1$个方程式batch在一起形成1个weighted inner product equation：

• Verifier 发送random challenge $y\in {\mathbb{Z}}_p$， $y\in {\mathbb{Z}}_p^{\ast }$，${\vec{y}}^n=(y,y^2,\cdots ,y^n),{\overleftarrow{y}}^n=(y^n,y^{n-1},\cdots ,y)$，从而有${\vec{y}}^n\circ {\overleftarrow{y}}^n=y^{n+1}\cdot {\vec{1}}^n$。
  $<\vec{a},\vec{b}>y^{n+1}=\vec{a}{⨀}_{{\vec{y}}^n}(\vec{b}\circ {\overleftarrow{y}}^n)$。则待证明的relation变为：
  – $<{\vec{a}}_L,{\vec{2}}^n>=v\Rightarrow {\vec{a}}_L{⨀}_{{\vec{y}}^n}({\vec{2}}^n\circ {\overleftarrow{y}}^n)=y^{n+1}v$
  – ${\vec{a}}_L-{\vec{a}}_R={\vec{1}}^n\Rightarrow ({\vec{a}}_L-{\vec{a}}_R){⨀}_{{\vec{y}}^n}{\vec{1}}^n={\vec{1}}^n{⨀}_{\vec{y}}{\vec{1}}^n=<{\vec{1}}^n,{\vec{y}}^n>$
  – ${\vec{a}}_L\circ {\vec{a}}_R={\vec{0}}^n\Rightarrow {\vec{a}}_L{⨀}_{{\vec{y}}^n}{\vec{a}}_R=0$

• Verifier发送random challenge $z\in {\mathbb{Z}}_p$，将以上三个relation组合在一起，合并为一个待证明的relation：
  注意，本博文以下内容是博主根据Bulletproofs的实现思路利用$z^2,z,1$进行linear combination，实际Bulletproofs+论文中，作者是利用$y^{n+1},z,1$进行linear combination。详情可参看：博主与论文作者的讨论
  以及 论文作者的博客解释。
  $z^2\cdot {\vec{a}}_L{⨀}_{{\vec{y}}^n}({\vec{2}}^n\circ {\overleftarrow{y}}^n)+z\cdot ({\vec{a}}_L-{\vec{a}}_R){⨀}_{{\vec{y}}^n}{\vec{1}}^n+{\vec{a}}_L{⨀}_{{\vec{y}}^n}{\vec{a}}_R=z^2{y}^{n+1}v+z\cdot <{\vec{1}}^n,{\vec{y}}^n>$
  将以上等式以weighted inner product表示有：
  $({\vec{a}}_L-{\vec{1}}^n\cdot z){⨀}_{{\vec{y}}^n}({\vec{a}}_R+z^2{\vec{2}}^n\circ {\overleftarrow{y}}^n+{\vec{1}}^n\cdot z)=z^2{y}^{n+1}v+(z-z^2)<{\vec{1}}^n,\overrightarrow{y^n}>-y^{n+1}{z}^3<{\vec{1}}^n,{\vec{2}}^n>$ …… (7)

利用commitment的同态属性，the commitments to inputs and output of WIP in Eq. (7) can be publicly calculated from public parameters and the commitment sent by the prover at the beginning of our range protocol。
Prover和Verifier都可运行相应的$zk-WIP$ protocol。

range proof的基本信息为：

• public info：$g,h\in \mathbb{G},V\in \mathbb{G},n$，$\vec{g},\vec{h}\in {\mathbb{G}}^n$
• private info：$v,\gamma \in {\mathbb{Z}}_p$
• relation：$V=h^{\gamma }{g}^v\wedge v\in [0,2^n-1]$

详细的range proof实现为：

• Prover：根据$v$，计算 a ⃗ L ∈ { 0 , 1 } n \vec{a}_L\in\{0,1\}^n a L​∈{0,1}n 使得 $<{\vec{a}}_L,{\vec{2}}^n>=v$，计算${\vec{a}}_R={\vec{a}}_L-{\vec{1}}^n\in {\mathbb{Z}}_p^n$ 使得 ${\vec{a}}_L\circ {\vec{a}}_R={\vec{0}}^n$。引入Prover私有随机变量$\alpha \leftarrow {\mathbb{Z}}_p$，对${\vec{a}}_L$和${\vec{a}}_R$进行hiding commit：$A={\vec{g}}^{{\vec{a}}_L}{\vec{h}}^{{\vec{a}}_R}{h}^{\alpha }\in \mathbb{G}$。
  将$A\in \mathbb{G}$发送给Verifier。

• Verifier：发送random challenge $y,z\in {\mathbb{Z}}_p$发送给Prover。

• Prover和Verifier：利用commitment的同态属性，都计算对$({\vec{a}}_L-{\vec{1}}^n\cdot z){⨀}_{{\vec{y}}^n}({\vec{a}}_R+z^2{\vec{2}}^n\circ {\overleftarrow{y}}^n+{\vec{1}}^n\cdot z)=z^2{y}^{n+1}v+(z-z^2)<{\vec{1}}^n,\overrightarrow{y^n}>-y^{n+1}{z}^3<{\vec{1}}^n,{\vec{2}}^n>$ 进行形如${\vec{g}}^{\vec{a}}{\vec{h}}^{\vec{b}}{g}^{\vec{a}{⨀}_{{\vec{y}}^n}}$的commitment （参见本博文第2节 “基于Bulletproofs 构建的weighted inner product argument (不具有zero-knowledge) “）：
  $\hat{A}={\vec{g}}^{({\vec{a}}_L-{\vec{1}}^n\cdot z)}{\vec{h}}^{({\vec{a}}_R+z^2{\vec{2}}^n\circ {\overleftarrow{y}}^n+{\vec{1}}^n\cdot z)}{g}^{z^2{y}^{n+1}v+(z-z^2)<{\vec{1}}^n,\overrightarrow{y^n}>-y^{n+1}{z}^3<{\vec{1}}^n,{\vec{2}}^n>}$
  利用commitment同态属性，有：
  $\hat{A}=A\cdot {\vec{g}}^{-z{\vec{1}}^n}\cdot {\vec{h}}^{z{\vec{1}}^n+z^2{\vec{2}}^n\circ {\overleftarrow{y}}^n}\cdot V^{z^2{y}^{n+1}}\cdot g^{(z-z^2)<{\vec{1}}^n-{\vec{y}}^n>-z^3{y}^{n+1}<{\vec{1}}^n,{\vec{2}}^n>}$

• Prover：计算：【使得满足$\hat{A}={\vec{g}}^{\widehat{{\vec{a}}_L}}{\vec{h}}^{\widehat{{\vec{a}}_R}}{g}^{\widehat{{\vec{a}}_L}{⨀}_{{\vec{y}}^n}\widehat{{\vec{a}}_R}}{h}^{\hat{\alpha }}$】
  $\widehat{{\vec{a}}_L}={\vec{a}}_L-{\vec{1}}^n\cdot z$
  $\widehat{{\vec{a}}_R}={\vec{a}}_R+z^2{\vec{2}}^n\circ {\overleftarrow{y}}^n+{\vec{1}}^n\cdot z$
  $\hat{\alpha }=\alpha +z^2{y}^{n+1}\gamma$

• Prover和Verifier：调用 $zk-WI{P}_{{\vec{y}}^n}(\vec{g},\vec{h},g,h,\hat{A};\widehat{{\vec{a}}_L},\widehat{{\vec{a}}_R},\hat{\alpha })$。【调用本博文第3节 “zero-knowledge weighted inner product argument (具有zero-knowledge) “】

Bulletproofs+ 构建的range proof size为$2{\log }_{2}n+3$个elements in $\mathbb{G}$和$3$个elements in ${\mathbb{Z}}_p$。而Bulletproofs中的range proof size为$2{\log }_{2}n+4$个elements in $\mathbb{G}$和$5$个elements in ${\mathbb{Z}}_p$。Bulletproofs+比Bulletproofs算法的communication cost节约$1$个$\mathbb{G}$和$2$个${\mathbb{Z}}_p$。

5. aggregated range proof

Monero is one of the well-known privacy-enhanced blockchain projects which employ confidential transactions in the UTXO model。其每个UTXO交易平均有2.5个outputs，为每个output配置range proof。Bulletproofs中的aggregate range proof将具有2个output交易的size由13kB降为了2.5kB，而Bulletproofs+的aggregate range proof将比Bulletproof 小96bytes。

基本实现思路与Bulletproofs的类似：

Bulletproofs+ 构建的aggregate range proof size为$2\lceil {\log }_2(n\cdot m)\rceil +3$个elements in $\mathbb{G}$和$3$个elements in ${\mathbb{Z}}_p$。而Bulletproofs中的range proof size为$2\lceil {\log }_2(n\cdot m)\rceil +4$个elements in $\mathbb{G}$和$5$个elements in ${\mathbb{Z}}_p$。Bulletproofs+比Bulletproofs算法的communication cost节约$1$个$\mathbb{G}$和$2$个${\mathbb{Z}}_p$。

6. verifiable shuffle

可利用Bulletproofs来实现 Bayer和Groth 2012年论文《Efficient zero-knowledge argument for correctness of a shuffle》中的permutation argument and the multi-exponentiation argument，从而实现logarithmic proof size of verifiable shuffle。
（参见博客 Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1））

7. 改进Bulletproofs的相关研究成果

与本文同期，针对Bulletproofs改进的相关研究成果有：

• Boneh等人论文《https://hackmd.io/@dabo/B1U4kx8XI》中提出了基于hiding polynomial commitment scheme构建的简单range proof。为了证明$0\le v<2^n$ with zero-knowledge property，需要2个degree为$n+1$的plynomial，然后执行3个polynomial evaluation protocol，Prover需要传输$2\cdot \lceil {\log }_2(n+2)\rceil +2$个elements in $\mathbb{G}$和5个elements in ${\mathbb{Z}}_p$。 尽管其communication cost要低于Bulletproofs，但是仍然比本文的range proof多一个 element。而且，由于其使用的polynomial commitment scheme，需要选择a prime $p$ larger than $n$，a prover can only claim the same interval once a polynomial commitment scheme is determined，否则a prover should renew the polynomial commitment scheme if the prover wants a new range。相反地，本文的range proof scheme支持任意的$n$值，所以there is no restriction for a prover。

• Attema和Cramer论文《 Compressed σ-protocol theory and practical application to plug & play secure algorithmics》则注重将Bulletproofs与$\sum$-protocol结合：A prover needs to prove quadratic equations for a range proof, however, $\sum$-protocol可用于证明任意的linear relations，需要将Bulletproofs改造为quadratic constraint，改造过程中可能存在技术难度，为了解决该问题，其使用了arithmetic secret sharing技术来linearize all non-linear statements，从而保证the same communication reduction。其构建的range proof，proof size为$2\cdot \lceil {\log }_2(2n+3)\rceil$个elements in $\mathbb{G}$和5个elements in ${\mathbb{Z}}_p$。由此可知，Bulletproofs+仍然是具有smallest proof size的transparent range proof。

8. Bulletproofs+性能优化

基本优化思路与Bulletproofs中类似，可参见博客 Bulletproofs: Short Proofs for Confidential Transactions and More学习笔记 第6节内容“对range proof的性能优化”。

• 对Verifier，delay all the exponentiations到最后一步；
• 复用一些Scalars计算；
• 实现batch verification。

参考资料：

[1] 博客 Comparing Bulletproofs+ and Bulletproofs - Part I
[2] 博客 Comparing Bulletproofs+ and Bulletproofs - Part II