What Are BLS Signatures and How Do They Work?

Boneh-Lynn-Shacham (BLS) multi-signatures are a powerful cryptographic tool that enable multiple participants to jointly produce a single, compact signature. These signatures are particularly valuable in consensus mechanisms, such as Ethereum, where they help reduce signature size and enhance efficiency.

In this blog post, we delve into the implementation of BLS multi-signatures within EigenLayer’s Actively Validated Services (AVS) contracts. EigenLayer represents an important protocol in the blockchain ecosystem, extending Ethereum’s functionality through restaking. By using EigenLayer AVS as an example, we move beyond theoretical cryptographic constructions to demonstrating how BLS multi-signatures have been used to solve real-world challenges. We highlight in this post some key technical details that are often overlooked or not documented. We also present an important pitfall to avoid when using BLS multi-signatures, how EigenLayer solves this challenge, and an alternative approach that may be explored in the future.

Understanding EigenLayer’s AVS

EigenLayer is a protocol built on Ethereum that enables restaking, a process where Ethereum stakers can reuse or restake their staked ETH to secure additional services beyond the Ethereum blockchain itself. Those additional services are called in EigenLayer, Actively Validated Services (AVSs). Ethereum stakers can delegate some of their staked tokens to the operators that will be in charge to validate some tasks given by the AVSs. Some AVSs are already running different services, and a list of deployed AVSs is available here↗.

EigenLayer created a repository called the Incredible Squaring AVS↗, implementing a toy example of AVSs to show how it works in practice. In this simple example, a task is simply a number and the set of operators are in charge of computing and signing the square of the number. Here is an image from this repository showing how it works:

The task generator is in charge of submitting tasks to the AVS contracts. In this example, the task is composed of a number, the block number when the task was created, and a threshold indicating the percentage of operator validation, which is necessary to validate the task. The AVS contracts are developed by EigenLayer and are available here↗. However, it is up to each AVS to use those contracts or not according to their own needs.

Then the operators that opted in to the AVS are able to get those tasks, to compute the task answer — in the previous example, the square of the number — and to send the answer with their BLS signature of the task to the aggregator.

As soon as the threshold of identical answers is reached, the aggregator merges all the BLS signatures into a unique aggregate signature and sends it back to the AVS contract. The contract verifies that the signature is correct and opens a challenging period when a challenger can give proof that the validation was incorrect, and if so, the misbehaving operators are slashed.

The following part of the post is about the details of BLS signature aggregation and how it is implemented in the AVS contracts.

Defining Boneh-Lynn-Shacham

We recall briefly how the Boneh-Lynn-Shacham (BLS) signature works. For a more detailed definition, see the reference paper↗. The signature works with two different groups $\mathbb{G}_1, \mathbb{G}_2$ with respective generators $G_1, G_2$.

Then the secret key $sk$ is random number between $1$ and $q$ (the $G_1$ order). The corresponding public key is $pk = sk\cdot G_2 \in \mathbb{G}_2$. To sign a message, we need a hash function $H: \{ 0,1 \}^* \rightarrow \mathbb{G}_1$. This function maps arbitrary messages to elements of the first group. The signature of a message $m$ is given by the following:

$$\sigma = sk \cdot H(m) \in \mathbb{G}_1$$

Given a pairing $e$, to verify that a signature $\sigma$ is correct, the verifier checks the following equality holds:

$$e(H(m), pk) \stackrel{?}{=} e(\sigma, G_2)$$

From the bilinearity of the pairing $e$, if a signature is correct, we have

$$\begin{equation*} \begin{split} e( H(m), pk) & = e(H(m), sk \cdot G_2) \\ & = e(sk \cdot H(m), G_2) \\ & = e(\sigma, G_2) \end{split} \end{equation*}$$

To learn more about pairings and their properties, see our previous blog post↗.

There are few remarks regarding the previous definitions. First, since the pairing verification is symmetric, the signature scheme can be defined the other way around with the signatures in $\mathbb{G}_2$ and the public key in $\mathbb{G}_1$. Most of the time $\mathbb{G}_2$ is defined over the quadratic extension of the field and the storage of $\mathbb{G}_2$ element is larger. In addition, the arithmetic in $\mathbb{G}_2$ is more resource-intensive than in $\mathbb{G}_1$. It may be an advantage depending on the implementation constraints to switch the public key group. If the implementation needs to store all the public keys that signed a message, then it would be more interesting to have them in $\mathbb{G}_1$ to reduce storage. If it is possible to keep only the aggregate public key, but all the signatures must be stored, then the signature should be in $\mathbb{G}_1$ and the public keys in $\mathbb{G}_2$.

Another point is that, since the verification involves a pairing operation that is very complex, the verification is more time-consuming than other elliptic-curve signature verification like Schnorr or EdDSA. However, the BLS signature allows direct signature aggregation, which is not as straightforward for other signature algorithms.

In Solidity contracts, most of the time, the groups used are subgroups of the BN254 curves↗. This allows using the precompiled contracts as defined in EIP-196↗ and EIP-197↗ to save a large amount of gas. Nevertheless, the precompiled contracts impose some constraints since they provide only operations in $\mathbb{G}_1$ and not in $\mathbb{G}_2$. As we will see later, this forced smart contract developers to find some optimizations to avoid computation in $\mathbb{G}_2$.

Another problem for long-term security is that the BN254 curve was found to have a security level around 100 bits↗ instead of 128, as believed previously. For this reason, some projects like Zcash↗ moved to another curve called BLS12-381 with a higher security level. Don’t be confused with the name “BLS”; here, this curve is a member of the Barreto-Lynn-Scott curves↗. The Ethereum Pectra upgrade↗ now also includes precompiled contracts for the BLS12-381 curve with EIP-2537↗. The main improvement regarding BLS signatures is that operations in $\mathbb{G}_2$ for this curve are included.

Building Aggregation and Multi-signatures

The concept of signature aggregation is when $n$ participants have issued $n$ signatures of $n$ different messages, and they build an aggregate signature $\sigma_{\mathrm{agg}}$. When valid, this aggregate signature convinces a verifier that all the participants signed their message.

For BLS signatures, there is a natural way to build aggregate signatures. Suppose we have $n$ signatures $\sigma_0, \dots,\sigma_{n-1}$ of $n$ messages. Instead of verifying them independently, we can compute an aggregate signature with

$$\sigma_{\mathrm{agg}} = \sum_{i=0}^{n-1} \sigma_i$$

Then the verification algorithm becomes

$$e(\sigma_{\mathrm{agg}}, G_2) \stackrel{?}{=} e(H(m_0), pk_{0}) \cdot ... \cdot e(H(m_{n-1}), pk_{n-1})$$

The aggregate signature is small, a single group element, and it saved $n-1$ pairing evaluations for verification.

The concept of multi-signatures is similar to aggregation, but all the signers sign the same message $m$. For BLS, it further optimizes the verification. If we have $n$ signatures of the same message $m$, the verification becomes

$$e(\sigma_{\mathrm{agg}}, G_2) \stackrel{?}{=} e\left(H(m), \sum_{i=0}^{n-1} pk_{i}\right)$$

We only need two pairing evaluations, whatever the number of signatures. In addition, we can define an aggregate public key

$$apk = \sum_{i=0}^{n-1} pk_i$$

to be reused for each signature verification.

This efficient scheme is used a lot in practice. For example, it is used in Ethereum↗ to aggregate validator votes into a single signature. As mentioned earlier, it is also at the heart of AVS. This reduces the verification time and the signature storage. A good source of information for implementing BLS signature aggregation or multi-signatures is the IETF draft↗, which details the primitive to use and some pitfalls to avoid.

One question could arise at this point: Is it possible to build signature aggregation with Schnorr signatures? The answer is yes. Schnorr signatures are linear; thus, we can also aggregate them. However, since a nonce needs to be generated for each Schnorr signature, multi-signatures need at least two rounds of communication between participants compared to a single round for BLS. It makes the protocol more complex to implement for Schnorr and more error-prone. MuSig2↗ is one of the Schnorr multi-signature protocols used in practice. We have covered more on the topics of Schnorr multi-signatures and threshold signatures in our previous blog post↗ about Bitcoin.

What BLS Signatures Look Like in EigenLayer

As mentioned earlier, EigenLayer also uses BLS aggregation in their AVS implementation. The aggregator receives operators’ BLS signatures of the current task; as soon as it receives enough signatures, it aggregates them into a single signature and sends it to the BLSSignatureChecker contract together with the public keys that have signed the message. To verify the signature, the contract adds all the public keys together and verifies the aggregate signature as described earlier. In the contract, the verification happens in the trySignatureAndApkVerification function:

function trySignatureAndApkVerification(
    bytes32 msgHash,
    BN254.G1Point memory apk,
    BN254.G2Point memory apkG2,
    BN254.G1Point memory sigma
) public view returns(bool pairingSuccessful, bool siganatureIsValid) {
    // gamma = keccak256(abi.encodePacked(msgHash, apk, apkG2, sigma))
    uint256 gamma = uint256(keccak256(abi.encodePacked(msgHash, apk.X, apk.Y, apkG2.X[0], apkG2.X[1], apkG2.Y[0], apkG2.Y[1], sigma.X, sigma.Y))) % BN254.FR_MODULUS;
    // verify the signature
    (pairingSuccessful, siganatureIsValid) = BN254.safePairing(
            sigma.plus(apk.scalar_mul(gamma)),
            BN254.negGeneratorG2(),
            BN254.hashToG1(msgHash).plus(BN254.generatorG1().scalar_mul(gamma)),
            apkG2,
            PAIRING_EQUALITY_CHECK_GAS
        );
}

It is noticeable that the verification differs a bit compared to what we have introduced previously. First, it takes two public keys, $apk$ and $apk_2$, and the pairing check is modified to the following:

$$\begin{equation*} \begin{split} & e(\sigma + \gamma \cdot apk, G_2) \stackrel{?}{=} e(H(m) + \gamma \cdot G_1, apk_2)\\ \Leftrightarrow \quad & e(\sigma, G_2) \cdot e(\gamma \cdot apk, G_2) \stackrel{?}{=} e(H(m), apk_2) \cdot e(\gamma \cdot G_1, apk_2) \\ \end{split} \end{equation*}$$

After rearranging the terms, we can split the check in two:

$$\begin{cases} \begin{equation}e(\sigma, G_2) \stackrel{?}{=} e(H(m), apk_2)\qquad\qquad\:\end{equation} \\ \begin{equation}e(\gamma \cdot apk, G_2) \stackrel{?}{=} e(\gamma \cdot G_1, apk_2)\qquad\end{equation} \end{cases}$$

We recognize in the first check the BLS verification. The second check with the $\gamma$ factor is an optimization described in a previous paper↗. As we have seen, in Solidity, the EIP-196 precompiled contract allows performing operations in $\mathbb{G}_1$, but there is no precompiled contract for $\mathbb{G}_2$ operations. If the aggregator had sent only a list of a signer’s public keys in $\mathbb{G}_2$, then the aggregate public key would have to be computed in $\mathbb{G}_2$, which may be very gas-expensive. Instead, the aggregator sends a list of the signer’s public keys but in $\mathbb{G}_1$ and the aggregate key already $apk_2 \in \mathbb{G}_2$. Finally, the check in (2) is simply to ensure that $apk_2$ matches the value computed from the signer’s keys $apk$. As we have seen previously, with EIP-2537, this trick is not needed anymore if the operations are done on BLS12-381.

The $\gamma$ is the delineation factor. It is computed over all the public values to prevent a malicious aggregator from forging signatures. For example, if $\gamma$ does not include the signature and the public key, then an attacker can choose the following:

$$\begin{cases} \begin{equation*} \sigma = -\gamma \cdot apk \end{equation*} \\ \begin{equation*} apk_2 = \mathcal{O} \end{equation*} \end{cases}$$

With $\mathcal{O}$ being the point at infinity. Then, the signature would verify for any message $m$. In the previous function, $\gamma$ is computed in the contract with

$$\gamma = \mathrm{keccak256}(m, apk, apk_2, \sigma) \mod q$$

preventing the signature forgery since the $\gamma$ depends on all the public parameters. Similarly to the Fiat–Shamir heuristic↗, $\gamma$ must depend on all the verifying arguments to prevent a malicious aggregator from forging a signature.

There is another threat, as mentioned in the EigenLayer documentation:

msgHash is the hash being signed by the apk. Note that the caller is responsible for ensuring msgHash is a hash! If someone can provide arbitrary input, it may be possible to tamper with signature verification.

Indeed, if the hash value $h = H(m)$ can be freely chosen by a malicious operator, by setting the following —

$$\begin{cases} \begin{equation*} \sigma = apk \end{equation*} \\ \begin{equation*} h = G_1 \end{equation*} \end{cases}$$

again, the signature would be accepted for any message $m$. Fortunately, in the previous example, the task message is hashed before being passed to for signature verification:

/* CHECKING SIGNATURES & WHETHER THRESHOLD IS MET OR NOT */
// calculate message which operators signed
bytes32 message = keccak256(abi.encode(taskResponse));

// check the BLS signature
(QuorumStakeTotals memory quorumStakeTotals, bytes32 hashOfNonSigners) =
    checkSignatures(message, quorumNumbers, taskCreatedBlock, nonSignerStakesAndSignature);

Nevertheless, it is the AVS contracts’ responsibility to properly call the verification, and thus it is important to check.

The Pitfall of Multi-signatures

Multi-signatures come with a serious potential pitfall called rogue-key attacks. Let’s illustrate how this kind of attack works.

Let’s suppose an honest user has a public key $pk_0$. Then, an attacker who has previously seen $pk_0$ can choose their public key as $pk_1 = sk_1 \cdot G_1 - pk_0$. The attacker would not know the private key associated to the public key. However, the multi-signature verification would give the following:

$$e(G1, \sigma) \stackrel{?}{=} e(pk_1 + pk_0, H(m)) = e( sk_1 \cdot G_1, H(m))$$

Only $sk_1$ is needed to sign a message resulting in a valid multi-signature, even though the first user may not have signed it. This is easily generalized to any number $r$ of honest users by choosing the rogue key, being

$$pk_r = sk_r \cdot G_1 - \sum_{i=0}^{r-1} pk_i$$

This is a dangerous threat since, in our previous AVS example, a malicious aggregator that would have previously registered a rogue key could send aggregate signatures that were not signed by the validators but still will be accepted by the contract. This would lead to having validators being slashed even if they did not misbehave.

Preventing the Pitfall

Proof of Possession

To prevent a rogue-key attack, a common method is to request users to prove they know the private key matching their public key. Thus, in a first registration step, the user is requested to register their public key together with a proof of possession $\pi$ such that

$$\pi = sk \cdot \tilde{H}(pk)$$

Basically, the user is requested to sign their public key or any other identification message. However, the hash function $\tilde{H}$ used in the proof has to be different from the one used by the aggregated signature verification. In practice, the construction of $\tilde{H}$ is achieved by using domain separation as explained in the IETF draft↗.

Then the aggregator registers public keys by verifying the proof of possession $\pi$ with the BLS verification algorithm using the other hash function $\tilde{H}$.

In the EigenLayer contract, the proof of possession is verified by the registerBLSPublicKey function:

function registerBLSPublicKey(
    address operator,
    PubkeyRegistrationParams calldata params,
    BN254.G1Point calldata pubkeyRegistrationMessageHash
) external onlyRegistryCoordinator returns (bytes32 operatorId) {
    // [...]

    // gamma = h(sigma, P, P', H(m))
    uint256 gamma = uint256(keccak256(abi.encodePacked(
        params.pubkeyRegistrationSignature.X, 
        params.pubkeyRegistrationSignature.Y, 
        params.pubkeyG1.X, 
        params.pubkeyG1.Y, 
        params.pubkeyG2.X, 
        params.pubkeyG2.Y, 
        pubkeyRegistrationMessageHash.X, 
        pubkeyRegistrationMessageHash.Y
    ))) % BN254.FR_MODULUS;
    
    // e(sigma + P * gamma, [-1]_2) = e(H(m) + [1]_1 * gamma, P') 
    require(BN254.pairing(
        params.pubkeyRegistrationSignature.plus(params.pubkeyG1.scalar_mul(gamma)),
        BN254.negGeneratorG2(),
        pubkeyRegistrationMessageHash.plus(BN254.generatorG1().scalar_mul(gamma)),
        params.pubkeyG2
    ), "BLSApkRegistry.registerBLSPublicKey: either the G1 signature is wrong, or G1 and G2 private key do not match");

    operatorToPubkey[operator] = params.pubkeyG1;
    operatorToPubkeyHash[operator] = pubkeyHash;
    pubkeyHashToOperator[pubkeyHash] = operator;

    emit NewPubkeyRegistration(operator, params.pubkeyG1, params.pubkeyG2);
    return pubkeyHash;
}

The same trick as before for public key and signature verification is applied here as well. But as explained before, the hash is computed differently. The function pubkeyRegistrationMessageHash is used:

function pubkeyRegistrationMessageHash(address operator) public view returns (BN254.G1Point memory) {
    return BN254.hashToG1(
        _hashTypedDataV4(
            keccak256(abi.encode(PUBKEY_REGISTRATION_TYPEHASH, operator))
        )
    );
}

The hash function uses a custom domain separator PUBKEY_REGISTRATION_TYPEHASH to build a different hash function, and the message is simply the operator address. After registration, the public key is added to the contract. We can verify its value by calling the getRegisteredPubkey function. Here is an example of a BLS public key registered for EigenDA AVS:

It is important to have a different hash function for this part. Let’s see what would happen if we would use the same hash function $H$ as used in the BLS signature. This is the proof of possession:

$$\pi = sk \cdot H(pk)$$

If the attacker is able to request the aggregate signature $\sigma_{\mathrm{agg}}$ of $pk_{\mathrm{agg}}$, then they are able to register the rogue key

$$pk = sk \cdot G_1 - pk_{\mathrm{agg}}$$

by sending the proof:

$$\pi = sk \cdot H(pk) - \sigma_{\mathrm{agg}}$$

This would then allow the attacker to do a rogue-key attack, as described before. Thus, it is essential to use domain separation.

Proof of possession is basically a BLS signature. However, it is also not advisable to use multi-signatures during the proof-of-possession step, for example to register multiple public keys for a single participant. If so, the participant would achieve a splitting zero attack↗. In this case, the participant could register keys that would cancel out when summed together and could bypass the proof of possession.

Modified Aggregate Public Key

One thing to notice is that the burden of implementing proof of possession for BLS aggregate multi-signatures can be avoided. In 2018, Boneh et al. proposed a modified scheme↗ where BLS signatures can be aggregated without the threat of rogue-key attacks and without proof of possession. So far, we have not seen this solution implemented in EigenLayer AVS nor in other solutions, but it may be a possibility in the future.

To aggregate $n$ signatures, they used a hash function $H_n: \{0,1\}^*\rightarrow Z_q^n$. Then they generate a vector $(t_0,\dots, t_{n-1}) = H_n (pk_0, \dots, pk_{n-1})$. The aggregate public key is modified to be

$$apk = \sum_i t_i \cdot pk_i$$

and the aggregate signature is computed by the following:

$$\sigma = \sum_i t_i \cdot \sigma_i$$

The verification works the same as for previous aggregate signatures, except that the modified aggregate public key is used. Since this scheme is a modified version of BLS, it may not be compatible with existing implementations. However, it could be interesting to use it for new implementations. This would remove the need of key registration and proof of work and simplifies existing schemes.

Conclusion

We have seen that BLS multi-signatures offer a significant optimization opportunity. EigenLayer’s implementation demonstrates the power of BLS signatures and also highlights the complexities involved in their practical deployment. However, as discussed, multi-signatures introduce security risks such as rogue-key attacks, which necessitate safeguards like proof of possession. We also remarked that many optimizations are possible for Solidity contracts.

With the Pectra upgrade supporting BLS12-381, we may see further implementation and improvements in Solidity, and thus we hope this post helps to avoid known implementation bugs and vulnerabilities. Additionally, alternative aggregation schemes, such as the rogue-key–resistant approach, offer promising directions for future developments.