零点课堂 | 理解零知识证明算法Bulletproofs(一):Range Proof

前言

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……an ·bn},结果是一个向量

2

证明

Alice想要证明

v ∈[0, 2n-1]

=>则,需要证明一个relation得成立,如下所示:

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

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

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

  1. 验证者随机选取一个数z发送给证明者:
  2. 证明者利用z对公式(5)(6)(7)进行线性组合,得到如下公式:

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

4

三个点积优化成 1 个点积

=> 令

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的相关信息,因此,我们需要添加两个盲因子sLsR来隐藏aL,aR。如公式(10)(11)所示:

此时,定义公式(12)

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

因此,问题由证明:

转化成了,在任意一点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,即:

需要校验:

μ

为了保证t(x) well-fromed,即:t = t0+t1x + t2x2需要校验:

&&τττ

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

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

理解零知识证明算法Bulletproofs(一):Range Proof

总结

从上述流程可以看出,一次range proof,证明者需要发送总共{l / r / tx/μ/ T1/ T2/ A / S} 个元素给验证者,总共2n+3个Zp元素,4个G元素。

本文由 零点财经 作者:tao 发表,其版权均为 零点财经 所有,文章内容系作者个人观点,不代表 零点财经 对观点赞同或支持。如需转载,请注明文章来源。
分享生成图片
56

发表回复

零点课堂 | 理解零知识证明算法Bulletproofs(一):Range Proof

2021-06-28 10:43:52

前言

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……an ·bn},结果是一个向量

2

证明

Alice想要证明

v ∈[0, 2n-1]

=>则,需要证明一个relation得成立,如下所示:

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

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

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

  1. 验证者随机选取一个数z发送给证明者:
  2. 证明者利用z对公式(5)(6)(7)进行线性组合,得到如下公式:

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

4

三个点积优化成 1 个点积

=> 令

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的相关信息,因此,我们需要添加两个盲因子sLsR来隐藏aL,aR。如公式(10)(11)所示:

此时,定义公式(12)

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

因此,问题由证明:

转化成了,在任意一点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,即:

需要校验:

μ

为了保证t(x) well-fromed,即:t = t0+t1x + t2x2需要校验:

&&τττ

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

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

理解零知识证明算法Bulletproofs(一):Range Proof

总结

从上述流程可以看出,一次range proof,证明者需要发送总共{l / r / tx/μ/ T1/ T2/ A / S} 个元素给验证者,总共2n+3个Zp元素,4个G元素。