# Vanishing argument

Having committed to the circuit assignments, the prover now needs to demonstrate that the various circuit relations are satisfied:

- The custom gates, represented by polynomials $gate_{i}(X)$.
- The rules of the lookup arguments.
- The rules of the equality constraint permutations.

Each of these relations is represented as a polynomial of degree $d$ (the maximum degree of any of the relations) with respect to the circuit columns. Given that the degree of the assignment polynomials for each column is $n−1$, the relation polynomials have degree $d(n−1)$ with respect to $X$.

In our example, these would be the gate polynomials, of degree $3n−3$:

- $gate_{0}(X)=a_{0}(X)⋅a_{1}(X)⋅a_{2}(Xω_{−1})−a_{3}(X)$
- $gate_{1}(X)=f_{0}(Xω_{−1})⋅a_{2}(X)$
- $gate_{2}(X)=f_{0}(X)⋅a_{3}(X)⋅a_{0}(X)$

A relation is satisfied if its polynomial is equal to zero. One way to demonstrate this is to divide each polynomial relation by the vanishing polynomial $t(X)=(X_{n}−1)$, which is the lowest-degree monomial that has roots at every $ω_{i}$. If relation's polynomial is perfectly divisible by $t(X)$, it is equal to zero over the domain (as desired).

This simple construction would require a polynomial commitment per relation. Instead, we commit to all of the circuit relations simultaneously: the verifier samples $y$, and then the prover constructs the quotient polynomial

$h(X)=t(X)gate_{0}(X)+y⋅gate_{1}(X)+⋯+y_{i}⋅gate_{i}(X)+… ,$

where the numerator is a random (the prover commits to the cell assignments before the verifier samples $y$) linear combination of the circuit relations.

- If the numerator polynomial (in formal indeterminate $X$) is perfectly divisible by $t(X)$, then with high probability all relations are satisfied.
- Conversely, if at least one relation is not satisfied, then with high probability $h(x)⋅t(x)$ will not equal the evaluation of the numerator at $x$. In this case, the numerator polynomial would not be perfectly divisible by $t(X)$.

## Committing to $h(X)$

$h(X)$ has degree $(d−1)n−d$ (because the divisor $t(X)$ has degree $n$). However, the polynomial commitment scheme we use for Halo 2 only supports committing to polynomials of degree $n−1$ (which is the maximum degree that the rest of the protocol needs to commit to). Instead of increasing the cost of the polynomial commitment scheme, the prover split $h(X)$ into pieces of degree $n−1$

$h_{0}(X)+X_{n}h_{1}(X)+⋯+X_{n(d−1)}h_{d−1}(X),$

and produces blinding commitments to each piece

$H=[Commit(h_{0}(X)),Commit(h_{1}(X)),…,Commit(h_{d−1}(X))].$

## Evaluating the polynomials

At this point, all properties of the circuit have been committed to. The verifier now wants to see if the prover committed to the correct $h(X)$ polynomial. The verifier samples $x$, and the prover produces the purported evaluations of the various polynomials at $x$, for all the relative offsets used in the circuit, as well as $h(X)$.

In our example, this would be:

- $a_{0}(x)$
- $a_{1}(x)$
- $a_{2}(x)$, $a_{2}(xω_{−1})$
- $a_{3}(x)$
- $f_{0}(x)$, $f_{0}(xω_{−1})$
- $h_{0}(x)$, ..., $h_{d−1}(x)$

The verifier checks that these evaluations satisfy the form of $h(X)$:

$t(x)gate_{0}(x)+⋯+y_{i}⋅gate_{i}(x)+… =h_{0}(x)+⋯+x_{n(d−1)}h_{d−1}(x)$

Now content that the evaluations collectively satisfy the gate constraints, the verifier needs to check that the evaluations themselves are consistent with the original circuit commitments, as well as $H$. To implement this efficiently, we use a multipoint opening argument.