6%
• # Challenge Set 1: The Functionality of zk-SNARK

This set explores the notion of zk-SNARK and its properties. We will remain informal, and discuss how a zk-SNARK can be used as a black box. We assume you’ve already seen the basics of zk-SNARKs, but let us quickly review the setup and terminology (in an informal and simplified form). A “zk-SNARK” (zero-knowledge succinct non-interactive argument of knowledge) is a general-purpose cryptographic proof system that lets a prover convince a verifier that some statement is true. Each of the concepts in the name will be discussed in this set of riddles.

The set of statements allowed in zk-SNARKs are formally called NP statements, a concept taken from the field of Complexity Theory. In general, a problem is said to be in the class of NP its solution is easy to verify. Computational hardness can be thought of like this: for a large-sized input, the best known algorithm takes longer than a “lifetime” to compute in a regular machine.

For use in the zk-SNARK scheme, an NP statement must be expressible in the following form:

• For the value $x$ (the instance);

• I know some secret value $w$ (the witness);

• such that condition $D$ holds on $x$ and $w$ (the relation).

For example, the NP statement for “I know a factorization of 56145337” would be expressed as:

• For $x=56145337$;

• I know some integers $p$,$q$;

• such that $x=p\times q$.

As another example, the NP statement for “the chess board configuration $B$ is reachable from the initial board configuration $A$” would be expressed as:

• For the board configurations $A$ and $B$;

• I know some sequence $S$ of chess moves;

• such that when starting from configuration $A$, and applying $S$, all moves are legal and the final configuration is $B$.

Note that before the key generation process, the NP statement must be translated into a constraint system, whose size is proportional to the number of steps in the underlying computer program.

A scheme is complete if, whenever the prover knows a correct witness, the generated proof always verifies. A scheme is called sound if the verifier catches a cheating prover with overwhelming probability. In short, zk-SNARKs are complete and sound and are made up of three efficient algorithms.

1. The key generator, given a constraint system, samples some randomness and generates a proving key and a verification key (jointly also called the public parameters or common reference string).

2. The prover, given an instance, witness and proving key, generates a succint proof. That is, the proof is small and of constant size, independent of the constraint system’s size.

3. The verifier, given an instance, proof and verification key, accepts or rejects the proof.

This set does not include any prizes as the riddles simply give a hands-on introduction to the functionality and properties of zk-SNARKS.

GOOD LUCK HUNTING THE SNARK!

# 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 Proceedings of the 33rd Annual International Cryptology ConferenceCRYPTO ’13, pp. 90–108
• [4] 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].
• [5] 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
• [6] 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
• [7] (2016) BIU winter school: cryptography in the cloud — verifiable computation and special encryptionNote: workshop (with video recording). External Links: Link
• [8] V. Buterin (2017), zk-SNARKs: under the hoodNote: blog posts. External Links: Link
• [9] A. Gabizon (2017), Explaining snarks (parts i through vii)Note: blog posts. External Links: Link
• [10] R. Gennaro, C. Gentry, B. Parno and M. Raykova (2013), Quadratic span programs and succinct NIZKs without PCPsIn EUROCRYPT ’13pp. 626–645External Links: Link
• [11] S. Goldwasser, S. Micali and C. Rackoff (1985), The knowledge complexity of interactive proof-systemsIn STOC 1985pp. 291–304External Links: Link
• [12] M. Green (2014), Zero knowledge proofs: an illustrated primerNote: blog post. External Links: Link.
• [13] 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
• [14] M. Naor(Website). External Links: Link.
• [15] 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.
• [16] C. Reitwiessner (2016), zkSNARKs in a nutshellNote: blog post. External Links:
• [17] D. Benarroch and A. Zohar (2017), Trustless Computing on Private DataNote: blog post. External Links:
• [18] (2017) QED-it Meetup, Prove-it, Blockchain-it: ZKP in ActionNote: Tel Aviv Meetup (with video recording). External Links: Link
54321
(76 votes. Average 2.45 of 5)