You are looking at a specific version 20210920:115210 of this paper. See the latest version.

Paper 2021/1248

The Adversary Capabilities In Practical Byzantine Fault Tolerance

Yongge Wang

Abstract

The problem of Byzantine Fault Tolerance (BFT) has received a lot of attention in the last 30 years. The seminal work by Fisher, Lynch, and Paterson (FLP) shows that there does not exist a deterministic BFT protocol in complete asynchronous networks against a single failure. In order to address this challenge, researchers have designed randomized BFT protocols in asynchronous networks and deterministic BFT protocols in partial synchronous networks. For both kinds of protocols, a basic assumption is that there is an adversary that controls at most a threshold number of participating nodes and that has a full control of the message delivery order in the network. Due to the popularity of Proof of Stake (PoS) blockchains in recent years, several BFT protocols have been deployed in the large scale of Internet environment. We analyze several popular BFT protocols such as Capser FFG / CBC-FBC for Ethereum 2.0 and GRANDPA for Polkadot. Our analysis shows that the security models for these BFT protocols are slightly different from the models commonly accepted in the academic literature. For example, we show that, if the adversary has a full control of the message delivery order in the underlying network, then none of the BFT protocols for Ethereum blockchain 2.0 and Polkadot blockchain could achieve liveness even in a synchronized network. Though it is not clear whether a practical adversary could {\em actually} control and re-order the underlying message delivery system (at Internet scale) to mount these attacks, it raises an interesting question on security model gaps between academic BFT protocols and deployed BFT protocols in the Internet scale. With these analysis, this paper proposes a Casper CBC-FBC style binary BFT protocol and shows its security in the traditional academic security model with complete asynchronous networks. Finally, we propose a multi-value BFT protocol XP for complete asynchronous networks and show its security in the traditional academic BFT security model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. STM 2021 https://www.nics.uma.es/stm2021/
Keywords
Byzantine Fault Tolerance
Contact author(s)
yonwang @ uncc edu
History
2021-09-20: received
Short URL
https://ia.cr/2021/1248
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.