Fuzz failure: 32-bit Sum of products

[mratsim]

As of commit 56616f2

================================================================================
||
|| Running #18/112: nim c -r --passC:-fstack-protector-strong  --passC:-D_FORTIFY_SOURCE=3  -d:CTT_ASM=false  -d:lto  --passC:-Wno-stringop-overflow --passL:-Wno-stringop-overflow  --passC:-Wno-alloc-size-larger-than --passL:-Wno-alloc-size-larger-than  --tlsEmulation=off  -d:danger  --panics:on -d:noSignalHandler  --mm:arc -d:useMalloc  --verbosity:0 --hints:off --warnings:off  --passC:-fno-semantic-interposition  --passC:-falign-functions=64  --passC:-fmerge-all-constants --outdir:build/test_suite  --nimcache:nimcache/tests/math_fields/t_finite_fields_mulsquare.nim tests/math_fields/t_finite_fields_mulsquare.nim
||
================================================================================

------------------------------------------------------

test_finite_fields_mulsquare xoshiro512** seed: 1739968506

[Suite] Modular squaring is consistent with multiplication on special elements [32-bit words]
[OK] Squaring 0,1,2 with Fake101 [FastSquaring = true]
[OK] Squaring 0,1,2 with Mersenne61 [FastSquaring = true]
[OK] Squaring 0,1,2 with Mersenne127 [FastSquaring = false]
[OK] Squaring 0,1,2 with P224 [FastSquaring = false]
[OK] Squaring 0,1,2 with P256 [FastSquaring = false]
[OK] Squaring 0,1,2 with Secp256k1 [FastSquaring = false]
[OK] Squaring 0,1,2 with BLS12_381 [FastSquaring = true]
[OK] Squaring 0,1,2 with Edwards25519 [FastSquaring = false]
[OK] Squaring 0,1,2 with Bandersnatch [FastSquaring = false]
[OK] Squaring 0,1,2 with Pallas [FastSquaring = false]
[OK] Squaring 0,1,2 with Vesta [FastSquaring = false]

[Suite] Modular Squaring: selected tricky cases [32-bit words]
  [OK] P-256 [FastSquaring = false]

[Suite] Random Modular Squaring is consistent with Modular Multiplication [32-bit words]
stack trace: (most recent call last)
/tmp/nimblecache-709449152/nimscriptapi_1968637122.nim(216, 16)
/home/runner/work/constantine/constantine/constantine/constantine.nimble(920, 3) test_parallelTask
/home/runner/work/constantine/constantine/nim-linux-i386-version-2-2-510ac845188a26d4c317893ff7b260582beee54d/lib/system/nimscript.nim(264, 7) exec
/home/runner/work/constantine/constantine/nim-linux-i386-version-2-2-510ac845188a26d4c317893ff7b260582beee54d/lib/system/nimscript.nim(264, 7) Error: unhandled exception: FAILED: build/test_suite/pararun build/test_suite_parallel.txt [OSError]
  [OK] Random squaring mod P-224 [FastSquaring = false]
  [OK] Random squaring mod P-256 [FastSquaring = false]
  [OK] Random squaring mod Secp256k1 [FastSquaring = false]
  [OK] Random squaring mod BLS12_381 [FastSquaring = true]
  [OK] Random squaring mod Edwards25519 [FastSquaring = false]
  [OK] Random squaring mod Bandersnatch [FastSquaring = false]
  [OK] Random squaring mod Pallas [FastSquaring = false]
  [OK] Random squaring mod Vesta [FastSquaring = false]

[Suite] Modular squaring - bugs highlighted by property-based testing
  [OK] a² == (-a)² on for Fp[2^127 - 1] - #61
  [OK] a² == (-a)² on for Fp[2^127 - 1] - #62
  [OK] 32-bit fast squaring on BLS12-381 - #42
  [OK] 32-bit fast squaring on BLS12-381 - #43

[Suite] Random sum products is consistent with naive  [32-bit words]
  [OK] Random sum products mod P-224]
  [OK] Random sum products mod BN254_Nogami]
fatal.nim(53)            sysFatal
Error: unhandled exception: t_finite_fields_mulsquare.nim(344, 7) `bool(r`gensym1900 == r_ref`gensym1900)`  [AssertionDefect]
Error: execution of an external program failed: '/home/runner/work/constantine/constantine/constantine/build/test_suite/t_finite_fields_mulsquare'

========================== Command exited with code 1 ==========================
[FAIL]: 'nim c -r --passC:-fstack-protector-strong  --passC:-D_FORTIFY_SOURCE=3  -d:CTT_ASM=false  -d:lto  --passC:-Wno-stringop-overflow --passL:-Wno-stringop-overflow  --passC:-Wno-alloc-size-larger-than --passL:-Wno-alloc-size-larger-than  --tlsEmulation=off  -d:danger  --panics:on -d:noSignalHandler  --mm:arc -d:useMalloc  --verbosity:0 --hints:off --warnings:off  --passC:-fno-semantic-interposition  --passC:-falign-functions=64  --passC:-fmerge-all-constants --outdir:build/test_suite  --nimcache:nimcache/tests/math_fields/t_finite_fields_mulsquare.nim tests/math_fields/t_finite_fields_mulsquare.nim' (#18/112)
[FAIL]: Command #18 exited with error 1

The issue happens here:

constantine/tests/math_fields/t_finite_fields_mulsquare.nim

Lines 325 to 344 in 56616f2

	proc random_sumprod(Name: static Algebra, N: static int) =
	template sumprod_test(random_instancer: untyped) =
	block:
	var a: array[N, Fp[Name]]
	var b: array[N, Fp[Name]]
	for i in 0 ..< N:
	a[i] = rng.random_instancer(Fp[Name])
	b[i] = rng.random_instancer(Fp[Name])
	var r, r_ref, t: Fp[Name]
	r_ref.prod(a[0], b[0])
	for i in 1 ..< N:
	t.prod(a[i], b[i])
	r_ref += t
	r.sumprod(a, b)
	doAssert bool(r == r_ref)

for BN254-Snarks:

constantine/tests/math_fields/t_finite_fields_mulsquare.nim

Lines 371 to 393 in 56616f2

	suite "Random sum products is consistent with naive " & " [" & $WordBitWidth & "-bit words]":
	const MaxLength = 8
	test "Random sum products mod P-224]":
	for _ in 0 ..< Iters:
	staticFor N, 2, MaxLength:
	random_sumprod(P224, N)
	test "Random sum products mod BN254_Nogami]":
	for _ in 0 ..< Iters:
	staticFor N, 2, MaxLength:
	random_sumprod(BN254_Nogami, N)
	test "Random sum products mod BN254_Snarks]":
	for _ in 0 ..< Iters:
	staticFor N, 2, MaxLength:
	random_sumprod(BN254_Snarks, N)
	test "Random sum products mod BLS12_377]":
	for _ in 0 ..< Iters:
	staticFor N, 2, MaxLength:
	random_sumprod(BLS12_377, N)
	test "Random sum products mod BLS12_381]":
	for _ in 0 ..< Iters:
	staticFor N, 2, MaxLength:
	random_sumprod(BLS12_381, N)

with seed 1739968506 without assembly

[mratsim]

This can be reproduced on a 64-bit system with nim c -r -d:CTT_32 -d:danger --hints:off --warnings:off --outdir:build tests/math_fields/t_finite_fields_mulsquare.nim and also without ASM nim c -r -d:CTT_32 -d:CTT_ASM=false -d:danger --hints:off --warnings:off --outdir:build tests/math_fields/t_finite_fields_mulsquare.nim

I expect my bounds on the number of sums is incorrect:

constantine/constantine/math/arithmetic/limbs_montgomery.nim

Lines 332 to 342 in 56616f2

	static: doAssert K <= 8, "we cannot sum more than 8 products"
	# Bounds:
	# 1. To ensure mapping in [0, 2p), we need ⅀aᵢ.bᵢ <=pR
	# for all intent and purposes this is true since aᵢ.bᵢ is:
	# if reduced inputs: (p-1).(p-1) = p²-2p+1 which would allow more than p sums
	# if unreduced inputs: (2p-1).(2p-1) = 4p²-4p+1,
	# with 4p < R due to the 2 unused bits constraint so more than p sums are allowed
	# 2. We have a high-word tN to accumulate overflows.
	# with 2 unused bits in the last word,
	# the multiplication of two last words will leave 4 unused bits
	# enough for accumulating 8 additions and overflow.

[mratsim]

By changing the doAssert line 344 from the tests to

      doAssert bool(r == r_ref), block:
        "Failure for inputs:\n" &
          (
            var u = "let a = [\n"
            for i in 0 ..< N:
              u &= "  " & $Name & ".toHex\"" & a[i].toHex() & "\",\n"
            u &= "]\n"
            u
          ) & (
            var v = "let b = [\n"
            for i in 0 ..< N:
              v &= "  " & $Name & ".toHex\"" & b[i].toHex() & "\",\n"
            v &= "]\n"
            v
          ) &
          "Output:   " & r.toHex() & "\n" &
          "Expected: " & r_ref.tohex()

We can get the inputs that triggered the bug:

let a = [
  BN254_Snarks.toHex"0x1d863ec7567c23585a6a4393bb8c3b494cc05e86f4add7b517c9b23ab19500bc",
  BN254_Snarks.toHex"0x06967776f4707aa451ee3af80c4e0199a1b8bc9bb2ae204430e621e8f1ffec89",
  BN254_Snarks.toHex"0x228804e958f2e8ec7486f23b31020ddfcb8b62f3e9954a56ecb9d2ec22a1f99a",
  BN254_Snarks.toHex"0x01d8e3ca792fd67062a03104c6a36cc488c3fbf375fbd43681682237ebe934a6",
  BN254_Snarks.toHex"0x2ee2ba858492f76687eb6c1345a6540122a0a605c206c340b36543faf5721241",
  BN254_Snarks.toHex"0x0223ac2f3c7d92cfa5d1e52afd4176967be753e60bd47b6dd389e9c41e6eb04f",
  BN254_Snarks.toHex"0x2f38c3fc526bd1e1b41854845d9ef4a386ff968a06024d72ff6e35bd4b735318",
]
let b = [
  BN254_Snarks.toHex"0x0717d3316dfbee31674f1f2211eecf78645b2cf7366bdb75461010a549215711",
  BN254_Snarks.toHex"0x2a9fd05e4ee90e06ade6f46049fc6a27b3f02b7a218194a44d2810c48dbb430e",
  BN254_Snarks.toHex"0x08f5b6cc502d5f07d618c009821e8fbbf75f7677cb72cee5fc1cd0445b7fa28f",
  BN254_Snarks.toHex"0x00d205f17ea5ff3ad4bf7fc86ea2c1cdf6055e7f2781e3293ea964fc9e02acec",
  BN254_Snarks.toHex"0x205486cc57888310d03007c95e95c3e66f5ebfc638be4559a86ad2a8b67db48d",
  BN254_Snarks.toHex"0x003af16dd462af63e1ee418876f05245a3f336b47eaf7a675571ea34f8df76ee",
  BN254_Snarks.toHex"0x0553025349c6bb035ea895d6bacf17776a9bddfaa80e1accd976237201faf27d",
]
Output:   0x279d903141e65cd6b630ad4bc8966ecfb7e46b1f1929f21654eaf4818f5fa914
Expected: 0x226bfeee716b37dcb05d384afddef59a0fb40ce21a526eb3ce7ee20e273f1cbf

Note that 8 inputs are not used in production, the max is 4 for Fp4 and 6 for Fp6.