Fast amortized KZG commitments

[joebebel]

Description

This is an implementation of fast amortized KZG commitments with additional details from here and here and here

Definitely a "work in progress" but early-stage review, feedback, critique is appreciated.

[Pratyush]

Thanks for the PR! Left some comments

[joebebel]

I added more comments to the SubproductDomain algorithms

[Pratyush]

this looks great, modulo the nits and the bug fix!

[alxiong]

I stumble onto this stale PR yesterday, for those who want to use this FK23 today(Fast amortized KZG https://eprint.iacr.org/2023/033.pdf), we have an implementation in Jellyfish library. (relevant PR: initial work, follow-up refactor)

Essentially, you can go to: jellyfish/primitives/pcs/univariate_kzg/mod.rs::UnivariateKzgPCS::multi_open() for general multi-points opening, and the multi_open_rou_*() APIs in the same file that are specialized for roots of unity (faster)

Of independent interest, you can find

• Toeplitz Matrix multiplication implementation in jellyfish/primitives/toeplitz.rs
• our generalization of DensePolynomial in arkwork in jellyfish/primitives/pcs/poly.rs::GeneralDensePolynomial<T: GroupCoeff<F>, F: Field>
  • this allows polynomial whose coeffs can be both fields and groups elements. (this is useful when computing multi-proofs in the FK23)
  • imo, this actually should be eventually be pushed to upstream arkwork lib, since the underlying fft-related API in arkwork already implicitly support trait GroupCoeffs

(we are open-sourced under permissive license, so feel free to grab whichever subcomponent you find useful.)