Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / proof-carrying data; accumulation schemes; recursive proof composition

Date: received 31 Dec 2020

Contact author: benedikt at cs stanford edu,alexch@berkeley edu,pratyush@berkeley edu,nspooner@bu edu

Available format(s): PDF | BibTeX Citation

Version: 20201231:095317 (All versions of this report)

Short URL: ia.cr/2020/1618