Paper 2025/740

Otter: Scalable Sharding-Based Atomic Broadcast with Abortable Fork Detection

Xin Wang, Tsinghua University
Xiao Sui, Tsinghua University
Sisi Duan, Tsinghua University
Abstract

Sharding is a generic approach to enhance the scalability of distributed systems. In recent years, many efforts have been made to scale the consensus mechanism of blockchains from sharding. A crucial research question is how to achieve the sweet spot of having a relatively small shard size (to achieve decent performance) while achieving an overwhelming probability of correctness (so the system is safe and live). Many recent works fall into the two-layer design that uses some coordinating shards to monitor the correctness of other shards (CCS 2022, NDSS 2024, INFOCOM 2023). All of them involve expensive communication costs between the shards, significantly degrading performance. We present Otter, a scalable partially synchronous sharding-based Byzantine fault-tolerant atomic broadcast (ABC) protocol. We use coordinating shards in a completely new way. In particular, we randomly sample coordinating shards to directly participate in the consensus protocol. Such a random sampling mechanism makes it possible to analyze the correctness of the ABC protocol using a probabilistic model. In this way, we can significantly lower the shard size (informally, from over 1,200 in previous work to around 100) without lowering the probability of correctness. We also present a new notion called abortable fork detection (AFD) that might be of independent interest. Our evaluation results on Amazon EC2 using up to 1,000 replicas show that Otter achieves up to 4.38x the throughput of the state-of-the-art protocol.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
atomic broadcastsharding-based protocolblockchainsByzantine fault tolerance
Contact author(s)
wangxin87 @ tsinghua edu cn
suixiao @ mail tsinghua edu cn
duansisi @ tsinghua edu cn
History
2025-04-27: approved
2025-04-25: received
See all versions
Short URL
https://ia.cr/2025/740
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/740,
      author = {Xin Wang and Xiao Sui and Sisi Duan},
      title = {Otter: Scalable Sharding-Based Atomic Broadcast with Abortable Fork Detection},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/740},
      year = {2025},
      url = {https://eprint.iacr.org/2025/740}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.