Domains

Note that so far we have exploited a convenient structure to verify the correctness of a computation: that of evaluating polynomials on a set of points (or indexes) $I$ and checking constraints by means of quotient polynomials. This way we could almost bring the computational time of the verifier to a constant. But there is a catch: computing the vanishing polynomials $Z$ and $Z_1$ as the multiplication of $(x-i)$ monomials, although not a very expensive operation is still dependent on the number of rows of the circuit (which corresponds to the maximum polynomial degree $d$). Also, the way we check constraints $f_1$ and $f_2$, by comparing values in a given row with the next row, and by considering a different index set $I^{\prime }=I\setminus \{3,4\}$ is not very general. What if we want to evaluate a circuit where connections between gates are different, do we have to define a new polynomial for each constraint by hand and carefully think about which domain to evaluate?

To address this issues, and to improve efficiency even more, let us introduce a different type of indexing: using a multiplicative subgroup (also referred to commonly as a domain). A particularly interesting set of domains are the ones with size $n=2^k$. Mathematically we want to find a set of points $\mathrm{\Omega }\in {\mathbb{F}}_p$ such that:

$$\mathrm{\Omega }=\{\omega ,{\omega }^2,\dots ,{\omega }^{2^k-1},1\}$$

for some generator $\omega \in {\mathbb{F}}_p$. This set will replace our previous set of indexes $I$. One immediate advantage of this choice is that computing the vanishing polynomial for the domain can be done in constant time, because $Z=x^n-1$, and we no longer need to multiply each monomial $(x-i)$ as we did with the additive indexes. This follows immediately from the definition of $\mathrm{\Omega }$ given that each element is a so-called "$n$-root of unity", a field element of order $n$: for every ${\omega }^i\in \mathrm{\Omega }$, it holds $({\omega }^i{)}^n=({\omega }^n{)}^i=1^i=1$.

Exercise 11

Find a generator $\omega$ of a domain of order $4$ using the following algorithm. Consider $r=(p-1)/4$. Find the smallest $h\in {\mathbb{F}}_p$ such that $\omega =h^r$ has multiplicative order $4$. In other words, ${\omega }^4=1$ and ${\omega }^i\ne 1$ for $i\in \{1,2,3,4\}$.

n = pow(2,2)

#Solve here!
r = 
h = 
ω =

If computed correctly you should obtain:

$$\omega =21888242871839275217838484774961031246007050428528088939761107053157389710902$$

Note that a further interesting property of working with multiplicative indexes is that they "wrap around", that is, whenever we go beyond the order of the multiplicative group, we cycle back to the beginning of the group: ${\omega }^0={\omega }^n=1$. We will benefit from this property in the next section, were we generalize wiring constraints.