Zero-Knowledge Proof (ZKP)

If the statement is true and both the prover and verifier follow the protocol correctly, the verifier will be convinced. This ensures the proof system is functional for valid claims.

• Formal Guarantee: A correct proof for a true statement always results in acceptance.
• Reliability: The foundation for any useful ZKP, ensuring honest provers can always succeed.

If the statement is false, no cheating prover can convince an honest verifier that it is true, except with a negligible probability. This protects the verifier from accepting false claims.

• Security Guarantee: Makes it computationally infeasible to forge a proof for an invalid statement.
• Statistical vs. Computational: Soundness can be statistical (holds against any prover) or computational (holds against efficient, polynomial-time provers).

The verifier learns nothing about the witness (the secret information proving the statement) beyond the fact that the statement is true. This is the defining privacy property.

• Simulation Paradigm: Anything the verifier can compute after the proof, it could have computed without it, using only the public statement.
• Perfect, Statistical, Computational: Zero-knowledge can be perfect (no information leak), statistical (negligible leak), or computational (leak is infeasible to extract).

The proof size is small and the verification time is fast, typically much shorter than the computation being proven. This is a key feature of zk-SNARKs (Succinct Non-interactive ARguments of Knowledge).

• Efficient Verification: Enables verification of complex computations (e.g., blockchain state transitions) in milliseconds.
• Scalability: Critical for blockchain rollups where proofs are posted on-chain for cheap verification.

The proof consists of a single message from the prover to the verifier, requiring no back-and-forth interaction. This is enabled by a trusted setup (in zk-SNARKs) or different constructions (like zk-STARKs).

• Broadcastability: A non-interactive proof can be published (e.g., on a blockchain) and verified by anyone, anytime.
• Trusted Setup: Some systems (zk-SNARKs) require a one-time, ceremony-generated common reference string (CRS).

The prover not only proves a statement is true but also demonstrates they possess specific secret knowledge (the witness) that makes it true. This is the "Knowledge" part of zk-SNARK/STARK.

• Witness Extraction: Formally, there exists an "extractor" algorithm that can output the witness by interacting with a successful prover.
• Application: Essential for proving possession of a secret key, the pre-image of a hash, or a valid transaction signature without revealing it.

zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) are a class of ZKPs characterized by their small proof size and fast verification. They require a trusted setup ceremony to generate public parameters and are non-interactive, meaning the proof can be verified without further communication with the prover.

• Key Features: Succinct proofs, non-interactive verification.
• Common Use: Privacy and scalability in blockchains (e.g., Zcash, early versions of Tornado Cash).
• Trade-off: Requires a one-time, trusted setup.

zk-STARKs (Zero-Knowledge Scalable Transparent Argument of Knowledge) are ZKPs designed to be transparent, meaning they do not require a trusted setup. They offer post-quantum security and scalability, with proof size and verification time growing polylogarithmically with the computation size.

• Key Features: Transparent (no trusted setup), post-quantum secure, scalable.
• Common Use: High-throughput blockchain scaling (e.g., StarkNet, StarkEx).
• Trade-off: Larger proof sizes compared to SNARKs.

Bulletproofs are short, non-interactive zero-knowledge proofs that do not require a trusted setup. They are particularly efficient for proving statements about Pedersen commitments, such as range proofs (e.g., proving a committed value is within a certain range without revealing it).

• Key Features: No trusted setup, short proofs for specific statements.
• Common Use: Confidential transactions and range proofs (e.g., Monero, Mimblewimble).
• Trade-off: Verification can be computationally intensive for complex circuits.

PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge) is a universal and updatable SNARK construction. Its 'universal' trusted setup can be reused for any program up to a certain size, and it can be updated by adding new participants, enhancing security.

• Key Features: Universal & updatable trusted setup, efficient for general circuits.
• Common Use: A foundational proof system used by multiple blockchain scaling projects (e.g., Aztec, ZKSync Era).
• Trade-off: Still requires an initial trusted setup ceremony.

Interactive Proofs require multiple rounds of communication between the prover and verifier to convince the verifier of a statement's truth. They are a foundational concept for all ZKPs, though many modern systems (like SNARKs and STARKs) compile them into non-interactive versions using the Fiat-Shamir heuristic.

• Key Features: Multiple communication rounds, foundational theory.
• Common Use: Theoretical basis and protocol design; used directly in some identification schemes.
• Trade-off: Not succinct; requires ongoing interaction.

A critical distinction in ZKP systems is between a proof of knowledge and an argument of knowledge. A proof of knowledge provides unconditional (information-theoretic) security against an unbounded prover. An argument of knowledge provides computational security, assuming the prover's computational power is bounded (e.g., by cryptographic assumptions like collision-resistant hashes).

• Proof of Knowledge: Information-theoretic security. Example: Some STARK components.
• Argument of Knowledge: Computational security. Example: SNARKs, Bulletproofs.
• Implication: This affects the underlying security model and assumptions.

ZKPs allow users to prove attributes (e.g., age, citizenship, membership) without exposing the underlying credential or identity document. This enables self-sovereign identity and compliant access. Use cases include:

• Proof of Humanity: Verifying unique personhood anonymously.
• Selective Disclosure: Proving you are over 18 without revealing your birth date.
• Sybil Resistance: Preventing duplicate accounts in governance systems.

Institutions can use ZKPs to prove regulatory compliance without exposing sensitive commercial data. This bridges privacy and auditability. Applications include:

• Proof of Solvency: Exchanges prove they hold sufficient reserves to cover liabilities without revealing total assets.
• AML/KYC Checks: Proving a user is screened without leaking their personal data.
• Transaction Sanctions Screening: Demonstrating no transactions involve blacklisted addresses.

ZKPs enable trust-minimized bridging by proving state or ownership on another chain. A light client can verify a ZKP about a foreign chain's state faster than downloading all headers. This is used in:

• ZK Light Clients: Efficiently verifying consensus of another blockchain.
• Bridges like zkBridge: Using validity proofs to transfer assets or messages between chains.
• Omnichain Interoperability: Proving asset ownership across multiple ecosystems.

ZKPs can verify that off-chain data (e.g., from an oracle) was computed correctly according to a known algorithm, without revealing the raw data. This enhances trust in oracle networks. Examples include:

• Proof of Data Integrity: Proving a price feed is the median of specific sources.
• Private Computation Oracles: Using ZKPs to deliver the result of a private computation (e.g., a credit score) without exposing inputs.

Succinct Non-Interactive Argument of Knowledge is a type of ZKP characterized by small proof sizes and fast verification. It requires a trusted setup ceremony to generate public parameters but is highly efficient for blockchain scaling.

• Key Feature: Proofs are only a few hundred bytes and verify in milliseconds.
• Use Case: The backbone of ZK-Rollups like zkSync and privacy protocols like Zcash.

Scalable Transparent Argument of Knowledge is a ZKP variant that provides post-quantum security and does not require a trusted setup. STARK proofs are larger than SNARKs but scale more efficiently with computational complexity.

• Key Feature: Transparency and quantum-resistance, with verification time growing polylogarithmically with the computation size.
• Use Case: Employed by StarkNet for scalable, transparent L2 solutions.

A Layer 2 scaling solution that batches thousands of transactions off-chain, generates a ZK validity proof (SNARK/STARK), and posts it to the base layer (e.g., Ethereum). This ensures the same security as L1 while drastically increasing throughput and reducing costs.

• Mechanism: State transitions are proven correct, not re-executed.
• Example: zkSync, StarkNet, and Polygon zkEVM.

A one-time ceremony where participants generate the common reference string (CRS) or public parameters required for certain ZK systems (like SNARKs). If the ceremony is compromised, false proofs can be created.

• Powers of Tau: A common multi-party computation (MPC) protocol for secure setup.
• Transparent Alternative: STARKs and Bulletproofs eliminate this requirement.

A Zero-Knowledge Ethereum Virtual Machine that executes smart contracts compatibly with Ethereum, while generating ZK proofs of the correctness of its execution. It allows developers to deploy existing Ethereum smart contracts with minimal changes.

• Goal: Achieve EVM equivalence for seamless developer experience.
• Types: Range from language compatibility to full bytecode-level equivalence.

A universal and updatable SNARK construction. Its 'universal' trusted setup can be used for any program up to a certain size, and the setup can be securely updated by new participants, reducing ceremony overhead.

• Advantage: Simplifies application development with a single, reusable setup.
• Adoption: Widely used in protocols like Aztec Network and various ZK-Rollups.