Domain

needs a domain to encode the circuit on (for each point we can encode a row/constraint/gate). We choose a domain such that it is a multiplicative subgroup of the scalar field of our curve.

2-adicity

Furthermore, as FFT (used for interpolation, see the section on FFTs) works best in domains of size for some , we choose to be a subgroup of order .

Since the pasta curves both have scalar fields of prime orders and , their multiplicative subgroup is of order and respectively (without the zero element). The pasta curves were generated specifically so that both and are multiples of .

We say that they have 2-adicity of 32.

Looking at the definition of one of the pasta fields in Rust you can see that it is defined specifically for a trait related to FFTs:

#![allow(unused)]
fn main() {
impl FftParameters for FqParameters {
    type BigInt = BigInteger;

    const TWO_ADICITY: u32 = 32;

    #[rustfmt::skip]
    const TWO_ADIC_ROOT_OF_UNITY: BigInteger = BigInteger([
        0x218077428c9942de, 0xcc49578921b60494, 0xac2e5d27b2efbee2, 0xb79fa897f2db056
    ]);
}

The 2-adicity of 32 means that there’s a multiplicative subgroup of size that exists in the field. The code above also defines a generator for it, such that and for (so it’s a primitive -th root of unity).

Lagrange’s theorem tells us that if we have a group of order , then we’ll have subgroups with orders dividing . So in our case, we have subgroups with all the powers of 2, up to the 32-th power of 2.

To find any of these groups, it is pretty straight forward as well. Notice that:

  • let , then and so generates a subgroup of order 31
  • let , then and so generates a subgroup of order 30
  • and so on…

In arkworks you can see how this is implemented:

#![allow(unused)]
fn main() {
let size = n.next_power_of_two() as u64;
let log_size_of_group = ark_std::log2(usize::try_from(size).expect("too large"));
omega = Self::TWO_ADIC_ROOT_OF_UNITY;
for _ in log_size_of_group..Self::TWO_ADICITY {
    omega.square_in_place();
}
}

this allows you to easily find subgroups of different sizes of powers of 2, which is useful in zero-knowledge proof systems as FFT optimizations apply well on domains that are powers of 2. You can read more about that in the mina book.

Efficient computation of the vanishing polynomial

For each curve, we generate a domain as the set . As we work in a multiplicative subgroup, the polynomial that vanishes in all of these points can be written and efficiently calculated as . This is because, by definition, . If , then for some , and we have:

This optimization is important, as without it calculating the vanishing polynomial would take a number of operations linear in (which is not doable in a verifier circuit, for recursion). With the optimization, it takes us a logarithmic number of operation (using exponentiation by squaring) to calculate the vanishing polynomial.