Zero-Knowledge Proofs (ZK): Proving Facts Without Revealing Inputs

1) ZK Model: Statements, Witnesses, and Circuits

A zero-knowledge proof involves four ingredients: a language of valid statements, a relation that checks those statements, a witness (the secret that makes the relation true), and a protocol where a prover convinces a verifier that the relation holds without revealing the witness. The guarantees are:

• Completeness: an honest prover can convince an honest verifier of true statements.
• Soundness: a cheating prover cannot convince the verifier of false statements except with negligible probability.
• Zero-knowledge: the verifier learns nothing about the witness beyond the fact that a valid witness exists.

Modern systems encode the relation as a large set of algebraic constraints. If the witness satisfies them, a succinct proof exists. If not, any proof will fail verification.

• Witness examples: the preimage of a hash, factors of a number, the secret key corresponding to a signature, the private inputs and intermediate states of a computation.
• Public inputs: values the verifier already knows or that must be fixed by the application, such as a Merkle root, a state root, a recipient address, or an amount bound by policy.
• Non-interactive proofs: many interactive protocols become single-message proofs using Fiat–Shamir, where challenges are derived by hashing the transcript and public inputs.

// Conceptual statement
// Prove knowledge of x such that:
//   1) H(x) = y  (preimage relation)
//   2) 18 ≤ x < 2^64  (range relation)
// Public input: y
// Witness: x
// Output: succinct proof π; anyone verifies (y, π) without learning x.

2) zk-SNARKs versus zk-STARKs

Other axes to compare:

• Prover time: SNARK provers are often faster for small to medium circuits. STARK provers scale very well for massive traces because of FFT friendly fields and parallelism.
• Recursion: modern SNARKs support efficient recursion and folding (proofs of proofs). STARK recursion exists and is improving, but on EVM it may be more costly.
• Verifier costs: SNARK verification can fit into a few hundred thousand gas on Ethereum depending on scheme and batching. STARK verification may require more calldata and computation unless aided by precompiles or verified off chain then attested.
• Setup: circuit specific setups lock parameters to one circuit. Universal setups support many circuits with the same common reference string. Transparent schemes avoid setup entirely.
• Curves and fields: SNARKs often use BN254 or BLS12-381. STARKs favor fields that admit fast number theoretic transforms and efficient FRI parameters.

3) From Program to Circuit to Proof

Authoring ZK applications feels like writing a program that must obey algebra. Toolchains translate code into constraints; the prover finds a witness assignment that satisfies them; the verifier checks a succinct certificate.

1. Write logic: in a domain language like Circom, Noir, Halo2, Cairo, or a zkVM language. Think in terms of field arithmetic, range checks, table lookups, and Merkle gadgets.
2. Compile to constraints: the compiler emits R1CS or PLONKish gates for SNARKs, or an algebraic intermediate representation and an execution trace for STARKs.
3. Prove: the prover commits to polynomials or trace columns, answers consistency queries, and produces a short proof. Fiat–Shamir removes online interaction.
4. Verify: on chain or off chain, the verifier performs constant or logarithmic work to accept or reject the proof for given public inputs.

Design tips:

• Lookups and custom gates: PLONKish systems let you implement operations like Keccak rounds or elliptic curve additions more cheaply by baking them into gates or tables.
• Bit constraints: if you treat values as integers later, enforce bitness and ranges inside the circuit. Field arithmetic wraps modulo a prime; without checks you can “prove” invalid integer behavior.
• Hash choices: use ZK friendly hashes (Poseidon, Rescue) inside circuits for performance. Interoperate with Keccak or SHA at the boundaries if your chain requires it.

// Circom-like sketch: prove H(x) = y and x ≥ 18
template AgeGate() {
  signal input x;
  signal input y;   // public
  // 1) Range check (simple example; real code uses proper bit decomposition)
  component bits[64];
  var sum = 0;
  for (var i=0; i<64; i++) { bits[i] = IsBit(); bits[i].in <== ...; sum += bits[i].out * (1 << i); } x === sum; // bind x to its bits // enforce x ≥ 18 assert(x - 18 >= 0);            // conceptual; actual circuits use comparators
  // 2) Hash gadget
  component P = Poseidon(1);
  P.inputs[0] <== x;
  P.out === y;
}

4) Arithmetization: R1CS, PLONKish, and AIR

Arithmetization converts program semantics into algebra. You will meet three families often:

• R1CS: expresses constraints as A·w ∘ B·w = C·w where w is the vector of witness variables and ∘ is element wise product. Simple and widely supported; great for pedagogical circuits and many production systems.
• PLONKish gates: express constraints by wiring variables into gates and enforcing polynomial identities over a large evaluation domain. They support lookups and custom gates, which can drastically cut constraint counts for structured operations.
• AIR (for STARKs): defines transition rules over an execution trace, then checks that these rules hold on a random subset of rows using low degree tests and FRI. You think like a VM designer: specify next state as a function of current state.

Choosing one: R1CS is straightforward for small circuits. PLONKish dominates modern SNARK stacks because of flexibility. STARKs and zkVMs center around AIR because it is a natural fit for program traces.

5) Polynomial and Hash Commitments

Commitment schemes let the prover bind to polynomials or traces and later open values at chosen points.

• KZG commitments: tiny openings and constant verifier time. They require a structured reference string produced by a ceremony. Widely used in PLONK like systems.
• Inner product commitments: avoid trusted setup at the cost of larger proofs and linear verifier time in some dimensions. Used by Spartan or IPA based SNARKs.
• FRI and Merkle commitments: hash based commitments over evaluation tables. They underpin STARKs and give transparency at the cost of larger proof sizes and hashing work for the verifier.

At a high level, SNARK verifiers perform a few pairings or multi scalar multiplications; STARK verifiers perform many hashes and polynomial queries. Which is cheaper depends on your chain’s precompiles, gas schedule, and calldata limits.

6) Recursion, Folding, and Aggregation

Recursion means verifying a proof inside another proof. This unlocks powerful patterns:

• Batching: aggregate many user proofs into one. The chain verifies the batch once instead of verifying each proof individually.
• Incremental verification: maintain a single proof that attests to the validity of a growing log (for example, a rollup’s history or a set of private actions). Each new step folds into the cumulative proof.
• Cross system pipelines: a STARK proof can be wrapped in a small SNARK so the EVM pays a constant verification cost.

Folding schemes like Nova and successors reduce the cost of maintaining a running proof by folding many instances into one relation that stays small. They excel when you have long lived sessions or streaming computation.

7) Where ZK Is Used Today

• Validity rollups: batch many transactions, compute the new state off chain, and post a succinct proof that state transitions obeyed the rules. L1 verifies the proof and accepts the new state root. This yields L1 security while raising throughput.
• Shielded transfers: commitments hide values, nullifiers prevent double spends, Merkle proofs establish membership. Users transfer without revealing linkages or amounts while preserving conservation of value.
• Identity and access: holders present zero-knowledge attestations such as “over 18,” “belongs to organization X,” or “has an unspent membership token” without doxing every detail. This pairs naturally with DIDs and verifiable credentials.
• Verifiable compute: oracles and off-chain workers return answers alongside proofs that a specified algorithm executed on committed inputs. Think on chain TWAP, auctions, random beacons with bias resistance, or parts of ML inference.
• Fair lotteries and games: commit and reveal with ZK to prevent bias or timing manipulation. Players prove valid moves without revealing private state before its time.

8) Design Checklist and Footguns

• Constrain everything that matters: if a value affects an outcome outside the circuit, it must be constrained or it becomes a lever for cheating. Missing a constraint equals a vulnerability.
• Bind to domain and version: make the chain id, contract addresses, and a version tag part of public inputs. This prevents replay across apps and chains.
• Public input sanity: do not let the prover choose “constants” like the initial state root, fee policy, or verifier key hash. Those must be fixed by the application.
• Range and boolean checks: if you later cast a field element to a 64 bit int, prove it was within range. Constrain boolean flags to zero or one explicitly.
• Hash selection: choose ZK friendly hashes inside circuits and convert at boundaries if needed. Document the exact hash function and parameters.
• Trusted setup hygiene: if your SNARK needs it, run a multi party ceremony, publish transcripts, and prefer universal setups. Store verifying keys immutably or behind a timelocked governance process.
• Side channels: zero-knowledge hides witnesses, but implementations can still leak via logs or timing. Scrub debug output and avoid secret dependent branches in native code that feeds witnesses.
• Audit both halves: review the circuit and the host code that constructs witnesses. Many bugs live in witness assembly rather than the constraint system.

9) Verification Economics on Chain

Proof verification must fit your chain’s gas and calldata envelope. On the EVM, pairing friendly SNARKs are practical because precompiles accelerate pairings and multi scalar multiplications. STARK verification is heavier today; ecosystems mitigate this with specialized precompiles, verifying STARKs off chain and posting succinct attestations, or wrapping STARKs in small SNARKs.

• Aggregation and recursion: aggregate many proofs or verify a proof inside another proof to keep per transaction gas predictable. Rollups often aggregate user proofs off chain, then verify one object on L1.
• Calldata sizing: proof size matters because calldata costs accumulate. Favor schemes whose proofs fit comfortably within block limits when batching many users.
• Data availability: validity ensures correctness, not availability. If others need to reconstruct state, publish calldata, store blobs, or use a data availability committee with explicit trust assumptions.

10) Ceremonies, Keys, Tooling, and Operations

• Setup ceremonies: multi party “powers of tau” style procedures reduce trust in any one participant. Automate transcript verification and publish checksums.
• Key management: version proving and verifying keys, store them immutably or under timelock, and checksum them in code. Rotations should be rare and well publicized.
• Monitoring: track proving latency, throughput, proof failure rates, and verification gas trends. Alert on deviations from budgets.
• Audits and fuzzing: fuzz constraint boundaries and public input handling. Build property based tests that try to violate invariants.
• Developer ergonomics: start with tiny circuits that capture the core invariant, then iterate. Record benchmark deltas as features land.

11) Circuits versus zkVMs and zkEVMs

Hand written circuits give maximal performance and control but require domain expertise. zkVMs run ordinary programs on a constrained virtual machine and then prove the machine’s trace. zkEVMs aim to prove EVM execution faithfully so existing smart contracts work with minimal changes.

• Pros of zkVMs: faster iteration, easier portability, and a familiar developer experience. Good for verifiable compute and fast moving logic.
• Pros of hand circuits: lower proving cost and smaller proofs for narrowly defined tasks such as transfer circuits, Merkle updates, or bespoke privacy gadgets.
• Hybrid approach: prototype in a zkVM, then carve out hot paths into hand optimized circuits as usage grows.

12) Privacy Patterns: Commitments, Nullifiers, and Set Membership

Most privacy systems follow the same skeleton:

1. Commitment: create C = Commit(value, blinding) and add it to a Merkle tree. The tree root becomes a public input.
2. Set membership: prove inclusion of C in the tree by revealing only sibling hashes, not the path or the leaf value.
3. Nullifier: publish a unique nullifier derived from the secret so each note can be spent once without revealing which note it was. Verifiers reject repeated nullifiers.
4. Balance and policy: constrain that inputs equal outputs plus fees and that amounts stay in range. Bind destination addresses as public inputs if the policy requires it.

// Nullifier sketch (concept)
// nf = H(secret * domain + leafIndex)
// Circuit shows knowledge of secret and inclusion path, then exposes nf as public input.
// On chain, maintain a mapping[nf] = true to prevent double use.

For identity and selective disclosure, the pattern is similar: prove knowledge of a credential signed by an issuer and then prove a predicate on its attributes (for example “age ≥ 18”) without revealing raw fields. Bind the presentation to an audience and nonce to prevent replay.

13) Interoperability and Domain Binding

ZK by itself does not solve cross domain replay. Always bind proofs to the exact context where they will be accepted:

• Public inputs: include chain id, verifying contract, and version fields.
• Message binding: when a proof authorizes a cross chain message, include source and destination identifiers, a nonce, and the receiver program in the statement.
• Upgradability: if verifiers can change, consider hashing the verifier bytecode or a verifier id into the statement so old proofs cannot be replayed against new rules.

14) Debugging and Test Vectors

Most integration failures are not cryptography, they are plumbing. A crisp workflow saves days:

• Lock schema: version your public inputs and their order. A swapped field breaks verification even if the math is fine.
• Golden vectors: publish small fixtures with known witnesses and proofs. Verify them in your contract tests and in your off chain verifier.
• Determinism: pin toolchain versions and randomness sources for reproducible proofs during testing.
• Error surfaces: distinguish “proof does not verify” from “public inputs do not match” in logs to guide debugging.

// Solidity verifier wrapper (concept)
function verify(bytes calldata proof, bytes32[] calldata pub) external view returns (bool) {
  // 1) Decode and sanity-check public input length and order
  // 2) Call underlying verifier library
  // 3) Emit events for observability (proof size, gas)
}

15) FAQ

Q: Do ZK proofs give privacy by default?
A: No. A proof can be zero-knowledge or not depending on the relation. Many rollup proofs are about correctness rather than privacy. Privacy requires hiding witnesses and designing the app so that public outputs do not reveal sensitive linkages.

Q: Are SNARKs or STARKs “better”?
A: It depends on your constraints. If you need tiny proofs and cheap EVM verification with acceptable setup assumptions, SNARKs fit. If you want no trusted setup and prefer conservative assumptions with larger proofs, STARKs fit. Many systems combine them.

Q: If I use zero-knowledge, do I still need data availability?
A: Yes, if others must reconstruct state or independently verify and continue the protocol. Validity proves correct transitions but does not reveal the data itself.

Q: Can I just port my CPU code to ZK?
A: Not directly. You can run it in a zkVM, but cost will be high unless you optimize. ZK friendly algorithms and data structures matter a lot.

Q: How do I avoid replay across chains?
A: Bind chain id, contract address, and a nonce into public inputs. On the receiving side, store consumed proof identifiers.

Quick check

1. What role does the witness play, and how does zero-knowledge protect it?
2. Give one trade-off between zk-SNARKs and zk-STARKs.
3. Why do validity rollups scale better than replaying all transactions on L1?
4. Name two reasons to use ZK friendly hashes inside circuits.
5. What public inputs should you include to prevent cross domain replay?

Go deeper

• Concept lectures: Fiat–Shamir, polynomial commitments (KZG and IPA), R1CS versus PLONKish gates, AIR and FRI, recursion and folding schemes.
• Engineering lectures: designing Merkle and nullifier circuits, range proofs, table lookups and custom gates, benchmarking and gas budgeting.
• Security lectures: ceremony hygiene, public input binding, unconstrained variable audits, and replay defenses.
• Architecture lectures: hybrid SNARK and STARK stacks, zkVMs and zkEVMs, data availability strategies alongside validity proofs.

Next: Multi-Party Computation,  compute and sign without any single key.

Next: Multi-Party Computation →