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.

https://github.com/mratsim/constantine/blob/0fe6bbc4789d4311b1435d5eb858b19c1b0e1880/constantine/named/constants/banderwagon_subgroups.nim#L22-L41

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.