1. 引言

Benedikt B¨unz、 Jonathan Bootle和 Dan Boneh等人2018年论文《Bulletproofs: Short Proofs for Confidential Transactions and More》中：

• 提出了Bulletproofs算法——基于discrete logarithm assumption，无需trusted setup，具有short proofs的NIZK算法。（采用Fiat-Shamir heuristic来实现non-interactive。）Bulletproofs尤其适合用于为committed values提供range proofs：
  – 证明a committed value is in a range，仅需要 2 log ⁡ 2 ( n ) + 9 2\log_2(n)+9 2log2​(n)+9 group 和 field elements，其中 n n n为range的bit length。
  – Proof generation和verification time均为 O ( n ) O(n) O(n)。

• 现有Bitcoin及其它加密货币隐私交易的range proof size为 O ( n ) O(n) O(n)，Bulletproofs将其提高至 2 log ⁡ 2 ( n ) + 9 2\log_2(n)+9 2log2​(n)+9。

• Bulletproofs支持对多个range proofs的aggregation，
  – 为了证明来自同一party的 m m m个commitments lie in a given range，可将其aggregate 为 a single proof，并仅需额外再增加 O ( log ⁡ ( m ) ) O(\log(m)) O(log(m)) 个group elements。
  – 为了aggregate proofs from multiple parties，we enable the parties to generate a single proof without revealing their inputs to each other via a simple multi-parity computation (MPC) protocol for constructing Bulletproofs。该多方安全计算协议可为：1）具有constant number of rounds and linear communication或者2）具有a logarithmic number of rounds and logarithmic communication。以CoinJoin混币方案（Maxwell 2013年《 CoinJoin: Bitcoin privacy for the real world》）为例，隐私交易的inputs来自多个parties，可借助MPC protocol，allow multiple parties with secret committed values to jointly generate a single range proof for all their values, without revealing their secret values to each other。

• 尽管Bulltproofs的verification time为 O ( n ) O(n) O(n)，但实际是足够高效的。同时，支持对多个Bulletproofs仅需batch verify，从而进一步提升verify速度。
  verify an aggregation of 16 range proofs的时间与verify 16个ECDSA signatures的时间相当。

Bulletproofs构建在Bootle和Groth等人2016年论文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》算法基础之上，做了如下改进：

• 将其中的inner product argument的communication complexity降低了3倍。
• 构建range proofs时，在最后一轮无需为Verifier提供commitment openings。

除了用于range proofs，Bulletproofs还可用于：

• 为arithmetic circuit提供基于discrete logarithm assumption 无需trusted setup的short 零知识证明算法。其proof size 为 O ( N ) O(\sqrt{N}) O(N ​)，其中 N N N为multiplication gate的数量。
• verifiable shuffle。

本文对应的代码实现有：

• https://github.com/dalek-cryptography/bulletproofs
• https://github.com/adjoint-io/bulletproofs
• https://github.com/lovesh/bulletproofs-r1cs-gadgets
• https://github.com/KZen-networks/bulletproofs
• https://github.com/akosba/jsnark

https://github.com/akosba/jsnark 中提供了一个通用工具，用于构建Bulletproofs for any NP language，该工具可读取Pinocchio格式的arithmetic circuit，同时包含了将C语言编译为circuit fomat 的编译器。

1.1 背景

基于区块链构建的加密货币支持点对点的价值交互，通过维护全局同步的分布式账本——blockchain。
任何人均可验证区块链中当前状态以及账本中所有交易的有效性。为此，Bitcoin 要求交易中的所有信息均是public的：

• the sender 交易发起方；
• the receiver 交易接收方；
• the amount transferred 交易金额。

所谓隐私支付包含2个属性：

• 1）anonymity 匿名性，即交易中的发起方和接收方的身份信息均需隐藏；
• 2）confidentiality 机密性，即交易金额需隐藏。

由于Bitcoin addresses与现实真实身份之间存在unlinkability，Bitcoin提供了弱的anonymity，但是缺少confidentiality。这制约了Bitcoin的一些应用。如雇员并不喜欢被用bitcoin来支付薪水，因为那样他们的薪水金额将发布到public blockchain中。

为了对交易金额实现隐藏，Maxwell 在2016年《Confidential transactions》提出了confidential transactions (CT) 概念，通过对每笔交易金额进行commit实现隐藏。这种方式似乎会影响blockchain的public validation，an observer不再能够判断交易的输入之和是否大于交易的输出之和，以及验证所有的交易输入/输出金额是否为正数。通过为每笔交易提供一个证明隐私交易有效性的证明可以解决该问题。

Poelstra等人在2017年 《 Confidential assets 》中指出，现有的隐私交易零知识证明要么非常大，要么需要trusted setup。

• 需要trusted succinct 零知识证明方案有：如 Ben-Sasson等人2013年论文《SNARKs for C: verifying program executions succinctly and in Zero Knowledge》和 Gennaro等人2013年论文《Quadratic span programs and succinct NIZKs without PCPs》 。要求每个人都信任setup过程运行正确。
• 不需要trusted setup的零知识证明方案有： Ben-Sasson等人2018年论文《Scalable, transparent, and post-quantum secure computational integrity》。其所构建的range proof size 比当前的方案还要大。

构建同时具有short proof size和不需要trusted setup的零知识证明方案，在加密货币领域很有价值。对于任何分布式系统，若proofs需要通过网络传输或者需要长期存储时，更短的proof size将有助于节约cost。

1.2 相关研究

现有的range proofs方案有：

• Maxwell 2016年《Confidential transactions》中提出了confidential transactions (CT) 概念，通过对每笔交易金额进行commit实现隐藏。这种方式似乎会影响blockchain的public validation，an observer不再能够判断交易的输入之和是否大于交易的输出之和，以及验证所有的交易输入/输出金额是否为正数——即在区间 [ 0 , 2 n ] [0,2^n] [0,2n]，其中 2 n 2^n 2n远远小于group size。通过为每笔交易提供一个证明隐私交易有效性的证明可以解决该问题。
• [Poe] Poelstra 2016年《Mimblewimble》
• Maxwell和Poelstra 2015年《Borromean ring signatures》。
• Poelstra等人2017年《 Confidential assets 》中通过side-chains来实现隐私交易。
• Noether等人2016年《Ring confidential transactions》中提出了关注隐私的加密货币Monero。
• Andreev 2017年《Hidden in Plain Sight: Transacting Privately on a Blockchain》私有链中实现的隐私交易。

以上方案除[Poe] 外都是基于committed values 构建的range proofs，其proof size为 O ( n ) O(n) O(n)，这些proof是隐私交易中size的主要贡献者。
现有的Maxwell 2016年《Confidential transactions》实现，对于仅有2个output，32bit精度的隐私交易其大小为5.4KB，而其中5KB是由range proof贡献的。尽管近期有做优化，但range proof大小仍占据3.8KB。

在本文写作时，Bitcoin有来自2200万笔交易的约5000万个UTXOs。使用52-bit 来表示bitcoin从1 satoshi到2100万bitcoin的数值，若使用现有的range proofs方案，大约需要160GB的range proof data。而若采用aggregated Bulletproofs，则将仅需小于17GB的空间，节约了大概10倍的空间。

1.3 Mimblewimble

[Poe] Poelstra 2016年《Mimblewimble》和 Jedusor 2016年 《Mimblewimble》 提出的Mimblewimble协议，可进一步节约存储空间。

• Jedusor 2016年 《Mimblewimble》中指出：对0的Pedersen commitment可看成是一个ECDSA的公钥，而对于一个有效的隐私交易，其 (inputs-outputs-transaction fees) 必须为0。A prover constructing a confidential transaction can therefore sign the transaction with the difference of the outputs and inputs as the public key. This small change removes the need for a scriptSig which greatly simplifies the structure of confidential transactions。

• Poelstra 2016年《Mimblewimble》在Jedusor的基础上进一步改进了Mimblewimble协议，所有的spent transactions can be pruned and new nodes can efficiently validate the entire blockchain without downloading any old and spent transactions，从而大幅简化了区块链。进一步优化，可实现高度压缩的区块链，仅需要包含一小部分区块头和剩余的unspent transaction outputs 以及相应的range proofs和 an un-prunable 32 bytes per transaction。
  Mimblewimble协议支持对多个transaction先aggregate，然后再发送给blockchain。

Mimblewimble blockchain会随着UTXO set 的size而增长，而若使用Bulletproofs，其仅随那些具有unspent outputs的transaction数量而增长，unspent outputs的transaction数量远远小于UTXO set 的size。
总之Bulletproofs不仅适于替代现有隐私交易中的range proofs，同时也有助于帮助Mimblewimble成为实用的方案用于构建比现有Bitcoin blockchain更小的blockchain。

1.4 Provisions协议

Dagher等人在2015年论文《Privacy-preserving proofs of solvency for bitcoin exchanges (full version)》中提出了Provisions 协议，用于证明交易所可偿还能力。
该协议中依赖range proofs来防止插入负数金额的账户。当为a large exchange with 200万客户提供证明时需要约18GB的空间，而range proofs 将占据约13GB。
若用Bulletproofs协议替换Provisions协议中的NIZK proof时，the range proofs would take up less than 2KB, the proof for one commitment per customer 的size为62MB，从而将节约将近300倍的空间。

1.5 Verifiable shuffles

Verifiable shuffles是指：对于2组committed值 x 1 , ⋯   , x n x_1,\cdots,x_n x1​,⋯,xn​和 y 1 , ⋯   , y n y_1,\cdots,y_n y1​,⋯,yn​，证明第二组数据为第一组数据的permutation。