Introducing the `k256` crate: a pure Rust secp256k1 library based on projective formulas

By Tony Arcieri

The Rust programming language has received widespread adoption in the cryptocurrency space, owing to many things like its emphasis on safety, sophisticated type system, and impressive support for concurrency and async I/O. However, where Rust has succeeded in this space, it’s been despite the language’s sometimes spotty support for cryptographic algorithms used in cryptocurrency development.

One of the most critical algorithms commonly used in cryptocurrency is elliptic curve cryptography (ECC). While there are many impressively high quality ECC implementations written from the ground up in pure Rust, such as the curve25519-dalek and bls12_381 crates, the story around the most commonly used elliptic curve in cryptocurrency, secp256k1, is a bit more confusing and fragmented.

Here is a screenshot of the results you get if you search for “secp256k1” on crates.io, the Rust package repository:

secp256k1 on crates.io: lots and lots and lots of forks

The common theme here: lots and lots and lots of forks of Rust bindings to the bitcoin-core/secp256k1 C library. Using this library certainly isn’t a bad choice: it’s the fastest, most mature, and best-maintained secp256k1 library available. However, people are writing forks because the Rust bindings do not provide access to the C library’s API surface necessary to implement things like zero-knowledge protocols.

All that said, while Rust has fantastic C interop support, for many reasons it’s much nicer to have a high-quality pure Rust library over a C library. Concerns about the C language like memory safety aside, using C libraries limits portability because you also need a C compiler installed for all of your potential targets. It often slows down builds by requiring a build.rs step (as in secp256k1-sys which packages the bitcoin-core/secp256k1 library). When available, it’s much more convenient to use a high-quality Rust library than a C library wrapper.

There has been one attempt (to our knowledge) to create a pure Rust secp256k1 implementation: the paritytech/libsecp256k1 library released as the libsecp256k1 crate. However, this library is problematic for a few reasons:

Introducing the k256 crate #

The k256 crate is a pure Rust secp256k1 implementation created as part of the RustCrypto/elliptic-curves project. It’s the work of many collaborators who are interested in improving the quality of elliptic curve cryptography within the Rust ecosystem as well as specifically producing a high-quality secp256k1 library.

The project began as a fork of the RustCrypto p256 crate, which implements the NIST P-256 curve and was originally written from scratch by Jack Grigg (a.k.a. str4d), cryptographer, Zcash engineer, and co-author of several other elliptic curve libraries including the bls12_381 crate.

It was forked into the k256 crate by “tux” of NuCypher. Both NIST P-256 and secp256k1 are similar in that they are short Weierstrass curves, making it possible to repurpose large parts of the implementation for a different curve, namely reusing the Montgomery arithmetic code but despecializing it from the P-256 modulus.

Thanks to significant contributions by another NuCypher employee, Bogdan Opanchuk, the k256 crate now has both 32-bit and 64-bit backends leveraging several techniques used by the bitcoin-core/secp256k1, including lazy reduction and endomorphism optimizations. The latter were previously patented, but the last remaining patent recently expired allowing us to enable the endomorphism optimizations by default and remove the non-endomorphism code.

Below is a benchmark comparing the ECDSA signing and verification performance of the k256 crate, the pure Rust libsecp256k crate, and the C FFI (rust-)secp256k1 crate which wraps the bitcoin-core/secp256k1 library respectively:

k256 ECDSA benchmark.png

The bitcoin-core/secp256k1 C library provides the best performance, but the k256 crate is not substantially slower: it’s ~1.8x slower at signing, and ~2.4x slower at verification, as benchmarked on an Intel® Xeon® E-2286M CPU @ 2.40GHz.

Tour of the k256 API #

As mentioned above, the k256 crate is a general-purpose secp256k1 library. It’s implemented without heap allocations and designed from the ground-up to work in no_std environments.

It comes with the following features out-of-the-box:

ECDSA #

The Elliptic Curve Digital Signature Algorithm is one of the most common algorithms used in conjunction with the secp256k1 elliptic curve. As illustrated by the chart above, it’s also one of the main algorithms we’ve focused on in developing the k256 crate.

In k256, we’ve implemented ECDSA by leveraging shared functionality exposed from the ecdsa crate, which is generic over elliptic curves. The ecdsa crate implements functionality like RFC6979 deterministic signatures, including a mode of RFC6979 which takes additional randomness from an RNG, which can be used to harden it against things like fault attacks on embedded devices.

Additionally, the k256 crate supports Ethereum-style signatures with public key recovery, which are generic over digest functions and can be used in conjunction with Keccak256 as used by Ethereum.

In developing the k256 crate, we’ve definitely had cryptocurrency use cases on the top of our minds. If there’s some cryptocurrency application where you’d like to use secp256k1 and it’s not supported by the k256 crate, please open an issue!

Elliptic Curve Diffie-Hellman #

Diffie-Hellman key exchange is the primary way to perform public-key encryption using elliptic curves, and the k256 crate supports it.

It uses a shared, generic Diffie-Hellman implementation from the elliptic-curve crate.

Group-based operations #

The k256 crate provides support for implementing any group-based protocol using the Scalar, AffinePoint, and ProjectivePoint types. These types implement traits from the ff (i.e. finite field) and group crates. Most notably ProjectivePoint implements the group::Group trait, and with it a whole host of arithmetic operations such as point addition and scalar multiplication.

As mentioned at the beginning of this post, by making group-based operations part of the public API, it’s not necessary to fork the k256 crate in order to implement e.g. zero-knowledge protocols.

The idea of exposing “internals” of a cryptographic library like this may sound scary, however we have meticulously designed a safe API which is hard-to-misuse. When working with complete formulas for prime order curves like k256 implements, properly encapsulated in types which do not allow misuses by design, groups naturally lend themselves to safe APIs.

That’s not to say that group-based protocols are easy, or that k256 will somehow save you from a protocol-level design error. However, if you’re doing something like implementing a well-scrutinized group-based protocol with a security proof from a paper, k256 should make it easy to translate the prose in a paper into Rust code while avoiding implementer error (ideally catching mistakes with the help of Rust’s type system).

Crates using k256 today #

Though we haven’t done any sort of marketing push around it yet, the k256 crate has seen quite a bit of organic adoption. Here are a list of some of the notable crates using k256 today:

Conclusion #

If you’re using secp256k1 and want a pure Rust implementation of the elliptic curve, or just access to group-based operations as part fo the public API, give k256 a try!

If you’re having any trouble using it, please open a GitHub issue on our issue tracker, or say “hi” in our Zulip Chat.

 
35
Kudos
 
35
Kudos

Now read this

The Launch of the Oasis Testnet

By Zaki Manian Iqlusion has been helping Oasis get ready for the launch of it’s first public testnet for the last couple months. Getting to public testnets is a major milestone for the project and I’m excited about everything Tendermint... Continue →