Cryptology ePrint Archive: Report 2019/1021

Halo: Recursive Proof Composition without a Trusted Setup

Sean Bowe and Jack Grigg and Daira Hopwood

Abstract: Non-interactive proofs of knowledge allow us to publicly demonstrate the faithful execution of arbitrary computations. SNARKs have the additional property of succinctness, meaning that the proofs are short and fast to verify even when the computations involved are large. This property raises the prospect of recursive proof composition: proofs that verify other proofs. All previously known realizations of recursive proof composition have required a trusted setup and cycles of expensive pairing-friendly elliptic curves.

We obtain the first practical example of recursive proof composition without a trusted setup, using only ordinary cycles of elliptic curves. Our primary contribution is a novel technique for amortizing away expensive verification procedures from within the proof verification cycle so that we could obtain recursion using a composition of existing protocols and techniques. We devise a technique for amortizing the cost of verifying multiple inner product arguments which may be of independent interest.

Category / Keywords: cryptographic protocols / zero knowledge, elliptic curve cryptosystem

Date: received 10 Sep 2019

Contact author: sean at electriccoin co

Available format(s): PDF | BibTeX Citation

Version: 20190911:071840 (All versions of this report)

Short URL: ia.cr/2019/1021


[ Cryptology ePrint archive ]