Testing the `MUL` module's `EXP` instruction

[OlivierBBB]

As part of the work to produce "exhaustive" tests for the simpler modules (SHF, EXP, MUL, MOD, ...) and given the fact that the MUL module is blowing up on certain reference tests, with the EXP instruction (e.g. BlockchainReferenceTest_10), it makes sense to expand our test coverage.

The major difficulty will be that dealing with EXP can use up to 4096 = 256 * ( 8 + 8 ) rows (each multiplication is 8 rows and every bit of the exponent is responsible for 1 or 2 multiplication in the square and multiply algorithm that the module implements. So the batching strategy for the tests is an open question. These tests will likely be very long time wise but won't have to be run regularly, only when we modify the MUL module.

Generalities

There are 3 regimes for EXP instructions:

• OLI: whenever exponent or base is $\in \{0, 1\}$
  • 1 row
• TRIVIAL_EXP_REGIME : whenever the result of B^E mod 2^256 is predicted to be zero (and the instruction isn't a OLI)
  • 8 rows
• NONTRIVIAL_EXP_REGIME: whenever the result of B^E mod 2^256 is predicted to be nonzero (and the instruction isn't a OLI)
  • anywhere from 8 to 4096 rows

Test values

// bases:
even_base = { 0xff..ff << n where n = 1, ..., 256 }
          = { 0b11...10...0 with n zeros }

simple_odd_base = { 0x 00 ... 00 ff ... ff }
                = { 0xff..ff >> n where n = 0, 8, 16, ..., 256 }

other_odd_base = { mask ∧ [some 256 bit prime] | mask  ∈ simple_odd_base }

// exponents:
complex_exponents = { [some other 256 bit prime] >> n | n = 0, 1, ..., 256 }

tiny_exponents = { 0, 1, 2, ..., 256, 257, 65535, 65536, 65357 }

threshold_exponents = { (1 << 128) - 1, 1 << 128 , (1 << 128) + 1, (1 << 256) - 1 }

special_exponents = tiny_exponents ∪ threshold_exponents

// on the primes:
// both [some 256 bit prime] and [some other 256 bit prime] should be 'balanced' in the sense of having rougly as many 1's as 0's in base 2.

Test vectors

We should exhaustively test the following pairings:

• even_base & special_exponents: these are short (or even very short)
• simple_odd_base & special_exponents: long
• simple_odd_base & complex_exponents: very long
• other_odd_base & complex_exponents: very, very long

[lorenzogentile404]

Here are two 256 bits "0-1-balanced" primes:

0xF076B857FA9947C1F9EC558262C72704099CA8CD325566F73FB99238102ED171

0xC809C9170CA6FAEC82D43EE6754DBAD01D198ECAE0823BAC23CA30C7F0C9657D

[lorenzogentile404]

Code snippet from ShfExtensiveTest.java whose logic can be extracted, turned into a support method and re-used:

for (String XY : XYs) {
          String mask = XY + "00".repeat(31);
          String maskXorValue =
              String.format("%064X", new BigInteger(mask, 16).xor(new BigInteger(value, 16)));
          shfWithMaskTestSourceList.add(Arguments.of(maskXorValue, k, l, XY));
        }