Polygon zkEVM recursive proof technical documentation (5) – Appendix: Implementing proof composition with SNARKjs and PIL-STARK

Previous blogs include:

Polygon zkEVM recursive proof technical documentation (1) [mainly describes the combination, recursion and aggregation of related tools and proofs]
Polygon zkEVM recursive proof technical documentation (2) – Polygon zkEVM architecture design
Polygon zkEVM recursive proof technical documentation (3) – code compilation and operation
Polygon zkEVM recursive proof technical documentation (4)–C12 PIL Description

This article focuses on:

Appendix: Implement proof composition with SNARKjs and PIL-STARK.

7. Appendix: Using SNARKjs and PIL-STARK to achieve proof composition

This section will demonstrate the proof capabilities of the current SNARKjs and PIL-STARK tool stacks. In particular, it demonstrates how to implement certain types of proof combinations that exceed the original capabilities of SNARKjs and PIL-STARK.

Next, we will take the following statement as an example:

“I know a (secret) value

a

1

=

1

a_1 = 1

a1?=1 such that the

(

2

5

+

1

=

)

(2^5 + 1 =)

(25 + 1=)

33

33

33-th element of the Fibonacci sequence on (public) input

a

0

=

1

a_0 = 1

a0?=1 and

a

1

a_1

a1? is equal to

3524578

3524578

3524578.”

The first two sections of this article will show how to generate (depth 0) proof.

7.1 Depth 0: Circom + SNARKjs

Using Circom to represent the above statement means that the Fibonacci sequence calculation is expressed in R1CS format:

This circuit specific instance (i.e.

a_0=1,a_1=1

The execution trace of a0?=1,a1?=1) is:

The numbers in red font are information known only to Prover, while the numbers in green font are information known to both Prover and Verifier.
After describing the circuit with Circom, SNARKjs can be used to generate a valid zk-SNARK proof for it: [Currently SNARKjs supports Groth16, Fflonk and Plonk. For simplicity, they are all called Plonk in the following. 】

1) Compile circuit:

$ mkdir -p build & amp; & circom src/fibonacci.circom --r1cs --wasm -o build
template instances: 1
non-linear constraints: 0
linear constraints: 0
public inputs: 1
public outputs: 1
private inputs: 1
private outputs: 0
Wires: 3
labels: 35

2) In the same path, create the input.json input file for the circuit:

$ cat <<EOT > input.json
{ "a0": 1, "a1": 1}
EOT

3) Calculate witness for this input:

$ snarkjs wc build/fibonacci_js/fibonacci.wasm src/input.json build/fibonacci.wtns
out = 3524578

4) Download a large enough “powers of tau” file:

$ wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_10.ptau -O build/powersOfTau.ptau

5) Preprocess the circuit:

$ snarkjs pks build/fibonacci.r1cs build/powersOfTau.ptau build/fibonacci.zkey
[INFO] snarkJS: Reading r1cs
[INFO] snarkJS: Plonk constraints: 2
[INFO] snarkJS: Setup Finished

6) Export the verification key for proof verification:

$ snarkjs zkev build/fibonacci.zkey build/fibonacci-vk.json
[INFO] snarkJS: EXPORT VERIFICATION KEY STARTED
[INFO] snarkJS: > Detected protocol: plonk
[INFO] snarkJS: EXPORT VERIFICATION KEY FINISHED

7) Generate Plonk proof:

$ snarkjs pkp build/fibonacci.zkey build/fibonacci.wtns build/fibonacci.proof.json build/fibonacci.public.json

8) Finally, verify the proof:

$ snarkjs pkv build/fibonacci-vk.json build/fibonacci.public.json build/fibonacci.proof.json
[ INFO ] snarkJS : OK!

7.2 Depth 0: PIL + PIL-STARK

Using PIL to express the above statement means that the calculation of the Fibonacci sequence needs to be expressed in AIR format, that is, based on domain

< g >

A set of polynomial constraints for G=. At this time, if for all

∈

x\in G

x∈G, the following constraints:

If all are satisfied, the original statement is true.
Here:

L

1

,

L

32

L_1,L_{32}

L1?,L32? are the first and last ones based on

G

G

Lagrange polynomial of G
a

0

,

a

1

a_0,a_1

a0?, a1? are defined to maintain each state transition value of the Finbonacci sequence.

This state machine specific instance (i.e.

(

)

(

)

a_0(g)=1,a_1(g)=1

The execution trace of a0?(g)=1,a1?(g)=1) is:

After describing the circuit in PIL, you can use pil-stark to generate a valid eSTARK proof for the above example:

1) Fill the execution trace with constant polynomials:

$ mkdir -p build & amp; & amp; node src/main_buildconst.js -o build/fibonacci.const
file Generated Correctly

2) Fill in the committed polynomial in the execution trace:

$ node src/main_buildcommit.js -i src/input.json -o build/fibonacci.commit
Result: 3524578
file Generated Correctly

3) Verify whether the execution trace generated in the first 2 steps is valid:

$ node node_modules/pilcom/src/main_pilverifier.js build/fibonacci.commit -p src / fibonacci.pil -c build/fibonacci.const
PIL OK!!

4) In the same path, create a starkstruct.json file with eSTARK parameters:

$ cat << EOT > starkstruct.json
{
"nBits": 5,
"nBitsExt": 6,
"nQueries": 64,
"verificationHashType": "GL",
"steps": [
{ "nBits": 6},
{ "nBits": 4},
{ "nBits": 2}
]
}
EOT

5) According to the starkstruct.json file, generate the starkinfo.json file required for eSTARK:

$ node node_modules/pil-stark/src/main_genstarkinfo.js -p src/fibonacci.pil -s src/starkstruct.json -i build/starkinfo.json
filesGenerated Correctly

6) Preprocessing state machine:

$ node node_modules/pil-stark/src/main_buildconsttree.js -c build/fibonacci.const -p src/fibonacci.pil -s src/starkstruct.json -t build/fibonacci.consttree -v build/fibonacci. verkey.json
filesGenerated Correctly

7) Generate eSTARK proof:

$ node node_modules/pil-stark/src/main_prover.js -m build/fibonacci.commit -c build/fibonacci.const -t build/fibonacci.consttree -p src/fibonacci.pil -s build/starkinfo. json -o build/fibonacci.proof.json -z build/fibonacci.zkin.json -b build/fibonacci.public.json
filesGenerated Correctly

8) Finally verify the eSTARK proof:

$ node node_modules/pil-stark/src/main_verifier.js -p src/fibonacci.pil -s build/starkinfo.json -v build/fibonacci.verkey.json -o build/fibonacci.proof.json -b build/fibonacci.public.json
Verification Ok!!

7.3 Depth 0: Circom + PIL-STARK

This section will show how to generate an eSTARK proof for a Fibonacci circuit written directly in Circom:

1) Compile circuit: [Specify using Goldilocks domain]
```
$ mkdir -p build & amp; & circom src/fibonacci.circom --O1 --prime goldilocks --r1cs --wasm -o build
template instances: 1
non-linear constraints: 0
linear constraints: 31
public inputs: 1
public outputs: 1
private inputs: 1
private outputs: 0
Wires: 34
labels: 35
```
Note that the Goldilocks prime domain is used here, rather than the prime domain (default in Circom) that defines the BN128 elliptic curve. The reason is that currently state machines written in PIL only support Goldilocks domains.
2) In the same path, create the input file input.json for the circuit:

$ cat << EOT > input.json
{ "a0": 1 , "a1": 1}
EOT

3) Based on the input, calculate witness:

$ snarkjs wc build/fibonacci_js/fibonacci.wasm src/input.json build/fibonacci.wtns
out = 3524578

4) The witness (R1CS witness to be precise) has been calculated. Next, the R1CS representation of the circuit needs to be converted into the equivalent Plonk representation of the same circuit:

$ node node_modules/pil-stark/src/main_plonksetup.js -r build/fibonacci.r1cs -p build/fibonacci.pil -e build/fibonacci.exec -c build/fibonacci.const
filesGenerated Correctly

In the output fibonacci.pil, the state machine written in PIL is: [This conversion process will also generate a file fibonacci.const containing constant polynomials. 】

constant % N = 2**6;
namespace Global(%N);
pol constant L1;
pol constant L2;
namespace PlonkCircuit(%N);
pol constant S[3];
pol constant Qm, Ql, Qr, Qo, Qk;
pol commit a[3];
public pub0 = a[0](0);
public pub1 = a[0](1);
Global.L1 * (a[0] - :pub0) = 0;
Global.L2 * (a[0] - :pub1) = 0;
//Normal plot ecuations
pol a01 = a[0]*a[1];
Qm*a01 + Ql*a[0] + Qr*a[1] + Qo*a[2] + Qk = 0;
// Connection equations
{a[0] , a[1] , a[2]} connect {S[0], S[1], S[2]};

5) Fill the committed polynomial into the execution trace:

$ node node_modules/pil-stark/src/main_plonkexec.js -w build/fibonacci.wtns -p build/fibonacci.pil -e build/fibonacci.exec -m build/fibonacci.commit
file Generated Correctly

6) Verify whether the execution trace generated in the previous 2 steps is valid:

$ node node_modules/pilcom/src/main_pilverifier.js build/fibonacci.commit -p build/fibonacci.pil -c build/fibonacci.const
PIL OK!!

7) Create a strakstruct.json file with eSTARK parameters in the same path:
```
$ cat << EOT > starkstruct.json
{
"nBits": 6,
"nBitsExt": 7,
"nQueries": 64,
"verificationHashType": "BN128",
"steps": [
{ "nBits": 7},
{ "nBits": 5},
{ "nBits": 3}
]
}
EOT
```
Please note that the nBits value required here needs to be increased from 5 to 6 because of the overhead of converting R1CS to Plonk (see the fibonacci.pil state machine above for details).
The next step is to repeat the similar process in Section 7.2 to generate eSTARK proof.
8) Based on the starkstruct.json file, generate the starkinfo.json file required for eSTARK:

$ node node_modules/pil-stark/src/main_genstarkinfo.js -p src/fibonacci.pil -s src/starkstruct.json -i build/starkinfo.json
filesGenerated Correctly

9) Preprocessing state machine:

$ node node_modules/pil-stark/src/main_buildconsttree.js -c build/fibonacci.const -p src/fibonacci.pil -s src/starkstruct.json -t build/fibonacci.consttree -v build/fibonacci. verkey.json
filesGenerated Correctly

10) Generate eSTARK proof:

$ node node_modules/pil-stark/src/main_prover.js -m build/fibonacci.commit -c build/fibonacci.const -t build/fibonacci.consttree -p src/fibonacci.pil -s build/starkinfo. json -o build/fibonacci.proof.json -z build/fibonacci.zkin.json -b build/fibonacci.public.json
filesGenerated Correctly

11) Finally verify the eSTARK proof:

$ node node_modules/pil-stark/src/main_verifier.js -p src/fibonacci.pil -s build/starkinfo.json -v build/fibonacci.verkey.json -o build/fibonacci.proof.json -b build/fibonacci.public.json
Verification Ok!!

In the next section, the combination of “PIL-STARK + PIL-STARK” or “PIL-STARK + SNARKjs” will be used to expand the previous two processes.

7.4 Depth 1: Circom + PIL-STARK + SNARKjs

Next, we will show how to make the eSTARK proof of the statement represented by Circom valid, and the generated SNARK proof:

1) Compile circuit:

$ mkdir -p build & amp; & circom src/fibonacci.circom --O1 --prime goldilocks --r1cs --wasm -o build
Everything went okay, safe

2) In the same path, create the input file input.json of the circuit:

$ cat << EOT > input.json
{ "a0": 1, "a1": 1}
EOT

3) Calculate witness based on this input:

$ snarkjs wc build/fibonacci_js/fibonacci.wasm src/input.json build/fibonacci.wtns
out = 3524578

4) According to the calculated witness (R1CS to be precise), convert the R1CS representation of the circuit into the equivalent Plonk representation of the same circuit:

$ node node_modules/pil-stark/src/main_plonksetup.js -r build/fibonacci.r1cs -p build/fibonacci.pil -e build/fibonacci.exec -c build/fibonacci.const
filesGenerated Correctly

5) Fill the execution trace with committed polynomials:

$ node node_modules/pil-stark/src/main_plonkexec.js -w build/fibonacci.wtns -p build/fibonacci.pil -e build/fibonacci.exec -m build/fibonacci.commit
file Generated Correctly

6) Verify whether the execution trace generated in the first 2 steps is valid:

$ node node_modules/pilcom/src/main_pilverifier.js build/fibonacci.commit -p build/fibonacci.pil -c build/fibonacci.const
PIL OK!!

7) Create a strakstruct.json file with eSTARK parameters in the same path:

$ cat << EOT > starkstruct.json
{
"nBits": 6,
"nBitsExt": 7,
"nQueries": 64,
"verificationHashType": "BN128",
"steps": [
{ "nBits": 7},
{ "nBits": 5},
{ "nBits": 3}
]
}
EOT

8) Based on the starkstruct.json file, generate the strakinfo.json file required for eSTARK proof:

$ node node_modules/pil-stark/src/main_genstarkinfo.js -p build/fibonacci.pil -s src/starkstruct.json -i build/starkinfo.json
filesGenerated Correctly

9) Preprocessing state machine:

$ node node_modules/pil-stark/src/main_buildconsttree.js -c build/fibonacci.const -p build/fibonacci.pil -s src/starkstruct.json -t build/fibonacci.consttree -v build/fibonacci. verkey.json
filesGenerated Correctly

10) Generate eSTARK proof:

$ node node_modules/pil-stark/src/main_prover.js -m build/fibonacci.commit -c build/fibonacci.const -t build/fibonacci.consttree -p build/fibonacci.pil -s build/starkinfo. json -o build/fibonacci.proof.json -z build/fibonacci.zkin.json -b build/fibonacci.public.json --proverAddr 0x7BAbF98C66454aF8a3C366F893f99EBa26a15c66
filesGenerated Correctly

11) Verify whether the eSTARK proof is correct:

$ node node_modules/pil-stark/src/main_verifier.js -p build/fibonacci.pil -s build/starkinfo.json -v build/fibonacci.verkey.json -o build/fibonacci.proof.json -b build/fibonacci.public.json
Verification Ok!!

12) Next, generate the eSTARK verifier as a Circom circuit:
```
$ node node_modules/pil-stark/src/main_pil2circom.js -p build/fibonacci.pil -s build/starkinfo.json -v build/fibonacci.verkey .json -o build/verifier.circom
file Generated Correctly
```
Recursion is supported here: if a previously generated eSTARK proof is used as input and a valid SNARK is generated, it can be proved that the eSTARK proof is valid.
13) The circuit in circuits.gl needs to be used to compile the eSTARK verifier circuit:

$ circom build/verifier circom --r1cs --wasm -l node_modules/pil-stark/circuits.bn128 -l node_modules/circomlib/circuits -o build
template instances: 465
non-linear constraints: 2123834
linear constraints: 0
public inputs: 0
public outputs: 1
private inputs: 14682
private outputs: 0
wires: 2125925
labels: 5010997

14) Create the input file input.json for the circuit in the same path:

$ cat << EOT > input.json
{ "a0": 1, "a1": 1}
EOT

15) Calculate witness based on input:

$ snarkjs wc build/verifier_js/verifier.wasm build/fibonacci.zkin.json build/verifier.wtns
out = 3524578

16) Download a large enough “powers of tau” file:

$ wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_16.ptau -O build/powersOfTau.ptau

17) Preprocessing circuit:

$ snarkjs pks build/verifier.r1cs build/powersOfTau.ptau build/fibonacci.zkey
[INFO] snarkJS: Reading r1cs
[INFO] snarkJS: Plonk constraints: 2
[INFO] snarkJS: Setup Finished

18) Export the verification key required to verify the proof:

$ snarkjs zkev build/veirifer.zkey build/veirifer-vk.json
[INFO] snarkJS: EXPORT VERIFICATION KEY STARTED
[INFO] snarkJS: > Detected protocol: plonk
[INFO] snarkJS: EXPORT VERIFICATION KEY FINISHED

19) Generate Plonk proof:

$ snarkjs pkp build/veirifer.zkey build/veirifer.wtns build/veirifer.proof.json build/veirifer.public.json

20) Verify this Plonk proof:

$ snarkjs pkv build/veirifer-vk.json build/veirifer.public.json build/veirifer.proof.json
[INFO] snarkJS: OK!

7.5 unlimited depth with PIL-STARK

This section will focus on:

Fibonacci sequence written in PIL
Generate eSTARK proof for it
And based on the validity of the eSTARK proof, generate an eSTARK proof

The same process above can be repeated continuously to achieve infinite depth of proof composition. As shown in the previous sections, the infinite eSTARK composition finally ends with the final SNARK.

The following process demonstrates the power of the PIL-STARK and SNARKjs tool stack:

1) Fill the execution trace with constant polynomials:

$ mkdir -p build & amp; & amp; node src/main_buildconst.js -o build/fibonacci.const
file Generated Correctly

2) Fill in the committed polynomial in the execution trace:

$ node src/main_buildcommit.js -i src/input.json -o build/fibonacci.commit
Result: 3524578
file Generated Correctly

3) Verify whether the execution trace generated in the first 2 steps is valid:

$ node node_modules/pilcom/src/main_pilverifier.js build/fibonacci.commit -p src/fibonacci.pil -c build/fibonacci.const
PIL OK!!

4) Create a strakstruct.json file with eSTARK parameters in the same path:

$ cat << EOT > fibonacci.starkstruct.json
{
"nBits": 5,
"nBitsExt": 6,
"nQueries": 64,
"verificationHashType": "GL",
"steps": [
{ "nBits": 6},
{ "nBits": 4},
{ "nBits": 2}
]
}
EOT

5) Based on the strakstruct.json file, generate the starkinfo.json file required for eSTARK proof:

$ node node_modules/pil-stark/src/main_genstarkinfo.js -p src/fibonacci.pil -s src/fibonacci.starkstruct.json -i build/starkinfo.json
filesGenerated Correctly

6) Preprocessing state machine:

$ node node_modules/pil-stark/src/main_buildconsttree.js -c build/fibonacci.const -p src/fibonacci.pil -s src/fibonacci.starkstruct.json -t build/fibonacci.consttree -v build/ fibonacci.verkey.json
filesGenerated Correctly

7) Generate eSTARK proof:

$ node node_modules/pil-stark/src/main_prover.js -m build/fibonacci.commit -c build/fibonacci.const -t build/fibonacci.consttree -p src/fibonacci.pil -s build/starkinfo. json -o build/fibonacci.proof.json -z build/fibonacci.zkin.json -b build/fibonacci.public.json
filesGenerated Correctly

8) Verify whether the eSTARK proof is correct:

$ node node_modules/pil-stark/src/main_verifier.js -p src/fibonacci.pil -s build/starkinfo.json -v build/fibonacci.verkey.json -o build/fibonacci.proof.json -b build/fibonacci.public.json
Verification Ok!!

9) Generate Circom circuit for eSTARK verifier:

$ node node_modules/pil-stark/src/main_pil2circom.js -p src/fibonacci.pil -s build/starkinfo.json -v build/fibonacci.verkey.json -o build/verifier.circom
Verification Ok!!

10) Compile the verifier circom circuit:

$ circom --O1 --prime goldilocks --r1cs --wasm build/verifier.circom -l node_modules/pil-stark/circuits.gl -o build
Verification Ok!!

11) Calculate witness based on input

$ snarkjs wc build/verifier_js/verifier.wasm build/fibonacci.zkin.json build/verifier.wtns
out = 3524578

12) Convert the generated verifier circom (r1cs) circuit into a state machine:

$ node node_modules/pil-stark/src/main_plonksetup.js -r build/verifier.r1cs -p build/verifier.pil -c build/verifier.const -e build/verifier.exec
filesGenerated Correctly

13) Fill in the committed polynomial in the execution trace:

$ node node_modules/pil-stark/src/main_plonkexec.js -w build/verifier.wtns -p build/verifier.pil -e build/verifier.exec -m build/verifier.commit
filesGenerated Correctly

14) Verify whether the execution trace generated in the first 2 steps is valid:

$ node node_modules/pilcom/src/main_pilverifier.js build/verifier.commit -p build/verifier.pil -c build/verifier.const
PIL OK!!

15) Create a verifier.starkstruct.json file with eSTARK parameters in the same path:

$ cat << EOT > verifier.starkstruct.json
{
"nBits": 16,
"nBitsExt": 17,
"nQueries": 64,
"verificationHashType": "GL",
"steps": [
{ "nBits": 17},
{ "nBits": 14},
{ "nBits": 10},
{ "nBits": 6}
]
}
EOT

At this point, the previous process can be used to generate eSTARK proof.

16) According to the verifier.starkstruct.json file, generate the verifier.starkinfo.json file required for eSTARK proof:

$ node node_modules/pil-stark/src/main_genstarkinfo.js -p build/verifier.pil -s src/verifier.starkstruct.json -i build/verifier.starkinfo.json
filesGenerated Correctly

17) Preprocessing state machine verifier.pil:

$ node node_modules/pil-stark/src/main_buildconsttree.js -c build/verifier.const -p build/verifier.pil -s src/verifier.starkstruct.json -t build/verifier.consttree -v build/ verifier.verkey.json
filesGenerated Correctly

18) Generate eSTARK proof:

$ node node_modules/pil-stark/src/main_prover.js -m build/verifier.commit -c build/verifier.const -t build/verifier.consttree -p build/verifier.pil -s build/verifier. starkinfo.json -o build/verifier.proof.json -z build/verifier.zkin.json -b build/verifier.public.json
filesGenerated Correctly

19) Verify the eSTARK proof:

$ node node_modules/pil-stark/src/main_verifier.js -p build/verifier.pil -s build/verifier.starkinfo.json -v build/verifier.verkey.json -o build/verifier.proof.json -b build/verifier.public.json
Verification Ok!!

As mentioned before, the Circom circuit can be generated for the eSTARK verifier and the above process can be repeated by following steps 10-18, with each iteration creating a starkstruct.json file.

Reference materials

[1] Polygon zkEVM technical documentation Recursion, aggregation and composition of proofs v.1.1

Appendix: Polygon Hermez 2.0 zkEVM series blog

How ZK-Rollups work
Polygon zkEVM – Introduction to Hermez 2.0
Polygon zkEVM network node
Polygon zkEVM basic concepts
Polygon zkEVM Prover
Polygon zkEVM tools – PIL and CIRCOM
Polygon zkEVM node code analysis
First experience with Polygon zkEVM’s pil-stark Fibonacci state machine
Polygon zkEVM’s pil-stark Fibonacci state machine code analysis
Polygon zkEVM PIL compiler – pilcom code analysis
Polygon zkEVM Arithmetic state machine
Polygon constant polynomial in zkEVM
Polygon zkEVM Binary state machine
Polygon zkEVM Memory state machine
Polygon zkEVM Memory Align state machine
Polygon zkEVM zkASM compiler – zkasmcom
Polygon zkEVM hash state machine – Keccak-256 and Poseidon
Polygon zkEVM zkASM syntax
Polygon zkEVM verifiable computation simple state machine example
Polygon zkEVM zkASM and Ethereum virtual machine opcode corresponding set
Polygon zkEVM zkROM code analysis (1)
Collection of functions in Polygon zkEVM zkASM
Polygon zkEVM zkROM code analysis (2)
Polygon zkEVM zkROM code analysis (3)
Polygon zkEVM formula review
Merkle tree in Polygon zkEVM
Goldilocks domain element circom constraints in Polygon zkEVM
Circom constraints of Polygon zkEVM Merkle tree
Polygon zkEVM FFT and circom constraints for polynomial evaluate calculations
Polygon zkEVM R1CS and Plonk circuit conversion
Sub-constraint system in Polygon zkEVM
Polygon zkEVM transaction analysis
Polygon zkEVM audit and recursive proof
Polygon zkEVM releases public testnet 2.0
Polygon zkEVM test set – creating contract transactions
Recursive STARKs in Polygon zkEVM
Polygon zkEVM gas pricing
Polygon zkEVM zkProver basic design principles and Storage state machine
Polygon zkEVM bridge technical documentation
Polygon zkEVM Trustless L2 State Management Technical Documentation
Custom errors in Polygon zkEVM
Polygon zkEVM RPC service
RPC functionality of Polygon zkEVM Prover
Polygon zkEVM PIL technical documentation
Polygon zkEVM recursive proof technical documentation (1) [mainly describes the combination, recursion and aggregation of related tools and proofs]
Polygon zkEVM recursive proof technical documentation (2) – Polygon zkEVM architecture design
Polygon zkEVM recursive proof technical documentation (3) – code compilation and operation
Polygon zkEVM recursive proof technical documentation (4)–C12 PIL Description