The Feist-Khovratovich technique for computing KZG proofs efficiently relies on exploiting algebraic relationships among KZG quotient polynomials and leveraging the properties of Discrete Fourier Transform (DFT) on roots of unity.

In general, the quotient polynomial in KZG proof can be calculated directly as $q(x)=\frac{f(x)-v}{x-u}$. The FK technique demonstrates that the KZG commitments to the quotient polynomials are algebraically related when the evaluation points are roots of unity ($w^i$’s). This means that the proofs can be efficiently computed and manipulated due to these relationships.

In NomosDA, we also evaluate the proofs for roots of unities. Hence, we can apply this method to speed up the calculations of proofs. Given a polynomial $𝑓(x)$ of degree $d$, we can compute all $n$ KZG proofs for $f(w^i)$, $i\in$$[0,n-1]$ in $𝑂(n\log⁡n)$ time. Here is the brief explanation of algorithm:

• We can represent the quotient polynomial for roots of unity as $q_i(x)=\frac{f(x)-f(w^i)}{x-w^i}$ and the evaluation proof $\pi_i$ for $f(w^i)$ as $\pi_i = g^{q_i(\tau)}=g^{\frac{f(\tau)-f(w^i)}{\tau-w^i}}$
• The general idea here is focusing on the efficient calculation of $q_i$ polynomials. Therefore, the first thing that comes to mind is how to compute the coefficients of the $q_i$ polynomial quickly.
• If $f$ has a form such that $f(x)=a_0+a_1x+a_2x^2+\cdots+a_dx^d$ , we can say that when dividing $f$ of degree $d$ by $x-w^i$ we obtain a quotient polynomial with coefficients $𝑡_0,𝑡_1,…,𝑡_{d−1}$ such that:
  • $t_{d-1}=a_d$
  • $t_j=a_{j+1}+w^it_{j+1}$ for all $j\in[0,d-1)$
• Hence we can write;
  • $t_{d-1}=a_d$
  • $t_{d-2}=a_{d-1}+w^it_{d-1}=a_{d-1}+w^ia_d$
  • $t_{d-3}=a_{d-2}+w^it_{d-2}=a_{d-2}+w^i(a_{d-1}+w^it_{d-1})=a_{d-2}+w^ia_{d-1}+w^{2i}a_d$
• Hence we can represent $q_i(x)$ as a function with coefficient $a_d's$;
  • $q_i(x)=(a_dx^{d-1}+a_{d-1}x^{d-2}+\dots+a_1)(w^i)^0 + (a_dx^{d-2}+a_{d-1}x^{d-3}+\dots+a_2)(w^i)^1+\dots+a_d(w_i)^{d-1}$

To make this formula simple, we can write $q_i$ as a polynomial of $h_j$ such that;

$q_i(x)=h_1(x)(w^i)^0+h_2(x)(w^i)^1+\dots+h_d(x)(w^i)^{d-1}=\sum_{k=0}^{d-1}h_{j+1}(x)(w^i)^k$

Then;

$q_i(\tau)=\sum_{k=0}^{d-1}h_{j+1}(\tau)(w^i)^k$ and $\pi_i=g^{q_i(\tau)}=\prod_{j=0}^{d-1}H_j^{(w^i)^j}$ where $H_j=g^{h_j(\tau)}$.

This formula gives us DFT of $H_j's$ hence we can easily calculated every proof using DFT method. Also, to use more efficient way, we can use Toeplitz matrix product to generate every $H_j$ such that $[H_1 \quad H_2 \quad H_3 \quad \dots \quad H_{d-1}]=\mathbf{F}.V(\tau)$.

Libraries

https://github.com/Cardinal-Cryptography/Feist-Khovratovich/blob/main/src/lib.rs

https://github.com/caulk-crypto/caulk/blob/main/src/kzg.rs#L87

https://github.com/ethereum/research/tree/master/kzg_data_availability

https://github.com/crate-crypto/peerdas-kzg/tree/master