Zero-Knowledge Proof

If the statement is true and both the prover and verifier follow the protocol honestly, an honest verifier will always be convinced by an honest prover.

• Guarantee: No false negatives. A valid proof will never be rejected.
• Mechanism: The protocol's mathematical construction ensures that a prover possessing the secret witness can always generate a valid proof.
• Example: If Alice knows the preimage of a hash h, she can always successfully complete a ZKP protocol with Bob to prove this knowledge.

If the statement is false, no cheating prover can convince an honest verifier that it is true, except with some negligible probability.

• Guarantee: No false positives. A malicious prover cannot forge a proof for an invalid statement.
• Computational vs. Statistical: Computational soundness relies on computationally hard problems; statistical soundness holds against unbounded provers.
• Knowledge Soundness: A stronger variant where an extractor algorithm can recover the secret witness from any successful prover, proving the prover actually 'knows' the secret.

The verifier learns absolutely nothing about the secret witness beyond the single bit of information: 'the statement is true.'

• Guarantee: The verifier's view of the interaction can be perfectly simulated without any access to the prover's secret.
• Simulator Paradigm: Security is proven by constructing a simulator that, without knowing the secret, can produce a transcript indistinguishable from a real interaction.
• Types: Perfect ZK (distributions are identical), Statistical ZK (distributions are statistically close), and Computational ZK (distributions are computationally indistinguishable).

ZKPs can be categorized by the communication pattern between prover and verifier.

• Interactive ZKPs: Require multiple rounds of challenge-response messages. The verifier sends random challenges that the prover must answer. Example: the classic graph isomorphism protocol.
• Non-Interactive ZKPs (NIZKs): The prover generates a single, self-contained proof that anyone can verify without back-and-forth interaction. This is the practical standard for blockchain and confidential computing.
• Fiat-Shamir Heuristic: A transformation that converts interactive protocols into non-interactive ones by replacing the verifier's random challenges with the output of a cryptographic hash function applied to the protocol transcript.

A highly desirable property for modern ZKP systems, especially in blockchain scaling. A Succinct Non-Interactive Argument of Knowledge (SNARK) produces proofs that are:

• Tiny: Proof size is constant or logarithmic relative to the computation size, often just a few hundred bytes.
• Fast to Verify: Verification time is exponentially faster than re-executing the computation, often taking milliseconds regardless of the statement's complexity.
• Trade-off: Achieving succinctness often requires a trusted setup ceremony and relies on stronger cryptographic assumptions, though transparent setups (STARKs) eliminate this requirement.

A ZKP is a 'Proof of Knowledge' if it demonstrates not just that a statement is true, but that the prover actually possesses the specific secret witness w that makes the statement true.

• Formal Definition: There exists a knowledge extractor—a polynomial-time algorithm with privileged access to the prover—that can extract the witness w.
• Distinction: Proving 'a Sudoku solution exists' is different from proving 'I know a Sudoku solution.' The latter is a Proof of Knowledge.
• Application: Essential for authentication protocols where a user must prove possession of a private key corresponding to a public key, not just that such a key exists.

A Zero-Knowledge Succinct Non-Interactive Argument of Knowledge is a proof construction that is small in size and fast to verify, requiring no back-and-forth interaction between prover and verifier.

• Succinctness: Proof size is constant (a few hundred bytes) regardless of the statement's complexity.
• Trusted Setup: Requires a one-time generation of a Common Reference String (CRS) using secret randomness, known as toxic waste, which must be securely destroyed.
• Use Case: Privacy coins like Zcash and zk-rollup scaling solutions on Ethereum.

A Zero-Knowledge Scalable Transparent Argument of Knowledge eliminates the need for a trusted setup by relying on collision-resistant hash functions and public randomness.

• Transparency: No toxic waste; security relies purely on cryptographic hash functions like SHA-256.
• Post-Quantum Security: Resistant to attacks from both classical and quantum computers.
• Trade-off: Proofs are significantly larger (tens to hundreds of kilobytes) than SNARKs but offer faster proving times for complex computations.

A proof system where the prover generates a single message that any verifier can check independently, without real-time communication. This is essential for blockchain and asynchronous systems.

• Fiat-Shamir Heuristic: Transforms interactive protocols into non-interactive ones by replacing the verifier's random challenges with the output of a cryptographic hash function.
• Public Verifiability: Once generated, the proof can be verified by anyone, anywhere, at any time, enabling decentralized validation.

A technique where a ZKP attests to the validity of one or more previous proofs, enabling proof aggregation and unbounded computational compression.

• Infinite Scaling: A single proof can verify that an entire chain of previous proofs was correctly generated.
• IVC (Incrementally Verifiable Computation): A specific form of recursion where a proof attests to the correct execution of a step and the validity of the previous step's proof.
• Application: Enables zk-rollups to batch thousands of transactions into a single constant-size proof for settlement on a Layer 1 blockchain.

A sub-protocol where the prover first cryptographically commits to a witness using a hiding and binding scheme, then proves statements about the committed value without revealing it.

• Binding: The prover cannot change the witness after committing.
• Hiding: The verifier learns nothing about the witness from the commitment alone.
• Pedersen Commitments: A common homomorphic commitment scheme used in ZKP constructions, allowing linear operations on committed values.