前言
Bulletproofs，又一个有意思的零知识证明算法，相信读者已经很熟悉它了。和 zk-snark 相比，它不需要可信设置；和 zk-stark 算法相比，它具有较小的 proof size。 根据论文，它有两个方面的应用：
- 用于 range proof；
- 用于一般算术电路的零知识证明。下面，让我们先看一下 Bulletproofs 是如何高效的实现第一点。
Range proof
1. 预备知识
aL：表示向量 {a1、a2……an}
2n：表示向量 {20、21…2n-1}
< a、b> : 表示向量内积 ∑ ai*bi，结果是一个值
a o b：向量对应位相乘，{a1*b1……anbn}，结果是一个向量
2. 证明
Alice 想要证明 v ⸦ [0, 2n-1] =>则，需要证明一个 relation 得成立，如下所示：
{（g、h ⸦ G，V，n*；v，r ⸦ Zp）：V = grhv ^ v ⸦ [0, 2n-1] }
public-x witness-w relation-R
即，对于公开信息 x，Alice 有隐私信息 w，使得关系 R 成立。
令 aL为金额 v 的在范围 [0, 2n-1] 内的二进制形式，则 aL= {a1、a2……an}⸦{0,1}n，且满足 < aL, 2n > = v。因此，证明者需要证明以下几个等式相等：
等式 (1) 确保了承诺V和金额v的绑定关系，等式 (2) 确保了v的范围，等式 (3)、(4) 确保了 aL 元素只属于 {0,1}。等式 (2)/(3)/(4) 总共包含了 2n+1 个约束，其中公式 (2) 1 个，公式 (3)(4) 各 n 个。接下来，为了效率，我们需要把 2n+1 个约束转换成 1 个约束。
3. 2n+1个约束转换成 1 个约束
=>预备：从 Zp 中任意选择一个数 y，则b = 0n是等式 < b, yn> = 0成立的充分条件；因为当 b != 0n，等式成立的概率仅有 n/p，p 是有限域，远大于 n。（理解：如果 b != 0n ，把等式看作求 n 阶一次多项式的零点即可）因此，如果有< b, yn> = 0，那么验证者愿意相信 b != 0n 。
利用这个理论，我们把等式 (2)/(3)/(4) 做以下转换：
- 验证者随机选取一个数y发送给证明者
- 证明者要证明：
同理，等式 (5) 确保了 v 的范围，等式 (6)(7) 确保了 aL 元素只属于 {0,1}。此时 2n+1 个约束转换成 3 个约束，接下来，还需要做进一步的处理：
- 验证者随机选取一个数 z 发送给证明者
- 证明者利用 z 对公式 (5)(6)(7) 进行线性组合，得到如下公式：
z2** < aL、2n > + z*< aL – 1n- aR、yn> + < aL、aR o yn > = z2 * v (8)
至此，我们已经把 2n+1 个约束转换成 1 个约束。下面我们对公式 (8) 做进一步的优化，把三个点积优化成 1 个点积。
4. 三个点积优化成 1 个点积
=> 令
L = aL – z * 1n
R = (aR + z * 1n) o yn + z2 * 2n
δ = (z – z2) * < 1n, yn > – z3* < 1n, 2n >
5. 验证：
- 证明者把 L/R/V 发送给验证者；
- 验证者事先算好 δ
- 验证者根据L算出来aL，根据< aL, 2n > = v算出v
- 验证者根据L、R、v、δ验证等式< L, R > = z2 * v +δ
因为 y，z 都是验证者提供，因此如果验证者如果能验证公式 (9) 成立，则相信等式 (5)(6)(7) 成立，则相信等式 (2)(3)(4) 成立，则相信 v 满足关系 v ⸦ [0, 2n-1]。
但是，可以看到上述过程，泄露了 v 的信息，因此需要一个零知识证明协议。
6. 一个零知识证明协议
由于 L、R 包含了 v 的相关信息，因此，我们需要添加两个盲因子 sL、sR来隐藏 aL，aR。如公式 (10)(11) 所示：
此时，定义公式 (12)
可以看出系数 t0是 l(x)和 r(x) 常数项的乘积，即满足：
t0 = < L, R > = z2*v + δ
因此，问题由证明：
< L, R > = z2*v + δ
转化成了，在任意一点x，验证者验证多项式值 l(x), r(x), t(x) 满足关系：
< l (x), r (x)> = t (x)
多项式值 l (x), r (x), t (x) 由证明者提供，为了保证 l (x)，r (x) well-formed，即：
需要校验：
=> 当且仅当 l/r well-formed，等式成立
为了保证 t (x) well-fromed，即：
t = t0 +t1x + t2x2
需要校验：
=> 当且仅当 t 和 τx welle-formed，等式成立
具体的协议流程图如下图所示：
总结
从上述流程可以看出，一次 range proof，证明者需要发送总共**{ l / r / t / τx / μ / T1 / T2/ A / S}**个元素给验证者，总共2n+3个Zp元素，4个G元素。下一篇文章将细讲，Bulletproofs 如何将交互复杂度降低到对数级 O(log(n))。
附录
Bulletproofs 论文：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8418611
微信扫一扫 
