TL;DR
This paper introduces Pantry, a system that enables clients to verifiably outsource computations involving state (like RAM or disk access) to untrusted cloud providers. Pantry achieves this by extending existing proof-based verifiable computation techniques to handle state, making it practical for real-world applications like MapReduce and databases.
What Problem Does This Paper Address?
When a client outsources a computation to a third party, especially in the cloud, a critical question arises: how can the client be sure the result is correct without re-executing the entire computation? Existing solutions for "verifiable computation" have made significant progress, but they typically operate in a "stateless" model. This means they exclude computations that interact with memory (RAM), disk storage, or require the client to have the full input data. This limitation severely restricts their applicability to many real-world scenarios, such as large-scale data processing (MapReduce), database queries, and applications that rely on persistent state. The authors aim to bridge this gap by enabling verifiable computation for stateful tasks.
Methods
Pantry's core innovation lies in its ability to integrate verifiable computation with untrusted storage. The key techniques include:
- Storage Abstraction with Verifiable Blocks: Pantry introduces two primitives,
PutBlockandGetBlock, that allow computations to interact with storage. These primitives name data blocks using cryptographic hashes of their contents. This allows the client to express computations in terms of these hashes, and the prover (the cloud provider) must provide proofs that its interactions with storage are consistent with these hashes. - Constraint-Based Computation: Like its predecessors, Pantry compiles computations into a system of algebraic constraints. The prover then generates a satisfying assignment to these constraints, which serves as a proof of correct execution.
- Composition with Existing Verifiable Computation Frameworks: Pantry builds upon existing systems like Zaatar and Pinocchio, which provide the underlying machinery for generating and verifying proofs of computation.
- Higher-Level Abstractions: Pantry uses its storage primitives to build verifiable RAM, searchable trees, and a simple database that supports verifiable queries. This allows programmers to work with these familiar abstractions while still benefiting from verifiable computation.
- Zero-Knowledge Variant for Private State: By leveraging a zero-knowledge variant of Pinocchio, Pantry enables applications where the prover's state remains private from the verifier, such as face matching or toll collection.
Datasets
Not discussed in the paper. The paper focuses on evaluating the performance of Pantry on various computational tasks and applications rather than training on specific datasets.
Key Insights and Ideas
- State is Not an Obstacle to Verifiability: The paper demonstrates that stateful computations can be made verifiable without sacrificing the core guarantees of proof-based verifiable computation. This is a significant step beyond previous stateless models.
- Cryptographic Hashes as Verifiable Pointers: Using hashes of data blocks as names and references is a powerful way to authenticate data and enable verifiable interactions with storage. This leverages the collision-resistance of hash functions.
- Efficiency Gains Through Verifier Offloading: By having the verifier only deal with digests (hashes) of data rather than the full data itself, Pantry can significantly reduce the verifier's CPU and network costs, especially for large datasets. This allows the verifier to save resources compared to naive re-execution, even when the computation is linear.
- Amortization is Key: The per-instance costs for the verifier can be high. However, for applications with many instances (like MapReduce jobs), these costs can be amortized, making verifiable computation economically viable.
Key Results
- Pantry enables verifiable MapReduce jobs, database queries, and interactions with private state. This significantly expands the scope of applications for verifiable computation.
- Performance improvements: While prover overhead remains high, Pantry offers advantages for the verifier. For MapReduce, the verifier can save CPU and network costs when the job size is sufficiently large, allowing it to "beat naive verification" in certain scenarios.
- Verifiable RAM and databases: Pantry successfully implements these higher-level abstractions, demonstrating the practicality of its approach.
- Private state applications: Pantry, with the help of Pinocchio's zero-knowledge variant, can handle computations where the prover's state is private, opening up new possibilities for secure cloud services.
Limitations and Future Work
- High Prover Overhead: The prover's overhead is still tremendous, and the verifier's setup costs are significant, limiting the scale of current experiments.
- Constraint Model Clumsiness: The underlying constraint formalism imposes limitations, such as fixed loop bounds and static data structure sizes.
- Durability and Availability: Pantry does not formally enforce durability (malicious provers could discard blocks) or availability (provers could refuse to engage).
- Future Work: The authors suggest reducing argument protocol overhead, improving memory operation efficiency within the constraint model, and exploring alternatives to the constraint model. They also mention the need to handle multiple writers and to compare Pantry with other emerging approaches like BCGTV.
Summary updated