AleoBFT: Explore Aleo's consensus layer

In every decentralized system or blockchain, a consensus mechanism is essential for it to function properly and trustlessly. Aleo employs AleoBFT (Aleo Byzantine Fault Tolerance), a DAG-based (Directed Acyclic Graph) consensus algorithm largely inspired by Bullshark and Narwhal, with extensions for dynamic committees and staking. Additionally, AleoBFT is formally verified with a proof that demonstrates blockchains from different validators never fork, ensuring correctness in the system design. Read more about the formal verification in the blog here.

In this article, you'll learn how AleoBFT enables Aleo Network to achieve high transaction throughput and robust security through its innovative consensus mechanism, combining Narwhal's efficient data dissemination with Bullshark's streamlined ordering process. You'll understand how this architecture helps Aleo scale while maintaining decentralization and preventing blockchain forks, making it a powerful foundation for privacy-preserving blockchain applications.

Understanding Narwhal

Narwhal is a DAG-based mempool abstraction protocol that can work with any consensus mechanism. AleoBFT is built on the composition of Narwhal and a partially synchronous version of Bullshark. Narwhal facilitates the communication of transactions (a type of transmission on Aleo) between nodes, collects certificates, and builds the DAG with high throughput. A DAG is formed with certificates as the vertices of the graph, while the edges are represented by links connecting a certificate to a certain number of certificates from the previous round. Each certificate can have at most one author per round.

The figure below shows a visualization of how a DAG would look:

However, Narwhal can only provide a causal order - so this is where Bullshark steps in. By simply observing and interpreting the DAG built by Narwhal, Bullshark can sequence a single, definitive order with zero message overhead (i.e., no additional message exchanges are required). The commits of this total order form the finalized 'blockchain' of the network.

Narwhal works by offloading data dissemination from consensus, leaving consensus with only small, fixed-size references to sequence the transactions, thereby significantly increasing performance.

Image source - https://www.youtube.com/watch?v=NGOXVSFzYdI&t=2072s

How Narwhal works

Each validator runs multiple worker instances and a single primary. The workers continuously share batches of transactions with other validators in the background and create a digest for the primary. This digest also represents a certificate of availability for the underlying data (transactions). The consensus only needs to order block digest certificates, which are much smaller compared to the originally bulky transaction data.

The integrity of transaction data and the availability of block data are ensured by verifying the digest across other validators. Instead of including transactions directly in blocks, the primary includes all the cryptographic hashes of its own worker batches in the next block. This results in smaller primary blocks.

The DAG building process (and beyond)

The DAG is built in multiple rounds. To begin each round, n-f certificates from the previous round must be collected from distinct validators. Here, n represents the total number of validators and f represents the number of Byzantine or faulty validators, and n-f ensures that the network only accepts values agreed upon by more than two-thirds of all validator nodes.

During the round, each validator sends a proposal to other validators. The other validators endorse the proposal by signing it and returning it to the sender as an endorsement. Once n-f endorsements have been collected for a block, a quorum is reached. The validator then combines these endorsements into a certificate of block availability and broadcasts this certificate to all other validators, allowing them to include it in their next round. The validators can only move to the next round after they have stored a certain number of certificates. The validators can also advance their current round under other conditions such as if the timer has expired and the round already has as many certificates as the quorum number to adapt to network delays that affect certificate delivery.

Image source - https://www.youtube.com/watch?v=NGOXVSFzYdI&t=2133s

Now that the DAG has been built, Bullshark helps order (or interpret) the blocks without any need for extra communication between validators and the history can be committed and finalized.

Thanks to the way Narwhal constructs the DAG, it benefits from properties such as non-equivocation. This means that if two honest parties have a certificate in a round created by the same party, then the certificates are identical (i.e., the transaction data and edges are exactly the same). The requirements on signatures and edges ensure that there is enough consistency across the DAGs of different validators.

This significantly simplifies the ordering logic, eliminating the need for a view-change mechanism in cases of leader failure or inefficiency. The DAG encodes all necessary information, allowing each node to rely solely on its local view to interpret the total order. A new block can potentially be created for each even round, although it may sometimes be skipped, as explained below.

Every even round, a leader is selected through deterministic computation, a process known to all validators. If a certificate is authored by the leader, it is designated as an anchor. If the anchor has a sufficient number of incoming edges (votes) from certificates in subsequent odd rounds, it becomes committed. The commit rule is straightforward: an anchor must receive at least 1+f votes to be committed.

Due to the asynchronous nature of the network, the local view of the DAG may differ between parties. For example, Anchor A1 might be added by some parties even if Party 1 has not yet recognized it. However, since the commit rule requires at least 1+f votes and each certificate includes at least n-f edges to the previous certificate, it is guaranteed that if one party commits to Anchor A1, all anchors in higher rounds will have a path to A1, as illustrated with A3.

This also implies that if no path exists to an anchor in future rounds, that anchor will not be committed, making it safe to skip. This behavior can be observed in the case of Anchor A2 in the figure.

Advantages over traditional consensus

This protocol not only ensures that all validators commit to the same anchors in the same order but also achieves significantly higher throughput compared to traditional leader-based consensus protocols. In traditional systems, the leader bears most of the workload, often consuming substantial resources, while the resources of other validators remain underutilized as they wait to receive data from the leader.

For more on AleoBFT, check out the developer documentation.