Zcash ZEC to $100 in 2023: battle for After-Life Privacy cryptoRecursive Proof Composition without a Trusted
Setup
Sean Bowe1
, Jack Grigg1
, and Daira Hopwood1
1 Electric Coin Company
{sean,jack,daira}@electriccoin.co
electriccoin.co
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.
Keywords: recursive proofs · incrementally verifiable computation ·
zero knowledge