区块链技术博客
www.b2bchain.cn

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

第13009篇文章ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1,说明解释了ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1,是很好的区块链入门技术文章网站,提供了相应的代码的进行解释,并且把原理说的很清晰

前言

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

1. 用于 range proof;2. 用于一般算术电路的零知识证明。下面,让我们先看一下 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。因此,证明者需要证明以下几个等式相等:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

等式 (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) 做以下转换:

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

2. 证明者要证明:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

同理,等式 (5) 确保了 v 的范围,等式 (6)(7) 确保了 aL 元素只属于 {0,1}。此时 2n+1 个约束转换成 3 个约束,接下来,还需要做进一步的处理:

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

2. 证明者利用 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 个点积

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

=> 令

L = aL – z * 1n

R = (aR + z * 1n) o yn + z2 * 2n

δ = (z – z2) * < 1n, yn > – z3* < 1n, 2n >

5. 验证:

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

2. 验证者事先算好 δ

3. 验证者根据 L 算出来 aL,根据 < aL, 2n > = v 算出 v

4. 验证者根据 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) 所示:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

此时,定义公式 (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,即:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

需要校验:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

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

为了保证 t (x) well-fromed,即:

t = t0 +t1x + t2x2

需要校验:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

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

具体的协议流程图如下图所示:

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1

总结

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

来源:链闻ChainNews (ID:chainnewscom)

ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1 由www.b2bchain.cn 提供
文章整理自网络,只为个人学习与分享使用
链接地址https://www.b2bchain.cn/13009.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » ZKSwap 团队解读零知识证明算法之 Bulletproofs:Range Proof 1
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们