Improvements for comments/documentation

Some comments do not reflect the current implementation. This makes understanding the code more difficult and can cause mistakes when making changes to the code or writing code that uses the bigfield class.

Comment documenting is_composite

The constant is_composite in bigfield.hpp is documented as follows:

static constexpr bool is_composite = true; // false only when fr is native

The usage of r and fr here is potentially confusing, since elsewhere in bigfield, r and Fr are used to refer to the actual native scalar field over which the circuit is defined. An example is the following comment:

// the rationale of the expression is we should not overflow Fr when applying any bigfield operation (e.g. *) and
// starting with this max limb size

The comment documenting is_composite might thus be clearer if formulated for example as follows:

static constexpr bool is_composite = true; // false only when the modulus is the native one

In addition, note that in the documentation↗, the native field is noted ${\mathbb{F}}_n$. A unified notation should be used throughout the code and the documentation to avoid confusion.

Misplaced comment in operator-

See this comment in operator-:

/**
* Plookup bigfield subtractoin
*
* We have a special addition gate we can toggle, that will compute: (w_1 + w_4 - w_4_omega + q_arith = 0)
* This is in addition to the regular addition gate
*
* We can arrange our wires in memory like this:
*
*   |  1  |  2  |  3  |  4  |
*   |-----|-----|-----|-----|
*   | b.p | a.0 | b.0 | c.p | (b.p + c.p - a.p = 0) AND (a.0 - b.0 - c.0 = 0)
*   | a.p | a.1 | b.1 | c.0 | (a.1 - b.1 - c.1 = 0)
*   | a.2 | b.2 | c.2 | c.1 | (a.2 - b.2 - c.2 = 0)
*   | a.3 | b.3 | c.3 | --- | (a.3 - b.3 - c.3 = 0)
*
**/

It appears to fit better with the method evaluate_non_native_field_subtraction of the UltraCircuitBuilder_<Arithmetization> class, since that is where the wires are actually set and used.

Typo in operator- comment

In operator-, there is the following comment:

/**
 * Update the maximum possible value of the result. We assume here that (*this.value) = 0
**/

This should say Update the maximum possible value of the result. We assume here that other.value = 0 to be correct.

Typo in mul_product_overflows_crt_modulus functions

Both the function mul_product_overflows_crt_modulus functions refer to the ctf modulus:

/**
     * Check that the maximum value of a bigfield product with added values overflows ctf modulus.
     *
     * @param a_max multiplicand maximum value
     * @param b_max multiplier maximum value
     * @param to_add vector of field elements to be added
     *
     * @return true if there is an overflow, false otherwise
     **/

It should be the CRT modulus.

Documentation comment for operator*

The operator* documentation comment states the following:

/**
 * Evaluate a non-native field multiplication: (a * b = c mod p) where p == target_basis.modulus
 *
 * We compute quotient term `q` and remainder `c` and evaluate that:
 *
 * a * b - q * p - c = 0 mod modulus_u512 (binary basis modulus, currently 2**272)
 * a * b - q * p - c = 0 mod circuit modulus
 **/

However, the value stored in modulus_u512 is the target prime. What is intended in the second-to-last line is mod binary_basis.modulus (binary basis modulus, currently 2**272).

Misleading comment in unsafe_evaluate_multiply_add

The unsafe_evaluate_multiply_add function has the following comment:

// N.B. this method also evaluates the prime field component of the non-native field mul
const auto [lo_idx, hi_idx] = ctx->evaluate_non_native_field_multiplication(witnesses, false);

bb::fr neg_prime = -bb::fr(uint256_t(target_basis.modulus));
field_t<Builder>::evaluate_polynomial_identity(left.prime_basis_limb,
                                               to_mul.prime_basis_limb,
                                               quotient.prime_basis_limb * neg_prime,
                                               -remainder_prime_limb);

The comment could be read to suggest that the method evaluate_non_native_field_multiplication called immediately below it evaluates the prime field component of the non-native field multiplication. This is, however, not the case. This evaluation is instead done by the call to evaluate_polynomial_identity below.

Typo in decompose_into_bits documentation comments

There is a typo in the documentation comments for decompose_into_bits in cpp/src/barretenberg/stdlib/primitives/field/field.cpp: the names y_lo and y_hi are swapped in the subtraction table.

Typo in Plonk-gate explanation in field.hpp

Similarly, at the bottom of cpp/src/barretenberg/stdlib/primitives/field/field.hpp, there is the following comment,

* A Plonk gate is a mix of witness values and selector values. e.g. the regular PLONK arithmetic gate checks that:
*
*      w_1 * w_2 * q_m + w_1 * q_1 + w_2 * w_2 + w_3 * q_3 + q_c = 0

where it seems there is a typo, and the w_2 * w_2 summand should be w_2 * q_2.

Meaning of num_products argument for reduction_check

The reduction_check function parameter num_products is documented as follows:

/**
* REDUCTION CHECK

...

*
* @param num_products The number of products a*b in the parent function that calls the reduction check. Needed to
*limit overflow
**/

However, the meaning of the parameter num_products, needed to limit overflows, is unclear. It may be interpreted as the number of products $a\cdot b\cdot c\cdot \dots$ or the number of products in a sum $\sum a_i\cdot b_i$.

The code only calls the function with num_products=1, where the two interpretations do not differ. We recommend to either document more clearly how num_products is intended or remove that argument.

Endianness documentation

Different functions in the codebase make different endianness assumptions. For example, the bigfield(const byte_array<Builder>& bytes) constructor interprets the byte array as big endian. In contrast, the binary limbs of bigfield elements are stored in little endian, and other functions, such as UltraCircuitBuilder_<Arithmetization>::decompose_non_native_field_double_width_limb return little-endian values as well.

We thus recommend to document for each function, in which both little- or big-endian order for arguments or return values would be possible, which of the two is used.

Documentation comments for evaluate_non_native_field_multiplication

The function UltraCircuitBuilder_<Arithmetization>::evaluate_non_native_field_multiplication in cpp/src/barretenberg/stdlib_circuit_builders/ultra_circuit_builder.cpp is documented as follows:

/**
 * @brief Queue up non-native field multiplication data.
 *
 * @details The data queued represents a non-native field multiplication identity a * b = q * p + r,
 * where a, b, q, r are all emulated non-native field elements that are each split across 4 distinct witness variables.
 *
 * Without this queue some functions, such as bb::stdlib::element::multiple_montgomery_ladder, would
 * duplicate non-native field operations, which can be quite expensive. We queue up these operations, and remove
 * duplicates in the circuit finishing stage of the proving key computation.
 *
 * The non-native field modulus, p, is a circuit constant
 *
 * The return value are the witness indices of the two remainder limbs `lo_1, hi_2`
 *
 * N.B.: This method does NOT evaluate the prime field component of non-native field multiplications.
 **/

This suggests the function queues up multiplication checks. However, the function actually directly handles the relevant constraints and does not involve any queueing.

Documenting assumptions for to_byte_array

The bigfield::to_byte_array function can be used in circuit to serialize a bigfield element to a byte array of 32 bytes. It has a counterpart in a bigfield constructor taking a byte_array<Builder> as an argument, which deserializes a byte array to a bigfield again. The to_byte_array function is implemented as follows:

byte_array<Builder> to_byte_array() const
{
    byte_array<Builder> result(get_context());
    field_t<Builder> lo = binary_basis_limbs[0].element + (binary_basis_limbs[1].element * shift_1);
    field_t<Builder> hi = binary_basis_limbs[2].element + (binary_basis_limbs[3].element * shift_1);
    // n.b. this only works if NUM_LIMB_BITS * 2 is divisible by 8
    //
    // We are packing two bigfield limbs each into the field elements `lo` and `hi`.
    // Thus, each of `lo` and `hi` will contain (NUM_LIMB_BITS * 2) bits. We then convert
    // `lo` and `hi` to `byte_array` each containing ((NUM_LIMB_BITS * 2) / 8) bytes.
    // Therefore, it is necessary for (NUM_LIMB_BITS * 2) to be divisible by 8 for correctly
    // converting `lo` and `hi` to `byte_array`s.
    ASSERT((NUM_LIMB_BITS * 2 / 8) * 8 == NUM_LIMB_BITS * 2);
    result.write(byte_array<Builder>(hi, 32 - (NUM_LIMB_BITS / 4)));
    result.write(byte_array<Builder>(lo, (NUM_LIMB_BITS / 4)));
    return result;
}

Note that this function only produces a byte array from which the bigfield can be recovered using the mentioned constructor if lo and hi are at most 136 and 120 bits wide, respectively. This is also ensured by the byte_array constructor being used, which is documented in parts as follows:

* @brief Create a byte_array out of a field element.
*
* @details The length of the byte array will default to 32 bytes, but shorter lengths can be specified.
* If a shorter length is used, the circuit will NOT truncate the input to fit the reduced length.
* Instead, the circuit adds constraints that VALIDATE the input is smaller than the specified length
*
* e.g. if this constructor is used on a 16-bit input witness, where `num_bytes` is 1, the resulting proof will fail.

However, the bigfield::to_byte_array has no documenting comments indicating the requirements on the limbs' maximum size. Note that it does not suffice to have called reduction_check on the bigfield element before, as this, for example, allows up to 117-bit wide values for the second limb, so lo could be up to 185 bits wide. We recommend to document the requirements for to_byte_array to avoid a caller inadvertently creating completeness issues by failing to reduce the input when necessary. It could also be considered to create a variant of reduction_check, which reduces the element whenever it does not have reduced form (so whenever the lower three limbs are possibly more than 68 bits wide, rather than the 117 for reduction_check), and to call that at the start of to_byte_array.