Consensus in the Presence of Partial Synchrony 311 5.2 A DISTRIBUTED CLOCK FOR BYZANTINE FAULTS WITH AUTHENTICA- TION. The new clock is very similar to the one just described. We only explain the differences. Here we assume N 2 2t + 1. An i-claim is a signed message “I have broadcast an i-tick.” An i+-claim is a j-claim for any j 2 i. For i 2 1, an i-tick is the message “(i, i-proof),” where a l-proof is the empty string and where an i-proof (i > 1) is a list of t + 1 (i - I)+- claims each signed by a different processor. An i’-tick is a j-tick for any j 2 i. The definitions of broadcast an i-tick and broadcast an i-claim are the same as before. The master clock C: N + N is defined by C(s) = maximum j such that some correct processor has broadcast a j-tick by time s. The private clock ci: N + N is defined by ci(S) = maximum j such that pi has received t + 1 j’-claims (from different sources), either directly, or indirectly as part of a tick, by time s. The definition of the clock protocol is the same as before with the addition that, whenever a processor sends a (b + I)-claim in the procedure CLAIM(b), it attaches the largest size tick that it can construct (this will always be a (b + l)+-tick). A correct processor will ignore any received j-claim if it does not come with an attached j+-tick. The reason for this modification is so that correct processors will not accept claims that are much too large from faulty processors and incorporate these large claims into proofs. LEMMA 5.8. Lemmas 5.1-5.7 holdfor the authenticated Byzantine clock. PROOF. The proofs are virtually identical to the proofs for the unauthenticated Byzantine clock, and most details are omitted. The major differences are the following: The proof of Lemma 5.1 is easier since there is only one case. Lettingj = ci(s), processor pi has received t + 1 j+-claims from different processors, at least one of which must be correct. Since a correct processor sends a j+-claim only after it has broadcast a j-tick, we have C(s) L j by definition of the master clock. The proofs of Lemmas 5.2 and 5.3 are unchanged. In the proof of Lemma 5.4, change “2t + 1” to ‘2 + 1.” In the proof of Lemma 5.5, letting j = C(s), we can only say that at least one correct processor has broadcast a j-tick by time s. However, this j-tick contains a j-proof consisting of t + 1 (j - I)+-claims, so we can conclude that ci(S + 3N@ + D) 2 j - 1 for all correct pi as before. The proof of Lemma 5.6 is changed similarly. The proof of Lemma 5.7 follows from previous lemmas by calculations and is unchanged. 0 We need one more lemma to support our claim that the number of message bits sent by correct processors is bounded above by a polynomial in GST, N, A, and a. LEMMA 5.9. For all s z 0, the largest tick sent by any processor (correct or faulty) at real time s has size at most C(s) + 2. PROOF. A j-tick sent at time s contains t + 1 (j - I)+-claims, at least one of which was sent by a correct processor. The conclusion now follows from Lemma 5.2. Cl