Forensic Support for Abraham et al.’s BB Protocol

The consensus protocol is a fundamental building block in distributed computing and has been widely used in blockchain systems in recent years. Paxos, introduced by Lamport, stands out as one of the most widely adopted consensus protocols and has found application in renowned distributed systems, including Google's Spanner system. Abraham et al. analyzed the FaB Paxos protocol, a Byzantine version of Paxos. They abstracted the single-shot FaB Paxos into a Byzantine broadcast protocol and further gave an enhanced protocol known as Abraham et al.'s BB. Abraham et al.'s BB protocol achieved optimal two-round message interaction under good conditions, satisfying the optimal fault tolerance threshold of n=5t-1 where <i>n</i> represents total number of nodes in the system and <i>t</i> denotes the tolerable number of Byzantine nodes. This paper delves into scenarios wherein the actual number of Byzantine nodes surpasses the fault tolerance threshold during the operation of Abraham et al.'s BB protocol. To address this, we propose a forensic protocol designed to offer forensic support in cases of agreement violations. The forensic protocol aims to label Byzantine nodes through irrefutable evidence. We analyze the forensic protocol, elucidating the number of Byzantine nodes that the forensic protocol can label under different circumstances, along with the corresponding number of required messages. Additionally, we present an impossibility result, indicating that forensic support for Abraham et al.'s BB is impossible when the number of Byzantine nodes exceeds 2t-2.