{'fraction_non_alphanumeric': 0.031929795156057324, 'fraction_numerical': 0.009948878805655656, 'mean_word_length': 4.488402654576516, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 14, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bullshark: DAG BFT Protocols Made Practical

We present Bullshark, the first directed acyclic graph (DAG) based asynchronous Byzantine Atomic Broadcast protocol that is optimized for the common synchronous case. Like previous DAG-based BFT protocols, Bullshark requires no extra communication to achieve consensus on top of building the DAG. That is, parties can totally order the vertices of the DAG by interpreting their local view of the DAG edges. Unlike other asynchronous DAG-based protocols, Bullshark provides a practical low latency fast-path that exploits synchronous periods and deprecates the need for notoriously complex view-change mechanisms. Bullshark achieves this while maintaining all the desired properties of its predecessor DAG-Rider. Namely, it has optimal amortized communication complexity, it provides fairness and asynchronous liveness, and safety is guaranteed even under a quantum adversary. In order to show the practicality and simplicity of our approach, we also introduce a standalone partially synchronous version of Bullshark which we evaluate against the state of the art. The implemented protocol is embarrassingly simple (200 LOC on top of an existing DAG-based mempool implementation (Narwhal&Tusk). It is highly efficient, achieving for example, 125,000 transaction per second with a 2 seconds latency for a deployment of 50 parties. In the same setting the state of the art pays a steep 50% latency increase as it optimizes for asynchrony.

logic required to safely order them. The idea is simple. To propose transactions, parties send them in a way that forms a casual order among them. That is, messages contain blocks of transactions as well as references to previously received messages, which together form a directed acyclic graph (DAG). Interestingly, the structure of the DAG encodes information that allow parties to totally order the DAG by locally interpreting their view of it without sending any extra messages. That is, once we build the DAG, implementing consensus on top of it requires zero-overhead of communication.
The pioneering work of Hashgraph [9] constructed an unstructured DAG, where each message refers to two previous ones, and used hashes of messages as local coin flips to totally order the DAG in asynchronous settings. Aleph [22] later introduced a structured round-based DAG and encoded a shared randomness in each round via a threshold signature scheme to achieve constant latency in expectation. The state of the art is DAG-Rider [26], which is built on previous ideas. Every round in its DAG has at most vertices (one for each party), each of which contains a block of transactions as well as references (edges) to at least 2 + 1 vertices in the previous round. Blocks are disseminated via reliable broadcast [12] to avoid equivocation, and an honest party advances to the next round once it reliably delivers 2 + 1 vertices in the current round. Remarkably, by using the DAG to abstract away the communication layer, the entire edges interpretation logic of DAG-Rider to totally order the DAG spans less than 30 lines of pseudocode.
DAG-Rider is an asynchronous Byzantine atomic broadcast (BAB), which achieves optimal amortized communication complexity ( ( ) per transaction), post quantum safety, and some notion of fairness (called Validity) that guarantees that every transaction proposed by an honest party is eventually delivered (ordered). To achieve optimal amortized communication DAG-Rider combines batching techniques with an efficient asynchronous verifiable information dispersal protocol [15] for the reliable broadcast building block. The protocol is post quantum safe because it does not rely on primitives that a quantum computer can break for the safety properties. That is, a quantum adversary can prevent the protocol progress, but it cannot violate safety guarantees.
Although DAG-based protocols have a solid theoretical foundation, they have multiple gaps before being realistically deployable in practice. First, they all optimize for the worst case asynchronous network assumptions and do not take advantage of synchronous periods, resulting to higher latency than existing consensus protocols [13,42] in the good case. Second, they have some impractical assumptions such as needing unbounded memory in order to preserve fairness. The only existing solution to this comes from arXiv:2201.05677v3 [cs.CR] 7 Sep 2022 Tusk [20], which uses a garbage collection mechanism but does not allow for quantifiable fairness even during periods of synchrony.
On the other hand, existing partially synchronous consensus protocols are designed as a monolith, where the leader of the protocol has to propose blocks of transactions in the critical path, resulting in performance bottlenecks and relatively low throughput as shown by Narwhal [20].
To the best of our knowledge, this paper is the first to optimize the DAG-based BFT approach to the partially synchronous communication setting. First, we propose BullShark, which preserves all the theoretical properties of DAG-Rider (including asynchronous worst case liveness), and in addition, introduces a fast path that exploits common-case synchronous network conditions. That is, BullShark is the first BAB protocol with optimal amortized communication complexity ( ( ) per transaction) and post quantum safety that is optimized for the common case. BullShark needs only 2 roundtrips between commits during synchrony (thus a 75% improvement compared to DAG-Rider), and maintains a 6 round-trip expected latency in asynchronous executions (matching DAG-Rider). In addition, BullShark is built on top of Narwhal and thus inherits all of its practical benefits (e.g., decoupling data dissemination from the DAG construction and having an efficient reliable broadcast implementation).
Second, based on BullShark's fast path, we present an eventually synchronous variant of BullShark, which is the first partially synchronous consensus protocol that is completely embedded into a DAG. The protocol is fundamentally different from previous partially synchronous protocols since it is symmetric, and does not require a view-change or view synchronization mechanisms after a faulty leader. The resulting protocol is embarrassingly simple and extremely efficient, achieving 125k TPS and 2 second latency with 50 honest parties. As a final contribution, BullShark overcomes an existing practical limitation of DAG-based protocols of having to choose between fairness and garbage collection. BullShark garbage collects vertices belonging to old DAG rounds, and also provides fairness during synchronous periods. As an evidence to its practicality, the partially synchronous version of BullShark has already been productionized by Mysten Labs and is currently being integrated by Aptos.
In summary, this paper makes the following contributions: • We propose BullShark, the first slow-path/fast-path DAGbased consensus protocol that achieves significantly lower latency than prior work. BullShark takes 2 rounds in the good case and 6 rounds in expectation (matching DAG-Rider) in asynchrony. • We simplify BullShark to work only in partial synchrony.
This version of BullShark results in a significantly simpler partially synchronous consensus protocol than prior work (extra 200LOC vs 4000LOC of Hotstuff over a DAG [20]). BullShark additionally performs significantly better under faults making it the most performant and resilient partially synchronous protocol to date. • We show how to build a practical DAG-based system that allows for garbage collection and provides timely fairness after GST, answering an open question of prior work [20,26].

TECHNICAL CHALLENGES.
In order to design and implement BullShark we had to solve a number of theoretical and practical challenges.
Theoretical challenges. The approach in current DAG-based protocols is to advance rounds as soon as enough messages in the current round are received (2 + 1 for Aleph and DAG-Rider). This works perfectly for asynchronous consensus, but unfortunately cannot guarantee deterministic liveness during synchronous periods [21], as required by the eventually synchronous variant of BullShark. This is because the adversary can, for example, reorder messages (within the synchrony bound) to make sure parties advance rounds before getting messages from the predefined leaders. Note that this is inherent to any deterministic protocol. We considered and evaluated two alternatives (see Appendix B) and decided to embed timeouts into the DAG construction as it provided better performance. In a nutshell, if the first 2 + 1 messages in a round do not contain one from the leader, then parties wait for a timeout or a message from the leader before advancing to the next round. A further challenge is to take advantage of a common-case synchronous network without sacrificing latency in the asynchronous worst case. To this end, BullShark introduces two types of votessteady-state for the predefined leader and fallback for the random one. Similarly to DAG-Rider [26], BullShark rounds are grouped in waves, each of which consists of 4 rounds. Intuitively, each wave encodes the consensus logic. The first round of a wave has two potential leaders -a predefined steady-state leader and a leader that is chosen in retrospect by the randomness produced in the fourth round of the wave. To reduce latency in synchronous periods, the third round of a wave also has a predefined leader. It takes two rounds to commit a steady-state leader. Based on their voting type, the vertices in the second round can potentially vote for the steady-state leader in the first round and vertices in the fourth round can potentially vote for the fallback leader in round one or the steady-state leader in round three. Importantly, the same vertex cannot vote for both the fallback and steady-state leaders in the same wave. A vertex's voting type is determined by whether or not its source (the party that broadcasted it) committed a leader in the previous wave. This information is encoded in the DAG and since the DAG is built on top of a reliable broadcast abstraction, even Byzantine parties cannot lie about their voting type.
A nice property of BullShark is that it does not require a view change or view synchronization mechanisms to overcome faulty or slow leaders. Instead of a view change, BullShark uses the information encoded in the DAG to maintain safety. Since all parties agree on the causal histories of vertices they have in the DAG, after a leader is committed each party locally "rides" the DAG (wave by wave) backwards to see which leader-vertices could have been committed by other parties. Synchronizing views is not required because (as we show in our proofs) the DAG construction already provides it. If the first leader in a wave after GST is honest, then all parties advance to the third round of the wave roughly at the same time.
Practical challenges. Finally, to evaluate BullShark we had to resolve some practical challenges. First, all previous theoretical solutions require unbounded memory to hold the entire DAG, and second, the reliable broadcast primitive we use to clearly describe BullShark (used in DAG-Rider and Aleph as well) is inefficient in the common-case. Fortunately, Narwhal [20] implemented a scalable DAG and dealt exactly with these problems. We started from Narwhal's open source codebase and adopt their approach to decouple data from metadata to implement an efficient broadcast. Unfortunately, the Narwhal garbage collection mechanism directly conflicts with BullShark's mechanism to provide fairness. In fact, providing meaningful fairness for all honest parties seems to be impossible with bounded memory implementations in asynchronous networks since every message can be delayed to after the relevant prefix of the DAG is garbage collected. To deal with this issue we relax our fairness requirement. That is, our bounded memory implementation of BullShark guarantees timely fairness only during synchronous periods. This means that after GST all messages by honest parties make it into the DAG in finite time and before the garbage collection. For all the other messages (before GST) we use Tusk's approach of retransmission, where guarantees can only be made for an unbounded execution.

PRELIMINARIES 3.1 Model
We consider a peer to peer message passing model with a set of parties Π = { 1 , . . . , }, and a dynamic adversary that can corrupt up to < /3 of them during an execution. We say that corrupted parties are Byzantine and all other parties are honest. Byzantine parties may act arbitrarily, while honest ones follow the protocol. We assume that the adversary is computationally bounded.
For the description of the protocol we assume that links between honest parties are reliable. That is, all messages among honest parties eventually arrive 1 . Moreover, for simplicity, we assume that recipients can verify the senders identities. We assume a known Δ and say that an execution of a protocol is eventually synchronous if there is a global stabilization time (GST) after which all messages sent among honest parties are delivered within Δ time. An execution is synchronous if GST occurs at time 0, and asynchronous if GST never occurs.
For the protocol analysis we are interested in the practical performance as well as theoretical complexity during synchronous and asynchronous periods, or alternatively, before and after the GST. To this end, we define consider the following scenarios: • Worst case condition: asynchronous execution and byzantine parties • Common case condition: synchronous executions with no failures 2

Building blocks
Similarly to DAG-Rider, we use the following known building blocks for our modular protocol presentation: Reliable broadcast Each party can broadcast messages by calling r_bcast ( , ), where is a message and ∈ N is a round number. Every party has an output r_deliver ( , , ), where is a message, is a round number, and is the party that called the 1 We address this issues from a practical point of view in our implementation. 2 Same analysis apply to eventually synchronous failure-free executions after GST. corresponding r_bcast ( , ). The reliable broadcast abstraction guarantees the following properties: Agreement If an honest party outputs r_deliver ( , , ), then every other honest party eventually outputs r_deliver ( , , ). Integrity For each round ∈ N and party ∈ Π, an honest party outputs r_deliver ( , , ) at most once regardless of . Validity If an honest party calls r_bcast ( , ), then every honest party eventually outputs r_deliver ( , , ).
Global perfect coin An instance , ∈ N, of the coin is invoked by party ∈ Π by calling choose_leader ( ). This call returns a party ∈ Π, which is the chosen leader for instance . Let be the random variable that represents the probability that the coin returns party as the return value of the call choose_leader ( ). The global perfect coin has the following guarantees: Agreement If two honest parties , call choose_leader ( ) and choose_leader ( ) with respective return values 1 and 2 , then 1 = 2 . Termination If at least +1 honest parties call choose_leader( ), then every choose_leader( ) call eventually returns. Unpredictability As long as less than + 1 honest parties call choose_leader( ), the return value is indistinguishable from a random value except with negligible probability . Namely, the probability that the adversary can guess the returned party of the call choose_leader( ) is ≤ Pr[ = ] + . Fairness The coin is fair, i.e., ∀ ∈ N, ∀ ∈ Π : Pr Implementation examples that use PKI and a threshold signature scheme [11,30,35] can be found in [14,31]. See DAG-Rider for more details on how a coin implementation can be integrated into the DAG construction. It is important to note that the above mentioned implementations satisfy Agreement, Termination, and Fairness with information theoretical guarantees. That is, the assumption of a computationally bounded adversary is required only for the unpredictability property. As we later prove, the unpredictability property is only required for Liveness. Therefore, since similarly to DAG-Rider generating randomness is the only place where cryptography is used, the Safety properties of BullShark are post-quantum secure.

Problem Definition
Following DAG-Rider [26], our result focuses on the Byzantine Atomic Broadcast (BAB) problem. To avoid confusion with the events of the underlying reliable broadcast abstraction, the broadcast and deliver events of BAB are a_bcast( , ) and a_deliver( , , ), respectively, where is a message, ∈ N is a sequence number, and ∈ Π is a party. The purpose of the sequence numbers is to distinguish between messages broadcast by the same party. We assume that each party broadcasts infinitely many messages with consecutive sequence numbers.
Note that the above definition is agnostic to the network assumptions. However, in asynchronous executions, due to the FLP result [21], BAB cannot be solved deterministically and therefore we relax the validity property to hold with probability 1 in this case. Moreover, the validity property cannot be satisfied in asynchronous executions with bounded memory implementation. Therefore, as we discuss more in Section 7, for the practical version of this problem, we require validity to be satisfied only after GST in eventually synchronous executions.
Note that the BAB abstraction captures the core consensus logic in permissioned blockchain systems as it provides a mechanism to propose blocks of transactions and totally order them. Moreover, similar to Hyperledger [8], it supports a separation between the total order mechanism and transaction execution. Transaction validation can therefore be done as part of the execution [8] before applying it to the SMR.

DAG CONSTRUCTION
In this section we describe our DAG construction and explain how it is different from the one in DAG-Rider [26]. In a nutshell, DAG-Rider is a fully asynchronous atomic broadcast protocol and thus rounds in its DAG advance in network speed as soon as 2 +1 nodes from the current round are delivered. Here, we are interested in a protocol that deterministically achieves better latency in synchronous periods. Therefore, introducing timeouts into the system is unavoidable [21]. We considered and evaluated two alternatives (see Appendix B for more details) and decided to integrate timeouts into the DAG construction. It is important to note that despite the timeouts, our DAG still advances in network speed when the leader is honest.
We present the background, structures, and basic utilities we borrow from DAG-Rider in Section 4.1. We describe our DAG construction in Section 4.2.

Background
We use a DAG to abstract the communication layer among parties and enable the establishment of common knowledge. Each vertex in the DAG represents a message disseminated via reliable broadcast from a single party, containing, among other data, references to previously broadcasted vertices. Those references are the edges of the DAG. Each honest party maintains a local copy of the DAG, and different honest parties might observe different views of it (depending on the order in which they deliver the vertices). Nevertheless, reliable broadcast prevents equivocation and guarantees that all honest parties eventually deliver the same messages, hence their views of the DAG eventually converge.
The DAG data types and and basic utilities are specified in Algorithm 1. For each party , we denote 's local view of the DAG as , which is represented by an array of sets of vertices []. Vertexes are created via the _ _ ( ) procedure. Each vertex in the DAG is associated with a unique round number and the party who generated and reliably broadcasted it (the source). In addition, each vertex contains a block of transactions that were previously _ by the BAB protocol that is implemented on top of the DAG and two sets of outgoing edges. The set strong edges contains at least 2 + 1 references to vertexes associated with round − 1 and the set weak edges contains up to references to vertices in rounds < − 1 such that otherwise there is no path from to them. As explained in the next sections, strong edges are used for Safety and weak edges make sure we eventually include all vertices in the total order, to satisfy BAB's validity property.
The entry [ ] for ∈ N stores a set of vertices associated with round that previously delivered. By the reliable broadcast, each party can broadcast at most 1 vertex in each round and thus | [ ]| ≤ . The procedures ℎ( , ) and _ ℎ( , ) get two vertexes and check if there is a path from to . The difference between them is that ℎ( , ) considers all edges while _ ℎ( , ) only considers the strong ones.
The procedure _ _ _ gets a wave number, computes the randomly elected leader of the wave and then returns the vertex that the elected leader broadcast in the first round of the wave, if it is included in the DAG. Otherwise, returns ⊥. Similarly, the procedures _ _ _ _ and _ _ _ _ return the vertices broadcast by the first and second predefined leaders of the wave, respectively. We assume a predefined and known to all parties mapping waves to steady-state leaders.

Our DAG protocol
A detailed pseudocode is given in Algorithm 2. Each party maintains three local variables: round stores the last round in which broadcast a vertex, buffer stores vertices that where reliably delivered but not yet added to the DAG, and wait is an Boolean that indicate whether the timeout for the current round has already expired. Each party is constantly trying to advance rounds and calling the high-level BAB protocol to totally order all the vertices in its DAG. When advances its round, it broadcast its vertex for this round and start a timeout.
Our DAG protocol is triggered by one of two events: a vertex delivery (via reliable broadcast) or a timeout expiration. Once a party delivers a vertex it first checks if the vertex is legal, i.e., (1) the source and round must match the reliable broadcast instance to prevent equivocation, and (2) the vertex must has at least 2 + 1 strong edges. Then, checks if the vertex is ready to be added to the DAG by calling _ _ _ . The idea is to make sure that the causal history of a vertex is always available in the DAG. Therefore, a vertex is added to the DAG only if all the vertices it includes as references are already delivered. If this is not yet the case, the vertex is added to a buffer for a later retry. Once a vertex is added to the DAG, the high-level BAB protocol is invoked, via the _ ( ) interface, to check if more vertices can now be totally ordered.
We next describe the conditions for advancing rounds. Note that since DAG-Rider only cares about the asynchronous case, rounds are advanced as soon as 2 + 1 vertices in the current round are delivered. We, in contrast, optimize for the common case conditions and thus have to make sure that parties do not advance rounds too fast. Otherwise, the adversary can prevent honest parties from Algorithm 1 Data structures and basic utilities for party Local variables: struct vertex : ⊲ The struct of a vertex in the DAG .round -the round of in the DAG .source -the party that broadcast .block -a block of transactions .strongEdges -a set of vertices in .round − 1 that represent strong edges .weakEdges -a set of vertices in rounds < .round − 1 that represent weak edges [] -An array of sets of vertices, initially: [0] ← predefined hardcoded set of 2 + 1 "genesis" vertices ∀ ≥ 1 : [ ] ← { } blocksToPropose -A queue, initially empty, enqueues valid blocks of transactions from clients 1: procedure path( , ) ⊲ Check if exists a path consisting of strong and weak edges in the DAG 2: return exists a sequence of ∈ N, vertices 1 , 2 , . . . , s.t. . ← 8: .
We distinguish between slow and up-to-date parties. As mentioned in the introduction, BullShark does not require an external view-synchronization mechanism for slow parties. Instead, once delivers 2 + 1 vertices in a round > round, jumps forward to round , broadcasts a vertex in round , and starts a new timeout.
For the up-to-date parties we need to be more careful. As we explained more in the next section, each wave has a steady-state leader in the first round and a steady-state leader in the third one. Intuitively, the vertices of these leaders are interpreted as "proposals" and the vertices in immediately following rounds with strong edges to the leaders' vertices are interpreted as "votes". In addition, each party can vote for the steady-state leaders in a wave only if its voting type is steady-state for this wave. To make sure all honest parties get a chance to vote for steady state leaders, an up-to-date honest party will try to advance (via _ _ ) to the second and forth rounds of a wave only if (1) the timeout for this round expired or (2) delivered a vertex from the wave predefined first and second steady-state leader, respectively. Similarly, we need to make sure the adversary cannot prevent honest parties from collecting enough votes to commit an honest leader after GST. Therefore, before trying to advance (via _ _ ) to the third round a wave or the first round of the next wave, waits for either the timeout expiration or to deliver 2 + 1 vertices in the current round with steady-state voting type and strong edges to the first and second steady-leader, respectively. In Section C.2, we prove that after GST timeouts never expire for honest leaders and the DAG advances in network speed.

THE BULLSHARK PROTOCOL
In this section we present a detailed description of BullShark. Similarly to DAG-Rider [26], the ordering logic of BullShark requires no communication on top of building the DAG. Instead, each party observes its local copy of the DAG and totally order its vertices by interpreting the edges as "votes". In order to optimize for the common case conditions while guaranteeing liveness under worst case asynchronous conditions, BullShark has two types of leaders: steady-state and fallback. The main challenge in designing BullShark is the interplay between them as we need to make sure parties cannot vote for both types at the same round. Illustration of BullShark can be found in Figure 1. We divide the protocol description into two parts. In Section 5.1 we describe the commit rule of each leader, and in Section 5.2 we explain how parties totally order leaders' causal histories. In Section 6 we preset an eventually synchronous version of BullShark and in Section 7 we discuss the details of our garbage collection mechanism. For space limitations, we provide formal proofs for both versions on BullShark in Appendix C.

Algorithm 2 DAG construction, protocol for process
Local variables:

Voting Types
Similarly to DAG-Rider, to interpret the DAG, each party divides its local view of the DAG, , into waves of 4 rounds each. Unlike DAG-Rider, which has one potential leader in every wave, BullShark has three. One fallback leader in the first round of each wave, which is elected retrospectively via the randomness produced in the forth round of the wave (as in DAG-Rider), and two predefined steady-state leaders in the first and third rounds of each wave. In the common case, during synchronous periods, both steadystate leaders are committed in each wave, meaning that it takes two rounds on the DAG to commit a leader. During asynchronous periods, each fallback leader is committed with probability of at least 2/3. Meaning that during asynchrony, a fallback leader is . S1A denotes the first steady state leader of wave 1 (in round 1), and S1B denotes the second steady state leader of wave 1 (in round 3). F1 denotes the fallback leader of wave 1 (in round 1). All parties start off with a steady state vote type in wave 1. In round 2, P1 observes 3 (2f + 1) steady state votes for S1A (denoted in red), so P1 commits S1A. In round 4, P1 only observes 1 vote for the second steady state leader S1B, so P1 does not commit S1B. Since P1 does not commit the second steady state leader, it has a fallback vote type in wave 2. From the DAG in round 5, P1 also observes that P2, P3, P4 did not commit S1B, so all parties have a fallback vote type in wave 2. Thus S2A and S2B (the first and second steady state leaders in wave 2 respectively) cannot be committed since all vote types are fallback. In round 8, P1 observes 3 (2f + 1) fallback votes for the fallback leader F2 (denoted in blue), so P1 commits F2. Once P1 commits F2, it checks to see whether any previous leader it did not commit, could have been committed. In round 4, P1 only observes 1 steady state vote for S1B (less than f + 1), so it does not commit S1B since if it would have been committed by some party then P1 would observed at least + 1 votes. committed every 6 rounds in expectation and BullShark has liveness with probability 1.
A nice property of the common case execution of BullShark is that it does not require external view-change and view-synchronization mechanisms. When switching from asynchrony to synchrony, the first two rounds of each wave make sure that if the first leader is honest then all honest parties start the third round roughly at the same time. View-change is not required because the DAG encodes all the information needed for safety. In particular, parties can see what information other parties had when they interpreted the DAG, and decide accordingly.
The pseudocode appears in Algorithm 3. The procedure try_ordering is called every time a new vertex is added to the DAG. Since Bull-Shark has two types of leaders in each wave, we need to ensure that fallback and steady-state leaders are never committed in the same wave. To this end, parties cannot vote for both types of leaders in the same wave. That is, every party is assigned with a voting type in every wave that is either fallback or steady-state. When a party interprets its local copy of the DAG it keeps track of other parties voting types in steadyVoters[w] and fallbackVoters[w], where is a wave number.
Intuitively, a party is in steadyVoters[w] if it has committed either the second steady-state or the fallback leader in wave − 1. Specifically, party determines 's voting type in wave when it delivers 's vertex in the first round of wave , which triggers return true 94: return false the call to the determine_party_vote_type procedure. If the causal history of has enough information to commit one of these leaders, then determines 's voting type as steady-state, otherwise, as fallback. By the properties of reliable broadcast, all parties see the same causal history of vertex , and thus agree on 's voting type in round (even Byzantine parties cannot lie about their voting type).
To commit a leader in wave − 1 based on a vertex in the first round of a wave , considers the set of vertices pointed by 's strong edges as potential "votes". Note that these vertices belong to wave − 1 and each of them has a voting type that was already previously determined by . To commit the fallback leader of wave − 1, at least of 2 + 1 out of the potential votes must have strong paths to the leader and a fallback voting type. Similarly, to commit the second steady-state leader of wave − 1, at least 2 + 1 out of the potential votes must to have strong paths to the leader and steady-state voting type. Committing the first steady-state leader of a wave is similar but in this case the strong edges of a vertex in the third round of the wave are considered as potential votes. Note that since even a Byzantine party cannot lie about its voting type, quorum intersection guarantees that leaders with different types cannot be committed in the same wave. This is the reason we ask for 2 + 1 strong paths unlike Tusk where + 1 strong paths are sufficient for safety. As we describe next, when a leader is committed then the procedure commit_leader is called to totally order 's causal history.

Ordering The DAG
So far we described the wave commit rules and how parties use them to determine other parties voting types. Next we describe how we totally order the DAG. The pseudocode appears in Algorithm 4. Once a party commits a (steady-state or fallback) leader vertex it calls _ ( ). To totally order the causal history of , first tries to commit previous leaders for which the commit rule in its local copy of the DAG was not satisfied. To do this, traverses back the rounds of its DAG until the last round in which it committed a leader and check whether it is possible that other honest parties committed leaders in these rounds based on their local copy of the DAG. If encounters such a leader, it orders it before . Note that this part is much trickier than in DAG-Rider since BullShark has three potential leaders in every wave. ← v.round − 2 ⊲ There is a potential leader to commit every two rounds 98: if . = + 2 then 106: fbVotes ← { } ⊲ fallback leader could not be committed since 107: there at least 2 + 1 steady-state vote types in this wave 108: else 109: for every ′ ∈ verticesToDeliver in some deterministic order do 129: output a_deliver ( ′ .block, ′ .round, ′ .source) 130: By quorum intersection and the non-equivocation property of the DAG, if some party commits either a fallback or a steady-state leader by seeing 2 + 1 votes, then all other parties see at least + 1 of these votes. Moreover, since a party cannot vote for both types of leaders in the same wave, if sees + 1 votes for the fallback (steady-state) leader, then no party could have committed the steady-state (fallback) leader since in this case there are at most 2 votes with steady-state (fallback) type.
To make sure orders the leaders that precedes consistently with the other parties, we need to make sure that parties consider the same potential votes when deciding whether to order one of them. To this end, to decide whether to order a steady-state leader ′ , sets the potential votes to be all the vertices in round ′ . + 1 in its DAG such that there is a strong path between the last leader previously ordered and ′ . For a fallback leader ′ , the potential votes are set in a similar way but round ′ + 3 is used instead of ′ + 1 to be consistent with the commit rule.
After computing the potential votes, checks if one of the leaders in the round it is currently traversing could be committed by other honest parties. First, checks the potential votes type and the existence of strong paths to the leaders to determines the sets of votes for the steady-state and fallback leaders. Note that the set of votes for the fallback leader is empty in rounds without a fallback leader or if a steady-state leader was already committed in this wave. Then, checks if one of the leaders in the round has at least + 1 votes while the other has at most . If this is the case orders by pushing it to the leader's stack leaderStack and continues its traversal to the next rounds to check if there are leaders to order before . Otherwise, skips the leaders of the current round as it is guaranteed that none if them could have been committed.
As we prove in Appendix C, all honest parties order the same leaders and in the same order. All that is left is to apply some deterministic rule to order their causal histories one by one. Therefore, after committing a leader (and finishing ordering all leaders that proceeds for which the commit rule was not satisfied), party calls _ (). This function goes over the ordered leaders one by one, and for each of them delivers, by some deterministic order, all the blocks in the vertices in it causal history (strong and weak edges) that have not yet been delivered.

EVENTUALLY SYNCHRONOUS BULLSHARK
In this section we present an eventually synchronous version of the Bullshark protocol. This protocol is embarrassingly simple, and as we demonstrate in Section 9, very efficient. To the best of our knowledge, this is the first eventually synchronous BFT protocol that does not require view-change or view-synchronization mechanism. The presentation here is based on the terminology of Section 5. An intuitive illustration can be found in Appendix A and an extended description in [3]. In a nutshell, there are no fallback leaders in the eventually synchronous version of BullShark. Instead, parties keep trying to commit the steady-state leaders. The pseudocode, which overwrites the _ procedure, appears in Algorithm 5 (Note that some procedures from previous Algorithms are called). In section C.2 we give a formal proof of Safety and Liveness. In a nutshell, the safety proof has a similar proof structure as BullShark with fallback, and for liveness we show that after GST two consecutive honest predefined leaders guarantee that the second leader will be committed by all honest parties. In particular, we show that if the first leader of wave is honest, then all honest parties advance to the third round of roughly at the same time. Moreover, if the second leader is honest than all honest parties will wait for the second leader before advancing to the fourth round, and thus all honest will see at least 2 + 1 votes for the second leader in and commit it.

GARBAGE COLLECTION IN BULLSHARK
One of the main practical challenges and a potential reason that DAG-based BFT protocols are not yet widely deployed is the need for unbounded memory to guarantee validity and fairness. In other words, the question of how to satisfy fairness and at the same time garbage collect old parts of the DAG from the working memory of the system. For example, HashGraph [9] constructs an unstructured DAG, and thus has to keep in memory the entire prefix of the DAG in order to verify the validity of new blocks. DAG-Rider [26], Aleph [22], and Narwhal [20] use a round-based structured DAG, but do not provide a solution to the aforementioned question. The only DAGbased BFT we are aware of that proposed a garbage collection mechanism is Narwhal [20]. Their mechanism uses the consensus decision in order to agree what rounds in the DAG can be cleaned. However their protocol sacrifices the Validity (fairness) property of the BAB problem. It does not provide fairness to all parties since blocks of slow parties can be garbage collected before they have a chance to be totally ordered. DAG-Rider [26], on the other hand, make use of weak links to refer to yet unordered blocks in previous rounds, which guarantees that every block is eventually ordered. The solution works well in theory, but it is unclear how to garbage collect it.
In fact, through our investigation we realized that providing the BAB's validity (fairness) property with bounded memory in fully asynchronous executions is impossible since blocks of honest parties can be arbitrarily delayed. Similarly to the core observation in the FLP [21] impossibility result, in asynchronous settings, it is impossible to distinguish between faulty parties that will never broadcast a block and slow parties for which we need to wait before garbage collecting old rounds.
Fairness after GST. In the BullShark implementation we propose a practical alternative. We maintain bounded memory at the cost of providing fairness only after GST. What we need is a 3 failure detector [19,29] which will be strong and complete after GST letting us garbage collect rounds even if we did not get vertices from all parities (i.e., we do not need to wait forever for faulty parties). We do it by leveraging the structure of our DAG and introducing the notion of timestamp as described below. Formally, our implementation of BullShark maintains bounded memory and satisfies the following: Definition 7.1. If an honest party calls r_bcast ( , ) after GST, then every honest party eventually outputs r_deliver ( , , ).
For the garbage collection mechanism we add a timestamp for every vertex. That is, an honest party specify in . the time when it broadcast its vertex . In addition, parties maintain a garbage collection round, GCround, and never add vertices to the DAG in rounds below it. Note that the latency of the reliably broadcast building block we use is bounded after GST, but depends on the specific implementation. For the protocol description we assume that the time it takes to reliably broadcast a message after GST is Δ. The pseudocode, in which we describe how to change the function order_vertices that is used by both versions of BullShark, appears in Algorithm 6. The idea is simple. For every leader we order, we assign a timestamp , which is computed as the median of all the timestamp of ' parents (i.e., 's strong edges). Then, while traversing 's causal history to find vertices to order, we compute a timestamp for every round in a similar way (the median of timestamps of the vertices in this round). If the difference between the timestamp is above 3Δ the round is garbage collected.
Since by the properties of the underling reliable broadcast all parties agree on the causal histories of the leaders, once parties agree which leaders to order they also agree what rounds to garbage collect. Therefore, the garbage collection mechanism preserves the safety and liveness properties we prove in Appendix C. Below we argue that when announced with the above garbage collection, Bull-Shark satisfies Definition 7.1 while preserving bounded memory.
Bounded memory. In Appendix C we show that for every round there is a round ′ > in which a leader is committed. In particular, this means that for every round with median timestamp , there will be eventually a committed leader with a high enough timestamp for to be garbage collected.
Fairness. First note that since every round has at least 2 + 1 vertices, the median timestamp of a round always belongs to an honest party. Let be a party that broadcast a vertex at some round at time after GST, we show that all honest parties order . By the assumption on the reliable broadcast latency, all honest parties reliably deliver before time + Δ. Let be the first party Algorithm 6 Garbage collection. Algorithm for party . for every ′ ∈ verticesToDeliver do ⊲ in some deterministic order 20: output a_deliver ( ′ .block, ′ .round, ′ .source) 21: deliveredVertices ← deliveredVertices ∪ { ′ } that advances to round . In Appendix C we show that if an honest party advances to round at time after GST, then all honest parties advance to round no later than at time + 2Δ. Therefore, advanced to round not before − 2Δ. Therefore, the timestamp of round is at least − 2Δ. Thus, round is garbage collected only after a leader ′ with timestamp higher than + Δ is ordered. By the way the leader's timestamp is computed there is at least one vertex ′′ in ′ .strongEdges that broadcast by an honest party after time + Δ. Therefore, by the manner weak edges are added, there is an edge between ′′ and . Fairness follows since and ′′ are in ′ 's casual history and thus both ordered together with ′ .

IMPLEMENTATION
We implement a networked multi-core eventually synchronous BullShark party forking the Narwhal project 3 . Narwhal provides the structured DAG used at the core of BullShark, which we modify to support fast-path in partial synchrony as described in Section 4.2.
Additionally, it provides well-documented benchmarking scripts to measure performance in various conditions, and it is close to a production system (it provides real networking, cryptography, and persistent storage). It is implemented in Rust, uses tokio 4 for asynchronous networking, ed25519-dalek 5 for elliptic curve based signatures, and data-structures are persisted using Rocksdb 6 . It uses TCP to achieve reliable point-to-point channels, necessary to correctly implement the distributed system abstractions. By default, the Narwhal codebase runs the Tusk consensus protocol [20]; we modify the proposer module of the primary crate and the consensus crate to use BullShark instead. Implementing BullShark requires editing less than 200 LOC, and does not require any extra protocol message or cryptographic tool. We are open-sourcing Bull-Shark 7 along with any Amazon web services orchestration scripts and measurements data to enable reproducible results 8 .

EVALUATION
We evaluate the throughput and latency of our implementation of BullShark through experiments on AWS. We particularly aim to demonstrate that (i) BullShark achieves high throughput even for large committee sizes, (ii) BullShark has low latency even under high load, in the WAN, and with large committee sizes, and (iii) BullShark is robust when some parts of the system inevitably crashfail. Note that evaluating BFT protocols in the presence of Byzantine faults is still an open research question [10]. We deploy a testbed on AWS, using m5.8xlarge instances across 5 different AWS regions: N. Virginia (us-east-1), N. California (uswest-1), Sydney (ap-southeast-2), Stockholm (eu-north-1), and Tokyo (ap-northeast-1). Parties are distributed across those regions as equally as possible. Each machine provides 10Gbps of bandwidth, 32 virtual CPUs (16 physical core) on a 2.5GHz, Intel Xeon Platinum 8175, 128GB memory, and runs Linux Ubuntu server 20.04. We select these machines because they provide decent performance and are in the price range of 'commodity servers'.
In the following sections, each measurement in the graphs is the average of 2 independent runs, and the error bars represent one standard deviation; errors bars are sometimes too small to be visible on the graph. Our baseline experiment parameters are 10 honest parties, a maximum block size of 500KB, and a transaction size of 512B. We instantiate one benchmark client per party (collocated on the same machine) submitting transactions at a fixed rate for a duration of 5 minutes. The leader timeout value is set to 5 seconds. When referring to latency, we mean the time elapsed from when the client submits the transaction to when the transaction is committed by one party. We measure it by tracking sample transactions throughout the system. HotStuff The maximum throughput we observe for HotStuff is 70,000 tx/s for a committee of 10 parties, and lower (up to 50,000 tx/s) for a larger committee of 20, and even lower (around 30,000 tx/s) for a committee of 50. The experiments demonstrate that HotStuff does not scale well when increasing the committee size. However, its latency before saturation is low, at around 2 seconds.

Benchmark in the common case
Tusk Tusk exhibits a significantly higher throughput than HotStuff. It peaks at 110,000 tx/s for a committee of 10 and at around 160,000 tx/s for larger committees of 20 and 50 parties. It may seem counterintuitive that the throughput increases with the committee size: this is due to the implementation of the DAG not using all resources (network, disk, CPU) optimally. Therefore, more parties lead to increased multiplexing of resource use and higher performance [20]. 7 https://github.com/asonnino/narwhal/tree/bullshark 8 https://github.com/asonnino/narwhal/tree/bullshark/benchmark/data Despite its high throughput, Tusk's latency is higher than HotStuff, at around 3 secs (for all committee sizes).
BullShark BullShark strikes a balance between the high throughput of Tusk and the low latency of HotStuff. Its throughput is significantly higher than HotStuff, reaching 110,000 tx/s (for a committee of 10) and 130,000 tx/s (for a committee of 50); BullShark's throughput is over 2x higher than HotStuff's. Bullshark is built from the same DAG as Tusk and thus inherits its scalability allowing it to maintain high performance for large committee sizes. BullShark's selling point over Tusk is its low latency, at around 2 sec no matter the committee size. BullShark's latency is lower than Tusk since it commits within 2 DAG rounds while Tusk requires 4. BullShark's latency is comparable to HotStuff and 33% lower than Tusk. Figure 3 highlights this trade-off by showing the maximum throughput that can be achieved by HotStuff, Tusk, and Bullshark while keeping the latency under 2.5s and 5s. Tusk and Bullshark scale better than HotStuff when increasing the committee size; there is no dotted line for Tusk since it cannot commit transactions in less than 2.5s. Figure 4 depicts the performance of HotStuff, Tusk, and BullShark when a committee of 10 parties suffers 1 to 3 crash-faults (the maximum that can be tolerated in this setting). HotStuff suffers a massive degradation in throughput as well as a dramatic increase in latency. For 3 faults, the throughput of HotStuff drops by over 10x and its latency increases by 15x compared to no faults. In contrast, both Tusk and BullShark maintain a good level of throughput: the underlying DAG continues collecting and disseminating transactions despite the crash-faults, and is not overly affected by the faulty parties. The reduction in throughput is in great part due to losing the capacity of faulty parties. When operating with 3 faults, both Tusk and BullShark provide a 10x throughput increase and about 7x latency reduction with respect to HotStuff.

Performance under asynchrony
HotStuff has no liveness guarantees when the eventual synchrony assumption does not hold (before GST), either due to (aggressive) DDoS attacks targeted against the leaders [38] or adversarial delays on the leaders' messages as experimentally proven in prior work [20,23] . That is, the throughput of the system falls to 0. The same can happen to the partially synchronous version of BullShark. The reason is that whenever a party becomes the leader for some round, its proposal can be delayed such that all other parties timeout for that round. In order to avoid this attack, Tusk and DAG-Rider elects leaders unpredictably after the DAG is constructed which makes such attacks impossible. The purpose of the fallback mode of BullShark is to maintain the same liveness properties as Tusk and DAG-Rider under asynchrony without compromising on performance during periods of synchrony. If the voting type of all parties is fallback, then BullShark acts as Tusk. In the fallback mode, Bull-Shark thus renounces to its latency advantage with respect to Tusk in order to remain live under asynchrony. As any asynchronous protocol, the performance of both Tusk and BullShark during periods of asynchrony can be arbitrarily bad as they depend on the network conditions (which guarantee delivery after unbounded time). When   the period of asynchrony ends, parties change their voting type to steady-state, and BullShark offers again its state-of-the-art latency.

RELATED WORK
In this Section we discuss other prior works relevant to BullShark and a more in depth comparison with the systems against which we evaluate.
Performance comparisons: We compare BullShark with Tusk [20] and HotStuff [42]. Tusk is the most similar system to BullShark. It is a zero-message consensus protocol built on top of the same structured DAG as BullShark. It is however fully asynchronous while BullShark is partially-synchronous fast path. HotStuff is an established partially-synchronous protocol running at the heart of a number of projects [1, 2, 4-6], and a successor of the popular Tendermint [13]. We aim to compare BullShark with related systems as fairly as possible. An important reason for selecting Tusk 9 and HotStuff 10 is because they both have open-source implementations sharing deep similarities with our own. They are both written in Rust using the same network, cryptographic and storage libraries than ours. They are both designed to take full advantage of multi-core machines and to run in the WAN.
We limit our comparison to these two systems, thus omitting a number of important related works such as [13,17,18,25,27,39,41]. A practical comparison with those systems would hardly be fair as they do not provide an open-source implementations comparable to our own. Some selected different cryptographic libraries, use different cryptographic primitives (such as threshold signatures), or entirely emulate all cryptographic operations. A number of them are written in different programming languages, do not provide persistent storage, use a different network stack, or are not multithreaded thus under-utilizing the AWS machines we selected. Most implementations of prior works are not designed to run in the WAN (e.g., have no synchronizer), or are internally sized to process empty transactions and are thus not adapted to the 512B transaction size we use. Instead, we provide below a discussion on the performance of alternatives based on their reported work.
Partially-synchronous protocols: Hotstuff-over-Narwhal [20] and Mir-BFT [40] are the most performant partially synchronous consensus protocols available. The performance of the former is close to BullShark under no faults given that they share the same mempool implementation. However, BullShark performs considerably better under faults and the engineering effort of Hotstuffover-Narwhal is double that of BullShark. The extra code required to implement BullShark over Narwhal is about 200 LOC 11 (Alg. 5) whereas the extra code of Hotstuff is more than 4k LOC. Additionally, BullShark adapts to an asynchronous environment with the fallback protocol unlike Hotstuff that will completely forfeit liveness during asynchrony leading to an explosion of the confirmation latency (see Figure 4 of Section 9).
For Mir-BFT with transaction sizes of about 500B (similar to our benchmarks), the peak performance achieved on a WAN for 20 parties is around 80,000 tx/sec under 2 seconds -a performance comparable to our baseline HotStuff. Impressively, this throughput decreases only slowly for large committees up to 100 nodes (at 60,000 tx/sec). Crash-faults lead to throughput dropping to zero for up to 50 seconds, and then operation resuming after a reconfiguration to exclude faulty nodes. BullShark offers higher performance (almost 2x), at the same latency.
DAG-based protocols: The DAG have been used in the context of Blockchains in multiple systems. Hashgraph [9] embeds an asynchronous consensus mechanism into a DAG without a round-byround step structure which results to unclear rules on when consensus is reached. This consequently results on an inability to implement garbage collection and potentially unbounded state. Finally, Hashgraph uses local coins for randomness, which can potentially lead to exponential latency.
A number of blockchain projects build consensus over a DAG under open participation, partial synchrony or asynchrony network assumptions. GHOST [36] proposes a finalization layer over a proof-of-work consensus protocol, using sub-graph structures to confirm blocks as final potentially before a judgment based on longest-chain / most-work chain fork choice rule can be made. Tusk [20] is the most similar system to BullShark. It is an asynchronous consensus using the same structured DAG as BullShark. A limitation of any reactive asynchronous protocol, such as Tusk, is that slow parties are indistinguishable from faulty ones, and as a result the protocol proceeds without them. This creates issues around fairness and incentives, since honest, but geographically distant authorities may never be able to commit transactions submitted to them. Further, Tusk relies on clients to re-submit a transaction if it is not sequenced in time, due to leaders being faulty. In contrast, 11 https://github.com/asonnino/narwhal/tree/bullshark both versions of BullShark satisfy fairness after GST while ensuring bounded memory via a garbage collection mechanism.
Dual-Mode Consensus Protocols: The idea of having optimistic and fallback paths in BFT consensus has first been explored by Kurasawe et al [28] with followup improvements [33,37] on the communication complexity. However, these papers are theoretical and not designed for high-load applications hence their implementation would at best be close to the Hotstuff baseline.
The seminal work from Guerraoui et al [24] introduced Abstract, a framework in which developers can plug and play multiple consensus protocols based on the environment they plan to deploy the protocol. A followup work called the Bolt-Dumbo Transformer (BDT) [32], can be seen as instantiating of Abstract for the specific use case of a dual-mode consensus protocol. BDT takes Abstract's general proposal and instantiates it by composing three separate consensus protocols as black boxes. Every round starts with 1) a partially synchronous protocol (HotStuff), times-out the leader and runs 2) an Asynchronous Binary Agreement in order to move on and run 3) a fully asynchronous consensus protocol [25] as a fallback. Ditto [23] follows another approach that does not require these black boxes. Instead, it combines a 2-phase variant of Hotstuff with a variant of the asynchronous VABA [7] protocol for fallback. As a result it reduces the latency cost of BDT significantly, but cannot be generalized to a plug-and-play framework.
All the protocols above solve the problem of consensus in asynchrony, but they include the actual transactions in the proposals, hence their throughput is bounded by the one of Hotstuff. A way to increase their throughput would be to adopt the Narwhal-HS [20] approach introduced in prior work, which substitute the transaction dissemination with Narwhal as a mempool and includes only hashes of mempool batches in the proposals. This would potentially achieve similar performance to BullShark. However it would come at the steep costs of maintaining two code-bases (one for the mempool and one for the consensus), higher latency (since Narwhal does a reliable broadcast which is usually the first step of a consensus protocol) and loss of quantum-safety (since they all use threshold signatures to provide Safety with lower communication complexity). Unlike these "hybrids", BullShark provides both the theoretical contribution of being the first BAB with all the good properties we already described, the practical contribution of significant latency gains in synchrony and the usability contribution of modifying only 200 LOC from the base-protocol Tusk.

DISCUSSION
On the foundational level BullShark is the first DAG-based zero overhead BFT protocol that achieves the best of both worlds of partially synchronous and asynchronous protocols. It keeps all the desired properties of DAG-Rider, including optimal amortized complexity, asynchronous liveness, and post quantum security, while also allowing a fast-path during periods of synchrony. BullShark's parties switch their voting type to fallback after every unsuccessful wave. An interesting future direction is to add an adaptive mechanism for parties to learn when is best to switch between the types. Interestingly, since the DAG provides full information, this mechanism can be also implemented without extra communication.
The partially synchronous version of BullShark is extremely simple (200 LOC) and highly efficient. In particular, it does not need any view-change or view-synchronization mechanisms since the DAG already encodes all the required information. When implemented over the Narwhal mempool it has 2 the throughput of the partially synchronous HotStuff protocol and 33% lower latency than the asynchronous Tusk protocol over Narwhal. Figure 5 illustrates the partially synchronous Bullshark protocol for = 4 and = 1. Each odd round in the DAG has a predefined leader vertex (highlighted in solid green) and the goal is to first decide which leaders to commit. Then, to totally order all the vertices in the DAG, a party goes one by one over all the committed leaders and deterministically orders their causal histories.

A PARTIALLY SYNCHRONOUS BULLSHARK ILLUSTRATION
Each vertex in an even round can contribute one vote for the previous round leader. In particular, a vertex in round r votes for the leader of round − 1 if there is an edge between them. The commit rule is simple: a leader is committed if it has at least + 1 votes. In Figure 5, L3 is committed with 3 votes, whereas L1 and L2 have less then 2 = + 1 votes and are not committed.
Due to the asynchronous nature of the network, the local views of the DAG might differ for different parties. That is, some vertices might be delivered and added to the local view of the DAG of some of the parties but not yet delivered by the others. Therefore, even though some validators have not committed L1, others might have.
To guarantee all parties commit the same leaders, Bullshark relies on quorum intersection: Since the commit rule requires + 1 votes and each vertex in the DAG has at least − edges to vertices from the previous round, it is guaranteed that if some validator commits a leader L then all future leaders will have a path to at least one vertex that voted for L, and thus will have a path to L.
Therefore: If there is no path to a leader L from a future leader, then no party committed L and it is safe to skip L.
The logic to order leaders is the following: when a leader is committed, the party checks if there is a path between leader to leader − 1. If this is the case, leader − 1 is ordered before leader and the logic is recursively restarted from − 1.
Otherwise, leader − 1 is skipped and the party checks if there is a path between to − 2. If there is a path, leader − 2 is ordered before and the logic is recursively restarted from − 2. Otherwise, leader − 2 is skipped and the process continues in the same way. The process stops when it reaches a leader that was previously ordered.
In Figure 5, leaders L1 and L2 do not have enough votes to be committed and once the party commits L3 it has to decide whether to order L1 and L2. Since there is no path from L3 to L2, L2 can be skipped. However, since there is a path between L3 and L1, L1 is ordered before L3. Now, to totally order the vertices of the DAG, the party first orders the causal history of L1 (nothing to order in this example) by some deterministic rule and then orders the causal history of L3.

B LOGICAL VS PHYSICAL DAG
As mentioned above, to provide deterministic fast path, introducing timeouts is unavoidable [21]. After implementing and evaluating two alternatives, we decided to embed the timeouts into the DAG construction as described above. Intuitively, it might look inefficient as the DAG does not advance in network speed, but as we shorty explain, it is the other way round.
The other approach we consider is a virtual consensus DAG layer on top of the physical DAG. In this case the physical level has no timeouts and is very similar to the DAG construction in DAG-Rider, which advances rounds in networks speed once 2 + 1 nodes in the current round are delivered. To encode timeouts, some of the nodes in the physical DAG have "consensus" headers indicating that they belong to the virtual level. The logic to advance consensus rounds is almost similar to the one described in Alg 2. That is, consensus nodes indicate in their consensus header to which virtual nodes they refer as parents. This virtual nodes can be in arbitrary physical DAG rounds but they are at exactly one less ( − 1) consensus round. As a result, now timeouts are only needed at the virtual level and do not interfere with the physical DAG advancement. The only difference from Alg 2 is that weak links are not required on the virtual level since the weak links on the physical level already guarantee the validity property. All in all, the physical DAG advances in network speed and the virtual DAG provides the functionality required by the BullShark consensus protocol.
We implemented and evaluated this logical DAG construction, however, the results were not encouraging (around 50% latency increase without any significant throughput benefit). After investigation we attributed this to two main reasons: • Since BullShark is built on top of Narwhal, it inherent the data dissemination decoupling from the DAG construction. That is, data is disseminated at network speed regardless of the DAG construction, which contains only metadata. Therefore, if the DAG advances rounds slower, then each vertex in the DAG simply contains more metadata and the throughput is not compromised. • The logical split between virtual and physical DAG introduces a decoupling between delays/timeouts for the consensus messages and delays for the block creation. This results to a common pattern where a physical DAG blocks is created milliseconds before a vote is ready to be cast, but the vote missed the block and needs to wait for the next round to be cast. This introduces a small delay per vote but since we need 2f+1 votes to commit a consensus round the latency of the DAG moves from the median latency to the tail-latency of the 66th percentile. • Moreover, the smaller the DAG the less resources are required to manage it. For example, less memory to store it and less bandwidth to construct it.

C PROOFS
We provide proofs of correctness for both versions of BullShark.

C.1 BullShark With Fallback
Total order. Note that at any given time parties might have slightly different local DAGs. This is because some vertices may be delivered at some parties but not yet at others. However, since we use reliable broadcast for each vertex , and wait for the entire causal history of to be added to the before we add , we get the following important observation: Observation 1. For every two honest parties and we get: • To totally order the vertices in the DAG, each party locally interprets (there is no extra communication on top of building the DAG). To this end, divides its DAG into waves of 4 rounds each. Every wave has 3 leaders that can potentially be committed: 2 steady-state leaders and one fallback leader. The steady-state leaders are two pre-defined vertices, one in the first round of the wave and the other in the third. The fallback leader is a vertex in the first round of the wave that is selected by the randomness produced in the fourth round of the wave. To make sure a fallback leader and a steady state leader are not committed in the same wave, each party can only vote for either the fallback leader or the steadystate ones. In the code, steadyVoters[w] fallbackVoters[w] contain all the parties that can vote for steady-state or fallback leaders in wave , respectively. We say that a party determines vote type to be a steady-state (fallback) in wave if its steadyVoters[ ] ( [ ]) contains . Moreover, as we show in the next claim, all parties agree on 's vote type in wave . This, in particular, means that Byzantine parties cannot equivocate or hide their vote (a nice property that we get from using reliable broadcast as a building block).
Claim 1. For every party and round , each party determines at most one vote type for in wave . Moreover if and determine vote type and ′ for in wave , respectively, then = ′ .
Proof: The first part of the claim follows from the code of function determine_party_vote_type. This function is called by a party whenever it adds a new vertex to [ ] such that is the first round of a wave, and the source of the vertex (a party ) is either added to steadyVoters[w] or fallbackVoters [w]. The second part of the claim follows from Observation 1 and the fact (by the code of try_add_to_DAG) that is added to the DAG only after all its causal history is added. This guarantees that for every wave and party try_steady_commit and try_fallback_commit are called with the same parameters and thus return the same result. This in turn guarantees that all parities that determine 's vote type in wave see the same type.
There are two possible ways to commit a leader in BullShark. The first is to directly commit it when either try_steady_commit or try_fallback_commit, called with , return true. The second option is to indirectly commit it when it is added to leaderStack in Line 116 or 119. In both cases, to commit a leader in wave , we count the number of vertices in some round (depending on the leader type and whether we directly or indirectly commit it) in that have a strong path to the leader and their vote corresponds to the leader's type. We first show that steady state and fallback leaders cannot be directly committed in the same wave.
Claim 2. If a party directly commits a steady-state leader in wave , then no party commits (directly or indirectly) a fallback leader in wave , and vice versa.
Proof: Consider a steady state leader vertex committed by a party in round in wave . By the code, to directly commit a leader vertex a party need to determine the vote type of at least 2 + 1 parties in the wave to be the same as the leaders. Similarly, to indirectly commit a vertex leader, a party needs to determine the vote type of at least + 1 parties in the wave to be the same as the leaders. Since directly commits state leader vertex in wave , it determines 2 + 1 parties as steady state voters in wave . Since there are 3 + 1 parties in total, by Claim 1, no other party determines more than parties as fallback voters in wave . Therefore, no other party commit (directly or indirectly) a fallback leader in wave . From symmetry, the same argument works in the other direction.
For the proof of the next lemmas we say that a party consecutively directly commit leader vertices and ′ if directly commits them in rounds and ′ > , respectively, and does not directly commit any leader vertex between and ′ . In the next claims we are going to show that honest parties commit the same leaders and in the same order: Claim 3. Let and ′ be two leader vertices consecutively directly committed by a party in rounds and ′ > , respectively. Let and ′ be two leader vertices consecutively directly committed by a party in rounds and ′ > , respectively. If ≤ ≤ ′ , then both and (directly or indirectly) commit the same leader in round ( ′ , ′ ).
Proof: Claim 2 implies that that there is at most one committed leader in each round. Thus, if ′ = ′ we are done. Otherwise, assume without lost of generality that ′ < ′ . Thus, if = ′ we are done. Otherwise, we need to show that indirectly commits ′ in ′ .
By the code of commit_leader, after directly commits ′ in round ′ it tries to indirectly commit leaders in round numbers smaller than ′ until it reaches round < ′ . Let ′ < < ′ , be the smallest number between ′ and ′ in which (directly or indirectly) commits a leader . Consider two cases: • Vertex ′ is a steady-state leader. Note that > ′ + 1 since only odd rounds have potential leaders. Since directly commits ′ in round ′ , there is a set of 2 + 1 vertices in [ ′ + 1] with strong paths to ′ and with ′ 's types. By observation 1, Claim 1, and quorum intersection, there are at least + 1 vertices in [ ′ + 1] with ′ 's vote type and strong paths from the to them.
• Vertex ′ is a fallback leader. By Claim 2, no leader is committed in round + 2. Thus, > ′ + 3. Since directly commits ′ in round ′ and , there is a set of 2 + 1 vertices in [ ′ 1 + 3] with strong paths to ′ and with ′ 's types. By observation 1, Claim 1, and quorum intersection, there are at least + 1 vertices in [ ′ + 3] with ′ 's vote type and strong paths from the to them. In both cases counts (in ssVotes or fbVotes) at least + 1 votes for the leader. In addition, by observation 1 and Claim 1, since in both cases there are at least 2 + 1 vertices with the 's type, there are at most vertices with the opposite type. Thus, counts at most votes for the other leader. Therefore, by Lines 115-120 in commit_leader, indirectly commits ′ .
Claim 4. Let and ′ be two leader vertices consecutively directly committed by a party in rounds and ′ > , respectively. Let and ′ be two leader vertices consecutively directly committed by a party in rounds and ′ > , respectively. Then and commits the same leaders between rounds ( , ) and ( ′ , ′ ), and in the same order.
Proof: If ′ < or ′ < , then we are trivially done because there are no rounds between ( , ) and ( ′ , ′ ). Otherwise, assume without lost of generality that ≤ ≤ ′ . By Claim 3, both and (directly or indirectly) commit the same leader in round ( ′ , ′ ). Assume without lost of generality that Thus, by Claim 2, both and commit ′ in round ′ and in round . By the code of commit_leader, after (directly or indirectly) committing a leader, parties try to indirectly commit leaders in smaller round numbers until they reach a round in which they previously directly committed a leader. Therefore both and will try to indirectly commit all leaders going down from ′ = ( ′ , ′ ) to = ( , ). Since ′ appears in both and , by Observation 1, all vertices in such that there is a path from ′ to them appear also in . The claim follows from the deterministic code of the function commit_leader.
By inductively applying Claim 4 for every pair of honest parties we get the following: Corollary C.1. Honest parties commit the same leaders and in the same order.
For the next lemma we say that the causal history of a vertex leader in the DAG is the set of all vertices such that there is a path from to them. Lemma C.2. Algorithms 1, 2, 3, and 4 satisfy Total order.
Proof: By Corollary C.1, honest parties commit the same leaders and in the same order. By the code of the order_vertices procedure, parties iterate on the committed leaders according to their order and a_deliver all vertices in their causal history by a pre-defined deterministic rule. The lemma follows by Observation 1 since all honest parties has the same casual history in their DAG for every committed leader.
). We will show that every honest party outputs it as well. By the code of order_vertices, there is a leader vertex that committed such that is in 's casual history. By Observation 1, the 's casual histories in and are the same. Thus, by code of order_vertices, we only need to show that eventually commit leader vertex . Let ′ be the leader vertex with the lowest number that is higher than . that directly commits. Let ′′ be the vertex that triggers this direct commit, i.e., the vertex ′′ that passed to the try_ordering function that calls determine_party_vote_type, which in turn commits ′ . By Observation 1, eventually add ′′ to and call try_ordering with ′′ . By Observation 1 again, the casual history of ′′ in is equivalent the casual history of ′′ in . Hence, directly commits ′ as well. Since the casual history of ′ in is also equivalent the casual history of ′ in , also commits .
By the Liveness (Agreement and Validity) properties of reliable broadcast and since it is enough for parties to deliver 2 + 1 vertices in a round in order to move to the next one, the DAG grows indefinitely: Observation 2. For every round and honest party , [ ] eventually contains a vertex for every honest party.
In the next to claims we show that for every round there is an honest party that commit a leader in a round higher than with probability 1. First, we show that if it is not the case, then starting from some point the vote type of all parties is fallback. Note that this is true also for Byzantine parties since thanks to the reliable broadcast Byzantine parties cannot lie about their casual history.
Claim 5. Consider an honest party . If there is a wave after which no honest party commits a leader, then in all waves ′ > + 1 determines the vote type of all parties that reach ′ in as fallback.
Proof: Let ′ > + 1 be a wave that start after . By the claim assumption no honest party commits a leader in wave ′ − 1. Let be the first round of wave ′ . Consider a party for which has a vertex in [ ] By the code, calls try_ordering with , which in turn calls determine_party_vote_type to determine 's vote type for ′ . By Observation 1, the casual history of in is equivalent to the casual history of in . The claim follows from the code of determine_party_vote_type. Since did not commit a leader in wave ′ , both functions try_steady_commit and try_fallback_commit return falls ' invocation of determine_party_vote_type. Therefore, sets 's vote type in ′ to fallback.
The following claim is a known property of all to all communication, which sometimes referred as common core [16]. We provide proof for completeness. Next, we use the fact that fallback leaders are hidden from adversary until the last round of a wave to prove the following: Claim 7. Consider a party and a wave such that determines the vote type of all parties that reach in as fallback. Then the probability of to commit the fallback vertex leader of is at least 2/3.

Proof:
Let be the first round of . By the assumption, the vote type of all parties with vertices in [ +3] is fallback. Therefore, by Claim 6, there are at least 2 + 1 vertices in the first round of that satisfy the fallback commit rule. That is, there is a set of 2 +1 parties such that if any of them is elected to be the fallback leader, then will commit it. Since the fallback leader is elected with the randomness produced in round + 3, the set is determined before the adversary learns the leader. Therefore, even though the adversary fully controls delivery times, the probability for the elected leader to be in is at least 2 + 1/3 + 1 > 2/3. Claim 8. For every wave , there is an honest party that with probability 1 commits a leader in a wave higher than .
Proof: Assume by a way of contradiction no honest party commits a leader in a wave higher than . By Observation 2, for every round and honest party , [ ] eventually contains at least 2 + 1 vertices. Moreover, by Claim 5, there is an honest party that determines the vote type of all parties that reach ′ > + 1 in as fallback. Therefore, by Claim 7, the probability of to commit the fallback leader in any wave ′ > + 1 is at least 2 3 . Hence, with probability 1, there is a wave higher than that commits.
We next use Claim 8 to prove Validity.
Proof: Let be an honest party that calls _ ( , ), we need to show that all honest parties output _ ( , , ) with probability 1. By the code pushes in the blockToPropose queue. By Observation 2, advanced unbounded number of rounds and thus creates unbounded number of vertices. Therefore, eventually will create a vertex with and reliably broadcast it. By the Validity property of reliably broadcast, all honest parties will eventually add it to their DAG. That is, for every honest party , there is a round number such that ∈ [ ]. By the code of cre-ate_new_vertex, every vertex that creates after is added to [ ] have a path to (either with strong links or weak links). Therefor, by Claim 8, there is an honest party that with probability 1 commits a leader vertex with a path to . Thus, by the code of order_vertices, outputs _ ( , , ) with probability 1. Since is honest, we get that by Lemma C.3 (Agreement), all honest parties output _ ( , , ) with probability 1. Integrity.

C.2 Partially Synchronous BullShark
The proof of the Integrity property is identical to the proof of Lemma C.5. For the rest of the properties, due to similarities between the protocols and to avoid argument duplication, we will follow the structure of Section C.1 and sometimes explain how to adapt claims' proofs.
To be consistent with the BullShark with fallback presentation, waves here are also consist of 4 rounds, each with a pre-defined leader in the first and fourth rounds (we could have waves of 2 rounds since we do not have the fallback leader).
Total order. Observation 1 applies in this case as well because the protocol to build the DAG is the same. Claim 1 trivially holds here since there is only one possible vote type and Claim 2 holds since there are no fallback leaders. The proofs of Claims 3 and 4 apply to Algorithm 5 as well. Therefore, Corollary C.1 applies and since we use the same order_vertices procedure in both protocols we get: Lemma C.6. Algorithms 1, 2, 3, and 5 satisfy Total order.

Agreement and Validity.
The proof of the Agreement property is identical to the proof of Lemma C.3 and Observation 2 holds since the algorithm to build the DAG is the same as in BullShark with fallback. To proof Validity for the eventually synchronous variant of BullShark we do not need Claims 5 and 8. Instead, we use the fact that GST eventually occurs. We prove the protocol under the assumption that honest parties set their timeouts to be larger than 3Δ and the following holds for the reliable broadcast building block: Property 1. Let be a time after GST. If an honest party reliably broadcasts a message at time or an honest party delivers a message at time , then all honest parties deliver it by time + Δ.
The above property is the equivalent to the reliable broadcast Validity and Agreement properties in the asynchronous model. To the best of our knowledge, it is satisfied by all reliable broadcast protocol since before delivering a message honest parties echo it to all other honest parties. Claim 9. Let be a wave such that all honest parties advances to the first round of after GST. Let 1 and 2 be their first and second pre-defined leaders of , respectively. If 1 and 2 are honest, then all honest parties commit a leader in .
Proof: let be the first round of . First we show that all honest parties advance to round + 1 within 2Δ time of each other. By Observation 2, all honest parties eventually advance to round + 1. Let party be the first honest party that advances to round +1 and denote by the time it happened. By the code of try_advance_round, | [ ]| ≥ 2 +1. By Property 1, by time +Δ | [ ] | ≥ 2 +1 for all honest parties. Therefore, by Line 55, all honest party advance to round by time + Δ. In particular, the first leader of wave , 1 . Thus, 1 broadcasts its vertex 1 in round no later than time + Δ, and by Property 1, all honest deliver it by time + 2Δ. Therefore, by Line 40 and the code of try_advance_round, all honest parties advance to round + 2 by time + 2Δ.
Next we show that all honest parties advance to round + 2 with 3Δ time of each other. Since all honest parties advance to round + 1 within 2Δ time of each other, then they start their timeouts at round + 1 within 2Δ time of each other. Let party be the first honest party that advances to round + 2. If the first honest party waits for timeout (the if in Line 46) to advance to round + 2, then all honest parties advance to round + 2 within 2Δ. Otherwise, has 2 + 1 vertices in [ + 1] with strong path to ′ . By property 1, all other honest parties will deliver this vertices and advance to round + 2 within 3Δ from .
By the assumption, the second leader of the wave, 2 , is honest and will broadcast vertex 2 in round + 2 at most 3Δ after the first honest party advances to + 2. Since the timeouts are larger than 4Δ, all honest will advance to round + 3 within Δ of each other (by Line 42, all honest wait to deliver the leader's vertex or for a timeout). Moreover, they will all add a strong edge to 2 in their vertex in round + 3.
Since all honest advance to round + 3 within Δ of each other and the timeouts are larger than 2Δ, they will all wait for each other's vertices before advancing to the next round. Therefore, all honest will get 2 + 1 vertices in round + 3 with strong paths to the second vertex leader of the wave 2 . Thus, all honest commit a leader in wave .
The Validity property is proved under the assumption that eventually (after GST) there will be a wave in which both leaders are honest. For example, this assumption holds for every full permutation of the parties or if we maintain a fixed leader for the full wave. To avoid repetition, we omit the proof of the following lemma as it is similar to the proof of Lemma C.4. All we need to do to adapt it is to remove all appearances of "with probability 1" and replace the reference to Claim 8 with Claim 9.