zk-SNARK

The defining characteristic of a SNARK is that the proof size is small and verification time is fast, regardless of the complexity of the computation being proved.

• A proof is typically a constant few hundred bytes, even for computations involving millions of steps.
• Verification takes milliseconds, making it practical for resource-constrained environments like blockchains and smart contracts.
• This is achieved through advanced cryptographic techniques that compress the computation into a single, easily-checkable equation.

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

• The prover generates the proof independently and sends it to the verifier.
• The verifier can check the proof autonomously, without any real-time communication with the prover.
• This property is essential for asynchronous systems where the prover may be offline or the proof needs to be verified by many parties at different times.

The proof reveals absolutely no information about the secret witness (the private input) beyond the validity of the statement itself.

• A verifier learns only a single bit of information: whether the statement is true or false.
• This is formally defined through the existence of a simulator that can produce a valid-looking proof without knowing the witness.
• This property is what enables private transactions on public ledgers, where you can prove you have sufficient funds without revealing your balance.

zk-SNARKs require a one-time trusted setup ceremony to generate a Common Reference String (CRS) used by all provers and verifiers.

• The ceremony produces public parameters from a secret random value, often called "toxic waste."
• If the secret is not destroyed by all participants, it could be used to forge false proofs.
• Modern ceremonies use Multi-Party Computation (MPC) where security holds as long as at least one participant is honest and destroys their secret.

A SNARK is an "argument" rather than a "proof" because its security relies on computational assumptions, not unconditional mathematical truth.

• It is computationally infeasible for a malicious prover to create a valid proof for a false statement, assuming the hardness of certain mathematical problems.
• The "knowledge" aspect means the prover not only proves a statement is true but also proves they know a valid witness that makes it true.
• This is formalized by the existence of an extractor that can recover the witness from the prover's internal state.

The security guarantee is computational, meaning it holds against adversaries with bounded computational power, rather than being unconditionally secure.

• A computationally unbounded adversary could theoretically forge a proof, but such an adversary is not considered feasible in practice.
• This is in contrast to statistical soundness, which holds against all adversaries regardless of their computational power.
• The trade-off for computational soundness is the extreme efficiency gains in proof size and verification speed that make SNARKs practical.

A transparent and post-quantum secure alternative to zk-SNARKs. Unlike SNARKs, STARKs rely solely on collision-resistant hash functions and do not require a trusted setup ceremony, eliminating the toxic waste problem.

• Scalability: Proof size and verification time scale logarithmically with computation size.
• Quantum Resistance: Security based on hash functions rather than elliptic curve pairings.
• Trade-off: Proofs are significantly larger than SNARK proofs (often hundreds of kilobytes vs. a few hundred bytes).

A cryptographic primitive that allows a party to commit to a chosen value while keeping it hidden, with the ability to reveal it later. zk-SNARKs use polynomial commitment schemes as a core building block.

• Binding: The committer cannot change the value after committing.
• Hiding: The commitment reveals nothing about the value.
• KZG Commitments: A popular polynomial commitment scheme used in many SNARK constructions, based on bilinear pairings.

A cryptographic technique that transforms an interactive proof system into a non-interactive one. The verifier's random challenges are replaced by the output of a cryptographic hash function applied to the transcript.

• Mechanism: The prover hashes the current transcript to generate the next challenge deterministically.
• Application: This is the core technique that makes zk-SNARKs non-interactive, requiring only a single message from prover to verifier.
• Security: Proven secure in the random oracle model.

A form of encryption that allows computation directly on ciphertexts, generating an encrypted result that, when decrypted, matches the result of operations performed on the plaintext. While distinct from ZKPs, it serves a complementary privacy role.

• Partially Homomorphic: Supports only addition or multiplication (e.g., RSA, Paillier).
• Fully Homomorphic (FHE): Supports arbitrary computation on encrypted data.
• Synergy with ZKPs: FHE can compute privately, while a zk-SNARK can prove the computation was performed correctly.