secp256k1: Edge case of inconsistency in limbs' multiplicative constants

[suyash67]

When I run biggroup::secp256k1 scalar multiplication tests:

cmake --build --preset default --target stdlib_primitives_tests && (cd build && ./bin/stdlib_primitives_tests --gtest_filter=*pow*)

we see a weird pattern in the multiplicative constants of the bigfield limbs in bigfield::operator+ and bigfield::operator-. When adding/subtracting two circuit-witnesses we use an optimised bigfield addition/subtraction gate:

barretenberg/cpp/src/barretenberg/stdlib/primitives/bigfield/bigfield_impl.hpp

Lines 702 to 703 in 4306250

	if (prime_basis_limb.multiplicative_constant == 1 && other.prime_basis_limb.multiplicative_constant == 1 &&
	!is_constant() && !other.is_constant()) {

This condition is entered in the case when both inputs are witnesses AND if both inputs' prime limbs have multiplicative constants are 1.

1. !is_constant() && !other.is_constant()
2. prime_basis_limb.multiplicative_constant == 1 && other.prime_basis_limb.multiplicative_constant == 1

@Rumata888 raised a question: can there be a case when multiplicative constants of the prime limbs is 1 but multiplicative constants of the binary limbs is NOT 1? Intuitively, this shouldn't happen because this would mean the prime limbs are somehow normalised while the binary basis limbs are not. The binary and prime limbs are always updated/used together in the bigfield class so its unlikely that one is normalised and others are not.

So, I ran all stdlib_primitives_tests to check if this condition is triggered when any of the binary limb's mult const ≠ 1 but both prime limbs mult const = 1. Interestingly, for operator+ this never happens, i.e., all limbs mult const is 1 whenever we enter the if condition.

For operator- though, it does happen for secp256k1 scalar multiplication methods. Specifically, in the function compute_secp256k1_endo_wnaf in biggroup_nafs.hpp, we see that the bigfield::operator- triggers the optimised subtraction with the following inputs:

	limb	other limb
limb 0: value	0x175e49a535a9bd899a	0xe
limb 0: mul	0x1	0x1
limb 0: add	0x0	0xd
limb 1: value	0x24389a693106e500	0x2000000000000000
limb 1: mul	$\textcolor{red}{0x2}$	0x1
limb 1: add	0x0	0x0
limb 2: value	0x0	0x0
limb 2: mul	$\textcolor{red}{0x2}$	0x1
limb 2: add	0x0	0x0
limb 3: value	0x0	0x0
limb 3: mul	$\textcolor{red}{0x2}$	0x1
limb 3: add	0x0	0x0

We need to understand two things:

1. How do we get into this edge case of multiplicative constants? Is this expected?
2. If for operator+ this optimisation only gets triggered when all multiplicative constants are 1, can we simplify the bigfield multiplication gate structure?

We will cover this issue as a part of the biggroup audit.

[suyash67]

On diving deeper: we get the following state of the variable reconstructed_positive_part

prime_basis_limb: mult_const = 1 (new gate created)
binary_basis_limbs[0]: mult_const = 1 (new gate created)
binary_basis_limbs[1,2,3]: mult_const = 2 (unchanged lazy scaling)

because of the line:

// Double the final value and add the positive skew
reconstructed_positive_part =
    (reconstructed_positive_part + reconstructed_positive_part)
        .add_to_lower_limb(field_t<Builder>(positive_skew), /*other_maximum_value*/ uint256_t(1));

So when we add x to x (same witness indices), only the multiplicative constant is updated without adding any new gates. However, after computing 2x, we add the positive_skew to the limb 0 which normalizes it (multiplicative constant becomes 1). We reach a state where multiplicative constants of binary basis limbs are unequal. Hence when we call operator- on the variable reconstructed_positive_part later in that function, we see this state in bigfield operator-.

This is not a bug, the circuit behaves as expected. Further, relying on multiplicative constants of only prime limbs is the correct approach (because binary basis limbs' multiplicative constants can be unequal as we saw in this example).

Closing this issue as we don't need to change any code.