ZK Circuit Development

@nullity00

Our Main Characters

​

​

​

Bob Alice

The problem :

Alice has a secret array of 8 alphabets.

Secret = [ e, t, h, e, r, e, u, m ]

Alice wants to check if Bob has the same secret.

#1 : Hey Bob, is the second letter of the secret t ?

#2 : Hey Bob, send me hash of the 2nd alphabet.

Secrets aren’t leaked.

Ref : Justin Thaler’s Proofs & Arguments (Chapter 1)

Ref : SNARKS = PCS + IOP (Lec 2 from MOOC)

Part 1 (Hashing of alphabets)

​

• Message → Polynomial
• Eg: [1, 3, 4] → x2 + 3x + 4
• a1 * G + a2 * G2 + a3 * G3 + ..
• Polynomial Commitment Scheme

​

Commitment - hide now, reveal later

Part 2 (Interaction with Bob)

​

• Hey the hash of 2nd …
• Hey you just sent me your polynomial commitment,
• I’m gonna open it at a random point !
• Made Non Interactive, to avoid collusion

Zk SNARK

ZK - Zero Knowledge (Doesn’t reveal anything)

S - Succinct (Short)

N - Non Interactive

ARK - ARguments of Knowledge (Proof that prover possesses info)

When ZK ?

hiding - reveals nothing about the committed polynomial

Binding - cannot produce two valid openings for a commitment

A bigger problem

Verify if all the txns done so far in the EVM Network is right

​

Circuit

(A ZK Program)

Proof System

(zkSNARK)

Proof

Our characters

Prover Verifier

Circom | https://zkrepl.dev/ | https://circomscribe.dev/

pragma circom 2.1.6;

​

template Circuit() {

signal input a;

signal input b;

signal output c;

c <== a + b ;

c === 77;

}

​

component main = Circuit();

​

/* INPUT = {

"a": "5",

"b": "71"

} */

​

Prove that you know two numbers a & b which when added equate to 77

​

​

Circuit.a + Circuit.b - Circuit.c = 0

77 - Circuit.c = 0

​

​

Circom

• Signals are immutable, types : Inputs, output, intermediate
• Variables (var) : used to build up constraints
• All operations have to be of the form a*b + c
• Non quadratic constraints are not allowed ( x * x = x² )
• ← assignment operator (Not calculated by the verifier)
• === constraint generator
• <== Assign & constraint in a single step
• Constant Computation Graph
• Endless loops
• Scalar field is ~ 2²⁵⁴

Security Issues

• Malicious Provers
• Do not use <-- unless you know what you are doing
• Do not leave inputs unassigned
• If you use an integer of 2²⁵⁵ bits in circom, there would be an overflow
• Always check bit lengths

Let’s generate a proof & verify it using a Smart contract

1. Install circom : https://docs.circom.io/getting-started/installation/
2. Install snark js : https://github.com/iden3/snarkjs
3. Tutorials : https://www.rareskills.io/post/circom-tutorial , https://medium.com/@yujiangtham/writing-a-zero-knowledge-dapp-fd7f936e2d43
4. https://github.com/nullity00/demo-circ

ZK Circuit dev ecosystem

Languages

• Circom
• Noir
• Zokrates
• Leo
• Cairo
• Lurk

Libraries

• Bellman
• arkworks
• Halo2 (zcash)
• Halo2 (pse/axiom)
• Plonky2
• Plonky2x(succinct)

Proof systems

• Groth16(kzg+groth)
• Plonk(ipa + plonk)
• Plonk(kzg + plonk)
• plonky2(fri + plonk)
• boojum(fri+plonk)

r1cs

Column types in Halo 2

advice columns

private inputs & other witness

instance columns

public inputs

fixed columns

constants &

lookup tables

selector columns

control gates

Vary over each proof

Circuit configuration

About the Halo2 Table

• Column is a polynomial
• For each column i in the table, construct a Lagrange polynomial L_i(x)
• Rows are roots of unity (1, ω, ω², ω³, ω⁴, ω⁵, ω⁶, ω⁷, ….)
• Cell = Evaluation of a polynomial at the root of unity ..
• Evaluation of column i at cell j, L_i(ω^j) = …
• Selector - gate on / off
• 2^k rows & m columns

Circom resources

• https://github.com/iden3/circomlib
• https://docs.circom.io/
• https://github.com/arnaucube/awesome-circom
• https://github.com/iamsahu/awesome-circom
• https://github.com/stars/nullity00/lists/circom
• ​

Noir Resources

https://noir-lang.org/

https://github.com/stars/nullity00/lists/noir

https://github.com/noir-lang/noir-starter

https://github.com/noir-lang/awesome-noir

https://github.com/Miyamura80/ZKMicrophone

​

​

PLONK

https://github.com/nullity00/plonkathon

https://youtu.be/NqrVcDuQ8hM?si=BZDVcWKT_Uj-yF9g

https://youtu.be/A0oZVEXav24?si=p5tv4tWbJrC7bEgN

Plonk by David Wong : https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

https://github.com/dusk-network/plonk

https://github.com/EspressoSystems/jellyfish

​

More Plonk

https://github.com/ZK-Garage/plonk

https://github.com/fluidex/plonkit

https://github.com/barryWhiteHat/plonk_tutorial

https://github.com/adria0/plonk-by-fingers

https://github.com/AztecProtocol/plonk-with-lookups

https://github.com/kcharbo3/Plonk-By-Hand

​

Halo2 Resources

• Intro to Halo2 https://docs.google.com/presentation/d/1UpMo2Ze5iwzpwICPoKkeT04-xGFRp7ZzVPhgnidr-vs/edit#slide=id.p
• Intro to Halo2 API https://docs.google.com/presentation/d/1HUJPHXaqbmVsnmI331mJn9nRuZkeHQZkIMpWBOJ1itk/edit#slide=id.p1
• 0xPARC’s course https://learn.0xparc.org/materials/halo2/learning-group-1/introduction
• Differences between ZCash & PSE’s fork https://www.youtube.com/watch?v=ihPcnctm4q4

• Vitalik’s article on Halo : https://vitalik.ca/general/2021/11/05/halo.html
• Must watch Halo2 explainer by Scroll : https://www.youtube.com/watch?v=60lkR8DZKUA

​

We’d be using Axiom’s halo2-lib for circuit development

• https://github.com/axiom-crypto/halo2-lib
• https://docs.axiom.xyz/zero-knowledge-proofs/getting-started-with-halo2
• Get started here : https://hackmd.io/@axiom/HyoXzD7Zh

Plonky2

https://youtu.be/-pucWUDn5Hw?si=o_36u9MxqLaiGJGe

https://youtu.be/p77Av0sXKQ4?si=mhPtwZPSOkCzm8rn

Battle zips : https://youtu.be/DXaEScKJ4xY?si=XP5L4piHuQO9r91o

https://github.com/stars/nullity00/lists/plonky2

https://github.com/succinctlabs/plonky2x-example

https://github.com/succinctlabs/succinctx

​