Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings
The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
Abstract
Ever since their introduction, zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in a variety of 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 schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal structured reference string that is also updatable, but the string scales quadratically in the size of the supported relations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts
Kosba, A., Miller, A., Shi, E., Wen, Z., & Papamanthou, C. (2016) · 2016 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2016.55 · Cited by 2,227 · cited 1×
“In recent years, cryptocurrencies have been one increasingly popular real-world application [10, 44, 52, 57], with general zero-knowledge protocols now deployed in both Zcash and Ethereum.”
BackgroundZerocash: Decentralized Anonymous Payments from Bitcoin
Ben Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014) · 2014 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2014.36 · Cited by 1,925
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
On the Size of Pairing-Based Non-interactive Arguments
Groth, J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_11 · Cited by 1,271 · cited 17×
“Using knowledge assumptions, it is possible to build zk-SNARKs [15, 18, 35, 45, 47, 54, 59].”
BackgroundMethodResultInfluentialBulletproofs: Short Proofs for Confidential Transactions and More
Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., & Maxwell, G. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00020 · Cited by 1,154 · cited 3×
“We also give a more concrete efficiency comparison in Table 2 of Sonic against the fastest zk-SNARK in the literature (Groth 2016 [45]) and Bulletproofs [26].”
BackgroundResultScalable, transparent, and post-quantum secure computational integrity.Preprint
Ben‐Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018) · IACR Cryptology ePrint Archive · Cited by 873
Pinocchio: Nearly Practical Verifiable Computation
Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.47 · Cited by 864
Galbraith, S. D., Paterson, K. G., & Smart, N. P. (2008) · Discrete Applied Mathematics · doi:10.1016/j.dam.2007.12.010 · Cited by 794
Succinct non-interactive zero-knowledge for a von Neumann architecture
Ben‐Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014) · Cited by 772
Quadratic Span Programs and Succinct NIZKs without PCPs
Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38348-9_37 · Cited by 724
The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
Bellare, M., & Rogaway, P. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_25 · Cited by 672
Constant-Size Commitments to Polynomials and Their Applications
Kate, A., Zaverucha, G. M., & Goldberg, I. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_11 · Cited by 624
Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups
Boneh, D., & Boyen, X. (2008) · Journal of Cryptology · doi:10.1007/s00145-007-9005-7 · Cited by 605
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., & Virza, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_6 · Cited by 598 · cited 3×
“In the decades since their introduction, zero-knowledge proofs have been used to support a wide variety of potential applications, ranging from verifiable outsourced computation [11, 16, 24, 59]”
BackgroundMethodDelegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Separating succinct non-interactive arguments from all falsifiable assumptions
Gentry, C., & Wichs, D. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993651 · Cited by 456
Random Oracles in a Quantum World
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_3 · Cited by 449
Boneh, D., Bonneau, J., Bünz, B., & Fisch, B. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-96884-1_25 · Cited by 413
Aurora: Transparent Succinct Arguments for R1CS
Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., & Ward, N. P. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-17653-2_4 · Cited by 330
Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
Bootle, J., Cerulli, A., Chaidos, P., Groth, J., & Petit, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_12 · Cited by 325
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup
Ames, S., Hazay, C., Ishai, Y., & Venkitasubramaniam, M. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134104 · Cited by 305
Doubly-Efficient zkSNARKs Without Trusted Setup
Wahby, R. S., Tzialla, I., Shelat, A., Thaler, J., & Walfish, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00060 · Cited by 276
Randomizable Proofs and Delegatable Anonymous Credentials
Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., & Shacham, H. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_7 · Cited by 269
Self-citationBen-Sasson, E., Chiesa, A., & Spooner, N. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53644-5_2 · Cited by 252
Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives
Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., Slamanig, D., & Zaverucha, G. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133997 · Cited by 251
Bolt: Anonymous Payment Channels for Decentralized Currencies
Green, M., & Miers, I. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134093 · Cited by 237
Practical verified computation with streaming interactive proofs
Cormode, G., Mitzenmacher, M., & Thaler, J. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090245 · Cited by 200
Updating Key Size Estimations for Pairings
Barbulescu, R., & Duquesne, S. (2018) · Journal of Cryptology · doi:10.1007/s00145-018-9280-5 · Cited by 200
Efficient Zero-Knowledge Argument for Correctness of a Shuffle
Bayer, S., & Groth, J. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_17 · Cited by 193
Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs
Groth, J., & Maller, M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63715-0_20 · Cited by 190
Self-citationUpdatable and Universal Common Reference Strings with Applications to zk-SNARKs
Groth, J., Kohlweiss, M., Maller, M., Meiklejohn, S., & Miers, I. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96878-0_24 · Cited by 190
Self-citationScalable Zero Knowledge via Cycles of Elliptic Curves
Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-44381-1_16 · Cited by 189
Signatures of Correct Computation
Papamanthou, C., Shi, E., & Tamassia, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_13 · Cited by 188
Universal circuits (Preliminary Report)
Valiant, L. G. (1976) · Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76 · doi:10.1145/800113.803649 · Cited by 170
Zero-Knowledge Proofs from Secure Multiparty Computation
Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2009) · SIAM Journal on Computing · doi:10.1137/080725398 · Cited by 169
Cryptography with constant computational overhead
Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374438 · Cited by 158
Decentralized Anonymous Credentials
Garman, C., Green, M., & Miers, I. (2014) · Proceedings 2014 Network and Distributed System Security Symposium · doi:10.14722/ndss.2014.23253 · Cited by 155
Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation
Lindell, Y. (2003) · Journal of Cryptology · doi:10.1007/s00145-002-0143-7 · Cited by 153
ZKBoo: Faster Zero-Knowledge for Boolean CircuitsPreprint
Giacomelli, I., Madsen, J., & Orlandi, C. (2016) · IACR Cryptology ePrint Archive · Cited by 135
Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs
Ben-Sasson, E., Chiesa, A., Green, M., Tromer, E., & Virza, M. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.25 · Cited by 131
Composable and Modular Anonymous Credentials: Definitions and Practical Constructions
Camenisch, J. L., Dubovitskaya, M., Haralambiev, K., & Kohlweiss, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48800-3_11 · Cited by 127
Self-citationEfficient attributes for anonymous credentials
Camenisch, J. L., & Groß, T. (2008) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/1455770.1455814 · Cited by 121
NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion
Bellare, M., Fuchsbauer, G., & Scafuro, A. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53890-6_26 · Cited by 121
Lipmaa, H. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42033-7_3 · Cited by 109
Square Span Programs with Applications to Succinct NIZK Arguments
Danezis, G., Cédric Fournet, A., Groth, J., & Kohlweiss, M. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45611-8_28 · Cited by 104
Self-citationLinear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability
Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., & Jakobsen, S. K. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70700-6_12 · Cited by 87
Sub-linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
Baum, C., Bootle, J., Cerulli, A., del Pino, R., Groth, J., & Lyubashevsky, V. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96881-0_23 · Cited by 82
Malleable Signatures: New Definitions and Delegatable Anonymous Credentials
Chase, M., Kohlweiss, M., Lysyanskaya, A., & Meiklejohn, S. (2014) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf.2014.22 · Cited by 70
Self-citationSuccinct Malleable NIZKs and an Application to Compact Shuffles
Chase, M., Kohlweiss, M., Lysyanskaya, A., & Meiklejohn, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36594-2_6 · Cited by 30
Self-citationNearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution.Preprint
Bootle, J., Cerulli, A., Groth, J., Jakobsen, S., & Maller, M. (2018) · IACR Cryptology ePrint Archive · Cited by 3
Self-citation
Cited by
Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS
Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., & Ward, N. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45721-1_26 · Cited by 358
Self-citationDecentralized Privacy-Preserving Fair Exchange Scheme for V2G Based on Blockchain
Wan, Z., Zhang, T., Liu, W., Wang, M., & Zhu, L. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2021.3059345 · Cited by 44
Metadata
- Authors
- Maller, M., Bowe, S., Kohlweiss, M., & Meiklejohn, S.
- Venue
- Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
- Publisher
- ACM
- Published
- 2019-11-06
- Pages
- 2111-2128
- OpenAlex
- W2984674716
- Cited by
- 290
- References
- 50
- FWCI
- 12.82
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.