# Custom Gates

Consider the circuit below:

flowchart LR x1((x1)) --> +1[+ gate:1] x2((x2)) --> +1 x2 --> +2[+ gate:2] w1((w1)) --> +2 +1 --> x[x gate:3] +2 --> x x --> r(( ))

For a gate number $g$, denote the left input, right input, and the output as $a_{g},b_{g},c_{g}$ respectively. We would like the circuit to satisfy the following:

- $a_{1}+b_{1}=c_{1}=a_{3}$
- $a_{2}+b_{2}=c_{2}=b_{3}$
- $a_{3}×b_{3}=c_{3}$

You can write down these in a table:

$a$ (left input) | $b$ (right input) | $c$ (output) | $s$ (selector) | |
---|---|---|---|---|

Gate 1 | $a_{1}$ | $b_{1}$ | $c_{1}$ | 1 |

Gate 2 | $a_{2}$ | $b_{2}$ | $c_{2}$ | 1 |

Gate 3 | $a_{3}$ | $b_{3}$ | $c_{3}$ | 0 |

Notice the **selector** input $s$, where it is denoted as 1 for addition gates, and 0 for multiplication gates. With this, the entire circuit can be captured by the following equation:

$(s_{i})(a_{i}+b_{i})+(1−s_{i})(a_{i}×b_{i})−c_{i}=0$

Theoretically, you can capture any kind of computation using this model, but still, using addition and multiplication alone is a bit constraining set of functionality. We would in particularly like to have specialized parts of a circuit that can be re-used, say for elliptic curve operations or hash functions; saving us a lot of time (and decreasing the number of rows in the table)!

## Example: Using Hash Functions for Signature

Consider an example:

- Key generation:
- For the secret key, just sample $s_{k}ˉ ∈B$ where $B={0,1}_{32}$. The bar over $s_{k}$ denotes that it is a binary representation.
- $p_{k}=F(H(skˉ))$ which is the hash of $s_{k}ˉ $ mapped to some Field element.

- Signing a message $mˉ∈B$:
- First, pick a random $rˉ∈B$.
- Your signature is $σ=F(H(rˉ,s_{k}ˉ ,mˉ))$

So let us construct our circuit $C(pk,mˉ,σ,s_{k}ˉ ,rˉ)$. This circuit must check the following:

- Ensure that given variables are in the defined binary set: $rˉ,s_{k}ˉ ,mˉ∈B$
- Recreate the signature: $σˉ=H(rˉ,s_{k}ˉ ,mˉ)$
- Ensure that the given signature key matches the derived one: $σ=F(σˉ)$
- Ensure that public key is derived from the secret key: $p_{k}ˉ =H(skˉ)$
- Ensure that the given public key matches the derived one: $p_{k}=F(p_{k}ˉ )$

Working with binary is expensive in circuits, because technically you are checking if a given linear combination of field elements times some multiple of two is equal to some other field element, e.g. $35=2_{5}×1+2_{4}×0+2_{3}×0+2_{2}×0+2_{1}×1+2_{0}×1$.

## Decomposing Circuits to Binary Sets

For the sake of this example, let us have 3-bit numbers only (rather than 256 as most people use). You might have a number $cˉ=[c_{3},c_{2},c_{1}]∈B$ where $B={0,1}_{3}$. This gives us the constraint of $c=c_{3}+2c_{2}+4c_{1}=c_{3}+2×(c_{2}+2×(c_{1}+2×0))$.

When we look at the second formulation, we realize that the same operation ($…+2×(…))$ is happening a lot of times repetitively! Now let us do some renaming:

- $a_{0}=0$
- $a_{1}=c_{1}+2×a_{0}=c_{1}$
- $a_{2}=c_{2}+2×a_{1}=c_{2}+2×c_{1}$
- $a_{3}=c_{3}+2×a_{2}=c_{3}+2×c_{2}+4×c_{1}=c$

This way, notice that we are always doing the same operation on some other variable $a_{i}$. Let us write a table for these.

$i$ (index) | $b$ (bits) | $a$ (accumulation) |
---|---|---|

0 | $b_{0}=c$ | $a_{0}=0$ |

1 | $b_{1}=c_{1}$ | $a_{1}=c_{1}$ |

2 | $b_{2}=c_{2}$ | $a_{2}=c_{2}+2c_{1}$ |

3 | $b_{3}=c_{3}$ | $a_{3}=c$ |

There are some constraints to be written from this table:

- We need to make sure $b_{i}$ is a bit for $i=1,2,3$. We can do that simply by $b_{i}−b_{i}=0$.
- We also need to make sure $a_{i}$ is computed correctly. We can do that by: $a_{i}−b_{i}−2a_{i−1}=0$ for $i=1,2,3$.
- For $a_{0}$, we have the constraint $a_{0}=0$.
- Finally, for $b_{0}$ we have the constraint $b_{0}−a_{3}=0$.

We will capture all these constraints with a polynomial. For that, we use something called **Lagrange Interpolation**. Denote $ω$ as a root of unity. Let $H:={1,ω,ω_{2},ω_{3}}$. We had 3 bits in our example, and our table has 3+1 rows, so that is why we use this degree. In this case, $ω_{4}=ω_{0}=1$ which is as it is a root of unity.

Construct a set of Lagrange polynomials $L_{0}[X],L_{1}[X],…$ which gives us a really nice property:

$L_{j}(w_{i})={10 i=ji=j $

Now consider an element $a∈F_{4}$. We will also have a polynomial:

$a~(x)=a_{0}L_{0}(x)+a_{1}L_{1}(x)+…$

This is a really neat polynomial where we can select values of $a$ such as: $a~(ω_{i})=a_{i}$. You can create one for $b$ with the same procedure.

Let us revisit the constraints from before:

Applied Indices | Constraint | Selector | Polynomial Constraint |
---|---|---|---|

1, 2, 3 | $b_{i}−b_{i}=0$ | $S~(x)$ | $b(x)_{2}−b(x)=0$ |

1, 2, 3 | $a_{i}−b_{i}−2a_{i−1}$ | $S~(x)$ | $a(x)−b(x)−2a~(ω_{−1}x)=0$ |

0 | $a_{i}=0$ | $1−S~(x)$ | $a~(x)=0$ |

0 | $b_{i}−a_{i−3}=0$ | $1−S~(x)$ | $b(x)−a(ω_{3}x)=0$ |

Then you will make a single polynomial out of these, that the verifier can query at random points!

# Lookup Tables

Consider a computation like $c_{i}=a_{i}⊕b_{i}$ where $⊕$ is the XOR operation. Calculating this every time in the proof and writing the constraints for it will be costly. Instead, you could have a large table that shows all possible operation for the XOR (for example if $a,b,c∈{0,1}$ then the table has 4 rows, literally just the truth table for XOR operation) and simply make the argument "is there a row in this table with $a_{i},b_{i},c_{i}$? This is what is called a **Lookup Argument**. It is an optimization method to save from computation time, although generating the table could take time.

Think of the following problem, you have a $w$ and you would like to show that $w∈{0,3,4,7}$ which is a set and is known publicly. You would like to prove $w$ is in this set without revealing what $w$ is! (Set Membership Proof)

## Range Proof

For a private $w$, we would like to prove $w∈[0,2_{3})$. Proofs like this appear a lot of times in SNARKs.

One of the ways this is done is via binary decompositions: $∃b_{0},b_{1},b_{2}∈{0,1}$ such that $w=b_{0}+2b_{1}+4b_{2}$ where all $b_{i}$ are secret too (otherwise you would reveal $w$ somewhat). We write this as:

- $−w+b_{0}+2b_{1}+4b_{2}=0$

There are additional constraints to ensure that $b_{i}$ is a bit, which is done by $b_{i}−b_{i}=0$ (one for each $i$):

- $b_{0}×b_{0}−b_{0}=0$
- $b_{1}×b_{1}−b_{1}=0$
- $b_{2}×b_{2}−b_{2}=0$

### Rank-1 Constraint System

Let us construct the R1CS for this set of constraints.

$ 0000 0100 0010 0001 wb_{0}b_{1}b_{2} × 0000 0100 0010 0001 wb_{0}b_{1}b_{2} − 1000 −1100 −2010 −4001 wb_{0}b_{1}b_{2} = 0000 $

If you look at the calculations here for each element in the resulting vector, it captures all the four constraints! This literally captures the R1CS for the proof of $w∈[0,2_{3})$. Again, note that this set is public, but $w$ is not.

### Using a Table

So again, let us consider the same example: for some private $w$, prove that $w∈[0,2_{3})$. We will use a table this time:

0 | 5 |

1 | 6 |

2 | 7 |

3 | - |

4 | - |

We want to commit to a set of values in a table. We can do that by making a polynomial with the coefficients as these values. Suppose these values are $a_{0},a_{1},a_{2}$. Then, construct a polynomial:

$f(x)=a_{0}L_{0}(x)+a_{1}L_{1}(x)+a_{2}L_{2}(x)$

where $L_{0},L_{1},L_{2}$ are the Lagrange polynomials over the public set $V={ω_{0},ω_{1},ω_{2}}$ where $ω$ is a root of unity. What is a root of unity? It is a value such that $ω_{i}≡1(modp)$, also known as an $n$-th root of unity.

The thing about Lagrange polynomial is that $L_{0}(x)$ is the unique polynomial such that:

- $L_{0}(w_{0})=1$
- $L_{0}(w_{1})=0$
- $L_{0}(w_{2})=0$

When you use roots of unity, these polynomials turn out to be really quick to compute thanks to Fast Fourier Transform, but that is a bit too much detail to go into here.

Now, if you were to open $a_{1}$ on $f$, all you do is show that $f(w_{1})=a_{1}$. For this, you do the following constraint:

$f(x)−a_{1}=(x−w_{1})q(x)$

for some quotient polynomial $q(x)$.

**The rest of the video talks about HALO2, which I have not yet noted down.**