Byzantine Chain Replication
📜 Abstract
We present a new class of Byzantine-tolerant State Machine Replication protocols for asynchronous environments that we term Byzantine Chain Replication. We demonstrate two implementations that present different trade-offs between performance and security, and compare these with related work. Leveraging an external reconfiguration service, these protocols are not based on Byzantine consensus, do not require majority-based quorums during normal operation, and the set of replicas is easy to reconfigure. One of the implementations is instantiated with t+1 replicas to tolerate t failures and is useful in situations where perimeter security makes malicious attacks unlikely. Applied to in-memory BerkeleyDB replication, it supports 20,000 transactions per second while a fully Byzantine implementation supports 12,000 transactions per second—about 70% of the throughput of a non-replicated database.
✨ Summary
The paper introduces Byzantine Chain Replication, a class of asynchronous Byzantine-tolerant state-machine replication protocols that combines chain-based request processing with an external reconfiguration service. Its central design choice is to avoid Byzantine consensus and majority quorums during failure-free operation, while using signed histories, order proofs, checkpointing, and reconfiguration to preserve safety across failures and configuration changes.
The authors present Shuttle in two forms: CRC Shuttle, which uses t+1 replicas and targets accidental or non-malicious failures, and HMAC Shuttle, which uses 2t+1 replicas and tolerates arbitrary Byzantine failures. In the reported BerkeleyDB experiments with t=1, CRC-style chain replication reached approximately 20,000 transactions per second, while fully Byzantine HMAC Shuttle reached approximately 12,000 transactions per second, or about 70% of the throughput of a non-replicated database.
The clearest documented research follow-on is BChain: Byzantine Replication with High Throughput and Embedded Reconfiguration (2014). BChain explicitly builds on chain-based Byzantine replication, develops an embedded reconfiguration mechanism called re-chaining, and evaluates an NFS implementation under fault-free and failure conditions. (escholarship.org) Subsequent distributed-systems and blockchain research also cites Byzantine Chain Replication, including work on Byzantine blockchain consensus and BFT performance evaluation. (ouci.dntb.gov.ua) The search found evidence of continued academic influence, but no reliable evidence that the specific Shuttle implementation was deployed as an industry production system.