Integrity-Preserving Replica Coordination for Byzantine Fault Tolerant Systems

The use of good random numbers is essential to the integrity of many mission-critical systems. However, when such systems are replicated for Byzantine fault tolerance, a serious issue arises, i.e., how do we preserve the integrity of the systems while ensuring strong replica consistency? Despite the fact that there exists a large body of work on how to render replicas deterministic under the benign fault model, the solutions regarding the random number control are often overly simplistic without regard to the security requirement, and hence, they are not suitable for practical Byzantine fault tolerance. In this paper, we present a novel integrity-preserving replica coordination algorithm for Byzantine fault tolerant systems. The central idea behind this algorithm is that all random numbers to be used by the replicas are collectively determined, based on the contributions made by a quorum of replicas, at least one of which is correct. We have implemented the algorithm in Java and conducted extensive experiments, in both a LAN testbed and an emulated WAN environment. We show that our algorithm is particularly suited for Byzantine fault tolerant systems operating in the LAN environment, or where replicas are connected by high-speed low-latency networks.