BFT Protocol Forensics
This work addresses the critical issue of accountability and security in distributed systems, particularly for cryptocurrencies like Diem, by providing forensic tools to detect malicious actors, though it is incremental as it builds on existing BFT protocols.
The paper tackles the problem of identifying malicious replicas in Byzantine fault-tolerant (BFT) protocols when faults exceed the optimal threshold, by mathematically formalizing forensic support and characterizing it for popular protocols like PBFT, HotStuff, and Algorand, showing that minor implementation details can cause wide variations in forensic capabilities. It demonstrates strong forensic support for LibraBFT with a lightweight module implemented on a Diem client, and proves an impossibility result for all secure BFT protocols in synchronous networks with 2t+1 replicas.
Byzantine fault-tolerant (BFT) protocols allow a group of replicas to come to a consensus even when some of the replicas are Byzantine faulty. There exist multiple BFT protocols to securely tolerate an optimal number of faults $t$ under different network settings. However, if the number of faults $f$ exceeds $t$ then security could be violated. In this paper we mathematically formalize the study of forensic support of BFT protocols: we aim to identify (with cryptographic integrity) as many of the malicious replicas as possible and in as a distributed manner as possible. Our main result is that forensic support of BFT protocols depends heavily on minor implementation details that do not affect the protocol's security or complexity. Focusing on popular BFT protocols (PBFT, HotStuff, Algorand) we exactly characterize their forensic support, showing that there exist minor variants of each protocol for which the forensic supports vary widely. We show strong forensic support capability of LibraBFT, the consensus protocol of Diem cryptocurrency; our lightweight forensic module implemented on a Diem client is open-sourced and is under active consideration for deployment in Diem. Finally, we show that all secure BFT protocols designed for $2t+1$ replicas communicating over a synchronous network forensic support are inherently nonexistent; this impossibility result holds for all BFT protocols and even if one has access to the states of all replicas (including Byzantine ones).