ZK-1: SNARKS

@shubh_exists|Aug 20, 2025 (5m ago)50 views

This is a continuation to the last blog ZK-0

Bilinear Pairings

We work with three cyclic groups of the same prime order r:

G1=⟨g1⟩ — subgroup of points on an elliptic curve over F(p). G1 is the set of all multiples of a single point g1 (called the generator). g1 is a point lying on the elliptic curve E(Fp). g1 is chosen so that if you keep adding it to itself, you generate a large prime-order subgroup G1. It isn't something we calculate. It is hardcoded into the standard of curve we use.

G1 = {0, g1, 2g1, 3g1, ..., (r-1)g1}

G2=⟨g2⟩ — subgroup on (usually) a twist of the same curve over F(p^2). G2 should be in a finite field of F(p^2) only to prevent subgroups and make our verifications secure.
GT=⟨gT⟩ ∈ F(p^k) — a multiplicative subgroup in an extension field (degree k is the embedding degree)

A bilinear pairing is a function

e: G1 * G2 -> GT

If G1 = G2, we call it symmetric pairings and if G1 != G2, we call it asymmetric pairing.

Key properties of bilinear pairings are -

Bilinearity -

e(aP,bQ) = e(P,Q)^ab

Non-Degeneracy - e(g1, g2) != 1
Efficient computability - Easy to calculate e(P,Q)

Why is it useful? Because the verifier can calculate things like r = pq without knowing p or q. What happens in a ZK Proof is -

Prover sends:

P=[p]g1 in G1

Q=[q]g2 in G2

R=[r]g1 in G1

Verifier checks:

e(R,g2) =? e(P,Q)

Both will only be equal if r = pq.

In Ethereum, the precompiled contract (bn256Pairing) exposes a bilinear pairing. We give it multiple pair of points -

Pi ∈ G1 (on base curve Fp)
Qi ∈ G2 (on the twist over F(p^2))

// And the precompile checks

e(p1, q1) * e(p2, q2)* ................ * e(Pi, Qi) = 1

R1CS ( Rank-1 Constraint System )

R1CS is just a set of constraints of the form:

<ai,z> * <bi,z> = <ci,z>

In easy words, We break our computation into steps with at most one multiplication each.

Example -

(x ⋅ y) + (y ⋅ z) = w

Since we need only one multiplication in each equation, we will split each equation such that each row only has one multiplication.

t1 = (x * y)                ... 1
t2 = (y * z)                ... 2
w = (t1 + t2)* 1            ... 3

We use the variables in the above equations to create a variables vector ( also called witness vector ).

z = [1,x,y,z,w,t1,t2]

Index 0 is always 1 so we can encode constants in dot products. So,

By equation 1, Comparing t1 = x * y with <ai,z> * <bi,z> = <ci,z>,

a1 = [0,1,0,0,0,0,0]
b1 = [0,0,1,0,0,0,0]
c1 = [0,0,0,0,0,1,0]

By equation 2, Comparing t2 = y * z with <ai,z> * <bi,z> = <ci,z>,

a2 = [0,0,1,0,0,0,0]
b2 = [0,0,0,1,0,0,0]
c2 = [0,0,0,0,0,0,1]

By equation 3, Comparing w = (t1 + t2) * 1 with <ai,z> * <bi,z> = <ci,z>,

a3 = [0,0,0,0,0,1,1]
b3 = [1,0,0,1,0,0,0]
c3 = [0,0,0,0,1,0,0]

Join these to get the final R1CS matrices -

A = [[0,1,0,0,0,0,0], [0,0,1,0,0,0,0], [0,0,0,0,0,1,1]]
B = [[0,0,1,0,0,0,0], [0,0,0,1,0,0,0], [1,0,0,1,0,0,0]]
C = [[0,0,0,0,0,1,0], [0,0,0,0,0,0,1], [0,0,0,0,1,0,0]]

z = 2x^2 + y

Equations will be -

t = x * x                 .... 1
z = (2t + y) * 1          .... 2

Witness Vector - [1,x,y,z,t]

By equation 1, Comparing t1 = x * x with <ai,z> * <bi,z> = <ci,z>,

a1 = [0,1,0,0,0]
b1 = [0,1,0,0,0]
c1 = [0,0,0,0,1]

By equation 2, Comparing z = (2t + y) * 1 with <ai,z> * <bi,z> = <ci,z>,

a2 = [0,0,1,0,2]
b2 = [1,0,0,0,0]
c2 = [0,0,0,1,0]

So R1CS -

A = [[0,1,0,0,0], [0,0,1,0,2]]
B = [[0,1,0,0,0], [1,0,0,0,0]]
C = [[0,0,0,0,1], [0,0,0,1,0]]

Quadratic Arithmatic Programs

Before the prooving and verification, the R1CS is converted to QAPs so that it is easier to solve using algorithms. Instead of checking m constraints separately, we check one big algebraic condition: divisibility by Z(t).

Given an R1CS with m constraints, a QAP encodes it as polynomials A(t),B(t),C(t) so that -

P(t) = A(t)B(t) - C(t)

is divisible by the vanishing polynomial

Z(t) = (t-1)*(t-2)*(t-3).....(t-m)

Why this works?

If the solution provided by the prover is correct,

A(t)B(t) = C(t) at t = i where i = 1,2,....,m

So, we create a polynomial Z(t) which has the same roots as P(t) = A(t)B(t) - C(t) and if this is the case, then Z(t) divides P(t) as they have the exact same roots. So,

P(t)=Q(t)⋅Z(t)

Important: degree(Q(t)) <= m - 2, m is the number of roots of Z i.e. number of values of i

Lagrange's Basis/Interpolation

For a set of n points, there is a unique lowest-degree polynomial of at most n - 1 degree that interpolates them. Vice verse is - If we use the points (1,2,...,n) as the x values to convert a length n vector to a polynomial via Lagrange interpolation, then the resulting polynomial is unique.

Suppose you have some points you want to “fit” with a polynomial. For example, say we want a polynomial p(t) such that:

p(1)=5

p(2)=7

p(3)=4

We build such a polynomial using Lagrange's trick. The idea is: build basis polynomials Li(t) such that each one is 1 at its own point and 0 at all the others. So,

L1(t): equals 1 at t=1 but 0 at t=2,3

L2(t): equals 1 at t=2, but 0 at t=1,3

L3(t): equals 1 at t=3, but 0 at t=1,2

Once we have these, we can just combine these -

p(t)=5⋅L1(t) + 7⋅L2(t) + 4⋅L3(t).

Now to calculate L1(t), L2(t) and L3(t), we calculate -

Li(t) = Product of ((t - j)/(i - j)) from j = 1 to m and j != i

So,

// For i = 1,
L1(t) = (t - 2) (t - 3)/(1 - 2) (1 - 3) = 1/2 (t - 2)(t - 3)

// For i = 2,
L2(t) = (t - 1) (t - 3)/(2 - 1) (2 - 3) = -1 (t - 1)(t - 3)

// For i = 3,
L3(t) = (t - 1) (t - 2)/(3 - 1) (3 - 2) = -1/2 (t - 1)(t - 2)

Put these values in P(t) to get the QAP.

How SNARKs use QAP?

Circuit → R1CS The circuit is public and fixed. Anyone (both prover & verifier) can derive the R1CS matrices (A, B, C) from it.
R1CS → QAP Once the circuit is fixed, the QAP polynomials (the basis Aj(t),Bj(t),Cj(t), and target Z(t)) are also public. So the verifier knows these too.
Witness The prover has the private inputs (witness), e.g. x,y that satisfy the circuit. Using this witness, prover constructs the concrete polynomial A(t), B(t) and C(t). Then the prover computes -

H(t) = (A(t)B(t) - C(t))/ Z(t)
Prover commits to A,B,C,H.
Verifier only needs to check divisibility condition:
```
A(s)B(s) - C(s) =? H(s)⋅Z(s)
```

s is never known to the prover.

Two famous ways of doing it are Groth16 and Plonk

Trusted Setup

A trusted setup is a mechanism ZK-SNARKs use to evaluate a polynomial at a secret value.

TO BE CONTINUED : )