Attested Append-Only Memory: Making Adversaries Stick to Their Word

Researchers have made great strides in improving the fault tolerance 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, replicated state machines cannot tolerate more than a third of their replica population being Byzantine. In this paper, the authors investigate how minimal trusted abstractions can push through these hard limits in practical ways. They propose Attested Append-Only Memory (A2M), a trusted system facility that is small, easy to implement and easy to verify formally.