理解零知识证明算法Bulletproofs（三）：Range Proof 实现分析

Original 江小白安比技术社区 2019-12-31 13:00

本文作者江小白，来自安比技术社区的小伙伴，本系列文章将对 Bulletproof 算法在 Range Proof 和 general arithmetic circuits 上的应用展开介绍。

前言

本篇主要分享基于Bulletproofs的Range proof的具体实现细节，并和当前github已有的实现做了对比分析。

阅读本篇前，假设您已经阅读了：

回顾

在第一篇文章中，我们讲到了，对于 prover claim "v 属于[0,2ⁿ-1]范围"这个论新，在一个基于零知识的交互协议中，prover 需要计算并发送以下内容给 verifier：

让我们再一次回顾以下每个变量的意义：

A: 对 a_L，a_R 的承诺，用于 verifier 计算 P，

S: 对盲因子 s_L，s_R的承诺，用于 verifier 计算 P，

T₁/T₂：多项式系数 t₁，t₂的承诺，用于 verifier 验证 well-formed t

t：多项式 t(x) 在任意一点的值，用于 verifier 验证 well-formed t

τ：t 的盲因子，用于 verifier 验证 well-formed t

μ：承诺 A，S 的盲因子组合，用于验证 well-formed {a,b}

a,b：内积变量，满足 t=<a,b>，代表 claim 成立

verifier 根据 (1) 的信息，计算并验证：

同样，让我们回顾一下每个公式的意义：

公式（2）：用于构造 aR ○ yn，为了计算和验证公式（4）和（5）的成立，注意

公式（3）：验证 well-formed t，

注意

V 为 v 的承诺，因此公式（3）保证了 t 与 v 的一致性。

公式（4）和（5）:两个等式联合保证 well-formed a,b

公式（6）：若相等，则表明原 claim 成立。注，公式（6）是证明 v 属于[0,2ⁿ-1] 的最终等价形式，详见第一篇文章。

在第二篇文章中，我们讲到了，当 prover 想要证明：

}

成立时，prover 和 verifier 之间的 CC 只有 O(log(n))，n 是向量的长度。最终的交互内容如下：

Prover 需要向验证者发送以下内容：

Verifier 基于（7）的信息，计算并验证：

其中：

or 1 当整数 (i-1)的第 j 位是 1

若公式（8）成立，则表明原始 R 成立。

Range proof

现在，我们把两者结合在一起，看看优化后的 Range proof 的协议。

Prover：

首先，在第一篇文章中，我们看到，在优化前， prover 要发送给 verifier 的内容如公式（1）所示，其大小为 2n+7;

然后，基于第二篇文章中的优化方法，公式（1）的内容可修改为:

即优化后，prover 发送给 verifier 的内容大小减少为 2log(n)+9

Verifier：

接下来，看看 verifier 的改动。在优化前，verifier 要验证的内容如公式（2）（3）（4）（5）（6）所示，仔细观察公式（5）（6）,其实可以发现，就是第二篇R的验证。因此，实际上：Range proof 的问题可以转化位一下形式的R的满足性问题，即：

令

则 R 可等价为：

}

公式（2）（3）（4）仅仅是为了保证 t 和 a，b well-formed。

因此，基于第二篇文章的优化方法，verifier 验证的内容可修改为：

其中：

其中随机数 x μ 是相对第二篇的一个修改，由 verifier 产生，是为了保证 t=<a,b>

现在我们对 verifier 的验证过程进行一个简单的概括，具体如下：

Input:

Compute（红色标记）

令：

其中，b(i,j)=-1 or 1 当整数(i,-1)的第 j 位是1；

则有：

则，公式（21）等价于：

Bulletproof 的rangeproof的开源实现，项目地址在（），

相对于本篇分享的内容，下图中展示内容主要有以下几点不同：

本文讲述的是以离散对数为基础；图中以椭圆曲线离散对数为基础，因此只要把指数操作转化为乘法操作即可
图中最后的验证内容：实际上是本篇公式(19)和(24)的结合，利用假设：如果A^cB = 1,则有很大的概率满足A =1 & B =1。因此，公式(19)和(24)可优化为一个验证等式，即(19)^c(24) =？1，若成立，则等式 (19) =? 1 & (24) =? 1 大概率成立。