` 12 D. Mazieres 5.1. Voting with open membership Acorrect node in a Byzantine agreement system acts on a statement a only when it knows that other correct nodes will never agree to statements contradicting a. Most protocols employ voting for this purpose. Well-behaved nodes vote for a statement a only if it is valid. Well-behaved nodes also never change their votes. Hence, in central- ized Byzantine agreement, it is safe to accept a if a quorum comprising a majority of well-behaved nodes has voted for it. We say a statement is ratified once it has received the necessary votes. Inafederatedsetting,wemustadaptvotingtoaccommodateopenmembership.One difference is that a quorum no longer corresponds to a majority of well-behaved nodes. However, the majority requirement primarily serves to ensure quorum intersection of well-behaved nodes, which Section 4.1 already adapted to FBA. Another implication of open membership is that nodes must discover what constitutes a quorum as part of the voting process. To implement quorum discovery, a protocol should specify Q(v) in all messages from v. Definition (vote). A node v votes for an (abstract) statement a iff (1) v asserts a is valid and consistent with all statements v has accepted, and (2) v asserts it has never voted against a—i.e., voted for a statement that contra- dicts a—and v promises never to vote against a in the future. Definition (ratify). A quorum U ratifies a statement a iff every member of U votes a a for a. A node v ratifies a iff v is a member of a quorum U that ratifies a. a THEOREM4. Two contradictory statements a and ā cannot both be ratified in an FBASthatenjoysquorumintersection and contains no ill-behaved nodes. PROOF. By contradiction. Suppose quorum U ratifies a and quorum U ratifies ā. 1 2 By quorum intersection, ∃v ∈ U ∩ U . Such a v must have illegally voted for both a 1 2 andā, violating the assumption of no ill-behaved nodes. THEOREM5. Let ⟨V,Q⟩ be an FBAS enjoying quorum intersection despite B, and suppose B contains all ill-behaved nodes. Let v and v be two nodes not in B. Let a and 1 2 ā be contradictory statements. If v ratifies a then v cannot ratify ā. 1 2 PROOF. Bycontradiction. Suppose v ratifies a and v ratifies ā. By definition, there 1 2 mustexistaquorumU containingv thatratifiedaandquorumU containingv that 1 1 2 2 ratified ā. By Theorem 1, since U ⧵ B ≠ ç and U ⧵ B ≠ ç, both must be quorums 1 2 B B B in ⟨V,Q⟩ , meaning they ratified a and ā respectively in ⟨V,Q⟩ . But ⟨V,Q⟩ enjoys quorumintersection and has no ill-behaved nodes, so Theorem 4 tell us a and ā cannot both be ratified. THEOREM6. Twointact nodes in an FBAS with quorum intersection cannot ratify contradictory statements. PROOF. Let B be the set of befouled nodes. By Theorem 3, B is a DSet. By the defi- nition of DSet, ⟨V,Q⟩ enjoys quorum intersection despite B. By Theorem 5, two nodes not in B cannot ratify contradictory statements. 5.2. Blocking sets In centralized consensus, liveness is an all-or-nothing property of the system. Either a unanimously well-behaved quorum exists, or else ill-behaved nodes can prevent the rest of the system from accepting new statements. In FBA, by contrast, liveness may differ across nodes. For instance, in the tiered quorum example of Figure 3, if middle