Pinocchio: nearly practical verifiable computation

Bryan Parno, Jon Howell, Craig Gentry, Mariana RaykovaCommunications of the ACM 2016 · DOI

TL;DR

This paper introduces Pinocchio, a system that allows clients to outsource computations to untrusted workers and verify the results efficiently and privately. Pinocchio achieves this by using a novel compiler and cryptographic protocol, resulting in proofs that are tiny (288 bytes) and verification times that are orders of magnitude faster than previous methods, making verifiable computation practical for a wider range of applications.

What Problem Does This Paper Address?

In today's world of cloud computing and distributed systems, clients often outsource computationally intensive tasks to powerful, but potentially untrusted, workers. The critical challenge is how a client, who might have limited resources, can reliably verify that the worker has performed the computation correctly and hasn't tampered with the results. Existing solutions either are:

  • Function-specific: Efficient but only work for a narrow class of computations.
  • Rely on strong assumptions: Like replicated failures or trusted hardware, which may not always be applicable.
  • Theoretically advanced but impractical: Protocols like Probabilistically Checkable Proofs (PCPs) or Fully Homomorphic Encryption (FHE) have prohibitive performance overheads, taking years to verify even small computations.

Pinocchio aims to bridge this gap by providing a general-purpose, efficient, and practical solution for verifiable computation that relies only on standard cryptographic assumptions.

Methods

Pinocchio's core innovation lies in its combination of a compiler and a new cryptographic protocol based on Quadratic Arithmetic Programs (QAPs).

  • Compiler (qcc): This Python program takes a subset of C code and transforms it into an arithmetic circuit representation. It handles common programming constructs like loops, arrays, and structs, ultimately generating an expression suitable for the cryptographic protocol.
  • Quadratic Arithmetic Programs (QAPs): Inspired by Gennaro et al.'s work, QAPs provide a way to compactly encode computations. Pinocchio uses a refined protocol that works with "regular" QAPs (instead of "strong" QAPs), significantly reducing the complexity and overhead of key generation and proof creation.
  • Efficient Cryptographic Protocol: Pinocchio introduces a new protocol that leverages QAPs and optimizations in polynomial operations and exponentiation. This protocol allows for:
  • Public Verifiable Computation: Anyone can verify the proof using a public verification key.
  • Zero-Knowledge Verifiable Computation: The worker can prove correctness without revealing the input, at a negligible additional cost.
  • Toolchain: The system includes an end-to-end toolchain that compiles C code, generates QAPs, and runs the cryptographic protocol for key generation, proof computation, and verification.

Datasets

Not discussed in the paper. The paper focuses on evaluating its system on various computational tasks rather than training on datasets.

Key Insights and Ideas

  • QAPs are the key: The paper demonstrates that by carefully designing a VC protocol around regular QAPs, significant performance improvements can be achieved compared to using strong QAPs, without sacrificing security.
  • Compiler is crucial for practicality: A compiler that translates from a widely used language like C to the cryptographic primitives is essential for making verifiable computation accessible to developers.
  • Tiny proofs are achievable: The constant-size proof (288 bytes) is a major breakthrough, making proofs easy to store and transmit.
  • Verification can be cheaper than execution: For certain applications and parameter settings, Pinocchio shows that verifying an outsourced computation can be faster than performing it locally, a critical threshold for adoption.
  • Zero-knowledge is nearly free: The ability to perform zero-knowledge proofs adds minimal overhead, opening up privacy-preserving applications.

Key Results

  • Proof Size: Pinocchio produces proofs that are a constant 288 bytes, regardless of the computation's complexity or input/output size.
  • Verification Time: Verification is extremely fast, typically around 10ms, which is 5-7 orders of magnitude faster than previous theoretical schemes. For some applications, verification is faster than native C execution.
  • Worker Proof Effort: Pinocchio reduces the worker's proof generation effort by 19-60× compared to prior work.
  • Key Generation: Key setup time is reduced by 61% compared to GGPR's scheme.
  • Zero-Knowledge Overhead: Adding zero-knowledge capabilities incurs only a negligible cost (213µs for key generation, 0.1% for proof generation).
  • Application Performance: The system was evaluated on seven real-world C applications, demonstrating its versatility. Three of these applications showed verification times cheaper than native execution.

Limitations and Future Work

  • C Subset: The compiler currently supports a subset of C, and extending it to handle floating-point values and more complex language features is a future direction.
  • Performance for Bitwise Operations: Applications heavily reliant on bitwise operations and inequality comparisons are less efficient with the current circuit-based representation.
  • Amortization: While Pinocchio significantly reduces per-instance costs, some applications still require a substantial number of instances to amortize setup costs and achieve break-even with native execution.
  • Future Work: The authors suggest further theoretical improvements, expanding the toolchain to support floating-point operations and parallel execution, and continuing to advance towards truly practical verifiable computing.

Summary updated

BibTeX
@article{parno2016pinocchio,
  author = {Bryan Parno and Jon Howell and Craig Gentry and Mariana Raykova},
  title = {{Pinocchio: nearly practical verifiable computation}},
  journal = {Communications of the ACM},
  year = {2016},
  doi = {10.1145/2856449},
}
Figure