Attested append-only memory: making adversaries stick to their word

By Byung-Gon Chun, Petros Maniatis, Scott Shenker, John D. Kubiatowicz. Symposium on Operating Systems Principles, 2007

351 citations recorded by the source corpus.

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, we investigate how minimal trusted abstractions can push through these hard limits 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 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 -- which is a common source of Byzantine headaches. Using A2M, we 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. 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 experimentally through micro- and macro-benchmarks, and argue that the improved fault tolerance is cost-effective for a broad range of uses, opening up new avenues for practical, more reliable services.

Subfields: Computer Networks and Communications, Experimental and Cognitive Psychology

View Paper: https://www.semanticscholar.org/paper/d58f88930270a6ee0357806d8b0a0e1c086750e2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

BLOCKBENCH: A Framework for Analyzing Private Blockchains (2017, background): “be modified to incur fewer network messages [12].”
ROTE: Rollback Protection for Trusted Execution (2017, background): “Such approaches reduce the number of required replicas to 2 f + 1 [31, 32, 33, 34] or f + 1 [35].”
Augmented Smartphone Applications Through Clone Cloud Execution (2009, background): “At a high level, the trusted hardware receives inputs and simple programs written in a little, domain-specific language and sends out outputs and attestation, which is a generalized form of trusted primitives studied in [12, 13].”
Untangling Blockchain: A Data Processing View of Blockchain Systems (2017, methodology): “A2M [82] and Hybster [83] both exploit trusted hardware to reduce the number of replicas needed to tolerate f failures from 3 f + 1 to 2 f + 1 .”
Zyzzyva (2007, methodology): “Attested append-only memory [Chun et al. 2007] ensures correct operation even when half of the replicas are faulty under a stronger trust model where trusted hardware or software components implement A2M abstractions.”
Towards Scaling Blockchain Systems via Sharding (2018, methodology): “f groups of nodes that know each other. Shaded blocks are protocols that use trusted hardware. scaling BFT, we consider two trusted-hardware based PBFT variants: one follows the protocols specied in [18] and is called AHL, and the other adds the optimizations proposed in Byzcoin [32] and is dubbed A”
Efficient Byzantine Fault-Tolerance (2013, methodology): “presented another 2f þ 1 BFT algorithm based on similar ideas, A2M-PBFT-EA [13].”
SBFT: A Scalable and Decentralized Trust Infrastructure (2018, background): “Our protocol provides the same type of weak fairness guarantees as in PBFT; we leave for further work the question of adding stronger fairness properties to SBFT. A2M [29], TrInc [49] and Veronese et al. [73] use secure hardware to obtain non-equivocation.”
Mencius: Building Efficient Replicated State Machine for WANs (2008, positive): “We plan to explore a Byzantine version of Mencius by applying techniques such as Attested Append-only Memory [11].”
Enabling Security in Cloud Storage SLAs with CloudProof (2011, background): “Our scheme has the benefit that revocation and addition do not depend on the number of blocks in a family.”