david wong

Hey! I'm David, the author of the Real-World Cryptography book. I'm a crypto engineer at O(1) Labs on the Mina cryptocurrency, previously I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

What's two-adicity? posted May 2022

Some elliptic curves (related to zero-knowledge proofs I believe) have been claiming high 2-adicity. But for some reason, it seems a bit hard to find a definition of what this term means. And oddly, it's not a complicated thing to explain. So here's a short note about it.

You can see this being mentioned for example by the pasta curves:

They have the same 2-adicity, 32, unlike the Tweedle curves that had 2-adicity of 33 and 34. This simplifies implementations and may assist in square root performance (used for point decompression and internally to Halo 2) due to a new algorithm recently discovered; 32 is more convenient for this algorithm.

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

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
    ]);

so what's that? Well, simply put, a two-adicity of 32 means that there's a multiplicative subgroup of size $2^{32}$ that exists in the field. And the code above also defines a generator $g$ for it, such that $g^{2^{32}} = 1$ and $g^i \neq 1$ for $i \in [[1, 2^{32}-1]]$ (so it's a primitive $2^{32}$-th root of unity).

Lagrange's theorem tells us that if we have a group of order $n$, then we'll have subgroups with orders dividing $n$. 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 $h = g^2$, then $h^{2^{31}} = g^{2^{32}} = 1$ and so $h$ generates a subgroup of order 31
  • let $h = g^{2^2}$, then $h^{2^{30}} = g^{2^{32}} = 1$ and so $h$ generates a subgroup of order 30
  • and so on...

In arkworks you can see how this is implemented:

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.

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

DD

You write "g^i \neq 1 for i \in [[1, 2^{32}]]"
I'm not sure about your notation, but i must be strictly smaller than 2^{32}, so either exclude it from the interval by using ")" as bracket or subtract 1 of the upper limit.
Other than that: nice post, very informative!

david

Ah good point!

EE

Great writeup! I was confused by this term and came across your post.
It looks like knowing this number is valuable for programming a circuit for a Plonkish system. You need to fit into your application logic within a square region of columns and rows, where a column is a polynomial and the nth row is the nth root of unity. Adding columns adds to the overheads of commitment opening, while adding more rows adds to the prover costs of FFT time. But what is the maximum number of rows you can add? It looks like 2-adicity is the answer. Depending on what curve you use you have different 2-adicity and thus different capacities for the number of rows.

david

the table doesn't have to be square (see my defs here https://hackmd.io/Ct8AYVkaRbuzAF61yv1qYA?view), but you're right that adding columns increase the proof size and adding more rows increase the circuit size and thus increased complexity/space for the prover.

the rows are evaluated over the elements of a subgroup, and it's nice if you have a subgroup of size a power of 2, and so in that sense yeah the 2-adicity is the answer (so 2^32 rows is the max you can reach, but creating a proof for 2^32 rows would probably take a HUGE amount of time and space, so not something you'd want to do :D)

also you can probably non-powers of 2 subgroups, but that would be much less efficient

leave a comment...