Paper 2020/1618
Proof-Carrying Data without Succinct Arguments
Benedikt Bünz and Alessandro Chiesa and William Lin and Pratyush Mishra and Nicholas Spooner
Abstract
Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme for their proofs. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a *split accumulation scheme*, which is a weak form of accumulation that we introduce. We additionally construct a transparent non-interactive argument of knowledge for R1CS whose accumulation is verifiable via a *constant number of group and field operations*. This leads, via the random oracle heuristic and our result above, to efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- proof-carrying dataaccumulation schemesrecursive proof composition
- Contact author(s)
- benedikt @ cs stanford edu,alexch @ berkeley edu,pratyush @ berkeley edu,nspooner @ bu edu
- History
- 2021-12-01: last of 5 revisions
- 2020-12-31: received
- See all versions
- Short URL
- https://ia.cr/2020/1618
- License
-
CC BY