aniatis/publications/Thesis.pdf. It's a snapshot of the page taken as our search engine crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
HISTORIC INTEGRITY IN DISTRIBUTED SYSTEMS HISTORIC INTEGRITY IN DISTRIBUTED SYSTEMS
a dissertation
submitted to the department of computer science
and the committee on graduate studies
of stanford university
in partial fulfillment of the requirements
for the degree of
doctor of philosophy
Petros Maniatis
August 2003 c Copyright by Petros Maniatis 2003
All Rights Reserved
ii I certify that I have read this dissertation and that, in
my opinion, it is fully adequate in scope and quality as a
dissertation for the degree of Doctor of Philosophy.
Mary Baker
(Principal Adviser)
I certify that I have read this dissertation and that, in
my opinion, it is fully adequate in scope and quality as a
dissertation for the degree of Doctor of Philosophy.
Dan Boneh
I certify that I have read this dissertation and that, in
my opinion, it is fully adequate in scope and quality as a
dissertation for the degree of Doctor of Philosophy.
John Mitchell
Approved for the University Committee on Graduate
Studies.
iii Abstract
In an all-digital, all-online setting, long-term secure record-keeping is a dicult task.
The record-keeping problem comes up with increasing frequency, as we migrate to
exclusively digital ways of transacting business. Accountability requires information
about the content and the timing of business transactions. In the digital world,
ideally, we should be able to tell with conviction when a digital event occurred
with respect to other events such as storing a purchase receipt on a hard drive or
signing a contract digitally and we should be able to avert tampering with events
that have been committed to history.
Unfortunately, data on memory, on disk or on tape can change without leaving
a trace of when and how they were written. Especially in a complex loosely-coupled
distributed system that involves many interacting individuals, computers and organi-
zations over the Internet, the task of maintaining the history of events as they happen
for later perusal can be a management, security and storage nightmare.
In this thesis, we address the issue of historic integrity in large, loosely-coupled
distributed systems, and ways to ensure this integrity in a secure, yet ecient man-
ner. We describe Timeweave, a framework that allows the dierent participants in
a distributed system to maintain their own recorded histories, while contributing to
the maintenance and protection against tampering of collective history for the entire
system. Timeweave requires minimal trust among individual components of the sys-
tem and can survive the temporary or permanent departure of components from the
system. Finally, Timeweave can operate eciently in distributed systems numbering
a few thousand participating components for up to a few decades worth of history,
at overheads aordable to even medium-grade consumer systems available today.
iv Acknowledgments
It is certainly common for a soon-to-be-done graduate student to proclaim his bewil-
derment at the possibility of perhaps, maybe conceivably nishing. I do not deviate
from the norm: it is in sheer amazement and surprise that I write these lines. Fortu-
nately, I have been alone in my amazement all along. Many were those who believed
in me enough to push me forward when all I wanted to do was give up and open a
creperie, instead.
My advisor, Mary Baker, bore the brunt of keeping me on course throughout
my time in graduate school. She taught me how to do research, how to write about
research, and how to talk about research. She gave me room to explore what interested
me early on and never lost faith or patience, even after several false starts. For 7
years, she was my most ardent supporter, promoting and publicizing my work, and
keeping me encouraged and unencumbered in my path. She even laughed at my jokes,
including the non-funny ones. I could not have hoped for a better advisor.
For briefer periods, I was fortunate to work with Dan Boneh, Mike Genesereth, Leo
Guibas, Mark Handley, David Marimont, John Mitchell, Sylvia Ratnasamy, David
Rosenthal, Andreas Rouvas, Scott Shenker, Doug Terry, and Aphrodite Tsalgatidou,
who gave me the benet of their time, advice, expertise, support and enthusiasm. I
was equally fortunate to collaborate and commiserate with my fellow members
of the MosquitoNet group: Guido Appenzeller, Stuart Cheshire, TJ Giuli, Antonios
Hondroulis, Kevin Lai, Sergio Marti, Ichiro Okajima, Elliot Poger, Mema Roussopou-
los, Tyron Stading, Ed Swierk, Diane Tang, and Xinhua Zhao; I learned from them
much more than I gave in return.
Inescapably, I owe a big debt of gratitude to the wonderful friends who stood by
v me during the many stages of the graduate process: the Rains 14A bowling group
(Sam Fraidin, Bill Graham, and Jim Geist), Joe Barco, TJ Giuli, Roy Goldman, Luis
Gravano, Antonios Hondroulis, Sergio Marti, and Katerina Nickolopoulos. Kevin
Lai, my very own crisis management center, went beyond the call of duty oering
advice especially advice not asked but clearly needed and a role model for my
future career. And Mema Roussopoulos, my oce-mate, favorite co-author, personal
cheerleader and best friend, taught me by example that being kind and always smiling
are traits that can belong to a hard-working, brilliant woman. Their unconditional
friendship made the trip as worthwhile as the destination.
Finally, I thank my family for making the trip possible in the rst place: my mom
and brother who, months after the loss of my dad, saw me also y 7000 miles away,
practically forever, without questioning my need to continue my studies on the other
side of the world or ever withholding their support; and my partner Ed Swierk, the
least selsh and judgmental person I know, who against all odds, despite my stress
and my insecurities and my frustrations and my occasional ts of depression, kept me
motivated and content, and managed to make my years in the doctoral program the
best and happiest of my life. I wholeheartedly dedicate this thesis to them.
vi Contents
Abstract
iv
Acknowledgments
v
1 Introduction
1
1.1
Contributions of This Thesis . . . . . . . . . . . . . . . . . . . . . . .
6
1.2
Structure of This Thesis . . . . . . . . . . . . . . . . . . . . . . . . .
7
2 Background
9
2.1
Logical Time and Clocks . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2
Cryptographic Hash Functions . . . . . . . . . . . . . . . . . . . . . .
11
2.3
Authenticated Data Structures
. . . . . . . . . . . . . . . . . . . . .
12
2.4
Secure Time Stamping . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.5
Secure Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3 Authenticated Append-only Skip Lists
17
3.1
Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.1.1
AASL construction . . . . . . . . . . . . . . . . . . . . . . . .
19
3.1.2
AASL Membership Proofs . . . . . . . . . . . . . . . . . . . .
26
3.1.3
AASL Evolution . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.1.4
Temporal Ordering . . . . . . . . . . . . . . . . . . . . . . . .
39
3.2
Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.2.1
Tamper-Evident Digests in AASLs . . . . . . . . . . . . . . .
41
3.2.2
Membership Proofs in AASLs . . . . . . . . . . . . . . . . . .
46
vii 3.2.3
AASL Evolution . . . . . . . . . . . . . . . . . . . . . . . . .
51
3.3
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
3.4
Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . .
68
3.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4 RBB-Trees
73
4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
4.2
Authenticated Search Trees . . . . . . . . . . . . . . . . . . . . . . .
76
4.3
Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.3.1
Storage Considerations . . . . . . . . . . . . . . . . . . . . . .
79
4.3.2
Persistence
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
4.4
Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
4.5
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
4.6
Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . .
90
4.7
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
5 Timeweave
94
5.1
The Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
5.2
Secure Timelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
5.3
Timeline Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . .
98
5.3.1
Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
5.3.2
Cross-Timeline Ordering . . . . . . . . . . . . . . . . . . . . . 104
5.3.3
Historic Integrity . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.3.4
Historic Survivability . . . . . . . . . . . . . . . . . . . . . . . 112
5.4
Security Analysis . . . . . . . . . . . . . . . . . .