BullShark is a protocol that achieves Byzantine Atomic Broadcast (BAB) in a distributed system using a DAG. It lies in the DAG-Rider paradigm, optimized for the common synchronous case, and entails several main enhancements to ensure practical deployability. The core idea is to use the DAG to order transactions in a distributed Byzantine setting, and it gives a sound solution toward distributed consensus for deploying blockchain technologies. BullShark runs on a peer-to-peer message-passing model, where each message is a vertex in the DAG. The key primitive assumes a computationally bounded adversary who is allowed to corrupt at most a third of the parties. The notion of reliable link between honest parties means that all messages eventually arrive, which is what supports the operation of the protocol both in synchronous and asynchronous periods. The work adopts a GST model to be able to reason about synchronous network conditions.

BullShark Core: DAG Constructions

The protocol has a DAG construction at its core. Each party posts transaction proposals through messages into a DAG. In the DAG, vertices represent messages, and edges represent causal relationships. The parties make a new vertex through combining blocks of transactions and with references to messages which it has previously received. These references are either strong, hence link to vertices in the previous round, or weak, hence link to vertices in rounds which are earlier to ensure their eventual inclusion in the total order. BullShark relies on reliable broadcast mechanisms to give firm guarantees of message integrity, agreement, and validity among parties with the fact that all honest parties will eventually receive the same messages and have a consistent view of the DAG. The protocol further makes use of a global perfect coin for leader election and is charged with leaders who possess fairness and unpredictability in terms of leadership selections for message proposals.

Advancing rounds in BullShark

The protocol is built itself around certain conditions that drive the process of advancement. By feeding a round with enough vertices, specifically 2 f + 1, parties ensure advancement into the next. Advancing is guaranteed even when messages in the middle of the process of reaching another party are delayed. During synchronous periods, BullShark introduces timeouts to bound the round advancement protocol, and this dual approach gives the best of both worlds: very low latency and high throughput yet with liveness guarantee under worst-case asynchronous conditions

When we stop and think about it leader election is indeed a very crucial part of BullShark. Their approach is combining steady-state and fallback leaders, where steady-state leaders commit to being leaders for blocks in specific rounds and predefine fallback leaders in case. Their dual leader approach therefore got two key advantages: i) Lower latency since decisions can make independently of the serial nature of blocks, and ii) the protocol stays live even in the presence of faulty or malicious leaders. To keep a total order of transactions, the protocol treats each of the edges in the DAG as a "vote". The protocol organizes rounds into waves and establishes the predefined leaders for the specific round as proposers. Those proposers can be voted by parties to create vertices pointing to the proposals from proposers. This voting mechanism guarantees that commitment of the leaders is based on a majority vote and thus parties reach an agreement without any additional communication.

One of the most important innovations of BullShark is garbage collection. Garbage collection is instrumental for solving the memory of DAG protocols. By incorporating garbage collection, BullShark is able to flush ancient vertices while still ensuring fairness in synchronous periods. More significantly, this permits making the protocol practical for long-time operation since memory is bounded and avoids the memory limitations of previous DAG protocols.

Implementation.

Implementation-wise, BullShark is efficient and straightforward. Deployability: The protocol itself needs a minimum of additional code — 200 lines — over and above already existing DAG-based mempool implementations. This simplicity enhances its deployability, integration into many other prevailing blockchain systems. In practical evaluations, we show BullShark to be extremely efficient: it can process up to 125,000 transactions per second and achieve a latency of 2 seconds in a network of 50 parties.

The overall structure of this BullShark protocol is composed of the following steps: initialize the DAG and other structures of the protocol, create new vertices for transactions, deliver and validate messages, progress the round on each message delivery and when a timeout expires, leader election and leader commitment. All these procedures provide a way for the involved parties to agree consistently and securely on the order of the transactions, hence providing a robust consensus mechanism for distributed systems.