bug: subtraction padding in variable-modulus non-native arithmetic does not enforce underflow protection

[ivokub]

Description

The subtraction padding should ensure that we do not underflow when subtracting limbs. For fixed-modulus case we can compute the padding as a constant such that it always is bigger than the value we subtract, but for variable-modulus case we compute the padding on the go. We currently use the same function for the padding computation and add a range check on the limbs of the padding. However, we do not add assertion that it is actually sufficiently big for avoiding underflows.

There are several approaches we can take. We either try to fix it or omit the method and dependent methods.

For the second approach, we do not actually really use it in practice - we need subtraction for var-mod equality assertion which we only use in the tests for checking the results. So there shouldn't be a problem in making the methods private.

For the first approach, we can fix it by checking that pad[i] is greater than 1 << (fp.BitsBerLimb()+overflow+1). And in this case it would really make sense to cache the padding values for different overflow values so that we wouldn't add new constraints every time (padding depends on the overflow).

---

There is additional bug in the subtraction padding hint. There is

padding := f.newInternalElement(res, fp.BitsPerLimb()+overflow+1)

but should be

padding := f.newInternalElement(res, overflow+1)

---

Another bug is that we do not check that nextOverflow here doesn't overflow the native field