Verkle Trees: Faster subgroup checks for Banderwagon via vartime Legendre symbol

[mratsim]

Overview

This is a followup to #236 and #354.

For Ethereum Verkle tries, we will likely deserialize a massive number of elliptic curve points, especially during sync.

Subgroup checks are slow, for Banderwagon this is due to an isSquare check.

constantine/constantine/named/constants/banderwagon_subgroups.nim

Lines 22 to 41 in 0fe6bbc

	func isInSubgroup*(P: EC_TwEdw_Aff[Fp[Banderwagon]]): SecretBool =
	## Checks if the point is in the quotient subgroup
	## The group law does not change because what we quotiented by was a subgroup.
	## These are still points on the bandersnatch curve and form a group under point addition.
	##
	## This is to be used to check if the point lies in the Banderwagon
	## while importing a point from serialized bytes
	var t{.noInit.}: typeof(P).F
	var one{.noInit.}: typeof(P).F
	one.setOne()
	t.setZero()
	# Compute 1 - aX^2 and check its legendre symbol
	t.square(P.x)
	t *= Banderwagon.getCoefA()
	t.diff(one, t)
	return t.isSquare()

Looking at the benchmarks on a 7840U, isSquare takes 1089ns.

And non-subgroup checked deserialization adds 1800ns of overhead

We can reduce the gap by implementing a faster isSquare.

For Ethereum Verkle Tries we don't need the constant-time property. As modular inversion and isSquare use a very similar algorithm, we can expect a conservative 27% perf improvement by adding a useVartime: static bool parameter.

Implementation

Both modular inverse constant-time, vartime and legendre symbole constant-time are in the following file:
https://github.com/mratsim/constantine/blob/0fe6bbc/constantine/math/arithmetic/limbs_exgcd.nim

The legendre symbol constant-time needs to be adaptaed in a similar manner to how modular inverse was adapted for vartime evaluation.