# Shoal++: High Throughput DAG BFT Can Be Fast!

Balaji Arun  Aptos Labs ,  Zekun Li  Aptos Labs ,  Florian Suri-Payer  Cornell
University ,  Sourav Das  UIUC and  Alexander Spiegelman  Aptos Labs

###### Abstract.

Today’s practical partially synchronous Byzantine Fault Tolerant (BFT)
consensus protocols trade off low latency and high throughput. On the one end,
traditional BFT protocols such as PBFT and its derivatives optimize for
latency. They require, in fault-free executions, only 3 message exchanges to
commit, the optimum for BFT consensus. However, this class of protocols
typically relies on a single leader, hampering throughput scalability. On the
other end, a new class of so-called DAG-BFT protocols demonstrates how to
achieve highly scalable throughput by separating data dissemination from
consensus, and using every replica as proposer. Unfortunately, existing DAG-
BFT protocols pay a steep latency premium, requiring on average 10.5 message
exchanges to commit a transactions.

This work aims to soften this tension, and proposes Shoal++, a novel DAG-based
BFT consensus system that offers the throughput of DAGs while reducing commit
latency to an average of 4.5 message exchanges. Our empirical findings are
encouraging, showing that Shoal++ achieves throughput comparable to state-of-
the-art DAG BFT solutions while reducing latency by up to 60%.

††submissionid: 688††copyright: none

##  1\. Introduction

This paper presents Shoal++, a novel partially synchronous DAG-based Byzantine
Fault Tolerant (BFT) consensus protocol that matches the throughput of
contemporary DAG-BFT protocols while significantly reducing latency, closing
the gap with the theoretical optimum.

BFT consensus offers the attractive abstraction of a single, always available
server, that remains correct even as a subset of replicas may fail
arbitrarily. Fueled by recent advances to simplicity and practicality (Castro
and Liskov, 2002; Yin et al., 2019; Danezis et al., 2022; Spiegelman et al.,
2022a), interest and adoption of BFT protocols is skyrocketing: it is at the
core of aspiring multi-national projects such as the digital Euro (dig, [n.
d.]), confidential data sharing frameworks (ccf, [n. d.]) and the growing Web3
industry. Already today, numerous blockchain companies (Team, 2022, 2019,
2020, 2023) are actively deploying BFT protocols (Spiegelman et al., 2022a,
2023; Chen and Micali, 2019; Rocket, [n. d.]; Gelashvili et al., 2022),
supporting millions of daily worldwide users.

Following the seminal PBFT (Castro and Liskov, 2002) protocol, most
traditional BFT consensus protocols (Yin et al., 2019; Kotla et al., 2007;
Gueta et al., 2019) operate in a primary-backup like regime in which a single,
dedicated leader replica proposes an ordering of commands, and follower
replicas vote to ensure consistency and durability.

As demonstrated by PBFT, this approach can enjoy excellent latency in fault-
free executions, requiring only three message exchanges (henceforth message
delays, or md) to order a leader’s proposal, the optimum achievable for BFT
protocols. A dedicated leader, however, poses not only a single point of
failure, but constrains the achievable throughput to the processing and
networking bandwidth available to a single server. To improve scalability, and
meet the high throughput demands of modern applications, recent proposals
emphasize maximizing resource utilization and balancing load across all
replicas.

Initial approaches propose multi-log frameworks (Stathakopoulou et al., 2019)
that partition the request space, and operate multiple consensus instances in
parallel (each led by a different replica) whose logs are carefully
intertwined. More recent designs take scalability a notch further by entirely
separating data dissemination and consensus. Pioneered by Aleph (Gagol et al.,
2019) and DAG-Rider (Keidar et al., 2021), and made practical by Narwahl
(Danezis et al., 2022) a new class of so-called DAG-BFT protocols have risen
to popularity.

DAG-BFT protocols employ a structured, highly parallel, asynchronously
responsive data dissemination layer as a backbone, and layer consensus atop.
Data dissemination proceeds through a series of rounds in which each replica
proposes new transaction batches via reliable broadcast (RB); each proposal
(DAG node) references a subset of preceding proposals (DAG edges), resulting
in a Directed Acyclic Graph (DAG) of temporally (or causally) ordered
proposals. The consensus layer reaches agreement on prefixes of the DAG, and
derives an ordering for all causally referenced proposals.

State-of-the-art DAG protocols (Spiegelman et al., 2022a, 2023) avoid running
an explicit consensus protocol, and instead embed the consensus process onto
the DAG directly: they ensure that all replicas converge on the same view of
the DAG, and interpret it’s structure locally to implicitly determine
commitment. Consensus simulates leaders by assigning pre-determined ”fixpoint”
nodes in the DAG (henceforth anchors) and confirms agreement of an anchor by
waiting until it has gathered sufficient references in future DAG rounds that
guarantee its durability.

Upon committing an anchor node, all of its causally referenced proposals are
implicitly committed and ordered. Such design is appealingly simple – it
requires no additional communication for consensus and avoids the notoriously
complex view change logic inherent to traditional BFT protocols. It is also
very resource efficient – each replica acts as a proposer, thus allowing high
throughput with a large number of replicas. As a result, DAG-BFT has prompted
swift adoption by several large blockchain systems (Team, 2023, 2022).

However, despite their desirable features, today’s DAG protocols fall short in
terms of latency. They require several rounds, each consisting of a RB, in
order to commit a transaction. Bullshark (Spiegelman et al., 2022a) for
instance requires, even in fault-free cases, up to 4 rounds to commit a
proposal (12md in expectation, §3.2) ; recent advances made by Shoal
(Spiegelman et al., 2023) reduce it to 3 rounds (10.5md expected, §3.2). A far
cry from the 3md possible by traditional BFT protocols!

This work argues that these latency shortcomings is not fundamental to DAG
based BFT, and proposes a new DAG-based BFT system Shoal++ that reduces the
latency gap close to the optimum.

We begin by analyzing sources of end-to-end (e2e) transaction latency in DAG
protocols (§3.2); at a high level, it can be broken down into three stages.
(i) DAG proposals happen only at regular intervals (rounds), and transactions
that narrowly miss inclusion (e.g. arrive just after a batch is formed) must
wait for the next round. We refer to the time a transaction must wait to be
included in a DAG proposal as Queuing Latency. (ii) In order to be committed,
a proposed DAG node must be referenced by a committed anchor. Unfortunately,
in existing DAG protocols (Spiegelman et al., 2022a, 2023), at most one anchor
is scheduled per round111Bullshark (Spiegelman et al., 2022a) schedules an
anchor every second round; Shoal (Spiegelman et al., 2023) improves it to
every round. This results in additional Anchoring latency, the time until a
node is referenced by the next committed anchor. (iii) Finally, in existing
DAG protocols, an anchor requires at least 2 more DAG rounds to be committed;
we refer to this as Anchor Commit Latency.

##### Key ideas.

To reduce end-to-end latency, Shoal++ employs three techniques, respectively
addressing each latency stage. First, Shoal++ identifies and optimizes an
inefficiency in the existing Bullshark commit rule to reduce common case
Anchor Commit Latency to only 4md. Next, we configure Shoal++ to dynamically
attempt to make every node an anchor, thus eliminating Anchoring Latency.
Shoal++ builds on Shoal’s idea to dynamically re-interpret the anchor
assignment at each commit, and introduces small timeouts to help replicas
advance rounds in lock-step to ensure that future rounds sufficiently
reference anchor candidates. Finally, to minimize Queuing latencies, Shoal++
orchestrates multiple staggered DAG instantiations in parallel, and
intertwines their resulting logs; this allows transactions that miss inclusion
to simply board the new round of the next, staggered DAG.

Put together, these techniques allow Shoal++ to reduce expected end-to-end
latency to only 4.5md, shaving off 6md compared to Shoal, the state of the art
DAG-BFT.

We’ve implemented a prototype of Shoal++ and evaluated it empirically against
two popular DAG-BFT protocols (Bullshark (Spiegelman et al., 2022a) and Shoal
(Spiegelman et al., 2023)), a concurrent DAG-BFT protocol (Mysticeti (Babel et
al., 2023)), and a traditional BFT protocols (Jolteon (Gelashvili et al.,
2022)). Our results are promising, demonstrating matching throughput of
existing DAG BFT solutions while reducing latency by up to 40% over Mysticeti
and by up to 60% over Bullshark.

##  2\. Model

We adopt standard BFT assumptions (Castro and Liskov, 2002; Yin et al., 2019).
We refer to participants that follow the protocol as correct, and those that
deviate as faulty (or Byzantine). There are a total of $n=3f+1$ replicas, of
which at most $f$ may be faulty at any time. We make no assumptions on the
number of faulty clients. We assume the presence of a strong, yet static
adversary that may arbitrarily delay messages and coordinate all faulty
particpiants, but may not break standard cryptographic primitives such as
signatures. We denote signed messages using $\langle m\rangle\sigma$. We
assume that all signatures and Quorums are validated, and henceforth omit
explicit mention.

The goal of BFT consensus is to establish a common totally ordered log across
all correct replicas. We operate under the partially synchronous model (Dwork
et al., 1988). The system is safe at all times – no two correct replicas ever
disagree on a committed prefix of the log. Liveness is not guaranteed during
periods of asynchrony, but eventually there arrives a Global Stabilization
Time (GST) after which the network (temporarily) behaves synchronously, and
progress is guaranteed.

##  3\. Dissecting DAG-BFT

Before we present Shoal++, we provide some brief background on the core
mechanisms of DAG-BFT, and analyze the latency breakdown of existing
protocols. We focus implicitly on certified DAG protocols derived from
Narwahl(Danezis et al., 2022). While some recent works propose also
uncertified DAGs in an effort to save latency, this comes at a reduced
robustness and introduces new sources of unwanted latency (§3.2).

###  3.1. DAG core

At the core of DAG-BFT is the round-based, certified DAG structure proposed in
Narwahl (Danezis et al., 2022). Replicas proceed through a series of
structured rounds, in which replicas continuously propose new batches of
transactions. Each replica maintains their own local view of a DAG.

A replica adds another replica’s proposal as node in its local DAG once the
proposal is certified. Proposals in round $r$ must reference $n-f$ certified
proposals from round $r-1$ to be considered valid candidates, and each replica
may certify at most one candidate per round. To certify a proposal for round a
replica follows a simple Reliable Broadcast procedure.

  1. (1)

It broadcasts a signed proposal $P\coloneqq\langle r,B,edges\rangle_{\sigma}$
for round $r$ containing (i) a batch $B$ of transactions, and (ii) $n-f$
unique proposal certificates from round $r-1$ (edges for short).

  2. (2)

Upon receiving a valid proposal, a replica checks whether it has already
received a different proposal from the same author for round $r$. If it has,
it ignores the proposal; if it has not, it casts a signed vote
$S\coloneqq\langle r,d=hash(P)\rangle\sigma$ back to the proposing replica.

  3. (3)

A replica waits for $n-f$ matching signatures for its proposal $P$ and
aggregates them into a certificate $C\coloneqq\langle r,d,\\{S\\}\rangle$ that
it broadcasts to all replicas.

  4. (4)

Upon receiving a proposal certificate a replica adds a node to its local DAG.

Figure 1 illustrates a DAG of certified nodes as it appears in a local view of
one of the validators. We note that, because proposals are certified, no
replicas can produce two conflicting nodes for the same (round, replica)
position. All replicas thus eventually converge on the same local view of the
DAG.

Figure 1. Narwhal’s round-based DAG from a validator’s local point of view.
All nodes are certified.

####  3.1.1. Consensus core.

By itself, the DAG is no more than a scalable and robust mempool. It continues
to grow at the pace of the network (i.e. responsively), and, by virtue of
being certified, ensures that all disseminated transaction batches are
reliably available. A second consensus layer is needed to establish agreement.
It can either be modularly layered by running an external consensus blackbox
that commits views of the DAG (e.g. Narwhal+Hotstuff (Danezis et al., 2022)),
or logically embedded into the existing DAG messages without the need for
additional messages (e.g. Tusk (Danezis et al., 2022), Bullshark (Spiegelman
et al., 2022a), or Shoal (Spiegelman et al., 2023)). In the following we focus
solely on embedded DAG-BFT protocols as they are more efficient.

##### Embedded consensus.

At a high level, consensus is projected onto the DAG structure by designating
specific DAG nodes as fixpoints (henceforth anchors) that simulate a leader,
and interpreting DAG edges as votes for a leader. Upon committing an anchor,
all of its causal history can be implicitly committed as well; an ordering can
be derived using any deterministic function, e.g. using a topological sort.

Anchor nodes are deterministically chosen in advance (much like leaders in
traditional BFT protocols) and placed at regular intervals. Bullshark
(Spiegelman et al., 2022a), for instance, uses a round-robin scheme to select
anchor candidates, and places one anchor candidate at every other round of the
DAG. Figure 2 illustrates the anchor commit logic in Bullshark.

Figure 2. Bullshark Commit example. Replica 4 observes two ($f+1$) votes for
anchor A1, and thus directly commits it. Replica 1 observes only one ($<f+1$)
vote, and thus cannot directly commit A1. Upon committing A2, however, it
observes that A1 is present in its causal history and indirectly commits A1,
before ordering A2.

An anchor in round $r$ becomes committed as soon as $f+1$ nodes in a round
$r^{\prime}>r$ link to it (Direct Commit Rule). The safety intuition is
straightforward: (i) all nodes are certified, and thus every anchor is
equivocation-free, and (ii) all nodes in rounds $r^{\prime\prime}>r^{\prime}$
must include an edge to at least one of the nodes that link to the anchor, and
thus the anchor is durable.

In particular, every future committed anchor must link to all previously
committed anchors, thereby establishing a consistent total order amongst
anchors. Upon committing an anchor, a replica recursively traverses the
anchor’s causal history, and first commits all preceding anchors (Indirect
Commit Rule). Conversely, if an anchor candidate is not in a committed anchors
causal history, then it could never have committed, and it is safe to skip it.
Intuitively, the Indirect Commit Rule ensures that, even if a replica does not
invoke the Direct Commit rule on some anchors (e.g. because its local DAG view
is temporarily out of sync), all correct replicas will agree on the same
sequence of committed anchors.

We note that while this design is always safe, it relies on conservative
timeouts to ensure liveness (similarly to traditional BFT protocols). Since
nodes include only $2f+1$ edges, anchor candidates are not guaranteed to
receive the $f+1$ links required to commit. In the worst-case, candidates are
repeatedly skipped, thus stalling commit progress.

To reduce the expected latency, Shoal (Spiegelman et al., 2023) optimizes
Bullshark in two ways. First, it leverages the deterministic anchor commit
sequence to dynamically re-interpret the anchor schedule upon every commit.
Rather than placing anchors every other round, this allows it to place an
anchor every round. Second, it introduces an anchor reputation scheme to
attempt to select as candidates only the fastest, and best-connected replicas;
such candidates are more likely to be included as edges. This allows Shoal to
avoid timeouts in all but extremely unlikely scenarios.

###  3.2. Latency breakdown

While the design of embedded DAG-BFT protocols is appealingly simple, existing
protocols pay a high latency premium. In the following, we breakdown different
sources of latencies present in DAG-protocols, and analyze their respective
costs in Bullshark and Shoal.

We denote as the e2e commit latency of a transaction the time between a
replica first receives the transaction, and the time that the transaction is
ordered. We separate the e2e commit latency of certified DAG-BFT protocols
into three components:

  1. (1)

Queuing latency: the time it takes for a transaction to be proposed.

  2. (2)

Anchoring latency: the time it takes for a non-anchor node’s proposal to be
”picked up” by an eventually committing anchor.

  3. (3)

Anchor Commit latency: the time it takes to commit an anchor proposal.

##### Queuing Latency.

The DAG advances in a series of synchronized rounds, and each replica may
issue at most one proposal (containing a batch of transactions) per round.
Each round requires a Reliable Broadcast to certify a proposal, for a total of
3md. Consequently, a transaction that narrowly misses inclusion in the current
round proposal must, in the worst-case wait up to 3md before being broadcast;
assuming transactions arrive at a uniform rate, the average Queuing Latency is
1.5md.

##### Anchoring latency.

A proposal becomes ”anchored” once it is referenced by an eventually
committing anchor. Anchoring latency depends on two factors: (i) the frequency
of anchor candidates, and (ii) the reliability with which said anchor
candidates are committed (i.e. not skipped).222The proposals of non-anchor
candidates are subject to both factors; the proposals of anchors candidates
themselves, trivially, are subject only to the latter. Bullshark has anchor
candidates in every odd numbered round (only every second round).
Consequently, the best-case inclusion latency of non-anchor proposals in even
rounds is 1 round (3md), and 2 rounds (6md) in odd rounds; a best-case average
of 4.5md. Shoal increases candidate frequency to every round, and thus
improves the inclusion latency of non-anchor proposals to one round for all
(3md). The practical reliability of commitment cannot be easily quantified by
pen-and-paper, and is best left to empiric analysis as it depends on network
configuration and message delivery patterns. Shoal demonstrates that the use
of a reputation can aid significantly in ensuring that anchor candidates are
reliably included (Spiegelman et al., 2023).

##### Anchor Commit latency.

In both Bullshark and Shoal, an anchor becomes committed upon either (i) being
references by $f+1$ nodes in the next round (Direct Commit Rule), (ii) or
being subsumed in the causal history of future committed anchor (Indirect
Commit Rule). The Direct Commit Rule requires at least 2 rounds: one to
certify the anchor proposal, and one to certify $f+1$ proposals that reference
it, for a total of at least 6md. The latency of indirectly committed anchors
can be broken down into their own Anchoring Latency to a future anchor, plus
the future anchors Commit Latency.

Putting all latency stages together results in a best case average latency of
12md (1.5md + 4.5md + 6md) for Bullshark, and 10.5 for Shoal (1.5md + 3md +
6md).

##### A note on un-certified DAGs.

A class of recent DAG-based designs (Keidar et al., 2022; Babel et al., 2023;
Malkhi et al., 2023) proposes to replace nodes with un-certified proposals
that are disseminated with best-effort. At first glance, such design holds
promise by reducing latencies across the stack. However, removing certificates
makes the DAG brittle, and can introduce a significant amount of unwanted
synchronization on the critical path, and increase subsceptibility to timeout
violations (Giridharan et al., 2024). Edges to uncertified, yet locally
unavailable proposals must be validated by fetching missing data before
advancing to avoid losing liveness in the face of Byzantine fabrications or
unstable networks. In practice, such fetching can results in an additional 2md
that may be necessary in each round; resulting, in sum, in latencies no better
than in existing certified DAGs. In contrast, Shoal++ aims to demonstrates
that certification is not the root-cause of high latencies, and that latency
can be significantly reduced without sacrificing robustness.

##  4\. Shoal++ Overview

Shoal++ strives to reduce latency across each of the three latency stages; it
employs three different ideas that respectively address Queuing, Anchoring,
and Anchor Commit Latency. Together, Shoal++ is able to reduce total e2e
expected latency close to an average of 4.5md. We briefly outline each idea in
sequence.

##### Faster anchors!

The first observation Shoal++ makes is that the Bullshark Direct Commit rule
can be optimized when anchors are referenced by a supermajority of uncertified
nodes. Intuitively, a replica may eagerly commit an anchor as soon as $2f+1$
proposals that link to an anchor node are observed, as this implicitly
guarantees that eventually the Direct Commit Rule is satisfied. Since this is
an even stricter condition that may not be fulfilled, Shoal++ (i) retains the
existing Direct Commit Rule as backup, and (ii) leverages Shoal’s reputation
mechanism to reliably trigger the Fast Direct Commit Rule. This allows
Shoal++, in practice, to reduce Anchor Commit latency to 4md.

##### More anchors!

Next, Shoal++ takes Shoal’s idea of increased anchor frequency one step
further, and tries to turn as many nodes into anchors as possible. Doing so
requires striking balance. On the one hand, increasing the number of anchors
increases the opportunities for anchoring latency that we can avoid. On the
other hand, it introduces also opportunity for more uncommitted anchors, which
can stall progress. Adopting the reputation scheme proposed by Shoal can help
identify a reliable subset of candidates, but is not enough to streamline
progress in practice. Shoal++ (i) slows down round advancement to put the DAG
into lockstep and avoid missed anchors, and (ii) dynamically re-interprets the
tentative anchor schedule to skip anchors that are no longer needed.

##### More DAGs!

Finally, Shoal++ minimized Queuing latency by operating not one, but multiple
DAGs in parallel. DAGs are staggered using a small offset, allowing waiting
transactions that miss a round to quickly be included in the next DAG. This
simultaneously improves throughput via better resource utilization: proposals
are sent more frequently, batches are smaller and can be sent and processed
more efficiently (in a streaming fashion) than less frequent, large batches.

##  5\. Shoal++ In-Depth

We now describe the full Shoal++ system in detail.

Shoal++ uses as starting points the DAG-core of Narwahl (Danezis et al.,
2022), and Consensus-core of Bullshark (Spiegelman et al., 2022a) outlined in
§3. For the sake of brevity, we do not duplicate the pseudocode that is
available in previous works and, in particular, omit a detailed description of
the DAG construction (i.e., node broadcasts, transaction submission, node
fetching, garbage collection, and so on). We defer to the original papers for
an in-depth discussion and correctness proofs.

Algorithm 1 summarizes the DAG API and node structure. We abstract away the
node certification process, and the commit logic. Process_node and
Process_certified_node respectively involve checking that a node proposal is
valid and voting for it, and adding a new confirmed node to the DAG, prompting
invocation of commit rules. Run_bullshark performs an instance of the
Bullshark commit logic to determine (given a starting point) the first anchor
to be ordered (§3.1.1).

Upon committing an anchor, all of its (yet-to-be-ordered) causal history is
deterministically ordered as well. Helper functions causal_history and
get_anchors aid, respectively, in identifying the causal history of a node
(necessary for both commit and ordering logic), and the anchor candidate
schedule. Shoal++ adopts and extends Shoal’s (Spiegelman et al., 2023)
reputation logic; get_anchors returns, for each round, a vector of eligible
anchors.

Algorithm 1 DAG interface

1:DAG API:

2: process_node(v: Node)

3: process_certified_node(v: Node)

4: causal_history(v: Node) $\rightarrow$ Vec¡Node¿

5: run_bullshark(anchor: Node) $\rightarrow$ Node

6: get_anchors(round: int) -¿ Vec¡Node¿

7:

8:struct $\textit{Node }\mathsf{n}$:

9: $\mathsf{n}.\textit{round}$ $\triangleright$ the associated round in the
DAG

10: $\mathsf{n}.\textit{source}$ $\triangleright$ the replica proposing $n$

11: $\mathsf{n}.\textit{parents}$ $\triangleright$ $n-f$ nodes from round
$\mathsf{v}.\textit{round}-1$

Algorithm 2 Core Shoal++ utilities

1:Local variables:

2: dag: DAG $\triangleright$ Initially empty

3: weak_votes: Vec¡Vec¡int¿¿ $\triangleright$ Initially empty

4: round: int $\triangleright$ Initially 0

5: anchors: Vec¡Node¿ $\triangleright$ Initially empty

6:

7:procedure next_ordered_nodes()

8: while true do

9: if anchors.is_empty() then

10: round++

11: anchors $\leftarrow$ dag.get_anchors(round)

12: anchor $\leftarrow$ anchors.pop()

13: anchor_to_order $\leftarrow$ select

14: fast_commit(anchor)

15: dag.run_bullshark(anchor)

16: if anchor_to_order $\neq$ anchor then

17: skip_to(anchor_to_order)

18: return dag.causal_history(anchor_to_order)

19:

20:procedure skip_to(anchor: Node)

21: round $\leftarrow$ anchor.round

22: anchors $\leftarrow$ dag.get_anchors(round)

23: anchors.remove(anchor)

24:

25:procedure fast_commit(n: Node)

26: while true do

27: if weak_votes[n.round][n.source] $\geq 2f+1$ then

28: return n

29:

30:upon receiving node n do

31: $r\leftarrow n.round$

32: $s\leftarrow n.source$

33: if n is the first node revived from s in round r then

34: for each $parent\in n.parents$ do

35: weak_votes[r][parent]++

36: dag.process_node(n)

37:

38:upon receiving certified node cn do

39: dag.process_certified_node(cn)

Algorithm 2 summarizes the core protocol additions made by Shoal++ in an
effort to reduce Anchor Commit, and Anchoring latency. We now discuss both in
detail in turn.

###  5.1. A faster Direct Commit rule

As described in §3.2 it currently takes, in the best case, 6 message delays to
commit an anchor using the Bullshark Direct Commit Rule. One DAG round is
required to certify the anchor node itself, and a second DAG round is required
to collect sufficient votes. A replica can directly commit an anchor upon
observing $f+1$ certified nodes that link to the anchor (i.e. include the
anchor in their parent set).

Figure 3. Bullsharks’s direct commit rule requires f+1 certified vote nodes,
while Shoal++’s direct commit rule requires $2f+1$ (uncertified) node
proposals.

Shoal++ makes the following simple observation: if sufficiently many DAG
proposals link to the anchor, the anchors fate is already set in stone, and we
need not wait for round certification to complete. Recall that the
certification process consists of three message exchanges, a proposal step, a
voting step, and a certificate forwarding step (§3). Shoal++ allows replicas
to Fast_Commit (Alg. 2) as soon as it observes $2f+1$ proposals that link to
an anchor (Fig. 3). To do so, replicas simply additionally keep track of weak
votes for each round that correspond to the proposals observed. Weak votes are
not guaranteed to survive certification. For instance, a faulty proposer may
equivocate, and produce a node certificate containing a different proposal
that does not link to the anchor. However, out of any $2f+1$ weak-votes, at
least $f+1$ must be cast by correct proposers that will never equivocate.
Consequently, the presence of $2f+1$ weak-votes guarantees that eventually
$f+1$ certificates linking to the anchor must be formed, thus ensuring safety.
Using the Direct Fast Commit rule allows replicas to commit an anchor in only
$4$md: 3md to certify the anchor, and 1md to broadcast and receive proposals.

We note, however, that this rule places a stronger requirement for liveness;
$f$ additional proposals are (tentatively) required to link to an anchor. We
thus retain the existing Direct Commit rule as backup, and allow replicas to
commit using whichever rule is satisfied first. In some cases it may be faster
(and more reliable) to commit using $f+1$ certified nodes. For instance when
the network is unstable, or point latencies are asymmetric, the fastest $f+1$
replicas might advance much more quickly than the fastest $2f+1$.

In our empirical evaluation we find that this case is rare (§8) and that
replicas are, most of the time, able take advantage of the Fast Direct Commit
rule. Shoal’s reputation scheme ensures that eligible anchor candidates are
typically well connected, making it exceedingly commonplace for future round
proposals to link to an anchor.

###  5.2. Increasing anchor frequency

In order to reduce Anchoring latency, Shoal++ tries to dynamically designate
as many nodes as possible as anchors. Intuitively, if all nodes were anchors
that become committed, no node would experience any Anchoring latency.333We
note that such an approach is briefly discussed in the closing remarks of
Shoal (Spiegelman et al., 2023), but is neither implemented nor carefully
evaluated for practical considerations. Safely operating more than one anchor
per round requires additional orchestration. To ensure a consistent log order
across all correct replicas, parallel anchors must be committed in a pre-
defined order. One easy way to visualize parallel orchestration is by mapping
anchors to fixed slots; much like parallel proposals in traditional BFT
protocols such as PBFT (Castro and Liskov, 2002). Figure 4 shows a simple
example in which there are four anchors in one round (all $n$ nodes are
anchors). Each anchor employs it’s own consensus instance that may proceed in
parallel, and out of order, but anchors can be committed only in sequence.
Each consensus instance operates a one-shot Bullshark instance, augmented with
the Fast Direct Commit Rule. We remark that each Bullshark instance operates
it’s own tentative anchor schedule (e.g. the yellow anchor in Fig. 4 is
considered the next anchor in the instance started by the red anchor), but
terminates as soon as the initial anchor is resolved.

Figure 4. An illustration with four anchors in round $1$. Anchors follow the
pre-assigned order: blue, red, green, pink. The blue, green and pink anchor
commit directly; each has $\geq f+1$ references from nodes in round $2$. The
red anchor, however, lacks support, and is only indirectly committed upon
directly committing the yellow anchor in round $4$. The green and pink anchors
must wait to be ordered until the red anchor is resolved.

While simple, a straightforward instantiation of this design is not robust,
and may, in practice negate (or even hurt) any latency benefit. By treating
every node as anchor, progress is, in particular, bottlenecked on the slowest
anchor. We illustrate such an unwelcome scenario in Figure 4: although the
green and pink anchors have sufficient support to commit, they must wait until
the preceding red anchor becomes committed or skipped. Unfortunately, the red
anchor is slow and does not have any immediate links; it is indirectly
committed only two rounds later via the next anchor in it’s consensus instance
(yellow anchor). In even worse circumstances, an anchor might never commit. In
this case, we must wait for confirmation that the anchor is skipped, and fill
its assigned slot with a no-op. Such scenarios are not fringe outliers, but
expected by design: since DAG nodes include only $2f+1$ edges, rounds are
privy to advancing based on the fastest $2f+1$ nodes, and leaving the
remainder behind. Thus, with high probability, at least one anchor per round
will not receive sufficient direct votes.

Adopting the reputation mechanism proposed by Shoal can help ameliorate, but
not remedy the concern. We leverage reputation and modify Get_anchors(r) to
limit the set of eligible anchors per round only to those associated with
historically fast and well-connected replicas. Unfortunately, we find that in
practice leveraging reputation alone is insufficient, and does not reliably
enough exclude slow replicas. While past performance is a helpful indicator,
network instabilities in geo-distributed systems make it hard to accurately
predict future performance, and we observe that the set of ”slow” replicas
changes very dynamically. To improve robustness further, we add two additional
techniques that, respectively, try to (i) avoid unnecessarily classifying
nodes as slow, and (ii) dynamically skip likely obsolete anchors.

##### Round Timeouts.

Reputation alone is overly harsh in categorizing nodes as slow. Since DAGs can
advances with the fastest $2f+1$ replicas, to maximize the likelihood of
anchors that commit directly, reputation pessimistically caps the eligible
anchors per round to include only the (estimated) fastest $2f+1$ nodes. (i.e.
$\frac{2}{3}$ of total nodes). In reality, however, ineligible nodes may only
be fractionally slower, and arrive imminently. To avoid discriminating against
such nodes, Shoal++ makes the conscious choice to, in each round, additionally
wait for a small timeout beyond the first $2f+1$ nodes observed, and include
any momentarily received nodes as additional edges. While this slightly slows
down individual rounds, it encourages replicas to operate in lockstep,
resulting in a more densely connected DAG. This allows us, in turn, to
optimistically increase the set of eligible anchors back to include all $n$
nodes, thus reducing overall latency.

We note that timeouts are not necessary for liveness, and are purely
optimizing performance. They can thus be configured very aggressively, and
are, in practice, negligible compared to the 3 network delays required to
certify a node.

##### Skipping Anchor Candidates.

Although round timeouts increase the reliability of the Direct Commit Rule,
they cannot guarantee its success. Occasionally, replicas may fail or
experience high networking delays, resulting in missing, or unconnected nodes.
In such cases, all subsequently pre-ordered anchors must wait until the
current anchor is resolved. Recall that an anchor $A1$ in round $r$ is only
resolved only upon committing, in its local consensus instance, an anchor $A2$
in a future round $r^{\prime}>r$: $A1$ is committed if it is present in the
causal history of $A2$ (Indirect Commit), or skipped if it is not. In
practice, we expect indirectly committed anchors to be rare. Anchors that are
merely slow, are likely to be committed thanks to the round timeout. Crashes,
in turn, predominantly result in skips. Byzantine abuse can unfortunately not
be avoided, and we must rely on the reputation scheme to avoid such anchors;
fortunately, such faults are exceedingly rare in most practical
deployments.444Popular blockchain systems (Team, 2023, 2022) report observing
zero Byzantine faults in over a year of deployment. Reported faults are
typically benign crashes.

We note that, even though $A2$ has been committed, it cannot be ordered before
all preceding anchors in the pre-defined schedule have resolved their
respective consensus instances (i.e. commit or skip). This is undesirable:
such anchors are (i) likely already included in the causal history of $A2$,
and (ii) may be subject to further latency delays. Unfortunately we cannot
avoid this scenario if $A1$ is committed; another replica may have committed
it directly, and resolved (and applied) the output of the next scheduled
anchor $B1$. We can, however, sidestep the resolution of preceeding anchors’
Bullshark instances if $A1$ is skipped. For any given consensus instance, all
replicas necessarily agree on the order of all committed and skipped anchors.
Thus, in particular, they agree on the first committed anchor (in this case
$A2$, since $A1$ is skipped). Let the round of this anchor be $r^{\prime}$.
Shoal++ opts to skip all tentative anchor candidates in rounds $<r^{\prime}$.

Instead of pre-assigning anchors to fixed slots, Shoal++ considers all but the
first anchor in each round virtual, and dynamically materializes them as it
sees fit. At any given time, there is only a single materialized consensus
instance (with an anchor every other round); upon resolving the current
instance, Shoal++ re-evaluates where to sensibly place the next anchor. Only
then it begins evaluating the associated consensus instance. Since all
replicas resolve each instance identically, each locally re-interprets and
materializes the same anchor schedule. Consider a slightly modification of the
example in Figure 4, in which the yellow anchor does not extend the red
anchor. The blue anchor commits directly, and Shoal++ dynamically materialized
the red node as the next anchor to evaluate. The red anchor, however, will be
resolved as skipped upon committing the yellow anchor. Shoal++ thus skips
evaluating the virtual green and pink anchors, and instead tries to
materialize as anchor the first node after the yellow anchor.

###  5.3. Operating multiple DAGs in parallel

Finally, in an effort to minimize Queuing latency, Shoal++ chooses to operate
$k$ concurrent DAG instances, and interleave their outputs to construct a
single, totally ordered log. Intuitively, staggering multiple DAGs, in a
pipline-like manner, allows transactions to be proposed quicker. Instead of
waiting (up to 3md) for the next DAG round to begin, a transaction simply
joins the next round of the next DAG. This reduces the expected Queuing
latency from $1.5$md to $1.5/k$ md. In practice, we deploy Shoal++ with three
DAGs, each offset by one message delay. Since each DAG round requires 3md to
certify a node proposal, this ensures that a some DAG’s proposal is available
every 1md. We find that 3 DAGs offers a good sweetspot between theoretical
Queuing latency and batch sizes; additional DAGs offer diminishing returns as
proposals carry increasingly smaller batches.

Algorithm 3 summarizes the algorithm. Each DAG instance runs as a black-box,
isolated from the others. In order to create a consistent total order, we must
interleave their outputs. Each time a DAG commits an anchor, it outputs a new
log segment.Shoal++ rotates across DAGs in round-robin fashion, and appends,
in each round, exactly one available segment to the log. If, for whatever
reason, one DAG commits more frequently, then it’s excess available segments
must wait to be ordered until the other DAGs to make progress. Importantly,
the individual DAGs themselves never block, and progress unimpeded. We note
that segments also may not (and need not) be of equal size; each segment
corresponds to a newly committed anchor, each of which may order varying sizes
of causal histories.

Algorithm 3 Shoal++

1:Local variables:

2: $d_{1},d_{2},d_{3}$: DAG instances $\triangleright$ Initially empty

3:loop

4: for i=1 to 3 do

5: output $d_{i}$.next_ordered_nodes()

Operating additional DAGs incurs additional messages and associated processing
overhead. However, we find that in practice, this does not negatively affect
performance. In fact, throughput increases because smaller batches are
proposed more frequently which helps amortize bandwidth and processing,
resulting in better resource utilization. In theory, messages from different
DAGs can be overlayed in order to share signatures. For instance, a node-
proposal of DAG $i\in\\{0,1,2\\}$ can easily be combined with the certified-
node-broadcast message of DAG $(i+1)\%3$.555In theory, votes can also be
overlayed, though typically it is favorable to send them as fast as possible,
rather than synchronizing. This too, we find not to be worth it in practice as
(i) signatures are not the bottleneck, and (ii) message stages have assymetric
latencies, and artificially aligning them increases Queuing latency.

###  5.4. Discussion

The combination of the above techniques allows Shoal++ to, in the common,
fault-free case, reduce average e2e latency to only 4.5md: 4md to commit
anchors, and 0.5md queuing latency. In the presence of faults or bad network
behaviors, additional anchoring and commit latency will be incurred to resolve
anchors via the Indirect Commit/Skip Rule.

We note that Shoal++ uses a linear star-based communication pattern to ceritfy
nodes, while protocols such as PBFT (Castro and Liskov, 2002) leverages
quadratic all-to-all communication. If desired, Shoal++ can adopt all-to-all
communication as well, reducing latency by 1md (to 3.5md total) at the cost of
increased message complexity. Finally, we remark that although Shoal++ incurs
a small additional queuing latency, every replica acts as proposer, and
clients need only contact their local replica (in absence of faults). Single
leader designs, in contrast, require clients to contact possibly remote
leaders, introducing additional ”queuing” latency.

##  6\. Correctness

We now prove the Safety and Liveness of Shoal++. We separately prove each
augmentation Shoal++ introduces through a reduction to the Safety and Liveness
proofs of Bullshark and Shoal. To formalize the arguments, our proof relies on
the following three properties.

###### Property 1.

For any node $n$, the call causal_history(n) returns the same vector of nodes
to all replicas.

This holds true for all Narwhal-based DAGs, and follows directly from the fact
that all nodes in the DAG are certified.

We next summarize the Safety guarantee of Bullshark.

###### Property 2.

All replicas commit the same anchors, and in the same order.

Finally, we rely on the Safety proof of Shoal.

###### Property 3.

For any given round $r$ the leader reputation mechanism ensures that
get_anchors(r) return the same vector of nodes at all replicas.

###  6.1. Fast Direct Commit Rule

Since Shoal++ can commit using both the Fast Direct Commit Rule and the
existing (Bullshark) Direct Commit Rule, Liveness follows directly from
Bullshark. We prove that the Fast Direct Commit rule is safe:

###### Lemma 6.1.

For any anchor $a$, the procedures fast_commit($a$) and run_bullshark($a$)
never return contradictory values.

###### Proof.

By the code, fast_commit($a)$ can only return $a$. Thus we need to prove that
if fast_commit($a)$ triggers, then run_bullshark($a$) also returns $a$.
fast_commit($a)$ implies that the replica received $2f+1$ (uncertified) node
proposals from different replicas that reference $a$. Since there are at most
$f$ faulty replicas, at least $f+1$ of these proposals were broadcasted by
correct replicas and will eventually be certified. Since $f+1$ such certified
nodes exist, some replicas may directly commit the anchor $a$ via the
Bullshark logic. It follows from P.2 that in this case, the run_bullshark($a$)
call returns $a$ to all replicas.

∎

###  6.2. Multiple Anchors per Round

Liveness follows directly from Bullshark. We show that Shoal++’s dynamic
anchor mechanism retains Safety.

###### Lemma 6.2.

We assume all correct replicas are initialized with the same state (_round_
and _anchors_). Then, all correct replicas’ invocations of next_ordered_nodes
(Alg 2) return the same result.

###### Proof.

By the lemma assumption and Property 3, anchors.pop() returns the same anchor
in the first iteration of the while loop to all replicas (Line 12). By Lemma
6.1, all correct replicas agree on which anchor to order (Line 13). It
follows, from the determinism of next_ordered_nodes and P.1 that all replicas
return the same vector of nodes to be ordered in their first
next_ordered_nodes call (line 18). In addition, by the determinism of
next_ordered_nodes, all replicas end up with the same state (_round_ and
_anchors_) after the calls return. Therefore, by applying the argument above
inductively, it is easy to show that all replicas also return the same vector
of nodes in all future calls.

∎

###  6.3. Queuing latency

###### Theorem 6.3.

The Shoal++ protocol Algorithm 3 satisfies Safety and Liveness.

The Liveness and Safety proof of each DAG is given above. Since DAG outputs
are interleaved deterministically, Safety and Liveness of the composed system
follows immediately.

##  7\. Practical Considerations

We briefly discuss some implementation considerations.

##### Inline data streaming

Narwahl (Danezis et al., 2022) proposes, in addition to the DAG construction,
to further decouple, and horizontally scale data dissemination using an
additional ”worker”-layer. Workers disseminate batches optimistically
a-priori, and DAG proposals contain only hash references. This construction is
extremely throughput-friendly in the best case, as data is streamed
continuously, and consensus carries only metadata. In practice, however, much
like with uncertified DAG-BFT protocols (Keidar et al., 2022; Babel et al.,
2023), other replicas might not have the data behind the hashes (or the
references in the case of uncertified DAGs) when the proposal is received and
thus additional 2md latency is required for fetching. Shoal++ opts to forgo
the worker layer in order to avoid this latency, and chooses to disseminate
transaction batches inline with DAG proposals. Operating staggered DAGs allows
Shoal++ to nonetheless achieve throughput competitive to that of Narwahl (with
a single worker), as smaller batches are sent more frequently, thus amortizing
bandwidth close to a streaming design.666Scaling throughput by employing more
workers is typically not worth it in existing BFT deployments, as single-
worker ordering throughput in existing protocols already far exceeds execution
bandwidth. Finally, we note that inline data streaming simplifies data
fetching as it avoids an additional indirection needed to dereference digests.

##### Efficient fetching

DAG edges in Shoal++ contain only certified nodes, allowing Shoal++ to
efficiently fetch missing nodes and resolve inconsistencies across replicas.
Replicas whose DAG views are out of sync, may validate and vote on proposals
without locally observing the proposed node’s causal history. This streamlines
the certification process, and ensures that the DAG operates at predictable
rates. Any missing causal histories can be inferred asynchronously, off the
critical path. We remark that this is not possible in uncertified DAGs; to
ensure liveness, replicas must fetch all missing data before processing a new
node. This results in unsteady processing times, and may significantly
increase e2e latency. Certified edges, additionally allow us to balance data
fetching load: since at least $f+1$ correct replicas must have observed any
certify node, replicas missing the node may request it from different replicas
to balance load.

##### Distance-based priority broadcast.

We observe that in systems with large $n$, message broadcasting consumes
considerable CPU times. When sending messages in a fixed order (e.g. first to
$R1$, then to $R2$, …) can unintentionally cause replicas to consistently
receive messages with delay, making their nodes subject to falling behind in
the DAG. To circumvent this issue, Shoal++, periodically records point
latencies between replicas, and adjust broadcast send-orders to prioritize
farther away replicas. This results in a more balanced message distribution,
increasing the homogeneity of node certification pace.

##  8\. Evaluation

Our evaluation seeks to to answer three questions:

  1. (1)

Latency reduction: How much does Shoal++ reduce Latency compared to state-of-
the-art alternatives?

  2. (2)

Latency breakdown: How much does each of the augmentations introduced in
Shoal++ contribute to the latency reduction?

  3. (3)

Robustness: How well does Shoal++ tolerate faults?

We implemented Shoal++ in the Aptos Blockchain codebase. Our prototype is
written in Rust and utilizes the Tokio asynchronous runtime. It uses BLS
(Boneh et al., 2001) implemented over BLS12-381 curves for signatures, RocksDB
for persistent storage of consensus data, and Noise for authentication. We
disable the execution and ledger storage components of the original blockchain
in order to isolate consensus performance.

Figure 5. No failures with 100 replicas. Each data point represents the 50
percentile with error bars representing the 25, and 75th percentiles.

##### Baselines.

We compare Shoal++ against three popular, high throughput DAG-BFT consensus
protocols, Bullshark (Spiegelman et al., 2022b), Shoal (Spiegelman et al.,
2023), and Mysticeti (Babel et al., 2023), as well as one traditional low-
latency BFT protocol, Jolteon (Gelashvili et al., 2022). Bullshark and Shoal
represent state-of-the-art certified DAG-based protocols, while Mysticeti
(Babel et al., 2023) is a concurrent work to Shoal++ proposing an uncertified
design to reduce latency. Jolteon (Gelashvili et al., 2022) is a state-of-the-
art leader-based BFT protocol, which improves Hotstuff (Yin et al., 2019)
latency by 50%. Bullshark and Jolteon, respectively, are currently deployed on
the Sui (Team, 2023) and Aptos (Team, 2022) Blockchains.

For an apples-to-apples comparison, we re-implemented Bullshark, Shoal, and
Jolteon according to the papers’ description in the same codebase as Shoal++.
Like Shoal++, Bullshark and Shoal are run without the Narwhal worker layer to
minimize latency. For Mysticeti we run the publicly available source code; its
prototype too is written in Rust, using Tokio, but forgoes writing consensus
data to persistent storage, making it less production-realistic.

##### Experimental setup

We use the Google Cloud Platform (gcp, [n. d.]) to mimic the deployment of a
globally decentralized network. Our testbed consists of 100 replicas spread
evenly across 10 regions around the world: we choose 2 regions in the US (us-
west1 and us-east1), 2 regions in Europe (europe-west4 and europe-southwest1),
1 region each in South America (southamerica-east1), South Africa (africa-
south1) and Australia (australia-southeast1), and 3 in Asia (asia-northeast3,
asia-southeast1, and asia-south1). The round-trip times between these regions
range between 25ms and 317ms. We use n2d-standard-64 virtual machines,
containing 64 vCPUs and 256 GB of
memory777https://cloud.google.com/compute/docs/general-purpose-
machines#n2d_machines. We provisioned a 2TB network attached disk to each
machine to guarantee enough IOPS for persistence. This spec is similar to
those used by production blockchains and qualifies as commodity grade.

Each client connects to a single replica and issues a continuous stream of
dummy transactions, each consisting of 310 random bytes. The e2e latency is
measured as the time between when a transaction arrives at a replica, and when
the transaction is ordered and ready to be executed. We use a maximum batch
size of 500 transactions in all systems; in all DAG-based systems, each DAG
node proposal contains one batch, and for Jolteon the leader may propose up to
100 of them. We configure Jolteon to use a 1.5s timeout for view changes (the
standard in existing production systems (Team, 2022)). We use a timeout of
600ms in each round for Bullshark, Shoal and Shoal++; Mysticeti by default
uses a 1s round timeout. We note that timeouts in Bullshark, Shoal and Shoal++
serve different functions. Bullshark requires them for liveness, while Shoal
manages to sidestep using timeouts for liveness all but edge cases; Shoal++
follows Shoal, but re-introduces a timeout only for improved performance. We
note that the timeout is started at the beginning of a round, and thus
typically introduces only a small additional wait past observing the first
$2f+1$ certified nodes.

###  8.1. Failure-free case

Figure 5 illustrates throughput and latency under failure-free conditions.
Shoal++ is the only system to sustain sub-second e2e latency up to a
throughput of 100k transactions per second (tps) while simultaneously scaling
throughput to over 150k tps. At low load, Shoal++ achieves 775ms median
latency.

Jolteon is bottlenecked by the leader’s network bandwidth and cannot scale
throughput beyond 2100 tps. At a low load, Jolteon has 900ms median latency.

Bullshark and Shoal support much higher throughput but suffer from high
latency. They incur, even at 1400 tps, respectively 1.9s and 1.45s median e2e
latency. With 50k tps the latency increases to 2.4 and 1.7, respectively. This
follows directly from their high average number of required message delays
(§3.2). The throughput of Bullshark and Shoal is bottlenecked by network
utilization since we disabled Narwhal streaming for better latency.

Shoal++ significantly reduces latency (at least by 50% over Shoal, and 60%
over Bullshark), while simultaneously offering improved throughput. The
parallel DAG construction allows Shoal++ to better utilize network and storage
resources: rather than broadcasting and processing a large batch once per
round, it broadcasts and processes three smaller batches at the same time.

Mysticeti matches the throughput of Shoal++, which suggests that they both
reach a networking bandwidth bottleneck. However, Mysticeti fails to match the
latency of Shoal++ (and Jolteon at low load). This is presumably because at
higher loads – even in the absence of faults – replicas may be temporarily out
of sync and need to fetch missing data on the critical path of consensus,
resulting in a slowdown.

Figure 6. Shoal++ Breakdown. No failures with 100 geo-distributed replicas.

###  8.2. Latency improvement breakdown

Figure 6 isolates the respective latency improvement of each Shoal++
augmentation compared to the baseline, Shoal. Shoal++ Faster Anchors shows
Shoal augmented only with the Fast Direct Commit Rule. Shoal++ More Faster
Anchors adds the multiple anchor augmentation to the former, and omits the
parallel DAGs optimization. The Fast Commit rule in theory improves anchor
commit latency by 2md. In real, asymmetric network settings, however, it is
not always 2md faster than the Direct Commit rule, and thus the practical
latency improvement is smaller.

The multiple anchor augmentation contributes to improved latency the most.
First, it saves on average 3md by eliminating the anchoring latency for most
nodes. Second, it makes sure that the anchoring latency for non-anchor nodes
is one DAG round. This is because, with many anchors per round, each non-
anchor node is referenced by at least one anchor with an overwhelming
probability. The parallel DAG framework improves latency further by reducing
queuing latency, but more importantly, it improves throughput scalability by
approaching a the data ”streaming” effect; crucially, and unlike Narwhal-based
worker designs, it does so without incurring additional latency.

Figure 7. Latency/Throughput graph with 33 out of 100 crashed replicas.

###  8.3. Failure case

To understand how robust Shoal++ is, we compared it to the baseline systems
under less favorable conditions with 33 crash failures out of a total number
of 100 replicas. The results are shown in Figure 7. Unfortunately, we could
not run Mysticeti in this scenario because distributing failures across
regions is not supported in their codebase.888Mysticeti allows only for
specific regions to fail collectively. Jolteon demonstrates roughly the same
latency under low load as their leader reputation mechanism quickly overcomes
the failures and elects only alive replicas. Bullshark, in contrast, suffers
from higher latency and lower TP since it does not have a leader reputation
mechanism to elect the strongest anchors. Shoal and Bolt keep roughly the same
throughput as in the failure-free case but suffer from higher latency due to a
higher quorum time - since failures are equally distributed, a quorum of
replicas has to span more regions.

##  9\. Related work

##### Latency optimal BFT

Spurred by the seminal PBFT (Castro and Liskov, 2002) protocol, a long line of
systems (Kotla et al., 2007; Gueta et al., 2019; Martin and Alvisi, 2006;
Suri-Payer et al., 2021; Gelashvili et al., 2022) optimize for consensus
latency. PBFT-based protocols designate a single leader to act as sequencer,
and replace it only sporadically (e.g upon failure, or eagerly for fairness).
This approach enjoys excellent latency. PBFT requires, when led by a correct
replica, only 3 message delays (md); the optimum achievable latency in
presence of faults, and optimal resilience of $n=3f+1$. Several followup works
suggest optimistic Fast Paths (Kotla et al., 2007; Gueta et al., 2019; Martin
and Alvisi, 2006; Suri-Payer et al., 2021) that improve latency to only 2md in
absence of faults, or by weakening resilience to $n=5f+1$. Unfortunately,
single leader-based designs are fundamentally bottlenecked in throughput by
the bandwidth and processing capacity of a single replica.

##### High throughput BFT

The key idea to scale beyond this bottleneck was realizing that networking
resources must be fully utilized. Some works propose to decouple data
dissemination from the consensus logic (Danezis et al., 2022; Yang et al.,
2022; Arun and Ravindran, 2022), while others (Stathakopoulou et al., 2019;
Gupta et al., 2021; Stathakopoulou et al., 2022) propose multi-log frameworks:
these systems partition the request space and operate multiple parallel black-
box instances of consensus protocols (e.g. PBFT) – each led by a different
replica –, and carefully intertwine their outputs to construct a single,
totally ordered log. This approach can achieve high throughput but requires
complex coordination to deal with failures and re-configuration.

##### DAG BFT

More recently, a new class of so-called DAG-BFT protocols have emerged as the
popular choice for high throughput BFT. At a high level, deployed DAG-BFT
protocols propose to explicitly separate data dissemination from consensus,
and utilizing only a single common DAG data structure to implement consensus
(§3).

HashGraph (Baird, 2016) was the first to propose a DAG-based consensus
structure, and Danezis et al. (Schett and Danezis, 2021) showed that any
deterministic BFT protocol can, in theory, be embedded on a DAG. Aleph (Gagol
et al., 2019) and DAG-Rider (Keidar et al., 2021) were the first to introduce
additional rigidity to the DAG construction, leveraging a round-based
structure to design asynchronous BFT protocols. Blockmania (Danezis and
Hrycyszyn, 2018) was the first attempt to implement a DAG-BFT system, but fell
short of adoption as it inherited a complex view change procedure, notorious
to traditional BFT protocols such as PBFT.

Narwhal and Tusk (Danezis et al., 2022) catapulted DAG-BFT to popularity by
demonstrating that (i) (asynchronous) consensus can be embedded onto DAG-
structures without the need for explicit view changes (Tusk), and (ii)
throughput can be scaled nearly linearly through the addition of a
horizontally scalable worker layer (Narwahl Mempool). Bullshark (Spiegelman et
al., 2022a) improved upon Tusk by adopting partial synchrony and introducing a
common case fast path during synchronous intervals; in a future iteration
(Spiegelman et al., 2022b) Bullshark removed the asynchronous fallback, and
established itself as the de facto partially synchronous DAG-BFT protocol.

Bullshark designates, at regular intervals (every two rounds), DAG-nodes to
simulate a leader (anchor) akin to traditional BFT protocols, and commits them
upon observing DAG patterns that ensure durable agreement of the leader. We
refer to §3 for an overview of the Narwahl core DAG, and the partially
synchronous Bullshark consensus protocol. Shoal improves the latency of
Bullshark by (i) increasing anchor frequency to every round, (ii) utilizing a
deterministic reputation scheme to select as anchors only the fastest, and
best-connected replicas, and (iii) eliminating leader/anchor timeouts in all
but extremely unlikely scenarios. Shoal, in a closing remark, briefly
discusses the idea of multiple anchor per round; however, it neither provides
an implementation, nor detailed consideration of practical details.
Unfortunately, best case (failure free) average latency of state of the art
partially synchronous DAG-BFT protocols remains as high as 10.5md (Shoal).

##### Uncertified DAGs

A recent group of protocols propose the design of uncertified DAGs. Such
constructions can, in theory, reduce latency, but are increasingly brittle as
they are prone to data fetching on the critical path (§3.2). Cordial Miners
(Keidar et al., 2022) replaces the Reliable Broadcast (RB) in each round with
best-effort broadcast (BEB), allowing anchors to (in the best case) commit
within 3md; anchors are placed every other round, for an average latency of
4.5md. Similarly, BBCA-chain (Malkhi et al., 2023) replaces non-anchor nodes
with BEB, and strengthens anchor nodes to single-shot pbft instances.
Unfortunately, neither proposal has an implementation that empirically
evaluates practical performance.

##### Concurrent Latency reduction efforts.

In concurrent efforts to Shoal++, several recent (non-peer reviewed) protocols
suggest latency improvements, underlining the demand for high throughput
systems with lower latency.

Sailfish (Shrestha et al., 2024) introduces a new anchor commit rule that
resembles the Fast Direct Commit Rule proposed in Shoal++, but unlike Shoal++
forgoes leveraging the Bullshark Direct Commit rule as potentially faster
alternative. Unfortunately, Sailfish lacks an implementation that empirically
substantiates their suggested latency improvement.

Mysticeti improves upon Bullshark’s best case latency by transitioning to an
uncertified DAG and implementing the Cordial Miners (Keidar et al., 2022)
consensus protocol. Mysticeti, like Shoal++, adopts Shoal’s high-level
proposal to optimistically employ multiple anchors per round. Our evaluation
demonstrates that Mysticeti almost matches Shoal++’s latency in the common
case. However, as discussed in §3.2, and independently corroborated by
Motorway (Giridharan et al., 2024), uncertified DAG constructions are prone to
data fetching on the critical path, which can, in practice, negate the
suggested latency benefits. A single Byzantine (or slow) replica, for
instance, can impose at least 2 additional message delays per round in
Mysticeti by not fully (or timely) disseminating its node proposals. The
certified DAG employed by Shoal++ significantly enhances its resilience to
Byzantine behavior.

Motorway (Giridharan et al., 2024) introduces a promising DAG-free consensus
approach in which replicas efficiently and reliably disseminate data
independently in parallel ”data lanes”, and consensus commits only snapshot
cuts of the lane states.

##### Leader reputation in BFT

To the best of our knowledge, leader reputation for BFT systems was first
implemented in DiemBFT (Team, 2021), and formalized by Carousel (Cohen et al.,
2022). Shoal (Spiegelman et al., 2023) and later Hammerhead (Tsimos et al.,
2023) adopt leader reputation to DAG-BFT in an effort to exclude
underperforming leaders from anchor candidacy. Shoal++ extends the approach to
provide, in each round, a set of anchor candidates.

##  10\. Conclusion

This work introduces Shoal++, a DAG-based BFT consensus protocol that offers
high throughput, while significantly lowering e2e latency compared to current
state of the art DAG-BFT protocols. Shoal++ takes as its starting point
existing state of the art DAG-BFT protocols, and augments them in three key
ways: (i) it reduces, in the common case, the commit latency of leaders
(anchors), (ii) dynamically reinterprets anchor schedules to increase anchor
frequency, and (iii) operates multiple parallel DAG instances to increase
proposal frequency. This, in sum, allows Shoal++ to reduce the fault-free
average e2e latency from 10.5 message exchanges (Shoal (Spiegelman et al.,
2023)) to only 4.5 message exchanges, within reach of traditional latency
optimal (but throughput-inefficient) BFT protocols such as PBFT.

We note that the parallel DAG instances technique might be of independent
interest, as this idea can be applied to any BFT algorithm to reduce its
queuing latency.

## References

  * (1)
  * dig ([n. d.]) [n. d.].  The Digital Euro.  https://www.ecb.europa.eu/euro/digital_euro/html/index.en.html Accessed: May 2024.
  * gcp ([n. d.]) [n. d.].  Google Cloud Platform.  https://cloud.google.com/ Accessed: May 2024.
  * ccf ([n. d.]) [n. d.].  Microsoft Confidential Consortium Framework.  https://www.microsoft.com/en-us/research/project/confidential-consortium-framework/ Accessed: May 2024.
  * Arun and Ravindran (2022) Balaji Arun and Binoy Ravindran. 2022.  Scalable Byzantine Fault Tolerance via Partial Decentralization.  _Proc. VLDB Endow._ 15, 9 (may 2022), 1739–1752.  https://doi.org/10.14778/3538598.3538599
  * Babel et al. (2023) Kushal Babel, Andrey Chursin, George Danezis, Lefteris Kokoris-Kogias, and Alberto Sonnino. 2023.  Mysticeti: Low-Latency DAG Consensus with Fast Commit Path.  _arXiv preprint arXiv:2310.14821_ (2023).
  * Baird (2016) Leemon Baird. 2016.  The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance.  _Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep_ (2016).
  * Boneh et al. (2001) Dan Boneh, Benjamin Lynn, and Hovav Shacham. 2001.  Short signatures from the Weil pairing. In _Advances in Cryptology - CRYPTO 2001_ _(Lecture Notes in Computer Science, Vol. 2139)_. Springer, 514–532.  https://doi.org/10.1007/3-540-44647-8_32
  * Castro and Liskov (2002) Miguel Castro and Barbara Liskov. 2002.  Practical Byzantine fault tolerance and proactive recovery.  _ACM Transactions on Computer Systems (TOCS)_ 20, 4 (2002), 398–461.
  * Chen and Micali (2019) Jing Chen and Silvio Micali. 2019.  Algorand: A secure and efficient distributed ledger.  _Theoretical Computer Science_ 777 (2019), 155–183.
  * Cohen et al. (2022) Shir Cohen, Rati Gelashvili, Lefteris Kokoris Kogias, Zekun Li, Dahlia Malkhi, Alberto Sonnino, and Alexander Spiegelman. 2022.  Be aware of your leaders. In _Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers_. Springer, 279–295.
  * Danezis and Hrycyszyn (2018) George Danezis and David Hrycyszyn. 2018.  Blockmania: from block dags to consensus.  _arXiv preprint arXiv:1809.01620_ (2018).
  * Danezis et al. (2022) George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022.  Narwhal and tusk: a dag-based mempool and efficient bft consensus. In _Proceedings of the Seventeenth European Conference on Computer Systems_. 34–50.
  * Dwork et al. (1988) Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988.  Consensus in the presence of partial synchrony.  _Journal of the ACM (JACM)_ 35, 2 (1988), 288–323.
  * Gagol et al. (2019) Adam Gagol, Damian Leśniak, Damian Straszak, and Michał Świetek. 2019.  Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. In _Proceedings of the 1st ACM Conference on Advances in Financial Technologies_. 214–228.
  * Gelashvili et al. (2022) Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2022.  Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. In _Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers_. Springer, 296–315.
  * Giridharan et al. (2024) Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024.  Motorway: Seamless high speed BFT.  _arXiv preprint arXiv:2401.10369_ (2024).
  * Gueta et al. (2019) Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019.  Sbft: a scalable and decentralized trust infrastructure. In _2019 49th Annual IEEE/IFIP international conference on dependable systems and networks (DSN)_. IEEE, 568–580.
  * Gupta et al. (2021) Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. 2021.  Rcc: Resilient concurrent consensus for high-throughput secure transaction processing. In _2021 IEEE 37th International Conference on Data Engineering (ICDE)_. IEEE, 1392–1403.
  * Keidar et al. (2021) Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021.  All You Need is DAG. In _Proceedings of the 40th Symposium on Principles of Distributed Computing_ (Virtual Event, Italy) _(PODC ’21)_. Association for Computing Machinery, New York, NY, USA.
  * Keidar et al. (2022) Idit Keidar, Oded Naor, and Ehud Shapiro. 2022.  Cordial Miners: A Family of Simple, Efficient and Self-Contained Consensus Protocols for Every Eventuality.  _arXiv preprint arXiv:2205.09174_ (2022).
  * Kotla et al. (2007) Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2007.  Zyzzyva: speculative byzantine fault tolerance. In _Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles_. 45–58.
  * Malkhi et al. (2023) Dahlia Malkhi, Chrysoula Stathakopoulou, and Maofan Yin. 2023.  BBCA-CHAIN: One-Message, Low Latency BFT Consensus on a DAG.  _arXiv preprint arXiv:2310.06335_ (2023).
  * Martin and Alvisi (2006) J-P Martin and Lorenzo Alvisi. 2006.  Fast byzantine consensus.  _IEEE Transactions on Dependable and Secure Computing_ 3, 3 (2006), 202–215.
  * Rocket ([n. d.]) Team Rocket. [n. d.].  Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies.  ([n. d.]).
  * Schett and Danezis (2021) Maria A Schett and George Danezis. 2021.  Embedding a deterministic BFT protocol in a block DAG. In _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing_. 177–186.
  * Shrestha et al. (2024) Nibesh Shrestha, Aniket Kate, and Kartik Nayak. 2024.  Sailfish: Towards Improving Latency of DAG-based BFT.  Cryptology ePrint Archive, Paper 2024/472.  https://eprint.iacr.org/2024/472 https://eprint.iacr.org/2024/472.
  * Spiegelman et al. (2023) Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. 2023.  Shoal: Improving dag-bft latency and robustness.  _arXiv preprint arXiv:2306.03058_ (2023).  To appear at FC 2024.
  * Spiegelman et al. (2022a) Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022a.  Bullshark: Dag bft protocols made practical. In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_. 2705–2718.
  * Spiegelman et al. (2022b) Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022b.  Bullshark: The Partially Synchronous Version.  _arXiv preprint arXiv:2209.05633_ (2022).
  * Stathakopoulou et al. (2019) Chrysoula Stathakopoulou, Tudor David, and Marko Vukolic. 2019.  Mir-BFT: High-Throughput BFT for Blockchains.  _CoRR_ abs/1906.05552 (2019).  arXiv:1906.05552 http://arxiv.org/abs/1906.05552
  * Stathakopoulou et al. (2022) Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. 2022.  State machine replication scalability made simple. In _Proceedings of the Seventeenth European Conference on Computer Systems_. 17–33.
  * Suri-Payer et al. (2021) Florian Suri-Payer, Matthew Burke, Zheng Wang, Yunhao Zhang, Lorenzo Alvisi, and Natacha Crooks. 2021.  Basil: Breaking up BFT with ACID (transactions). In _Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles_. 1–17.
  * Team (2019) The Algorand Team. 2019.  Algorand Networks.  https://www.algorand.foundation/ Accessed: April 2024.
  * Team (2020) The Avalanche Team. 2020.  Avalanche Networks.  https://www.avax.network/ Accessed: May 2024.
  * Team (2022) The Aptos Team. 2022.  Aptos Networks.  https://aptosfoundation.org/ Accessed: May 2024.
  * Team (2021) The Diem Team. 2021.  DiemBFTv4.  https://developers.diem.com/papers/diem-consensus-state-machine-replication-in-the-diem-blockchain/2021-08-17.pdf Accessed: May 2023.
  * Team (2023) The Sui Team. 2023.  Sui Networks.  https://sui.io/ Accessed: May 2023.
  * Tsimos et al. (2023) Giorgos Tsimos, Anastasios Kichidis, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2023.  Hammerhead: Leader reputation for dynamic scheduling.  _arXiv preprint arXiv:2309.12713_ (2023).
  * Yang et al. (2022) Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. 2022.  $\\{$DispersedLedger$\\}$:$\\{$High-Throughput$\\}$ Byzantine Consensus on Variable Bandwidth Networks. In _19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)_. 493–512.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019.  HotStuff: BFT Consensus with Linearity and Responsiveness. In _Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019_ , Peter Robinson and Faith Ellen (Eds.). ACM, 347–356.