### Recursive Proof Composition without a Trusted Setup

Sean Bowe, Jack Grigg, and Daira Hopwood

##### Abstract

Non-interactive arguments of knowledge are powerful cryptographic tools that can be used to demonstrate the faithful execution of arbitrary computations with publicly verifiable proofs. Increasingly efficient protocols have been described in recent years, with verification time and/or communication complexity that is sublinear in the size of the computation being described. These efficiencies can be exploited to realize recursive proof composition: the concept of proofs that attest to the correctness of other instances of themselves, thereby allowing large computational effort to be incrementally verified. All previously known realizations of recursive proof composition have required a trusted setup and cycles of expensive pairing-friendly elliptic curves. We obtain and implement Halo, the first practical example of recursive proof composition without a trusted setup, using the discrete log assumption over normal cycles of elliptic curves. In the process we develop several novel techniques that may be of independent interest.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
recursive proofsincrementally verifiable computationzero knowledge
Contact author(s)
sean @ electriccoin co
History
2020-02-18: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/1021

CC BY

BibTeX

@misc{cryptoeprint:2019/1021,
author = {Sean Bowe and Jack Grigg and Daira Hopwood},
title = {Recursive Proof Composition without a Trusted Setup},
howpublished = {Cryptology ePrint Archive, Paper 2019/1021},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1021}},
url = {https://eprint.iacr.org/2019/1021}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.