Theorem Proving

A domain-specific language (DSL) and compiler for constructing arithmetic circuits, which are the fundamental building blocks for zk-SNARKs. Developers write circuit logic in Circom, which is then compiled into R1CS constraints for proof generation.

• Primary Use: Circuit design for zk-SNARKs.
• Key Feature: Generates Solidity verifiers for Ethereum.
• Ecosystem: Part of the iden3 toolkit, widely used for applications like Tornado Cash.

A proving system and framework developed by the Electric Coin Company (creators of Zcash). It introduced recursive proof composition without a trusted setup and uses PLONKish arithmetization for flexible circuit design.

• Core Innovation: Enables efficient proof recursion for incremental verifiable computation.
• Application: Powers the zero-knowledge scalability of Zcash and other L2s.
• Backend: Often used with the KZG polynomial commitment scheme.

A highly efficient zk-SNARK construction known for its small proof sizes and fast verification. It requires a per-circuit trusted setup, making it optimal for applications where a circuit is fixed.

• Proof Size: ~200 bytes.
• Verification Speed: Constant time, often sub-second on Ethereum.
• Limitation: The trusted setup is circuit-specific; any logic change requires a new ceremony.

A universal and updatable zk-SNARK protocol. Its major advantage is a universal and updatable trusted setup, meaning a single ceremony can support many different circuits and can be safely updated by new participants.

• Key Benefit: Reduces overhead compared to circuit-specific setups like Groth16.
• Flexibility: Uses a standardized constraint system for arithmetization.
• Adoption: A foundational protocol used by many zk-rollups.

A class of zero-knowledge proofs that are transparent (no trusted setup) and scale efficiently with large computations. They use hash-based cryptography (like Merkle trees) and rely on interactive oracle proofs (IOPs).

• Transparency: Eliminates the need for a trusted setup ceremony.
• Scalability: Prover time is quasi-linear; verification is poly-logarithmic.
• Trade-off: Proof sizes (tens of KBs) are larger than SNARKs but compress well.

A tool that generates proofs for general-purpose computation, typically by proving correct execution of a virtual machine (e.g., RISC-V, EVM). Instead of writing custom circuits, developers write standard code in languages like Rust or Solidity.

• Abstraction: Hides circuit complexity from developers.
• Examples: zkEVM (proves EVM execution), RISC Zero (proves RISC-V execution).
• Use Case: Enables general-purpose zk-rollups and verifiable off-chain computation.

Theorem proving is used to formally verify the correctness of smart contracts, proving they meet their specifications and are free from critical bugs. This is done by:

• Writing a formal specification of the contract's intended behavior.
• Using a proof assistant (like Coq or Isabelle) to construct a mathematical proof that the code matches the spec.
• This method is exhaustive, covering all possible execution paths, unlike testing which only samples them.
• Key projects using this include the Ethereum 2.0 deposit contract and CompCert (a verified C compiler).

zk-SNARKs and zk-STARKs are advanced cryptographic protocols that rely on theorem proving concepts. They allow one party to prove they know a secret or that a computation is correct without revealing the underlying data.

• The prover generates a proof for a statement (theorem).
• The verifier checks the proof's validity with minimal computation.
• This enables privacy-preserving applications like ZK-Rollups (scaling) and private transactions.
• Tools like Circom and ZoKrates are used to construct the arithmetic circuits that represent the statements to be proven.

Specialized languages and interactive tools form the core infrastructure for theorem proving in blockchain.

• Coq & Isabelle: General-purpose proof assistants used for verifying protocol designs and compiler correctness.
• Lean: Used for formalizing complex mathematics, with projects like formalizing the Ethereum Virtual Machine (EVM) semantics.
• Dafny & Why3: Languages that integrate specification and verification directly into the programming process.
• Viper: An intermediate verification language used by the Solidity compiler for automated reasoning about smart contracts.

Theorem proving is applied at the protocol layer to mathematically verify the security properties of consensus mechanisms and blockchain designs.

• It proves properties like safety (no two valid blocks conflict) and liveness (the chain eventually progresses).
• Used to verify the core algorithms of Proof-of-Stake systems, such as Casper FFG.
• The TLA+ specification language is often used to model and model-check distributed systems.
• This formal approach helps prevent critical, systemic failures that could compromise an entire network.

Automated Theorem Provers are software tools that attempt to prove mathematical theorems without human guidance for each step.

• They are used for SMT (Satisfiability Modulo Theories) solving, which checks the satisfiability of logical formulas.
• Key tools include Z3 (from Microsoft) and CVC5, which are integrated into blockchain analysis frameworks.
• They are used for symbolic execution and bounded model checking of smart contracts to find vulnerabilities automatically.
• ATPs provide a more automated, though sometimes less complete, alternative to interactive proof assistants.

Blockchain theorem proving draws heavily from established fields in computer science and mathematics.

• Type Theory: Provides the basis for languages like Coq and Agda, where proofs are constructed via rich type systems.
• Logic & Proof Theory: The study of formal proofs, their structure, and properties.
• Cryptography: Relies on proving the security of cryptographic constructions under specific assumptions.
• Program Verification: The general discipline of proving software correctness, with decades of research applied to blockchain's unique challenges.

A cryptographic protocol where one party (the prover) can prove to another (the verifier) that a statement is true without revealing any information beyond the validity of the statement itself. Theorem proving is the underlying logical foundation for constructing these proofs, ensuring the statements about secret data are mathematically sound.

• Types: Includes zk-SNARKs, zk-STARKs, and Bulletproofs.
• Use Case: Enables private transactions and scalable rollups by proving computational integrity.

The act of proving or disproving the correctness of a system's design with respect to a formal specification, using mathematical logic and automated theorem provers. In blockchain, it is used to verify smart contracts and consensus protocols are bug-free.

• Tools: Includes model checkers and interactive theorem provers like Coq and Isabelle.
• Goal: To provide absolute guarantees that code behaves as intended, eliminating vulnerabilities.

A protocol involving multiple rounds of communication between a computationally unbounded prover and a polynomial-time verifier. The prover convinces the verifier of a statement's truth. This is a foundational model for many zero-knowledge proof constructions.

• Key Property: The verifier can only be convinced by a true statement (soundness).
• Evolution: Non-interactive proofs (NIZKs) remove the need for live interaction, which is critical for blockchain.

A set of equations or inequalities that define the conditions a valid solution must satisfy. In zk-SNARKs, a computational program is compiled into an arithmetic circuit, which is then expressed as a rank-1 constraint system (R1CS). The theorem being proven is that a witness satisfies all these constraints.

• Role: Translates program execution into a format suitable for cryptographic proof generation.
• Example: Used in Zcash's Sapling protocol and various zk-rollups.

A type of zero-knowledge proof characterized by small proof size and fast verification. It relies on theorem proving to create a cryptographic proof that a statement is true. The 'succinct' property is vital for blockchain scalability.

• Components: Comprises a proving key, a verification key, and the short proof.
• Trust Setup: Often requires a trusted ceremony to generate initial parameters, a potential security consideration.

The guarantee that a computation was executed correctly according to a prescribed program. Theorem proving and zero-knowledge proofs are primary tools for achieving this. A verifier can be assured of integrity without re-executing the computation.

• Blockchain Application: Enables validity proofs for rollups, where off-chain computation is proven correct on-chain.
• Benefit: Allows for massive scalability by moving execution off the main chain while maintaining security.