In this post, we discuss a new zk-SNARK, Sonic, developed by Mary Maller, Sean Bowe, Markulf Kohlweiss and Sarah Meiklejohn. Unlike other SNARKs, Sonic does not require a trusted setup for each circuit, but only a single setup for all circuits. Further, the setup for Sonic never has to end, so it can be continuously secured by accumulating more contributions. This property makes it ideal for any system where there is not a trusted party, and there is a need to validate data without leaking confidential information. For example, a company might wish to show solvency to an auditor without revealing which products they have invested in. The construction is highly practical.
More about zk-SNARKs
Like all other zero-knowledge proofs, zk-SNARKs are a tool used to build applications where users must prove the validity of their data, such as in verifiable computation or anonymous credentials. Additionally, zk-SNARKs have the smallest proof sizes and verifier time out of all other known techniques for building zero-knowledge proofs. However, they typically require a trusted setup process, introducing the possibility of fraudulent data being input by the actors that implemented the system. For example, Zcash uses zk-SNARKs to send private cryptocurrency transactions, and if their setup was compromised then a small number of users could generate an unlimited supply of currency without detection.
| Characteristics of zk-SNARKs |
|---|
| 🙂 Can be used to build many cryptographic protocols 🙂 Very small proof sizes 🙂 Very fast verifier time 😐 Average prover time ☹️ Requires a trusted setup ☹️ Security assumes non-standard cryptographic assumptions |
In 2018, Groth et al. introduced a zk-SNARK that could be built from an updatable and universal setup. We describe these properties below and claim that these properties help mitigate the security concerns around trusted setup. However, unlike Sonic, Groth et al.’s setup outputs a large set of global parameters (in the order of terabytes), which would be unwieldy to store, update and verify.
Updatability
Updatability means that any user, at any time, can update the parameters, including after the system goes live. After a single honest user has participated, no party can prove fraudulent data. This property means that a distrustful user could update the parameters themselves and have personal confidence in the parameters from that point forward. The update proofs are short and quick to verify.
Universality
Universality means that the same parameters can be used for any application using this zk-SNARK. Thus one can imagine including the global parameters in an open-source implementation, or one could use the same parameters for all smart contracts in Ethereum.
Why Use Sonic?
Sonic is universal, updatable, and has a small set of global parameters (in the order of megabytes). Proof sizes are small (256 bytes) and verifier time is competitive with the fastest zk-SNARKs in the literature. It is especially well suited to systems where the same zk-SNARK is run by many different provers and verified by many different parties. This is exactly the situation for many blockchain systems.
The advantage of Sonic over Groth et al.’s design is that Sonic uses a smaller set of global parameters. As a result, storing, updating, and verifying Sonic’s parameters could be achieved on a personal laptop. On the other hand, Groth et al.’s public parameters are expensive to store, update, and verify, to the extent that it would require a distributed set of computers to carry out these tasks. Also, to use Groth et al.’s zk-SNARK with a specific application, some party has to run an expensive (but untrusted) derivation process on the global parameters to obtain application-specific parameters. Sonic does not require any derivation process.
Compared to Bulletproofs (introduced by Bootle et al. and improved by Bünz et al. ), Sonic has a smaller proof size and much smaller verifier computation. The Bulletproof verifier requires a computation whose size depends on the size of the underlying application. Sonic, on the other hand, has a fixed-size verifier for any application. Bulletproofs do have a fully trustless setup whereas Sonic merely has a nearly trustless setup. Also, Bulletproofs base their security on more standard assumptions than Sonic. Overall Bulletproofs is better for smaller applications and Sonic is better for larger applications.
Sonic would be used in different applications to zk-STARKs. STARKs are feasibly postquantum secure and have a fully trustless setup, but have high concrete overhead. Even for modestly-sized applications, current STARK proof sizes are at least 40kB. This property makes them more suitable for applications where the STARK is run as a one-off cost and is less suitable for applications where multiple proofs for the same program run, stored and verified.
Techniques
Sonic describes its problem statements using the same techniques as Bulletproofs. It is built over pairing based groups and makes heavy use of a constant-sized polynomial commitment scheme by Kate et al.. It assumes two rounds of interaction between the prover and the verifier and is then made non-interactive in the random oracle model.
Sonic has two modes of operation, the “helper” mode, and the “unhelped” mode. The helper mode is simpler and more efficient but assumes the presence of untrusted third parties that aggregate a number of proofs together. The unhelped mode assumes neither batching or aggregation, however, is more expensive (estimated proof sizes over 256-bit groups is 1kb). For each proof, the Sonic verifier requires knowledge of the evaluation of a (sparse) polynomial s(z,y) for known polynomial s(X,Y). Computing this polynomial for themselves requires an undesirable level of work for the verifier, but a reasonable level of work for the prover or helper.
Helper Mode
The helper commits to a batch of proofs. They then calculate the verifiers’ polynomials and provide a short, easy to verify proof of the correct calculation. In the blockchain setting, they could be run by the miners. The miner who adds a block would be required to provide the help for all proofs in the block, and all other parties in the network could quickly verify the validity of this help.
Given m proofs, the helper runs in time proportional to m provers. The helpers’ proof sizes are small. Verifying the help requires a one-off calculation of the polynomial s(X,Y) at known points z,y and then a small computation per proof (this computation is independent of the size of the application).
Unhelped Mode
In the unhelped mode, the prover calculates the polynomial for the verifier and provides a short, easy to verify proof of the correct calculation. This mode is ideal for settings either where proofs cannot be batched or where there are no helpers available. While the proof size and verifier computation remain independent of the size of the computation, they are concretely several times larger than the proof size and the verifier computation of the helped proofs.
Further details
Further information on the construction can be found in our paper – Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings – available on the IACR ePrint Archive.