# 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
• [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:
• [16] D. Benarroch and A. Zohar (2017), Trustless Computing on Private DataNote: blog post. External Links:
• [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_{\mathsf{x}}},{n_{\mathsf{w}}},n_{\mathsf{c}}$ be positive integers, and ${n_{\mathsf{z}}}={n_{\mathsf{x}}}+{n_{\mathsf{w}}}+1$. A bilinear constraint system over $\mathbb{F}_{q}$ is a tuple $\mathbf{S}=\big{(}(\vec{a}_{j},\vec{b}_{j},\vec{c}_{j})_{j=1}^{n_{\mathsf{c}}}% ,{n_{\mathsf{x}}}\big{)}$ where $\vec{a}_{j},\vec{b}_{j},\vec{c}_{j}\in\mathbb{F}_{q}^{{n_{\mathsf{z}}}}$. Such a system $\mathbf{S}$ is satisfiable with an input $\vec{x}\in\mathbb{F}_{q}^{{n_{\mathsf{x}}}}$ if the following is true:

• For these $\mathbf{S}=\big{(}(\vec{a}_{j},\vec{b}_{j},\vec{c}_{j})_{j=1}^{n_{\mathsf{c}}}% ,{n_{\mathsf{x}}}\big{)}$ and $\vec{x}\in\mathbb{F}_{q}^{{n_{\mathsf{x}}}}$;

• there exists a witness $\vec{w}\in\mathbb{F}_{q}^{{n_{\mathsf{w}}}}$;

• such that $\left\langle\vec{a}_{j},\vec{z}\right\rangle\cdot\left\langle\vec{b}_{j},\vec{% z}\right\rangle=\left\langle\vec{c}_{j},\vec{z}\right\rangle$   for all for $j\in[n_{\mathsf{c}}]$, where $\vec{z}=(1,\vec{x},\vec{w})\in\mathbb{F}_{q}^{{n_{\mathsf{z}}}}$ .

Above, $\left\langle\cdots,\cdots\right\rangle$ denotes inner product of vectors over $\mathbb{F}_{q}$, and $\cdot$ denotes multiplication in $\mathbb{F}_{q}$.

For example, the bilinear constraint system

 \mathbf{S}=\left(\left(\begin{aligned} \displaystyle\vec{a}_{1}=(0,3,0,0),\,% \vec{b}_{1}=(1,1,0,0),\,\vec{c}_{1}=(4,0,5,0)\\ \displaystyle\vec{a}_{2}=(0,1,2,0),\,\vec{b}_{2}=(6,0,1,0),\,\vec{c}_{2}=(7,0,% 0,1)\end{aligned}\right),1\right) (1)

represents the two bilinear constraints

 \begin{aligned} \displaystyle\left\langle(0,3,0,0),\vec{z}\right\rangle\cdot% \left\langle(1,1,0,0),\vec{z}\right\rangle&\displaystyle=\left\langle(4,0,5,0)% ,\vec{z}\right\rangle\\ \displaystyle\left\langle(0,1,2,0),\vec{z}\right\rangle\cdot\left\langle(6,0,1% ,0),\vec{z}\right\rangle&\displaystyle=\left\langle(7,0,0,1),\vec{z}\right% \rangle\end{aligned}\quad\mbox{ where }\vec{z}=(1,x_{1},w_{1},w_{2}) (2)

or simply:

 $\displaystyle 3x_{1}\cdot(1+x_{1})$ $\displaystyle=5w_{1}+4$ (3) $\displaystyle(x_{1}+2w_{1})\cdot(w_{1}+6)$ $\displaystyle=w_{2}+7$

By definition, this system $\mathbf{S}$ is satisfiable with input $x_{1}$ if the following is true:

• For the instance $x_{1}$;

• there exist a witness $w_{1},w_{2}$;

• such that

 $\displaystyle 3x_{1}\cdot(1+x_{1})$ $\displaystyle=5w_{1}+4$ $\displaystyle(x_{1}+2w_{1})\cdot(w_{1}+6)$ $\displaystyle=w_{2}+7$

$\begin{array}[]{l}\textsc{Boolean}(v):=\{{\quad\mbox{// {v is 0 or 1}}}\\ \mbox{}\quad\begin{array}[]{l}v\cdot(v-1)=0\end{array}\\ \}\end{array}$
$\begin{array}[]{l}\textsc{Square}(v):=\{{\quad\mbox{// {v\in\mathbb{F}_{q} % is a square (i.e., quadratic residue) in \mathbb{F}_{q}}}}\\ \mbox{}\quad\begin{array}[]{l}u:\mbox{\quad// u is a square root of v}\\ u\cdot u=v\end{array}\\ \}\end{array}$
$\begin{array}[]{l}\textsc{Booleanify}(v,b):=\{{\quad\mbox{// {for v\in\mathbb% {F}_{q}, if v=0 then b=0, else b=1}}}\\ \mbox{}\quad\begin{array}[]{l}u\mbox{\quad// if v\neq 0 then u=v^{-1} over% \mathbb{F}_{q}, otherwise u is arbitrary}\\ u\cdot v=b\\ b\cdot v=v\end{array}\\ \}\end{array}$
$\begin{array}[]{l}\textsc{Or}(a,b,c):=\{{\quad\mbox{// {a,b,c\in\{0,1\}% \subset\mathbb{F}_{q}, and c=a\wedge b as Boolean variables}}}\\ \mbox{}\quad\begin{array}[]{l}s:\\ \textsc{Boolean}(a)\\ \textsc{Boolean}(b)\\ a+b=s\\ \textsc{Booleanify}(s,c)\end{array}\\ \}\end{array}$
$\begin{array}[]{l}\textsc{IsEqual}(a,b,c):=\{{\quad\mbox{// {if a=b then c=% 1, else c=0}}}\\ \mbox{}\quad\begin{array}[]{l}d,e:\\ a-b=d\\ \textsc{Booleanify}(d,e)\\ 1-e=c\end{array}\\ \}\end{array}$