` 4 D. Mazieres ownership.SCPisthefirstByzantineagreementprotocoltogiveeachparticipantmax- imumfreedominchosingwhichcombinationsofotherparticipants to trust. 3. FEDERATEDBYZANTINEAGREEMENTSYSTEMS This section introduces the federated Byzantine agreement (FBA) model. Like non- federated Byzantine agreement, FBA addresses the problem of updating replicated state, such as a transaction ledger or certificate tree. By agreeing on what updates to apply, nodes avoid contradictory, irreconcilable states. We identify each update by a unique slot from which inter-update dependencies can be inferred. For instance, slots maybeconsecutively numbered positions in a sequentially applied log. AnFBAsystemrunsaconsensusprotocolthatensuresnodesagreeonslotcontents. Anode v can safely apply update x in slot i when it has safely applied updates in all slots upon which i depends and, additionally, it believes all correctly functioning nodes will eventually agree on x for slot i. At this point, we say v has externalized x for slot i. The outside world may react to externalized values in irreversible ways, so a node cannot later change its mind about them. Achallenge for FBA is that malicious parties can join many times and outnumber honest nodes. Hence, traditional majority-based quorums do not work. Instead, FBA determines quorums in a decentralized way, by each node selecting what we call quo- rumslices. The next subsection defines quorums based on slices. The following subsec- tion provides some examples and discussion. Finally, we define the key properties of safety and liveness that a consensus protocol should hope to achieve. 3.1. Quorum slices In a consensus protocol, nodes exchange messages asserting statements about slots. We assume such assertions cannot be forged, which can be guaranteed if nodes are namedbypublickeyandtheydigitallysignmessages.Whenanodehearsasufficient set of nodes assert a statement, it assumes no functioning node will ever contradict that statement. We call such a sufficient set a quorum slice, or, more concisely, just a slice. To permit progress in the face of node failures, a node may have multiple slices, any one of which is sufficient to convince it of a statement. At a high level, then, an FBAsystemconsistsofalooseconfederation of nodes each of which has chosen one or moreslices. More formally: Definition (FBAS). A federated Byzantine agreement system, or FBAS, is a pair 2V ⟨V,Q⟩ comprising a set of nodes V and a quorum function Q ∶ V → 2 ⧵ {ç} speci- fying one or more quorum slices for each node, where a node belongs to all of its own X quorumslices—i.e., ∀v ∈ V,∀q ∈ Q(v),v ∈ q. (Note 2 denotes the powerset of X.) Definition (quorum). A set of nodes U ⊆ V in FBAS ⟨V,Q⟩ is a quorum iff U ≠ ç and U contains a slice for each member—i.e., ∀v ∈ U,∃q ∈ Q(v) such that q ⊆ U. A quorum is a set of nodes sufficient to reach agreement. A quorum slice is the subset of a quorum convincing one particular node of agreement. A quorum slice may besmallerthanaquorum.Considerthefour-nodesysteminFigure2,whereeachnode has a single slice and arrows point to the other members of that slice. Node v1’s slice {v ,v ,v } is sufficient to convince v of a statement. But v ’s and v ’s slices include v , 1 2 3 1 2 3 4 meaning neither v2 nor v3 can assert a statement without v4’s agreement. Hence, no agreement is possible without v4’s participation, and the only quorum including v1 is the set of all nodes {v ,v ,v ,v }. 1 2 3 4 Traditional, non-federated Byzantine agreement requires all nodes to accept the sameslices, meaning ∀v ,v ,Q(v ) = Q(v ). Because every member accepts every slice, 1 2 1 2 traditional systems do not distinguish between slices and quorums. The downside is