Towards Practical Communication in Byzantine-Resistant DHTs
Maxwell Young, Aniket Kate, Ian Goldberg, Martin Karsten · IEEE/ACM Transactions on Networking · 2013
There are several analytical results on distributed hash tables (DHTs) that can tolerate Byzantine faults. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. For example, a simple scheme used in many Byzantine fault-tolerant DHT constructions ofnnodes requiresO(log3n) messages; this is likely impractical for real-world applications. The previous best known message complexity isO(log2n) in expectation. However, the corresponding protocol suffers from prohibitive costs owing to hidden constants in the asymptotic notation and setup costs. In this paper, we focus on reducing the communication costs against a computationally bounded adversary. We employ threshold cryptography and distributed key generation to define two protocols, both of which are more efficient than existing solutions. In comparison, our first protocol is deterministic withO(log2n) message complexity, and our second protocol is randomized with expectedO(logn) message complexity. Furthermore, both the hidden constants and setup costs for our protocols are small, and no trusted third party is required. Finally, we present results from microbenchmarks conducted over PlanetLab showing that our protocols are practical for deployment under significant levels of churn and adversarial behavior.