batch univariate KZG

[mrain]

Reference: https://eprint.iacr.org/2020/1536.pdf (Appendix C)

Reference implementation: EspressoSystems/hyperplonk#53

• single poly, multiple points
• single point, multiple poly
• multi poly, multi points

(possible ref: https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html, https://eprint.iacr.org/2023/033.pdf)

[chancharles92]

For Verifiable Information Dispersal, we only need to implement the API in https://eprint.iacr.org/2023/033.pdf

[alxiong]

Plan for FK23

• Define Circulant matrix
  • [x] figure out API for FFT for group elements
  • [x] impl matrix mul
• Define Toeplitz matrix
  • [x] impl Toeplitz -> Circulant transform
  • [x] test matrix mul
• [x] Implement fast (and general so that coeff can be group elems) poly evaluation algorithm
• Putting them together
  • [x] design interfaces for choosing different batching techniques (leave room/flexibility for future addition of other batching techniques)
  • [x] impl FK23 by using components above

[chancharles92]

close after #231

[alxiong]

Oh actually, I wish to keep this issue open for other batching scheme impl later.

[chancharles92]

OK, can we create a issue particularly for FK23 then? And close the one for FK23