TLDR:
 Sonic is a universal zkSNARK scheme, which makes applications launchable without running a separate trusted setup
 Sonic supports a universal and continually updatable structured reference string that scales linearly in supported circuit size.
Core Research Question
Given that zeroknowledge applications require a trusted setup, which adds significant costs to builds and iterations, how can we design an efficient zkSNARK scheme and use it universally?
Citation
 Groth, Jens. “On the Size of PairingBased NonInteractive Arguments.” Advances in Cryptology – EUROCRYPT 2016, edited by Marc Fischlin and JeanSébastien Coron, vol. 9666, Springer Berlin Heidelberg, 2016, pp. 305–26. DOI.org (Crossref), https://doi.org/10.1007/9783662498965_11.
 Bunz, Benedikt, et al. “Bulletproofs: Short Proofs for Confidential Transactions and More.” 2018 IEEE Symposium on Security and Privacy (SP), IEEE, 2018, pp. 315–34. DOI.org (Crossref), https://doi.org/10.1109/SP.2018.00020.
 Groth, Jens, et al. “Updatable and Universal Common Reference Strings with Applications to ZkSNARKs.” Advances in Cryptology – CRYPTO 2018, edited by Hovav Shacham and Alexandra Boldyreva, vol. 10993, Springer International Publishing, 2018, pp. 698–728. DOI.org (Crossref), https://doi.org/10.1007/9783319968780_24.
 Bootle, Jonathan, et al. “Efficient ZeroKnowledge Arguments for Arithmetic Circuits in the Discrete Log Setting.” Advances in Cryptology – EUROCRYPT 2016, edited by Marc Fischlin and JeanSébastien Coron, vol. 9666, Springer Berlin Heidelberg, 2016, pp. 327–57. DOI.org (Crossref), https://doi.org/10.1007/9783662498965_12.
 Kate, Aniket, et al. “ConstantSize Commitments to Polynomials and Their Applications.” Advances in Cryptology  ASIACRYPT 2010, edited by Masayuki Abe, vol. 6477, Springer Berlin Heidelberg, 2010, pp. 177–94. DOI.org (Crossref), https://doi.org/10.1007/9783642173738_11.
 Fuchsbauer, Georg, et al. “The Algebraic Group Model and Its Applications.” Advances in Cryptology – CRYPTO 2018, edited by Hovav Shacham and Alexandra Boldyreva, vol. 10992, Springer International Publishing, 2018, pp. 33–62. DOI.org (Crossref), https://doi.org/10.1007/9783319968810_2.
 Bellare, Mihir, et al. “NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion.” Advances in Cryptology – ASIACRYPT 2016, edited by Jung Hee Cheon and Tsuyoshi Takagi, vol. 10032, Springer Berlin Heidelberg, 2016, pp. 777–804. DOI.org (Crossref), https://doi.org/10.1007/9783662538906_26.
 Lindell, Yehuda. “Parallel cointossing and constantround secure twoparty computation.” Journal of Cryptology 16.3 (2003).
Link
Sonic: ZeroKnowledge SNARKs from LinearSize Universal and Updatable Structured Reference Strings
Background
Most zkSNARKs require a trusted setup. A setup can only be used once, thus different applications and versions require a new setup each time. These setups are costly, they take a long time and need multiple people to participate. However, Groth [1] demonstrated an efficient scheme (known as Groth 16) which contains only three group elements. There are also proving systems that work without a trusted setup such as BulletProofs (Bunz et al. [2]), but BulletProofs verification time scales linearly. Therefore those systems are better suited to simpler applications.
Groth et al. [3] have proposed a zkSNARK scheme with a universal and updatable structured reference string (SRS, the outcome of the trusted setup in (some) zkSNARK schemes construction). This universal property makes its setup not applicationspecific and the updatable property increases the confidence of the setup. However, this scheme requires an SRS that is quadratic with respect to the number of multiplication gates in the supported arithmetic circuits, a quadratic number of group exponentiations for verifying, and a linear number of pairings for updating SRS. Besides, deriving circuitspecific strings requires an expensive Gaussian elimination process.
In this work, Sonic introduces a new scheme based on Groth et al. [3] with a lot of efficiency improvements.
Summary
Introduction
 Sonic is a new zkSNARK that still needs a trusted setup, but the setup can be used in different circuits (applications) without being preprocessed and can be updated. These two features make Sonic more applicable and reliable(trustable) for the industry.
 It also brings better efficiency by making the proof elements in the same group to reduce pairing operations, introducing a method for verifying correct evaluation, and introducing a method to speed up the verifier by outsourcing some operations in batching to untrusted helper parties.
 Sonic defines its constraint system with respect to the twovariate polynomial equation used in Bulletproofs that was designed by Bootle et al. [4].
 The polynomial determined by the instance of the language can be split into monomials scaled by each element of the instance.
 Groth et al. [3] showed that an SRS that contains monomials is updatable.
 SRS is used to derive the instance of the language and the polynomial determined by the constraints is known to the verifier, thus no constraintspecific secrets were put in the SRS
 Sonic uses a variation of PCS by Kate et al. [5] (known as Kate Commitments)
 The authors prove it’s secure in the AGM (Fuchsbauer et al. [6]) as this work needs to use twovariate polynomials while Kate Commitments are designed for a singlevariate polynomial and this work needed another feature that an adversary can extract the committed polynomials from.
 If the prover and the verifier both know a twovariate polynomial that the verifier wants to calculate, the work can be unloaded onto the prover.
 Sonic unloads the work of computing the polynomial specifying the constraints onto the prover.
 There are two ways of achieving this. One provides a proof of evaluation correctness from each prover, the other introduces a role “helper” who calculates the circuitspecifying polynomial for each proof in the former way (batching)
Definitions for Updatable Reference Strings
 The subvertible and updatable SRS model
 “Subvertible” means that it’s secure when the parameters are maliciously generated at setup (Bellare et al. [7]).
 “Updatable” means that it’s secure when the adversary maliciously performs some update (Groth et al. [3])
 It’s defined by two Probabilistic Polynomial Time (PPT) algorithms,
Setup
andUpdate
, and one deterministic Polynomial Time (DPT) algorithm,VerifySRS
.
Setup
: takes a security parameter and returns an SRS and proof of its correctness 
Update
: takes a security parameter, an SRS, and update proofs and returns an updated SRS and a proof of the correctness of updates 
VerifySRS
: takes same inputs as Update and returns a bit indicating acceptance or rejection

 Bellare et al. [7] described that a protocol cannot satisfy both subvertible zeroknowledge and subvertible soundness
 Sonic preserves the subvertible zeroknowledge and provides update knowledge soundness, which means if an adversary has all randomness used in setup and update, the adversary can create a valid proof with invalid inputs
 To prove Sonic provides update knowledge soundness, it uses a technique here called “witnessextended emulation” with respect to Lindell [8]
Method
In this summary, we will walk through the protocol and provide context for the techniques used in each steps.
PreProcessing
In the preprocessing session, the prover will construct polynomials from constraints. Note that it’s not a Trusted Setup.
System of Constraints
Sonic represents circuits using a form of constraint system proposed by Bootle et al. [4]. In brief, there will be 4 polynomials:
 r(X, Y): constructed by provers with their hidden witness, designed that r(X, Y) = r(XY, 1) by protocol
 s(X, Y): signature of correct computation, constructed from constraints only
 t(X, Y) = r(X, 1)r'(X, Y)  k(Y): constant term of it is designed to be zero when the constraint system is satisfied, r'(X, Y) stands for r(X, Y) + s(X, Y) and we will use it later.
 k(Y): which is used to upload instance k into constraint system
The X and Y are indeterminates.
Protocol
Here Sonic will represent an interactive protocol that can be turned into noninteractive with the FiatShamir transformation. Refer to the original paper chapter 6 for details.
n is the number of gates and d is some number large enough (actually, 3n < d). x \xleftarrow{\$} S denotes sampling a member uniformly from S and assigning it to x.
Inputs
 Common Inputs: a bilinear group, an SRS, s(X, Y), k(Y), a paring function e(g, h^\alpha)
 Prover’s Inputs (witness): a, b, c
Steps
 As the prover and the simulator will evaluate g^{r(x,1)}, r(z,1), and r(zy, 1), the prover first extends r(X, Y) with 4 blinders to make them indistinguishable from each other and commits to r(X, 1) (extended).
 The verifier sends a random challenge y and the prover replies the commitment t(X, y), which has no constant term as mentioned above.
 The verifier sends another random challenge z and the prover opens the committed polynomials to r(z, 1), r(z, y), t(z, y)
 The verifier computes r'(z, y) = r(z, y) + s(z, y) (the prover or a helper can provide it with a signature of correct computation) and check r(z, y)r'(z, y)  k(y) = t(z, y)
Signatures of Correct Computation
Sonic uses a signature of correct computation to ensure that an element s is equal to s(z, y). The polynomial s(X, Y) is designed to be able to apply permutation. Then, the verifier’s computational costs at step 4 are offloaded to the prover or a helper. The permutation can be reused between instances by generating a derived reference string.
The helper will join protocol when available and there is a sufficiently large number of proofs in the batch. The idea is the helper commits to s(X,y_j) for each element y_j, and opens at s(z_j,y_j). The verifier will challenge it and be convinced that all the signatures are correct, thus the proof size is reduced. That is to say, instead of sending and verifying proofs of s(z,y) for each input, the helped version sends a proof of correctness of those proofs.
Result
Sonic is a competitive zkSNARKs, it has an efficient performance and is universal and updatable.
Proving Knowledge of Preimage
The authors implemented the helped version and obtained the following table by using BLS12381 elliptic curve construction on CPU i7 2600K with 32GB RAM, running at 3.4GHz.
Asymptotic efficiency comparison of zeroknowledge proofs for arithmetic circuits
The following table shows the comparison with related works. As Sonic can be considered as an evolution of Groth et al. [3] (Groth et al. [46] in the table), the major differences are 1) CRS is shorter 2) use the AGM (Fuchsbauer et al. [6]) assumption which could be considered less secure.
Comparison against a pairingbased zkSNARK and against Bulletproofs
Discussion and Key Takeaways
 Traditional zkSNARKs need a trusted setup for a circuit (application). By introducing universal SRS, we can now construct it once and use it in circuits under a limitation on the number of gates and depth of the setup.
 By making the SRS updatable, the confidence of security is increased, as any one of the participants destroys zir waste, the adversary won’t be able to cheat.
Implications and Followups
 Sonic introduces a new zkSNARK scheme that can solve the problem of trusted setup, making developers easier to build and iterate zk apps.
 This work might be considered as a milestone that inspired PlonK, RedShift, Marlin, Halo, and so on. Those zkSNRAKs are applied to many systems now, and many other universal zkSNARK works.
Applicability
 It seems no application directly uses Sonic, however, this work brings the applicability of zkSNARKs to the next level.