A turbo-PLONK program P can be thought of as sequence of states vāFw, where the state size w is chosen by the program designer. The proof size and prover run time increase linearly in w and standard choices are 3 or 4.
A valid execution trace Tā(Fw)t for Psatisfies P's transition gate and copy constraint.
transition gate - A transition constraint of P is a 2w+ā -variate degree at most d polynomial P , where d is the degree of P, and is recommended to be set to w+1, and ā is the selector number.
The transition gate of P consists of all the transition constraints together with ā selector vectors q1ā,ā¦,qāāāFt. T is said to satisfy the transition gate if for each transition constraintiā[t] , P(Ti,1ā,ā¦,Ti,wā,Ti+1,1ā,ā¦,Ti+1,wā,q1ā(i),ā¦,qāā(i))=0.
copy constraint - this is a partition of wĆt into distinct sets {Siā} . T is said to satisfy the copy constraint if Ti,jā=Tiā²,jā²ā whenever (i,j) and (iā²,jā²) belong to the same set in the partition.
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 t circuits we'll use w=t+1. For example, for fan-in 2 the row values v1ā,v2ā,v3ā 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" valuesTi+1,1ā,ā¦Ti+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 P of degree t+1 . E.g., for fan-in 2 we use:
P(qLā,qRā,qMā,x1ā,x2ā,x3ā):=qLāā
x1ā+qRāā
x2ā+qMāā
x1āx2āāx3ā
By setting qLā(i)=qRā(i)=1,qMā(i)=0 for an addition gate and qLā(i)=qRā(i)=0,qMā(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,1ā.