` 2 D. Mazieres We also show that SCP is free from blocked states—in which consensus is no longer possible—unless participant failures make it impossible to satisfy trust dependencies. SCPisthefirstprovablysafeconsensusmechanismtoenjoyfourkeypropertiessimul- taneously: —Decentralized control. Anyone is able to participate and no central authority dictates whose approval is required for consensus. —Lowlatency.Inpractice,nodescanreachconsensusattimescaleshumansexpect for web or payment transactions—i.e., a few seconds at most. —Flexible trust. Users have the freedom to trust any combination of parties they see fit. For example, a small non-profit may play a key role in keeping much larger institutions honest. —Asymptoticsecurity. Safety rests on digital signatures and hash families whose parameters can realistically be tuned to protect against adversaries with unimag- inably vast computing power. SCPhasapplications beyond financial markets for ensuring organizations perform importantfunctionshonestly. Anexampleiscertificateauthorities(CAs),wholiterally holdthekeystotheweb.ExperienceshowsthatCAssignincorrectcertificatesthatget used in the wild [Microsoft 2013; Langley 2015]. Several proposals address this prob- lem through certificate transparency [Kim et al. 2013; Laurie et al. 2013; Basin et al. 2014;Melaraetal.2014].Certificatetransparencyallowsuserstoexaminethehistory of certificates issued for any given entity and detect attempts by CAs to change an en- tity’s public key without the endorsement of the previous key. SCP holds the potential to strengthen the indelible certificate history at the core of certificate transparency. Demandingglobalconsensusoncertificatehistory amongadecentralized group of au- ditors would make it harder to backpedal and override previously issued certificates. The next section discusses previous approaches to consensus. Section 3 defines fed- erated Byzantine agreement (FBA) and lays out notions of safety and liveness ap- plicable in the FBA model. Section 4 discusses optimal failure resilience in an FBA system, thereby establishing the security goals for SCP. Section 5 develops federated voting, a key building block of the SCP protocol. Section 6 presents SCP itself, proving safety andfreedomfromblockedstates.Section7discusseslimitationsofSCP.Finally, Section 8 summarizes results. For readers less familiar with mathematical notation, Appendix A defines some symbols used throughout the paper. 2. RELATEDWORK Figure1summarizeshowSCPdiffersfrompreviousconsensusmechanisms.Themost famous decentralized consensus mechanism is the proof-of-work scheme advanced by Bitcoin [Nakamoto 2008]. Bitcoin takes a two-pronged approach to consensus. First, it provides incentives for rational actors to behave well. Second, it settles transactions through a proof-of-work [Dwork and Naor 1992] algorithm designed to protect against ill-behaved actors who do not possess the majority of the system’s computing power. Bitcoin has overwhelminglydemonstratedtheappealofdecentralizedconsensus[Bon- neauetal. 2015]. Proof of work has limitations, however. First, it wastes resources: by one estimate from 2014, Bitcoin might consume as much electric power as the entire country of Ire- land [O’Dwyer and Malone 2014]. Second, secure transaction settlement suffers from expected latencies in the minutes or tens of minutes [Karame et al. 2012]. Finally, in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security. Given non-rational attackers—or ones with extrinsic incentives to sabotage