Verifiable Computation

The guarantee that an honest prover can always convince an honest verifier that a correct computation was executed. If the prover follows the protocol and generates a valid output y from input x and program P, the verifier's check will always pass.

• Ensures the system works as designed under normal operation
• A fundamental requirement for any proof system to be usable
• Mathematically: If P(x) = y, then Verify(pk, x, y, π) = 1

The property that a malicious prover cannot convince a verifier to accept a false statement. A computationally bounded adversary has a negligible probability of generating a convincing proof for an incorrect output y' where y' ≠ P(x).

• Computational soundness: Security against polynomial-time adversaries (SNARKs)
• Statistical soundness: Unconditional security regardless of computational power (STARKs)
• Typically quantified as a soundness error of 2^-λ for security parameter λ

The proof size and verification time must be sublinear in the size of the computation being verified. Ideally, the proof is constant-size (a few hundred bytes) and verification takes logarithmic or constant time regardless of the computation's complexity.

• Enables verification on resource-constrained devices like phones or blockchains
• A ZK-SNARK proof for an arbitrary computation is typically ~200-300 bytes
• Verification time measured in milliseconds, not proportional to computation length

An additional privacy property where the proof reveals nothing beyond the validity of the statement. The verifier learns that P(x) = y is correct but gains zero information about the witness w (which may include private inputs or proprietary model weights).

• Critical for zkML where model weights remain confidential
• Enables private transactions in blockchain systems
• Achieved through randomized proof generation that simulates without the witness
• Not all verifiable computation systems require this property

The proof generation and verification occur in a single round without back-and-forth communication between prover and verifier. The prover generates a proof π and the verifier checks it independently.

• Enabled by the Fiat-Shamir heuristic which replaces verifier challenges with a random oracle (hash function)
• Essential for blockchain deployment where verifiers are anonymous and asynchronous
• Allows proofs to be publicly verifiable by anyone, anytime
• Contrasts with interactive proof systems requiring multiple rounds

Anyone with access to the verification key and the proof can independently verify correctness without needing to interact with or trust the prover. This enables decentralized verification across trustless networks.

• Proofs can be posted on-chain for any observer to validate
• No reliance on a trusted third party or centralized verification service
• Critical for decentralized oracle networks and cross-chain bridges
• Enables auditable AI inference where model outputs carry cryptographic proof