PlonK Permutations over Lagrange

PlonK Permutations over Lagrange"/>

PlonK Permutations over Lagrange

PLONK 课程笔记

最近在看plonk，直接看论文有些吃力，在哔哩哔哩上观看课程讲解，很细致

1. plonk的基本原理

1.将数学运算化为多项式，之后再化为电路。

2.多项式承诺（手上的一堆多项式，满足一定的关系：证明方发送给验证者，承诺发出后，多项式不可以再改变）。

零知识证明基本原理：
证明R(x,w) = 1. x :是数学问题，w是问题的解。证明方P找到了解w,向验证方V证明拥有w。

电路中门的分类：加法门、乘法门和常数门。

2. plonk 处理门的方案：

​ Q L ∗ a + Q R ∗ b + Q O ∗ c + Q M ∗ a ∗ b + Q C = 0 Q_L*a + Q_R*b + Q_O*c + Q_M*a*b +Q_C = 0 QL​∗a+QR​∗b+QO​∗c+QM​∗a∗b+QC​=0
通过限制 Q L ， Q R ， Q O ， Q M ， Q C ， Q_L， Q_R， Q_O，Q_M，Q_C， QL​，QR​，QO​，QM​，QC​， 可以得到任意a,b,c 的关系：

​ a + b = c ( Q L = 1 , Q R = 1 , Q O = − 1 ) , a ∗ b = c , a = 5 a+b =c(Q_L =1,Q_R =1 ,Q_O =-1),a*b=c,a=5 a+b=c(QL​=1,QR​=1,QO​=−1),a∗b=c,a=5

电路中有两个约束：门约束和复制约束。

​ plonk将这两种约束变成某种多项式的额关系，并加以证明。

i=1,2,…,n个门，电路中的门可以统一为如下的形式(将i想象成变量)：

q L i a i + q R i b i + q O i c i + q M i a i b i + Q c i = 0 q_{L_i}a_i + q_{R_i}b_i +q_{O_i}c_i +q_{M_i}a_ib_i +Q_{c_i} =0 qLi​​ai​+qRi​​bi​+qOi​​ci​+qMi​​ai​bi​+Qci​​=0

根据拉格朗日差值，在{1,2，…,n}个门中，x轴对应n个点，每个对应一个y值，n个点可以确定n-1个多项式。

n个点的 q L ( X ) q_L(X) qL​(X)对应于一个多项式， q L ( i ) = q L i q_L(i)=q_{Li} qL​(i)=qLi​，代表了所有的做系数。

一共是5n个q,3n个门（a,b,c).

n个方程压缩为 q L ( X ) a ( X ) + q R ( X ) b ( X ) + q O ( X ) c ( X ) + q M ( X ) a ( X ) b ( X ) + Q c ( X ) = 0 q_{L}(X)a(X) + q_{R}(X)b(X) +q_{O}(X)c(X) +q_{M}(X)a(X)b(X) +Q_{c}(X) =0 qL​(X)a(X)+qR​(X)b(X)+qO​(X)c(X)+qM​(X)a(X)b(X)+Qc​(X)=0

复制约束：

将相等的关系放做成置换， σ \sigma σ = （1 3 5）（2 6 8 9），相等的关系放在一堆， 如图：

定义多项式:

a ( x ) , b ( x ) , c ( x ) , a ′ ( x ) , b ′ ( x ) , c ′ ( x ) a(x),b(x),c(x),a'(x),b'(x),c'(x) a(x),b(x),c(x),a′(x),b′(x),c′(x)使得 σ ( a ′ ( x ) , b ′ ( x ) , c ′ ( x ) ) = ( a ( x ) , b ( x ) , c ( x ) ) \sigma (a'(x),b'(x),c'(x))=(a(x),b(x),c(x)) σ(a′(x),b′(x),c′(x))=(a(x),b(x),c(x))。复制约束也就此转化为多项式方程。

**承诺：**将多项式写成 f ( x ) = a 0 + a 1 x + a 2 x 2 + , . . . , q k x k f(x)=a_0 + a_1x +a_2x^2+,...,q_kx^k f(x)=a0​+a1​x+a2​x2+,...,qk​xk

证明方要算 f ( x ) − > c f(x) -> c f(x)−>c发给验证方，一旦将 f ( x ) f(x) f(x)发给验证方就不能修改。 相当于A给B一个信，使用信封封起来之后就不能修改。

opening：包括单个点上的打开和整个的打开。可以在某些点上打开（局部打开）如下图：z点为例，V可以向P要求某点的值，并没有暴露整个多项式，多项式的信息V是不知道的。（打开的意思是可以算完值给你，而不泄露多项式）。

P将 f 1 ( x ) , f 2 ( x ) , . . . , f k ( x )