深造笔记 | 零知识证明算法之PLONK——和谈 | BTC
发布日期:2022-10-16 19:30    点击次数:183

上一篇次要形貌了PLONK和谈里的一个焦点部份,用置换校验的编制去证明电路门之间的分歧性;接上去,将延续分享怎么样证明门的解放纠葛得创建,以及总体的和谈分析。

门解放

举个俭朴的例子,假若存在一个电路,电路中惟一3个乘法门,对应的解放以下:

L1 * R1 - O1 = 0

L2 * R2 - O2 = 0

L3 * R3 - O3 = 0

举行多项式压缩:定义多项式函数L(X),R(X),O(X) 餍足:

L(1) = L1, R(1) = R1, O(1) = O1

L(2) = L2, R(2) = R2, O(2) = O2

L(3) = L3, R(3) = R3, O(3) = O3

此时,定义新的多项式函数F(X),令F(X) = L(X) * R(X) - O(X)

则有:

F(1) = L(1) * R(1) - O(1) = 0

F(2) = L(2) * R(2) - O(2) = 0

F(3) = L(3) * R(3) - O(3) = 0

也就是评释:假定多项式函数F(X)在X=1,2,3处有零点,则分析门纠葛解放创建。

多项式函数F(X)在X=1,2,3处有零点则评释多项式F(X)可以或许被(X - 1)(X - 2)(X - 3)整除,为了和论文分歧,我们把这个多项式函数配置成Z(X),即:

F(X) = T(X) * Z(X) ==> T(X) = F(X) / Z(X)

假定能证明T(X)是一个多项式,则分析多项式F(X)与Z(X)有沟通的零点,进而分析门解放纠葛创建。

普通进程该当以下:

1. P计算F(X)并把F(X)发送给V;

2. V痛处Z(X)间接校验F(X) / Z(X)

然则云云进程存在两个成就,一个是宏壮性成就,假若F(X)的阶为n,那通信宏壮度就是O(n);而是安好性成就,多项式F(X)齐全表露给V。

那该当怎么样经管这两个成就呢?最好的答案可以或许就是:多项式承诺

多项式承诺

什么是多项式承诺?就是证明方P用一个很短的数据来代表一个多项式F,这些很短的数据可以或许被验证方V用来验证多项式F在某一点的值确凿为证明方P声称的值z。

具体看一下论文里的定义:

由图可知:

1. Setup: 初始化,生成计算多项式承诺需求的一些必备参数;

2. Co妹妹it: 计算多项式承诺,其下场是一个值;

3. Open: 前去与多项式承诺对应的多项式函数;

4. VerifyPoly: 验证多项式承诺是否和多项式函数分歧;

5. CreateWitness: 证明多项式函数在某一点的值是不是证明方P声称的值,具体的数学编制就是:鉴定多项式是否能被整除,即:

6. VerifyEval: 验证方V验证多项式函数在某一点的值是不是证明方P声称的值,具体的数学编制是:行使双线性配对验证其数学乘法逻辑纠葛。

延续回到我们上面的成就:

证明方怎么样证明:T(X) = F(X) / Z(X),我们再简化一下场景,就令Z(X) = X - 1,则:

T(X) = F(X) / (X - 1) ==> T(X) * (X - 1) = F(X) ==> T(X) * X = F(X) + T(X)

对应多项式承诺的和谈可知:证明方P理论上是想证明多项式函数F(X)再X = 1处的值为0,因而痛处协验证方只需求证明:

e(Co妹妹it(T(x)), x*G) =? e(Co妹妹it(F(x)) +Co妹妹it (T(x)), G) (双线性配对的性质)

可以或许看出,行使多项式承诺的数学器材,既可以或许实现宏壮度的优化,又可以或许实现隐私呵护。

和谈

接上去阐发一下完备的PLONK和谈:

Relation

上图默示了PLONK算法里,要证明的一种纠葛,需求分析的是:

1. w 代表着电路里的输入、输出,总共3n个,n是电路里乘法门的数量,每个门都有左输入,右输入和输出,因而w总共有3n个;

2. q* 代表着抉择向量,它的取值对应这这个是乘法门,照旧加法门等近似的解放范例

3. σ 代表着置换多项式,其默示门之间的分歧性解放索引

4. 倒数第一个公式代表 门之间的解放创建

5. 倒数第二个公式代表 门的解放纠葛创建

CRS & P_Input & V_Input

上图默示了PLONK算法里的CRS配置,以及证明方P和验证方V的一些输入,需求分析的是:

1. 全副和谈都是基于多项式的,因而需求构建对应的多项式模式。

2. 多项式σ的阶是3n的,由于和多项式承诺相干的CRS最高的阶位n+2,因而需求把σ拆分成3个多项式S,划分记载每个多项式的置换纠葛(L,R,O);

3. 为了削减通信宏壮度和呵护隐私,和谈基于多项式承诺构建,因而验证方V的输入都是承诺值。

Prove

上图默示了PLONK算法里证明方的一些操作,需求分析的是:

1. b1,...b9是随机数,从用法看是为了安好,然则我姑且也没显然,不加这个随机数,又会有什么安好成就?

2. a(X),b(X),c(X)划分是代表了电路里的左输入,右输入和输出

3. [a],[b],工场场景[c]默示多项式的承诺值,参考多项式承诺小节里的承诺计算编制

上图默示了PLONK算法里证明方的一些操作,主若是置换校验,参考第一篇的置换校验的和谈进程,生成多项式z(X),需求分析的是:

1. β和ϒ都是用来生成置换校验函数的参数,详见第一篇里f`(x)和g`(x)的生成进程;

2. z(X)的生成编制对应置换校验里跨多项式的生成进程,Li(X)为拉格朗日多项式基,性质餍足,尽在x=i的岁月为1,别的为0;

3. 留心判别ω和w,ω是群H的生成元,是多项式的自变量的取值。w是电路的左输入,右输入和输出,是多项式L,R,O在在群H上的取值。

上图默示了PLONK算法里证明方P的一些操作,主若是把门解放和门之间的分歧性解放组合到一起,经由过程α,需求分析的是:

1. 痛处前面的形貌,门解放多项式和分歧性解放多项式在群H上的全体元素都是取值为0的,因而都市被多项式ZH(X)整除,等同于上面所述的T(X);

2. 因而,证明方只需能证明整除的下场切实是多项式,那便可以或许证明,门解放多项式和分歧性多项式在群H全体元素上取值为0,即全体解放纠葛创建,即电路逻辑创建;

3. 可以或许晓得的是t(X)的阶最高为3n,然则用于计算承诺的CRS只到了n的级别,因而需求把多项式t(X)拆分,尔后零丁计算承诺值。

上图默示了PLONK算法了证明方P的一些操作,次要痛处多项式承诺的和谈,前面P算出了多个多项式在点x=z处的值是几多,今朝要用多项式承诺和谈去证明,这些计算是准确的,需求分析的是:

1. 为了削减验证方V的操作宏壮度,t(X)的分子部份r(X)在x=z处的值,P计算好,尔后验证方间接验证,别的的操作近似;

2. v的值看起来是为了更安好;

3. Wz(X)对应多项式和谈里的CreateWitness操作,证明这些多项式r(X),a(X),b(X)等在x=z处的值确凿等于r,a,b等,对Wzw(X)同理,并前去承诺值。

Verify

至此,证明方P的全体操作都完事了,接上去都是验证方V的操作。

上图默示了PLONK算法里验证方V的一些操作,次要从头生成相干的参数,确担保明方P没有作恶。需求分析的是:

1. 从输入看,相比明晰,就是一些果真的输入和证明方P的证明输出;

2. 痛处输入,生成置换校验进程中需求的一些参数

上图默示了PLONK算法里验证方V的一些操作,关于一些果真的,并且计算宏壮度很小的多项式,其在x=z处的值照旧需求自身计算,加倍方便。需求分析的是:

1. 痛处证明方P的进程来看,验证方V的焦点事变就是验证两个多项式承诺;

2. 两个多项式承诺验证需求两个配对,可以或许经由过程一个参数组解析一个配对,即μ;

3. 在验证前,先计算Wz(x), Wzw(x)的分母在x=z处的值,两部份,减数和被减数,划分对应[F],[E]。μ作为系数的,就是对应Wzw(X)多项式的。

4. 最后经由过程一个双线性配对操作实现两个多项式承诺的验证。

终止

至此,PLONK算法的和谈道理已扫数份享实现,公式很鳞集,然则细分上去,又颇有条理感。能维持看完,已实属不轻易。各位读者有什么差别的简介,还请指教,感谢。



热点资讯
相关资讯