I will be taking on ZKP MOOC (https://zk-learning.org) this spring. The class starts January 17, 2023. This class aims to bring together students and experts in academia and industry to explore Zero-Knowledge Proofs (ZKP).
ZKP is a classical cryptographic primitive that ensures the validity of data and computations without sacrificing their confidentiality.
Some background notes from ZKP Workshop during CESC:
What does it take to develop a zkSNARK application?
The steps include choosing a problem, generating cryptographic parameters and keys, constructing a proof for the problem, and verifying the proof. Each of these steps has a specific set of requirements and processes associated with it that must be followed to create a valid zkp.
ZkSNARKS understand algebraic constraint system. Write, Express, Code : your computation in a high level manor using ZoKrates, Noir, Circom, Gnark, Cairo etc. and that gets compiled down to the constraint system needed, then you need to decide which zkSNARK do you want to use (different SNARKs to use listed below). Lastly, need to choose algebraic object and find and optimized implementation.
circom, gnark, libsnark.
Optimization to overcome overhead of SNARKs
Need to interface well with existing codebase
How do we build snarks for the next generation: arkworks
Modular - easy to mix-and-match
Rust type system to abstract details and offer reusable interfaces
Ergonomic - easy to write
Encapsulates implementation details to offer secure defaults
Rust cross-compilation and FFI features to enable easy interfacing with other languages
Efficient - easy to get performance matching best
assembly / intrinsic implementations of field and curve arithmetic.
Axis of SNARKS
We have found axis with regards to SNARKS
Prover time
Proof size
Verifier time | yes or no
Trusted Setup preprocessor
I think the main line of thought is that zkps provide a highly needed function of data integrity which crypto and blockchains are driving due to the implications related to pricacy and security.
Internet Security → Secure Communication —> encryption, key exchange.
However the internet is now somewhat ocified.
Blockchain Systems —> data integrity —> signature, commitments, proofs
We are already seeing research across txns, bridges, mempools and other aspects of blockchain networks leveraging zkps for enhancement.
ZKPs a way to convince a verifier that something is true.
Proof is Short & Fast to Verify.
Prover and Verifier
Family of Functions
Prover P, Verifier V
f(x) = y
(P, V) interactive, completeness, soundness.
Verifier knows simulated views and real interactions are indistiguishable.
An L1 Blockchain can monitor the operation of a heard of GPUS using ZKPS.
Here are my notes from the lectures:
Lecture 1
What the verifier can compute after the interaction = what the verifier could have computed before the computation.
The simulation paradigm.
The simulated view and real-view are computationally-indistinguishable.
The poly-time distinguisher.
GIVE ME A SAMPLE.
I need to determine if its from the real view or the simulated view.
If the distinguished can’t tell them apart.
Then they are computationally-indistinguishable.
After receiving a polynomial number of samples, essentially the notion that they are “effectively the same”.
Eg. Instead of my node verifying every single transactions, I will verify a proof from a batch of transactions that is indistinguishable from that of my verifying each txn,
An Interactive Protocol (P, V) is honest-verifier zero-knowledge for a language L if there exist a PPT algorith such that for every x L, the following probability distributions are poly-time indistinguishable.
P,V is a zk interactive protocol if it is complete, sound and zero-knowledge.
PZK = Perfect Zero Knowledge: verifier’s view can be efficiently simulated exactly ‘Simulated views’ = ‘real ‘views’.
SNARK: a succinct proof that a certain statement is true.
The proof is always short and always very fast to verify.
The magic, that we can actually do this.
Not only is the proof fast to verify, I can convince you without revealing the data.
Checking Computation in Polylogarithmic Time.
ZKGPT Summary:
Lecture 1: Introduction to Zero-Knowledge Proofs (ZKPs)
1. The Simulation Paradigm: In Zero-Knowledge Proofs, the verifier's ability to compute after the interaction is equivalent to what they could have computed before the interaction.
2. Computationally Indistinguishable Views: The simulated view and the real view are indistinguishable to polynomial-time distinguishers.
3. Interactive Protocols for Zero-Knowledge: An Interactive Protocol (P, V) is considered honest-verifier zero-knowledge for a language L if a probabilistic polynomial-time (PPT) algorithm exists that ensures the probability distributions for every x in L are polynomial-time indistinguishable.
A Zero-Knowledge Interactive Protocol must be complete, sound, and zero-knowledge.
4. Perfect Zero Knowledge (PZK): The verifier's view can be efficiently simulated exactly, making the simulated views and real views the same.
5. SNARKs - Succinct Non-interactive Arguments of Knowledge: SNARKs are short, fast-to-verify proofs that a particular statement is true. They allow proving statements without revealing underlying data.
6. Scalable Computation Verification: Using ZKPs, nodes can verify a batch of transactions indistinguishable from verifying each individual transaction.
Lecture 2
Slow and expensive computer can verify the work of GPUs.
L1 Blockchain viewed as a slow expensive computer.
Outsourcing computation.
Scalability.
Proof-Based Rollups (zkRollups).
L1 Chain verifies a succint proof that TX were processed correctly.
The L1 chain just verifies a short proof.
Bridging Blockchains: proof of consensus.
Target chain agrees to the state of the locked asset, proof of the state of source chain is what it claims to be, therefore allowing the target chain to mint.
Both of these applications need to be noninteractive.
Prover can prove to each validator.
ZkSNARK Private TX on a public blockchain.
The txn data is not available for everyone to see.
Compliance private TX is compliant with banking laws. (espresso)
Proof that an exchange is solvent in zero knowledge. (Raposa)
Fighting disinformation using ZKs.
C2PA content provenance. embedded certified Signing key skills. Sign the picture with the Metadata as well.
Embedded in the raw image data.
Post processing problem
Resized, Cropped etc. AP liste allowed Ops
Laptop needs original image data for verification.
A solution using snarks. Replace the signaturewith a zk snark. The editing software will generate a proof. I know the original image and valid signature from that original image.
The Metadata is equal to the original. The laptop will verify the data and show the Metadata.
Succint proofs. Fast to verify. In 10ms.
How long does it take the generate the proof?
Only takes a few minutes. Proof generation can be parallelized. The proof are noninteractive.
Single proof sent to all the readers. Can on their own prove its valid.
Breakthrough in New snark provers. Fast provers. Work so quickly. Allows for proving large statements. Proving properties of polynomials and algebra.
a16zcrypto.com/zero-knowledge-canon
Fix a computation model a finite field. 0 up to some large prime.
Arithmetic circuits, structured and unstructured circuits.
Takes public statement x
Take a secret witness w
Prover and Verifier
Triple (S, P, V)
S Public Parameters
P proof
V ACCEPT OR REJECT
Complete
Sound
ZK reveal nothing new about w
Succint (must be sub linear, strongly succintft)
Short
Fast to Verify
ZKGPT Summary:
Lecture 2:
1. Scalability through Outsourcing Computation: L1 blockchains can be viewed as slow and expensive computers, and ZKPs enable these networks to verify the results of more powerful computing devices like GPUs.
2. Proof-Based Blockchain Rollups (zkRollups): L1 chains can utilize succinct proofs to verify that transactions were processed correctly in rollup solutions, improving scalability.
3. Bridging Blockchains: Proofs of consensus allow cross-chain interaction by obtaining agreement on the state of locked or transferred assets by providing a proof of the valid state of the source chain.
4. ZkSNARK Private Transactions: These secure transactions on public blockchains keep data private and inaccessible to others.
5. Compliance, Solvency, and Disinformation: ZKPs can be utilized to ensure compliance with banking laws, prove an exchange's solvency in zero-knowledge, or fight disinformation by using content provenance and certified signing keys.
6. Image Metadata Verification with ZKPs: Provac makes use of zkSNARKs to generate a proof that verifies the original image and the associated metadata had a valid signature. This proof is succinct, fast to verify, and non-interactive, allowing single proofs to be sent to multiple readers for independent verification.
Lecture 3 ZK Programming Languages
ZKSNARK usually requires implementing a program in arithmetic circuits or circuit-friendly languages.
Libraries and Compilers to build ZKP:
HDL - Circom
Libary - Arkworks.rs Rust
Language - Zokrates
ZKPs a way to convince a verifier that something is true
private input x, w, public w verifier knows phi, x
proof shows that phi, (x, w) holds 1
in a way that completely hides input w
Key Question: what can phi actually express
phi can be any statement
w is a factorization of integer x
w is the secret key for public key x
w is the credential for account x
w is a valid transaction
1. Circom HDL: A hardware description language specifically designed for creating arithmetic circuits to be used in ZKP systems.
2. Arkworks.rs: A Rust library containing a collection of tools for constructing zkSNARKs and other zero-knowledge proving systems.
3. ZoKrates: A domain-specific language and toolbox for zkSNARKs on Ethereum that allows developers to create and verify proofs in a secure and efficient manner.
In essence, ZKPs allow a prover to convince a verifier of the truth of a statement without revealing any confidential information about the inputs. Some possibilities of what these statements might express:
1. w is a factorization of integer x
2. w is the secret key for public key x
3. w is the credential for account x
4. w is a valid transaction
With zkSNARKs typically requiring implementations using arithmetic circuits or circuit-friendly languages, the libraries and compilers mentioned above can help developers and researchers build and implement practical ZKP systems across various domains.
phi in practice
phi is an
Arithmetic Circuit, Part 1
Domain: "prime field"
p: a large (~255 bit) prime Zp: the integers, mod p operations: +,
x = (mod p)
Example in Z 5 like a boolean circuit.
Multiplication, Addition Mod P
4 + 5 = 9 = 44 X 4 = 16 = 1
How do we express
ACs as systems of field equations
w0xw0xw0 = xw1xw1xw1 = x
express any polynomial over the field
Addition is also OK
Arithmetic Circuits (ACs), Part II
ACs as circuits
Directed Acyclic graph
Nodes: inputs, gates, constants
Edges: wires/connections
w0xw0xw0 = xw1xw1xw1 = x
1. Prime Field Domain: "Prime field" refers to the domain in which arithmetic circuits operate. In this context, p denotes a large prime number (about 255 bits), and Zp represents a set of integers modulo p, with operations including addition and multiplication (mod p).
2. Modulo Arithmetic Examples: In Z5, which is similar to a Boolean circuit, - Addition, Mod P: 4 + 5 = 9 ≡ 4 (mod 5) - Multiplication, Mod P: 4 × 4 = 16 ≡ 1 (mod 5)
3. Expressing Arithmetic Circuits as Systems of Field Equations: Arithmetic circuits (ACs) can be expressed as systems of field equations with variables like w0 and w1, e.g., - w0 × w0 × w0 = x - w1 × w1 × w1 = x These equations can represent any polynomial over the field. Addition and multiplication operations are valid in this representation.
4. Arithmetic Circuits as Directed Acyclic Graphs (DAGs): ACs can be represented as circuits in the form of DAGs, where nodes correspond to inputs, gates, and constants, and edges represent connections between these nodes. For example, the equation w0 × w0 × w0 = x could be represented as a DAG, with w0 cubed equal to the public input x.
Represent as a DAG:
As a circuit:
w,x =
w0 cubed is equal to the public
R1CSs
Rank 1 Constraint Systems (R1CSs)
format for ZKP ACs
Definition:
x: vector of l field elements
w: vector of m - l - 1 field elements
linear combination of variables matrices
Programming in high-level language
Libraries
Compilers
Progamming Langs.
Domain Specific Langs.
High Level Code
Compiler / Library / R1CS / ZK Proof System
Zcash Circuit
Merkle Tree
Pedersen Hash
Signatures
Spend Logic
Bellman Library
R1CS
Groth16
Programming Languages (PLs) vs. Hardware Description Languages (HDLs)
Variables
Operations
Program / Functions
PL Actions
Mutate Variables
Call functions
HDL objects
Wires
Gates
Circuit/Sub-circuits
HDL actions
Connect wires
Create sub-circuits
HDLs for Digital Circuits
Verilog
SystemVerilog
VHDL
Chisel
An HDL for R1CS circom wires: R1CS variables gates: R1CS constraints
a circom circuit does 2 things:
sets variable values
creates R1CS constraints
Circom: Base Language
Circom to create Custom Gates
A template is a (sub)circuit
a signal is a wire input or output
<-- sets signal values
=== creates constraints
<== does both
template Multiply() { signal input x; signal input y; signal output z;
z <-- x * y; z === x * y;
// ERROR: z === x * x * y // OR : z <== x * y; }
component main { public [x]} = Multiply();
Circom: Metaprogamming Language
Template arguments
Signal arrays
Variables
Mutable
Not signals
Evaluated at compile-time
Loops
template RepeatedSquaring(n) { signal input x; signal output y;
signal xs[n+1]; xs[0] <== x; for (var i = 0; i < n; i++) { xs[i+1] <== xs[i] * xs[i]; } y <== xs[n];}
Circom: witness computation & sub-circuits
Witness computation:more general than R1CS
<-- is more general than "==="
"components" hold sub-circuits
Access inputs/outputs with dot-notation
template NonZero() { signal input in; signal inverse; inverse <-- 1 / in; 1 === in * signal}
template Main() { signal input a; signal input b; component nz = NonZero(); nz.in <== a; 0 === a * b;}
Constraint Systems
A library in a host system
Key type: constraint system
Maintains state about R1CS constraints and variables
The puzzle example using Circom:
pragma circom 2.0.0;
template NonEqual(){
signal input in0;
signal input in1;
signal inv;
inv <-- 1/ (in0 - in1);
inv*(in0 - in1) === 1;
}
template Distinct(n) {
signal input in[n];
component nonEqual[n][n];
for(var i = 0; i < n; i++){
for(var j = 0; j < i; j++){
nonEqual[i][j] = NonEqual();
nonEqual[i][j].in0 <== in[i];
nonEqual[i][j].in1 <== in[j];
}
}
}
// Enforce that 0 <= in < 16
template Bits4(){
signal input in;
signal bits[4];
var bitsum = 0;
for (var i = 0; i < 4; i++) {
bits[i] <-- (in >> i) & 1;
bits[i] * (bits[i] - 1) === 0;
bitsum = bitsum + 2 ** i * bits[i];
}
bitsum === in;
}
// Enforce that 1 <= in <= 9
template OneToNine() {
signal input in;
component lowerBound = Bits4();
component upperBound = Bits4();
lowerBound.in <== in - 1;
upperBound.in <== in + 6;
}
template Sudoku(n) {
// solution is a 2D array: indices are (row_i, col_i)
signal input solution[n][n];
// puzzle is the same, but a zero indicates a blank
signal input puzzle[n][n];
component distinct[n];
component inRange[n][n];
for (var row_i = 0; row_i < n; row_i++) {
for (var col_i = 0; col_i < n; col_i++) {
// we could make this a component
puzzle[row_i][col_i] * (puzzle[row_i][col_i] - solution[row_i][col_i]) === 0;
}
}
for (var row_i = 0; row_i < n; row_i++) {
for (var col_i = 0; col_i < n; col_i++) {
if (row_i == 0) {
distinct[col_i] = Distinct(n);
}
inRange[row_i][col_i] = OneToNine();
inRange[row_i][col_i].in <== solution[row_i][col_i];
distinct[col_i].in[row_i] <== solution[row_i][col_i];
}
}
}
component main {public[puzzle]} = Sudoku(9);
Key operators:
create variable
create linear combinations of variables
add constraint
Variable creation
cs. add_var (p, v) -> id
cs: constraint system
p: visbility of variable
v: assigned value
id: variable handle
Linear combination creation:
cs.zero(): returns the empty LCl
c.add(c, id) -> l
c'id: variable
c: coefficientlc : = lc + c * id
Adding constraints
cs.constrain (lcA, lcB, LcC)
Adds a constraint lcA, lcB, = lcC
We can use language abstrations like structs, operator overloading, methods, etc. to allow better developer UX:
Can use abstractions like normal code:let a = Boolean::new_witness(|| true);
let b = Boolean::new_witness(|| false);
(a & b).enforce_equal(Boolean::false);
Many different gadget libraries: -
libsnark: gadgerlib (C++) -
arkworks: r1cs-std + crypto-primitives (Rust)
- Snarky (Ocaml)
- Gnark (Go)
What about Witness Computation?
Can perform arbitrary computations to generate witnesses
let a = Boolean::new_witness(|| (4 == 5) & (x < y));
let b = Boolean::new_witness(|| false);
(a & b).enforce_equal(Boolean::false);
Arkworks.Rs: Constraint Programming Language
Arkworks
r1cs-std
integers
booleans,
equality,
comparison
Use Rust's type system
Check Rows
Check Puzzle
The puzzle example using Arkworks:
use ark_ff::PrimeField;
use ark_r1cs_std::{
prelude::{Boolean, EqGadget, AllocVar},
uint8::UInt8
};
use ark_relations::r1cs::{SynthesisError, ConstraintSystem};
use cmp::CmpGadget;
mod cmp;
mod alloc;
pub struct Puzzle<const N: usize, ConstraintF: PrimeField>([[UInt8<ConstraintF>; N]; N]);
pub struct Solution<const N: usize, ConstraintF: PrimeField>([[UInt8<ConstraintF>; N]; N]);
fn check_rows<const N: usize, ConstraintF: PrimeField>(
solution: &Solution<N, ConstraintF>,
) -> Result<(), SynthesisError> {
for row in &solution.0 {
for (j, cell) in row.iter().enumerate() {
for prior_cell in &row[0..j] {
cell.is_neq(&prior_cell)?
.enforce_equal(&Boolean::TRUE)?;
}
}
}
Ok(())
}
fn check_puzzle_matches_solution<const N: usize, ConstraintF: PrimeField>(
puzzle: &Puzzle<N, ConstraintF>,
solution: &Solution<N, ConstraintF>,
) -> Result<(), SynthesisError> {
for (p_row, s_row) in puzzle.0.iter().zip(&solution.0) {
for (p, s) in p_row.iter().zip(s_row) {
// Ensure that the solution `s` is in the range [1, N]
s.is_leq(&UInt8::constant(N as u8))?
.and(&s.is_geq(&UInt8::constant(1))?)?
.enforce_equal(&Boolean::TRUE)?;
// Ensure that either the puzzle slot is 0, or that
// the slot matches equivalent slot in the solution
(p.is_eq(s)?.or(&p.is_eq(&UInt8::constant(0))?)?)
.enforce_equal(&Boolean::TRUE)?;
}
}
Ok(())
}
fn check_helper<const N: usize, ConstraintF: PrimeField>(
puzzle: &[[u8; N]; N],
solution: &[[u8; N]; N],
) {
let cs = ConstraintSystem::<ConstraintF>::new_ref();
let puzzle_var = Puzzle::new_input(cs.clone(), || Ok(puzzle)).unwrap();
let solution_var = Solution::new_witness(cs.clone(), || Ok(solution)).unwrap();
check_puzzle_matches_solution(&puzzle_var, &solution_var).unwrap();
check_rows(&solution_var).unwrap();
assert!(cs.is_satisfied().unwrap());
}
fn main() {
use ark_bls12_381::Fq as F;
// Check that it accepts a valid solution.
let puzzle = [
[1, 0],
[0, 2],
];
let solution = [
[1, 2],
[1, 2],
];
check_helper::<2, F>(&puzzle, &solution);
// Check that it rejects a solution with a repeated number in a row.
let puzzle = [
[1, 0],
[0, 2],
];
let solution = [
[1, 0],
[1, 2],
];
check_helper::<2, F>(&puzzle, &solution);
}
HDLs & Circuit Libaries
explicit wire creation (explicitly wire values)
explicit constraint creation
Do we need to explicity build a circuit? No
Compiling PLs to Circuits (Idea)
Program
Variables
Mutation
Functions
Arrays
--> Compiler to R1Cs Wires, Constraints etc.
ZoKrates
Struct syntax for custom types
Variables contain values during execution / proving
Can annotate privacy "assert" creates constraints
type F = field
def main (public F x, private F[2] ys) { field y0 = y[0]; field y1 = y[1]; assert(x = y0 * y1); }
ZoKrates language features:
Integer
generics
Arrays
Variables
Mutable
Fixed-length loops
If expressions
Array accesses
The puzzle example using ZoKrates:
struct Puzzle<N> {
u8[N][N] elems;
}
struct Solution<N> {
u8[N][N] elems;
}
def check_rows<N>(Solution<N> sol) -> bool {
// for each row
for u32 i in 0..N {
// for each column
for u32 j in 0..N {
// Check that the (i, j)-th element is not equal to any of the
// the elements preceding it in the same row.
for u32 k in 0..j {
assert(sol.elems[i][j] != sol.elems[i][k]);
}
}
}
return true;
}
def check_puzzle_matches_solution<N>(Solution<N> sol, Puzzle<N> puzzle) -> bool {
for u32 i in 0..N {
for u32 j in 0..N {
assert((sol.elems[i][j] > 0) && (sol.elems[i][j] < 10));
assert(\
(puzzle.elems[i][j] == 0) ||\
(puzzle.elems[i][j] == sol.elems[i][j])\
);
}
}
return true;
}
def main(public Puzzle<2> puzzle, private Solution<2> sol) {
assert(check_puzzle_matches_solution(sol, puzzle));
assert(check_rows(sol));
}
What about Witness Computation?
No way to compute witnesses
All witnesses must be provided as input
def main(private field a, public field b) { assert (a * b == 1)}
ZKP ToolsChains
HDL - a language for decribing circuit synthesis
Library - a language for describing circuit synthesis
PL + Compiler - a language, compiled to a circuit
Language Type Circuit (Library (arkworks)
HDL (circom))
circom, arkworks, ZoKrates
circom - clear constraints, elegant syntax, limited abstration
arkworks - clear constraints, expressive as rust, manual opts
ZoKrates - easiest to learn, elegant syntax, limited witness computation
Arkworks (Rust)
Gadgetlub (C++)
Bellman (Rust)
Snarky (OCaml)
PLONKish (Rust)
PL + Compiler
ZoKrates
Noir
Leo
Cairo
Targets
R1CS
Plonk
AIR
Lecture 4
Achieving Linear Prover Time
Protocol with Random Challenges
Performance of GKR based Schemes
Fast Prover Time
Fast Verifier Time
No Trusted Setup
Large proof Size
Hyrax, zkVSQL, libra, Virgo, Spectra
Lecture 5
A polynomial commitment scheme + A polynomial interactive oracle proof = SNARK for general circuits
Eval proof size and verifier time need to be at least linear. Very short. Very fast to verify.
KZG poly-commit scheme
Coefficient representation
Point-value representation: a better way to compute com f
We can look at the Lagrange interpolation
Idea: transform gp into Lagrange from (a linear map)
KZG fast multi-point proof generation
generate all proofs in time 0 (d log d)
Vector commitment (a drop-in replacement for Merkle trees)
Verkle Trees. using Polynomial Comittments.
Comit to vectors in a way that is better.
Proving properties of committed polynomials
Prover P(f,g) Verifier V(f,g)
accept or reject
V sends x to P who responds with f(x) and eval proof
Polynomial equality testing
The proof system as an IOP (interactive oracle proof)
Prover → Verifier
f, g
test all 4 points (all four poly) and tests equality
Complete and sound protocol
Proof Gadgets (Prover convince the Verifier of)
ZeroTest
SumCheck → Sum is equal to 0
ProdCheck → Product evals to 1
The vanishing polynomial
Prover P(f) VerifierV(f)
Product Check
Sumamary:
1. Efficient SNARKs for General Circuits: Polynomial commitment schemes combined with polynomial interactive oracle proofs (IOPs) create SNARKs for general circuits. These SNARKs have small proof sizes and fast verifier times, making them short and quick to verify.
2. The KZG poly-commit scheme uses coefficient representation and point-value representation as more efficient ways to compute committed polynomials.
3. Lagrange Interpolation: Lagrange interpolation plays a critical role in transforming group elements (G and H) into their respective Lagrange forms using a linear map.
4. Fast Multi-Point Proof Generation: KZG allows generating all proofs in time proportional to d*log(d), speeding up the process.
5. Vector Commitments and Verkle Trees: Vector commitment schemes, such as Verkle trees utilizing polynomial commitments, serve as drop-in replacements for Merkle trees, providing a more efficient way to commit to vectors.
6. Proving Properties in Committed Polynomials: Both a prover (P) and a verifier (V) play roles in establishing and verifying properties of committed polynomials (f and g).
7. Polynomial Equality Testing: With IOPs, provers and verifiers interact to test points across all polynomials, checking for equality.
8. Proof Gadgets: Proof gadgets are efficient tools for provers and verifiers that check specific properties: - ZeroTest: Tests if a value is zero. - SumCheck: Ensures that the sum is equal to zero. - ProdCheck: Verifies that the product evaluates to one.
9. The Vanishing Polynomial: The vanishing polynomial plays a vital role in proving the commitment properties.
10. Product Check Protocol: In this protocol, the Prover P(f) and Verifier V(f) collaborate to verify the committed polynomial's product.
If we remember the axis are:
Prover time
Proof size
Verifier time | yes or no
Trusted Setup preprocessor
Lecture 6
Polynomial Commitments based on Pairing and Discrete Logarithm
▪ keygen(𝜆, 𝓕) ⇾ gp
▪ commit(gp,𝑓) ⇾ comf
▪ eval(gp,𝑓,u) ⇾ v, 𝜋
▪ verify(gp, comf ,u,v, 𝜋) ⇾ accept or reject
KZG
▪ Keygen: trusted setup!
▪ Commit: O(d) group exponentiations, O(1) commitment size
▪ Eval: O(d) group exponentiations q(x) can be computed efficiently in linear time!
▪ Proof size: O(1), 1 group element
▪ Verifier time: O(1), 1 pairing
Plonk
Bulletproofs
Keygen: O(d), transparent setup!
▪ Commit: O(d) group exponentiations, O(1) commitment size
▪ Eval: O(d) group exponentiations (non-interactive via Fiat Shamir)
▪ Proof size: O(log d)
▪ Verifier time: O(d)
Lecture 7
Polynomial Commitments based on Error-correcting code
Motivations: ✓Plausibly post-quantum secure ✓No group exponentiations (prover only uses hashes, additions and multiplications) ✓Small global parameters Drawbacks: Large proof size Not homomorphic and hard to aggregate
▪ Keygen: sample a hash function
▪ Commit: encode the coefficient matrix of 𝑓 row-wise with a linear code, compute the Merkle tree commitment
▪ Eval and Verify:
▪ Proximity test: random linear combination of all rows, check its consistency with 𝑡 random columns
▪ Consistency test: 𝑢 × 𝐹 = 𝑚, encode 𝑚 and check its consistency with 𝑡 random columns ▪ 𝑓 𝑢 = 𝑚, 𝑢′
Keygen: O(1), transparent setup!
▪ Commit:
▪ Encoding: O(d logd) field multiplications using RS code, O(d) using linear-time encodable code
▪ Merkle tree: O(d) hashes, O(1) commitment size
▪ Eval: O(d) field multiplications (non-interactive via Fiat Shamir)
▪ Proof size: O( 𝑑)
▪ Verifier time: O( 𝑑)
Polynomial commitment (and SNARK) based on linear code ✓Transparent setup: 𝑂(1) ✓Commit and Prover time: 𝑂(𝑑) field additions and multiplications ✓Plausibly post-quantum secure ✓Field agnostic
Linear time encodable error correcting code
Breakdown, Orion
Fast prover time
Fast verifier time
No Trusted Setup
Trade offs between proof size and efficiencies.
This technique allows a prover to commit to a polynomial without the need for expensive group exponentiations, using only hash functions, additions, and multiplications. The commitment is made by encoding the coefficient matrix of the polynomial with a linear code and then computing a Merkle tree commitment. The commitment can be verified by performing a proximity test and a consistency test. The scheme has some drawbacks, including a large proof size and difficulty in homomorphic aggregation.
Lecture 8
FRI
▪A polynomial commitment scheme such as FRI, when run interactively at “𝜆 bits of security”, has the following security guarantee ▪ Assuming P cannot find a collision in the hash function used to build Merkle trees, a lying P cannot pass the verifier’s checks with probability better than 2 −𝜆 . ▪ A lying P must actually interact with V to learn V’s challenges, in order to find out if it receives a “lucky” challenge!
▪ Suppose Fiat-Shamir is applied to an interactive protocol such as FRI that was run at 𝜆 bits of interactive security.
▪ The resulting non-interactive protocol has the following much weaker guarantee:
▪ A lying P willing to perform 2 𝑘 hash evaluations can successfully attack the protocol with probability 2 𝑘−𝜆 .
▪ A lying P can attempt the attack “silently”.
▪ Unlike in the interactive case, P can perform a ”grinding attack” without interacting with V until P receives a lucky challenge.
Applying Fiat-Shamir to a many-round interactive protocol can lead to a huge loss in security, whereby the resulting non-interactive protocol is totally insecure.
SNARK designers applying Fiat-Shamir to interactive protocols with more than 3 messages should show that the protocol is round-by-round sound if they want to rule out a major security loss.
SNARKs learned so far, a summary by ChatGPT:
In Lecture 6, three types of polynomial commitments were compared: polynomial commitments based on pairing and discrete logarithm, KZG, and Bulletproofs. Polynomial commitments based on pairing and discrete logarithm have a trusted setup, and their proof size and verifier time are both O(1). KZG has a transparent setup, and its proof size is O(1) while its verifier time is O(1) as well. Bulletproofs also have a transparent setup, and their proof size is O(log d) while their verifier time is O(d).
Trusted Setup
Pairing
Plonk
Interactive Proofs
In Lecture 7, polynomial commitments based on error-correcting code were discussed. This technique allows a prover to commit to a polynomial without the need for expensive group exponentiations, using only hash functions, additions, and multiplications. The commitment can be verified by performing a proximity test and a consistency test. This technique has a transparent setup, and its proof size and verifier time are both O(d).
No Trusted Setup
Discrete Log
Bulletproofs, Dory, Dark, Hyrax, Halo2
In Lecture 8, FRI was discussed as a polynomial commitment scheme. When run interactively at "𝜆 bits of security," it has a strong security guarantee. However, when Fiat-Shamir is applied to the interactive protocol, the resulting non-interactive protocol can be totally insecure if the protocol has more than three messages. SNARK designers applying Fiat-Shamir to interactive protocols with more than three messages should show that the protocol is round-by-round sound if they want to rule out a major security loss.
No Trusted Setup
Hashing
Breakdown, Orion (linear-time encodable code)
Stark, Aurora, Fractal, Virgo (RS code and FRI)
Today there is a Snarkyjs zoom meeting. Ahead of the meeting I wanted to test out a few examples using ChatGPT:
SnarkyJS is a JavaScript library that allows you to create and verify zk-SNARKs (zero-knowledge succinct non-interactive arguments of knowledge) proofs. To write a ZKP circuit in SnarkyJS, you will need to:
Define the input and output variables of the circuit.
Define the constraints that the input variables must satisfy.
Compile the circuit using SnarkyJS.
Generate a proving key and a verification key for the circuit.
Generate a proof using the proving key and the input variables.
Verify the proof using the verification key and the output variables.
Examples
Here's an example of how to write a simple ZKP circuit in SnarkyJS:
const snarky = require('snarkyjs');
const circuit = async (inputs) => {
const [a, b, c] = inputs;
// Define the constraints of the circuit
return {
constraints: [
{
// Enforce that a + b = c
a: [1],
b: [1],
c: [1, -1, 0],
},
{
// Enforce that a and b are less than 10
a: [10],
b: [10],
},
],
// Return the output variable
output: c,
};
};
(async () => {
// Compile the circuit
const compiledCircuit = await snarky.compile(circuit);
// Generate the proving and verification keys
const provingKey = await snarky.generateProofKey(compiledCircuit);
const verificationKey = await snarky.generateVerificationKey(compiledCircuit);
// Generate a proof
const inputs = [5, 3, 8]; // a = 5, b = 3, c = 8
const proof = await snarky.generateProof(compiledCircuit, provingKey, inputs);
// Verify the proof
const verified = await snarky.verifyProof(compiledCircuit, verificationKey, proof, inputs);
console.log(verified); // true
})();
This example defines a circuit that takes three input variables a
, b
, and c
, and enforces two constraints: a + b = c
and a < 10
and b < 10
. The output variable of the circuit is c
. The code then compiles the circuit, generates the proving and verification keys, generates a proof using the input variables, and verifies the proof using the verification key and the output variable.
This is just a simple example, but you can use SnarkyJS to define more complex circuits with more input and output variables, and more complex constraints.
Here's a more advanced example of a ZKP circuit in SnarkyJS. This example implements a ZKP for a private set intersection protocol, which allows two parties to determine if they have any common elements in their sets without revealing the contents of their sets to each other.
const snarky = require('snarkyjs');
const circuit = async (inputs) => {
const [x, y, witness] = inputs;
const hashX = await snarky.sha256(x);
const hashY = await snarky.sha256(y);
const n = x.length;
const hX = await snarky.hugeInt(await snarky.hexToInt(hashX));
const hY = await snarky.hugeInt(await snarky.hexToInt(hashY));
const g1 = await snarky.g1();
const [a, b] = await Promise.all([
snarky.hugeInt(witness.slice(0, n)),
snarky.hugeInt(witness.slice(n)),
]);
const hXa = await snarky.g1mul(hX, a);
const hYb = await snarky.g1mul(hY, b);
const g1add = await snarky.g1add(hXa, hYb);
const pairingCheck = await snarky.pairingCheck(
g1add,
g1,
await snarky.g2(),
await snarky.pairing(),
);
return {
constraints: [
{
// Enforce that the witness satisfies the pairing check
g1add: [pairingCheck],
},
],
output: null,
};
};
(async () => {
// Define the two sets
const x = [1, 2, 3, 4];
const y = [2, 4, 6, 8];
// Compute the witness
const witness = new Array(x.length + y.length)
.fill(0)
.map(() => Math.floor(Math.random() * 100));
// Compute the input to the circuit
const inputs = [x, y, witness];
// Compile the circuit
const compiledCircuit = await snarky.compile(circuit);
// Generate the proving and verification keys
const provingKey = await snarky.generateProofKey(compiledCircuit);
const verificationKey = await snarky.generateVerificationKey(compiledCircuit);
// Generate a proof
const proof = await snarky.generateProof(compiledCircuit, provingKey, inputs);
// Verify the proof
const verified = await snarky.verifyProof(compiledCircuit, verificationKey, proof, inputs);
console.log(verified); // true
})();
In this example, the ZKP circuit takes three input variables: x
, y
, and a witness
. The x
and y
variables are the two sets that are being compared, and the witness
variable is a random string that is used to generate a proof. The circuit computes the SHA-256 hashes of x
and y
, converts them to elliptic curve points using the G1 hash-to-curve function, and multiplies them by random numbers a
and b
to generate two new points in G1. The circuit then adds these points and checks if the result satisfies a bilinear pairing equation. The output variable of the circuit is null
.
The code then compiles the circuit, generates the proving and verification keys, generates a proof using the input variables, and verifies the proof using the
Here's an even more advanced example of a ZKP circuit in SnarkyJS. This example implements a ZKP for a simple voting system, where a voter can submit a vote and prove that they voted for a particular candidate without revealing their identity or the candidate they voted for.
const snarky = require('snarkyjs');
const circuit = async (inputs) => {
const [voter, candidate, salt, signature, publicKey] = inputs;
const g1 = await snarky.g1();
const g2 = await snarky.g2();
const h = await snarky.g1mul(g1, await snarky.sha256(candidate));
const hToPoint = await snarky.g1mul(h, await snarky.hexToInt(salt));
const rToPoint = await snarky.g2mul(g2, await snarky.hexToInt(signature));
const p = await snarky.g1add(hToPoint, await snarky.g1mul(voter, g1));
const q = await snarky.g2add(rToPoint, await snarky.g2mul(publicKey, g2));
const pairingCheck = await snarky.pairingCheck(p, g2, q, g1);
return {
constraints: [
{
// Enforce that the pairing check is true
p: [pairingCheck],
},
],
output: null,
};
};
(async () => {
// Define the voter's private information
const voter = await snarky.g1();
const salt = 'abc123';
const signature = 'def456';
// Define the candidate and public key
const candidate = 'Alice';
const publicKey = await snarky.g2mul(await snarky.g2(), 12345);
// Compute the input to the circuit
const inputs = [voter, candidate, salt, signature, publicKey];
// Compile the circuit
const compiledCircuit = await snarky.compile(circuit);
// Generate the proving and verification keys
const provingKey = await snarky.generateProofKey(compiledCircuit);
const verificationKey = await snarky.generateVerificationKey(compiledCircuit);
// Generate a proof
const proof = await snarky.generateProof(compiledCircuit, provingKey, inputs);
// Verify the proof
const verified = await snarky.verifyProof(compiledCircuit, verificationKey, proof, inputs);
console.log(verified); // true
})();
const snarky = require('snarkyjs');
const circuit = async (inputs) => {
const [userAddress, userID, userEmail, orgAddress, orgID, orgEmail, proof] = inputs;
const g1 = await snarky.g1();
const g2 = await snarky.g2();
const userPublicKey = await snarky.g1add(await snarky.g1mul(await snarky.sha256(userID), g1), userAddress);
const orgPublicKey = await snarky.g2add(await snarky.g2mul(await snarky.sha256(orgID), g2), orgAddress);
const pairingCheck = await snarky.pairingCheck(userPublicKey, g2, proof, orgPublicKey);
return {
constraints: [
{
// Enforce that the pairing check is true
p: [pairingCheck],
},
],
output: null,
};
};
(async () => {
// Define the user and organization information
const userAddress = await snarky.g1();
const userID = 'user123';
const userEmail = 'user@example.com';
const orgAddress = await snarky.g2();
const orgID = 'org123';
const orgEmail = 'org@example.com';
// Compute the input to the circuit
const inputs = [userAddress, userID, userEmail, orgAddress, orgID, orgEmail];
// Generate the user and organization public keys
const compiledCircuit = await snarky.compile(circuit);
const userPublicKey = await snarky.g1add(await snarky.g1mul(await snarky.sha256(userID), await snarky.g1()), userAddress);
const orgPublicKey = await snarky.g2add(await snarky.g2mul(await snarky.sha256(orgID), await snarky.g2()), orgAddress);
// Generate the proof
const proof = await snarky.generateProof(compiledCircuit, [userPublicKey, userID, userEmail, orgPublicKey, orgID, orgEmail]);
// Verify the proof
const verificationKey = await snarky.generateVerificationKey(compiledCircuit);
const verified = await snarky.verifyProof(compiledCircuit, verificationKey, proof, [userPublicKey, userID, userEmail, orgPublicKey, orgID, orgEmail, proof]);
console.log(verified); // true
})();
const snarky = require('snarkyjs');
const circuit = async (inputs) => {
const [buyerAddress, sellerAddress, contractID, contractAmount, buyerSignature, proof] = inputs;
const g1 = await snarky.g1();
const buyerPublicKey = await snarky.g1add(await snarky.sha256(buyerSignature), buyerAddress);
const sellerPublicKey = sellerAddress;
const contractHash = await snarky.sha256(contractID, contractAmount);
const contractPublicKey = await snarky.g1add(contractHash, buyerPublicKey);
const pairingCheck1 = await snarky.pairingCheck(contractPublicKey, g1, proof[0], sellerPublicKey);
const pairingCheck2 = await snarky.pairingCheck(buyerPublicKey, g1, proof[1], sellerPublicKey);
return {
constraints: [
{
// Enforce that both pairing checks are true
p: [pairingCheck1, pairingCheck2],
},
],
output: null,
};
};
(async () => {
// Define the buyer and seller information
const buyerAddress = await snarky.g1();
const sellerAddress = await snarky.g2();
const contractID = 'contract123';
const contractAmount = 100;
const buyerSignature = 'buyerSignature123';
// Compute the input to the circuit
const inputs = [buyerAddress, sellerAddress, contractID, contractAmount, buyerSignature];
// Generate the buyer, seller, and contract public keys
const compiledCircuit = await snarky.compile(circuit);
const buyerPublicKey = await snarky.g1add(await snarky.sha256(buyerSignature), buyerAddress);
const sellerPublicKey = sellerAddress;
const contractHash = await snarky.sha256(contractID, contractAmount);
const contractPublicKey = await snarky.g1add(contractHash, buyerPublicKey);
// Generate the proof
const proof = await snarky.generateProof(compiledCircuit, [buyerAddress, sellerAddress, contractID, contractAmount, buyerSignature, [contractPublicKey, buyerPublicKey]]);
// Verify the proof
const verificationKey = await snarky.generateVerificationKey(compiledCircuit);
const verified = await snarky.verifyProof(compiledCircuit, verificationKey, proof, [buyerAddress, sellerAddress, contractID, contractAmount, buyerSignature, proof]);
console.log(verified); // true
})();
const snarky = require('snarkyjs');
const circuit = async (inputs) => {
const [purchaseOrderID, invoiceID, invoiceAmount, invoiceDate, buyerAddress, sellerAddress, proof] = inputs;
const g1 = await snarky.g1();
const purchaseOrderHash = await snarky.sha256(purchaseOrderID);
const purchaseOrderPublicKey = await snarky.g1add(purchaseOrderHash, buyerAddress);
const invoiceHash = await snarky.sha256(invoiceID, invoiceAmount, invoiceDate);
const invoicePublicKey = await snarky.g1add(invoiceHash, sellerAddress);
const pairingCheck1 = await snarky.pairingCheck(purchaseOrderPublicKey, g1, proof[0], sellerAddress);
const pairingCheck2 = await snarky.pairingCheck(invoicePublicKey, g1, proof[1], buyerAddress);
return {
constraints: [
{
// Enforce that both pairing checks are true
p: [pairingCheck1, pairingCheck2],
},
],
output: null,
};
};
(async () => {
// Define the purchase order and invoice information
const purchaseOrderID = 'PO123';
const invoiceID = 'INV456';
const invoiceAmount = 100;
const invoiceDate = '2022-03-14';
const buyerAddress = await snarky.g1();
const sellerAddress = await snarky.g2();
// Compute the input to the circuit
const inputs = [purchaseOrderID, invoiceID, invoiceAmount, invoiceDate, buyerAddress, sellerAddress];
// Generate the purchase order and invoice public keys
const compiledCircuit = await snarky.compile(circuit);
const purchaseOrderHash = await snarky.sha256(purchaseOrderID);
const purchaseOrderPublicKey = await snarky.g1add(purchaseOrderHash, buyerAddress);
const invoiceHash = await snarky.sha256(invoiceID, invoiceAmount, invoiceDate);
const invoicePublicKey = await snarky.g1add(invoiceHash, sellerAddress);
// Generate the proof
const proof = await snarky.generateProof(compiledCircuit, [purchaseOrderID, invoiceID, invoiceAmount, invoiceDate, buyerAddress, sellerAddress, [purchaseOrderPublicKey, invoicePublicKey]]);
// Verify the proof
const verificationKey = await snarky.generateVerificationKey(compiledCircuit);
const verified = await snarky.verifyProof(compiledCircuit, verificationKey, proof, [purchaseOrderID, invoiceID, invoiceAmount, invoiceDate, buyerAddress, sellerAddress, proof]);
console.log(verified); // true
})();
KZG Verifier between SFDC and SAP:
const { KZG } = require("snarkjs");
// Define the circuit inputs, public inputs, and outputs
const input = {
crmData: [["field1", ""], ["field2", ""], ["field3", 0]],
sapData: [["field1", ""], ["field2", ""], ["field3", 0]],
crmPublicKey: "",
sapPublicKey: "",
};
const publicInput = [];
const output = [];
// Define the circuit constraints
const constraints = [
{
inputs: ["crmData[0]", "sapData[0]"],
evaluator: "equal(string, string)",
output: "field1Equal",
},
{
inputs: ["crmData[1]", "sapData[1]"],
evaluator: "equal(string, string)",
output: "field2Equal",
},
{
inputs: ["crmData[2]", "sapData[2]"],
evaluator: "equal(float, float)",
output: "field3Equal",
},
];
// Compile the circuit
const compiledCircuit = await snarky.compile(constraints, input, publicInput, output);
// Define the verifyCrmSapDataMatch function
const verifyCrmSapDataMatch = await KZG.generateVerifier(compiledCircuit);
// Define the hashDataFields function
const hashDataFields = async (dataFields, publicKey) => {
const domain = "crm-sap-data-match";
const pointCount = 3;
const crmDataFields = dataFields.map((field) => {
const fieldName = field[0];
const fieldValue = field[1];
if (fieldName === "field1") {
return KZG.Field.ofString(fieldValue);
} else if (fieldName === "field2") {
return KZG.Field.ofString(fieldValue);
} else if (fieldName === "field3") {
return KZG.Field.ofFloat(fieldValue);
}
});
const crmDataCommitment = await KZG.commit(crmDataFields, domain, pointCount, publicKey);
return crmDataCommitment;
};
// Hash the CRM data fields
const crmPublicKey = KZG.hashToPoint(Buffer.from("crm-public-key", "utf-8"));
const crmDataHashed = await hashDataFields(crmData, crmPublicKey);
// Hash the SAP data fields
const sapPublicKey = KZG.hashToPoint(Buffer.from("sap-public-key", "utf-8"));
const sapDataHashed = await hashDataFields(sapData, sapPublicKey);
// Verify that the hashed data matches the expected values
const crmDataMatches = await KZG.verify(crmDataHashed, sapPublicKey, sapDataHashed);
console.log("CRM data matches SAP data:", crmDataMatches);
FRI
const { FRI } = require("snarkjs");
// Define the circuit inputs, public inputs, and outputs
const input = {
crmData: [["field1", ""], ["field2", ""], ["field3", 0]],
sapData: [["field1", ""], ["field2", ""], ["field3", 0]],
crmPublicKey: "",
sapPublicKey: "",
};
const publicInput = [];
const output = [];
// Define the circuit constraints
const constraints = [
{
inputs: ["crmData[0]", "sapData[0]"],
evaluator: "equal(string, string)",
output: "field1Equal",
},
{
inputs: ["crmData[1]", "sapData[1]"],
evaluator: "equal(string, string)",
output: "field2Equal",
},
{
inputs: ["crmData[2]", "sapData[2]"],
evaluator: "equal(float, float)",
output: "field3Equal",
},
];
// Compile the circuit
const compiledCircuit = await snarky.compile(constraints, input, publicInput, output);
// Define the verifyCrmSapDataMatch function
const verifyCrmSapDataMatch = async (crmData, sapData, crmPublicKey, sapPublicKey) => {
const domain = "crm-sap-data-match";
const pointCount = 3;
// Generate the FRI proof
const fri = await FRI.generateProof(
compiledCircuit,
[crmData, sapData],
publicInput,
output,
domain,
pointCount
);
// Verify the FRI proof
const isVerified = await FRI.verifyProof(
compiledCircuit,
[crmData, sapData],
publicInput,
output,
fri,
domain,
pointCount,
[crmPublicKey, sapPublicKey]
);
return isVerified;
};
// Hash the CRM data fields
const crmPublicKey = await snarky.hashToPoint(Buffer.from("crm-public-key", "utf-8"));
const crmDataHashed = await hashDataFields(crmData, crmPublicKey);
// Hash the SAP data fields
const sapPublicKey = await snarky.hashToPoint(Buffer.from("sap-public-key", "utf-8"));
const sapDataHashed = await hashDataFields(sapData, sapPublicKey);
// Verify that the hashed data matches the expected values using FRI
const crmDataMatches = await verifyCrmSapDataMatch(crmDataHashed, sapDataHashed, crmPublicKey, sapPublicKey);
console.log("CRM data matches SAP data:", crmDataMatches);
This implementation uses the FRI protocol to generate and verify a proof of the circuit's correctness, which can be more efficient than the pairing-based and KZG-based approaches for certain use cases. The rest of the implementation is similar to the previous examples, with the circuit constraints defined, compiled, and used to generate a proof and verify it.
SNARKs based on Linear PCP
Earlist Implemented SNARKS
Shortest proof size (3 elements [Groth16])
Fast verifier (bilinear pairing)
FF and group exponentiations on the prover
Circuit-specific trusted setup
A cryptographic tool —>
A linear PCP (QAP) —>
SNARK for general circuits
Quadratic Arithmetic Program (QAP)
From QAP to SNARK
Other variants
Probabilistic Checkable Proofs (PCP)
Prover ←PCP oracle —> Verifier
Multiple Oracles
Prover —> polynomial f -< evaluation queries f(r) Verifier
Linear PCP oracle c
Prover ←Verifier
QAP and Linear PCP
Prover ← extended witness c and coefficients of q(x) —> Verifier
Properties of SNARK
per-circuit tusted setup
prover time
proof size
verifier time
Other variants
R1CS
Groth 16 - Proof size 3 group elements, 144 bytes, 1 pairing equation for verification