Signatures on secp256k1

I’ve released a library supporting BIP340 Schnorr signatures and deterministic ECDSA on the elliptic curve secp256k1. Get it while it’s hot – for when you just aren’t feeling libsecp256k1!

This is another “minimal” library in the ppad suite of libraries I’m working on. Minimal in the sense that it is pure Haskell (no FFI – you can check out ppad-csecp256k1 if you want that) and depends only on ‘base’, ‘bytestring’, and my own HMAC-DRBG and SHA256 libraries. The feature set also intentionally remains rather lean for the time being (though if you could use other features in there, let me know!).

Performance is decent, though unsurprisingly it still pales in comparison to the low-level and battle-hardened libsecp256k1 (think 5ms vs 50μs to create a Schnorr signature, for example). There’s ample room for optimisation, though. Probably the lowest-hanging fruit is that scalar multiplication on secp256k1 can seemingly be made much more efficient via the so-called wNAF method that relies on precomputed points, such that we might be looking at more like 500μs to create a Schnorr signature, with a similar improvement for ECDSA. It would require slightly more annoying UX, probably warranting its own set of user-facing functions that would also accept a context argument, but does not appear difficult to implement.

A few things I observed or noted while writing this library:

• The modular arithmetic functions for arbitrary-precision Integers contained in GHC.Num.Integer can be extremely fast, compared to hand-rolled alternatives. Things like integerPowMod# and integerRecipMod# absolutely fly, and will probably beat any hand-rolled variant.

• Arbitrary-precision Integers are still slow, compared to fixed-width stuff that modern computers can positively chew through (this is not news to me, but still). I achieved a staggering speedup on some basic integer parsing by using a custom Word256 type (built from a bunch of Word64 values) under the hood, and converting to Integer only at the end.

  They can also be annoying when one wants to achieve constant-time execution of cryptographically-sensitive functions, for obvious reasons. It would be nice to have good fixed-width support for stuff like Word128, Word256, Word512, and so on – I briefly considered implementing and using a custom Word256 type for everything, but this would be a ton of work, and I’m not sure I could beat GHC’s native bigint support for e.g. modular multiplication, exponentiation, and inversion anyway. We’ll stick with plain-old Integer for the time being – it’s still no slouch.

• Algorithmically constant-time operations can still fail to be constant-time in practice due to factors largely outside the programmer’s control. A good example is found in bit operations; looping through a bytestring and performing some “equivalent-looking” work on every byte may still result in execution time discrepancies between zero and nonzero bytes, for example, and these can be very hard to eliminate. This stuff can depend on the compiler or runtime, the architecture/processor used, etc.

• The necessary organization of this kind of “catch-all” library is kind of unsatisfying. Rather than picking a single curve, and then implementing every feature one can possibly think of for it, it would intuitively be better to implement a generic curve library or libraries (for Weierstrass, Edwards, Montgomery, etc.), and then implement e.g. ECDSA or EdDSA or ECDH or or whatever as separate libraries depending on those generic curves as appropriate. One could then use everything in more of a plug-and-play fashion – this might be a design I’ll explore further in the future.

• ByteString seems to provide a good user-facing “interface” for libraries like this. It’s reliable, familiar to Haskellers, has a great API, and is very well-tuned. It’s possible one might want to standardize on something else for internals, though; unboxed vectors are an obvious choice, though I would actually be inclined to use the primitive library’s PrimArrays directly, favouring simplicity, and eschewing vector’s harder-core optimisations.

  The idea here in any case would be that one would use ByteString only at the user-facing layer, and then work with PrimArrays (or whatever) everywhere internally. It’s perhaps worth exploring further – bytestring is very fast (strict bytestrings are, after all, merely pointers to cstrings), but so are PrimArrays, and mutation à la MutablePrimArray could be very helpful to have here and there.

  (FWIW, though, I’ve benchmarked PrimArray/MutablePrimArray in ppad-sha256 and found them to yield equivalent-or-slower performance compared to ByteString in that setting.)

The library has been tested on the Project Wycheproof and official BIP340 test vectors, as well as noble-secp256k1’s test suite, and care has been taken around timing of functions that operate on secret data. Kick the tires on it, if you feel so inclined!

(I mentioned this in my last post as well, but I’m indebted to Paul Miller’s noble cryptography project for this work, both as inspiration and also as a reference.)