Super important SNARK open question: given univariate polys f,g of deg<n, let h be the deg<n poly such h=f*g on a set H of size n. I.e. h=f*g mod Z_H. Can we prove given KZG commitments to f,g,h that h is correct in time O(n) without computing a quotient?

This question and the question of whether we need to switch from univariate to multilinear things like hyperplonk are very much related. Currently I'm tending to think it will be the latter.

Has the problem been thought about extensively at this point, or is it relatively new?

I think relatively new, since it relates to hyperoptimizing snarks in production

but maybe I'm missing some reduction to polynomial multiplication or some other well studied problem

This is basically the problem of polynomial identity testing over the quotient ring, no? A quick search doesn’t reveal anything useful, but I have also never been good at googling math papers

Our current algorithms for this reduce it to PIT over the field, but that seems wasteful, since we’re not leveraging the structure meaningfully

multilinear schemes still have much larger proof sizes, right?

larger proofs and verification time

Right. I wonder if the BDFG algorithm can be adapted to help here

What's BDFG?

is there an easier way to do this with multilinear extensions? could someone point me toward that protocol?

oh wait is it just classical sum check over H of f·g-h?

Good observation. With the tweak that you need to multiply it by something to give you random coefficients

we really keep using the same two or three ideas over and over again, don't we? 🤦‍♀️

not sure I understand the context - is it clear sumcheck doesn't solve the problem as I stated?

oh yes, I'm entirely in agreement with you. I was just making a joke about how often ideas get re-used for SNARKs. (in this case, taking a random linear combination of constraints)

oh also there are other things you can do with univariate polynomials to avoid the need for FFTs: ia.cr/2022/420

Woah didn't know about this idea, that's quite cool! At what point is this faster than the fft? Is there a comparison graph of marlin vs Gemini (time mode) prover times?

I think it's never faster than Marlin, until you run out of memory

(just because of the need to do more MSMs)

Maybe

I think we could do it with a commitment to the low half of f*g (or f*g - h), though in a sense it's just a specialized way of dividing by Z_H. I take it the goal is not just avoiding division algorithms, but avoiding any new commitments?

The goal is getting n instead of nlogn time, so that doesn't necessarily exclude other commitments

If you are fine with significant performance improvement over the univariate strategy, then take the zero-check over the Boolean hypercube from Hyperplonk, which does a multivariate sumcheck to zero on (f(x)*g(x)-h(x))*L(x,y) where L(x,y) is the Lagrange kernel for the hypercube.

(the Lagrange kernel is essentially the eq function in the paper). However, this is only linear time if you already have the values over the cube. If you don't, you need to do an FFT, which is still much faster than in the univariate case, but still O(n*log n) field adds/subs.

If you want to entirely avoid FFTs then you might want to take a look at Gemini's Hadamard check.

But does that work for the univariate question I stated? Or is this all about multivariates? I know that for multilinear I can get O(n), the question is about univariates

Oh, then I completely missed your point. For univariate polynomials over FFT domains H, I don't know.

I might be missing something, but seems like @drakefjustin's Hadamard check would be a direct solution to this? notes.ethereum.org/Il4z42lmQtaUYF…

Trying to understand that. Justin says compute poylnomials c,d such that ab=c+d . Wondering how that's done in linear time when a,b have deg n

Ohh that parts fine he just calls h=c+d and only's talking about equality on H

Yeah I don't think I ever understood this approach till now. This needs to be seriously looked into imo to see how it compares with hyperplonk

One thing to check is how it scales when the verification equations grows from fg-h to a more complex plonkish equation of deg > 2 e.g. fgh+fw... Multivariate sumcheck works well with that

I recall we studied this when first working on Gemini. Yuncong Hu will know much better then me, but I think there's a problem in step 5<->6?

haha...got stuck at the same place going over it last two days! :(