Not enough variety in `add_dummy_constraints` can cause commitment errors for circuits of length 2^k before padding

[lopeetall]

The function add_dummy_constraints uses two arithmetic gates to add witnesses to the circuit. If the circuit itself also uses only arithmetic gates AND the total number of gates is a power of 2, then the circuit is never padded with 0s and the q_arith vector becomes constant which causes an error when committing to q_arith_poly.

Although this is unlikely to happen in a production circuit with many gates it can easily happen in tests of small subcircuits.

Until we implement lookups, all gates (including range, logic, etc.) resolve to arithmetic gates, so it might be tricky to make this work until lookups are enabled and we have a second "elemental" gate. But there may be a way to do it sooner by using an arithmetic selector value > 1.

[bhgomes]

I think the long-term solution here is to have the proof system detect which gates are always on (or always off) and reduce to the minimal quotient polynomial. In this case, it should reduce to omitting q_arith entirely (as well as all the other custom gate selectors).

[lopeetall]

That's a great solution. Should we open a new issue on reducing to the minimal quotient that replaces this one? Or would you consider this a part of #67?

[bhgomes]

I think it's more general than the issue in #67. That issue is about computing the linearisation from the quotient. In general, we want to make the quotient as efficient as possible.

See #79.

[GhostOfGauss]

@lopeetall could you help me understand what it means to have something like q_arith = 2 ?  Does that multiply the equation q_L w_L + ... + q_C =0 by an overall factor of 2?  That seems like an effective short term solution to just change the second of the dummy constraints to use a different value for the arithmetic selector.

[lopeetall]

@GhostOfGauss Yes! Using q_arith = 2 works as you think it does, and it would be a solution to the dummy constraint problem from earlier. I confirmed by double-checking the code that it should work and tried it yesterday but I still got an error. This is how I learned there is an issue in ark-poly-commit.

When ark-poly-commit checks the degree of a polynomial before committing, it fails if the coefficient list is empty OR if the leading coefficient is 0. In the case of your test circuits, the first problem we had was a degree 0 polynomial from q_arith. But after this was fixed there was another problem with q_4 having a leading coefficient of 0 which was also rejected by ark-poly-commit.

I will work on filing an issue at arkworks to fix this. Polynomials with a leading coefficient of 0 happens easily when your polynomial is generated by ifft in arkworks. For some reason they don't trim leading zeros when checking the degree, and I think this is an oversight on their part.

[lopeetall]

I hope that once the degree check is fixed in arkworks, we can to use q_arith = 2 in the dummy constraints as a temporary solution and close this issue. Then #79 will solve it long term.

[GhostOfGauss]

Wow, more complicated than I had expected.  Nice work getting to the bottom of this!  

I'm trying to understand the leading coefficient problem: first off, does "leading" refer to lowest or highest degree coefficient?  Is the idea here just that by chance you can have an interpolation polynomial whose degree is accidentally lower than the maximum degree? Like your points happen to land on some lower-dimensional locus?  I agree it's odd that they wouldn't have trimmed leading zeros.

[lopeetall]

does "leading" refer to lowest or highest degree coefficient?

Highest degree

Is the idea here just that by chance you can have an interpolation polynomial whose degree is accidentally lower than the maximum degree?

Exactly. From messing around with it I found (and Pratyush just confirmed) that leading zeros are trimmed off if you create polynomials from a vector rather than using the raw constructor, which appears to avoid the whole problem.

[lopeetall]

Closing this due to #83