Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection

Abstract

Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively corrupt up to f < n/3 parties. Moreover, the problem is insoluble with f ≥ n/3 corruptions. However, Bracha's [Bra87] 1984 protocol (see also Ben-Or [Ben83]) achieved f < n/3 resilience at the cost of exponential expected latency 2θ(n), a bound that has never been improved in this model with f = ⌊(n- 1)/3⌋ corruptions.

Locations

• arXiv (Cornell University) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View