Lattice decomposition cleanup

[mratsim]

Endomorphism acceleration #44 requires decomposing a scalar.

This is done using lattice decomposition using Babai's rounding techniques.

• Integrate in the property-based tests (requires clear cofactor Fast clear cofactor #46)
• The lattices should be moved in a per-curve-family configuration file:

  • constantine/constantine/elliptic/ec_endomorphism_params.nim

    Lines 29 to 42 in 2613356

    	const Lattice_BN254_Snarks_G1: array[2, array[2, tuple[b: BigInt[127], isNeg: bool]]] = [
    	# Curve of order 254 -> mini scalars of size 127
    	# u = 0x44E992B44A6909F1
    	[(BigInt[127].fromHex"0x89d3256894d213e3", false), # 2u + 1
    	(BigInt[127].fromHex"0x6f4d8248eeb859fd0be4e1541221250b", false)], # 6u² + 4u + 1
    	[(BigInt[127].fromHex"0x6f4d8248eeb859fc8211bbeb7d4f1128", false), # 6u² + 2u
    	(BigInt[127].fromHex"0x89d3256894d213e3", true)] # -2u - 1
    	]
    	const Babai_BN254_Snarks_G1 = [
    	# Vector for Babai rounding
    	BigInt[127].fromHex"0x89d3256894d213e3", # 2u + 1
    	BigInt[127].fromHex"0x6f4d8248eeb859fd0be4e1541221250b" # 6u² + 4u + 1
    	]

  • constantine/constantine/elliptic/ec_endomorphism_params.nim

    Lines 83 to 96 in 2613356

    	const Lattice_BLS12_381_G1: array[2, array[2, tuple[b: BigInt[128], isNeg: bool]]] = [
    	# Curve of order 254 -> mini scalars of size 127
    	# u = 0x44E992B44A6909F1
    	[(BigInt[128].fromHex"0xac45a4010001a40200000000ffffffff", false), # u² - 1
    	(BigInt[128].fromHex"0x1", true)], # -1
    	[(BigInt[128].fromHex"0x1", false), # 1
    	(BigInt[128].fromHex"0xac45a4010001a4020000000100000000", false)] # u²
    	]
    	const Babai_BLS12_381_G1 = [
    	# Vector for Babai rounding
    	BigInt[128].fromHex"0xac45a4010001a4020000000100000000",
    	BigInt[128].fromHex"0x1"
    	]

• Instead of a separate "true"/"false" field, the BIgInt can use an extra bit as a sign flag (still using 2-complement), this is detailed in the paper
  
  
• The encoding can use 1-bit per bit instead of 2 for {-1, 0, 1} as the column sign information is already encoded in the very first row, this will also speed up recoding
  
  
• The lattice can be stored in tuples instead of arrays so that the BigInt have the minimal size possible to reduce the cost of BigInt multiplication
• BLS has multiplication factors of 1 and/or 2 which can be optimized
• The lattice and Babai roundings coefficient can be precomputed from the curve parameter instead of being hardcoded
• The sage script should be fixed:

  constantine/sage/lattice_decomposition_bn254_snarks_g1.sage

  Lines 132 to 178 in 2613356

  	def scalarMulGLV(scalar, P0):
  	m = 2
  	L = ((int(r).bit_length() + m-1) // m) + 1 # l = ⌈log2 r/m⌉ + 1
  	print('L: ' + str(L))
  	print('scalar: ' + Integer(scalar).hex())
  	k0, k1 = getGLV2_decomp(scalar)
  	print('k0: ' + k0.hex())
  	print('k1: ' + k1.hex())
  	P1 = (lambda1_r % r) * P0
  	(Px, Py, Pz) = P0
  	P1_endo = G1([Px*phi1 % p, Py, Pz])
  	assert P1 == P1_endo
  	expected = scalar * P0
  	decomp = k0*P0 + k1*P1
  	assert expected == decomp
  	print('------ recode scalar -----------')
  	even = k0 & 1 == 1
  	if even:
  	k0 -= 1
  	b = recodeScalars([k0, k1])
  	print('b0: ' + str(list(reversed(b[0]))))
  	print('b1: ' + str(list(reversed(b[1]))))
  	print('------------ lut ---------------')
  	lut = buildLut(P0, P1)
  	print('------------ mul ---------------')
  	print('b0 L-1: ' + str(b[0][L-1]))
  	Q = b[0][L-1] * lut[b[1][L-1] & 1]
  	for i in range(L-2, -1, -1):
  	Q *= 2
  	Q += b[0][i] * lut[b[1][i] & 1]
  	if even:
  	Q += P0
  	print('final Q: ' + pointToString(Q))
  	print('expected: ' + pointToString(expected))
  	assert Q == expected # TODO debug

• We should not used signed integer as they introduce overflow checks which might leak secret bits
• Some buffers don't need to be zero-initialized
• Use window method to further accelerate 2-dimensional decompositions (Window method for GLV acceleration #45)
• Used mixed coordinates in the multiplication loop via an intermediate simultaneous inversion (Mixed addition #75)

[mratsim]

Several tasks ticked in #71

[mratsim]

And most other ticked in #94.

No plan to follow up on the rest for now.