Sharpedo: Dual-Mode Uncertified DAG-Based Consensus Protocol

Introduction

• Consensus constrains blockchain latency and throughput, while DAGs enable concurrent proposals; uncertified DAG protocols reduce communication delays to lower latency.DAG proposals can include blocks from multiple participants, rather than one block per consensus round.Source: Introduction · pp. 6–7
• Uncertified DAG protocols lack a dual-mode counterpart, leaving an opening to combine their advantages with flexible network assumptions.Existing dual-mode examples include Ditto for linear chains and Bullshark for DAGs.Source: Introduction · p. 7

1.1 Research Objectives

• Sharpedo’s objective is to combine Mysticeti and Mahi-Mahi into the first dual-mode uncertified DAG consensus protocol.The proposed combination targets partially synchronous low latency alongside asynchronous resilience.Source: §1.1 · p. 7

1.2 Contribution

• Sharpedo’s stated contributions include dynamic scheduling, implementation and testing, and Byzantine safety and liveness proofs.The schedule is intended to improve latency in both synchrony and asynchrony.Source: §1.2 · p. 8

1.3 General Overview

• The report proceeds from protocol background to Sharpedo’s design, implementation and simulations, formal proofs, and further work.Source: §1.3 · p. 8

2.1 Consensus Protocols

• Consensus protocols support state machine replication by having distributed nodes agree on values and the order of inputs.Safety prevents undesirable states; liveness requires eventual progress.Source: §2.1 · p. 9

2.1.1 Problem Specification

• Atomic broadcast extends reliable broadcast with a shared message order; consensus is framed through integrity, validity, agreement, and total order.The section connects satisfying atomic-broadcast properties with safety and liveness.Source: §2.1.1 · p. 10

2.2 Network Models

• Synchronous systems assume a fixed message-delay bound, asynchronous systems make no timing assumptions, and partial synchrony assumes the bound holds after GST.Dual-mode protocols switch network modes; this can add complexity because they handle distinct consensus protocols.Source: §2.2 · pp. 11–12

2.3 Threat Models

• BFT protocols tolerate faulty and malicious participants with 3f + 1 participants and quorums of 2f + 1, whose overlap supports agreement.By contrast, CFT protocols handle a fixed number of nodes that stop communicating; the text associates CFT assumptions with centralized protocols such as Paxos and Raft.Source: §2.3 · p. 13

2.4 Linear-chain Consensus Protocols

• Linear-chain protocols extend one chain through leader-proposed blocks and quorum votes, while PBFT requires O(n^2) messages.Bitcoin-style longest-chain protocols offer only probabilistic finality; PBFT uses pre-prepare, prepare, and commit stages.Source: §2.4 · pp. 14–15

2.4.1 Hotstuff

• Hotstuff reduces PBFT’s communication complexity to O(n), but repeated message delays beyond ∆ can trigger view changes and prevent liveness during asynchrony [25].If a leader does not create a quorum certificate before ∆, participants change views and elect another leader.Source: §2.4.1 · p. 15

2.4.2 Validated Asynchronous Byzantine Agreement (VABA)

• Multi-world VABA uses n view-based consensus instances and a randomness beacon to choose a proposer after n − f instances finish, supporting liveness under asynchrony [27].Its decoy instances are discarded after a view change, and the approach incurs O(n^2) message complexity and increased latency.Source: §2.4.2 · pp. 15–16

2.4.3 Ditto

• Ditto uses Jolteon with O(n) communication on its happy path and an asynchronous fallback with O(n^2) communication, while requiring synchronization to limit fragmentation [37].A process needs at least 2f + 1 timeout messages before switching to the fallback.Source: §2.4.3 · pp. 16–17

2.5 DAG-Based Consensus Protocols

• DAG-based protocols let validators propose blocks concurrently, and committing a leader proposal also commits its referenced causal history, removing the one-block-per-view bottleneck.Rounds are logical sequences, and waves group consecutive rounds; each round can include as many as n blocks.Source: §2.5 · pp. 17–18

2.5.1 DAG-Rider & Tusk

• DAG-Rider uses a common coin to select a wave leader retroactively, while Tusk separates transaction dissemination from ordering through Narwhal [28] [31].DAG-Rider includes non-leader blocks through the committed block’s causal history; Tusk’s Narwhal availability certificates require a 3-message delay before DAG addition.Source: §2.5.1 · pp. 18–19

2.5.2 BullShark

• Bullshark combines steady-state leaders with a common-coin fallback leader for asynchronous periods, but validators must track which voting mode applies [33].The cited comparison reports ≈100,000−130,000 transactions per second and 2s latency for Bullshark, versus 3s latency for Tusk [31] [32].Source: §2.5.2 · pp. 19–20

2.6 Uncertified DAG-Based Consensus Protocol

• Uncertified DAGs remove the need to certify blocks before broadcast: interpreting the DAG in a specific way forms certificates explicitly, with the process done within the DAG itself.For block B in round r to be committed, it needs 2f + 1 unique references in round r + 1 and 2f + 1 blocks in round r + 2 whose causal history observes that pattern.Source: §2.6 · p. 20, §2.6.1 · p. 21

2.6.1 Cordial Miners

• Cordial Miners has asynchronous and partially synchronous versions, while its suggested dual-mode extension uses deterministic and random leaders, an approach described as complicated to implement.A block must reference 2f + 1 unique valid blocks from the previous round to be eligible for commitment.Source: §2.6.1 · p. 21

2.6.2 Mysticeti

• Mysticeti uses partially synchronous assumptions and timeouts after GST; its uncertified blocks can be proposed in one message delay and committed in three, versus six for partially synchronous Bullshark.Multi-leader rounds and pipelining allow a proposed leader block to be committed every round.Source: §2.6.2 · pp. 21–22

2.6.3 Mahi-Mahi

• Mahi-Mahi is asynchronous and uses four- or five-round waves to propagate proposals before voting; its fallback can commit in four or five message delays, versus Bullshark’s twelve.Five rounds increase resilience to an active asynchronous adversary; four rounds reduce latency and have weaker liveness guarantees, especially under the asynchronous network model.Source: §2.6.3 · p. 22, §3.2.2 · p. 25

The Sharpedo Protocol

• Sharpedo combines Mysticeti and Mahi-Mahi as a dual-mode uncertified DAG protocol, targeting liveness in asynchronous and partially synchronous settings with low latency comparable to Mysticeti.Its fallback is run periodically because committing a DAG block also commits its causal history.Source: The Sharpedo Protocol · p. 23

3.1 System Design and Core Assumptions

• Sharpedo assumes n = 3f + 1 validators, up to f Byzantine validators, and reliable authenticated links; before GST messages may be delayed arbitrarily but are eventually delivered, while after GST transactions commit within ∆.Honest validators propose signed blocks with fresh transactions and at least 2f + 1 references to distinct valid blocks from the previous round.Source: §3.1 · pp. 23–24, §3.2 · p. 24, §3.2.1 · p. 25

3.2.2 Round and Wave

• Sharpedo uses three-round partially synchronous waves for a three-message commit delay, and four- or five-round asynchronous waves with boost rounds to propagate leader proposals before voting.The four-round asynchronous wave has weaker liveness guarantees in the asynchronous network model, but high-probability commitment under the random network model.Source: §3.2.2 · p. 25

3.2.3 DAG Patterns

• A certificate pattern has 2f + 1 references supporting a proposed block, while a skip pattern has 2f + 1 blocks that do not support it; Sharpedo determines certificates by analyzing these DAG patterns.Before GST, a perfect global coin supports eventual probabilistic progress; after GST, timeouts ensure a certificate for the deterministically selected primary block. Honest validators support at most one block per slot, so quorum intersection prevents multiple equivocating blocks from receiving sufficient support.Source: §3.2.3 · p. 26, §3.2.4 · p. 27, §3.2.5 · p. 27

3.3.1 Proposer Slot and Leader Selection

• Proposer slots can be committed, skipped, or left undecided; asynchronous leader selection uses 2f + 1 shares of a global perfect coin, while partially-synchronous selection is round-robin.Undecided slots make later slots wait, preserving a deterministic proposer sequence; Sharpedo allows up to 3f + 1 proposer slots per round.Source: §3.3.1 · pp. 28–29

3.3.2 Decision Rules

• Direct rules use commit or skip patterns; if a slot remains undecided, indirect rules inspect later anchors and their certificate links to decide whether to commit or skip it.If an anchor is undecided, the slot remains undecided; a to-skip anchor is bypassed in favor of the next available anchor.Source: Direct Rule · p. 29, Indirect Rule · pp. 29–30

3.3.3 Sequence

• Validators process the ordered leader sequence, omit skipped slots, stop at the first undecided slot, then linearize each committed block’s subDAG deterministically.Undecided slots therefore hold later leaders back from the final commit sequence.Source: §3.3.3 · p. 31

3.4 Dual-Mode

• Sharpedo runs one asynchronous wave every K rounds and otherwise uses partially-synchronous mode, aiming for partially-synchronous latency with asynchronous liveness.With pipelining, decision rounds may overlap, but a later round’s leader waits until earlier leaders are decided.Source: §3.4 · pp. 31–32, Figure 3.6 · p. 32

3.4.1 Dynamic Scheduling

• After a Kth leader commits, Sharpedo analyzes its subDAG and adjusts the asynchronous interval using the ratio of direct commits to expected commits, counting skipped slots as an asynchrony signal.The analysis excludes leaders that the subDAG cannot determine; L5a’s causal history, for example, lacks an additional vote needed to directly commit L2a.Source: §3.4.1 · pp. 33–34, Figure 3.7 · p. 34

3.4.2 Sequence (Extended)

• If turbulence leaves two asynchronous waves undecided, a validator may process schedule-dependent decisions out of order; Sharpedo cuts off the sequence at the first asynchronous committed leader so it can update and reanalyse.This mechanism is intended to prevent schedule divergence between validators.Source: §3.4.2 · p. 34

Implementation

• Sharpedo is implemented in Rust as a networked, multi-core validator, with asynchronous networking and consensus logic on a dedicated synchronous thread.The implementation uses raw TCP sockets, ed25519-consensus signatures, and blake2 hashing.Source: Implementation · p. 35

4.1 Decision Rule

• On block receipt, an idempotent function attempts to decide uncommitted leaders; a UniversalCommitter coordinates BaseCommitters for pipelining and multiple leaders per round.The UniversalCommitter manages each BaseCommitter’s leader and round offsets.Source: §4.1 · pp. 35–36, §4.1.1 · p. 36

4.1.1 Universal Committer

• The UniversalCommitter passes AsyncState to try_commit, which decides as many leaders as possible between the highest proposal round and highest committed round using the applicable mode.Source: §4.1.1 · p. 36

4.1.2 Base Committer

• The BaseCommitter applies direct and indirect decisions with mode-dependent round lengths: decision round r + w − 1 and anchor round r′ ≥ r + w.The asynchronous state selects w, including w = 3 or w = 4/w = 5.Source: §4.1.2 · p. 36

4.2 Dual-Mode Scheduler

• DualModeScheduler stores AsyncState, configuration bounds, and decided-leader sequences and counts; it updates the asynchronous interval when an asynchronous leader commits.AsyncState records the previous asynchronous round and current frequency; configuration includes wave length and leader count.Source: §4.2 · pp. 37–38

4.2.1 Collect Subdag Function

• For schedule updates, collect_subdag gathers the newest leader’s causal history back to the oldest committed leader in the stored sequence, producing identical subDAGs across validators.Source: §4.2.1 · p. 38

4.2.2 Count Direct Commits Function

• Sharpedo counts direct commits only in the update anchor’s causal history, then compares that count with eligible expected commits to adjust the asynchronous interval deterministically.Expected commits exclude proposals the subDAG cannot determine, including some leaders in pipelined sequences.Source: §4.2.2 · p. 39

4.3 Sequence Cutoff

• Leader processing stops at an undecided leader or an asynchronous committed leader; in the latter case it discards subsequent leaders and updates the interval before trying again.Source: §4.3 · pp. 39–40, Figure 4.2 · p. 40

4.4.1 Decision Rule

• Tests pass for partially synchronous, asynchronous, and switching operation, including asynchronous_wave settings of 4 and 5.The test suite also combines configurations such as pipelining and leader count.Source: §4.4.1 · p. 41

4.4.2 Dual-Mode Scheduler

• Scheduler tests check subDAG collection, direct-commit decisions, and leader-sequence truncation across schedule transitions.The tests include multi-leader and pipeline modes and verify that asynchronous rounds are identified for schedule recalculation.Source: §4.4.2 · pp. 41–42

4.5 Simulations

• Simulations use a discrete-event layer to model WAN latencies and time, with asynchronous testing configured to reach asynchronous mode more often than in normal use.The comparison includes p-sync, async-only, and dual mode, and measures transaction commit latency.Source: §4.5 · pp. 42–43
• Dual mode incurs a minimal latency increase over p-sync while providing asynchronous liveness; its latency rise from w = 4 to w = 5 is also minimal.Async-only latency increases substantially, and the authors caution that simulation does not replace geo-distributed cloud testing.Source: §4.5 · p. 44, Table 4.1 · p. 44

Dual-Mode Protocol Security

• Formal proofs adapt existing safety arguments and establish that Sharpedo’s dynamic schedule preserves safety and liveness.The safety proofs draw on Mahi-Mahi [38], while liveness arguments depend on whether GST has been reached, as in Mysticeti and Mahi-Mahi [36] [38].Source: Dual-Mode Protocol Security · p. 45

5.1 Total Order and Integrity Proofs

• Honest validators decide each slot consistently: they agree on leader slots and cannot disagree between committing and skipping a slot.The argument uses quorum intersection and common leader selection in asynchronous and partially synchronous modes.Source: §5.1 · pp. 47–48
• Delivered non-leader blocks appear at the same slot and with the same leader block at every honest validator.The delivery rule uses a committed leader’s causal history and prevents redelivery through a lower slot.Source: §5.1 · pp. 48–49
• Schedule agreement follows because validators process shared committed anchors and deterministically converge, including through later schedule transitions.A validator that lags can reach the next schedule by ordering the anchor that triggered the transition.Source: §5.1 · pp. 50–51
• Sharpedo satisfies Byzantine Atomic Broadcast total order and integrity through deterministic causal-history ordering and duplicate-block removal.The integrity argument relies on the linearizer removing duplicate sequence numbers before producing the final block sequence.Source: §5.1 · p. 51
• The scheduling mechanism preserves total order by ensuring that honest validators eventually converge on the same schedule.The schedule-transition argument is adapted from Tsimos et al. [35].Source: §5.1 · pp. 49, 51

5.2 Validity and Agreement Proofs

• Sharpedo proves Byzantine Atomic Broadcast validity and agreement while supporting partially synchronous and asynchronous assumptions.The proof treats the network cases separately and establishes progress regardless of network conditions.Source: §5.2 · pp. 51, 53
• Before GST, Sharpedo’s asynchronous mode eventually commits and delivers honest proposals consistently despite the absence of timing guarantees.The stated liveness cases use asynchronous wavelengths w = 4 and w = 5.Source: §5.2 · p. 52
• After GST, progress occurs within a bounded number of rounds, and the protocol eventually progresses across schedule changes.Advancement follows when all honest validators share a schedule and apply the same deterministic update rule.Source: §5.2 · pp. 52–53

Conclusion

• Sharpedo claims the 3-message-delay lower bound for most of its operation while providing liveness during asynchrony.The paper expects throughput and latency similar to Mysticeti and lower latency than Mahi-Mahi based on theoretical analysis, but empirical evaluation is outside its scope.Source: Conclusion · p. 54

6.1 Further Work

• The optimal K, asynchronous-interval bounds, and schedule adjustment factor remain undetermined.Experiments are proposed to determine these settings and evaluate protocol performance.Source: §6.1 · p. 55
• The proposed comparisons predict similar throughput and lower latency than Mahi-Mahi, and similar throughput with marginally higher latency than Mysticeti, under ideal conditions.These are claims the proposed experiments would test, not reported evaluation results.Source: §6.1 · p. 55
• Geo-distributed cloud experiments are proposed to evaluate Sharpedo against Mysticeti and Mahi-Mahi under ideal and crash-fault conditions.The proposed committee sizes are 10 and 50; Byzantine-fault performance evaluation is described as an open research question, with formal proofs used for safety and liveness.Source: §6.1 · p. 55

Universal Committer

• The UniversalCommitter selects asynchronous or partially-synchronous decision rounds and anchor thresholds according to the current leader’s mode.Its asynchronous wave length can be set to four or five rounds, and try_commit receives AsyncState to determine which mode applies.Source: Universal Committer · p. 61, BaseCommitter · p. 62

A.1.2 Dual-Mode Scheduler

• AsyncState records the interval between asynchronous rounds and the last round in which one ran.The scheduler uses this state to identify asynchronous rounds; its configuration can be stored in the WAL to support crashed-node session recovery.Source: Asynchronous State · pp. 63–64
• The scheduler configuration also controls partially-synchronous wave length, leaders per round, and whether consensus execution is pipelined.These settings are presented as static values that allow the aggressivity of schedule changes to be adjusted.Source: Dual Mode Configuration · p. 64

DualModeScheduler

• The scheduler stores async state, committee, configuration, committed leaders, and decided-slot length; simulator history checks that validators share the same asynchronous-interval history.The simulator also tracks update intervals to check schedule agreement across validators.Source: DualModeScheduler · p. 66, CollectSubdag · p. 72
• The scheduler selects asynchronous mode for a round from the current AsyncState and gathers an anchor’s sub-DAG through the round after the last asynchronous round.The traversal follows included blocks and avoids revisiting blocks.Source: DualModeScheduler · p. 66, CollectSubdag · p. 67
• On an asynchronous leader commit, the scheduler collects its sub-DAG, counts direct commits against expected commits, updates AsyncState, and resets the decided-slot sequence length.In simulator mode, it records the new interval for later analysis.Source: CollectSubdag · p. 68
• Direct-commit checks use committee stake weights, while expected-commit calculations account for indeterminate leader slots and whether pipeline mode is enabled.The scheduler evaluates committed leader slots against the collected sub-DAG and empties the leader queue as it checks them.Source: CollectSubdag · pp. 68–69
• A deterministic commit-ratio rule adjusts the asynchronous interval toward the target direct-commit ratio, bounded by minimum and maximum thresholds.When pipeline mode is disabled, the adjustment is aligned to a multiple of wave_length.Source: CollectSubdag · p. 71
• To prevent schedule desynchronization, the scheduler truncates the leader sequence at the first asynchronous leader and updates the schedule when the top leader is asynchronous; Lemma 9 proves validators agree on the resulting schedule.The risk arises when committing a leader can involve two distinct asynchronous rounds.Source: Safety Mechanism · p. 72

A.2.1 Decision Rule

• All tests passed across the tested modes when DEFAULT_WAVE_LENGTH_ASYNC was set to either 4 or 5.The representative dual-mode cases commit a partially-synchronous leader, then commit or skip an asynchronous leader, and commit another partially-synchronous leader.Source: §A.2.1 · pp. 74–75
• The tests use configurable committees, DAG builders, leader election, and quorum and validity thresholds to construct decision-rule scenarios.The section presents a representative subset and identifies base, multi-committer, and pipelined-committer test files.Source: §A.2.1 · p. 74
• The test suite includes cases for committing or skipping an asynchronous leader between partially-synchronous leaders.The described cases build DAGs and vary whether the asynchronous leader is present or filtered out.Source: §A.2.1 · p. 75, Dual-Mode Commit   · p. 75, Dual-Mode Skip   · p. 76

A.2.2 Dual-Mode Scheduler

• The tests verify asynchronous-rate detection and commit-counting behavior with pipelining enabled and with multiple leaders per round.The described multi-leader setup uses 2f + 1 leaders per round.Source: §A.2.2 · p. 77, Count Direct Commits (Indirect) · p. 78, Count Direct Commits · p. 78
• The scheduler tests emphasize count_direct_commits() and collect_subdag() because they determine deterministic schedule changes consistent across validators.The section says the tests are in dual_mode_scheduler.rs.Source: §A.2.2 · p. 77
• The scheduler tests check that direct-commit counting distinguishes direct commits from indirect commits within a subDAG.The stated expected counts are 1 for a DAG with all direct commits and 0 for a DAG with indirect commits.Source: Count Direct Commits · p. 77, Count Direct Commits (Indirect) · p. 78

Sequence Cutoff

• The cutoff test creates 300 * 5 blocks for a 300-round interval, then calls try_commit until the sequence empties or async_rate_round is reached and updated.Each loop should either stop at the correct async_rate_round or continue until the sequence is empty.Source: Sequence Cutoff · p. 78

A.3 Simulations

• Under ideal conditions, validators reach their leader slots within the timeout; simulations check that asynchronous intervals increase and histories match across validators.The increasing interval means the frequency of asynchronous mode decreases.Source: Good Network Simulations · p. 78
• In a 10-validator high-latency simulation, f validators miss leader slots and others mark them to-skip; asynchronous intervals decrease consistently, including for slow validators.The decreasing interval means asynchronous mode becomes more frequent.Source: Slow Network Simulations · pp. 78–79

Consensus Protocol Structures

• The PBFT and Hotstuff figures depict p3 as a Byzantine or faulty node that does not communicate with the others.Source: Figure B.1 · p. 80, Figure B.2 · p. 80
• In Tusk and partially-synchronous Bullshark, a committed leader’s causal history can place an earlier leader first; Bullshark can skip a leader absent from that history.The illustrated final sequences are {L0, L1} for Tusk and {L0, L2} for partially-synchronous Bullshark.Source: Figure B.3 · p. 81, Figure B.4 · p. 81
• Bullshark uses fallback leaders after a steady-state leader fails to commit, while Mysticeti uses two leaders per round and treats each round as a new wave.Source: Figure B.5 · p. 82, Figure B.6 · p. 82

Sharpedo Additional Figures

• In asynchronous mode with w = 5, a leader is committed when validators’ round r + 3 blocks contain it in their causal history, and skipped when those blocks do not vote for it.The figures illustrate the commit and skip patterns for leader block L1b.Source: Figure C.2 · p. 84, Figure C.3 · p. 84
• In partially-synchronous mode, an indirect certificate link lets a leader be committed without 2f + 1 certificates, or safely skipped without 2f + 1 blames when the link is absent.The examples use a directly committed leader L2a as the anchor for deciding L1a.Source: Figure C.4 · p. 85, Figure C.5 · p. 85
• Appendix figures show throughput and latency comparisons of Mysticeti-C and Mahi-Mahi with other state-of-the-art protocols, as presented in the works of Babel et al. [36] and Jovanovic et al. [38].Source: Figure C.6 · p. 86, Figure C.7 · p. 86

Algorithms

• Sharpedo’s pseudocode applies direct decision rules before indirect ones, then commits leaders in sequence until it encounters an undecided leader or an asynchronous commit.The selected mode is determined by the scheduler for each round; the resulting sequence is also recorded for later schedule analysis.Source: Algorithms · pp. 87–88
• Leader election is deterministic in partially-synchronous mode via GetLeader, like Mysticeti; in asynchronous mode, an offset from combined coin shares is added before electing the leader, introducing randomness.Source: Algorithms · pp. 88–89
• Sharpedo’s dual-mode scheduler includes UpdateAsyncSchedule, which TryCommit calls, and CountDirectCommits; for a committed asynchronous-mode leader, it obtains the leader’s subDAG and uses it to count direct commits.Source: Algorithms · p. 89
• IsVote checks whether a vote block’s voted block matches the specified leader, using the leader’s author and round.VotedBlock returns ⊥ when the queried round is at least the block’s round.Source: Algorithms · p. 93
• IsCert returns true when at least 2f + 1 parents of a certificate block vote for the specified leader.Source: Algorithms · p. 93
• IsLink checks whether a path through parent relationships connects the old block to the new block.Source: Algorithms · p. 93
• IsCertifiedLink checks whether a decision block in the leader’s wave certifies the leader and links to the anchor block.The procedure obtains the wave from the leader’s round and retrieves that wave’s decision blocks.Source: Algorithms · p. 93

• Claude is acknowledged for guidance on Mysticeti’s codebase and Rust, plus technical help with LaTeX formatting and figure creation.Source: Research Assistance Methods · p. 94