VID ADVZ: aggregate KZG proofs when multiplicity > 1

[ggutoski]

The ADVZ scheme specifies only 1 evaluation per polynomial. Thus, communication to storage nodes includes k polynomial evaluations + k polynomial commitments. As suggested by @chancharles92 we could reduce the number of polynomial commitments by a factor of t by allowing t evaluations per polynomial. [EDIT: the quantity t is called multiplicity.]

This will complicate the generation and verification of KZG proofs but it should still be practical. Currently we need only a batch proof + verification for evaluations of k polynomials at a single point j. This feature will require a batch proof for evaluations of k polynomials at multiple points j_1,...,j_t.

[chancharles92]

Let each node receive t evaluations per polynomial doesn't necessarily mean we need to change anything about the KZG generation/verification. For now, we can simply let each storage node receive t KZG individual evaluation proofs, one per evaluation point.

[ggutoski]

True. On the upside, we easily save space for polynomial commitments in the size-critical Common struct that is broadcast to all storage nodes. 🙂