Missing limb maximum-value check
Description
The self_reduce function reduces a bigfield element to a representation of at most the bit width as the emulated modulus . An assumption is made that a value quotient_limb that is calculated has at most NUM_LIMB_BITS bits, as is also mentioned in the following comment:
// TODO: implicit assumption here - NUM_LIMB_BITS large enough for all the quotientHowever, it is not checked whether this assumption holds.
Impact
There does not seem to be direct impact, as the relevant limb is constructed with maximum value taken from the actual maximum value for the quotient, and it is separately checked that that size is small enough to not cause problems with an overflow of the CRT modulus in unsafe_evaluate_multiply_add.
Recommendations
Instead of making an implicit assumption, we recommend asserting it:
template <typename Builder, typename T> void bigfield<Builder, T>::self_reduce() const
{
// Warning: this assumes we have run circuit construction at least once in debug mode where large non reduced
// constants are disallowed via ASSERT
if (is_constant()) {
return;
}
// TODO: handle situation where some limbs are constant and others are not constant
const auto [quotient_value, remainder_value] = get_value().divmod(target_basis.modulus);
bigfield quotient(context);
uint512_t maximum_quotient_size = get_maximum_value() / target_basis.modulus;
uint64_t maximum_quotient_bits = maximum_quotient_size.get_msb() + 1;
if ((maximum_quotient_bits & 1ULL) == 1ULL) {
++maximum_quotient_bits;
}
- // TODO: implicit assumption here - NUM_LIMB_BITS large enough for all the quotient
+ ASSERT(maximum_quotient_bits <= NUM_LIMB_BITS)
uint32_t quotient_limb_index = context->add_variable(bb::fr(quotient_value.lo));Remediation
This issue has been acknowledged by Aztec, and a fix was implemented in commit 6d3556c5↗.