pointMultiply performance has a problem #5
Comments
|
Hey @junderw, Thanks for flagging this! I've been able to replicate your results. Your benchmark findings align with my observations - the Quick note though, the log entries list "[email protected]", but we're actually testing with "@noble/secp256k1": "^1.7.1", which might lead to some confusion. To rule out any issues with my wrapper functions around noble, I removed the data assertions and similar elements. After profiling the code, I've discovered that around 86% of the execution time is taken up specifically by const _pointMultiply = (p, tweak, isCompressed) => {
const P = necc.Point.fromHex(p);
const h = typeof tweak === 'string' ? tweak : necc.utils.bytesToHex(tweak);
const t = BigInt(`0x${h}`);
return P.multiply(t).toRawBytes(isCompressed);
};I'm wondering, @paulmillr, if you might have any insights into this. I'm certainly open to the idea that I might not be using noble optimally. Would it be possible to gain some performance improvement by moving to noble 2.0, or is this slowdown just an inherent part of the process? I'll keep this thread open for a bit in case anyone else has suggestions or potential fixes. Cheers! |
|
It's worth looking into why elliptic has this advantage. However, elliptic is unsafe. For one, it exposes multiplication exponent bits: shorter private keys would take less time to calculate. (https://minerva.crocs.fi.muni.cz) With js implementations, there's always a question of "how fast do we actually need to be?". Non-base-point multiplication is used mostly in ECDH. So far we've received 0 reports about its slowness. |
|
Also, I think elliptic author acknowledges the need for noble aka safer crypto libs, since he is a github sponsor. |
|
One way to sort-of test if that's the issue is to restrict the benchmark's set of scalars from a random distribution to lower values (maybe 1 - 255) and see if that closes the gap. If so, that's definitely the cause. (Edit: oops, I mean the other way around, we should restrict to higher values like (n - 255 to n - 1) I'll try messing around with it later today. (It might also help catch similar issues in the other impls (even though they are compiled from libsecp256k1, optimizers have been known to mess with constant-time-ness before)) |
|
It looks like the fixtures used to measure the benchmark were using low scalar values (like 1,2,3,4 etc.) so I switched it to n-1 n-2 n-3 n-4 and re-ran. (I'm doing some other computations on my PC rn so the variance % of the runs is a bit unstable, but most are within 10%) I would assume that this would close the gap a bit, but interestingly enough, tiny didn't change, and secp256k1 changed a bit +25%. bitcoinerlab (using noble) stayed the same, at about 7x ~ 8x tiny elliptic. I guess this is just a product of: elliptic uses a theoretically non-constant-time multiply algorithm. vs. noble uses a theoretically constant-time multiple algorithm that is more expensive. But the weird thing: pointToScalar (which is basically just pointMultiply with the point being the generator G) is actually faster with noble... which leads me to believe the reason is somewhere in the bitcoinerlab wrapper. (See benchmarks below) |
Yes, because noble precomputes multiples of base point. Just like native libsecp256k1. |
gist https://gist.github.com/paulmillr/cccaf4e57aa54f5d6946922a3c36fb4a |
I was adding this library to our benchmarks (we had noble before but only implemented one of the functions)
It does very well, and surprisingly almost matches WASM performance on some of the less intensive operations.
But there was a huge outlier in pointMultiply.
Comparing to the other JS ones (elliptic based) the time is an order of magnitude too slow.
Maybe looking into it is warranted. If it doesn't matter, please ignore. (I'm not sure where pointMultiply is used tbh, maybe some taproot stuff)
The text was updated successfully, but these errors were encountered: