An FFT may be saved

[swasilyev]

We can save 1 FFT (of 7) if we compute the h_query points in the evaluation form during the setup. We can similarly avoid the division when computing h by normalizing these points by g^n - 1 (evaluations of the vanishing polynomial on the coset). See the PoC here: https://github.com/achimcc/groth16/pull/1/files

These changes break existing proving keys, though I believe they can be updated. Does it worth the burden?

---

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

[Pratyush]

I believe this is the R1CS-to-QAP reduction used in Circom, right? If so, then we've added partial support for this in #34. The remaining TODO to support this would be to (a) actually implement the new reduction, and (b) generalize the Groth16 struct to allow using different reduction strategies, via the idea in https://github.com/arkworks-rs/groth16/pull/34#issuecomment-883633375