2.4 Gadgets
It is useful to introduce gadgets as a way to construct constraint systems in a modular fashion, by grouping fundamental constraints and using the groups to build more complex constraint systems. In turn, gadgets can be used to create larger gadgets, recursively. A gadget is like a macro that, applied to some formal variables, expands to a set of constraints applied to those variables. For example:
$\begin{array}{c}\mathrm{\text{Boolean}}(v):=\{\mathit{\hspace{1em}}\text{//}v\text{is 0 or 1}\hfill \\ \mathit{\hspace{1em}}\begin{array}{c}v\cdot (v1)=0\hfill \end{array}\hfill \\ \}\hfill \end{array}$
A gadget can introduce ancillary (helper) local variables. When the gadget is used, each such ancillary variable adds a fresh variable to the witness $\overrightarrow{w}$ of the overall constraint system, and increases its ${n}_{\U0001d5d0}$ by 1. For example:
$\begin{array}{c}\mathrm{\text{Square}}(v):=\{\mathit{\hspace{1em}}\text{//}v\in {\mathbb{F}}_{q}\text{is a square (i.e., quadratic residue) in}{\mathbb{F}}_{q}\hfill \\ \mathit{\hspace{1em}}\begin{array}{c}u:\text{//}u\text{is a square root of}v\hfill \\ u\cdot u=v\hfill \end{array}\hfill \\ \}\hfill \end{array}$
Every time the Square gadget is used, a fresh variable corresponding to $u$ (in that instance of Square) is added to the overall constraint system. To satisfy the constraint system (and produce a proof of this satisfiability, using a zkSNARK), the variable must be assigned a value which is indeed a square root of the variable $v$ (in that instance of Square).
Note that above, “$u$ is a square root of $v$” is merely a textual comment, to aid our intuition. It’s the subsequent bilinear constraint, $u\cdot u=v$, that actually enforce this requirement. Had the two been inconsistent, the gadget may have failed to correctly express our intention.
Here is another, very useful gadget:
$\begin{array}{c}\mathrm{\text{Booleanify}}(v,b):=\{\mathit{\hspace{1em}}\text{// for}v\in {\mathbb{F}}_{q}\text{, if}v=0\text{then}b=0\text{, else}b=1\hfill \\ \mathit{\hspace{1em}}\begin{array}{c}u\text{// if}v\ne 0\text{then}u={v}^{1}\text{over}{\mathbb{F}}_{q}\text{, otherwise}u\text{is arbitrary}\hfill \\ u\cdot v=b\hfill \\ b\cdot v=v\hfill \end{array}\hfill \\ \}\hfill \end{array}$
We can also compose gadgets, by which we mean the natural recursive macro expansion:
$\begin{array}{c}\mathrm{\text{Or}}(a,b,c):=\{\mathit{\hspace{1em}}\text{//}a,b,c\in \{0,1\}\subset {\mathbb{F}}_{q}\text{, and}c=a\wedge b\text{as Boolean variables}\hfill \\ \mathit{\hspace{1em}}\begin{array}{c}s:\hfill \\ \mathrm{\text{Boolean}}(a)\hfill \\ \mathrm{\text{Boolean}}(b)\hfill \\ a+b=s\hfill \\ \mathrm{\text{Booleanify}}(s,c)\hfill \end{array}\hfill \\ \}\hfill \end{array}$
$\begin{array}{c}\mathrm{\text{IsEqual}}(a,b,c):=\{\mathit{\hspace{1em}}\text{// if}a=b\text{then}c=1\text{, else}c=0\hfill \\ \mathit{\hspace{1em}}\begin{array}{c}d,e:\hfill \\ ab=d\hfill \\ \mathrm{\text{Booleanify}}(d,e)\hfill \\ 1e=c\hfill \end{array}\hfill \\ \}\hfill \end{array}$
Having defined gadgets, we can use them to build a constraint system. For example, the following bilinear constraint systems says that ${x}_{1}\in {\mathbb{F}}_{q}$ equals 17 or is a square in ${\mathbb{F}}_{q}$:

$$\mathbf{S}=(\left(\begin{array}{c}\mathrm{\text{Square}}({w}_{1})\hfill \\ \mathrm{\text{IsEqual}}({w}_{1},{x}_{1},{w}_{2})\hfill \\ \mathrm{\text{IsEqual}}(17,{x}_{1},{w}_{3})\hfill \\ \mathrm{\text{Or}}({w}_{2},{w}_{3},{w}_{4})\hfill \\ {w}_{4}=1\hfill \end{array}\right),1)$$ 

a. What is the total number of constraints ${n}_{\U0001d5bc}$, and the size ${n}_{\U0001d5d0}$ of the witness $\overrightarrow{w}$, in the above $\mathbf{S}$ (after all gadgets are expanded)?
b. For ${x}_{1}$ that fulfills this NP statement, how would you assign values to the witness $\overrightarrow{w}$?
c. Is this ${n}_{\U0001d5bc}$ optimal for this NP statement? Explain.