Additive NTT
This article aims to intuitively explain the goals and process of the Additive NTT protocol.
Introduction
Binius is a SNARK constructed using a characteristic-2 finite field. In Binius, RS-encoding (Reed-Solomon encoding) is employed, but there is a challenge: the conventional Radix-2 FFT cannot be utilized in characteristic-2 finite fields. This paper addresses that challenge.
The title of the paper is "Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes." A characteristic-2 finite field is an extension field of the form , which can be constructed as a polynomial ring. Traditionally, polynomials are represented using the Monomial Basis which is a natural choice. However, this paper introduces an ingenious new polynomial basis and proposes an encoding algorithm that achieves performance comparable to the Radix-2 FFT.
Background
Radix-2 FFT
The coefficient form of a univariate polynomial of degree is defined as:
where the basis is .
On the other hand, the evaluation form of a univariate polynomial is defined as:
where the basis is , called the Lagrange basis.
In Radix-2 FFT (Fast Fourier Transform), a Lagrange basis is constructed using the roots of unity. Each basis polynomial is defined as:
Since we use finite fields instead of complex numbers, this is technically a Radix-2 NTT (Number Theoretic Transform), but for simplicity, we'll refer to it as FFT. Radix-2 FFT transforms a polynomial in coefficient form into its evaluation form. The matrix used to multiply the coefficient vector is called a Vandermonde matrix:
The -th roots of unity satisfy:
Since cannot equal , it must equal .
Using the property of , Radix-2 FFT is efficiently computed via the Cooley-Tukey algorithm. The polynomial is divided into two parts:
: even powers of .
: odd powers of .
This gives:
For ,substituting , we have:
This transforms an -point FFT problem into two -point FFT problems.
Define as follows:
For example, for , the recursive computation proceeds as such:
By recursively applying this process, the computational complexity of FFT becomes .
The Inverse FFT (IFFT) converts a polynomial from its evaluation form back to its coefficient form by using the inverse of the Vandermonde matrix:
The IFFT can also be computed in using a similar recursive approach to FFT.
2-adicity
When the modulus of a prime field is of the form , a -th root of unity for can be determined as follows.
In other words, if the order of the multiplicative subgroup of a prime field is of the form , and (also known as the 2-adicity) is large, FFT can be used effectively. Fields with this structure are referred to as FFT-friendly fields.
What about characteristic-2 finite fields, such as ? For these fields, the order of the multiplicative subgroup is . Since the 2-adicity of is 0, Radix-2 FFT cannot be used.
This naturally raises the question: when the characteristic is 2, what new polynomial basis would be suitable? Moreover, to achieve fast computation similar to Radix-2 FFT, the method must recursively reduce the problem into smaller subproblems.Protocol Explanation
NOTE: From this point onward, is no longer a root of unity, and will be newly defined.
Polynomial Basis
The elements of can be represented as the set , where:
Given a basis vector composed of elements from , each can be expressed as:
We define the subspace vanishing polynomial as:
This mean the full form of the vanishing polynomials are as follows:
and so on.
Thus, and the roots of are . This follows from the fact that addition in is XOR, so , a direct result of the field’s characteristic being 2.
Lemma 1. is a -linearized polynomial.
Furthermore, satisfies the following property:
We now define a new polynomial basis as:
where:
The new polynomial basis is as follows:
and so on.
Thus, .
The coefficient form of an -degree univariate polynomial is expressed as:
The evaluation form of this polynomial is:
where is defined as:
We denote the set of evaluations as , defined as such:
Delta Polynomial
The recursive calculation of can be performed by defining as follows:
where .
For , exists as follows:
is equivalent to . For example, is recursively computed as follows:
Lemma 2.
Proof:
Case 1: , both and equal , so the equality holds trivially.
Case 2: , is given as:
which simplifies as follows:
Using Lemma 1:
Since , we know , so:
Case 3: Inductive Step
Assume the equality holds for . At , we have:
By Lemma 1:
Since , we know , thus:
Transform
Define the transform as:
where .
The transform computes . For , this becomes:
Remember that is equivalent to .
can be divided into two parts as follows:
which can be computed from .
which can be computed from .
Part 1.
Since all the right-hand terms are known, the left-hand terms can be determined.
Part 2.
Since can be computed from the Part 1, the left-hand terms can be determined.
When , for , it can be split into and .
When , for , it can be split into and .
Inverse Transform
To compute and from :
Part 1.
where: (Refer to Part 2. in Transform section above.)
Since all the right-hand terms are known, the left-hand terms can be determined.
Part 2.
where (Refer to Part 1. in Transform section above):
Since can be computed from the Part 1, the left-hand terms can be determined.

The diagram above illustrates the data dependencies for transforming and inversely transforming a polynomial of size 8. Each elemetter represents scalar multiplication by .
Conclusion
The method for performing a formal derivative on the Novel Polynomial Basis and its use in the RS erasure decoding algorithm is omitted here due to space constraints. For those interested, please refer to the original paper.

Using the newly proposed Novel Polynomial Basis, the Additive NTT achieves additive complexity and multiplicative complexity without any constraints. Consequently, for the first time, RS-encoding over characteristic-2 finite fields achieves complexity.

Additionally, it is well-known that polynomial multiplication can be optimized using FFT. Similarly, by leveraging the Novel Polynomial Basis, multiplication in characteristic-2 finite fields can also be optimized.
Last updated