The Protocol. ∈ ∈ { } ∈ { }{ }Definition 1 (Broadcast). A protocol among n parties P = p1, . . . , pn where a sender ps P inputs a value xs 0, 1 and each party pi computes an output yi 0, 1 achieves broadcast if the followingconditions are satisfied:1. (Validity). If ps is honest then each honest party pi computes yi = xi.2. (Consistency). All honest parties compute the same output value.∈ { } ∈ { }{ }Definition 2 (Consensus). A protocol among n parties P = p1, . . . , pn where each party pi inputs a value xi 0, 1 and each party pi computes an output yi 0, 1 achieves broadcast if the following conditions are satisfied:1. (Validity). If every honest party pi holds the same input value xi = b then each honest party pi computes yi = xi.2. (Consistency). All honest parties compute the same output value. 2.1 Overview− − ≥[ |{ }With n parties P = p1, . . . , pn of which t < n/2 are corrupted, one can achieve broadcast in t/2 + 4 synchronous rounds followed by a fullyasynchronous protocol. In general, d + 4 synchronous rounds are sufficient for d such that 3(t d) < n d. When t n/2 we need d + 5 rounds.The synchronous part is an n-party protocol that either detectably achieves agreement or wherein, alternatively, all honest parties detect a common set of some d parties that are corrupted — similar to a single phase in the protocols by Bar-Noy et al. [BDDS92]. We call this protocol Correct-Or-Detect Broadcast, d-CoD . We will choose d such that n − d > 3(t − d), i.e., that out of the N = n − d remainingnon-detected parties at mostT = t − d < N/3 are corrupted.The d-CoD protocol is followed by a protocol constructingproofs of participation, calledthe PoP protocol. There exists a verification algorithm ver which takes as input a bitstring pop and party id pj and outputs ver(pop, pj) ∈ {0, 1}. Below we write popj to mean that pop is a bit string for which ver(pop, pj) = 1 and we call such a popj a proof of participation for pj. After the execution of PoP all honest parties will hold some popj for all other honest pj. Furthermore, no popj will ever be constructed for a commonly detected pj. For pj which is not honest nor commonly detected some honest parties might hold a popj and some mightnot. In addition the proofs popj are transferable. I.e., they can be sent along with messages in the asynchronous phase and will be accepted by the recipient. The PoP protocol adds one extra synchronous rounds when t ≥ n/2.After the PoP protocol follows the asynchronous part, which is a conse...