BFT Protocol Forensics

Abstract

In this work, we explore the idea of forensics for BFT protocols. BFT protocols are designed to solve consensus among n replicas as long as the number of Byzantine replicas or faults f is less than a threshold T. If there are more faults than T, either safety or liveness can be violated. Safety is violated when at least two honest replicas commit two different values. Forensics is a “day after” analysis, which asks, can we identify the Byzantine nodes responsible for this violation? More importantly, the analysis should be able to provide irrefutable proof of culpability of those nodes. So it is not enough that some honest nodes can identify the Byzantine nodes, knowing that they themselves are honest. In a real scenario, where we do not know which nodes are honest, forensics makes sense only if the honest nodes can put together a proof that shows the perpetrators of the protocol violation. Naturally, the proof can not depend on logs of all replicas, since Byzantine nodes can forge it. The best forensics would require logs of as few nodes as possible to prove culpability of as many Byzantine nodes as possible.