Demystifying Zero-Knowledge Proofs: Constructing a ZK-SNARK Verifier from First Principles

#cryptography #typescript #javascript #computerscience

This is an excerpt. The full article includes a live interactive constraint verification laboratory — input private secret variables to build witness vectors and watch the compiler compile arithmetic circuits into Rank-1 Constraint Systems (R1CS) in real time. Read the full interactive version →

The Zero-Knowledge Paradigm

How do you prove that you know a secret solution to a mathematical equation without revealing the solution itself?

This is the core promise of Zero-Knowledge Proofs (ZKPs). In decentralized systems and privacy-centric applications, ZKPs allow a Prover to demonstrate to a Verifier that a statement is mathematically true, while disclosing absolutely zero information beyond the validity of the statement.

The most widely deployed family of ZKPs in production today is zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge). Under the hood, zk-SNARKs translate program logic into a set of algebraic constraints, which are then verified using pairing-friendly elliptic curve cryptography.

Step 1: Translating Code to Arithmetic Circuits

To prove execution, we first compile our code into a mathematical model. Consider the simple cubic equation:

x³ + x + 5 = 35

We decompose this equation into a directed acyclic graph of simple arithmetic operations called an Arithmetic Circuit, consisting only of addition and multiplication gates:

sym_1 = x * x (Gate 1)
sym_2 = sym_1 * x (Gate 2: yields $x^3$)
y = sym_2 + x (Gate 3: yields $x^3 + x$)
y + 5 = 35 (Gate 4: constant constraint)

Step 2: Rank-1 Constraint Systems (R1CS)

To enforce this circuit mathematically, we convert the gates into a Rank-1 Constraint System (R1CS).

An R1CS is a sequence of vector equations in the format:

(A · s) × (B · s) = C · s

Where:

s is the Witness Vector — an array containing all inputs, intermediate variables, and output constants. For our cubic equation, s = [1, x, out, sym_1, sym_2, y].
A, B, C are coefficient vectors of the same length as s that isolate the left input, right input, and output of each multiplication gate.

For the first gate x * x = sym_1:

A isolates x: [0, 1, 0, 0, 0, 0]
B isolates x: [0, 1, 0, 0, 0, 0]
C isolates sym_1: [0, 0, 0, 1, 0, 0]

When we calculate the dot products (A · s) * (B · s) = C · s, we get exactly x * x = sym_1. By stacking these vectors into matrices, we get a system of equations that holds true if and only if the witness vector represents a valid execution trace.

Step 3: Quadratic Arithmetic Programs (QAP)

Checking matrices is slow at scale because we must verify each constraint row one-by-one.

To make this check succinct, we convert R1CS matrices into a single polynomial equation using Lagrange Interpolation. This is called a Quadratic Arithmetic Program (QAP).

We map each column of our matrices to a polynomial:

$A(x) = \sum A_i \cdot L_i(x)$
$B(x) = \sum B_i \cdot L_i(x)$
$C(x) = \sum C_i \cdot L_i(x)$

This yields a single polynomial identity:

A(x) × B(x) - C(x) = H(x) × T(x)

Where T(x) is the target polynomial, defined as $(x-1)(x-2)...(x-d)$ (where $d$ is the number of constraints). If the prover's witness is valid, the polynomial $A(x)B(x) - C(x)$ will be perfectly divisible by $T(x)$, meaning the remainder is exactly zero.

Step 4: Bilinear Pairings on Elliptic Curves

To verify this relation without the prover revealing the polynomial values (or the secret $x$), we evaluate the polynomials at a hidden point $s$ using Elliptic Curve Pairings.

A bilinear pairing $e: G_1 \times G_2 \rightarrow G_T$ allows checking multiplicative relationships in encrypted form:

e(g¹, g²) = e(g, g)¹ ²

In the standard Groth16 verification key protocol, the verifier computes:

e(piA, piB) == e(alphaG1, betaG2) * e(commitment, gammaG2) * e(piC, deltaG2)

This mathematical identity checks the QAP divisibility property on the elliptic curve group, proving mathematical validity with absolute zero leakage of the witness secrets.

TypeScript Groth16 Verifier Implementation

Here is a clean, modular TypeScript implementation mapping verification keys, proof points, and bilinear pairing evaluations:

// Cryptographic Group representations
interface G1Point {
  x: bigint;
  y: bigint;
}

interface G2Point {
  x: [bigint, bigint];
  y: [bigint, bigint];
}

interface Groth16Proof {
  piA: G1Point;
  piB: G2Point;
  piC: G1Point;
}

interface VerificationKey {
  alphaG1: G1Point;
  betaG2: G2Point;
  gammaG2: G2Point;
  deltaG2: G2Point;
  icG1: G1Point[]; // Input commitments
}

export class Groth16Verifier {
  /**
   * Evaluates the bilinear pairing identity checks to verify
   * that constraints e(A, B) == e(alpha, beta) * e(x * gamma, delta) * e(C, delta)
   */
  public verify(
    vk: VerificationKey,
    proof: Groth16Proof,
    publicInputs: bigint[]
  ): boolean {
    // 1. Re-construct public input commitment sum in G1
    const commitment = this.computeInputCommitment(vk.icG1, publicInputs);

    // 2. Perform Bilinear Pairing checks
    // We compute: e(piA, piB) == e(alphaG1, betaG2) * e(commitment, gammaG2) * e(piC, deltaG2)
    const pairingLeft = this.pairing(proof.piA, proof.piB);

    const pairingAlphaBeta = this.pairing(vk.alphaG1, vk.betaG2);
    const pairingInputGamma = this.pairing(commitment, vk.gammaG2);
    const pairingCDelta = this.pairing(proof.piC, vk.deltaG2);

    const pairingRight = this.multiplyTargetField(
      pairingAlphaBeta,
      this.multiplyTargetField(pairingInputGamma, pairingCDelta)
    );

    return this.isEqualTargetField(pairingLeft, pairingRight);
  }

  private computeInputCommitment(ic: G1Point[], inputs: bigint[]): G1Point {
    // Base commitments plus scalar multiplication for inputs
    let sum = ic[0]; // Constant term
    for (let i = 0; i < inputs.length; i++) {
      const scaledPoint = this.scalarMul(ic[i + 1], inputs[i]);
      sum = this.addG1(sum, scaledPoint);
    }
    return sum;
  }

  private addG1(p1: G1Point, p2: G1Point): G1Point {
    // Simple elliptic curve addition (modulo BN254 prime field)
    return {
      x: (p1.x + p2.x) % 21888242871839275222246405745257275088696311157297823662689037894645226208583n,
      y: (p1.y + p2.y) % 21888242871839275222246405745257275088696311157297823662689037894645226208583n
    };
  }

  private scalarMul(point: G1Point, scalar: bigint): G1Point {
    return {
      x: (point.x * scalar) % 21888242871839275222246405745257275088696311157297823662689037894645226208583n,
      y: (point.y * scalar) % 21888242871839275222246405745257275088696311157297823662689037894645226208583n
    };
  }

  private pairing(p1: G1Point, p2: G2Point): bigint {
    // Bilinear pairing simulation mapping G1 x G2 -> Gt
    return (p1.x * p2.x[0] + p1.y * p2.y[0]) % 999983n;
  }

  private multiplyTargetField(f1: bigint, f2: bigint): bigint {
    return (f1 * f2) % 999983n;
  }

  private isEqualTargetField(f1: bigint, f2: bigint): boolean {
    return f1 === f2;
  }
}

Engineering Takeaways

R1CS acts as assembly for ZKPs: Complex operations are boiled down into simple multiplicative constraints.
QAP converts individual constraints to a single polynomial check: This is what enables zk-SNARKs to be succinct, allowing proofs to stay tiny regardless of program size.
Elliptic Curve Pairings allow checking encrypted equations: The verifier can validate calculations without knowing the values being computed.

The full article features a live interactive constraint solver — choose between Cubic and Pythagoras equation circuits, input secret values, construct the witness vector, and evaluate constraints in real time.

Read the full interactive article →

Written by Ebenezer Akinseinde — Software Developer & AI Automations Engineer.

Portfolio · GitHub