search

arkworks-rs / sumcheck

linear-time sumcheck protocol for multilinear polynomials and related addends
Apache License 2.0
51 stars 29 forks source link

Sumcheck over DenseMultilinearExtension vs. DenseMVPolynomial #60

Closed mmagician closed 8 months ago

mmagician commented 1 year ago

If I understand correctly, the current API allows running the sumcheck protocol over products of DenseMultilinearExtension. If one wanted to prove knowledge of evaluations over arbitrary multivariate (not just multilinear) g, then sure it's possible by multiplying a few multilinear polynomials, but I feel that this turns out to be unneccearily complex for the end user.

Is there a reason why this API was chosen as such? Perhaps we could rework it to support DenseMVPolynomial instead?

Also would be good to hear how/if poeple use this library in their proof systems, or what would they require from arkworks sumcheck to be practical?

Pratyush commented 1 year ago

I think in general efficient proof systems perform sumcheck over multilinear polynomials, because those are the ones for which (for example) efficient polynomial commitment schemes exist.