Add degree bounds to Ligero

[Antonio95]

Sometimes, it is crucial that a PCS give the verifier guarantees about the degree of the committed polynomial. poly-commit's trim methods allow the user to enforce degree bounds at the key level, but we don't have any dedicated code to handle that in Ligero (indeed, these bounds are ignored).

Ligero (and its family of linear-code-based PCSs) have a natural degree bound in m*n - 1, where m and n are the number of rows and columns of the unencoded matrix. These parameters are known to the verifier. Therefore, if the user requests a degree bound And it happens to be of that shape, nothing needs to be done. I suspect this is not an infrequent situation (e.g. in Aurora).

Things get more complicated if the user requires a degree bound smaller than that. The immediate way I see to go about it is for the user to reveal as many zeros of the unencoded matrix as it is necessary to confirm the degree claim. For instance, if the user requests degree bound m*n - 2, then it is enough to show that the last element of the unencoded matrix is 0. Smaller degree bound -> more zeros need to be revealed. Of course, the natural way to show these zeros is to open the columns containing them (in addition to the usual column openings). In our FFT implementation of Ligero, the unencoded matrix is interleaved inside the encoded matrix due to the FFT, so this would be easy to implement.

If the number of zeros that needs to be shown is at least equal to the number of columns of the encoded matrix, one would actually need to open all columns, which is a problem. At that point, I believe the well-formedness check can be used (if there is one) to show that the element coming from the random linear combination of the last row is equal to zero. Here things get subtler and there is a lot to discuss. We could leave this case as unimplemented, too.