Cardano delivers yet another holy grail, this time for fungibility/privacy!!!
Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings
ABSTRACT
Zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in cryptocurrencies and other applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify.The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zk-SNARK scheme scan be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth etal. discovered a zk-SNARK protocol with a universal and updateable structured reference string, however the string scales quadratically in the size of the supported relations.Here we describe a zero-knowledge SNARK, Sonic, which sup-ports a universal and continually updateable structured reference string that scales linearly in size. Sonic proofs are constant size, and in the batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature.We also describe a generally useful technique in which untrusted “helpers” can compute advice which allows batches of proofs to be verified more efficiently.
Our Contributions
We present Sonic, a new zk-SNARK for general arithmetic circuit satisfiability. Sonic requires a trusted setup, but unlike conventional SNARKs the structured reference string supports all circuits (up to a given size bound) and is also updateable, so that it can be continually strengthened. This addresses many of the practical challenges and risks surrounding such setups. Sonic’s structured reference string grows linear in size with respect to the size of supported circuits,as opposed to the scheme by Groth et al. which scales quadratically. The structured reference string in Sonic also does not need to be specialized or pre-processed for a given circuit. This makes a large,distributed and never-ending setup process a practical reality.
CONCLUSIONS
Zero-knowledge protocols have gained significant traction in recent years in the application domain of cryptocurrencies, which has led to the development of new protocols with significant performance gains. At the same time, the requirements of this application have given rise to protocols with new features, such as an untrusted setup and a reference string that allows one to prove more than a single relation. In this paper, we present Sonic, which captures a valuable set of trade-offs between these key functional requirements of untrusted setup and universality. At the same time, as we demonstrate via a prototype implementation, Sonic has competitive proof sizes and verification time with the state-of-the-art.
tldr; Cardano fixed all the things that make Zcash shitty but kept the good stuff that makes Zcash marginally interesting