One of the fastest BLS signature implementations
The world of cryptocurrency can seem like magic when compared to the archaic systems of banks and fiat. But beneath this magical veneer, there’s something even more arcane. Tons of math, software, and infrastructure combine thanks to the tireless (and in some cases practically magical themselves) efforts of motivated and intelligent people working toward something better for us all.
We’re going to zoom in on a specific part of this combination—one that we have recently made some big developments in. Skipping to the punchline, Mamy, one of our engineers, has made one of the world’s fastest BLS signature implementations. We have been working on this since 2018, and have some big results to show for it.
Cryptographic protocols typically provide at least one of: confidentiality, integrity, non-repudiation, or authentication. Confidentiality means only the desired parties can read a message, and is usually achieved via encryption. Integrity proves that a message has not been tampered with, and is usually achieved via hashing functions. Non-repudiation guarantees the validity of authorship—i.e. that someone actually did something. Authentication proves that someone is who they say. Both non-repudiation and authentication are usually achieved via digital signatures.
We’re going to talk about a specific type of digital signature: BLS signatures (Boneh-Lynn-Shacham, the three authors of the algorithm). Much like ECDSA signatures, used by Bitcoin and Ethereum 1, BLS signatures provide integrity, authentication, and non-repudiation. They are of particular note to Status, as they are used in Ethereum 2 (as well as Algorand, Chia, Dfinity, Filecoin, Tezos, Zcash, and many more).
BLS signatures provide a notable advantage over ECDSA: namely, BLS signatures can be aggregated, and moreso, in constant space. An aggregate signature is a combination of signatures that provides the same guarantees that the original signatures did, but takes less space and is usually more efficient to work with. Constant space means that one vote from one validator takes the same amount of storage space as 10,000 votes from 10,000 validators (or any other number). Verifying 10,000 votes is also as costly as verifying a single vote. BLS signatures don’t win out in every metric—it is significantly slower to verify a BLS signature compared to an ECDSA signature, for example. Thus, optimizing BLS signatures is extremely important.
A proliferation of “next-generation”, scalable blockchain protocols has put a premium on generating short digital signatures that can be efficiently aggregated or easily thresholded.
- Ben Edgington, BLS12-381 For The Rest Of Us
BLS cryptography is the most expensive bottleneck in Nimbus—and all consensus clients, for that matter—and will be an even more significant bottleneck for sharding. Mamy’s BLS implementation (called Constantine) is 1.14x faster than BLST for signing, and 1.18x faster than BLST for verification. These optimizations are related to both some brutal number theory, and implementation/engineering details. Some examples are using a compressed representation of numbers that satisfy a special polynomial relationship, and using assembly in more optimal ways to reduce memory usage.
The detail (and number) of the optimizations are beyond the scope of this article, but a complete list is available here.
Cryptographers working on optimizing algorithms like this are planning to work together to create a repository for pairing benchmarks, to help measure the performance of such algorithms, and make Ethereum 2 (as well as other cryptocurrency ecosystems that rely on BLS) as fast as it can be!
Constantine will not appear in Nimbus for a while yet, as there are more optimizations to be done, and the library is currently unaudited—currently (but will be audited some time soon).
(If you are not interested in the mathematics of BLS, you can stop here.)
We’ll cover in brief(-ish) some details of the BLS signature scheme, but there is some relatively complex math under the hood and a full explanation would require several articles. For mathematicians (or masochists), Ben Edginton’s BLS12-381 For The Rest Of Us has a more comprehensive explanation (and also served as a crucial reference for this post). The variables we use are given the same names as in his article.
Note that this section is meant to give some measure of understanding of BLS, but it should not be used as more than a very basic introduction to the material, as certain important but more technical details are omitted. The topics we touch on, abstract algebra, group theory, field theory, finite fields, and elliptic curves are each complex enough to warrant their own blog posts, but we fear for our readership should we become too much like a mathematical textbook.
The BLS signature scheme was created by the trio Dan Boneh, Ben Lynn, and Hovav Shacham in 2001.
Clocks aka Modular Arithmetic
When you do “time math” (consider a 12 hour clock for this example) you add numbers in a way that doesn’t match with our usual understanding of addition. “3 hours after 11” does not equal 14, it is 2. We are performing a special type of addition, where we add the numbers, and then reduce by 12. It is no coincidence that 2 = 14 - 12.
An elliptic curve (over the real numbers) is a curve that is described by the equation:
y^2 = x^3 + ax + b,
where a and b are the “usual” kind of numbers (real numbers, e.g. 10, sqrt(2), pi).
Elliptic curves are crucial for many types of cryptography and cryptocurrency applications. They are also a bit like clocks. The points on an elliptic curve are points (x, y) that satisfy the equation of the curve. These points can be added together, notably, in a way that doesn’t match with our usual understanding of addition.
Elliptic curve addition
Elliptic curves are symmetrical around the horizontal axis. To add two points on an elliptic curve, draw a line through the two points and find the third point on the curve that intersects the line. Then, reflect that point over the horizontal axis: this is the sum of two points on an elliptic curve. (Adding a point P to its reflection, i.e. P + (-P), is a special case and results in “the point at infinity”, but for our purposes we can just think of it as “zero”.)
For more details on elliptic curve addition, see A (Relatively Easy to Understand) Primer on Elliptic Curve Cryptography, particularly the sections “Elliptic curves: Building blocks of a better Trapdoor” and “Strange Symmetry”.
To make matters worse, not all elliptic curves are defined “over the real numbers”, which means that a and b can be less familiar. They can be complex numbers, for example, or elements of whatever field the elliptic curve is defined over (as in “the elliptic curve E defined over the field F”)--a field is a set of number-like things that behave generally like numbers (they can be added, subtracted, multiplied, and divided, except by zero).
Finite Fields aka Weird Clocks
Finite fields are a common and useful type of field. Consider a clock that only goes to 5. Each time you add numbers on this clock, you reduce by 5.
1 + 3 = 4
2 + 4 = 6 → 1
2 + 3 = 5 → 0
We can also multiply these numbers, and apply a similar process of reduction:
2*2 = 4
2*4 = 8 → 3
0*2 = 0
(Division is a bit weirder, and conveniently unnecessary for our purposes.)
Groups
Groups are like fields, but with less rules. A group is a collection of number-like things that can be added (not necessarily in the way we normally think of addition), and adding any two elements of a group will always produce a third element of the group. Every field is a group, but not every group is a field.
The groups we are concerned with will be cyclic, which means that some specific element of the group can be added to itself to get any other element of the group. This element is called a generator.
BLS prelude
We are concerned with two elliptic curves that are referred to as BLS12-381 (Barreto-Lynn-Scott, same Lynn). The first curve is defined over a prime finite field, i.e. a finite field with q elements, where q is prime. The second curve is a bit more complex, and is defined over a finite field with q^2 elements. The relationship between the first and second field is much like that between real and complex numbers, the second field is essentially the first field combined with i.
We said elliptic curves are described by the equation y^2 = x^3 + ax + b. Our first curve looks like
y^2 = x^3 + 0x + 4, i.e. a = 0 and b = 4. Points on this curve are represented as pairs of integers.
Our second curve looks like
y^2 = x^3 + 4(1 + i), where i is the square root of -1. Points on this curve are represented as pairs of complex numbers.
We find a group of points on each curve (the addition of such points is performed as described in “Elliptic Curve Addition”), which we will call G1 for the first curve, and G2 for the second. Each group has the same number of elements, r. For our purposes, it is important that r is prime.
Pairings/Bilinear Functions
We'll be talking about pairings and bilinear functions in just a second, but first, what's a linear function? A function f is linear if f(x+y) = f(x) + f(y) and f(a * x) = a * f(x).
A bilinear function is a function of two variables that is linear with respect to each. Consider this simple example: f(x,y) = xy. If we choose some non-zero constant value for y, e.g. y=2, then f(x,2) = 2x, which we know is linear; and if we choose some non-zero constant value for x instead, e.g. x=3, then f(3,y) = 3y, which we know is linear. So f(x,y) = xy is bilinear.
We will need a pairing for BLS. For the sake of simplicity, we can consider a pairing to be a bilinear function that takes two parameters from two groups (G1 and G2) of the same size as inputs, and produces one output from a third group. Pairings are usually written like:
e(x,y), where x is an element of G1, and y is an element of G2.
BLS scheme (finally)
So, here are all the pieces.
r = number of elements of the groups G1 and G2, prime, <= 255 bits
sk = private/secret key, randomly chosen number between 1 and r – 1, inclusive
g1 = chosen generator of G1, (i.e. we can add g1 to itself some number of times to get any point in G1). Because G1 has a prime number of elements, any point can function as the chosen generator (though in practice there are certain efficiency reasons to prefer one generator to another, and deciding which generator to use is done in a reproducible way such that people on either end of the signature scheme are able to choose the same one).
pk = public key; pk = [sk]g1, i.e. g1 + g1 + … + g1, sk times
The discrete logarithm problem makes it infeasible to figure out sk if you are starting with pk.
m = the message to be signed.
We assume there is some way to map m to a point of G2, done via some hashing function we call H. Practically every cryptographic scheme involving elliptic curves includes some method of translating messages to a group on the curve, so we will gloss over the details.
H(m) = the corresponding point on G2 for the message m
σ = signature, σ = [sk]H(m), i.e. H(m) + H(m) + … + H(m), sk times
So, a brief interlude: g1 is an element of G1, which means it’s a point on the first elliptic curve. This means addition of g1 is elliptic curve addition, which is a bit funky (as described in “Elliptic Curve Addition”). H(m) is an element of G2, which means it’s a point on the second, complex elliptic curve. The addition of H(m) to itself is similarly weird.
To verify a signature, we take the message m, the signature σ, and the public key pk. We are verifying that the message was signed with the secret key (sk) that corresponds to pk.
The signature is valid if and only if e(g1, σ) = e(pk, H(m)), which can be easily verified (preferably by a computer) given the generator (which is chosen in a specific and reproducible way), the signature, the public key, and the hash of the message.
We can use a simpler example to understand how pairings are useful in BLS. We will use the simple example bilinear function f(x,y) = xy.
So,
pk = public key = secret key * generator = sk * g1
σ = signature = secret key * H(message) = sk * H(m)
If the message was signed by the corresponding public key, then the following two function inputs will produce the same output (without revealing the secret key):
f(g1, σ) = g1 * σ = g1 * sk * H(m)
f(pk, H(m)) = pk * H(m) = sk * g1 * H(m) = g1 * sk * H(m)
(Bold is just for emphasis.)