ZK-SNARKS

Non-interactive zero-knowledge proofs are a variant of zero-knowledge proofs in which no interaction is necessary between prover and verifier.

The Scheme

Generator (C circuit, λ is ️):
(pk, vk) = G(λ, C)
Prover (x pub inp, w sec inp):
π = P(pk, x, w)
Verifier:
V(vk, x, π) == (∃ w s.t. C(x,w))

This library implements the pipeline end to end: a small JS-subset compiler turns an arithmetic circuit into an R1CS, R1CS is reduced to a QAP, and the QAP is proved and verified with a pairing-based trusted setup over a BN (Barreto–Naehrig) elliptic curve.

Install

npm install

Quick start

The one-shot pipeline, from source code to a verified proof:

const { toR1CS } = require('zk-snark')

toR1CS(
    `
    function qeval(x) {
        let y = x**3
        return y + x + 5
    }
    `,
    [3] // public input: x = 3
)
// logs the flattened circuit and "Verifiable or NOT? =>  true"

Or drive each stage yourself for more control:

const {
    R1CS, QAP, TrustedSetup,
    Curve, Curve2,
    bn, bn2, Field2,
} = require('zk-snark')

const code = `
    function qeval(x) {
        let y = x**3
        return y + x + 5
    }
`
const { inputs, body } = R1CS.extractCode(code)
const flatcode = R1CS.convertToFlat(body)
const { A, B, C } = R1CS.fromFlatcode(inputs, flatcode)
const r = R1CS.evaluateCode(inputs, [3], flatcode) // witness, incl. public input

const { Ap, Bp, Cp, Z } = QAP.fromR1CS(A, B, C)
Z.push(new Field2(bn2, bn2._0))
Z.push(new Field2(bn2, bn2._0))

const E = new Curve(bn)
const Et = new Curve2(E)
const ts = new TrustedSetup(E, Et)

const { pk, vk } = ts.createkey(Ap, Bp, Cp, Z)
const proof = ts.prover(Ap, Bp, Cp, Z, pk, r)

ts.verify(proof, vk, r.slice(0, 2)) // => true

Testing

npm test              # run the unit + end-to-end test suite
npm run test:coverage # the same, with a coverage report
npm run lint          # ESLint

The test suite (test/*.test.js, plus the original end-to-end all.test.js) exercises every export below: field and curve group-law identities, pairing bilinearity e(aG, bH) == e(G, H)^(ab), R1CS constraint satisfaction, QAP interpolation correctness, and full proof generation/verification including soundness (a proof for one public input is rejected against another).

API

Everything below is a named export of the package root (require('zk-snark') / require('./src')).

SNARK pipeline

R1CS

Compiles a small JS subset (a single function using + - * / ** with integer literal exponents) into an R1CS (Rank-1 Constraint System).

• R1CS.extractCode(code) → { inputs, body } — parses the source (via esprima) into its parameter list and statement body.
• R1CS.convertToFlat(body) → flat 4-tuples like ['*', 'sym_1', 'x', 'x'], one per elementary operation. a**n for a literal integer n is unrolled into repeated multiplications; a**0/a**1 become a set.
• R1CS.fromFlatcode(inputs, flatcode) → { A, B, C }, the constraint matrices such that for every row i, (A[i]·r) * (B[i]·r) === (C[i]·r) for the witness vector r.
• R1CS.evaluateCode(inputs, inputVars, flatcode) → the witness vector r (as Field2 elements) obtained by concretely running the flat code on inputVars.
• R1CS.genid() → a fresh unique symbol name (sym_1, sym_2, …) used for intermediate variables.

QAP

Reduces an R1CS to a Quadratic Arithmetic Program by Lagrange-interpolating each matrix column over the points x = 1..m (m = number of constraints).

• QAP.fromR1CS(A, B, C) → { Ap, Bp, Cp, Z } — Ap[j]/Bp[j]/Cp[j] are the interpolated polynomials for variable column j; Z is the vanishing polynomial ∏(x - i) for i = 1..m.

TrustedSetup

The pairing-based setup/prove/verify protocol, over a curve E and its twist Et (see Curve).

• new TrustedSetup(E, Et)
• .createkey(Ap, Bp, Cp, Z) → { pk, vk } — the (insecure toy) trusted setup, sampling the proving and verification keys.
• .prover(Ap, Bp, Cp, Z, pk, r) → proof — builds a proof from the witness r and the proving key.
• .verify(proof, vk, input) → boolean — input is the public prefix of the witness vector (e.g. r.slice(0, 2) for [~one, x]). Checks the knowledge-commitment pairings, the same-coefficients pairing, and the QAP divisibility pairing.

toR1CS(code, inputVars)

Convenience one-shot pipeline that strings R1CS → QAP → TrustedSetup together for a single public input vector and logs whether the resulting proof verifies. Returns nothing; see Quick start.

Polynomials

Polynomial

Static helpers for polynomials represented as coefficient arrays, index = degree. Two parallel families exist: the *Field/undecorated methods operate on arrays of Field2 elements (used by the QAP/SNARK pipeline); the *2 methods operate on arrays of plain JS numbers.

• Polynomial.add(a, b, subtract = false) / .sub(a, b) / .mul(a, b) — Field2-coefficient add/subtract/multiply.
• Polynomial.div(a, b), .polyLongDivField(n, d) — division with remainder; polyLongDivField requires n.length === d.length (pad the shorter side with zero coefficients first).
• Polynomial.degree2(p) — highest non-zero coefficient index (-Infinity for the zero polynomial).
• Polynomial.evaluateField(poly, x) — evaluate at a Field2 point x.
• Polynomial.evaluateFieldOverPrime(poly, x, p) — evaluate poly[i].re at a raw-bigint point x.re, reduced mod a given prime p.
• Polynomial.evaluateNum(poly, x) — same, returning a raw bigint instead of a Field2.
• Polynomial.interpolation(i, x) — Lagrange basis coefficients for point index i over sample points x (all Field2).
• Polynomial.interpolationOverField(x, y) — the full interpolated polynomial through points (x[i], y[i]).
• Polynomial.add2/sub2/mul2/div2/degree/polyShiftRight/polyLongDiv/evaluate — the plain-number counterparts, useful outside the Field2 pipeline.

bn

The default curve parameters: new Parameters(128) (see Parameters).

bn2

A minimal { p, _0, _1, _5, Fp2_1 } params object with p = bn.n (the curve order, not its base-field prime) — this is the field the R1CS witness and QAP polynomials live in.

evalAll(polymatrix, x)

Evaluates every polynomial in a matrix (e.g. Ap/Bp/Cp) at the point x (a plain number or bigint, wrapped into Field2(bn2, x)).

linearCombination(r, A, B, C)

Combines the QAP polynomials with witness weights: Apoly = Σ r[i]·A[i], likewise for B/C, and returns { Apoly, Bpoly, Cpoly, sol } where sol = Apoly*Bpoly - Cpoly (the polynomial that Z must divide for a valid witness).

Elliptic curves & points

Curve / Curve2

Curve is the base BN curve E: y² = x³ + b over Fp; Curve2 is its sextic twist Et over Fp2, used as the second pairing source group.

• new Curve(bn) / new Curve2(E) — bn is a Parameters instance; exposes .G/.Gt (generator), .infinity, .b.
• .contains(P) → boolean — checks the (Jacobian-coordinate) curve equation.
• .pointFactory(rand) — samples a random point given a CryptoRandom.
• .kG(k) — windowed scalar multiplication of the generator by k.

Point / Point2

Jacobian-coordinate points on Curve/Curve2 respectively. Both expose the same group-law API:

• new Point(E, x, y) / new Point(E, x, y, z) / new Point(otherPoint)
• .add(Q), .twice(n) (2ⁿ-fold doubling), .neg(), .subtract(Q)
• .multiply(k) — scalar multiplication (GLV decomposition, or windowed via a precomputed table after calling .getSerializedTable()).
• .zero() / .eq(Q) / .same(Q) (same curve) / .opposite(Q) (this == -Q) / .isNormal() (Z ∈ {0, 1}) / .norm() (normalize to Z = 1).
• .toByteArray(formFlags) — SEC1-style point serialization (formFlags: 2 = include a compressed y-parity bit, 4 = also include the full y).

Pairing

Pairing

The bilinear pairing e: E(Fp) × Et(Fp2) → Fp12*, i.e. e(aP, bQ) = e(P, Q)^(ab).

• new Pairing(Et)
• .ate(P, Q) — the Optimal Ate pairing (used by TrustedSetup).
• .tate(P, Q) — the Tate pairing via Miller's algorithm; also bilinear, independent implementation.
• .doubletate(P, Q, P2, Q2) — batches two Miller loops without the final exponentiation, i.e. finExp(doubletate(P,Q,P2,Q2)) == tate(P,Q) * tate(P2,Q2), for callers who want to defer/amortize the (expensive) final exponentiation.

Fields & curve parameters

Field2, Field4, Field6, Field12

The tower of extension fields Fp ⊂ Fp2 ⊂ Fp4/Fp6 ⊂ Fp12 used for curve coordinates (Fp/Fp2) and pairing outputs (Fp12). All four share the same shape of API:

• .zero() / .one() / .eq(v) / .neg()
• .add(v) / .subtract(v) / .multiply(v) / .square()
• .inverse() (Field2, Field4, Field12) — multiplicative inverse.
• .twice(k) / .halve() (Field2, Field6) — 2ᵏ-fold doubling / its inverse.
• Field2 also has .exp(k), .sqrt(), .cbrt(), .mulV()/.divV() (multiply/divide by the sextic non-residue), and stores its two coordinates as raw bigints in .re/.im.

Construction mirrors the tower: new Field2(bn, someBigInt), new Field4(bn, aField2), new Field6(bn, aField2), new Field12(bn, someBigInt) all build the corresponding zero-extended element; passing a CryptoRandom instance instead samples a random element.

Parameters

BN-curve parameter generation: given a target field size, derives the base prime p, curve order n, trace t, and every derived constant the field tower and pairing need (zeta, sqrtExponent2, Fp2_0/Fp2_1, Fp12_0/Fp12_1, …).

• new Parameters(fieldBits) — fieldBits must be one of the 68 supported sizes (multiples of 8 from 48 to 512, plus a 27-bit debug curve); throws otherwise. bn is new Parameters(128).
• .p / .n / .t — base prime, curve order, trace (n = p + 1 - t).
• .modulus / .order — getters aliasing .p / .n.
• .legendre(v), .lucas(P, k) — number-theoretic helpers used internally by square/cube-root finding.

Utilities

ExNumber

Static bigint helpers with the Java-BigInteger-flavored names the rest of the codebase expects:

• ExNumber.construct(n, b) — from a bit length (number, random), a string (optionally in base b), or passes a bigint through.
• ExNumber.mod(a, p) — reduces a into [0, p), unlike the native % which keeps the sign of a.
• ExNumber.signum(a) → -1 | 0 | 1.
• ExNumber.testBit(a, n) → boolean — the two's-complement bit at position n.
• ExNumber.toByteArray(a) — big-endian byte array of a's magnitude.

CryptoRandom

A minimal nextBytes(byteArray) PRNG backed by Node's crypto.randomBytes, implementing the interface Field2/Field4/Field6/Field12/Curve constructors accept for random sampling.

bigInt

The big-integer-compatible factory this whole library is built on (src/BigIntCompat.js). Every arithmetic value in the library is a native bigint primitive; this module adds big-integer's chained-method API (.add(), .multiply(), .shiftLeft(), .modPow(), .isInstance(), …) as extensions on BigInt.prototype plus a handful of static helpers (bigInt.zero, bigInt.isInstance, bigInt.randBetween, bigInt.gcd, …), so bigInt(x) and bigInt('ff', 16) behave as they would with the big-integer npm package, without the extra dependency.

PrimeField

A tiny standalone Z/pZ field for plain JS numbers (not bigint), used by KnowledgeCoefficient.

• new PrimeField(p)
• .add(a, b) / .mul(a, b) / .mod(a) — all reduced into [0, p).
• .oneElement() / .nullElement() — the 1 / 0 identities.

KnowledgeCoefficient

A standalone implementation of the knowledge-of-coefficient (KC) test — Pepper's/Groth's technique for checking a prover evaluated the same committed polynomial coefficients it claims to have, without a full pairing setup. Independent of the R1CS/QAP/TrustedSetup pipeline above; operates over a plain PrimeField.

• new KnowledgeCoefficient(a, alpha, coeffs, p) — samples b = a·alpha.
• .respond(gamma) — derives the challenge response a2 = a·gamma, b2 = b·gamma.
• .generateHidings(s, d) → { hidings, hidingsalpha } — commitments to the coefficients at point s and their alpha-shifted counterparts.
• .evaluatePolynomial(hidings) — evaluates Σ coeffs[i] · hidings[i].