Attested append-only memory: making adversaries stick to their word
Researchers have made great strides in improving the fault toler-ance of both centralized and replicated systems against arbitrary (Byzantine) faults. However, there are hard limits to how much can be done with entirely untrusted components; for example, repli-cated state machines cannot tolerate more than a third of their replica population being Byzantine. In this paper, we investigate how minimal trusted abstractions can push through these hard lim-its in practical ways. We propose Attested Append-Only Memory (A2M), a trusted system facility that is small, easy to implement and easy to verify formally. A2M provides the programming ab-straction of a trusted log, which leads to protocol designs immune to equivocation – the ability of a faulty host to lie in different ways to different clients or servers – which is a common source of Byzan-tine headaches. Using A2M, we improve upon the state of the art in Byzantine-fault tolerant replicated state machines, produc-ing A2M-enabled protocols (variants of Castro and Liskov’s PBFT) that remain correct (linearizable) and keep making progress (live) even when half the replicas are faulty, in contrast to the previous up-per bound. We also present an A2M-enabled single-server shared storage protocol that guarantees linearizability despite server faults. We implement A2M and our protocols, evaluate them experimen-tally through micro- and macro-benchmarks, and argue that the im-proved fault tolerance is cost-effective for a broad range of uses, opening up new avenues for practical, more reliable services.