Audit of Matter Labs' Era Consensus
April 22, 2024

Description. The signature scheme used, BLS signatures, is well-known to be vulnerable to "rogue key attacks" if not used correctly. A rogue key attack allows a malicious actor to forge an aggregated signature that looks like other (victim) signers were involved when they were not.

The first line of defense against such attacks is to ensure that each participant truly knows their keypairs. As discussed in "The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks", not any "public key validation" scheme is secure, and either a knowledge of the secret key (KOSK) or a Proof of Possession (PoP) scheme (with a separate hash function) must be used.

Currently, it is not clear if the public keys of the validators are vetted in some way that would prevent such rogue key attacks. As such, it is possible that two malicious replicas could collude to forge arbitrary quorum certificates in the consensus protocol. The reason for the collusion is that one malicious replica would need to create a malicious keypair that would not allow them to sign on their own (and thus one of the malicious replicas would not be able to participate directly in the consensus protocol).

To understand the attack, let's spend some time understanding how BLS works.

BLS works by checking that a signature $S$ is equal to $r \cdot x$, where $r$ is an "unknown and hidden value" derived from the message and $x$ is the private key of the signer.

The check works because of the combination of:

• $r$ being unknown and hidden: given a message and a base point $P$ anybody can compute $Q = r \cdot P$, but not $r$ itself
• only the signer can produce $(r \cdot x) \cdot P$: they can do so by scaling $Q$ with their secret key

Anyone can then verify the equality without knowing the values themselves by using a pairing over public values (the hidden value $Q = [r]$, the public key $X = [x]$, and the signature $S$):

An aggregated signature over the same message is simply the addition of multiple signatures $\sum_i S_i$, which can be checked with a similarly aggregated public key $\sum_i X_i = \sum_i [x_i]$. This follows from the generalization of the previous pairing equation:

The attack works by creating a keypair $(\tilde{x}, \tilde{X})$ such that its public key cancels a set $S$ of "victim" public keys involved in the aggregated signature:

and to simply sign as if we were alone:

so that the pairing check passes:

In addition, the library does not enforce nor warn its potential users of the necessity of such proofs of possessions.

Recommendation. Document the requirements on the user of the library to use an anti-rogue attack measure, and implement the IETF's BLS standard (section 3.3) proposed solution.

Consider using a type-state pattern (as in Enforce Validity of Data Statically) to statically enforce the validity of the public keys.

Description. The protocol, as implemented currently, does not allow to easily reconfigure the set of validators. The set of validators is hardcoded in the genesis and cannot be changed without a manual intervention:

/// Genesis of the blockchain, unique for each blockchain instance.
pub struct Genesis {
     /// Genesis encoding version
    pub version: GenesisVersion,
    /// Set of validators of the chain.
    pub validators: Committee,
    /// Fork of the chain to follow.
    pub fork: Fork,
}

This can become problematic if validators' keys get compromised, or lost, or worse if validators turn malicious and need to be removed from the validator set.

Recommendation. We recommend addressing this issue either in documenting manual reconfiguration processes to streamline such interventions, or in researching augmentation to the current protocol to support reconfigurations (while preserving the safety of the protocol).

Description. The consensus protocol must force a leader to repropose in case a commit might have happened in the previous view, even if the commit is not clearly visible. As we explained in the overview, replicas do that by ignoring proposals that do not repropose when a subquorum of $2f+1$ "high votes" is present in the leader's certificate AND is different from the highest observed commit.

There are two problems with the way the current check is done. First, a certificate can hold as many votes as the leader wants them to carry, as long as it has more than $4f+1$. So the leader could include $5f+1$ votes, for example, which would lead to two subquorum potentially being present in the certificate.

In addition, the current implementation supports a "weighted" BFT variant which counts the number of votes based on the weight of each signer (who can potentially weigh for more than 1 vote). In this case, an exact quorum of $4f+1$ votes might be impossible to achieve.

Thus, the problem remains that it is possible to have two subquorums of $2f+1$ high votes. When faced with such a situation, replicas currently pick non-deterministically (due to the non-determinism of Rust's HashMap):

pub fn high_vote(&self, genesis: &Genesis) -> Option<BlockHeader> {
    let mut count: HashMap<_, u64> = HashMap::new();
    for (msg, signers) in &self.map {
        if let Some(v) = &msg.high_vote {
            *count.entry(v.proposal).or_default() += genesis.validators.weight(signers);
        }
    }
    // We only take one value from the iterator because there can only be at most one block with a quorum of 2f+1 votes.
    let min = 2 * genesis.validators.max_faulty_weight() + 1;
    count.into_iter().find(|x| x.1 >= min).map(|x| x.0)
}

But the logic of the replica would later dismiss the proposal altogether if its block number doesn't match the expected one (which should be one more than the latest commit):

/// Verifies LeaderPrepare.
pub fn verify(&self, genesis: &Genesis) -> Result<(), LeaderPrepareVerifyError> {
    // TRUNCATED...

    // Check that the proposal is valid.
    match &self.proposal_payload {
        // The leader proposed a new block.
        Some(payload) => {
            // TRUNCATED...
        }
        None => {
            let Some(high_vote) = &high_vote else {
                return Err(Error::ReproposalWithoutQuorum);
            };
            if let Some(high_qc) = &high_qc {
                if high_vote.number == high_qc.header().number {
                    return Err(Error::ReproposalWhenFinalized);
                }
            }
            if high_vote != &self.proposal {
                return Err(Error::ReproposalBadBlock);
            }
        }
    }
    Ok(())
}

Thus this issue might lead to replicas refusing to proceed on a valid leader proposal, affecting the liveness of the protocol.

Note that if the previous proposal was committed, the problem doesn't occur as this means that $3f+1$ honest replicas have voted for it and there aren't enough honest and dishonest replicas left to create a subquorum of $2f+1$ high votes for a previous proposal.

Recommendation. Change the logic to return as "high vote" the proposal that has amassed at least $2f+1$ votes AND that has the highest block number. If there are still more than one such proposal, then deterministically choose which one to pick (for example, based on its hash) or return no high vote (which will allow a reproposal). This should address the two example scenarios depicted in the following diagram:

Description. Cryptographically-Secure Pseudo-Random Number Generators (CSPRNGs) are used to obtain random numbers throughout the protocols. Such CSPRNGs are expected to provide unpredictable numbers. While this assumption is currently correct, the internal libraries implement patterns that could lead a code change to violate the assumption.

To see why, let's look at how a context's rng is constructed when we call ctx.rng():

// -- libs/concurrency/src/ctx/mod.rs --
impl Ctx {
    pub fn rng(&self) -> rand::rngs::StdRng {
        self.0.rng_provider.rng()
    }
}

// -- libs/concurrency/src/ctx/rng.rs --
impl Provider {
    pub(super) fn rng(&self) -> StdRng {
        StdRng::from_seed(match self {
            // StdRng seeded with OS entropy is what rand::thread_rng() does,
            // except that it caches the rng in thread-local memory and reseeds it
            // periodically. Here we push the responsibility of reseeding
            // (i.e. dropping the rng and creating another one) on the user.
            Self::OsRng => OsRng.gen(),
            Self::Split(split) => split.next_builder().finalize().into(),
        })
    }
}

As you can see, the output of OsRng is used not directly (which would be secure) but to seed a software CSPRNG. This pattern is dangerous as the seeded RNG is implemented as Clonable, which could lead to multiple instantiation producing the same RNG. For example:

#[test]
fn test_rng() {
    abort_on_panic();
    let ctx = &ctx::root();
    let rng = &mut ctx.rng();

    fn sample(mut rng: impl rand::RngCore) {
        println!("Random number: {}", rng.next_u32());
    }

    sample(rng.clone());
    sample(rng);
}

Recommendation. We recommend to only use OsRng and to avoid seeding software RNGs, unless when testing.

Description. The Noise protocol framework is used to encrypt and authenticate communications between consensus participants of the consensus protocol. When someone attempts to connect to a node, they first perform an Noise NN handshake with them. A Noise NN handshake is an unauthenticated connection, sometimes called "opportunistic", that can be man-in-the-middle'd during the first few messages. It is opportunistic as the connection will be secure if an attacker is not present during this narrow window of time. That being said, it is often not deemed enough as man-in-the-middle attackers can easily force peers to restart their connection.

To strongly authenticate both sides of the encrypted channel, an additional "handshake" protocol is implemented on top of a connection secured by the Noise protocol. The handshake consists of the two peers sending each other a Handshake object,, which contains the genesis configuration used (to ensure that the peers are not part of a different chain) and a signature over the session ID (which is designed to be unique for every new connection).

The inbound function is written to follow this handshake protocol when a validator attempts to connect to our own validator:

pub(super) async fn inbound(
    ctx: &ctx::Ctx,
    me: &validator::SecretKey,
    genesis: validator::GenesisHash,
    stream: &mut noise::Stream,
) -> Result<validator::PublicKey, Error> {
    let ctx = &ctx.with_timeout(TIMEOUT);
    let session_id = node::SessionId(stream.id().encode());
    let h: Handshake = frame::recv_proto(ctx, stream, MAX_FRAME)
        .await
        .map_err(Error::Stream)?;
    if h.genesis != genesis {
        return Err(Error::GenesisMismatch);
    }
    if h.session_id.msg != session_id.clone() {
        return Err(Error::SessionIdMismatch);
    }
    h.session_id.verify()?;
    frame::send_proto(
        ctx,
        stream,
        &Handshake {
            session_id: me.sign_msg(session_id.clone()),
            genesis,
        },
    )
    .await
    .map_err(Error::Stream)?;
    Ok(h.session_id.key)
}

Interestingly, the public key of the node is only returned at the end and checked on the caller side (who will dismiss the connection if it is not from a validator).

As such, a non-consensus participant can connect to a node, establish an encrypted channel via the Noise protocol, and then force them into further potentially-expensive operations (verify a signature, sign a handshake message, send the handshake message) with their own signature even if they are not part of the validators.

Recommendation. Check that the public key (h.session_id.key) is part of the validator set as soon as it is received. It is easy to do that in the current function as the genesis configuration is available in the scope.

Furthermore, consider using different Noise handshake patterns that force the peers authentication during the handshake itself, and would allow a receiving peer to discard the connection attempt as early as it can.

Ideally, one should try to use a Noise handshake pattern that provides mutual authentication, such as the Noise IK pattern. This would ensure both parties are authenticated before any further operations are performed. That being said such handshake patterns come with their own downsides, like replayability of the messages or lack of key confirmation, and should be carefully considered before being implemented (see how similar protocols handled these downsides).

Description. The consensus protocol uses the BLS signature scheme to benefit from its signature aggregation feature.

The current implementation follows the BLS Signatures RFC which is a well-accepted Internet Draft in the community.

The implementation does not follow the standard in a few places. For example, the key generation is simply done using rejection sampling, which seems much more simple, and the hash-to-curve algorithm used is the try-and-increment algorithm which is not part of RFC 9380: Hashing to Elliptic Curves.

While both examples are secure divergences of the standard, the latter might lead to non-interoperability with other libraries, which could force people to implement their own BLS implementation, which could in turn lead to security issues.

Recommendation. Choose one of the "ciphersuite" from the BLS Signatures RFC in order to implement one of the standardized variants of BLS.

Description. In a number of places, validation of data can be enforced statistically to avoid programming mistakes that could lead to bugs.

For example, at the moment signed messages can be used without verifying their attached signature (through the verify function). This is due to the object giving free access to its fields:

pub struct Signed<V: Variant<Msg>> {
    /// The message that was signed.
    pub msg: V,
    /// The public key of the signer.
    pub key: validator::PublicKey,
    /// The signature.
    pub sig: validator::Signature,
}

impl<V: Variant<Msg> + Clone> Signed<V> {
    /// Verify the signature on the message.
    pub fn verify(&self) -> anyhow::Result<()> {
        self.sig.verify_msg(&self.msg.clone().insert(), &self.key)
    }
}

The validation is thus done in different places, manually. As part of the audit we confirmed that every signed message was validated when used. That being said, it can be difficult to track where a signature is being checked, and future refactors and code changes have the potential to introduce bugs.

The above example could be refactored to prevent access to a message before verification:

pub struct Signed<V: Variant<Msg>> {
    /// The message that was signed.
    msg: V,
    /// The public key of the signer.
    pub key: validator::PublicKey,
    /// The signature.
    pub sig: validator::Signature,
}

impl<V: Variant<Msg> + Clone> Signed<V> {
    /// Verify the signature on the message.
    pub fn verify(self) -> anyhow::Result<V> {
        self.sig.verify_msg(&self.msg.clone().insert(), &self.key)?;
        Ok(self.msg)        
    }
}

Another example is for public keys in BLS, which need to be validated to prevent rogue key attacks (as mentioned in finding Lack of Proof of Possession for BLS Signatures).

To statically enforce that public keys can't be used without having been validated, we recommend a type state pattern, as described in The Typestate Pattern in Rust , to keep track of objects in their unvalidated and validated forms, and enforce validation before usage of the object:

pub struct PublicKey<const VERIFIED: bool>(u8);

impl PublicKey<false> {
    fn from_byte(byte: u8) -> Self {
        Self(byte)
    }
    
    fn verify(self) -> PublicKey<true> {
        // TRUNCATED verification logic...

        PublicKey(self.0)
    }
}

impl PublicKey<true> {
    fn do_stuff(&self) {
        println!("doing stuff!");
    }
}

fn main() {
    let pubkey = PublicKey::from_byte(5);
    let pubkey = pubkey.verify();
    pubkey.do_stuff();
}

Description. Anyone on the network can block the connection between validators, effectively performing a Denial of Service (DoS) attack on the network.

Alternatively, they can spam the storage of validators to achieve similar results.

To do this to validator $V$, first find all views $i$ such that $V$ is a leader. There's almost an infinite number of them, as you just need to solve $V_{idx} = i \mod N$ where $N$ is the number of validators.

Then, create a message ReplicaCommit { view, proposal } with a garbage proposal, potentially sign it if you are a validator (otherwise choose a random validator $V'$ and a garbage signature), and send it to $V$.

$V$ will call process_replica_commit which will do a number of checks that will pass, and then store the garbage proposal:

impl StateMachine {
    #[instrument(level = "trace", skip(self), ret)]
    pub(crate) fn process_replica_commit(
        &mut self,
        ctx: &ctx::Ctx,
        signed_message: validator::Signed<validator::ReplicaCommit>,
    ) -> Result<(), Error> {
        // TRUNCATED number of checks that will pass...

        // Get current incrementally-constructed QC to work on it
        let commit_qc = self
            .commit_qcs
            .entry(message.view.number)
            .or_default()
            .entry(message.clone())
            .or_insert_with(|| CommitQC::new(message.clone(), self.config.genesis()));
        
        // If we already have a message from the same validator and for the same view, we discard it.
        let validator_view = self.validator_views.get(author);
        if validator_view.is_some_and(|view_number| *view_number >= message.view.number) {
            return Err(Error::DuplicateSignature {
                message: commit_qc.message.clone(),
            });
        }
        self.validator_views
            .insert(author.clone(), message.view.number);

        // TRUNCATED...

        // Check the signature on the message.
        signed_message.verify().map_err(Error::InvalidSignature)?;

        // TRUNCATED...
    }

Due to the signature being checked after the storage update, the attack can be performed by non-validators as well.

To spam the validator's storage, either we choose a new view number as discussed above to create a new entry, or we create a new message with a new garbage proposal which will create a new subentry.

In addition, such messages in the future will also block the author $V'$ from sending valid ReplicaCommit messages to this validator, as one of the checks above will prevent any messages from previous views to be processed.

Note that after this finding was reported, Matter Labs informed us that they were already aware of it and even had a PR (#100) fixing it. As such, this finding is marked as a "known issue".

Recommendation. Move the signature check before all storage updates.