A New Look at Composition of Authenticated Byzantine Generals
This work addresses composition issues in fault-tolerant distributed systems, providing new insights for protocol design and the Universal Composability framework, but it is incremental as it builds on existing ABG models.
The paper tackles the problem of self-composition in Authenticated Byzantine Generals protocols, showing that no protocol can compose in parallel twice if n < 2t, and designing protocols that compose for any number of parallel executions when n ≥ 2t.
The problem of Authenticated Byzantine Generals (ABG) aims to simulate a virtual reliable broadcast channel from the General to all the players via a protocol over a real (point-to-point) network in the presence of faults. We propose a new model to study the self-composition of ABG protocols. The central dogma of our approach can be phrased as follows: Consider a player who diligently executes (only) the delegated protocol but the adversary steals some private information from him. Should such a player be considered faulty? With respect to ABG protocols, we argue that the answer has to be no. In the new model we show that in spite of using unique session identifiers, if $n < 2t$, there cannot exist any ABG protocol that composes in parallel even twice. Further, for $n \geq 2t$, we design ABG protocols that compose for any number of parallel executions. Besides investigating the composition of ABG under a new light, our work also brings out several new insights into Canetti's Universal Composability framework. Specifically, we show that there are several undesirable effects if one deviates from our dogma. This provides further evidence as to why our dogma is the right framework to study the composition of ABG protocols.