Part 2: Technical Overview

The Building Blocks

BLS Signatures

First cut \checkmark Revision TODO
  • Proof of stake protocols use digital signatures to identify their participants and hold them accountable.
  • BLS signatures can be aggregated together, making them efficient to verify at large scale.
  • Signature aggregation allows the beacon chain to scale to hundreds of thousands of validators.
  • Ethereum transaction signatures on the execution (Eth1) layer remain as-is.

Digital signatures

Digital signatures are heavily used in blockchain technology. A digital signature is applied to a message to ensure two things: (1) that the message has not been tampered with in any way; and (2) that the sender of the message is who it claims to be. Digital signatures are not new, and really developed during the 1980s as a result of the invention of asymmetric cryptography. However, more recent developments involving elliptic curve, pairing-based cryptography have heavily influenced the design of Ethereum 2.

Every time you send an Ethereum transaction you are using a digital signature; all Ethereum users are familiar with the signing work flow. But that's at the transaction level. At the consensus protocol level digital signatures are not used at all in Ethereum 1 – Under proof of work, a block just needs to have a correct mixHash proving that it was correctly mined, nobody cares who actually mined the block, so no signature is needed.

In Ethereum 2, however, validators have identities and are accountable for their actions. In order to enforce the Casper FFG rules, and in order to be able to count votes for the LMD GHOST fork choice, we need to be able to uniquely identify the validators making individual attestations and blocks.

Digital signature usage

The primary function of a digital signature is to irrevocably link the sender of a message with the contents of the message. This can be used, for example, to prove with certainty that a validator has published conflicting votes and thus is subject to being slashed.

The ability to tie messages to validators is also useful outside the protocol. For example, in the gossip layer, signatures are validated by nodes before they are forwarded as an anti-spam mechanism.

Alongside their usual function of identifying message senders, digital signatures have a couple of fairly novel uses within the Ethereum 2 protocol. They are used when contributing randomness to the RANDAO, and they are used to select subsets of committees for aggregation duty. We will discuss those usages in their respective sections and focus on the signing of protocol messages in this section.

Background

One of the characteristics of proof of stake protocols is the sheer number of protocol messages that need to be handled. With 300,000 active validators, the current beacon chain design calls for over 780 attestations per second to be gossiped globally. That's a sustained average, there are much higher bursts in practice. Not only do these messages need to travel over the network, but each individual digital signature needs to be verified by every node, which is a CPU-intensive operation. Not to mention having to store all those signed messages in the block history. These challenging requirements have typically limited the validator numbers in proof of stake or proof of authority networks. Pure PBFT-based consensus protocols tend to have validator sets that number in the dozens rather than the thousands.

The prevailing work-in-progress design in early 2018 for Ethereum's (partial) move to proof of stake, EIP-1011, estimated that the protocol could handle a maximum of around 900 validators due to this message overhead, and accordingly set a hefty stake size of 1500 ETH per validator.

The turning point came in May 2018 with the publication by Justin Drake of an article on the Ethresear.ch forum titled Pragmatic signature aggregation with BLS. The article proposed using a new signature scheme that is able to aggregate many digital signatures into one while preserving the individual accountability of each validator that signed. Aggregation provides a way to dramatically reduce the number of individual messages that must be gossiped around the network and the cost of verifying the integrity of those messages, and thus enables scaling to hundreds of thousands of participants.1

This signature aggregation capability was the main breakthrough that prompted us to abandon the EIP-1011 on-chain PoS management mechanism entirely and move to the "beacon chain" model that we have today2.

BLS Signatures

Digital signatures in the blockchain world are usually based on elliptic curve groups. For signing users' transactions, Ethereum uses ECDSA signatures with the secp256k1 elliptic curve. However, the beacon chain protocol uses BLS signatures with the BLS12-381 elliptic curve3. Although similar in usage, ECDSA and BLS signatures are mathematically quite different, with the latter relying on a special property of certain elliptic curves called "pairing". Although ECDSA signatures are much faster than BLS signatures, it is the pairing property of BLS signatures that allows us to aggregate signatures, thus making the whole consensus protocol practical.

Several other blockchain protocols have adopted or will adopt BLS signatures over the BLS12-381 curve, and throughout our implementation in Eth2 we have been mindful to follow whatever standards exist, and to participate in the defining of those standards where possible. This both helps interoperability and supports the development of common libraries and tooling.

The high-level workflow for creating and verifying a BLS signature is relatively straightforward. In the sections that follow I'll describe how it all works with some words, some pictures, and some maths. Feel free to skip the maths if you wish, it's not compulsory and there's no test at the end. Though it is rather elegant.

Components

There are four component pieces of data within the BLS digital signature process.

  1. The secret key. Every entity acting within the protocol (that is, a validator in the context of Eth2) has a secret key, sometimes called a private key. The secret key is used to sign messages and must be kept secret, as its name suggests.
  2. The public key. The public key is uniquely derived from the secret key, but the secret key cannot be reverse engineered from it (without impossibly huge amounts of work). A validator's public key represents its identity within the protocol, and is known to everybody.
  3. The message. We'll look later at the kinds of messages used in the Eth2 protocol and how they are constructed. For now, the message is just a string of bytes.
  4. The signature, which is the output of the signing process. The signature is created by combining the message with the secret key. Given a message, a signature for that message, and a public key, we can verify that the validator with that public key signed exactly that message. In other words, no-one else could have signed that message, and the message has not been changed since signing.

More mathematically, things look like this. We use two subgroups of the BLS12-381 elliptic curve: G1G_1 defined over a base field FqF_q, and G2G_2 defined over the field extension Fq2F_{q^2}. The order of both the subgroups is rr, a 77 digit prime number. The (arbitrarily chosen) generator of G1G_1 is g1g_1, and of G2G_2, g2g_2.

  1. The secret key, sksk, is a number between 11 and rr (technically the range includes 11, but not rr. However, very small values of sksk would be hopelessly insecure).
  2. The public key, pkpk, is [sk]g1[sk]g_1 where the square brackets represent scalar multiplication of the elliptic curve group point. The public key is thus a member of the G1G_1 group.
  3. The message, mm is a sequence of bytes. During the signing process this will be mapped to some point H(m)H(m) that is a member of the G2G_2 group.
  4. The signature, σ\sigma, is also a member of the G2G_2 group, namely [sk]H(m)[sk]H(m).

Diagram showing how we will depict the various components in the diagrams below The key to the keys. This is how we will depict the various components in the diagrams below. Variants of the same object are hatched differently. The secret key is mathematically a scalar; public keys are G1G_1 group members; message roots are mapped to G2G_2 group members; and signatures are G2G_2 group members.

Key pairs

A key pair is a secret key along with its public key. Together these irrefutably link each validator with its actions.

Every validator on the beacon chain has at least one key pair, the "signing key" that is used in daily operations (making attestations, producing blocks, etc.). Depending on which version of withdrawal credentials the validator is using, it may also have a second BLS key pair, the "withdrawal key", that is kept offline.

The secret key is supposed to be uniformly randomly generated in the range [1,r)[1,r). EIP-2333 defines a standard way to do this based on the KeyGen method of the draft IETF BLS signatures standard. It's not compulsory to use this method – no-one will ever know if you don't – but you'd be ill advised not to. In practice, many stakers generate their keys with the eth2.0-deposit-cli tool created by the Ethereum Foundation. Operationally, key pairs are often stored in password-protected EIP-2335 keystore files.

The secret key, sksk is a 32 byte unsigned integer. The public key, pkpk, is a point on the G1G_1 curve, which is represented in-protocol in its compressed serialised form as a string of 48 bytes.

Diagram of the generation of the public key A validator randomly generates its secret key. Its public key is then derived from that.

Signing

In the beacon chain protocol the only messages that get signed are hash tree roots of objects: their so-called signing roots, which are 32 byte strings. The compute_signing_root() function always combines the hash tree root of an object with a "domain" as described below.

Once we have the signing root it needs to be mapped onto an elliptic curve point in the G2G_2 group. If the message's signing root is mm, then the point is H(m)H(m) where H()H() is a function that maps bytes to G2G_2. This mapping is hard to do well and an entire draft standard exists to define the process. Thankfully, we can ignore the details completely and leave them to our cryptographic libraries4.

Now that we have H(m)H(m), the signing process itself is simple, being just a scalar multiplication of the G2G_2 point by the secret key:

σ=[sk]H(m)\sigma = [sk]H(m)

Evidently the signature σ\sigma is also a member of the G2G_2 group, and it serialises to a 96 byte string in compressed form.

Diagram of signing a message A validator applies its secret key to a message to generate a unique digital signature.

Verifying

To verify a signature we need to know the public key of the validator that signed it. Every validator's public key is stored in the beacon state and can be simply looked up via the validator's index which, by design, is always available by some means whenever it's required.

Signature verification can be treated as a black-box: we send the message, the public key, and the signature to the verifier; if after some cryptographic magic the signature matches the public key and the message then we declare it valid. Otherwise, either the signature is corrupt, the incorrect secret key was used, or the message is not what was signed.

More formally, signatures are verified using elliptic curve pairings.

With respect to the curve BLS12-381, a pairing simply takes a point PG1P\in G_1, and a point QG2Q\in G_2 and outputs a point from a group GTFq12G_T\subset F_{q^{12}}. That is, for a pairing ee, e:G1×G2GTe:G_1\times G_2\rightarrow G_T.

Pairings are usually denoted e(P,Q)e(P,Q) and have very special properties. In particular, with PP and SS in G1G_1 and QQ and RR in G2G_2,

  • e(P,Q+R)=e(P,Q)e(P,R)e(P, Q + R) = e(P, Q) \cdot e(P, R), and
  • e(P+S,R)=e(P,R)e(S,R)e(P + S, R) = e(P, R) \cdot e(S, R).

(Conventionally G1G_1 and G2G_2 are written as additive groups, and GTG_T as multiplicative, so the \cdot operator is point multiplication in GTG_T.)

From this, we can deduce that all of the following identities hold:

e([a]P,[b]Q)=e(P,[b]Q)a=e(P,Q)ab=e(P,[a]Q)b=e([b]P,[a]Q)e([a]P,[b]Q)=e(P,[b]Q)^a=e(P,Q)^{ab}=e(P,[a]Q)^b=e([b]P,[a]Q)

Armed with our pairing, verifying a signature is straightforward. The signature is valid if and only if

e(g1,σ)=e(pk,H(m))e(g_1,\sigma)=e(pk,H(m))

That is, given the message mm, the public key pkpk, the signature σ\sigma, and the fixed public value g1g_1 (the generator of the G1G_1 group), we can verify that the message was signed by the secret key sksk.

This identity comes directly from the properties of pairings described above.

e(pk,H(m))=e([sk]g1,H(m))=e(g1,H(m))(sk)=e(g1,[sk]H(m))=e(g1,σ)e(pk,H(m)) = e([sk]g_1,H(m)) = e(g_1,H(m))^{(sk)} = e(g_1,[sk]H(m)) = e(g_1,\sigma)

Note that elliptic curves supporting such a pairing function are very rare. Such curves can be constructed, as BLS12-381 was, but general elliptic curves such as the more commonly used secp256k1 curve do not support pairings and cannot be used for BLS signatures.

Diagram of verifying a signature To verify that a particular validator signed a particular message we use the validator's public key, the original message, and the signature. The verification operation outputs true if the signature is correct and false otherwise.

The verification will return True if and only if the signature corresponds both to the public key (that is, the signature and the public key were both generated from the same secret key) and to the message (that is, the message is identical to the one that was signed originally). Otherwise it will return False.

Aggregation

So far we've looked at the basic set up of BLS signatures. In functional terms, what we've seen is very similar to any other digital signature scheme. Where the magic happens is in aggregation.

Aggregation means that multiple signatures over the same message – potentially thousands of signatures – can be checked with a single verification operation. Furthermore, the aggregate signature has the same size as a regular signature, 96 bytes. This is a massive gain in scalability, and it is this gain that fundamentally makes the Ethereum 2 consensus protocol viable.

How does this work? Recall that public keys and signatures are elliptic curve points. Because of the bilinearity property of the pairing function, e()e(), it turns out that we can form linear combinations of public keys and signatures over the same message, and verification still works as expected.

This statement is a little opaque; let's go step by step.

Aggregating signatures

In all of the following we will only consider aggregation of signatures over the same message5.

The process is conceptually very simple: we simply "add up" the signatures. The exact operations are not like normal the addition of numbers that we are familiar with, but the operation is completely analogous. Addition of points on the elliptic curve is the group operation for the G2G_2 group, and each signature is a point in this group, thus the result is also a point in the group. An aggregated signature is mathematically indistinguishable from a non-aggregated signature, and has the same 96 byte size.

Diagram showing aggregation of signatures Aggregation of signatures is simply group addition in the G2G_2 group.

Aggregating public keys

To verify an aggregate signature, we need an aggregate public key. As long as we know exactly which validators signed the original message, this is equally easy to construct. Once again we simply "add up" the public keys of the signers. This time the addition is the group operation of the G1G_1 elliptic curve group, and the result will also be a member of the G1G_1 group, so it is mathematically indistinguishable from a non-aggregated public key, and has the same 48 byte size.

Diagram of public key aggregation Aggregation of public keys is simply group addition in the G1G_1 group.

Verifying aggregate signatures

Since aggregate signatures are indistinguishable from normal signatures, and aggregate public keys are indistinguishable from normal public keys, we can simply feed them into our normal verification algorithm.

Diagram of verification of an aggregate signature Verification of an aggregate signature is identical to verification of a normal signature as long as we use the corresponding aggregate public key.

This miracle is due to the bilinearity of the pairing operation. With an aggregate signature σagg\sigma_{agg} and a corresponding aggregate public key pkaggpk_{agg}, and common message mm, we have the following identity, which is exactly the same as the verification identity for a single signature and public key.

e(pkagg,H(m))=e(pk1+pk2++pkn,H(m))=e([sk1+sk2++skn]g1,H(m))=e(g1,H(m))(sk1+sk2++skn)=e(g1,[sk1+sk2++skn]H(m))=e(g1,σ1+σ2++σn)=e(g1,σagg)\begin{aligned} e(pk_{agg},H(m)) &= e(pk_1 + pk_2 + \ldots + pk_n,H(m)) \\ &= e([sk_1 + sk_2 + \ldots + sk_n]g_1,H(m)) \\ &= e(g_1,H(m))^{(sk_1 + sk_2 + \ldots + sk_n)} \\ &= e(g_1,[sk_1 + sk_2 + \ldots + sk_n]H(m)) \\ &= e(g_1,\sigma_1 + \sigma_2 + \ldots + \sigma_n) \\ &= e(g_1,\sigma_{agg}) \end{aligned}
Benefits of aggregation

Verification of a BLS signature is expensive (resource intensive) compared with verification of an ECDSA signature, more than an order of magnitude slower due to the pairing operation, so what benefits do we gain?

The benefits accrue when we are able to aggregate significant numbers of signatures. This is exactly what we have with beacon chain attestation committees. Ideally, all the validators in the committee sign-off on the same attestation data, so all their signatures can be aggregated. In practice, there might be differences of opinion about the chain state between committee members resulting in two or three different attestations, but even so there will be many fewer aggregates compared with the total number of committee members.

Speed benefits

To a first approximation, then, we can verify all of the attestations of a whole committee – potentially hundreds – with a single signature verification operation.

This is a first approximation because we also need to account for aggregating the the public keys and the signatures. But these aggregation operations involve only point additions in their respective elliptic curve groups, which are very cheap compared with the verification.

In summary:

  • We can verify a single signature with two pairings.
  • We can naively verify NN signatures with 2N2N pairings.
  • Or we can verify NN signatures via aggregation with just two pairings, N1N-1 additions in G1G_1, and N1N-1 additions in G2G_2. Each elliptic curve point additions is much, much cheaper than a pairing.
Space benefits

There is also a huge space saving when we aggregate signatures.

An aggregate signature has 96 bytes as all BLS signatures do. So, to a first approximation, an aggregate of NN signatures occupies 1N\frac{1}{N} the space of the unaggregated signatures.

Again, this is only a first approximation. The subtlety here is that, in order to construct the corresponding aggregate public key, we somehow need to keep track of which validators signed the message. We cannot assume that the whole committee participated, and we need to be careful not to include any validator more than once.

If we know in advance who the members of the committee are and how they are ordered then this tracking can be done at the marginal cost of one bit per validator: true if the validator contributed to the aggregate, false if it did not.

The full picture

This diagram illustrates the full flow from signing, through aggregating, to verifying. There are three validators in this case, although there could be many more, and each is signing the same message contents. Each validator has its own unique secret key and public key pair. The workflow is entirely non-interactive, and any of the actions before the verification can happen independently. Even the aggregation can be done incrementally.

Diagram showing the end-to-end aggregate signature workflow The end-to-end aggregate signature workflow. Verifying the single aggregate signature is much faster than verifying the original signatures separately.

Aggregation examples

Two useful examples of how aggregate signatures are used in practice are in aggregate attestations and in sync committee aggregates.

Aggregate attestations

Aggregate attestations are a very compact way store and prove which validators made a particular attestation.

Within each beacon chain committee at each slot, individual validators attest to their view of the chain, as described in the validator spec.

An Attestation object looks like this:

class Attestation(Container):
    aggregation_bits: Bitlist[MAX_VALIDATORS_PER_COMMITTEE]
    data: AttestationData
    signature: BLSSignature

When making its attestation, the validator sets a single bit in the aggregation_bits field to indicate which member of the committee it is. That is sufficient, in conjunction with the slot number and the committee index, to uniquely identify the attesting validator in the global validator set.

The signature field is the validator's signature over the AttestationData in the data field.

This attestation will later be aggregated with other attestations from the committee that contain identical data. An attestation is added to an aggregate by copying over its bit from the aggregation_bits field and adding (in the sense of elliptic curve addition) its signature to the signature field. Aggregate attestations can be aggregated together in the same way, but only if their aggregation_bits lists are disjoint: we must not include a validator more than once. (In principle we could include individual validators multiple times, but then we'd need more than a single bit to track how many times, and the redundancy is not useful.)

This aggregate attestation will be gossiped around the network and eventually included in a block. At each step the aggregate signature will be verified.

To verify the signature, a node needs to reconstruct the list of validators in the committee, which it can do from the information in the AttestationData:

class AttestationData(Container):
    slot: Slot
    index: CommitteeIndex
    beacon_block_root: Root
...

Given the reconstructed list of committee members, the validating node filters the list according to which aggregation_bits are set in the attestation. Now it has the indices of all the validators that contributed to this attestation. The node retrieves the public keys of those validators from the beacon state and aggregates those keys together (by elliptic curve addition).

Finally, the aggregate signature, the aggregate public key, and the signing root of the data are fed into the standard BLS signature verification function. If all is well this will return True, else the aggregate attestation is invalid.

Sync aggregates

SyncAggregates are produced by a sync committee of 512 members.

class SyncAggregate(Container):
    sync_committee_bits: Bitvector[SYNC_COMMITTEE_SIZE]
    sync_committee_signature: BLSSignature

The current members of the SyncCommittee are stored in the beacon state in the following form:

class SyncCommittee(Container):
    pubkeys: Vector[BLSPubkey, SYNC_COMMITTEE_SIZE]
    aggregate_pubkey: BLSPubkey

Production and aggregation of sync committee messages differs slightly from attestations, but is sufficiently similar that I'll skip over it here.

The main points of interest are that the SyncCommittee object contains the actual public keys of all the members (possibly with duplicates), rather than validator indices. It also contains a pre-computed aggregate_pubkey field that is the aggregate of all the public keys in the committee.

The idea of this is to reduce the computation load for light clients, who will be the ones needing to verify the SyncAggregate signatures. Sync committees are expected to have high participation, with, say, 90% of the validators contributing. To verify the aggregate signature we need to aggregate the public keys of all the contributors. Starting from an empty set, that would mean 461 elliptic curve point additions (90% of 512). However, if we start from the full set, aggregate_pubkey, then we can achieve the same thing by subtracting the 10% that did not participate. That's 51 elliptic curve subtractions (which have the same cost as additions) and nine times less work.

Various topics

Domain separation and forks

Every signature that's used in the Eth2 protocol has a domain value mixed into the message before signing. This is taken care of by the compute_signing_root() function which both calculates the SSZ hash tree root of the object to be signed and mixes in the given domain.

def compute_signing_root(ssz_object: SSZObject, domain: Domain) -> Root:
    return hash_tree_root(SigningData(
        object_root=hash_tree_root(ssz_object),
        domain=domain,
    ))

The domain, in turn, is calculated by the compute_domain() function which combines one of ten domain types with a mash-up of the fork version and the genesis validators root.

Each of the extra quantities that's rolled into the message has a specific purpose.

  • The domain type ensures that signatures made for one purpose cannot be re-used for a different purpose. Objects of different SSZ types are not guaranteed to have unique hash tree roots, and we would rather like to be able to tell the difference between them. The ten domain types are all the different ways signatures are used in the protocol.
  • The genesis validators root uniquely identifies this particular beacon chain, distinguishing it from any other testnet or alternative chain. This ensures that signatures from different chains are always incompatible.
  • The fork version identifies deliberate consensus upgrades to the beacon chain. Mixing the fork version into the message ensures that messages from validators that have not upgraded are invalid. They are out of consensus and have no information that is useful to us, so this provides a convenient way to ignore their messages. Alternatively, a validator may wish to operate on both sides of a contentious fork, and the fork version provides a way for them to do so safely.

The sole exception to the mixing-in of the fork version is signatures on deposits. Deposits are always valid, however the beacon chain gets upgraded.

Choice of groups

BLS signatures are based on two elliptic curve groups, G1G_1 and G2G_2. Elements of G1G_1 are small (48 bytes when serialised), and their group arithmetic is faster; elements of G2G_2 are large (96 bytes when serialised) and their group arithmetic is slower, perhaps three times slower.

We can choose to use either group for public keys, as long as we use the other group for signatures: the pairing function doesn't care; everything still works if we swap the groups over. The original paper describing BLS aggregate signatures has public keys in G2G_2 and signatures in G1G_1, while for Ethereum 2 we made the opposite choice.

The main reason for this is that we want public key aggregation to be as fast as possible. Signatures are verified much more often than they are aggregated – by far the main load on beacon chain clients currently is signature verification – and verification requires public key aggregation. So we choose to have our public keys in the faster G1G_1 group. This also has the benefit of reducing the size of the beacon state, since public keys are stored in validator records. If we were to use the G2G_2 group for public keys, the beacon state would be about 35% larger.

The trade-off is that protocol messages and beacon chain blocks are larger due to the larger signature size.

Fundamentally, verification of aggregate signatures is an "on-chain" activity that we wish to be as light as possible, and signature aggregation is "off-chain" so can be more heavyweight.

Proof of possession

There is a possible attack on the BLS signature scheme that we wish to avoid, the "rogue public key" attack.

Say your public key is pk1pk_1, and I have a secret key, sk2sk_2. But instead of publishing my true public key, I publish pk2=[sk2]g1pk1pk'_2=[sk_2]g_1-pk_1 (that is, my real public key plus the inverse of yours). I can sign a message H(m)H(m) with my secret key to make σ=[sk2]H(m)\sigma=[sk_2]H(m). I then publish this claiming that it is an aggregate signature that both you and I have signed.

Now, when verifying with my rogue public key and your actual public key, the claim checks out: it looks like you signed the message when you didn't: e(g1,σ)=e(g1,[sk2]H(m))=e([sk2]g1,H(m))=e(pk1+pk2,H(m))e(g1,\sigma)=e(g_1,[sk_2]H(m))=e([sk_2]g_1,H(m))=e(pk_1+pk'_2,H(m)).

One relatively simple defence against this – the one we are using in Ethereum 2 – is to force validators to register a "proof of possession" of the private key corresponding to their claimed public key. You see, the attacker doesn't have and cannot calculate the sk2sk'_2 corresponding to pk2pk'_2. The proof of possession can be done simply by getting all validators to sign their public keys on registration, that is, when they deposit their stakes in the deposit contract. If the actual signature validates with the claimed public key then all is well.

Threshold signatures

In addition to aggregation, the BLS scheme also supports threshold signatures. This is where a secret key is divided between NN validators. For a predefined value of MNM \le N, if MM of the validators sign a message then a single joint public key of all the validators can be used to verify the signature.

Threshold signatures are not currently used within the core Ethereum 2 protocol. However they are useful at an infrastructure level. For example, for security and resilience it might be desirable to split a validator's secret key between multiple locations. If an attacker acquires fewer than MM shares then the key still remains secure; if up to MNM-N keystores are unavailable, the validator can still sign correctly. An operational example of this is Attestant's Dirk key manager.

Threshold signatures also find a place in Distributed Validator Technology, which I will write about in a different chapter.

Batch verification

The bilinearity of the pairing function allows for some pretty funky optimisations. For example, Vitalik has formulated a method for verifying a batch of signatures simultaneously – such as all the signatures contained in a block – that significantly reduces the number of pairing operations required. Since this technique constitutes a client-side optimisation rather than being a fundamental part of the protocol, I shall describe it properly in the Implementation chapter.

Quantum security

The security (unforgeability) of BLS signatures relies, among other things, on the hardness of something called the elliptic curve discrete logarithm problem (ECDLP)6. Basically, given the public key [sk]g1[sk]g_1 it is computationally infeasible to work out what the secret key sksk is.

The ECDLP is believed to be vulnerable to attack by quantum computers, thus our signature scheme may have a limited shelf-life.

Quantum-resistant alternatives such as zkSTARKs are known, but currently not as practical as the BLS scheme. The expectation is that, at some point, we will migrate to such a scheme as a drop-in replacement for BLS signatures.

In case someone overnight unveils a sufficiently capable quantum computer, EIP-2333 (which is a standard for BLS key generation in Ethereum) describes a way to generate a hierarchy of Lamport signatures. Lamport signatures are believed to be quantum secure, but come with their own limitations. In principle we could make an emergency switch over to these to tide us over while implementing STARKs. But this would be extremely challenging in practice.

BLS library functions

As a reference, the following are the BLS library functions used in the Ethereum 2 specification. They are named for and defined by the BLS Signature Standard. Function names link to the definitions in the standard. Since we use the proof of possession scheme defined in the standard, our Sign, Verify, and AggregateVerify functions correspond to CoreSign, CoreVerify, and CoreAggregateVerify respectively.

  • def Sign(privkey: int, message: Bytes) -> BLSSignature
    • Sign a message with the validator's private key.
  • def Verify(pubkey: BLSPubkey, message: Bytes, signature: BLSSignature) -> bool
    • Verify a signature given the public key and the message.
  • def Aggregate(signatures: Sequence[BLSSignature]) -> BLSSignature
    • Aggregate a list of signatures.
  • def FastAggregateVerify(pubkeys: Sequence[BLSPubkey], message: Bytes, signature: BLSSignature) - bool
    • Verify an aggregate signature given the message and the list of public keys corresponding to the validators that contributed to the aggregate signature.
  • def AggregateVerify(pubkeys: Sequence[BLSPubkey], messages: Sequence[Bytes], signature: BLSSignature) -> bool
    • This is not used in the current spec but appears in the future Proof of Custody spec. It takes nn messages signed by nn validators and verifies their aggregate signature. The mathematics is similar to that above, but requires n+1n+1 pairing operations rather than just two. But this is better than the 2n2n pairings that would be required to verify the unaggregated signatures.
  • def KeyValidate(pubkey: BLSPubkey) -> bool
    • Checks that a public key is valid. That is, it lies on the elliptic curve, it is not the group's identity point (corresponding to the zero secret key), and it is a member of the G1G_1 subgroup of the curve. All these checks are important to avoid certain attacks. The group membership check is quite expensive but only ever needs to be done once per public key stored in the beacon state.

The Eth2 spec also defines two further BLS utility functions, eth_aggregate_pubkeys() and eth_fast_aggregate_verify() that I describe in the annotated spec.

See also

The main standards that we strive to follow are the following IETF drafts:

Compact Multi-Signatures for Smaller Blockchains (Boneh, Drijvers, Neven) is the original paper that described efficient BLS multi-signatures. And Pragmatic signature aggregation with BLS is Justin Drake's proposal to use these signatures in an Ethereum 2 context.

For a gentle(ish) introduction to pairings, Vitalik's Exploring Elliptic Curve Pairings is very good. If you are looking for a very deep rabbit hole to explore, Pairings for Beginners by Craig Costello is amazing.

I've written a lengthy homage to the BLS12-381 elliptic curve that also covers some BLS signature topics.

Three EIPs are intended to govern the generation and storage of keys in practice:

  • EIP-2333 provides a method for deriving a tree-hierarchy of BLS12-381 keys based on an entropy seed.
  • EIP-2334 defines a deterministic account hierarchy for specifying the purpose of keys.
  • EIP-2335 specifies a standard keystore format for storage and interchange of BLS12-381 keys.

There are several implementations of pairings on the BLS12-381 curve around, which can be used to implement the BLS signature scheme we use:

  • The Blst library is the most commonly used by Eth2 client implementers.
  • The noble-bls12-381 library is better documented and may be more enjoyable if you want to try playing around with these things.

  1. To give credit where it is due, the Dfinity blockchain researchers had published a white paper a few months earlier proposing the use of BLS signatures in a threshold scheme. However, their use of threshold signatures makes the chain vulnerable to liveness failures, and also requires a tricky distributed key generation protocol. Ethereum's aggregation-based approach has neither of these issues. Nonetheless, the name "beacon chain" that we still use today derives from Dfinity's "randomness beacon" described in that paper.
  2. The last significant update to EIP-1011 was made on the 16th of May, 2018. Justin Drake's post on signature aggregation was made just two weeks later.
  3. There is a curious naming collision here. The BLS trio of "BLS signatures" are Boneh, Lynn, and Shacham, whereas those of the "BLS12-381" elliptic curve are Barreto, Lynn, and Scott. Ben Lynn is the only common name between the two.
  4. Unless you have to implement the thing, as I ended up doing in Java.
  5. A note on terminology. The original paper describing this scheme uses the term "multi-signature" when combining signatures over the same message, and "aggregate signature" when combining signatures over distinct messages. In Eth2 we only do the former, and just call it aggregation.
  6. It's puzzling to me that this is called the discrete logarithm problem when we write groups additively, rather than the discrete division problem. But it's far from being the most confusing thing about elliptic curves.

Created by Ben Edgington. Licensed under CC BY-SA 4.0. Published 2022-05-12 12:26 UTC. Commit 0cc9f0b.