BFT storage with 2t + 1 data replicas
Christian Cachin · 2013
The cost of Byzantine Fault Tolerant (BFT) storage is the main concern preventing its adoption in practice. This cost stems from the need to maintain at least 3t + 1 replicas in different storage servers in the asynchronous model, so that t Byzantine replica faults can be tolerated. In this paper we show a fundamental separation of data from metadata for BFT storage, which allows us to develop a novel BFT storage protocol that reduces the number of data replicas to as few as 2t + 1, maintaining 3t + 1 replicas of metadata at (possibly) different servers. We also show that this is optimal, i.e., that 2t + 1 data replicas are needed even for crash-tolerant storage that uses a fault-free metadata service oracle. We show also that separating data from metadata for reducing the cost of BFT storage is not possible without cryptographic assumptions. However, our protocol uses only lightweight cryptographic hash functions. ar X iv