Mysticeti: Reaching the Limits of Latency with Uncertified DAGs

• URL: http://arxiv.org/abs/2310.14821v4
• Date: Sat, 13 Jul 2024 18:10:57 GMT
• Title: Mysticeti: Reaching the Limits of Latency with Uncertified DAGs
• Authors: Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, Mingwei Tian,
• Abstract summary: We introduce Mysticeti-C, the first DAG-based Byzantine consensus protocol to achieve the lower bounds of latency of 3 message rounds. We extend Mysticeti-C to Mysticeti-FPC, which incorporates a fast commit path that achieves even lower latency for transferring assets.
• Score: 5.328717371685882
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce Mysticeti-C, the first DAG-based Byzantine consensus protocol to achieve the lower bounds of latency of 3 message rounds. Since Mysticeti-C is built over DAGs it also achieves high resource efficiency and censorship resistance. Mysticeti-C achieves this latency improvement by avoiding explicit certification of the DAG blocks and by proposing a novel commit rule such that every block can be committed without delays, resulting in optimal latency in the steady state and under crash failures. We further extend Mysticeti-C to Mysticeti-FPC, which incorporates a fast commit path that achieves even lower latency for transferring assets. Unlike prior fast commit path protocols, Mysticeti-FPC minimizes the number of signatures and messages by weaving the fast path transactions into the DAG. This frees up resources, which subsequently result in better performance. We prove the safety and liveness in a Byzantine context. We evaluate both Mysticeti protocols and compare them with state-of-the-art consensus and fast path protocols to demonstrate their low latency and resource efficiency, as well as their more graceful degradation under crash failures. Mysticeti-C is the first Byzantine consensus protocol to achieve WAN latency of 0.5s for consensus commit while simultaneously maintaining state-of-the-art throughput of over 200k TPS. Finally, we report on integrating Mysticeti-C as the consensus protocol into the Sui blockchain, resulting in over 4x latency reduction.

Related papers

• Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding [58.92526489742584]
  We propose provably lossless.<n> verification method that significantly boosts the expected number of accepted tokens.<n>We show that HSD yields consistent improvements in acceptance rates across diverse model families and benchmarks.
  arXiv  Detail & Related papers  (2026-01-09T11:10:29Z)
• SoK: Speedy Secure Finality [0.0]
  This paper surveys the state of the art in fast finality protocol design.<n>We introduce the core theoretical primitives underlying this space.<n>We then analyze the communication and aggregation bottlenecks faced by single-slot finality protocols.
  arXiv  Detail & Related papers  (2025-12-23T19:25:02Z)
• Universally Composable Termination Analysis of Tendermint [3.6181225888186055]
  This paper presents the first universally composable (UC) security analysis of Tendermint.<n>It demonstrates its resilience against strategic message-delay attacks.<n>Our main result proves that the Tendermint protocol UC-realizes the ideal Tendermint model.
  arXiv  Detail & Related papers  (2025-10-01T16:44:23Z)
• Odontoceti: Ultra-Fast DAG Consensus with Two Round Commitment [0.0]
  Odontoceti is the latest in DAG-based consensus, operating with a 20% fault tolerance instead of the established 33% level.<n>It is the first DAG-based protocol to achieve commitment in just two communication rounds, delivering median latency of 300 milliseconds.<n>This paper establishes the practical viability of lower fault tolerance consensus protocols for blockchains.
  arXiv  Detail & Related papers  (2025-09-19T15:22:28Z)
• Neutralizing Token Aggregation via Information Augmentation for Efficient Test-Time Adaptation [59.1067331268383]
  Test-Time Adaptation (TTA) has emerged as an effective solution for adapting Vision Transformers (ViT) to distribution shifts without additional training data.<n>To reduce inference cost, plug-and-play token aggregation methods merge redundant tokens in ViTs to reduce total processed tokens.<n>We formalize this problem as Efficient Test-Time Adaptation (ETTA), seeking to preserve the adaptation capability of TTA while reducing inference latency.
  arXiv  Detail & Related papers  (2025-08-05T12:40:55Z)
• Zaptos: Towards Optimal Blockchain Latency [52.30047458198369]
  We introduce Zaptos, a parallel pipelined architecture designed to minimize end-to-end latency. Zaptos achieves a throughput of 20,000 transactions per second with sub-second latency.
  arXiv  Detail & Related papers  (2025-01-18T00:22:22Z)
• Pioplat: A Scalable, Low-Cost Framework for Latency Reduction in Ethereum Blockchain [10.807408760944632]
  Pioplat is a feasible, customizable, and low-cost latency reduction framework. We show that Pioplat can significantly reduce the latency of receiving blocks/transactions and sending transactions.
  arXiv  Detail & Related papers  (2024-12-11T13:15:16Z)
• Mahi-Mahi: Low-Latency Asynchronous BFT DAG-Based Consensus [3.4234734330005]
  Mahi-Mahi is the first asynchronous BFT consensus protocol that achieves sub-second latency in the WAN. We build Mahi-Mahi on an uncertified structured Directed Acyclic Graph (DAG) We demonstrate the safety and liveness of Mahi-Mahi in a Byzantine context.
  arXiv  Detail & Related papers  (2024-10-11T09:54:56Z)
• Adelie: Detection and prevention of Byzantine behaviour in DAG-based consensus protocols [0.0]
  Recent developments in Byzantine Fault Tolerant consensus protocols have shown the DAG-based protocols to be a very promising technique. The latest versions of DAG-based protocols such as Mysticeti and Shoal++ show that indeed a latency comparable to that of traditional consensus protocols such as HotStuff can be achieve. This paper presents an implementation of Adelie protocol - bftd that demonstrates yet another breakthrough in the maximum achieved TPS and low latency.
  arXiv  Detail & Related papers  (2024-08-04T11:56:28Z)
• The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
  We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols. Existing approaches for threshold cryptosystems introduce a latency overhead of at least one message delay for running the threshold cryptographic protocol. We propose a mechanism to eliminate this overhead for blockchain-native threshold cryptosystems with tight thresholds.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus [1.6364535330823093]
  TetraBFT is a Byzantine fault tolerant protocol for solving consensus in partial synchrony. We validate the correctness of TetraBFT through rigorous security analysis and formal verification. We extend TetraBFT into a multi-shot, chained consensus protocol.
  arXiv  Detail & Related papers  (2024-05-04T08:54:42Z)
• Theoretically Achieving Continuous Representation of Oriented Bounding Boxes [64.15627958879053]
  This paper endeavors to completely solve the issue of discontinuity in Oriented Bounding Box representation. We propose a novel representation method called Continuous OBB (COBB) which can be readily integrated into existing detectors. For fairness and transparency of experiments, we have developed a modularized benchmark based on the open-source deep learning framework Jittor's detection toolbox JDet for OOD evaluation.
  arXiv  Detail & Related papers  (2024-02-29T09:27:40Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Banyan: Fast Rotating Leader BFT [20.52947785138998]
  Banyan is the first rotating leader state machine replication protocol that allows transactions to be confirmed in just a single round-trip time. We introduce a novel dual mode mechanism that enables optimal block finalization latency in the fast path. Our evaluation reveals that Banyan reduces latency by up to 30% compared to state-of-the-art protocols.
  arXiv  Detail & Related papers  (2023-12-10T12:32:58Z)
• Consistency Trajectory Models: Learning Probability Flow ODE Trajectory of Diffusion [56.38386580040991]
  Consistency Trajectory Model (CTM) is a generalization of Consistency Models (CM) CTM enables the efficient combination of adversarial training and denoising score matching loss to enhance performance. Unlike CM, CTM's access to the score function can streamline the adoption of established controllable/conditional generation methods.
  arXiv  Detail & Related papers  (2023-10-01T05:07:17Z)
• Resilient Output Consensus Control of Heterogeneous Multi-agent Systems against Byzantine Attacks: A Twin Layer Approach [23.824617731137877]
  We study the problem of cooperative control of heterogeneous multi-agent systems (MASs) against Byzantine attacks. Inspired by the concept of Digital Twin, a new hierarchical protocol equipped with a virtual twin layer (TL) is proposed.
  arXiv  Detail & Related papers  (2023-03-22T18:23:21Z)
• Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation [122.83280749890078]
  We propose an improved certified defense against general poisoning attacks, namely Finite Aggregation. In contrast to DPA, which directly splits the training set into disjoint subsets, our method first splits the training set into smaller disjoint subsets. We offer an alternative view of our method, bridging the designs of deterministic and aggregation-based certified defenses.
  arXiv  Detail & Related papers  (2022-02-05T20:08:58Z)
• Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
  Communication bottleneck has been a critical problem in large-scale deep learning. We propose a new distributed error feedback (DEF) algorithm, which shows better convergence than error feedback for non-efficient distributed problems. We also propose DEFA to accelerate the generalization of DEF, which shows better bounds than DEF.
  arXiv  Detail & Related papers  (2020-04-11T03:50:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.