The Hunting of the SNARK

The Hunting of the SNARK

We are very excited to present to you The Hunting of the SNARK, a treasure hunt consisting of cryptographic challenges that will guide you through a zero-knowledge proof (ZKP) learning experience. As a reminder, Zero-Knowledge Proofs, invented decades ago [10], allow verifiers to validate a computation on private data by allowing a prover to generate a cryptographic proof that asserts to the correctness of the computed output. zk-SNARK, a sub-class of zero-knowledge proofs [5], further makes these proofs succinct and noninteractive — as needed in many applications. In these riddles, we will explore the definition of zk-SNARK and how it can be correctly used in applications. We will then look at the state-of-the-art approach to constructing zk-SNARKs. Check out our latest tech post [16] or our recent meetup [17] to get a feeling of how powerful ZKPs can be.

We have seen plenty of other great posts and articles explaining ZKPs, including an overview [11], detailed technical tutorials [15, 7, 8], and a video-recorded workshop [6]. Yet, just like with all math, it is not enough to read about it, you need to practice it. At QED-it we have come up with an innovative way to learn cryptography, while at the same time understanding its implications in practice.

How it Works

Every once in a while we will publish a new challenge set, composed of several riddles, which will increase in difficulty with each new set. Every riddle is designed to teach you a new aspect of zk-SNARKs by making you discover the intricacies of the protocol and its smart design features.

If you complete the treasure hunt, you will gain an understanding of zk-SNARKs, how they work, what the security assumptions mean for the scheme and how to properly define the statements to be proven. The more difficult riddles will guide you towards generating proofs that can verify a false claim (when a security assumption is broken) and how to break some of the security assumptions, while at the same time understanding how to prevent other people from doing so. You will learn all this and much more.

If this was not enough motivation, some of the riddles will be accompanied with a prize, awarded to the best solutions. With each riddle we will specify the prize and how many of them will be given.

 

Here are the links to the challenge sets:

  1. Challenge One: The Functionality of zk-SNARK
  2. Challenge Two: Crafting Constraint Systems
  3. Challenge Three: to be released…
Acknowledgements

The QED-it team wants to thank Prof. Eran Tromer, a coauthor of The Hunting of the SNARK, for helping us make this treasure hunt a reality. He not only advised us in designing the riddles and perfecting the educational content, but also instantiated the details in the problems and wrote the riddle descriptions. We are happy to have him as a scientific advisor.

 

Sign up to our mailing list here in order to receive notifications when we release the riddles.

Subscribe to our mailing list:

References

  • [1] E. Ben-Sasson, A. Chiesa, C. Garman, Green, I. Miers, E. Tromer and M. Virza (2014), Zerocash: decentralized anonymous payments from BitcoinIn Proceedings of the 2014 IEEE Symposium on Security and PrivacySP ’14, pp. 459–474External Links: Link
  • [2] E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer and M. Virza (2013), SNARKs for C: verifying program executions succinctly and in zero knowledge (extended version)Note: Cryptology ePrint Archive, Report 2013/507. External Links: Link
  • [3] E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer and M. Virza (2013), SNARKs for C: verifying program executions succinctly and in zero knowledgeIn CRYPTO ’13pp. 90–108Note: Extended version: [2]. 
  • [4] E. Ben-Sasson, A. Chiesa, E. Tromer and M. Virza (2014), Succinct non-interactive zero knowledge for a von Neumann architectureIn USENIX Security 2014pp. 781–796External Links: Link
  • [5] N. Bitansky, R. Canetti, A. Chiesa, S. Goldwasser, H. Lin, A. Rubinstein and E. Tromer, The hunting of the SNARKJournal of CryptologyNote: to appear. External Links: Link
  • [6] (2016) BIU winter school: cryptography in the cloud — verifiable computation and special encryptionNote: workshop (with video recording). External Links: Link
  • [7] V. Buterin (2017), zk-SNARKs: under the hoodNote: blog posts. External Links: Link
  • [8] A. Gabizon (2017), Explaining snarks (parts i through vii)Note: blog posts. External Links: Link
  • [9] R. Gennaro, C. Gentry, B. Parno and M. Raykova (2013), Quadratic span programs and succinct NIZKs without PCPsIn EUROCRYPT ’13pp. 626–645External Links: Link
  • [10] S. Goldwasser, S. Micali and C. Rackoff (1985), The knowledge complexity of interactive proof-systemsIn STOC 1985pp. 291–304External Links: Link
  • [11] M. Green (2014), Zero knowledge proofs: an illustrated primerNote: blog post. External Links: Link.
  • [12] M. Naor, Y. Naor and O. Reingold (1999), Applied kid cryptography or how to convince your children you are not cheatingIn Eurocrypt ’94pp. 1–12
  • [13] M. Naor(Website). External Links: Link.
  • [14] B. Parno, J. Howell, C. Gentry and M. Raykova (2013), Pinocchio: nearly practical verifiable computationIn IEEE Symposium on Security and Privacypp. 238–252External Links: Link.
  • [15] C. Reitwiessner (2016), zkSNARKs in a nutshellNote: blog post. External Links: Link. 
  • [16] D. Benarroch and A. Zohar (2017), Trustless Computing on Private DataNote: blog post. External Links: Link. 
  • [17] (2017) QED-it Meetup, Prove-it, Blockchain-it: ZKP in ActionNote: Tel Aviv Meetup (with video recording). External Links: Link
  • [18] T. Sander and A. Ta-Shma (1999)Auditable, anonymous electronic cash.In Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology,CRYPTO ’99, pp. 555–572. External Links: Link

Logo Header Menu