To What Extent does FFT Accelerates Plonk System?

[Pupil1999]

Hi, nb men!

I am confused about some polynomial operations in Plonk using FFT.
In Plonk, we interpolate witness polynomials $a(x),b(x),c(x)$ on subgroup $\{1, w, w^2,...,w^{n-1}\}$, where $n$ is about the size of each witness vector after padding and zero-knowledge randomization. The algorithm runs in $O(NlogN)$ time and we get three vectors of evaluations, each having $n$ elements.

My question comes in Round 3, where we need to compute a quotient polynomial: $t(x)=\frac{a(x)b(x)q_M(x)\cdots}{Z_H(x)}$. If we do the multiplication on FFT subgroup, we take $O(N)$ time, but we can only get totally $n$ evaluations on the subgroup, which will be transformed into a $n$-degree polynomial after inverse FFT. But the $t(x)$ has about $3n$-degree, considering we need to compute $t(x)=x^{2n}t_{hi}(x)+x^{n}t_{mid}(x)+t_{low}(x)$. So actually we need to do inverse FFT before we multiply these polynomials. And the multiplication will take $O(N^2)$ time. So does FFT really accelerate the system asymptotically?

[Pupil1999]

Oh, I notice that although the $|SRS|$ is reduced to about $n$, $|\{w\}|=3n$. So we just pad the evaluations to be $2n$, and interpolate a new polynomial?