TY - JOUR
T1 - Communication complexity of byzantine agreement, revisited
AU - Abraham, Ittai
AU - Chan, T. H.Hubert
AU - Dolev, Danny
AU - Nayak, Kartik
AU - Pass, Rafael
AU - Ren, Ling
AU - Shi, Elaine
N1 - This work is partially supported by The Federmann Cyber Security Center in conjunction with the Israel National Cyber Directorate. T.-H. Hubert Chan was partially supported by the Hong Kong RGC under the Grants 17200418 and 17201220.
PY - 2023/3
Y1 - 2023/3
N2 - As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an adaptive adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary cannot erase the message that was already sent—henceforth we say that such an adversary cannot perform “after-the-fact removal”. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieve near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
AB - As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an adaptive adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary cannot erase the message that was already sent—henceforth we say that such an adversary cannot perform “after-the-fact removal”. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieve near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
KW - Byzantine agreement
KW - Communication complexity
KW - Lower bounds
KW - Subquadratic
UR - http://www.scopus.com/inward/record.url?scp=85134543912&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134543912&partnerID=8YFLogxK
U2 - 10.1007/s00446-022-00428-8
DO - 10.1007/s00446-022-00428-8
M3 - Article
AN - SCOPUS:85134543912
SN - 0178-2770
VL - 36
SP - 3
EP - 28
JO - Distributed Computing
JF - Distributed Computing
IS - 1
ER -