Research Summary: Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings

Cryptography
1

TLDR:

  • Sonic is a universal zk-SNARK 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 zero-knowledge applications require a trusted setup, which adds significant costs to builds and iterations, how can we design an efficient zk-SNARK scheme and use it universally?

Citation

  1. Groth, Jens. “On the Size of Pairing-Based Non-Interactive Arguments.” Advances in Cryptology – EUROCRYPT 2016, edited by Marc Fischlin and Jean-Sébastien Coron, vol. 9666, Springer Berlin Heidelberg, 2016, pp. 305–26. DOI.org (Crossref), https://doi.org/10.1007/978-3-662-49896-5_11.
  2. 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.
  3. Groth, Jens, et al. “Updatable and Universal Common Reference Strings with Applications to Zk-SNARKs.” 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/978-3-319-96878-0_24.
  4. Bootle, Jonathan, et al. “Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting.” Advances in Cryptology – EUROCRYPT 2016, edited by Marc Fischlin and Jean-Sébastien Coron, vol. 9666, Springer Berlin Heidelberg, 2016, pp. 327–57. DOI.org (Crossref), https://doi.org/10.1007/978-3-662-49896-5_12.
  5. Kate, Aniket, et al. “Constant-Size 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/978-3-642-17373-8_11.
  6. 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/978-3-319-96881-0_2.
  7. 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/978-3-662-53890-6_26.
  8. Lindell, Yehuda. “Parallel coin-tossing and constant-round secure two-party computation.” Journal of Cryptology 16.3 (2003).

Link

Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings

Background

Most zk-SNARKs 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 zk-SNARK scheme with a universal and updatable structured reference string (SRS, the outcome of the trusted setup in (some) zk-SNARK schemes construction). This universal property makes its setup not application-specific 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 circuit-specific 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 zk-SNARK that still needs a trusted setup, but the setup can be used in different circuits (applications) without being pre-processed 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 two-variate 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 constraint-specific 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 two-variate polynomials while Kate Commitments are designed for a single-variate 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 two-variate 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 circuit-specifying 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 and Update, 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 zero-knowledge and subvertible soundness
      • Sonic preserves the subvertible zero-knowledge 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 “witness-extended 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.

Pre-Processing

In the pre-processing session, the prover will construct polynomials from constraints. Note that it’s not a Trusted Setup.

814×384 23.5 KB

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:

  1. r(X, Y): constructed by provers with their hidden witness, designed that r(X, Y) = r(XY, 1) by protocol
  2. s(X, Y): signature of correct computation, constructed from constraints only
  3. 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.
  4. 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 non-interactive with the Fiat-Shamir transformation. Refer to the original paper chapter 6 for details.

1820×854 78.6 KB

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

  1. 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).
  2. The verifier sends a random challenge y and the prover replies the commitment t(X, y), which has no constant term as mentioned above.
  3. The verifier sends another random challenge z and the prover opens the committed polynomials to r(z, 1), r(z, y), t(z, y)
  4. 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 zk-SNARKs, 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 BLS12-381 elliptic curve construction on CPU i7 2600K with 32GB RAM, running at 3.4GHz.

1240×427 77 KB

Asymptotic efficiency comparison of zero-knowledge 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.

953×437 142 KB

Comparison against a pairing-based zk-SNARK and against Bulletproofs

953×249 102 KB

Discussion and Key Takeaways

  • Traditional zk-SNARKs 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 Follow-ups

  • Sonic introduces a new zk-SNARK 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 zk-SNRAKs are applied to many systems now, and many other universal zk-SNARK works.

Applicability

  • It seems no application directly uses Sonic, however, this work brings the applicability of zk-SNARKs to the next level.
5 Likes
2

@flyinglimao Thanks for a fascinating contribution to the Research Summaries! I have a few simple questions about your summary:

  • You state that “most zk-SNARKs require a trusted setup,” which may imply that some do not. Is this true, and if so, what can we learn from these “other” zk-SNARKs?

  • Why are traditional zk-SNARKs trusted setups so time-consuming and costly?

  • What are the major zk-SNARKs platforms and the differences among them?

  • You state that by making SRS updatable, Sonic “might be considered a milestone that inspired PlonK, et al.,” but you also state that “no application directly uses Sonic.” Does this suggest that Sonic’s contribution is of historical interest only, or does Sonic have the possibility of real-world adoption?

5 Likes
3

Hi @rlombreglia

  • I heard Spartan[1] that Microsoft published and claimed it doesn’t need a trusted setup and RedShift[2] is also zkSNARK without a trusted setup, so I said most of them require it. For the latter question, I can’t provide an answer yet.
  • As I heard from a participant of a trusted setup ceremony in a ZKP study group in TEM, they usually have to run a script for hours to guarantee the randomness and then pass the result to the next participant. That has to be done by a lot of participants to convince users (e.g. if a global system was set up by a group of only 10 contributors, it’s more likely to be considered insecure). But I’d say that is a practice consideration instead of an academic research conclusion.
  • I think these can first be split into 2 groups: non-universal (traditional) and universal. For platforms in the same group, the major differences will be proof size, verification time, proving time, and setup procedure, and other differences will be post-quantum, assumption (security), and so on. As I know so far, Groth16 might be the most important platform in former groups as it has better results than others on the major differences. The latter groups have Sonic, PlonK, RedShift, Halo…etc. I’ve not read into them so I can’t describe the exact differences here, but the major differences mentioned above may be part of those.
  • My answer to this question is totally in my opinion. I’d say that the previous work (Groth, Jens, et al., Citation 3 in summary) brought the interest to researchers but had practice issues and Sonic solved them and brought the possibility of adoption. The reason Sonic wasn’t used is the evolution is too rapid.
  1. https://eprint.iacr.org/2019/550.pdf
  2. Research Summary: REDSHIFT: Transparent SNARKs from List Polynominal Commitment IOPs
3 Likes
4

Hi @flyinglimao

Very interesting topic. What could be the next steps in terms of convincing industry players to adopt Sonic for those who already use the “mainstream” zk-SNARKs?

Would there be any instances where Sonic wouldn’t be as effective as your summary claims? If so, what would be some of the limiting factors and why?

2 Likes
5

Hi @shoule

In my opinion, if an application had run a trusted setup and doesn’t need an update, it may not necessary for them to adopt Sonic, PlonK, and other universal zkSNARKs for performance consideration (except the construction they used is less efficient than those). But for those who are going to release a new app or delivery an update, adopting universal zkSNARKs can speed up the software iteration and cut the cost of starting. (I indeed don’t know if people will adopting Sonic instead of PlonK and if PlonK is only a more efficient scheme based on Sonic without bringing other changes.)

If the amount of users of a Sonic application isn’t enough to make a helper work, Sonic might unable to be most effective in theory. Except that, I don’t have an idea about if any factor may make it not effective, but I also cannot simply say no since I don’t have enough knowledge about it, thus I can’t provide an complete answer.

3 Likes
6

Hey @flyinglimao, thanks for the summary.

The previous zk-SNARK was impractical because the SRS (Structured reference string) resulted in large computation time. To what extent did Sonic solve this problem?
What might be the other trade-offs for Sonics and universal SNARKs in general? It’s hard to imagine why no application directly uses Sonic, given that universality seems like a critical improvement.

2 Likes
7

Hi @Twan

I’m not sure if the kinda answer is what you want and the computation is correct, according to the table (Result > Proving Knowledge of Preimage), the previous work might need an SRS with size (3.74 MB * 1024 KB/MB * 1024 B/KB / (8~1024) B)^2 * (8~1024) (element/B) ~= 1.79 TB ~ 13.99 GB for proving a preimage of Pedersen hash with 384 bits input (here assume an element in SRS takes 8 bytes (long int) to 1024 bytes), while Sonic used only 3.74 MB.

As I know so far, the most trade-offs for universal SNARKs are SRS size, verification time, and proving time. I don’t know much about the industry, therefore, I can’t give an answer to the reason for not adopting.

3 Likes
8

Hi @flyinglimao. Thanks for your detailed response to my questions. Obviously, I’m not an expert on zk-SNARKs, but in my general reading I have seen it said that “the time for zero-knowledge proofs has arrived,” and that the time-consuming downsides of trusted setups make universal SNARKs especially appealing.

You mentioned that Sonic “wasn’t used [because] the evolution is too rapid.” I’m not sure what the word “evolution” refers to, so I’ll ask part of my question again: Is Sonic (in your view) a currently applicable solution going forward, or has the “evolution” of universal, update-able SNARKs made Sonic an early pioneer that is now part of the history of this field?

Or is the work on Sonic still ongoing? If that is true and “Sonic v.2” is in the works, can you disclose anything about the way it will solve some of the “evolutionary” issues that zk-SNARKs in general are facing?

2 Likes
9

Hi @rlombreglia.

In my view, Sonic is an applicable solution but we may use Marlin or PlonK instead as they improved the efficiency (that’s the “evolution” in my previous words). Hence for short, it’s not suitable currently as we have alternatives that have better efficiency, and I’ll agree that Sonic is now a part of the history. (I’m not sure what’s “currently applicable” means here. Maybe giving an analogy here will help: Sonic is like Dial-up internet that it’s applicable but not suitable today.)

I saw there is SuperSonic but I’ve not read into it and it’s not a work from anyone of the Sonic authors thus I don’t consider it as “Sonic v2”. I’m trying to give a roadmap: Mary Maller (first author of Sonic) published the Marlin which improves efficiency by using algebraic holographic proof. Sean Bowe (second author) published the Halo which does too by using an aggression technique (here is a post explaining Halo 2 and mentioned Sonic from him, maybe it’s a good material FYI).

2 Likes
10

You mentioned that SONIC has become part of SNARKS history. I was wondering if you could shed some light on something Vitalik Buterin said in response to a question about which privacy technology would be the most prevalent in 2050: he replied, “I expect ZK-SNARKs to be a significant revolution as they permeate the mainstream world over the next 10-20 years.” and when asked about the first SNARK(ed) application to hit 10mm users would be, replied “Oh my answer is something much more mundane like some cryptographic anti-sybil thing by Cloudflare.” @flyinglimao, how do you imagine SNARKS and privacy in general over the next few decades?

1 Like
11

This is a question for @cipherix (SCRF research lead) who suggested this article for summary: I know that background is important to SCRF’s selection criteria, I’m curious whether or not there was an order to the way you chose which zero-knowledge summaries to feature on SCRF. We’ve had a couple of questions about the historical value of SONIC, universal generation and Kate Commitments, where there any other considerations for SONIC or the other pieces featured on SCRF?

12

Hi @jmcgirk.

For me, SNARKS (or more general, ZKP) is a tool that brings applications (including blockchain, web, and many things) a way to balance transparency and privacy. Also, the awareness of privacy is increasing these years, I imagine that people may not understand how it works but why they need and will use them frequently (just like TCP/IP, SSL).

1 Like
13

This is a great question and I don’t think there is a perfect sequencing for SNARK coverage. We have covered what are arguably the two most significant schemes under the Knowledge of Exponent (KoE) assumption, SONIC and PLONK, but there are several other schemes worth summarizing.

@flyinglimao is right in that SuperSonic is the natural evolution of Sonic. From a taxonomy perspective, SuperSonic falls under a new variant of asymmetric assumptions generally called Groups of Unknown Order Together with DARK, these constructs can provide some usability benefits and do not require a trusted setup. Here is an incredibly helpful post by STARKWARE that does a great job contextualizing this evolution:

3 Likes
14

@cipherix, I immediately recognized, ‘cambrian explosion’ in the reference link you provided here, with similar phraseology you used in SCRF Interviews: PlonK and SNARKS with Ariel Gabizon and Lucas Nuzzi. Digesting the referenced article put the organization of cryptographic proofs into perspective for me. Specifically, the figures are fantastic, and represent a plethora of information in a succinct manner. I see an outline for what original research papers to read and when doing so, the overarching context they fit into as a whole. Additionally, I see a reference framework for reading future research papers in this space. This article gave me an on-ramp and a reference frame to this topic…greatly appreciated!

2 Likes
15

Just some appendix here…

For ZK proof systems, terms and glossaries are often hard to describe and harder to categorize.
We have:

“require trusted setup”
“does not require trusted setup”
“(SRS), require trusted setup but updatable”
“(CRS) require trusted setup and not updatable…”
etc…

Although it’s far from being standardized/widely recognized, I’d say if we use the following abbreviations (usage promoted by matter labs, probably, citation needed), it can make discussing things easier=we now know what each other’s talking about faster, and also makes googling (SEO-wise) easier.

so,
SNARK: Groth16, the snark we know
require trusted setup (CRS), not updatable and thus not universal, generally accepted and widely used atm.

SNORK: Started from sonic=>plonk/merlin, O stands for oecumenical, a fancy way of saying that it’s universal and updatable. Still require trusted setup as sort of an infrastructure for the first time, but the parameter can be reused by anyone for circuits under a certain size (hence universal/updatable).

STARK: Started from FRI STARK(Fast Reed-Solomon Interactive protocol)=>halo/supersonic/fractal…, and T stands for transparent. Trusted setup is not needed.

Although there are so many variations about the primitives (lego block) in use of those systems, I hope that by introducing the top level categorizing words in our discussions (snark/snork/stark), we can help standardize the word usage and make newer learner feel less confused about it.

(Language can and will evolve - we just need to embrace the usage we think is the fittest)

4 Likes
16

One of my favorite topics to discuss the zkSNARKs; In 2017 when I began to develop the concepts of my then OffChain StartUp for my eNotaries Public Portal, this was also the year I first learned about zkSNARKS and since then i wanted to work with this technology but i didnt know how, as it was in its early stages.

Since then I became almost obsessed over the technology rapid development, in fact, it is how today we obtain our decentralized identities. Earlier this year I made the executive decision to pivot my StartUp into our OnChain Ecosystem. Why i bring this into context is the easiest way to demonstrate how zkSNARKS are being utilized and how they are proving current standards are outdated.

Knowledge base authentication is the most commonly used method of user authentication in banks today. It may seem like a good idea at first, but when you look deeper into it you’ll see that it’s not as secure or efficient as other methods out there. This article will explain why zkSNARKS should replace knowledge base authentication for improving security and streamlining processes within financial institutions.

  • It’s not secure - Anyone with access to your database could potentially tamper with your credentials/authentication information. This means if someone gets hold of these sensitive details, they’d be able to impersonate users on your site without any problems whatsoever! This can lead into some serious consequences if left unchecked

  • It’s slow - Understanding all potential variations between two different sets of data takes time—and even more so when there are many different permutations between those sets! You’ll find yourself spending hours trying out various combinations just so that you can see which ones work best for each particular situation…or worse yet…trying everything one by one until something finally works out perfectly well enough for us.

Then there is, Credential analysis is the process of examining a user’s credentials to determine if they are authentic. It’s used in most banks and other financial institutions, as well as many government agencies and large corporations. Credential analysis is outdated and insecure. Hashes only add more data to an attacker’s hands—they don’t provide any context about what that data means or how it should be interpreted.

zkSNARKs replace knowledge bases with zero-knowledge proofs: instead of checking if two pieces of information are equal, you prove how much one piece resembles another without revealing anything else about either piece zkSNARKs are more secure, scalable, flexible & cheaper to implement than any other method of authentication such as knowledge base or credential analysis They are also resistant to data tampering, which makes them ideal for applications like supply chain logistics, medical records, and financial transactions. I will be publishing a few article in the upcoming weeks addressing this and other technologies that are natively developed into my portal and before we launch next year i’ll be releasing a more cohesive white paper.

1 Like
17

We know that a proof has something to do with an arithmetic circuit, but not how it does so or why? Can anyone help answer this, and also, how does a proof look like?

18

@Freakytainment You would have to study the subject to understand the concept, as it is not as simple but if i had to over simplify the convoluted process, you are entitled from birth to personal information that can be used for the entitlement of unique identifiers then add a personal device purchased by you and so these items have additional unique identifiers. Your UID and the tech UID are hashed and correlated to more UIDs, and other parameters are introduce to be able to process and obtain a decentralized identity and remember i’m not an expert so this analogy is as accurate as i have come to understand it over the course of the years

1 Like