Assessment reports>Barretenberg Bigfield>Discussion>Unnecessary assert in mul_product_overflows_crt_modulus

Unnecessary assert in mul_product_overflows_crt_modulus

The two functions mul_product_overflows_crt_modulus are used to check if terms of the form would overflow modulo the CRT modulus , where is the native circuit prime modulus. One variant is for the case in which — otherwise they are identical. The single-product variant is implemented as follows:

static bool mul_product_overflows_crt_modulus(const uint1024_t& a_max,
                                                  const uint1024_t& b_max,
                                                  const std::vector<bigfield>& to_add)
{
    uint1024_t product = a_max * b_max;
    uint1024_t add_term;
    for (const auto& add : to_add) {
        add_term += add.get_maximum_value();
    }
    constexpr uint1024_t maximum_default_bigint = uint1024_t(1) << (NUM_LIMB_BITS * 6 + NUM_LAST_LIMB_BITS * 2);

    // check that the add terms alone cannot overflow the crt modulus. v. unlikely so just forbid circuits that
    // trigger this case
    ASSERT(add_term + maximum_default_bigint < get_maximum_crt_product());
    return ((product + add_term) >= get_maximum_crt_product());
}

It is unclear what the reason of the assertion add_term + maximum_default_bigint < get_maximum_crt_product() is here. The comment suggests the intention to forbid cases in which the sum ( in the expression at the start) would already overflow. This would be the check add_term < get_maximum_crt_product(), so it is unclear why maximum_default_bigint is added.

Note that we have the following bound for get_maximum_crt_product:

get_maximum_crt_product() = r*2^t = r * 2^(4*68) > (r-1) * 2^(272)

The maximum value an unreduced bigfield could possibly attain is one in which all four binary limbs are r-1. This value is

(r-1)*(1 + 2^68 + 2^(2*68) + 2^(3*68)) < (r-1) * 2^(3*68+1) = (r-1) * 2^205

The number of addition terms needed to overflow the CRT modulus in a sum are thus at least 2^(272-205) = 2^67. This is an unrealistic number of summands, so such an overflow should never happen in practice.

The value of maximum_default_bigint is 2^(2*s), where s is the number of bits of p. Note that s<=256 as the emulated prime can be at most 256 bits. Thus, the number of addition terms needed for add_term + maximum_default_bigint >= get_maximum_crt_product() to be possible is at least

  ((r-1) * 2^272 - 2^512)  /  ((r-1) * 2^205)
> (2^253 * 2^272 - 2^512)  /  (2^254 * 2^205)
= (2^525 - 2^512) / 2^459
> 2^525 / 2^459
= 2^66

This is still an unrealistic number of summands, so the current assert should also never trigger in practice.

The maximum value get_maximum_value() can return for a bigfield element is less than 2^(256+3*68)=2^460, so a product of two such values will be less than 2^920. Thus, an overflow due to adding product is also not possible in practice, as long as a_max and b_max are obtained from such a call to get_maximum_value().

Zellic © 2025Back to top ↑