文档章节

Zero Knowledge Proof 解密 QAP

字数 1189
阅读 70
收藏 0

本文的内容来自于V神的博客文章,再加上一些自己的理解。验证代码在https://github.com/ethereum/research/blob/master/zksnark/

零知识的证明逻辑需要花很多篇幅仔细介绍,涉及到QAP,KCA,Groth16,同态隐藏,双线性映射等。这篇文章主要介绍quadratic arithmetic program(QAP)。

ZK-snark不能直接拿来应用,我们必须把原始数据转换成适合ZK-snark处理的方式。以如下的3次方等式为例:

x**3 + x + 5 == 35 (答案是 3)

编程Python程序如下:

def qeval(x):

    y = x**3

    return x + y + 5

扁平化展开

上面的2元3次方程可以展开为:【1】

sym_1 = x * x

y = sym_1 * x

sym_2 = y + x

~out = sym_2 + 5

R1CS转换

rank-1 constraint system (R1CS) 是一个(a.b.c)的3个向量,R1CS的解答是一个向量S,满足s . a * s . b - s . c = 0, 此处 . 代表相应位置的乘法,然后再将乘法的结果相加,随后,对b 和s ,以及 c 和 s做同样的操作。

S.a=(1×5 +3×0 +35×0 + 9×0 + 27 ×0 + 30 ×1) =35 

S.b=(1×1 + 3×0 +35×0+9×0+27×0+30×0)=1

S.c=(1×0 +3×0 + 35×1 + 9×0+27×0+30×0)=35

显然上面的S向量(1,3,35,9,27,30)就是上述二元3次方程的一个解

为了规范化,我们加了一个哑元'~one',以及中间变量'sym_1',  'sym_2',向量变成下面这样:

'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

第一个门:

a = [0, 1, 0, 0, 0, 0]

b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 1, 0, 0]

上面的(a,b,c)矢量组表示下面的语句:s.a*s.b-s.c=0

sym_1 = x * x

同理:

a = [0, 0, 0, 1, 0, 0]

b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 0, 1, 0]

代表:

sym_1 * x = y

上面的语句来自【1】

sym_1 = x * x

y = sym_1 * x

sym_2 = y + x

~out = sym_2 + 5

上面语句的完整的R1CS如下:【2】

A

[0, 1, 0, 0, 0, 0]

[0, 0, 0, 1, 0, 0]

[0, 1, 0, 0, 1, 0]

[5, 0, 0, 0, 0, 1]

B

[0, 1, 0, 0, 0, 0]

[0, 1, 0, 0, 0, 0]

[1, 0, 0, 0, 0, 0]

[1, 0, 0, 0, 0, 0]

C

[0, 0, 0, 1, 0, 0]

[0, 0, 0, 0, 1, 0]

[0, 0, 0, 0, 0, 1]

[0, 0, 1, 0, 0, 0]

下面利用拉格朗日插值来把R1CS编成QAP

拉格朗日插值

学过数值分析的应该很容易理解,对于一列坐标:(x0,y0),(x1,y1)...(xi,yi),可以通过拉格朗日插值,找到一个多项式,它通过这个坐标序列里的每一个点。具体的方法是:

 对于(x0,y0), 我们找到一个多项式,在x1,x2....xi处,y1,y2,..yi均为零。这样的多项式很容易找,比如,下面就是一个例子:

y= (x-x1)(x-x2)...(x-xi)

举个例子,比如有3个点:(1, 3), (2, 2) 和(3, 4)。

    - 首先我们找到通过(1, 3), (2, 0)和 (3, 0)的多项式。

    - 其次我们找到通过(1, 0), (2, 2)和 (3, 0)的多项式。

    - 再次我们找到通过(1, 0), (2, 0)和 (3, 4)的多项式。

    - 最后,我们把上面得到的多项式加起来就是通过这三个点的多项式

 

我们用拉格朗日插值来变换上面的【2】

程序如下

#Assumes vec[0] = p(1), vec[1] = p(2), etc, tries to find p,

#expresses result as [deg 0 coeff, deg 1 coeff...]

def lagrange_interp(vec):

    o=[]

    for i in range (len(vec)):

        o=add_polys(o, mk_singleton(i+1, vec[i],len(vec)))

    for i in range(len(vec)):

        assert abs(eval_poly(o, i+1)-vec[i]<10**-10), (o, eval_poly(o, i+1), i+1)

    return o

 

def transpose(matrix):

    return list(map(list,zip(*matrix)))

 

#A, B, C = matrices of m vectors of length n, where for each

#0 <= i < m, we want to satisfy A[i] * B[i] - C[i] = 0

def r1cs_to_qap(A,B,C):

    A, B, C=transpose(A), transpose(B), transpose(C)

    new_A=[lagrange_interp(a) for a in A]

    new_B=[lagrange_interp(b) for b in B]

    new_C=[lagrange_interp(c) for c in C]

    Z=[1]

    for i in range(1,len(A[0])+1):

        Z=multiply_polys(Z, [-i,1])

    return(new_A, new_B, new_C, Z)

結果如下

A 多项式

[-5.0, 9.166, -5.0, 0.833]

[8.0, -11.333, 5.0, -0.666]

[0.0, 0.0, 0.0, 0.0]

[-6.0, 9.5, -4.0, 0.5]

[4.0, -7.0, 3.5, -0.5]

[-1.0, 1.833, -1.0, 0.166]

B 多项式

[3.0, -5.166, 2.5, -0.333]

[-2.0, 5.166, -2.5, 0.333]

[0.0, 0.0, 0.0, 0.0]

[0.0, 0.0, 0.0, 0.0]

[0.0, 0.0, 0.0, 0.0]

[0.0, 0.0, 0.0, 0.0]

C 多项式

[0.0, 0.0, 0.0, 0.0]

[0.0, 0.0, 0.0, 0.0]

[-1.0, 1.833, -1.0, 0.166]

[4.0, -4.333, 1.5, -0.166]

[-6.0, 9.5, -4.0, 0.5]

[4.0, -7.0, 3.5, -0.5]

 

 

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

 

附录

拉格朗日的定义和证明可以参看这里这里

还有一篇零知识证明的文章 - Christian Reitwiessner 

© 著作权归作者所有

怎当她临去时秋波那一转
粉丝 11
博文 79
码字总数 37853
作品 0
其它
CTO(技术副总裁)
私信 提问
零知识证明 - libsnark源代码分析

libsnark源代码,建议想深入零知识证明的小伙伴都读一读。Bellman库主要围绕Groth16算法,libsnark给出了SNARK相关算法的全貌,各种Relation,Language,Proof System。为了更好的生成R1CS电...

深入浅出区块链
08/15
0
0
零知识证明 - 从QSP到QAP

前一段时间,介绍了零知识证明的入门知识,通过QSP问题证明来验证另外一个NP问题的解。最近在看QAP问题相关的文章和资料,这篇文章分享一下QAP问题的理解。 背景介绍 QSP/QAP问题的思想都是出...

深入浅出区块链
05/07
0
0
filecoin技术架构分析二:filecoin通用语言理解

我是先河系统CTO杨尉,欢迎大加关注的的Github: waynewyang,本文是filecoin技术架构分析系列文章第二章filecoin通用语言理解。 为什么要把filecoin通用语言单独列为一讲 笔者认为一位优秀的...

深入浅出区块链
02/20
0
0
零知识证明 - Groth16算法介绍

看zk-SNARK的文章或者资料的时候,经常会碰到一些算法名称,比如Groth16,GGPR13等等。这些名称是由算法提出的作者名称或者名称首字母以及相应的年份组成。Groth16,是由Jens Groth在2016年提...

深入浅出区块链
05/27
0
0
区块链学堂——图灵完备、零知识证明

区块链学堂第14篇 前言 在学习区块链的过程中,常常被一些外星人词汇(专业术语)困扰,图灵完备、零知识证明就是其中之二,今天就彻底搞定这两个“天外来客”。 学习目标 ① 理解图灵完备、...

叶先生的鱼
2018/01/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

[mycat]PartitionByString分片报错

java.lang.RuntimeException: error,check your partitionScope definition.at io.mycat.route.util.PartitionUtil.<init>(PartitionUtil.java:69) PartitionUtil.java 注意:其中count,l......

Danni3
31分钟前
8
0
OSChina 周三乱弹 —— 魂淡!不是这种粪发涂墙

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @小小编辑推荐歌曲《10/10》- Rex Orange County 《10/10》- Rex Orange County 手机党少年们想听歌,请使劲儿戳(这里) @奋斗的小牛 :上午...

小小编辑
44分钟前
774
12
Arduino教程:认识Arduino控制板

@toc 1.1 课程说明 认识Arduino控制板的各个部分, 1.2 器材 名称 数量 规格 Arduino uno控制板 1 R3 1.3 UNO电路: UNO参数 名称 参数说明 工作电压: 5V 输入电压: 接上USB时无须外部供电...

acktomas
50分钟前
9
0
WeUI框架

WeUI框架 WeUI是一套小程序的UI框架,所谓UI框架就是一套界面设计方案,有了组件,我们可以用它来拼接出一个内容丰富的小程序,而有了UI框架,我们就可以让我们的小程序变得更加美观。 体验W...

达达前端小酒馆
53分钟前
5
0
Rainbond 5.1.8发布,应用网关支持多IP网络接入

2019年10月23日,Rainbond发布5.1.8版本,本次版本更新带来了应用网关对多IP的支持, 第三方组件对域名实例的支持 等新功能和修复若干BUG。 Rainbond:支撑企业应用的开发、架构、交付和运维的...

好雨云帮
54分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部