Improved Byzantine Agreement via Accountability

Abstract:

Distributed systems are everywhere in the modern world. In distributed systems, processes (or users) collaborate to achieve a common goal. At the heart of distributed systems lies the problem of having all processes to agree even if some processes are failing. This is captured in Byzantine agreement -- where all processes have to agree, even if some processes may deviate arbitrarily. Therefore, an efficient algorithm for Byzantine agreement is crucial.

A property important in both distributed systems and real life is accountability. In short, processes (or users) must be accountable for their actions and thus can be caught when they misbehave. Furthermore, if failures can be detected, then intuitively, Byzantine agreement can be done more efficiently. This thesis addresses the following key question: how much can accountability help in obtaining an efficient Byzantine agreement algorithm?

First, we look at how a strong notion of accountability can be used to do Byzantine agreement efficiently. A key insight here is that a malicious process can be forced to speak or face undeniable proof of misbehavior. This culminates in ADA-DARE, a Byzantine agreement with optimal resilience and asymptotically near-optimal communication complexity. Notably, ADA-DARE improves upon existing results by up to a linear factor.

Next, we look at how a weaker notion of accountability can be used to do repeated Byzantine agreement more efficiently. We observe that by allowing an honest process to be suspected alongside a malicious process, we can achieve a very efficient Byzantine agreement in the long run. From this observation, we build RARECOMPLAIN, a Byzantine agreement with optimal resilience, that has linear communication complexity and constant latency except for a bounded number of instances. Interestingly, RARECOMPLAIN shows that Byzantine agreement can be done essentially "for free".

Finally, we look at how (imperfect) accountability with the help of third parties can be used to obtain an efficient Byzantine agreement. Formally, we model Byzantine agreement where each process also receives (possibly inaccurate) prediction bits from an external party that classifies each process, whether it is honest or malicious. We showed that Byzantine agreement can be very fast when the prediction is very accurate, and still as fast as Byzantine agreement without prediction when the prediction is completely wrong. We also showed a matching lower bound, showing that our algorithm is asymptotically optimal.