L-06: Code Simplifications

[0xisk]

Source: OpenZeppelin Midnight - Compact Contracts Audit

Description

The Uint128 _mul function multiplies two 128-bit numbers by combining all four combinations of 64-bit products. However, the implementation processes intermediate values and carries incrementally, while tracking their original source. For example it first sums the low-half of the cross terms and then later adds the high-half of the lowest term. This adds unnecessary complexity.

Consider aligning the partial products to their respective positions and then processing all 64-bit words at each position in one operation. Here is a sample implementation:

circuit _mul(a: U128, b: U128): U256 {
    // Work with 64-bit words
    // Compute partial products (each is Uint<128> comprising 2 words within a 4-word result)
    const ll = toU128(a.low * b.low);   //  0       || 0        || ll.high  || ll.low
    const hl = toU128(a.high * b.low);  //  0       || hl.high  || hl.low   || 0
    const lh = toU128(a.low * b.high);  //  0       || lh.high  || lh.low   || 0
    const hh = toU128(a.high * b.high); //  hh.high || hh.low   || 0        || 0

    // add the values at word 1. offset1.high is the carry, which is added to the next word
    const offset1 = toU128(ll.high + hl.low + lh.low);
    // add the values at word 2. offset2.high is the carry, which is added to the next word
    const offset2 = toU128(offset1.high + hl.high + lh.high + hh.low);
    // add the values at word 3. There should be no carry here since the result fits in 256 bits
    const offset3 = toU128(offset2.high + hh.high);
    
    const resultLow = U128 { low: ll.low, high: offset1.low };
    const resultHigh = U128 { low: offset2.low, high: offset3.low };
    assert(isZero(offset3.high), "Uint128: unexpected multiplication overflow");

    return U256 { low: resultLow, high: resultHigh };
  }

Additional simplifications were also identified:

• These two lines are redundant and could be removed.
• The isApprovedForAll circuit could replace the if statement with a single boolean statement (i.e. return whether all three conditions are satisfied).

Recommendation

Consider implementing these simplifications to improve code quality.