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 work, I investigate how minimal trusted abstractions can push through these hard limits in practical and meaningful ways. I propose Attested Append-Only Memory (A2M), a trusted system facility that is small, easy to implement and easy to formally verify. A2M provides the programming abstraction 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, a common source of Byzantine headaches. Using A2M, I improve upon the state of the art in Byzantine-fault tolerant replicated state machines, producing 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 upper bound. I also present an A2M-enabled single-server protocol that guarantees linearizability despite server faults. A2M-enabled protocols improve fault tolerance in a cost effective way for a broad range of uses, opening up new avenues for practical, more reliable services. Finally, I discuss Byzantine fault tolerance in long-term services that aims to achieve a new service property with A2M.