工程项目
你的位置:乐鱼电竞-合作伙伴大巴黎 > 工程项目 > 学习条记 | 零常识默契算法之PLONK——条约 | BTC

学习条记 | 零常识默契算法之PLONK——条约 | BTC

时间:2022-08-25 00:47 点击:143 次

学习条记 | 零常识默契算法之PLONK——条约 | BTC

上一篇主要神气了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. Commit: 谋略多项式开心,其着力是一个值;

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(Commit(T(x)), x*G) =? e(Commit(F(x)) +Commit (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算法的条约旨趣已全部共享完成,公式很密集,然则细分下来,又很有档次感。能宝石看完,已实属不易。列位读者有什么不同的简介,还请见教,谢谢。

服务热线
官方网站:www.fsjzx.cn
工作时间:周一至周六(09:00-18:00)
联系我们
QQ:50931028
邮箱:9fe8b2@www.fsjzx.cn
地址:北京工程项目国际企业中心4971号
关注公众号

Powered by 乐鱼电竞-合作伙伴大巴黎 RSS地图 HTML地图


乐鱼电竞-合作伙伴大巴黎-学习条记 | 零常识默契算法之PLONK——条约 | BTC

回到顶部