📌
📌
📌
📌
zkproofs proposal
Search…
📌
📌
📌
📌
zkproofs proposal
Proposal: The Turbo-PLONK program syntax for specifying SNARK programs
Common techniques
Example: Fixed-base scalar multiplication
Implementation and Benchmarks
Powered By GitBook
Proposal: The Turbo-PLONK program syntax for specifying SNARK programs

Ariel Gabizon and Zachary J. Williamson (Aztec Protocol)

Introduction

Recent zk-SNARK constructions such as Marlin and PLONK relying on Polynomial commitment schemes are not inherently tied to R1CS constraints to specify the statement to be proven. This is roughly because the verifier equation is checked "in the clear" on a random opening of the prover polynomials, rather than "in the exponent" using a pairing. We provide a framework to capture more general and flexible constraints which we call turbo-PLONK programs. We give an example of how this framework allows for more concise representation of fixed-base elliptic curve scalar multiplication (only 1 turbo-PLONK gate for each two input bits), a primitive useful for constructing Pedersen hashes. We also include benchmarks of proving time for scalar multiplication on the Grumkin curve (a 255 bit curve embedded over bn254). Our results indicate a 2x improvement over Groth16.

Turbo PLONK programs

A turbo-PLONK program
P\mathscr{P}
 can be thought of as sequence of states
v∈Fwv\in \mathbb{F}^w
, where the state size
ww
 is chosen by the program designer. The proof size and prover run time increase linearly in
ww
 and standard choices are 3 or 4.
A valid execution trace
T∈(Fw)tT\in (\mathbb{F}^w)^t
 for
P\mathscr{P}
satisfies
P\mathscr{P}
's transition gate and copy constraint.
transition gate - A transition constraint of
P\mathscr{P}
 is a
2w+ℓ2w+\ell
 -variate degree at most
dd
 polynomial
PP
 , where
dd
 is the degree of
P\mathscr{P}
, and is recommended to be set to
w+1w+1
, and
ℓ\ell
 is the selector number.
The transition gate of
P\mathscr{P}
 consists of all the transition constraints together with
ℓ\ell
 selector vectors
q1,…,qℓ∈Ftq_1,\ldots,q_\ell\in \mathbb{F}^t
.
TT
 is said to satisfy the transition gate if for each transition constraint
i∈[t]i\in [t]
 ,
P(Ti,1,…,Ti,w,Ti+1,1,…,Ti+1,w,q1(i),…,qℓ(i))=0P(T_{i,1},\ldots,T_{i,w},T_{i+1,1},\ldots,T_{i+1,w},q_1(i),\ldots,q_\ell(i)) = 0
.
copy constraint - this is a partition of
w×tw \times t
 into distinct sets
{Si}\{S_i\}
 .
TT
 is said to satisfy the copy constraint if
Ti,j=Ti′,j′T_{i,j} = T_{i',j'}
 whenever
(i,j)(i,j)
 and
(i′,j′)(i',j')
 belong to the same set in the partition.
The copy constraint can be thought of as enabling memory access, since we can force a subsequent value in the execution trace to be equal to a preceding one.

The special case of arithmetic circuits

Let's see how an arithmetic circuit can be represented in this format. Every row will correspond to a gate, and the row values will be the incoming and outgoing wire values of the gate; so to represent fan-in
tt
 circuits we'll use
w=t+1w=t+1
. For example, for fan-in 2 the row values
v1,v2,v3v_1,v_2,v_3
 will correspond to the left,right and output wire values of the gate associated with the row.
The transition constraints will be somewhat "degenerate" in the sense that we won't use the "next row" values
Ti+1,1,…Ti+1,wT_{i+1,1},\ldots T_{i+1,w}
. They will check if the correct input and output relations hold inside the row according to whether it's an addition or multiplication gate. This can be done with 3 selectors and one constraint polynomial
PP
 of degree
t+1t+1
 . E.g., for fan-in 2 we use:
​
P(qL,qR,qM,x1,x2,x3):=qL⋅x1+qR⋅x2+qM⋅x1x2−x3P(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_1 x_2-x_3
By setting
qL(i)=qR(i)=1,qM(i)=0q_L(i)=q_R(i)=1,q_M(i) =0
 for an addition gate and
qL(i)=qR(i)=0,qM(i)=1q_L(i)=q_R(i)=0,q_M(i)=1
 for a multiplication gate, we can see the above equation checks the correct input/output relation in both cases.
The copy constraint will enforce the wiring of the circuit. For example, if the left wire of the 4th gate is the output wire of the second gate, we will enforce
T2,3=T4,1T_{2,3} = T_{4,1}
.
​
Next
Common techniques
Last modified 1yr ago
Copy link
Contents
Ariel Gabizon and Zachary J. Williamson (Aztec Protocol)
Introduction
Turbo PLONK programs
The special case of arithmetic circuits