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.
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
isSquarecheck.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 boolparameter.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.