Guest Lecturer: Jordi Baylina Zero Knowledge  Proofs Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang Section 1
Learning objective: ● ● ● understand the concept of rollups how they can help achieve scalability the components of a zero knowledge rollup
シ

4

5

newStateRoot 6
ZKP MOOC R1CS Polynomial Identities/ State Machines PIL Polynomial Identity Language zkASM cP polygon zkEVM ZKP MOOC
8
Section 2
Learning objective: ●    Overview of PIL and why it is important ● ● Creating circuits with polynomials Introduction to state machines
F 0xfffffff000001 ai+1 = ai-1 + ai ZKP MOOC
fibonacci.circom
pragma circom 2.0.6; template  Fibonacci (n)  { signal input a0; signal input al; signal output out; signal im[n-1]; for (var i=0; i<n-1; i++) { if (i==0) { im[i] <== a0 + a1; } else if (i==1) { im[i] <== a1 + im[0]; } else { im[i] <== im[i-2] + im[i-1]; } } out <== im[n-2]; component main = Fibonacci(1024);
aBeforeLast(ωx) = aLast(x) aLast(ωx) = aBeforeLast(x) + aLast(x)
fibonacci.pil constant %N = 1024;
13
fibonacci.js const { FGL } = require("pil-stark"); module.exports.buildConstants = async function (pols) { const N = pols.ISLAST.length; for ( let i=0; i<N; i++) { pols.ISLAST[i] = (i == N-1) ? 1n : 0n; - → module.exports.execute = async function (pols, input) { const N = pols.aLast.length; pols.aBeforeLast[0] = BigInt(input[0]); pols.aLast[0] = BigInt(input[1]); for (let i=1; i<N; i++) { pols.aBeforeLast[i] =pols.aLast[i-1]; pols.aLast[i] = FGL.add( pols.aBeforeLast[i-1], pols.aLast[i-1] ); - return pols.aLast[N-1]; }
fibonacci.test.js
const assert = require("assert"); const path = require("path"); const { FGL, starkSetup, starkGen, starkVerify } = require("pil-stark"); const { newConstantPolsArray, newCommitPolsArray, compile, verifyPil } = require("pilcom"); const smFibonacci = require("../src/fibonacci.js"); describe("test fibonacci sm", async function () { this.timeout(1000000); let constPols, cmPols, pil; it("It should create the pols main", async () => { pil = await compile( FGL, path.join(__dirname, "../src/fibonacci.pil")); constPols =  newConstantPolsArray(pil); await smFibonacci.buildConstants( constPols.Fibonacci); cmPols = newCommitPolsArray(pil); const result = await smFibonacci.execute( cmPols.Fibonacci, [1,2]); console.log("Result: " + result); const res = await verifyPil( FGL, pil, cmPols, constPols); assert (res.length == 0); }); it("It should generate and verify the stark", async () => { const starkStruct = { nBits: 10, nBitsExt: 14, nQueries: 32, verificationHashType : "GL", steps: [ {nBits: 14}, {nBits: 9}, {nBits: 4} } ; const setup = await starkSetup( constPols, pil, starkStruct ) ; ) ; const resP = await starkGen( cmPols, constPols, setup.constTree, setup.starkInfo const resV = await starkVerify( resP.proof, resP.publics, setup.constRoot, setup.starkInfo ) ; assert(resV==true); }); });
namespace PermutationExample(%N); pol commit a, b; a is b;
namespace PermutationExample(%N); pol constant SELB, B1, B2; pol commit selA, a1, a2; selA { a1, a2 } is SELB { B1, B2 };
namespace PlookupExample(%N); pol commit a, b; a in b;
18

namespace PlookupExample(%N); pol constant SELB, B1, B2; pol commit selA, a1, a2; selA { a1, a2 } in SELB { B1, B2 };
namespace ConnectionExample(%N); pol constant S; pol commit a; a connect S;
20

namespace PermutationExample(%N); pol constant SELB, B1, B2; pol commit selA, a1, a2; { a1, a2, a3 } connect { S1, S2, S3 };
21

// Plonk circuit namespace main; pol committed a, b, c pol constant Sa, Sb, Sc; pol constant Q1, Qr, Qm, Qo, Qc; pol constant L1; // 1, 0, 0, … public publicInput = a(0); {a, b, c} connect {Sa, Sb, Sc}; pol ab = a*b; Ql*a + Qr*b + Qo*c + Qm*ab + Qc = 0; L1 * (a - :publicInput) = 0;
22

pragma circom 2.0.6; pragma custom templates; template custom CMul() { signal input ina[3]; signal input inb[3]; signal output out[3]; var A = (ina[0] + ina[1]) * (inb[0] + inb[1]); * (inb[0] + inb[2]); var B = (ina[0] + ina[2]) var C = (ina[1] + ina[2]) * (inb[1] + inb[2]); var D = ina[0]*inb[0]; var E = ina[1]*inb[1]; var F = ina[2]*inb[2]; var G = D-E; out[0] <-- C+G-F; out[1] <-- A+C-E-E-D; out[2] <-- B-G; }
●    Can be used as normal templates. ●    Witness calculator is generated by CIRCOM like any other template. ●    No constraints are allowed. ●    All the custom gates are exported to the .r1cs file. ●    This allows to do a circuit in circom and proof/verify it with a STARK! ●    Supported primes in circom: BN128, BLS-12381, Goldilocks
ZKP MOOC

// Plonk circuit namespace main; pol committed a, b, c pol constant Sa, Sb, Sc; pol constant Ql, Qr, Qm, Qo, Qc; pol constant L1; // 1, 0, 0, … public publicInput = a(0); {a, b, c} connect {Sa, Sb, Sc}; pol ab = a*b; Ql*a + Qr*b + Qo*c + Qm*ab + Qc = 0; L1 * (a - :publicInput) = 0;
25
Section 3
Learning objective: how to use PIL to  build a processor twenth c/Sh
newStateRoot pol op = A*inA + B*inB + C*inC + D*inD + E*inE + freeIn*inFreeIn + CONST; A’ = (op - A) * setA + A; B’ = (op - B) * setB + B; C’ = (op - C) * setC + C; D’ = (op - D) * setD + D; E’ = (op - E) * setE + E; pol commit inv; pol isZero = 1 -op * inv; isZero * op = 0; pol jmp = JMPIZ*isZero; PC’ = jmp * (addr - (PC+INC)) + (PC+INC);
29

ROM
Execution Trace
Memory
MAIN.arith {MAIN.A , MAIN.B , MAIN.C , MAIN.D, MAIN.op} in ARITH.latch {ARITH.A , ARITH.B , ARITH.C , ARITH.D , ARITH.E}; MAIN
ROM STORAGE o ● ● Multiple R/W 1 Access per CLOCK Paged for handling Ethereum CALL contexts ● 32 byte alignment sub stat machine. ● ● The Code that always execute the prover It cannot be modified. ● ● Sparse Merkle Tree Goldilocks Poseidon hash function ● ● Single tree for the system Hashes of the smart contract codes are in the tree.
33
EVM Processor RAM ROM BINARY ARITHMETIC o Operations done byte to byte with a carry from a plookup table o 256 bits arithmetic operations o ● o o Range check of inputs and outputs 32 CLOCKs per operation Includes EC addition formulas for ECDSA multiplication. HASH ● Binary circuit of ANDn and XOR We use a plookup to do various circuits in parallel We currently can do 468 keccakf’s in the current circuit. (N = 2^23). o ADD o SUB o LT & SLT o EQ
AND
XOR A*B + C = D*2^256 + E ● ●
34
OR Section 4 zkROM enabling EVM Emulation Learning objective: how to run a program on top of the processor
Ethereum Transaction processor FREE Input the Transactions and the hash must match. zkCounters to prevent the proof to fail (DoS). Some examples: ● Opcodes RLP Processing ●
36
ZKP MOOC
2109 opPUSH31: 2110 31 => D 2111 $t => B 2112 0 - B 2113 2114. 2115 opPUSH32: 2116 32 => D 2117 $ => Bl 2118 0 - B 2119 2120 2121 opDUP1: 2122 2123 2124 %MAX_CNT_STEPS - STEP - 120 :JMPN(outOfCounters) 2125 2126 2127 2128 2129 2130 2131 2132 2133 opDUP2: 2134 2135 %MAX_CNT_STEPS - STEP - 120 :JMPN(outOfCounters) 2136 2137 2138 SP - 1 => SP $: => A 1024 - SP A 1024 - SP GAS-3 => GASo :JMPN(stackUnderflow) :MLOAD(SP++) :JMPN(stackOverflow) :MSTORE(SP++) :JMPN(stackOverflow) :JMPN(outOfGas) : JMP ( readCode ) :JMPN(stackUnderflow) SP = 2 => SP :MLOAD(SP) $ => A :MLOAD(isCreateContract) : JMPN(opAuxPUSHB) : JMP ( opAuxPUSHA ) :MLOAD(isCreateContract) : JMPN(opAuxPUSHB) : JMP ( opAuxPUSHA )
Learning objective: Understand how to compress and aggregate the proof and verify them on-chain
38
Creating to this Ashurtenstock
.
Number of Commited Polynomials: 669 Number of permutation checks: 18 Number of plookups: 29 Number of connection checks (copy constraints): 2 Total number of columns: 1184 Degree of the polynomials (rows) n= 2²³ Max degree of the constraint polynomial: 3n Blowup factor: 2 Proof computation time: 129s Size of the proof: 1.9M
42
newAccInputHash ZKP MOOC
Circom works in goldilocks Signals in 12 columns Gates: Standard PLONK gates (4 per row) Poseidon STEP (12 inputs 12 outputs). We use 2 rows for a step. 31 rows for a full poseidon hash. FFT4  FFT of 4 elements in extension 3 (12 inputs - 12 outputs). Basic block to build bigger FFTs. D = A*B + C in extension 3 (1 row) Polynomial evaluation custom gate in extension3. newA = (((oldA * x + C3)*x + C2)*x +C1)*x + C0 . This uses 2 rows and can be used to compute evaluations of pols of bigger size. Given a circom circuit it can be converted to a PIL, a constants polynomial and a witness computation program.
ZKP MOOC

Number of Commited Polynomials: 12 Number of permutation checks: 0 Number of plookups: 0 Number of connection checks (copy constraints): 1 Total number of columns: 65 Degree of the polynomials (rows) n= 2²² Max degree of the constraint polynomial: 5n Blowup factor: 4 Proof computation time: 14s Size of the proof: 494K
45
newStateRoot newAccInputHash loaclExitRoot newBatchNum
Number of Commited Polynomials: 12 Number of permutation checks: 0 Number of plookups: 0 Number of connection checks (copy constraints): 1 Total number of columns: 45 Degree of the polynomials (rows) n= 220 Max degree of the constraint polynomial: 9n Blowup factor: 16 Proof computation time: 10s Size of the proof: ~260K
52
● ● Forces the ROOTC_recursive2 in the circuit STARK is generated with BN128 poseidon
Number of Commited Polynomials: 12 Number of permutation checks: 0 Number of plookups: 0 Number of connection checks (copy constraints): 1 Total number of columns: 45 Degree of the polynomials (rows) n= 219 Max degree of the constraint polynomial: 9n Blowup factor: 16 Proof computation time: 17s Size of the proof: ~505K
54

Number of constraints: 16M Proof computation time: 120s Size of the proof: <1k Gas cost: 362K (Full proving TX)
ZKP MOOC
56
Section 6
Learning objective: Understand the sustained evolution of the zkEVM (Performance, Security and Decentralization
The next work in the pipeline to evolve zkEVM: Transition from a Type 3 to Type 2 zkEVM according to Vitalik’s ZK Rollups categorization Data compression optimizations EIP 4844 Variable size Prover Security Decentralized Sequencer
ZKP MOOO
58

zkEVM Documentation https://wiki.polygon.technology/docs/zkEVM/introduction/ Core repos ● zkevm-proveris ● zkevm-rom ● zkevm-prover ● zkevm-node ● zkevm-contracts ● zkevm-bridge-service ● zkevm-bridge-ui zkevm-techdocs zkEVM specific tools and libraries ● zkevm-commonis ● zkasmcom ● zkevm-testvectors ● zkevm-storagerom Generic tools and libraries ● pilcom pil-stark
59