Zero-Knowledge Proof (ZKP)

If the statement is true and both the prover and verifier follow the protocol honestly, the verifier will always be convinced of the statement's validity.

• Honest-Verifier Guarantee: A legitimate prover possessing the secret witness will never fail to convince the verifier.
• Deterministic Acceptance: The probability of acceptance for a true statement is 1 (or negligibly close to 1 in probabilistic constructions).
• Example: In the classic Ali Baba cave scenario, if Peggy truly knows the secret password to open the magic door, she can always emerge from the correct path Victor specifies, proving knowledge without fail.

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

• Knowledge Extraction: A malicious prover without the witness cannot produce a valid proof, even with arbitrary computational resources (for statistical soundness).
• Computational Soundness: In practical systems like zk-SNARKs, soundness holds only against computationally bounded adversaries, relying on cryptographic hardness assumptions.
• Negligible Error: The probability of a false statement being accepted is bounded by a small value (e.g., 2^-128), often called the soundness error.

The verifier learns absolutely nothing beyond the single fact that the statement is true. No information about the secret witness is leaked during the interaction.

• Simulation Paradigm: Formally, for any verifier, there exists a simulator that can produce a transcript indistinguishable from a real interaction without access to the secret. This proves no knowledge is extracted.
• Perfect vs. Computational: Perfect zero-knowledge means the simulated and real distributions are identical. Computational zero-knowledge means they are computationally indistinguishable, which is sufficient for most practical applications.
• Example: Proving you know the preimage of a hash without revealing the preimage itself. The verifier confirms the hash matches but gains zero insight into the input value.

A stronger notion often bundled with ZKPs, requiring that the prover not only demonstrates a statement is true but also proves possession of the specific secret witness.

• Extractor Existence: There must exist an extractor algorithm that, given special access to the prover (e.g., rewinding), can efficiently extract the witness. This proves the prover actually 'knows' the secret.
• Distinction from Soundness: Soundness only guarantees the statement is true; proof of knowledge guarantees the prover holds the underlying witness. A statement can be true without the prover knowing why.
• Critical for Authentication: This property is essential for identity verification and credential systems, where proving possession of a private key is more important than proving a mathematical statement about the key.

A practical property of modern ZKP systems where the proof size is very small (often constant or logarithmic) and verification is exponentially faster than re-executing the computation.

• Constant-Size Proofs: zk-SNARKs produce proofs that are typically only a few hundred bytes, regardless of the complexity of the statement being proven.
• Sublinear Verification: The verifier's work is logarithmic or constant relative to the computation size, enabling verification on resource-constrained devices like mobile phones or on-chain smart contracts.
• Trade-off: Succinctness often requires a trusted setup ceremony (as in Groth16) or relies on newer transparent setups (as in zk-STARKs) that produce larger proofs but eliminate toxic waste concerns.

The entire proof consists of a single message from prover to verifier, eliminating the need for back-and-forth communication and enabling asynchronous verification.

• Fiat-Shamir Heuristic: Interactive protocols are transformed into non-interactive ones by replacing the verifier's random challenges with the output of a cryptographic hash function applied to the transcript so far.
• Public Verifiability: A non-interactive proof can be published and verified by anyone, anywhere, at any time, making it ideal for blockchain scalability and decentralized identity.
• NIZK: Non-Interactive Zero-Knowledge proofs are the standard for real-world deployments, where maintaining a live channel between prover and verifier is impractical.

A hash-based data structure where every leaf node is labeled with a cryptographic hash of a data block, and every non-leaf node is labeled with the hash of its child nodes. Merkle trees enable efficient and secure verification of content integrity without revealing the entire dataset.

• Forms the backbone of blockchain state verification
• Allows generation of compact Merkle proofs for inclusion checks
• Fundamental building block in many ZKP constructions like zk-SNARKs

Cryptographic methods for proving that a specific computation was executed correctly on a specific dataset without revealing the data itself. This extends ZKP principles to entire computational workflows.

• Enables auditable AI training on private data
• Combines ZKPs with homomorphic encryption in some architectures
• Critical for regulatory compliance in sensitive industries

A mathematical scheme using public-key cryptography to verify the authenticity and integrity of a digital message or document, providing non-repudiation of the signer. While ZKPs prove knowledge of a secret, digital signatures prove authorization of an action.

• Standardized in schemes like ECDSA and EdDSA
• ZKP-based signature schemes (e.g., Schnorr) offer additional privacy properties
• Foundational to all content attestation frameworks

A distributed database or record-keeping system where entries cannot be altered or deleted after they are committed, providing a permanent and auditable history of transactions. ZKPs enhance ledger privacy through zero-knowledge rollups.

• Enables zk-rollups that batch thousands of transactions into a single proof
• Provides verifiable audit trails without exposing sensitive details
• Used in supply chain provenance and regulatory compliance