ZKSwap 团队解析零常识证明算法之 Bulletproofs:Range Proof 1
本文摘要:撰文:ZKSwap江菜鸟前言Bulletproofs,又一个有意思的零常识证明算法,相信读者已经很了解它了。

出处链接:zks.org

t0 = lt; L, R gt; = z2*v + δ

L = aL – z * 1n

lt; l , r gt; = t

多项式值 l , r , t 由证明者提供,为了保证 l ,r well-formed,即:

R = o yn + z2 * 2n

δ = * lt; 1n, yn gt; – z3* lt; 1n, 2n gt;

因此,问题由证明:

2. 证明

Alice 想要证明 v ⸦ [0, 2n-1] =gt; 则,需要证明一个 relation 得成立,如下所示:

{(g、h ⸦ G,V,n*;v,r ⸦ Zp):V = grhv ^ v ⸦ [0, 2n-1] }

2n:表示向量 {20、21…2n-1}

lt; a、bgt; : 表示向量内积 ∑ ai*bi,结果是一个值

a o b:向量对应位相乘,{a1*b1……anbn},结果是一个向量

为了保证 t well-fromed,即:

此时,概念公式

可以看出系数 t0 是 l 和 r 常数项的乘积,即满足:

5. 验证:

1. 证明者把 L/R/V 发送给验证者;

前言

Bulletproofs,又一个有意思的零常识证明算法,相信读者已经很了解它了。和 zk-snark 相比,它无需可信设置;和 zk-stark 算法相比,它具备较小的 proof size。 依据论文,它有两个方面的应用:

1. 用于 range proof;
2. 用于通常算术电路的零常识证明。下面,让大家先看一下 Bulletproofs 是怎么样高效的达成第一点。

概要

从上述步骤可以看出,一次 range proof,证明者需要发送总共{ l / r / t / τx / μ / T1 / T2/ A / S}个元素给验证者,总共 2n+3 个 Zp 元素,4 个 G 元素。下一篇文章将细讲,Bulletproofs 怎么样将交互复杂度减少到对数级 O)。

Range h3roof 1. 预备常识

h3ublic-x witness-w relation-R

即,对于公开信息 x,Alice 有隐私聊息 w,使得关系 R 成立。

令 aL 为金额 v 的在范围 [0, 2n-1] 内的二进制形式,则 aL= {a1、a2……an}⸦{0,1}n,且满足 lt; aL, 2n gt; = v。因此,证明者需要证明以下几个等式相等:

等式 确保了承诺 V 和金额 v 的绑定关系,等式 确保了 v 的范围,等式 、 确保了 aL 元素只是 {0,1}。等式 // 总共包含了 2n+1 个约束,其中公式 1 个,公式 各 n 个。下面,为了效率,大家需要把 2n+1 个约束转换成 1 个约束。

3. 2n+1 个约束转换成 1 个约束

=gt; 预备:从 Zp 中任意选择一个数 y,则 b = 0n 是等式 lt; b, yngt; = 0 成立的充分条件;由于当 b != 0n,等式成立的概率仅有 n/p,p 是有限域,远大于 n。(理解:假如 b != 0n ,把等式看作求 n 阶一次多项式的零点即可)因此,假如有 lt; b, yngt; = 0,那样验证者想相信 b != 0n 。

借助这个理论,大家把等式 // 做以下转换:

1. 验证者随机选取一个数 y 发送给证明者

4. 三个点积优化成 1 个点积

需要校验:

=gt; 当且仅当 t 和 τx welle-formed,等式成立

需要校验:

=gt; 当且仅当 l/r well-formed,等式成立

=gt; 令

lt; L, R gt; = z2*v + δ

转化成了,在任意一点 x,验证者验证多项式值 l, r, t 满足关系:

6. 一个零常识证明协议

因为 L、R 包含了 v 的有关信息,因此,大家需要添加两个盲因子 sL、sR 来隐藏 aL,aR。如公式 所示:

aL:表示向量 {a1、a2……an}

撰文: ZKSwah3 江菜鸟

2. 证明者要证明:

同理,等式 确保了 v 的范围,等式 确保了 aL 元素只是 {0,1}。此时 2n+1 个约束转换成 3 个约束,下面,还需要做进一步的处置:

1. 验证者随机选取一个数 z 发送给证明者

2. 证明者借助 z 对公式 进行线性组合,得到如下公式:

z2*lt; aL、2n gt; + zlt; aL – 1n- aR、yngt; + lt; aL、aR o yn gt; = z2 * v

至此,大家已经把 2n+1 个约束转换成 1 个约束。下面大家对公式 做进一步的优化,把三个点积优化成 1 个点积。

t = t0 +t1x + t2x2

具体的协议步骤图如下图所示:

附录

Bulletproofs 论文:https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=AMPLarnumber=8418611

2. 验证者事先算好 δ

3. 验证者依据 L 算出来 aL,依据 lt; aL, 2n gt; = v 算出 v

4. 验证者依据 L、R、v、δ验证等式 lt; L, R gt; = z2 * v +δ

由于 y,z 都是验证者提供,因此假如验证者假如能验证公式 成立,则相信等式 成立,则相信等式 成立,则相信 v 满足关系 v ⸦ [0, 2n-1]。

但,可以看到上述过程,泄露了 v 的信息,因此需要一个零常识证明协议。