Challenge Two: Crafting Constraint Systems

Challenge Two: Crafting Constraint Systems

Challenge Two: Crafting Constraint Systems

Step 1 of 11

9%
  • Challenge Set 2: Crafting Constraint Systems‣ QED-it SNARK Treasure Hunt

    Challenge Set 2: Crafting Constraint Systems

    In the last challenge set, we explored the functionality of zkSNARKs by learning how to write problem statements in a format that allows proving efficiently. In this set we will see how to translate these NP statements into the language of constraint systems, used in the current implementations of zkSNARKs. We will give out a total of $500 in Bitcoin prizes to the top ten answers. In about a month, we will publish the solutions, inform the winners and award the prizes.

    In this challenge set, we will see how useful statements can be expressed in the native language of zkSNARKs, along with its pitfalls and tricks. It will culminate in a simple zkSNARK application, for proving ownership of anonymous tokens.

    Note: It can be very challenging to create these riddles, which means that you may find some issues. It may be typos, mathematical errors or even confusion between different interpretations of the question. If this is the case, just click on "Save and Continue Later / Report Issue" and fill in details in the confirmation page so that we can get back to you with an answer. Or just email us at [email protected].

    Teaser: the upcoming Challenge Set 3 will feature a zero-knowledge proof based protocol for a simple decentralized private credit score platform. It will use the ideas we present here, but not always correctly… Your job will be to find the bugs and fix them, to get a secure protocol (and a major prize!). So pay attention and good luck with the hunting!

    We would like to thank our advisor, Prof. Eran Tromer, who coauthored these riddles.

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

BCS Definition

Definition.    Let n𝗑,n𝗐,n𝖼 be positive integers, and n𝗓=n𝗑+n𝗐+1. A bilinear constraint system over 𝔽q is a tuple 𝐒=((aj,bj,cj)j=1n𝖼,n𝗑) where aj,bj,cj𝔽qn𝗓. Such a system 𝐒 is satisfiable with an input x𝔽qn𝗑 if the following is true:

  • For these 𝐒=((aj,bj,cj)j=1n𝖼,n𝗑) and x𝔽qn𝗑;

  • there exists a witness w𝔽qn𝗐;

  • such that aj,zbj,z=cj,z   for all for j[n𝖼], where z=(1,x,w)𝔽qn𝗓 .

Above, , denotes inner product of vectors over 𝔽q, and denotes multiplication in 𝔽q.

For example, the bilinear constraint system

𝐒=((a1=(0,3,0,0),b1=(1,1,0,0),c1=(4,0,5,0)a2=(0,1,2,0),b2=(6,0,1,0),c2=(7,0,0,1)),1) (1)

represents the two bilinear constraints

(0,3,0,0),z(1,1,0,0),z=(4,0,5,0),z(0,1,2,0),z(6,0,1,0),z=(7,0,0,1),z where z=(1,x1,w1,w2) (2)

or simply:

3x1(1+x1) =5w1+4 (3)
(x1+2w1)(w1+6) =w2+7

By definition, this system 𝐒 is satisfiable with input x1 if the following is true:

  • For the instance x1;

  • there exist a witness w1,w2;

  • such that

    3x1(1+x1) =5w1+4
    (x1+2w1)(w1+6) =w2+7

Gadgets

We recall the gadgets introduced previously.

Boolean(v):={// v is 0 or 1v(v-1)=0}

Square(v):={// v𝔽q is a square (i.e., quadratic residue) in 𝔽qu: // u is a square root of vuu=v}

Booleanify(v,b):={// for v𝔽q, if v=0 then b=0, else b=1u // if v0 then u=v-1 over 𝔽q, otherwise u is arbitraryuv=bbv=v}

Or(a,b,c):={// a,b,c{0,1}𝔽q, and c=ab as Boolean variabless:Boolean(a)Boolean(b)a+b=sBooleanify(s,c)}

IsEqual(a,b,c):={// if a=b then c=1, else c=0d,e:a-b=dBooleanify(d,e)1-e=c}

Logo Header Menu