Zero-Knowledge Proof (ZKP)

The protocol must always convince an honest verifier if the statement is true and the prover follows the rules.

• Mechanism: If the prover possesses a valid witness (the secret), the verifier's check will always pass.
• Analogy: A honest Sudoku champion can always prove they solved the puzzle without revealing the numbers.
• Failure Mode: A lack of completeness means a truthful prover cannot generate a valid proof, rendering the system useless for legitimate users.

A malicious prover cannot convince the verifier of a false statement, except with negligible probability.

• Mechanism: The protocol is mathematically structured so that a lying prover would need to solve a hard problem (e.g., breaking a hash function) to cheat.
• Knowledge Soundness: A stronger variant where an extractor algorithm can retrieve the witness from a successful prover, proving the prover actually knows the secret.
• Statistical vs. Computational: Soundness can be unconditional (statistical) or rely on computational hardness assumptions.

The verifier learns absolutely nothing beyond the validity of the statement. No information about the secret witness is leaked.

• Mechanism: A simulator can generate a transcript indistinguishable from a real interaction without knowing the secret, proving no knowledge is transferred.
• Perfect vs. Computational: Perfect ZK means the distributions are identical; computational ZK means they are indistinguishable to a bounded adversary.
• Example: Proving you know a password to a vault without revealing the password itself or any derivative that could be used to reconstruct it.

While not part of the classical definition, modern zk-SNARKs add a fourth critical property: the proof is extremely small and fast to verify.

• Constant Size: The proof size is often just a few hundred bytes, regardless of the complexity of the computation being proven.
• Sub-linear Verification: Verification time is logarithmic or constant relative to the computation size.
• Trade-off: This usually requires a trusted setup ceremony, which introduces a different security assumption.

Zero-Knowledge Succinct Non-Interactive Argument of Knowledge is the most widely deployed ZKP construction. It generates a tiny, constant-size proof that can be verified in milliseconds regardless of the computation's complexity. Requires a trusted setup ceremony to generate a Common Reference String (CRS); if the ceremony's toxic waste is not destroyed, false proofs can be forged. Used in privacy coins like Zcash and Ethereum Layer 2 scaling solutions.

Zero-Knowledge Scalable Transparent ARguments of Knowledge eliminate the trusted setup requirement entirely, relying on collision-resistant hash functions and public randomness. Proofs are larger than SNARKs but scale logarithmically with computation size, making them post-quantum secure. Ideal for high-throughput rollups where transparency and quantum resistance are prioritized over minimal proof size.

A non-interactive zero-knowledge proof protocol optimized for range proofs and short verification times without a trusted setup. Bulletproofs enable proving that a committed value lies within a specific range without revealing the value itself. Used extensively in confidential transactions for cryptocurrencies like Monero to hide transaction amounts while preventing inflation.

A cryptographic primitive allowing a prover to commit to a polynomial and later open evaluations at specific points without revealing the full polynomial. KZG commitments (based on bilinear pairings) provide constant-size proofs and are the engine behind many zk-SNARKs. FRI (Fast Reed-Solomon IOP of Proximity) offers a hash-based alternative with post-quantum security, used in STARKs.

A class of three-move interactive zero-knowledge proofs for specific algebraic relations such as knowledge of a discrete logarithm. Sigma protocols satisfy honest-verifier zero-knowledge and can be made non-interactive via the Fiat-Shamir heuristic by replacing the verifier's random challenge with a hash of the prover's commitment. They form the building blocks for anonymous credential systems and digital signatures.