BLS Signatures & Withdrawals

TL;DR

‍

In this post, we examine the BLS signatures and their role in Ethereum, specifically in withdrawals which will be allowed after the upcoming Shanghai/Capella hard fork. We define the scheme, the BLS12–381 curve, including the subgroups and hash to curve function. Then, we describe the aggregation property of BLS signatures and two challenges against aggregation. Finally, we conclude with how we use BLS signatures in the withdrawals.

‍

‍

‍

Introduction

‍

The Merge transitioned the network from a proof-of-work (PoW) to a proof-of-stake (PoS) consensus mechanism. This transition was a crucial step toward achieving the long-term scalability and sustainability goals of the Ethereum network.

‍

The staking process is a key part of the PoS mechanism. Ethereum holders can lock up their ETH in a validator node and participate in the network’s consensus mechanism. The Shanghai/Capella hard fork (Shanghai in the execution layer and Capella in the consensus layer) will enable the validators to exit, perform a full withdrawal, or change the prefix of their withdrawal credential in order to be able to collect their rewards via automatic partial withdrawals. All these operations demand the validators sign a message using either their BLS validator private key or their BLS withdrawal private key (depending on the operation).

‍

‍

‍

BLS Signature

‍

In Ethereum, validators sign and attest blocks to ensure that all of them follow the consensus rules honestly. Storing and verifying those signatures on-chain may lead to scalability issues as the number of validators (more than 500K at the time of writing) increases. However, using a signature scheme like BLS can help to address this problem.

‍

BLS signature is a digital signature scheme proposed by Boneh, Lynn, and Shacham in 2001. The scheme relies on the hardness of the Computational Diffie-Hellman (CDH) Problem to prevent forgery. A high-level description of the BLS scheme goes as follows. The user randomly chooses a secret key from a predetermined field and computes the corresponding public key as a point on a predetermined elliptic curve. To sign, the user multiplies the hash of the message (a curve point) by the secret key (a field element). The resulting signature is also a curve point. For verification of the signature, a bilinear pairing is used.

‍

‍

Bilinear pairings

‍

Let 𝔽ᵣ be the finite field with prime order r, 𝔾₁ and 𝔾₂ be two additive cyclic groups with prime order r, and 𝔾ₜ be a multiplicative target group with the same order. Let g₁, g₂ be generators of 𝔾₁ and 𝔾₂, respectively. A bilinear pairing is a map e : 𝔾₁ × 𝔾₂ → 𝔾ₜ that is:
‍

1. Bilinear: For all field elements a, b ∈ 𝔽ᵣ and for all group elements P ∈ 𝔾₁ and Q ∈ 𝔾₂, it holds that e(a⋅ P, b⋅ Q) = e(P, Q)ᵃᵇ.
   ‍
2. Non-degenerate: For all nonzero A ∈ 𝔾₁ (resp. all nonzero B ∈ 𝔾₂) there exist B ∈ 𝔾₂ (resp. A ∈ 𝔾₁) such that e(A, B) ≠ 1.

‍

‍

The scheme

‍

Let 𝔾₁, 𝔾₂, g₁, g₂, and e be as above; and let H: {0,1}* → 𝔾₂ be a hash function which maps any binary string to the group 𝔾₂.

‍

BLS signature scheme consists of three algorithms, i.e., key generation, signature generation, and verification, such that:

‍

KeyGen(par) → (sk, pk): The key generation algorithm takes the public parameters par as input and outputs the key pair as follows:

‍

• chooses a uniformly random secret key, sk ← 𝔽ᵣ
• computes the corresponding public key pk ← sk ⋅ g₁ (Note that pk ∈ 𝔾₁)
  ‍

Sign(par, M, sk) → σ: The signature generation algorithm takes the public parameters par, the message M and the secret key sk as inputs, and outputs the signature σ as follows:
‍

• computes the hash h ∈ 𝔾₂ of the message M, i.e. h ← H(M)
• computes the signature σ ∈ 𝔾₂ on the message M, i.e., σ ← sk ⋅ h

Verify(par, M, σ, pk) → 1/0: The verification algorithm takes public parameters par, the message M, the signature σ and the public key pk as inputs, and outputs “accept” if e(pk, h) = e(g₁, σ), “reject” otherwise.

‍

‍

The curve

‍

To instantiate the BLS signature, the Ethereum Foundation (EF) uses the BLS12–381 curve, a pairing-friendly elliptic curve constructed by Sean Bowe in [Bow17]. The curve provides ~128-bit security and is a member of a family of curves defined in [BLS02]. Let us break down the meaning of “BLS”, “12”, and “381”:

‍

• BLS stands for the curve family
  ‍
• 12 is the embedding degree (see below)
  ‍
• 381 is the number of bits for representing the coordinates of the points
  ‍

As described in the pairing definition above, a pairing takes two elements from groups 𝔾₁ and 𝔾₂ and maps them to an element of the third group 𝔾ₜ. In the BLS12–381, 𝔾₁ is of prime order, say r. Furthermore, it is a subgroup of an elliptic curve group E(𝔽ₚ) with curve equation y² = x³ + 4. Pairings require 𝔾₁ to be of the same order as 𝔾₂. Unfortunately, E(𝔽ₚ) does not include any other subgroup with prime order r. Hence, the underlying field 𝔽ₚ needs to be extended until an elliptic curve group with another subgroup of order r is found. In BLS12–381, the elliptic curve group E(𝔽ₚ¹²) has the required subgroup. The number 12 is called the embedding degree of the curve.

‍

Now we have two different subgroups with the same prime order r, i.e., 𝔾₁ ⊂ E(𝔽ₚ) and 𝔾₂ ⊂ E(𝔽ₚ¹²). Can we perform pairing computation now? Yes, we have all we need. But we also have an efficiency problem because of the complexity of the arithmetic in 𝔽ₚ¹². Luckily, there is a notion of “twist” that is a kind of coordinate transformation. Using this transformation, we obtain a subgroup 𝔾₂ of order r of another elliptic curve group E’(𝔽ₚ²) with equation y² = x³ + 4(1 + i).

Using the embedding degree and the twist, we have two distinct subgroups of prime order r.

‍

💡 Notice that the coordinates of the points in 𝔾₁ are elements of 𝔽ₚ, but the coordinates of the points in 𝔾₂ are elements of 𝔽ₚ². That is why 𝔾₁ has points of smaller size, and it provides faster operations than 𝔾₂. Note that, for BLS12–381, 𝔾₁ and 𝔾₂ have elements of size 48 and 96 bytes, respectively.

‍

For more information about the curve, we suggest Ben Edgington’s post, BLS12–381 For The Rest Of Us.

‍

‍

The choice of the subgroups

‍

As you can see from the definition of the BLS signature scheme, the signature and the public key must be defined in opposite groups to make the verification work. Usually, the signature in the BLS scheme is a 𝔾₁ element, while the public key is in 𝔾₂ because the signature size is generally desired to be as small as possible for efficiency reasons. However, in the above definition, the signature is an element of 𝔾₂, and the public key is an element of 𝔾₁. That’s also how EF defines the BLS signature. There is a couple of reasons behind this choice:

‍

• To reduce the computational cost: The signature aggregation is an “off-chain” operation. Once the signatures are aggregated, the result is sent to the Beacon chain. On the other hand, the most load in the consensus layer clients comes from the signature verification, which requires public keys aggregation (cf. BLS Signatures). Hence, making the key aggregation as light as possible is crucial.
  ‍
• To store less data on-chain: Since the public keys of the validators are stored in the Beacon chain’s state, it is crucial to choose them as small as possible.
  
  ‍

Hashing to elliptic curves

‍

The BLS signature scheme requires a hash function that maps an arbitrary length message to a point in 𝔾₂. A natural way to map a point from a curve E’(𝔽ₚ²) to its subgroup 𝔾₂ is called cofactor clearing and is performed by scalar multiplication of the point A₁ ∈ E’(𝔽ₚ²) with cofactor c₂ = d/r, i.e., A₂ = c₂ ⋅ A₁, where d = |E’(𝔽ₚ²)| and r = |𝔾₂|. The resulting point A₂ is an element of 𝔾₂.

‍

💡 The reason why A₂ is an element of 𝔾₂ is that the set of 𝔾₂-cosets {A + 𝔾₂ | A ∈ E’(𝔽ₚ²) } (i.e. the quotient E’(𝔽ₚ²)/𝔾₂) forms a group of order c₂ = d/r. Hence c₂ ⋅ (A + 𝔾₂) is the identity element of such a group, namely 𝔾₂, and so c₂ ⋅ (A + 𝔾₂) = c₂ ⋅ A + 𝔾₂ = 𝔾₂ as cosets. This is equivalent to saying that c₂ ⋅ A ∈ 𝔾₂, as needed.

‍

However, we need to translate our message to a point in the curve E’(𝔽ₚ²) before performing cofactor clearing. The authors of the BLS signature scheme suggest the MapToGroup method, also known as hash-and-check. The proposed hash-and-check algorithm works as follows.

‍

1. Compute the hash of the message, i.e. x’ = Hash(b ‖ message), where Hash : {0, 1}* → ℤₚ. We set b = 0 initially.
   ‍
2. Check whether there is a point P = (x, y) on the curve E’(𝔽ₚ²), where x = x’. (One can do this by evaluating the curve equation on x)
   a. If there is,
   (1) perform cofactor clearing, i.e., Pₘ = c₂ ⋅ P.
   (2) If Pₘ ≠ 𝒪 (point at infinity), return Pₘ ∈ 𝔾₂. Otherwise, set b = b + 1 and go to step 1.
   b. Else, set b = b + 1, and go to step 1.

‍

For each b, the probability that Hash(b ‖ message) outputs a valid x-coordinate of a point in 𝔾₂ is roughly 1/2. Hence this is not a constant-time method. Note that the exact probability depends on the choice of the function Hash. Because of this probability, even if it is very unlikely, we may encounter messages that may require a long time to be hashed.

‍

EF has chosen another constant-time approach to hash the inputs to elliptic curve groups to eliminate this possibility. The approach was proposed by Wahby and Boneh in [WB19], along with several constructions of hash functions on the BLS12–381 curve.

‍

The approach chosen by EF goes as follows.

‍

1. Map the message to ℤₚ.
   ‍
2. Apply the Brier et al.’s simplified SWU (Shallue–van de Woestijne–Ulas) map to the result of the hash and obtain a point Q ∈ W, where W is isogenous to our target curve E’(𝔽ₚ²).
   ‍
3. Apply the 3-isogeny map described in [WB19] to the point Q ∈ W, and obtain a point P ∈ E’(𝔽ₚ²).
   ‍
4. Finally, multiply this point P with the cofactor c₂ and get the point Pₘ = c₂ ⋅ P ∈ 𝔾₂.
   ‍

💡 In some cases, there are faster cofactor-clearing methods than scalar multiplication. These methods are equivalent to multiplication by some scalar hₑ whose value is determined by the method and the curve. (For more information, see the Hashing to Elliptic Curves draft by IETF.)

‍

We skipped the technical definitions here. Check [WB19] for further details on the simplified SWU map, isogenies, and benchmarks for the different types of operations. Also, we refer to Ben Edgington’s post, BLS12–381 For The Rest Of Us, for a comprehensive summary of EF’s choice of BLS12–381.

‍

‍

‍

Aggregation

‍

A massive number of signatures could be a bottleneck of computation as the number of validators and messages grows. Fortunately, BLS signatures allow aggregating multiple signatures into a single signature, reducing the number of signatures that need to be verified. The aggregation property of BLS signatures makes the process more scalable as it reduces the computational overhead, allowing more validators and messages to be processed efficiently.

‍

We can aggregate different signatures by simply summing them up, i.e., performing elliptic curve point addition. However, the efficiency of verifying an aggregated signature differs according to the message and the signer. If the messages or the signers are the same, the aggregated signatures can be verified efficiently. We will analyze this in the following cases:

‍

Case 1. n signers, n messages:
Signers Pᵢ sign the messages Mᵢ and obtain σᵢ for i = 1, …, n. We can aggregate these signatures as σ = ∑ᵢ σᵢ (for i = 1, …, n). The verification is performed by checking the below equation.

‍

💡 Note that the bilinearity property of the pairing function implies that for all X ∈ 𝔾₁ (resp. 𝔾₂) and Y, Z ∈ 𝔾₂ (resp. 𝔾₁) the followings hold:
1. e(X, Y + Z) = e(X, Y) ⋅ e(X, Z)
2. resp. e(Y + Z, X) = e(Y, X) ⋅ e(Z, X).

‍

Case 2. The same signer, n messages:
Signer P signs the messages Mᵢ and obtains σᵢ for i = 1, …, n. We can aggregate these signatures as σ = ∑ᵢ σᵢ (for i = 1, …, n). The verification is the same as in Case 1. However, since we have one signer, using the bilinearity property of the pairing function (see the definition above), we can further aggregate the pairings on the LHS of Equation (1), and the verification equation of Case 2 becomes

‍

Case 3. n signers, the same message:
Signers Pᵢ sign the message M and obtain σᵢ for i = 1, …, n. We can aggregate these signatures as σ = ∑ᵢ σᵢ (for i = 1, …, n). With a similar discussion in Case 2, the pairings on the LHS of Equation (1) can also be aggregated. The verification in Case 3 is performed by checking

‍

💡 Verifying n signatures requires 2n pairings without aggregation. However, in Case 1, where both messages and the signers are distinct, verification requires n + 1 pairing computations. Furthermore, in Cases 2 and 3, where the signers or the messages are the same, verification requires only two pairings.

‍

Note that among these cases, Case 3 is of particular interest because it is useful in block attestation. If the proof of custody idea gets implemented, Case 1 will also help to aggregate multiple signatures on multiple messages.

‍

Although the aggregation and verification can be done very efficiently, one shouldn’t directly aggregate the signatures on the same message by different signers because of the so-called rogue key attack.

‍

‍

Rogue key attack

‍

There is a well-known attack in the literature against signatures on the same message, like multi-signatures or aggregate signatures [BGLS03]. This attack strategy relies on an adversary who chooses its public key after seeing other users’ public keys.

‍

Assume that Alice and Bob have their secret and public keys (skₐ, pkₐ) and (skᵦ,pkᵦ), respectively. Suppose that Oscar wants to forge a signature that seems to be signed by Oscar, Alice, and Bob without the participation of Alice and Bob.

‍

• Oscar chooses a random κ ∈ ℤᵣ and registers pkₒ = κ ⋅ g₁ - pkₐ - pkᵦ as his public key, (this implies that κ = skₒ + skₐ + skᵦ)
• Oscar signs with κ and gets σ = κ ⋅ h, a valid signature of Oscar, Alice, and Bob, even though Alice and Bob didn’t sign.
• One can verify that e(pkₒ + pkₐ + pkᵦ, h) = e(g₁, σ), because

‍

Known defenses. There are some well-known measures to avoid rogue-key attacks, i.e.,

• making the messages distinct by adding some user-specific information (e.g., the public key of the user),
• using Proof of Possession (PoP) of the secret key (e.g., a signature on the user’s public key),
• using the key aggregation technique in [BDN18].
  ‍

All of the defenses above have some downsides, e.g., making the messages distinct kills the batch verification possibility (see Case 1 above), and using the key aggregation technique in [BDN18] or using PoP brings additional computational costs.

‍

Ethereum Foundation (EF) chose to use one-time PoP during the registrations. Although the cost of PoP is much higher than the key aggregation technique proposed in [BDN18], EF decided to use it because the frequency of performing PoP is much lower than the frequency of performing key aggregation. In PoPs, each user’s registration (one-time operation) requires two pairings to be computed. On the other hand, in the case of using key aggregation, one scalar multiplication and one hash computation per user are required for each signature aggregation. For further discussion on that choice, we refer to the thread on Justin Drake’s post Pragmatic signature aggregation with BLS.

‍

Using PoP avoids rogue-key attacks, but there also exists another attack against which PoP does not work. Nguyen Thoi Minh Quan developed the splitting zero attack against the proof-of-possession aggregate signature scheme standardized in BLS RFC draft v4. We describe the attack with examples in the next section.

‍

‍

Splitting zero attack

‍

Assuming that Oscar has chosen a secret key skₒ = 0, and computed his public key pkₒ = skₒ ⋅ g₁ = 0 ⋅ g₁ = 𝒪, where 𝒪 is the point at infinity. Oscar computes his signature σₒ on a message Mₒ, i.e., σₒ = skₒ ⋅ hₒ = 0 ⋅ h = 𝒪 where hₒ is the hash of the message Mₒ. Then we have

‍

It is easily seen from (4) that the signature σₒ is also valid for all messages M, because

where h is the hash of the message M.

‍

There is a simple way to avoid this attack: to check whether the public keys are 𝒪 during registration. This simple check guarantees that the users’ secret keys are not equal to 0. However, this doesn’t work in the aggregation case.

‍

What about if two malicious users, say, Oscar and Eve, collude? Assume that they have chosen the secret keys skₒ and skₑ, respectively, such that skₒ + skₑ = 0. Since their public keys pkₒ, pkₑ ≠ 𝒪, they can pass the checks during registration.

‍

Now assume an aggregation case in which Oscar, Eve, and honest Alice participate.

‍

• Alice signs on a message Mₐ and obtains the signature σₐ.
• Oscar and Eve sign on a message M’ and obtain the signatures σₒ and σₑ, respectively.
• The aggregation of the signatures results in σ = σₐ + σₒ + σₑ.
• Verification is performed by checking

‍

where hₐ, h’ are the hashes of the messages Mₐ and M’, respectively.

‍

• Since the messages are the same, using the bilinearity property, we can aggregate the last two pairings on the RHS of (6), and we get

‍

Since Oscar and Eve have chosen their secret keys such that skₒ + skₑ = 0, the last pairing of (7) will always equal 1. Therefore if Alice’s individual signature σₐ is a valid signature on the message Mₐ, then the aggregate signature σ will be valid for all messages M’ because

‍

In other words, the malicious users (Oscar and Eve) -even without signing- can convince any verifier that the signature σₐ is an aggregate signature on the messages Mₐ, M’, M’, for any M’, by Alice, Oscar and Eve, respectively.

‍

Note that we assumed the collusion of two malicious parties, i.e., Oscar and Eve, for simplicity. However, it can easily be generalized to n malicious parties for any n>1.

‍

Avoiding this attack with a non-zero secret key check during registration is impossible. The problem is that a linear combination of distinct public keys is equal to 𝒪. Therefore, we need to check whether all possible linear combinations of the public keys are equal to 𝒪, which is infeasible if the number of users is large.

‍

We refer to the original paper for further details of the splitting zero attack.

‍

‍

‍

Withdrawals (Shanghai/Capella fork)

‍

‍

The sets of BLS keys of the validators

‍

The validators must create two BLS key sets (public and private keys): a validator set and a withdrawal set. For the validator to submit its deposit and let the Ethereum ecosystem know data that will enable the other validators to verify its signatures, it sends a transaction to the Deposit Contract. In this transaction, the validator includes, among others:

‍

• The validator public key that will be used as an identifier of the validator
  ‍
• A hashed version of the validator’s withdrawal public key that constitutes its withdrawal credentials.

‍

Other validators will use the validator’s public key and the withdrawal credential to verify the signatures produced by this validator during its participation in the Ethereum ecosystem.

The validator will use the private keys of the validator set for signing block proposals, attestations, and aggregations. This key will also be used to sign the message needed to exit the active set of validators. This signed message is called SignedVoluntaryExit.

‍

This key is a hot BLS key, meaning that the validators will need to use it frequently to participate in the consensus layer of Ethereum.

‍

The withdrawal private key is used by the validator when it wants to remove its deposit and its rewards after it has exited the active set of validators.

‍

‍

Types of withdrawals in the Shanghai/Capella fork

‍

The upcoming hard forks will allow validators to perform two withdrawal actions: partial and full withdrawals.

‍

A partial withdrawal will be performed automatically, in a regular period, for the validators whose withdrawal credentials’ prefix is 0x01 and whose balance is above 32 ETH (due to their rewards). The exceeding amount of ETH will be transferred to the Ethereum account they have declared in the transaction they submitted to the Deposit Contract (in the field -eth1_withdrawal_address), or in the message they sent to change their withdrawal credentials’ prefix (SignedBLSToExecutionChange) (see details below).

‍

Note that some validators have credentials’ prefix 0x00. Those validators can change their withdrawal credentials’ prefix to 0x01 by signing a message called BLSToExecutionChange that includes their BLS validator public key, which is signed using their BLS private key.

‍

A validator will perform a full withdrawal when it wants to exit the active set of validators and remove all its funds and rewards. Contrary to partial withdrawals, full withdrawals need to be initiated by the validator.