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

ABSTRACT

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.

REFERENCES

• 1: Amazon S3. http://aws.amazon.com/s3/.
• 2: Intel Active Management Technology (AMT). http://www.intel.com/technology/platform-technology/intel-amt/index.htm.
• 3: Java. http://java.sun.com/.
• 4: SFSlite. http://www.okws.org/doku.php?id=sfslite.
• 5: Trusted Computing Group (TCG). http://www.trustedcomputinggroup.org/.
• 6: Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 7: Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 8: T. W. Arnold , L. P. Van Doom, The IBM PCIXCC: a new cryptographic coprocessor for the IBM eServer, IBM Journal of Research and Development, v.48 n.3-4, p.475-487, May 2004
• 9: M. H. Azadmanesh , R. M. Kieckhafer, New Hybrid Fault Models for Asynchronous Approximate Agreement, IEEE Transactions on Computers, v.45 n.4, p.439-449, April 1996 [doi>10.1109/12.494101]
• 10: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 11: Stefan Berger , Ramón Cáceres , Kenneth A. Goldman , Ronald Perez , Reiner Sailer , Leendert van Doorn, vTPM: virtualizing the trusted platform module, Proceedings of the 15th conference on USENIX Security Symposium, p.21-21, July 31-August 04, 2006, Vancouver, B.C., Canada
• 12: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 13: Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002 [doi>10.1145/571637.571640]
• 14: James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , Liuba Shrira, HQ replication: a hybrid quorum protocol for byzantine fault tolerance, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 15: S. Haber and W. S. Stornetta. How to time-stamp a digital document. Journal of Cryptology, 3(2):99--111, 1991.
• 16: Andreas Haeberlen , Petr Kouznetsov , Peter Druschel, PeerReview: practical accountability for distributed systems, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 17: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 18: Galen Hunt , Mark Aiken , Manuel Fähndrich , Chris Hawblitzel , Orion Hodson , James Larus , Steven Levi , Bjarne Steensgaard , David Tarditi , Ted Wobber, Sealing OS processes to improve dependability and safety, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 19: Galen C. Hunt , James R. Larus, Singularity: rethinking the software stack, ACM SIGOPS Operating Systems Review, v.41 n.2, p.37-49, April 2007 [doi>10.1145/1243418.1243424]
• 20: Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 21: R. M. Kieckhafer , M. H. Azadmanesh, Reaching Approximate Agreement with Mixed-Mode Faults, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.53-63, January 1994 [doi>10.1109/71.262588]
• 22: Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 23: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 24: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 25: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 26: Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
• 27: J. Li and D. Mazißres. Beyond One-third Faulty Replicas in Byzantine Fault Tolerant Systems. In Proc. of NSDI, 2007.
• 28: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.569-578, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258650]
• 29: Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000 [doi>10.1109/69.842262]
• 30: Petros Maniatis , Mary Baker, Secure History Preservation Through Timeline Entanglement, Proceedings of the 11th USENIX Security Symposium, p.297-312, August 05-09, 2002
• 31: Larry McVoy , Carl Staelin, lmbench: portable tools for performance analysis, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.23-23, January 22-26, 1996, San Diego, CA
• 32: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 33: Athicha Muthitacharoen , Robert Morris , Thomer M. Gil , Benjie Chen, Ivy: a read/write peer-to-peer file system, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060293]
• 34: M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151--158, 1991.
• 35: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 36: Rodrigo Rodrigues , Miguel Castro , Barbara Liskov, BASE: using abstraction to improve fault tolerance, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 37: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 38: P. Thambidurai and Y.-K. Park. Interactive consistency with multiple failure modes. In Proc. of SRDS, 1988.
• 39: Jian Yin , Jean-Philippe Martin , Arun Venkataramani , Lorenzo Alvisi , Mike Dahlin, Separating agreement from execution for byzantine fault tolerant services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 40: Aydan R. Yumerefendi , Jeffrey S. Chase, Strong accountability for network storage, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.6-6, February 13-16, 2007, San Jose, CA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

General Terms:
Algorithms, Design, Reliability, Security

Keywords:
attested append-only memory, byzantine-fault tolerance, equivocation, replicated state machines, shared storage