Part 2: Technical Overview
The Building Blocks
- 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 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.
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.
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.
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.
There are four component pieces of data within the BLS digital signature process.
- 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.
- 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.
- 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.
- 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: defined over a base field , and defined over the field extension . The order of both the subgroups is , a 77 digit prime number. The (arbitrarily chosen) generator of is , and of , .
- The secret key, , is a number between and (technically the range includes , but not . However, very small values of would be hopelessly insecure).
- The public key, , is where the square brackets represent scalar multiplication of the elliptic curve group point. The public key is thus a member of the group.
- The message, is a sequence of bytes. During the signing process this will be mapped to some point that is a member of the group.
- The signature, , is also a member of the group, namely .
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 . 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, is a 32 byte unsigned integer. The public key, , is a point on the curve, which is represented in-protocol in its compressed serialised form as a string of 48 bytes.
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 group. If the message's signing root is , then the point is where is a function that maps bytes to . 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 , the signing process itself is simple, being just a scalar multiplication of the point by the secret key:
Evidently the signature is also a member of the group, and it serialises to a 96 byte string in compressed form.
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 , and a point and outputs a point from a group . That is, for a pairing , .
Pairings are usually denoted and have very special properties. In particular, with and in and and in ,
- , and
(Conventionally and are written as additive groups, and as multiplicative, so the operator is point multiplication in .)
From this, we can deduce that all of the following identities hold:
Armed with our pairing, verifying a signature is straightforward. The signature is valid if and only if
That is, given the message , the public key , the signature , and the fixed public value (the generator of the group), we can verify that the message was signed by the secret key .
This identity comes directly from the properties of pairings described above.
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.
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
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, , 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.
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 the normal 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 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.
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 elliptic curve group, and the result will also be a member of the group, so it is mathematically indistinguishable from a non-aggregated public key, and has the same 48 byte size.
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.
This miracle is due to the bilinearity of the pairing operation. With an aggregate signature and a corresponding aggregate public key , and common message , we have the following identity, which is exactly the same as the verification identity for a single signature and public key.
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.
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 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.
- We can verify a single signature with two pairings.
- We can naively verify signatures with pairings.
- Or we can verify signatures via aggregation with just two pairings, additions in , and additions in . Each elliptic curve point additions is much, much cheaper than a pairing.
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 signatures occupies 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.
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.
Two useful examples of how aggregate signatures are used in practice are in aggregate attestations and in sync committee aggregates.
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.
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.
signature field is the validator's signature over the
AttestationData in the
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
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.
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.
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, ))
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.
BLS signatures are based on two elliptic curve groups, and . Elements of are small (48 bytes when serialised), and their group arithmetic is faster; elements of 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 and signatures in , 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 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 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.
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 , and I have a secret key, . But instead of publishing my true public key, I publish (that is, my real public key plus the inverse of yours). I can sign a message with my secret key to make . 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: .
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 secret key corresponding to their claimed public key. You see, the attacker doesn't have and cannot calculate the corresponding to . 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.
In addition to aggregation, the BLS scheme also supports threshold signatures. This is where a secret key is divided between validators. For a predefined value of , if 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 shares then the key still remains secure; if up to 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.
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.
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 it is computationally infeasible to work out what the secret key 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.
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
AggregateVerify functions correspond to
(privkey: int, message: Bytes) -> BLSSignature
- Sign a message with the validator's secret (private) key.
(pubkey: BLSPubkey, message: Bytes, signature: BLSSignature) -> bool
- Verify a signature given the public key and the message.
(signatures: Sequence[BLSSignature]) -> BLSSignature
- Aggregate a list of signatures.
(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.
(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 messages signed by validators and verifies their aggregate signature. The mathematics is similar to that above, but requires pairing operations rather than just two. But this is better than the pairings that would be required to verify the unaggregated signatures.
(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 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_fast_aggregate_verify() that I describe in the annotated spec.
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.
- 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.↩
- 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.↩
- 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.↩
- Unless you have to implement the thing, as I ended up doing in Java.↩
- 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.↩
- 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.↩