zkSNARK

The 'ZK' in zkSNARK. This property ensures the verifier learns absolutely nothing about the prover's secret witness beyond the validity of the statement itself.

• Mechanism: Achieved through a simulator that can generate valid-looking proofs without the witness, proving no information is leaked.
• Practical Impact: Enables private inference in zkML, where a model owner can prove the output of a proprietary model without revealing the model weights or the user's input data.
• Formal Guarantee: Computational zero-knowledge ensures no polynomial-time adversary can extract any information from the proof transcript.

The 'S' in zkSNARK. A proof must be very small (ideally constant in size) and very fast to verify, regardless of the complexity of the computation being proven.

• Proof Size: A Groth16 proof is only ~128 bytes, independent of the circuit size.
• Verification Time: Verification is typically O(1) or logarithmic, often taking only a few milliseconds.
• Scalability Driver: This property is the foundation of ZK-Rollups, where a single succinct proof on a Layer-1 blockchain can attest to the validity of thousands of Layer-2 transactions.

The 'N' in zkSNARK. The proof generation and verification process requires only a single message from the prover to the verifier, with no back-and-forth interaction.

• Construction: Achieved by applying the Fiat-Shamir heuristic, which replaces the verifier's interactive random challenges with the output of a cryptographic hash function modeled as a random oracle.
• Practical Benefit: The prover can generate a proof offline and broadcast it to an unlimited number of verifiers asynchronously, which is essential for blockchain and decentralized systems.
• Contrast: Older interactive protocols required multiple rounds of communication, making them impractical for public, large-scale deployments.

The 'A' and 'K' in zkSNARK. This is a dual property that provides computational soundness and a proof of witness possession.

• Argument: Soundness holds only against computationally bounded provers (unlike a 'proof' which is unconditionally sound). Security relies on cryptographic assumptions like the hardness of the discrete logarithm problem.
• Knowledge: An extractor algorithm exists that can recover the secret witness by interacting with a successful prover. This proves the prover genuinely 'knows' the data that satisfies the circuit, not just that a solution exists.
• Formal Distinction: This is stronger than a simple proof of existence; it is a proof of possession of the underlying secret information.

A fundamental correctness property ensuring that an honest prover with a valid witness can always convince an honest verifier.

• Guarantee: If the prover correctly executes the protocol with a valid witness that satisfies the arithmetic circuit, the verifier will always accept the proof. The probability of rejection is zero.
• Protocol Design: This property is non-negotiable for any practical system. A lack of completeness would mean valid computations could be falsely rejected, breaking the system's reliability.
• Relationship to Soundness: Completeness and soundness are dual properties. Completeness protects the honest prover, while soundness protects the verifier from a malicious prover.

The security property that protects the verifier. A malicious prover without a valid witness cannot convince an honest verifier to accept a false statement, except with negligible probability.

• Computational Soundness: For zkSNARKs, this relies on cryptographic hardness assumptions. A prover breaking soundness would need to solve a computationally infeasible problem, like breaking the discrete log.
• Knowledge Soundness: A stronger variant that guarantees an extractor can retrieve the witness. This is the formal definition of an 'argument of knowledge'.
• Negligible Error: The probability of a false proof being accepted is astronomically small, typically bounded by the security parameter (e.g., 2^-128).

The foundational computational representation that zkSNARKs prove over. A directed acyclic graph where inputs and intermediate values flow through addition and multiplication gates over a finite field.

• Every high-level program must be compiled into an arithmetic circuit before a proof can be generated
• The circuit's size directly impacts prover time and proof generation cost
• Non-arithmetic operations like comparisons and bitwise functions are expensive to represent, requiring decomposition into many gates

A standard format for expressing arithmetic circuit satisfiability as a set of quadratic constraints. Each constraint takes the form (a·s) * (b·s) = (c·s), where s is the witness vector.

• Used extensively in early zkSNARK constructions like Groth16
• The number of constraints equals the number of multiplication gates in the circuit
• Serves as an intermediate representation between high-level code and the cryptographic proving system

A pairing-based zkSNARK protocol that produces the smallest proof sizes (as few as 128 bytes) and fastest verification times (a few milliseconds) in the entire ZKP landscape.

• Requires a circuit-specific trusted setup — each new circuit demands a fresh ceremony
• Verification involves checking a single pairing equation over elliptic curves
• Widely deployed in production systems like Zcash and various zk-rollups where minimal on-chain verification cost is paramount

A universal and updatable zkSNARK construction that uses a single trusted setup ceremony for all circuits up to a bounded size. Introduces the concept of a polynomial interactive oracle proof.

• Eliminates the need for per-circuit ceremonies, dramatically improving developer ergonomics
• Uses permutation arguments and lookup tables to handle copy constraints efficiently
• The universal setup can be updated over time by new participants, strengthening security guarantees

A cryptographic primitive allowing a prover to commit to a polynomial and later open it at specific points with a proof whose size is independent of the polynomial's degree.

• KZG commitments (used in Plonk) offer constant-size openings but require a trusted setup
• FRI (Fast Reed-Solomon IOP of Proximity) commitments (used in STARKs) rely on hash functions and offer post-quantum security
• The choice of commitment scheme fundamentally determines the proof system's size, verification speed, and security assumptions

A technique where the verifier algorithm itself is expressed as an arithmetic circuit, enabling the creation of a single proof that attests to the validity of multiple prior proofs.

• Enables proof aggregation — compressing thousands of individual proofs into one constant-size proof
• Forms the backbone of incrementally verifiable computation (IVC) and proof carrying data (PCD)
• Systems like Halo2 and Nova leverage recursion to achieve scalable, trustless verification of long-running computations