Turbo-Plonk：用于特定SNARK程序的语法提案

1. 引言

Aztec protocol 团队的Gabizon 和 Williamson 发表于2020年ZKProof第3届Workshop的论文《Proposal: The Turbo-PLONK program syntax for specifying SNARK programs》。

代码实现有：

• https://github.com/AZTECProtocol/barretenberg

近期的Marlin和PLONK都是依赖于Polynomial commitment scheme来构建zk-SNARK了，而与待证明的statement采用R1CS constraints 关系并不紧密。主要原因在于，polynomial commitment scheme构建zk-SNARK中，其verifier equation 为checked “in the clear” on a random opening of the prover polynomials，而之前的R1CS constraint zk-SNARK方案中的verifier equation 是“in the exponent” using a pairing。

在本论文中，提供了一种框架来实现更通用和灵活的constraint类型，该框架称为 turbo-PLONK programs。

turbo-PLONK programs 框架可提供：

• fixed-base elliptic curve scalar multiplication (仅需1 turbo-PLONK gate for each two input bits)
• a primitive useful for constructing Pedersen hashes。

同时，使用Grumkin curve (255-bit curve embedded over bn254)，针对scalar multiplication操作，本文的方案相比于Groth16快约2倍。

2. Turbo PLONK programs

a turbo-PLONK program P \mathscr{P} P 可看成是一系列的状态 v ∈ F w v\in\mathbb{F}^w v∈Fw，其中 w w w为state size，由program designer设定。 Proof size和Prover run time随着 w w w线性增加，通常 w w w的值为3或者4。

P \mathscr{P} P支持两种类型：

• transition gate
• copy constraint

相应的valid execution trace 为 T ∈ ( F w ) t T\in(\mathbb{F}^w)^t T∈(Fw)t。

2.1 transition gate

P \mathscr{P} P 的 transition constraint 对应为 a 2 w + l 2w+l 2w+l-variate degree at most d d d polynomial P P P，其中 d d d为 P \mathscr{P} P的degree，建议设置 d = w + 1 d=w+1 d=w+1， l l l为the selector number。

P \mathscr{P} P 的 transition gate 中包含了：

• 所有的transition constraints
• l l l selector vectors q 1 , ⋯   , q l ∈ F t q_1,\cdots,q_l\in\mathbb{F}^t q1​,⋯,ql​∈Ft

若满足以下条件，可称 T T T satisfy the transition gate：

• 对于每一个transition constraint i ∈ [ t ] i\in[t] i∈[t]， P ( T i , 1 , ⋯   , T i , w , T i + 1 , 1 , ⋯   , T i + 1 , w , q 1 ( i ) , ⋯   , q l ( i ) ) = 0 P(T_{i,1},\cdots,T_{i,w},T_{i+1,1},\cdots,T_{i+1,w},q_1(i),\cdots,q_l(i))=0 P(Ti,1​,⋯,Ti,w​,Ti+1,1​,⋯,Ti+1,w​,q1​(i),⋯,ql​(i))=0均成立。

2.2 copy constraint

a partition of w × t w\times t w×t into distinct sets { S i } \{S_i\} {Si​}。

若满足以下条件，可称 T T T satisfy the copy constraint：

• 当 ( i , j ) 和 ( i ′ , j ′ ) (i,j)和(i',j') (i,j)和(i′,j′) 属于partition中的同一set时，有 T i , j = T i ′ , j ′ T_{i,j}=T_{i',j'} Ti,j​=Ti′,j′​。

copy constraint可理解为enabling memory access，因为我们可以要求execution trace中的后一值等于前一值。

3. arithmetic circuit的特例

arithmetic circuit的表达规则为：

• 每一行表示1个gate；
• 每一行中的值（row values）表示该gate对应的incoming wire values和outgoing wire values
• 若需表达 fan-in t t t circuits，则设置 w = t + 1 w=t+1 w=t+1。

如，对于 fan-in 2 2 2，其row values 为 v 1 , v 2 , v 3 v_1,v_2,v_3 v1​,v2​,v3​，分别为该row 对应gate的left wire value、right wire value 和 output wire value。

3.1 transition constraint

对于transition constraint，其不会用到下一行的values T i + 1 , 1 , ⋯   , T i + 1 , w T_{i+1,1},\cdots,T_{i+1,w} Ti+1,1​,⋯,Ti+1,w​，transition constraint仅check 其所在行中的值是否符合addition gate或multiplication gate规则。可借助 3个selectors 和 1个constraint polynomial P P P of degree t + 1 t+1 t+1。 如对于fan-in 2 2 2 circuit，可定义为： P ( q L , q R , q M , x 1 , x 2 , x 3 ) = q L ⋅ x 1 + q R ⋅ x 2 + q M ⋅ x 1 x 2 − x 3 P(q_L,q_R,q_M,x_1,x_2,x_3)=q_L\cdot x_1+q_R\cdot x_2+q_M\cdot x_1x_2-x_3 P(qL​,qR​,qM​,x1​,x2​,x3​)=qL​⋅x1​+qR​⋅x2​+qM​⋅x1​x2​−x3​

具体为：

• 对于addition gate，设置 q L ( i ) = q R ( i ) = 1 , q M ( i ) = 0 q_L(i)=q_R(i)=1,q_M(i)=0 qL​(i)=qR​(i)=1,qM​(i)=0；
• 对于multiplication gate，设置 q L ( i ) = q R ( i ) = 0 , q M ( i ) = 1 q_L(i)=q_R(i)=0,q_M(i)=1 qL​(i)=qR​(i)=0,qM​(i)=1。

3.2 copy constraint

copy constraint用于enforce the wiring of the circuit。如，对于4th gate，其left wire 为 the second gate的output wire，则可表示为： T 2 , 3 = T 4 , 1 T_{2,3}=T_{4,1} T2,3​=T4,1​

4. 基础技术

Turbo-PLONK中主要使用了2个基础技术：

• Look Ups
• Interleaving PLONK Gates

4.1 Look Ups

假设有2个selector q 1 , q 2 q_1,q_2 q1​,q2​，为了enforce： row i i i的第一个值 等于 q b ( i ) q_b(i) qb​(i)，其中 b b b为同一行中的第二个值。

则相应的constraint可表示为：【即 x 1 = q x 2 x_1=q_{x_2} x1​=qx2​​。当 x 2 x_2 x2​等于1时，有 x 1 = q 1 x_1=q_1 x1​=q1​；当 x 2 = 2 x_2=2 x2​=2时，有 x 1 = q 2 x_1=q_2 x1​=q2​。】 x 1 = − q 1 ⋅ ( x 2 − 2 ) + q 2 ⋅ ( x 2 − 1 ) x_1=-q_1\cdot (x_2-2)+q_2\cdot (x_2-1) x1​=−q1​⋅(x2​−2)+q2​⋅(x2​−1)

接下来，如果需要在两个值之间进行选择，或者选择其负数，可引入row中的第三个值，设其为 1 1 1或 − 1 -1 −1，相应的constraint可表示为：【即 x 1 = x 3 ⋅ q x 2 x_1=x_3\cdot q_{x_2} x1​=x3​⋅qx2​​。其中 x 3 x_3 x3​取 1 1 1或 − 1 -1 −1。】 x 1 = ( − q 1 ⋅ ( x 2 − 2 ) + q 2 ⋅ ( x 2 − 1 ) ) ⋅ x 3 x_1=(-q_1\cdot (x_2-2)+q_2\cdot (x_2-1))\cdot x_3 x1​=(−q1​⋅(x2​−2)+q2​⋅(x2​−1))⋅x3​

4.2 Interleaving PLONK Gates

之前设计的transition gate对应为a set of 2 w + l 2w+l 2w+l-variate polynomials，伴随有 l l l个selector polynomials。 针对每一行，可专门设计不同的subset of constraints depending on the row。

如，已知2个gate G 1 , G 2 G_1,G_2 G1​,G2​，需仅对 G 1 G_1 G1​ enforce some row transitions，而仅对 G 2 G_2 G2​ enforce 另一组row transitions， G 1 G_1 G1​和 G 2 G_2 G2​之间有一些共同的constraints。

通用的解决方案为：增加2个selector q G 1 , q G 2 q_{G_1},q_{G_2} qG1​​,qG2​​，根据指定row中相应的gate是否激活对应取值为 0 或 1 0或1 0或1。然后multiply each constraint P P P in G i G_i Gi​ by q G i q_{G_i} qGi​​。同时，defIne the new gate’s constraints to be the union of these constraints from both gates。

5. Fixed-base scalar multiplication

在椭圆密码学中，最贵的操作之一就是scalar multiplication： 假设scalar k = 15 k=15 k=15，对应的二进制表示为 0 b 1111 0b1111 0b1111，即 k k k的hamming weight为4。若采用如上double-and-add算法，需要3次point doubling操作和4次point addtion操作，整个操作的复杂度高度依赖于the number of set 或 hamming weight，且加法操作仅在当前bit不为0时执行。

为了减少scalar multiplication操作的计算复杂度，方法之一是reduce hamming weights of the scalar。

假设 # E ( F q ) = r h \#E(\mathbb{F}_q)=rh #E(Fq​)=rh，其中 r r r为prime的， h h h很小，使得 r ≈ q r\approx q r≈q。point P 和 Q P和Q P和Q均具有order r r r，scalar k k k为在 [ 1 , r − 1 ] [1,r-1] [1,r−1]区间的随机值。 k k k的二进制表示为 ( k t − 1 , ⋯   , k 2 , k 1 , k 0 ) 2 (k_{t-1},\cdots,k_2,k_1,k_0)_2 (kt−1​,⋯,k2​,k1​,k0​)2​，其中 t ≈ m = ⌈ log ⁡ 2 q ⌉ t\approx m=\left \lceil \log_2 q \right \rceil t≈m=⌈log2​q⌉。若point P P P为fixed且storage is availabe，则point multilication 可借助pre-computation table来加速。 具体的加速方法有：【本节主要关注fixed-base下对hamming weight的reduce。】

• Non-Adjacent Form（NAF）
• Window Method
• Zero Occurence Evaluation
• Lim and Lee’s Method
• Tsaur and Chou’s Method
• Direct Doubling Method
• Mohamed, Hashim and Hutter’s Method

本文主要关注NAF算法： 若 P = ( x , y ) ∈ E ( F q ) P=(x,y)\in E(\mathbb{F}_q) P=(x,y)∈E(Fq​)，则 − P -P −P表示为 − P = ( x , − y ) -P=(x,-y) −P=(x,−y)。因此，point减法 可转换为 point加法 进行运算。

针对NAF的主要优化策略为：

• 1）约定 scalar s s s NAF representation；
• 2）选择每轮中要add的correction point；
• 3）add the selected point；
• 4）initialization gate

5.1 the NAF scalar representation

假设scalar s s s的取值范围为 { 1 , . . , M } \{1,..,M\} {1,..,M}，其中 M < r / 2 M