Another G2 MSM wrong result

[bkomuves]

Wrong result for a particular G2 MSM calculation (this time multiScalarMul_vartime is affected).

Unfortunately I don't have a small example (so far the smallest one is ~24,000 elements) and I don't have the energy or patience to try find a minimal one, so I just created a repo with all the data and code to reproduce.

Two independent implementations gives the correct result, and also constantine gives the correct result for smaller prefix vectors (I haven't done exhaustive testing here, but for example the first 10,000 elements is fine)

• machine/OS used for the testing: macbook pro M2 (arm); but I think earlier I tried Intel/Linux too
• constantine commit used: latest commit c7979b0 (but the bug should be present for at least a few months)
• nim version: 1.6.18

[mratsim]

Thanks for the repro.

It seems like it's once again the endomorphism acceleration that is problematic.

Using multiScalarMul_reference_vartime from

constantine/constantine/math/elliptic/ec_multi_scalar_mul.nim

Lines 95 to 97 in c7979b0

	func multiScalarMul_reference_vartime*[EC, ECaff](r: var EC, coefs: openArray[BigInt], points: openArray[ECaff]) {.tags:[VarTime, HeapAlloc].} =
	## Multiscalar multiplication:
	## r <- [a₀]P₀ + [a₁]P₁ + ... + [aₙ]Pₙ

works

And removing withEndo from

constantine/constantine/math/elliptic/ec_multi_scalar_mul.nim

Lines 406 to 437 in c7979b0

	func multiScalarMul_dispatch_vartime[bits: static int, F, G](
	r: var (ECP_ShortW_Jac[F, G] or ECP_ShortW_Prj[F, G]),
	coefs: ptr UncheckedArray[BigInt[bits]],
	points: ptr UncheckedArray[ECP_ShortW_Aff[F, G]], N: int) =
	## Multiscalar multiplication:
	## r <- [a₀]P₀ + [a₁]P₁ + ... + [aₙ]Pₙ
	let c = bestBucketBitSize(N, bits, useSignedBuckets = true, useManualTuning = true)
	# Given that bits and N change after applying an endomorphism,
	# we are able to use a bigger `c`
	# but it has no significant impact on performance
	case c
	of 2: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 2)
	of 3: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 3)
	of 4: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 4)
	of 5: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 5)
	of 6: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 6)
	of 7: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 7)
	of 8: withEndo(multiScalarMul_vartime, r, coefs, points, N, c = 8)
	of 9: withEndo(multiScalarMulAffine_vartime, r, coefs, points, N, c = 9)
	of 10: withEndo(multiScalarMulAffine_vartime, r, coefs, points, N, c = 10)
	of 11: withEndo(multiScalarMulAffine_vartime, r, coefs, points, N, c = 11)
	of 12: withEndo(multiScalarMulAffine_vartime, r, coefs, points, N, c = 12)
	of 13: withEndo(multiScalarMulAffine_vartime, r, coefs, points, N, c = 13)
	of 14: multiScalarMulAffine_vartime(r, coefs, points, N, c = 14)
	of 15: multiScalarMulAffine_vartime(r, coefs, points, N, c = 15)
	of 16..17: multiScalarMulAffine_vartime(r, coefs, points, N, c = 16)
	else:
	unreachable()

works as well.

[mratsim]

One thing really strange is that I tried to slice the input from 0 to 22000 or 1000 to 23000 and having too few points make the bug disappear.

[bkomuves]

So how this bug was discovered was really strange. These are the B2 points from a Groth16 proof. The circuit is essentially doing Poseidon2 hashes. The proof always succeeded below a given circuit size and always failed above a given size, no matter what the inputs are, what the exact structure of these hashes are (linear sponge, Merkle tree, independent permutation calls), this threshold even survived changing the number of the rounds in the Poseidon permutation. However with completely different circuits, much larger circuits worked fine too...

[bkomuves]

multiScalarMul_reference_vartime seems to be a good workaround, but it's more than 3x slower, becoming the primary bottleneck (this single MSM becoming more than half of the total runtime of a Groth16 proof).

[mratsim]

Further investigation shows that when 22528 points work while 22529 points doesn't.

This is the exact value for which c, the bucket size, changes from 12 to 13.