[low priority] Univariate KZG in evaluation form

[ggutoski]

In some applications of univariate KZG the polynomial is given in evaluation form (as d evaluations p(1),...,p(d) of polynomial p at input points 1,...,d) instead of the conventional coefficient form (as d coefficients of p). Example: KZG as a vector commitment.

Currently we enforce coefficient form at the API level: commit, open and their batch/multi variants all require a Self::Polynomial in coeff form: https://github.com/EspressoSystems/jellyfish/blob/ff340418250c761c345e6aa613175ce82ebca6c1/primitives/src/pcs/mod.rs#L116-L119

This API can be used for polynomials in evaluation form, but it forces the user to do a bunch of unnecessary and expensive FFTs.

It is possible to do all KZG operations natively in evaluation form, with no need for FFT anywhere in the stack: see here. (Skip to "evaluation form" section.)

Suggestions

1. Low-level. Add a mirror API that accepts polynomials in evaluation form. This is a good opportunity to coordinate with #338
2. High-level. Same API. Set Self::Polynomial to a type that abstracts over the underlying representation (coeff vs. eval). Methods such as commit, open, etc select the underlying implementation according to the underlying polynomial representation.

I prefer a low-level solution such as item 1 but that's open to discussion.

[alxiong]

as weekend fun, I wrote down how I think KZG in eval form should work here: https://www.notion.so/espressosys/KZG-in-Evaluation-Form-c58004c5ca7f427f92799aaeea7c6e1a

literature note, Dankrad has indeed described how KZG in eval form should work in his blog post linked above, but he only consider the special case when the polynomial degree d equals to the supported degree in SRS setup n.

where what I wrote is more general for any d<=n, which give rise to two flavors of KZG, one with shorter SRS, one with faster commit.

cc @chancharles92 @ggutoski

again, agree this should be super low priority, given the requirement on new trusted setup for the SRS.

---

update: I think I was mistaken, we don't know new SRS, we can compute the Lagrange poly (of trapdoor) using linear combination of the coefficient form SRS values.