A Lower Bound on Communication Complexity for BA Sample Clauses

A Lower Bound on Communication Complexity for BA. As a third contribution, we give the first lower bound for communication complexity of BA, assuming parties have bounded computational resources. Concretely, we show that in the VDF model without additional trusted setup, no protocol can realize BA with overwhelming probability by multicasting fewer than O(√n) messages in the presence of 3 The construction in [KMS14] uses only a proof of sequential as opposed to a VDF. adaptive corruptions. In the multicast model of communication, honest parties are re- stricted to sending messages to all parties at once, whereas the adversary can send to only a subset of the parties. This models a setting in which parties communicate via a gossip network [GKPS18,AD15]. The cost of running the same protocol from the multicast model in the bilateral channel model [DS83] would be O(n3/2). We remark, however, that the multicast restriction is crucially used in the lower bound, and thus, a better communica- tion complexity might be possible in the bilateral channels model. Our lower bound builds on ideas of Xxxxxxx et al. [ACD+19] who show a bound for Byzantine broadcast in the multicast model without setup. Our bound has to overcome several technical challenges that arise when parties have limited computational resources. The adversary in our attack has to carry out a simulation of the protocol in its head (this is a standard technique used in lower bounds), which may require to query the VDF oracle. At the same time, the adversary must also participate in an actual execution of the protocol it is attacking, which, of course, also results in queries to the oracle. Thus, the key difficulty in our lower bound is to carefully balance the adversary’s limited budget of queries to VDF over the two executions of the protocol (real and simulated). Although our lower bound is relatively weak compared to most existing lower bounds in this area (which are quadratic, or of the form O(n) in the multicast model, respectively), we argue that it is still meaningful. Namely, protocols that require significantly above O(κ) multicasts are deemed impractical for large-scale settings with millions or even billions of users. This means that our bound essentially rules out efficient solutions in the VDF model unless further setup is assumed among the parties. Second, we point out that our lower bound actually holds in the relatively weak VDF-model and can likely be carried over to a less restrictive model (e.g., to the PoW model used by Bitcoin). I...