技术入门 | 理解零知识证明算法之Bulletproofs :Range Proof II

江小白 发布在 技术指南 海盗号 873519

前言

在本系列的第一篇文章中,我们介绍了Bulletproofs在Range proof上的应用,当prover想要证明v值在范围[0, 2n-1]内时,他需要发送2n+7个元素。然而,这种O(n)级的CC并不是我们想要的,希望能寻找一种方法可以把CC降低到O(log(n)级。本篇我们就主要介绍这个优化过程。主要分为两部分:

1.    以简单的场景去阐述这个优化过程

2.    把第一篇的Range proof结果嵌入到优化过程

注:第一篇文章由于格式的原因,公式显示会有误差,向量的特殊标记也没有显示出来,因此本篇将以图片的形式展示整个过程;另外,本文最后也附上了第一篇文章的图,帮助大家理解^_^

 

Improved Range proof

A simple example

1.    预备知识

2.    一个简单的场景

3. 复杂度优化到O(log(n))

下图是一张基于上述过程的交互协议

有几点需要说明:

1.    图的右半部分分为两个部分

a.     黄色部分为文章前面部分讲述的过程。这又分为三个部分:

i.     初始化:省略了P的计算和交互的过程,我们假定开始此证明协议前,验证者已经有了一些基本的信息。这并不严谨,仅仅是为了清晰的表示后面的交互过程

ii.     LOOP:一个不断迭代的过程,每次迭代,会:

1).    产生一对(Li, Ri),

2).    所有向量长度减半

3).    Verifier计算Pi`/gi`/hi`

iii.     End:最后一步,向量a,b已减半成常量a,b

b.    绿色部分为黄色部分的进一步优化,优化思想主要是多次幂乘操作缩减成单词幂乘操作,具体的是:

i.     上述LOOP中的第3步,延迟到最后一部一次性计算,

A real Rang proof

    回顾第一篇文章,我们知道,当我们要证明v属于[0, 2n-1]时,验证者最终要验证:

P =? hμ  * gl * (h`)r

t =? <l, r>

    对关系式做个变换:

P * h =? * gl * (h`)r

t =? <l, r>

    因此,prover是要证明有向量l, r满足关系:

Relation : {( g、h ⸦ Gn, P * h-μ  ⸦ G, t ⸦Zp ) : P = glhr ^ t = <a, b>}

基于此关系,使用上述协议,就可以使range proof的交互复杂度降低到对数级。现在,是不是找到点内味了?^_^

                        

总结

本篇文章主要讲到了,BulletProof是如何把Range proof的CC降低到O(log(n)),并且介绍了更近一步的优化。结合第一篇文章,相信你已经对基于Bulletproofs的Range proof原理有了整体的了解,在本系列的第三篇文章中,将给大家分享Range proof的工程上实现细节。

 

附录

1.Bulletproofs 论文:chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2017%2F1066.pdf

2.    附一张图,方便大家理解第一篇文章(https://www.8btc.com/media/530155)

本文链接:https://www.8btc.com/media/532874
转载请注明文章出处

评论
登录 账号发表你的看法,还没有账号?立即免费 注册