1.4 Consensus - AleoBFT
In decentralized ledgers, the consensus mechanism is the fundamental component that enforces trustless verifiable operations. The Aleo network employs the Aleo Byzantine Fault Tolerance (AleoBFT) algorithm, a consensus mechanism based on a Directed Acyclic Graph (DAG) structure, a directed graph with no directed cycles. AleoBFT takes inspiration from Bullshark and Narwhal, incorporating modifications that enable dynamic committees of validator and staking.
Structure of AleoBFT
AleoBFT achieves high transaction throughput and security by integrating Narwhal’s efficient data dissemination with Bullshark’s streamlined ordering process. This hybrid architecture enables Aleo to scale effectively while preserving decentralization and preventing blockchain forks, making it a suitable foundation for privacy-preserving blockchain applications.
Narwhal: DAG-Based Mempool Abstraction
Narwhal serves as a DAG-based mempool abstraction layer that can function alongside any consensus mechanism. AleoBFT relies on a combination of Narwhal and a partially synchronous implementation of Bullshark. The primary role of Narwhal is to facilitate the transmission of transactions between network nodes while assembling certificates and constructing the DAG.
DAG Construction
A DAG consists of:
Vertices, representing transaction certificates.
Edges, representing references to certificates from the previous round.
Each certificate has a unique author per round, and validators contribute to the construction of the DAG by forming references across rounds. However, Narwhal alone provides only a causal order of events; final sequencing is performed by Bullshark.
Bullshark: Total Order Determination
Bullshark determines a definitive sequence of transactions by interpreting the DAG structure generated by Narwhal. This ordering process occurs with zero additional message overhead, meaning that no extra message exchanges are required between validators. The finalized sequence forms the blockchain ledger for the network.
Operation of Narwhal
Each validator node comprises multiple worker instances and a single primary instance. The workers distribute transaction batches among validators while generating a digest for the primary instance. The digest serves as a certificate of availability for the underlying transaction data. The consensus mechanism operates solely on ordering block digest certificates, which are significantly smaller than raw transaction data, thereby improving efficiency.
DAG Formation Process
The DAG is constructed over multiple rounds. Each round requires (n - f) certificates from the previous round, where:
n is the total number of validators,
f is the maximum number of Byzantine (faulty) validators.
This ensures that the network commits to values agreed upon by at least two-thirds of all validators. The steps involved are:
Validators propose transactions and broadcast them to the network.
Other validators endorse proposals by signing them and returning the endorsements to the sender.
Once a validator receives (n - f) endorsements, it forms a certificate of availability and broadcasts it.
The validators incorporate this certificate in their next round.
Validators transition to the subsequent round upon collecting the required number of certificates.
This mechanism ensures that block propagation remains resilient to network delays and Byzantine faults.
Bullshark: Ordering the DAG
Once the DAG is established, Bullshark determines the total order of transactions without additional communication. The properties of Narwhal guarantee non-equivocation, meaning that:
If two honest validators obtain a certificate for the same round from the same author, the certificates are identical.
The combination of signature verification and graph structure ensures consistency across different validator DAGs.
Leader Selection and Commit Rules
Bullshark employs deterministic leader selection every even-numbered round. If a leader authors a certificate, it is designated as an anchor. The commit rule is as follows:
If an anchor receives at least (1 + f) incoming edges (votes) from odd-round certificates, it is committed.
If an anchor lacks sufficient votes, it remains uncommitted and may be skipped.
Due to network asynchrony, some validators may recognize an anchor while others do not. However, if an anchor is committed by one validator, all future anchors will have a reference to it, ensuring eventual consistency.
Advantages of AleoBFT over Traditional Consensus
AleoBFT provides several advantages over traditional leader-based consensus protocols:
High Throughput: Traditional consensus mechanisms rely on a single leader, creating a bottleneck. AleoBFT, by contrast, distributes workload across multiple validators.
Reduced Overhead: The use of block digest certificates minimizes the amount of data processed during consensus.
Resilience to Failures: The DAG structure encodes all necessary information, eliminating the need for view-change mechanisms in case of leader failure.
AleoBFT is a formally verified, DAG-based consensus protocol that ensures high security, decentralization, and scalability. By integrating Narwhal and Bullshark, it achieves a balance between efficient data dissemination and optimal transaction sequencing. These properties make AleoBFT a suitable foundation for next-generation blockchain applications, particularly those requiring privacy-preserving computation.
Last updated