arxiv: 2604.03974 · v1 · submitted 2026-04-05 · 💻 cs.DC

Recognition: 2 theorem links

· Lean Theorem

Lemonshark: Asynchronous DAG-BFT With Early Finality

Michael Yiqing Hu , Alvin Hong Yao Yan , Yang Yihan , Liu Xiang , Li Jialin

Authors on Pith no claims yet

Pith reviewed 2026-05-13 17:32 UTC · model grok-4.3

classification 💻 cs.DC

keywords asynchronous BFTDAG-BFTearly finalitylatency reductionByzantine consensustransaction finalizationdistributed systems

0 comments

The pith

Lemonshark allows nodes to finalize transactions early in asynchronous DAG-BFT before official commitment, cutting latency by up to 65% while preserving correctness.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Lemonshark as an asynchronous DAG-BFT protocol that reinterprets the DAG structure at the level of individual transactions. It locates conditions where a transaction can be finalized safely without waiting for the full commitment phase. This approach maintains all safety and liveness guarantees even when the network provides no timing bounds. A reader would care because current DAG-BFT methods optimize latency only for leader blocks, leaving non-leader transactions slower; early finality extends the benefit to every transaction.

Core claim

Lemonshark reinterprets the DAG at a transactional level and identifies conditions where commitment is sufficient but not necessary for safe results. This enables nodes to finalize transactions before official commitment without compromising correctness in fully asynchronous networks. The design yields up to 65% lower latency than the leading asynchronous BFT protocol.

What carries the argument

Transactional-level reinterpretation of the DAG that locates safe early-finalization conditions before official commitment.

Load-bearing premise

That identifiable conditions exist under which commitment is sufficient but not necessary for safe transaction results.

What would settle it

An asynchronous execution in which an early-finalized transaction produces a safety violation or inconsistency with later committed blocks.

Figures

Figures reproduced from arXiv: 2604.03974 by Alvin Hong Yao Yan, Li Jialin, Liu Xiang, Michael Yiqing Hu, Yang Yihan.

**Figure 2.** Figure 2: Both bˆ and b˜ contain transactions conflicting with those in b. This figure demonstrates that Bullshark requires commitment to resolve ordering uncertainty for such blocks. may vary depending on its perception of the last committed leader. Each leader block’s causal history is sorted using a deterministic algorithm and ordered in the same sequence as the initial totally ordered list. When a new leader b ′… view at source ↗

**Figure 3.** Figure 3: Blue blocks represent the causal history of [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

**Figure 4.** Figure 4: Orange blocks represent all uncommitted blocks from [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

**Figure 6.** Figure 6: Suppose green blocks are in-charge of a unique shard ( [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗

**Figure 7.** Figure 7: Suppose the green and yellow blocks are in-charge of two [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗

**Figure 8.** Figure 8: This figure shows how a Type γ transaction (t1,t2) affects the execution order. the final outcome to deviate from the desired result. Therefore, the sub-transactions that constitute a Type γ transaction must be executed atomically at the same time for the desired outcome to be achievable. 5.4.1 Ordering and Executing Type γ Sub-Transactions Enforcing that both sub-transactions of a Type γ transaction are e… view at source ↗

**Figure 9.** Figure 9: How speculation can aid in reducing latencies for depen [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗

**Figure 10.** Figure 10: Performance of Lemonshark with Type α transactions vs Bullshark with no faults, varying the number of nodes. locally to each instance and continuously send streams of 512B “nop” transactions. This approach isolates consensus performance from two orthogonal factors: (1) client geolocation, which would otherwise introduce variable network delays based on client proximity to the instances2 , and (2) transac… view at source ↗

**Figure 11.** Figure 11: Performance of Lemonshark with Type β transactions, while varying the amount of cross-shard activity and STO failure rates; “Cs Count” refers to “Cross-shard Count”. For the remainder of our experiments, we utilize a baseline transaction rate of 100K-tx/s and a committee size of 10. This represents a moderate load that effectively stresses the consensus mechanism while remaining within capacity. 8.2 Cross… view at source ↗

**Figure 12.** Figure 12: Performance of (a) Type α (b) Type β/γ (with moderate amount of cross-shard activity, (Cross-shard Count = 4, Cross-Shard Failure = 33%, while varying the number of faults. actions are cross-shard, we maintain ∼18% consensus latency reduction when “Cross-shard Count = 4” (details in §E.3). 8.3 Performance under Failures We vary the number of crash-faults to evaluate their impact on consensus latency. When… view at source ↗

read the original abstract

DAG-Rider popularized a new paradigm of DAG-BFT protocols, separating dissemination from consensus: all nodes disseminate transactions as blocks that reference previously known blocks, while consensus is reached by electing certain blocks as leaders. This design yields high throughput but confers optimal latency only to leader blocks; non-leader blocks cannot be committed independently. We present Lemonshark, an asynchronous DAG-BFT protocol that reinterprets the DAG at a transactional level and identifies conditions where commitment is sufficient -- but not necessary -- for safe results, enabling nodes to finalize transactions before official commitment, without compromising correctness. Compared to the state-of-the-art asynchronous BFT protocol, Lemonshark reduces latency by up to 65\%.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Lemonshark adds early transaction-level finality to DAG-BFT and claims a large latency win, but the supporting conditions and measurements need direct verification.

read the letter

The main point is that Lemonshark reworks the DAG at the transaction level so nodes can finalize some transactions early, before the usual leader-based commitment step, while staying fully asynchronous. This produces the reported latency drop of up to 65 percent versus prior DAG-BFT protocols like DAG-Rider. The change is narrow but targeted: it keeps the high-throughput dissemination structure and only relaxes the finality rule when specific local conditions hold. That is the actual novelty relative to the cited prior work. The paper does a clean job laying out why non-leader blocks normally wait and how the transaction view lets some of them finish sooner without new synchrony assumptions. If the conditions are stated precisely and the safety argument closes, this is a practical increment that implementers could use. The experimental numbers are presented as direct comparisons, which is the right format for this kind of systems claim. The soft spots are exactly where the abstract leaves them thin. The safety argument rests on the claim that commitment is sufficient but not always necessary; the paper must show that the early-finality rule never violates the global ordering or safety invariants, and that part is not visible in the summary. The 65 percent figure also needs the full experimental setup, workload details, and baseline configuration to be reproducible. No hidden synchrony or circular math appears in the description, but those two elements are load-bearing. This is work for people who build or tune high-throughput ledgers and consensus layers. A reader already familiar with DAG-Rider or similar protocols will get the most out of it and can judge whether the early-finality conditions are worth adopting. It deserves a serious referee. The idea is concrete enough and the performance target is relevant enough that the community should see the proofs and the data in full.

Referee Report

3 major / 2 minor

Summary. The paper presents Lemonshark, an asynchronous DAG-BFT protocol extending the DAG-Rider paradigm by reinterpreting the DAG at the transaction level. It identifies conditions under which commitment is sufficient but not necessary for safe results, allowing nodes to finalize transactions early before official commitment while claiming to preserve correctness in fully asynchronous networks, with a reported latency reduction of up to 65% versus state-of-the-art asynchronous BFT protocols.

Significance. If the early-finalization conditions can be shown to preserve both safety and liveness without hidden synchrony assumptions, the result would meaningfully improve practical latency for non-leader blocks in high-throughput DAG-BFT systems. The approach of relaxing commitment necessity under identifiable conditions is a targeted and potentially impactful refinement of existing DAG-BFT designs.

major comments (3)

Abstract: the claim of up to 65% latency reduction is presented without any experimental setup, baseline protocol details, measurement methodology, or error analysis; this empirical claim is load-bearing for the performance contribution yet lacks visible supporting data or derivation.
The protocol description (full text, assumed §3–4): the conditions under which commitment is sufficient but not necessary for safe early finalization are asserted to preserve correctness in fully asynchronous networks, but no formal safety proof, invariant, or theorem statement is referenced; without this, the central correctness claim cannot be verified.
§5 (performance evaluation, if present): the 65% figure is stated as a direct comparison, yet no table, figure, or parameter settings for the baseline (e.g., DAG-Rider) are cited, making it impossible to assess whether the reduction is robust or sensitive to network conditions.

minor comments (2)

Abstract: the baseline protocol for the latency comparison should be named explicitly rather than referred to generically as 'the state-of-the-art asynchronous BFT protocol'.
Notation: the distinction between 'commitment' and 'finalization' is used throughout but never given a concise formal definition; a short glossary or inline definition would improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below with clarifications drawn from the full text and indicate revisions to improve verifiability and presentation of the early-finalization claims and empirical results.

read point-by-point responses

Referee: Abstract: the claim of up to 65% latency reduction is presented without any experimental setup, baseline protocol details, measurement methodology, or error analysis; this empirical claim is load-bearing for the performance contribution yet lacks visible supporting data or derivation.

Authors: The abstract concisely reports the maximum observed latency reduction from the evaluation in Section 5, which compares Lemonshark against DAG-Rider under fully asynchronous message scheduling with fixed dissemination rates and varying network delays. We agree the abstract would benefit from a brief pointer to the evaluation. In revision we will append a short clause directing readers to Section 5 for the baseline (DAG-Rider), measurement (end-to-end commit latency), and parameter settings while respecting abstract length limits; detailed error bars and sensitivity analysis remain in the body. revision: partial
Referee: The protocol description (full text, assumed §3–4): the conditions under which commitment is sufficient but not necessary for safe early finalization are asserted to preserve correctness in fully asynchronous networks, but no formal safety proof, invariant, or theorem statement is referenced; without this, the central correctness claim cannot be verified.

Authors: Sections 3 and 4 define the early-finalization predicate over the DAG and argue that any transaction finalized early satisfies the same total-order and validity properties that DAG-Rider eventually commits, because the predicate only triggers on blocks that are already causally stable and cannot be reordered. We acknowledge that an explicit theorem statement would make verification easier. We will add a dedicated subsection stating the safety invariant (early finalization implies eventual commitment) together with a proof sketch that relies only on the asynchronous network model and the existing DAG-Rider leader-election properties. revision: yes
Referee: §5 (performance evaluation, if present): the 65% figure is stated as a direct comparison, yet no table, figure, or parameter settings for the baseline (e.g., DAG-Rider) are cited, making it impossible to assess whether the reduction is robust or sensitive to network conditions.

Authors: Section 5 contains latency plots and tables that directly compare Lemonshark and DAG-Rider across the same set of runs (4–16 nodes, block sizes 100–500 tx, message delays drawn from exponential distributions with means 50–200 ms). The 65 % figure is the maximum reduction recorded in the highest-delay configuration. We will revise the section text to explicitly cite the relevant figures, tables, and the exact parameter vector used for the baseline, enabling readers to judge robustness. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper describes Lemonshark as a reinterpretation of the DAG structure at the transaction level to enable early finalization under identifiable conditions while preserving safety in asynchronous networks. The central latency-reduction claim (up to 65%) is presented as an empirical comparison against the state-of-the-art asynchronous BFT protocol rather than a derived quantity obtained from fitted parameters or self-referential equations. No load-bearing steps reduce by construction to the paper's own inputs, no self-citation chains justify uniqueness theorems, and no ansatzes are smuggled via prior work by the same authors. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; the ledger is therefore empty pending full text.

pith-pipeline@v0.9.0 · 5418 in / 993 out tokens · 56720 ms · 2026-05-13T17:32:01.506370+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemonshark ... reinterprets the DAG at a transactional level and identifies conditions where commitment is sufficient—but not necessary—for safe results, enabling nodes to finalize transactions before official commitment
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We partition the key-space ... into n disjoint shards ... only a single node may produce a block containing transactions that modify keys of a particular shard

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

65 extracted references · 65 canonical work pages

[1]

Wall Street Journal, https://arc.net/l/quote/sr jmeosq

Accolade gathers $202 million for new blockchain fund of funds as crypto market recovers. Wall Street Journal, https://arc.net/l/quote/sr jmeosq. Accessed: 2026-02-21

work page 2026
[2]

https://aws.amazon.com/ec2/instance-t ypes/m5/

Amazon EC2 instance types. https://aws.amazon.com/ec2/instance-t ypes/m5/

work page
[3]

https://github.com/asonnino/narw hal/tree/bullshark-fallback

Bullshark Github implementation. https://github.com/asonnino/narw hal/tree/bullshark-fallback

work page
[4]

https://github.com/dalek-cry ptography/curve25519-dalek

Dalek elliptic curve cryptography library. https://github.com/dalek-cry ptography/curve25519-dalek

work page
[5]

https://www.ecb.europa.eu/ euro/digital_euro/html/index.en.html

European Central Bank: The digital euro. https://www.ecb.europa.eu/ euro/digital_euro/html/index.en.html

work page
[6]

https://arc.net/l/quote/srjmeosq

Janus Henderson to follow BlackRock and Fidelity into tokenisation. https://arc.net/l/quote/srjmeosq

work page
[7]

https://github.com/facebookresearch/ narwhal

Narwhal Github implementation. https://github.com/facebookresearch/ narwhal

work page
[8]

https://rocksdb.org/

RocksDB, A persistent key-value store. https://rocksdb.org/

work page
[9]

https://tokio.rs/

Tokio: An asynchronous runtime for the Rust programming language. https://tokio.rs/

work page
[10]

Asymptotically optimal validated asynchronous Byzantine agreement.ACM Sympo- sium on Principles of Distributed Computing(2019)

ABRAHAM, I., MALKHI, D.,ANDSPIEGELMAN, A. Asymptotically optimal validated asynchronous Byzantine agreement.ACM Sympo- sium on Principles of Distributed Computing(2019)

work page 2019
[11]

Shoal++: High throughput DAG BFT can be fast!ArXiv abs/2405.20488(2024)

ARUN, B., LI, Z., SURI-PAYER, F., DAS, S.,ANDSPIEGELMAN, A. Shoal++: High throughput DAG BFT can be fast!ArXiv abs/2405.20488(2024)

work page arXiv 2024
[12]

Mysticeti: Reaching the latency limits with uncertified DAGs.Network and Distributed System Security Symposium(2023)

BABEL, K., CHURSIN, A., DANEZIS, G., KICHIDIS, A., KOKORIS- KOGIAS, L., KOSHY, A., SONNINO, A.,ANDTIAN, M. Mysticeti: Reaching the latency limits with uncertified DAGs.Network and Distributed System Security Symposium(2023)

work page 2023
[13]

The Swirlds Hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance

BAIRD, L. The Swirlds Hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance

work page
[14]

Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols

BEN-OR, M. Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols. InACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing(1983)

work page 1983
[15]

Asynchronous secure computations with optimal resilience (extended abstract)

BEN-OR, M., KELMER, B.,ANDRABIN, T. Asynchronous secure computations with optimal resilience (extended abstract). InACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (1994)

work page 1994
[16]

Short signatures from the Weil pairing.Journal of Cryptology 17(2001), 297–319

BONEH, D., LYNN, B.,ANDSHACHAM, H. Short signatures from the Weil pairing.Journal of Cryptology 17(2001), 297–319

work page 2001
[17]

Asynchronous Byzantine agreement protocols.Inf

BRACHA, G. Asynchronous Byzantine agreement protocols.Inf. Comput. 75(1987), 130–143

work page 1987
[18]

Secure and efficient asynchronous broadcast protocols

CACHIN, C., KURSAWE, K., PETZOLD, F.,ANDSHOUP, V. Secure and efficient asynchronous broadcast protocols. InAnnual International Cryptology Conference(2001)

work page 2001
[19]

Studies in secure multiparty computation and applica- tions

CANETTI, R. Studies in secure multiparty computation and applica- tions

work page
[20]

Practical Byzantine fault tolerance

CASTRO, M. Practical Byzantine fault tolerance. InUSENIX Sympo- sium on Operating Systems Design and Implementation(1999)

work page 1999
[21]

F., WICKERSON, J.,ANDRIGGER, M

CLARK, J., DONALDSON, A. F., WICKERSON, J.,ANDRIGGER, M. Validating database system isolation level implementations with version certificate recovery.Proceedings of the Nineteenth European Conference on Computer Systems(2024)

work page 2024
[22]

P., NEVES, N

CORREIA, M. P., NEVES, N. F.,ANDVERÍSSIMO, P. From consensus to atomic broadcast: Time-Free Byzantine-Resistant protocols without signatures. 82–96

work page
[23]

Narwhal and Tusk: A DAG-based mempool and efficient BFT consensus.European Conference on Computer Systems(2021)

DANEZIS, G., KOKORIS-KOGIAS, E., SONNINO, A.,ANDSPIEGEL- MAN, A. Narwhal and Tusk: A DAG-based mempool and efficient BFT consensus.European Conference on Computer Systems(2021)

work page 2021
[24]

J., FOWLER, R

DOLEV, D., FISCHER, M. J., FOWLER, R. J., LYNCH, N. A.,AND STRONG, H. R. An efficient algorithm for Byzantine agreement with- out authentication.Information and Control 52(1982), 257–274

work page 1982
[25]

Some garbage in - some garbage out: Asynchronous t-Byzantine as Asynchronous benign t-resilient system with fixed t-trojan-horse inputs.ArXiv abs/1607.01210(2016)

DOLEV, D.,ANDGAFNI, E. Some garbage in - some garbage out: Asynchronous t-Byzantine as Asynchronous benign t-resilient system with fixed t-trojan-horse inputs.ArXiv abs/1607.01210(2016)

work page arXiv 2016
[26]

K.,ANDZHANG, H

DUAN, S., REITER, M. K.,ANDZHANG, H. BEAT: Asynchronous BFT made practical.ACM SIGSAC Conference on Computer and Communications Security(2018)

work page 2018
[27]

J., LYNCH, N

FISCHER, M. J., LYNCH, N. A.,ANDPATERSON, M. Impossibility of distributed consensus with one faulty process.J. ACM 32(1985), 374–382

work page 1985
[28]

Aleph: Efficient atomic broadcast in asynchronous networks with Byzantine nodes.ACM Conference on Advances in Financial Technologies (2019)

GAGOL, A., LESNIAK, D., STRASZAK, D.,ANDSWIETEK, M. Aleph: Efficient atomic broadcast in asynchronous networks with Byzantine nodes.ACM Conference on Advances in Financial Technologies (2019)

work page 2019
[29]

Bullshark: DAG BFT protocols made practical

GIRIDHARAN, N., KOKORIS-KOGIAS, L., SONNINO, A.,AND SPIEGELMAN, A. Bullshark: DAG BFT protocols made practical. ACM SIGSAC Conference on Computer and Communications Security (2022)

work page 2022
[30]

Autobahn: Seamless high speed BFT.ACM SIGOPS Symposium on Operating Systems Principles(2024)

GIRIDHARAN, N., SURI-PAYER, F., ABRAHAM, I., ALVISI, L.,AND CROOKS, N. Autobahn: Seamless high speed BFT.ACM SIGOPS Symposium on Operating Systems Principles(2024)

work page 2024
[31]

Analysing and improving shard allocation protocols for sharded blockchains.ACM Conference on Advances in Financial Technologies(2022)

HAN, R., YU, J.,ANDZHANG, R. Analysing and improving shard allocation protocols for sharded blockchains.ACM Conference on Advances in Financial Technologies(2022)

work page 2022
[32]

KAHN, A. B. Topological sorting of large networks.Communications of the ACM 5(1962), 558 – 562

work page 1962
[33]

H., GUPTA, S., MALKHI, D.,ANDSADOGHI, M

KANG, D. H., GUPTA, S., MALKHI, D.,ANDSADOGHI, M. Hotstuff- 1: Linear consensus with one-phase speculation.Proceedings of the ACM on Management of Data 3(2024), 1 – 29

work page 2024
[34]

All you need is DAG.ACM Symposium on Principles of Distributed Computing(2021)

KEIDAR, I., KOKORIS-KOGIAS, E., NAOR, O.,ANDSPIEGELMAN, A. All you need is DAG.ACM Symposium on Principles of Distributed Computing(2021)

work page 2021
[35]

KEIDAR, I., NAOR, O., POUPKO, O.,ANDSHAPIRO, E. Y. Cordial miners: Fast and efficient consensus for every eventuality. InInterna- tional Symposium on Distributed Computing(2022)

work page 2022
[36]

Elle: Inferring isolation anomalies from experimental observations.ArXiv abs/2003.10554(2020)

KINGSBURY, K.,ANDALVARO, P. Elle: Inferring isolation anomalies from experimental observations.ArXiv abs/2003.10554(2020)

work page arXiv 2003
[37]

LIBERT, B., JOYE, M.,ANDYUNG, M. Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares.ACM symposium on Principles of Distributed com- puting(2014)

work page 2014
[38]

EPIC: Efficient Asynchronous BFT with adaptive security.IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)(2020), 437–451

LIU, C., DUAN, S.,ANDZHANG, H. EPIC: Efficient Asynchronous BFT with adaptive security.IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)(2020), 437–451

work page 2020
[39]

J., KAMINSKY, M.,ANDANDERSEN, D

LLOYD, W., FREEDMAN, M. J., KAMINSKY, M.,ANDANDERSEN, D. G. Don’t settle for eventual: Scalable causal consistency for wide- area storage with COPS.ACM Symposium on Operating Systems Principles(2011)

work page 2011
[40]

Dumbo-MVBA: Optimal multi-valued validated asynchronous Byzantine agreement, revisited

LU, Y., LU, Z., TANG, Q.,ANDWANG, G. Dumbo-MVBA: Optimal multi-valued validated asynchronous Byzantine agreement, revisited. Symposium on Principles of Distributed Computing(2020)

work page 2020
[41]

BBCA-CHAIN: One-Message, low latency BFT consensus on a DAG.ArXiv abs/2310.06335(2023)

MALKHI, D., STATHAKOPOULOU, C.,ANDYIN, M. BBCA-CHAIN: One-Message, low latency BFT consensus on a DAG.ArXiv abs/2310.06335(2023)

work page arXiv 2023
[42]

K., XIA, Y., CROMAN, K., SHI, E.,ANDSONG, D

MILLER, A. K., XIA, Y., CROMAN, K., SHI, E.,ANDSONG, D. X. The Honey Badger of BFT protocols.Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (2016)

work page 2016
[43]

Consolidating concur- rency control and consensus for commits under conflicts

MU, S., NELSON, L., LLOYD, W.,ANDLI, J. Consolidating concur- rency control and consensus for commits under conflicts. InUSENIX Symposium on Operating Systems Design and Implementation(2016)

work page 2016
[44]

Load balancing for sharded blockchains

OKANAMI, N., NAKAMURA, R.,ANDNISHIDE, T. Load balancing for sharded blockchains. InFinancial Cryptography Workshops(2020)

work page 2020
[45]

B.,ANDTHEIMER, M

PETERSEN, K., SPREITZER, M., TERRY, D. B.,ANDTHEIMER, M. Bayou: Replicated database services for world-wide applications

work page
[46]

Mako: Specu- lative distributed transactions with geo-replication

SHEN, W., CUI, Y., SEN, S., ANGEL, S.,ANDMU, S. Mako: Specu- lative distributed transactions with geo-replication. InUSENIX Sympo- sium on Operating Systems Design and Implementation(2025)

work page 2025
[47]

Practical threshold signatures

SHOUP, V. Practical threshold signatures. InInternational Conference on the Theory and Application of Cryptographic Techniques(2000)

work page 2000
[48]

Shoal: Improving DAG-BFT latency and robustness.ArXiv abs/2306.03058 (2023)

SPIEGELMAN, A., AURN, B., GELASHVILI, R.,ANDLI, Z. Shoal: Improving DAG-BFT latency and robustness.ArXiv abs/2306.03058 (2023)

work page arXiv 2023
[49]

Bullshark: The partially synchronous version.ArXiv abs/2209.05633(2022)

SPIEGELMAN, A., GIRIDHARAN, N., SONNINO, A.,ANDKOKORIS- KOGIAS, L. Bullshark: The partially synchronous version.ArXiv abs/2209.05633(2022)

work page arXiv 2022
[50]

weak- links

TAN, C., ZHAO, C., MU, S.,ANDWALFISH, M. Cobra: Making trans- actional key-value stores verifiably serializable. InUSENIX Symposium on Operating Systems Design and Implementation(2020). A Definitions and Proofs A.1 Definitions for Bullshark This subsection describes the Bullshark consensus engine. We utilize definitions to illustrate better how Lemonshark...

work page 2020
[51]

Committed

In the raw causal history of the block produced by pi in the first round of the wave: if it shows neither the 2nd Stable leader in wave w−1 nor the Fallback leader is committed, paths by the block produced by pi in the last round of w to the Fallback leader are considered as a fallback vote. In Bullshark, a leader that has garnered sufficient votes is con...

work page
[52]

In the next round, there exist no leaders (odd round)

work page
[53]

if there exists a steady leader and there exists sufficient steady votes, if it is in-charge ofki, it must have a pointer to b

work page
[54]

Or a leader in r+1 is already committed, while b is not

If there exists sufficient fallback votes,br+1 i must have a pointer to b. Or a leader in r+1 is already committed, while b is not. Otherwise, the block fails the leader check on shard ki. Note that b does not need to be in-charge of shard ki in this definition. We now prove using the following propositions that if the leader check is satisfied for a bloc...

work page
[55]

t meets all of the conditions for STO for a Type α trans- action (see Lemma A.2)

work page
[56]

b r i has a pointer to br−1 j and it has SBO, or br j is the oldest uncommitted block in-charge of kj

work page
[57]

b r j does not have a transaction that modifies ka j, or br j is known to already be committed by some leader block

work page
[58]

inherited

b r i passes the leader check for k j or the br+1 j does not have a transaction that modifies ka j. Proof. Let b′ be the leader block that eventually commits br i . As the transaction writes to ki, we require that t meets the conditions for STO as if it is a Type α transaction, including that it persists in roundr+1. Now, since t reads from k j, we now ad...

work page
[59]

However, we achieved similar results when we utilized the parameters present in their repository 5

We were unable to get the claimed performance when utilizing parameters as described in their paper (utilizing their code). However, we achieved similar results when we utilized the parameters present in their repository 5. We believe this could either be a mistake on their part or one of the various bugs in their fallback version of the protocol

work page
[60]

Each batch contains up to 500kB of transactions, but can be represented by a 32B hash

Similar to Narwhal-Tusk [23], nodes perform 1 round of one-to-all broadcast to create batches, and another one- to-all broadcast to form blocks including those batches. Each batch contains up to 500kB of transactions, but can be represented by a 32B hash. Therefore, a block size of 1000B should only contain approximately 32 batches. In their code, wheneve...

work page
[61]

Cross-shard probability

In Bullshark’s implementation, they ordered the nodes sequentially and selected the last f nodes to be faulty. We instead, chose to randomized the selection of faulty nodes. Furthermore, we also randomized the steady leader election as compared to a simple round-robin rotation (per Bullshark). However, we add a restriction that no two consecutive steady l...

work page
[62]

Suppose the process receiving the transaction provides the (unfinalized and potentially unsafe) speculative TO for t1 in b1 for round r1 during the first phase

of one-to-all broadcast. Suppose the process receiving the transaction provides the (unfinalized and potentially unsafe) speculative TO for t1 in b1 for round r1 during the first phase. In that case, the client may send a tentative transaction t′ 2 that executes conditionally on the speculated outcome of t1 being the one specified int ′ 2. Before the firs...

work page
[63]

The finalized outcome matches the speculated out- come provided previously:In this case, the client sim- ply continues, knowing that t′ 2 has been submitted and will be executed in due time

work page
[64]

The finalized outcome doesnotmatch the previously speculated outcome:In this case, t′ 2 will only execute if the speculative outcome of t1 aligns with the one in- cluded in t′

work page
[65]

Cross-shard Count

If not, t′ 2 is aborted, as are any subsequent transactions that depend on its speculated outcome. The client then immediately submits a new transaction, t′′ 2 , based on the finalized outcome of t1, thereby restarting the chain of transactions. Because cascading failure is intrinsic to the transaction chain itself, the above conclusions can be reached in...

work page