DAG It Off: Latency Prefers No Common Coins

The paper is structured as follows. Section 1 briefly describes the paper. Section 2 details the state of the art of DAG-based protocols. Section 3 sets the notation and key concepts used in the paper. Section 4 describes Black Marlin in full detail. Section 5 shows that Black Marlin implements atomic broadcast and studies its complexities. Section 6 describes a comparison of the throughput and latency of Black Marlin and Bullshark.

We consider a set $𝒩=\{0,\mathrm{\dots },n-1\}$ of $n$ parties running a round-based algorithm. In each round, these parties create blocks that form the vertices of a directed acyclic graph $(\text{DAG},ℛ)$ with references that constitute the edges. Edge $(B_1,B_2)\in ℛ$ if $B_1$ includes a reference to $B_2$. A block $B=[r,i,\text{refs},{\text{refs}}^{\prime }]$ is a tuple formed by a round number $r$, an identifier for party $i$, a set of strong references refs, and a set of weak references ${\text{refs}}^{\prime }$. For simplicity, we omit the set of transactions and the signature from the block, as these transactions play no role in the consensus mechanism. Given a block $B$, $\text{creator}(B)$ denotes the party that created $B$, $\text{round}(B)$ denotes the round in which $B$ was created. The variable $\text{DAG}(r)$ denotes the set of block $B^{\prime }\in \text{DAG}$ such that $\text{round}(B^{\prime })=r$. A party selected by a round-robin mechanism is referred to as anchor, blocks produced by the anchor party are referred to as anchor blocks.

We model parties as interactive Turing machines (ITM). An interactive Turing machine is a Turing machine with an input and an output tape that allows the Turing machine to communicate with other Turing machines and make decisions based on the content of their input tape. The adversary is modeled as another ITM that corrupts up to $f$ parties at the beginning of the execution, the actual number of corruptions is denoted by . These corrupted parties obey the adversary; i.e., they may diverge from the execution of the protocol. Corrupted parties are often referred to as Byzantine and non-corrupted as honest.

We assume a partial synchronous communication model [13] on point-to-point links. The network begins in an asynchronous state and turns synchronous after a global stabilization time (GST). After this point, every message sent is delivered with a delay of up to $\mathrm{\Delta }$. The adversary not only decides the global stabilization time but also when the message is made available to the party within the $\mathrm{\Delta }$ time limit. We also assume that the local computations are instantaneous, this assumption can easily be relaxed by factoring the computation of the honest parties in the network delay. We assume the existence of a public key infrastructure. We also assume that every block and a message produced by every party is signed, and that the signature scheme is secure.

We model our protocol as atomic broadcast. Our atomic broadcast primitive is accessed with the events $\text{ab-broadcast}(B,i,r)$ and outputs events $\text{ab-deliver}(B,j,r)$. The event $\text{ab-broadcast}(B,i,r)$ can only be triggered by party $i$, but $\text{ab-deliver}(B,j,r)$ may be output by every party.

Note that our definition of atomic broadcast is adapted to the partial synchrony model; the validity property applies to blocks that are broadcast after the network becomes synchronous. However, the safety properties are satisfied during both synchrony and asynchrony.

A block from round $r\ne 1$ and creator $j$ is valid if it is signed by party $j$ and contains references to valid blocks created by at least $n-f$ parties from round $r-1$. Since blocks in round $r=1$ do not reference any previous blocks, a block is valid if it has been signed by its creator. A history $\mathscr{H}$ is valid if all the blocks contained in it are also valid.

When receiving a message $[\text{block},B^{\prime },{\mathscr{H}}^{\prime },j,r^{\prime }]$ (L57), party $i$ checks the validity of both the block $B^{\prime }$ and the history ${\mathscr{H}}^{\prime }$, and adds the block $B^{\prime }$ along with every unknown block from the history ${\mathscr{H}}^{\prime }$ to its local view (DAG). Party $i$ also updates party $j$’s local history (L60), used solely to optimize message complexity by sending only strictly necessary blocks.

The first round of the protocol differs from the rest as there are no blocks from earlier rounds. Party $i$ creates a block with an empty set of references and invokes the event $\text{ab-broadcast}(B,i)$ before sending the message $[\text{block},B,\{\},i,0]$ to every party and starting a timeout with time $2\mathrm{\Delta }$. Party $i$ then moves to the next round, a standard round.

Every round beyond the first shares the same structure. Consider an honest party $i$ in round $r$, i.e., it has just produced a block corresponding to round $r$. Party $i$ waits to receive messages $[\text{block},B,\mathscr{H},j,r^{\prime }]$ from at least $n-f$ different parties for some round $r^{\prime }\ge r$. Once sufficient messages for such a round have been received, party $i$ checks whether it has received a message $[\text{block},B^{\prime },{\mathscr{H}}^{\prime },j,r^{\prime }]$ with $j$ being the anchor for the current round, and verifies that the previous two anchors have enough support, or if a timeout has been triggered, to conclude the round. This dual condition to start a new round allows the protocol to be responsive, i.e., it runs at the speed of the actual network delay instead of the estimated network delay $\mathrm{\Delta }$ without deadlocking when an anchor party behaves maliciously.

Party $i$ concludes the round by performing the following sequential operations. First, $i$ attempts the delivery of blocks (L42); this function is described in its own paragraph below. Secondly, party $i$ creates a new block $B$ corresponding to the next round $r^{\prime }+1$, including strong references refs to every block in $\text{DAG}(r^{\prime })$ (L43–50). A set of weak references ${\text{refs}}^{\prime }$ to blocks from previous rounds are also included; this secondary set is time-bounded, preventing the usual garbage collection problem associated with these solutions. Party $i$ concludes these operations by sending $B$ to every other party, together with the history of the parties (L54). Note that party $i$ may skip one or multiple rounds if an appropriate quorum is received.

The delivery function determines which blocks are delivered and in what order, based on the local view of the DAG. Upon concluding round $r$, party $i$ attempts the commitment of the anchor block $B$ from round $r-2$ (L14–17). $B$ is an anchor block if its creator has been elected by the round-robin mechanism. However, it is only committed if it is supported by at least $n-f$ parties in round $r-1$ and including an anchor of round $r-1$ $B^{\prime }$, and $B^{\prime }$ is also supported by at least $n-f$ parties in round $r$. These conditions prevent honest parties from committing different blocks when the anchor party is Byzantine.

If this check succeeds, party $i$ calls the function $\text{commit}(B)$ (L18–32), which iterates through the local view of the DAG. Party $i$ searches for a non-delivered block $B^{\prime }$ from a higher round reachable through strong references from $B$. If such a block $B^{\prime }$ exists, the function $\text{commit}(B^{\prime })$ is called recursively. If no such block exists, party $i$ deterministically orders the blocks in $\text{past}(B)$ before invoking ab-deliver on them. In case of conflicting blocks from the same party and round, only the first block – determined by the deterministic ordering above – is ab-delivered. Figure 2 shows an example of the commitment rule.

Black Marlin (Algorithm 2) uses special functions as described in the paragraphs above. For the sake of the reader, we summarize the functions together in this section.

Given a block $B$, the function $\text{creator}(B)$ returns the party that created and signed $B$, and the function $\text{round}(B)$ returns the round in which $B$ was created. The validity predicate $V(B)$ returns $1$ if $B$ has at least $n-f$ blocks from different parties and no two blocks from the same party corresponding to $\text{round}(B)-1$ in its references, and $B$ has been signed by its creator. When invoked with a set of blocks $\mathscr{H}$, the validity predicate $V(\mathscr{H})$ returns $1$ if every block $B^{\prime }\in \mathscr{H}$ satisfies $V(B^{\prime })$. The function $\text{past}(B)$ returns the set of blocks reachable from $B$ through strong and weak links, and the function $\text{strong}(B)$ returns the set of blocks reachable from $B$ through strong links, $B$ is not part of the output of either function. The function $\text{supp}(B)$ counts the number of parties $i$ that created a block $B_i$ in round $\text{round}(B)+1$ such that $B\in \text{strong}(B_i)$ and no other block from the same creator and round is in $\text{strong}(B_i)$. The function $H(B)$ is a collision-resistant hash function. The operation $\text{setTimeout}(r,\rho )$ starts a timeout of duration $\rho$ corresponding to round $r$, whereas $\text{timeout}(r)$ triggers when the timeout is completed and $\text{clearTimeout}(r)$ removes any active timeout corresponding to round $r$. The function $\text{time}()$ returns the local time of the party and when input with a round $r$, $\text{time}(r)$ returns the local time when the party adopted round $r$. In the case that the party never adopted round $r$, $\text{time}(r)$ returns the time when the party adopted the smallest round $r^{\prime }>r$. The function $\text{RR}(r)$ takes a round as an input and returns the party by the round-robin mechanism in round $r$, a block from this party is also referred to as anchor. In case multiple blocks exist, e.g. due to Byzantine behavior, the function returns both blocks. The variable $\text{DAG}(r)$ returns the set of blocks from round $r$ in the local view of the party. The operation $\text{maxAnchor}(𝒜)$ takes a set of blocks $𝒜$ as an input and returns the anchor from the highest round. Given a round $r$, the function $\text{quorum}(r)$ returns 1 if there are blocks from at least $n-f$ parties in $\text{DAG}(r)$. The function $\text{anchor}(r)$ returns 1 if there is a block created by the anchor of $r$ in $\text{DAG}(r)$, and $\text{suppAnchor}(r)$ returns 1 if there is an anchor block in $r$ that is supported by at least $n-f$ parties in $\text{DAG}(r+1)$.

The results in this section apply to every block, even during the asynchronous phase.

Liveness is guaranteed only after the global stabilization time. For this reason, the majority of the results presented here apply only to blocks that are ab-broadcast after time GST.

Previous lemmas are sufficient to show that Black Marlin implements atomic broadcast.

Previously, we showed that Algorithm 2 is both safe and live in a partial synchronous network. In particular, we demonstrated that blocks are eventually delivered, avoiding any concrete analysis of the communication and time complexity of the algorithm.

We conducted all benchmarks locally on a MacBook Pro equipped with an M1 Pro chip, 16 GB of RAM, 10 cores (8 performance and 2 efficiency), and running macOS Sequoia Version 15.0.1. To ensure a fair comparison, we modified the benchmarking framework developed for Bullshark [26, 21]²²2Bullshark has been chosen over more recent frameworks such as Mysticeti [18] due to its closer similarity to Black Marlin and the timing of this project. to incorporate our implementation of Black Marlin. The biggest difference between Black Marlin and Bullshark is the use of common coins by Bullshark. However, their implementation also uses round-robin³³3https://github.com/facebookresearch/narwhal/blob/bullshark/consensus/src/lib.rs L202.. This approach allows a close performance comparison between Black Marlin and Bullshark and also demonstrates that Bullshark’s preprocessing techniques can be adapted to Black Marlin. Note that the actual performance of Bullshark is worse due to the lack of common coins in the implementation.

To emulate realistic network conditions despite running benchmarks on a single machine, we modified both the Black Marlin and Bullshark implementations to introduce configurable network delays. Specifically, messages are delivered based on a Poisson distribution with the expected value $\mathrm{\Delta }/2$, where $\mathrm{\Delta }$ represents the maximum network delay assumed by the protocol. This design ensures that with high probability, the actual message delay remains below $\mathrm{\Delta }$. For instance, when $\mathrm{\Delta }=400$ ms, the average delivery time for a message is 200 ms.

For each experimental run, we measure throughput as the total number of transactions delivered divided by the total duration of the run. The latency of a transaction tx is defined as the time elapsed from the creation of the block containing tx until it is ab-delivered. The latency for a run is the average latency of all ab-delivered transactions in the run. Every party behaves honestly during the benchmarking.

Each data point in Figure 3 represents the average throughput or latency over 10 independent runs, each lasting 60 seconds. Error bars indicate two standard deviations. We report results across varying numbers of parties (4, 10, and 13) and network delays ($\mathrm{\Delta }=200$, 400, 600, 800, and 1000 ms). All other parameters remained constant throughout the experiments: one worker per party, a transaction size of 512 bytes, and a transaction injection rate of 50,000 transactions per second.

The results of the experiments described above are summarized in Figure 3, Black Marlin is represented by blue tones and Bullshark by red ones. The two figures of merit that we consider are throughput and latency.

Black Marlin consistently achieves lower latency than Bullshark across all configurations. The latency improvement ranges from a factor of 2 to 3, depending on the network delay. For example, with 10 parties and a network delay of $\mathrm{\Delta }=200$ ms, Black Marlin achieves a latency of $696\pm 5$ ms, compared to $1800\pm 54$ ms for Bullshark. At $\mathrm{\Delta }=1000$ ms, Black Marlin’s latency is $3226\pm 55$ ms, while Bullshark’s latency increases to $7773\pm 360$ ms. This improvement is expected: Black Marlin eliminates the need for reliable broadcast, reducing latency by approximately a factor of 2. Additionally, its more frequent anchor selection contributes to a constant-factor latency reduction, further widening the latency gap.

Black Marlin also achieves consistently higher throughput than Bullshark across all network delay scenarios. In contrast to the more pronounced latency gains, the throughput improvement is by a constant margin. This behavior can be explained by the way Bullshark constructs blocks: a party running Bullshark accumulates batches of transactions from workers until it is ready to broadcast a new block. As network delay increases, blocks become larger, which helps mitigate throughput loss. Therefore, the $\sim 2\times$ latency improvement observed with Black Marlin does not directly translate into an equivalent gain in throughput – unless the number of workers or the network delay is significantly increased. However, these adjustments were beyond the scope of this study. We were unable to increase the number of workers due to hardware limitations, and we excluded network delays greater than 1 second, as such conditions are considered unrealistic. This block size phenomenon also explains the erratic throughput results observed for Bullshark under configurations with 4 parties and low network delays. In these cases, small block sizes limited Bullshark’s throughput.

Figure 3 also demonstrates that Black Marlin’s garbage collection mechanism is robust to overestimations of the actual network delay. Specifically, a constant-factor overestimation leads to only a constant increase in the number of rounds that parties must retain in memory. This implies that even for arbitrarily long executions, Black Marlin only requires $𝒪(n)$ memory, provided the network delay is overestimated by a constant factor.

Overall, Black Marlin outperforms Bullshark in our implementation, which uses the same codebase and experimental conditions for both protocols. Unfortunately, source code for more recent DAG-based protocols is not publicly available, preventing a direct empirical comparison. However, as we demonstrate in Section 5.4, Black Marlin also surpasses these protocols at a theoretical level in terms of communication and latency complexities while allowing implementations with $𝒪(n)$ memory.