This repository accompanies the report "Investigating IVC with Accumulation Schemes". It explores the theoretical foundation of accumulation schemes and their application in Incrementally Verifiable Computation (IVC). While the Rust implementation included here serves as a concrete demonstration of the theory, the focus remains on the mathematical and cryptographic insights behind the constructions and benchmarking, not production-grade code.
The theory and code is mostly based on the 2020 paper "Proof-Carrying Data from Accumulation Schemes" by Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra, and Nicholas Spooner.
Accumulation schemes are cryptographic primitives that allow for the incremental verification of multiple computations or proofs. They enable efficient proof systems by cheaply "accumulating" intermediate results, which can then be checked in a single, possibly expensive, verification step.
These schemes are particularly relevant in IVC, where a sequence of computations or proofs needs to be verified succinctly. By using the accumulation scheme, benchmarking shows significant improvements over naive series of PCS checks.
The ASDL allows for an efficient IVC construction despite the linear runtime
of a full PCS check, by leveraging the succinct check in PCDL. This means
you can have verification that does not scale linearly with the number of
IVC steps, since the linear computation is only done at the end of the IVC
chain, not at each step. This means that, using a PCS based on Bulletproof's
Inner Product Argument, we can create an IVC construction that does not
depend on a trusted setup.
The report included in this repository covers:
-
Prerequisites and Cryptographic Background
- Proof Systems
- Fiat-Shamir heuristic
- SNARKs and Bulletproofs
-
Incrementally Verifiable Computation (IVC)
- Introduction to IVC and its applications
- An IVC construction using traditional SNARKS with sublinear verification
-
Polynomial Commitment Schemes (PCS)
- Theory behind PCS and their role in succinct proofs
-
Accumulation Schemes (AS)
- How accumulation schemes work
- Theoretical properties (completeness, soundness)
-
IVC Using Accumulation Schemes
- How accumulation schemes lead to new IVC constructions, without the need for a trusted setup
-
The Implementation
- Implementation details for
PCDL, with a completeness proof and a knowledge extractability discussion - Implementation details for
ASDL, with soundness and completeness proofs.
- Implementation details for
-
Efficiency and Benchmarking
- Comparison between naive PCS and accumulation schemes
- Preliminary benchmarking results showing promising results
The Rust code provides a concrete implementation of the described accumulation
scheme (ASDL) and polynomial commitment scheme (PCDL). While the
implementation is not designed for production use, it is a useful tool for
understanding the theory and experimenting with the concepts.
This project has nix support, as such, navigating to /code and typing
nix develop, will install the necessary rust version, with the correct
formatter and rust-analyzer included.
Unit tests can be run with cargo test in the /code directory.
Benchmarks can be run with cargo benchmark in the /code directory.
- Polynomial Commitment Scheme (
PCDL): Implements commitment, opening, and succinct checking. - Accumulation Scheme (
ASDL): Demonstrates the efficiency of accumulation-based verification. - Benchmarks: Includes preliminary performance comparisons between naive PCS usage and accumulation schemes.
The full report, "Investigating IVC with Accumulation Schemes", is included in this repository and provides a detailed explanation of the theory, constructions, and benchmarks.
This work is primarily intended for those interested in understanding the theory behind accumulation schemes and their application to IVC. Contributions or suggestions for improving the theoretical explanations are welcome.
This project is licensed under the MIT License. See the LICENSE file for details.