Detailed Proof of Proposition 16. As described in Section 5.1, suppose there is an algorithm A that solves Byzantine agreement with ℓ ≤ t. We consider only executions of A with some fixed set of ℓ Byzantine processes, chosen so that each of the ℓ identities is held by one Byzantine process. We use Ck to denote a configuration at end of round k. From Ck, the system can reach different possible configu- rations Ck+1. In an execution of algorithm A, the config- uration Ck+1 is completely determined by (1) Ck and (2) the messages sent by the Byzantine processes to the correct processes in round k + 1. (The messages sent by correct processes are determined by Ck and X.)
