Security 2002 Paper
[Security '02 Tech Program Index]
Secure History Preservation through
Figure 1 illustrates the first few time steps of a secure timeline. In the figure, the new timeline authenticator is also fed into the new state of the system. Depending on the definition of the state digest function, a new state of the service can be shown to be fresh, i.e., to have followed the computation of the authenticator for the previous time step. In Time Stamping Services, this places the time stamp of a document between two rounds of the service. In the Key Archival Service, this bounds the time interval during which a change in the Certification Authority (new certificate, revocation, or refresh) has occurred. In a CRT timeline system, this bounds the time when a revocation database was built. Some authenticated dictionaries can be shown to be fresh(e.g., ), and we explain how we handle freshness in Section 5.2.
Secure timelines can be used to answer two basic kinds of questions: existence questions and temporal precedence questions. Existence questions are of the form ``is the -th system state?'', and are used to establish that the service exhibited a certain kind of behavior at a particular phase in its history. In the time stamping example, an existence question could be ``is the round hash at time ?'' A positive answer allows a client to verify the validity of a time stamp from round , since time stamps from round are authenticated with the root hash of that round. Temporal precedence questions are of the form ``did state occur before state ?''. In time stamping, answers to precedence questions can establish precedence between two time stamped documents.
Answers to both existence and temporal precedence questions are provable. Given the last authenticator in the timeline, to prove the existence of a state in the timeline's past I have to produce a one-way path--a sequence of applications of one-way functions--from that state to the current timeline authenticator. Similarly, to prove that state precedes state , I have to show that there exists a one-way path from state to state . For example, in Figure 1, the path from to , and then to is one-way and establishes that state occurred before . Extending this path to provides an existence proof for state , if the verifier knows that is the latest timeline authenticator.
Secure timelines are a general mechanism for temporal authentication. As with any other authentication mechanism, timeline proofs are useful only if the authenticator against which they are validated is itself secure and easily accessible to all verifiers, i.e., the clients within the service domain. In other words, clients must be able to receive securely authenticator tuples of the form from the service at every time step, or at coarser intervals. This assumes that clients have a means to open authenticated channels to the service. Furthermore, there must be a unique tuple for every time step . Either the service must be trusted by the clients to maintain a unique timeline, or the timeline must be periodically ``anchored'' on an unconditionally trusted write-once publication medium, such as a paper journal or popular newspaper. The latter technique is used by some commercial time stamping services , to reduce the clients' need to trust the service.
For the remainder of this paper, ``time '' means the state of the service that is current right before timeline element has been published, as well as the physical time period between the publication of the timeline authenticators for time steps and . For service , we denote time as , the associated timeline authenticator as and the precedence proof from to as .
In the previous section, we describe how a secure timeline can be used by the clients within a service domain to reason about the temporal ordering of the states of the service in a provable manner. In so doing, the clients of the service have access to tamper-evident historic information about the operation of the service in the past.
However, the timeline of service does not carry much conviction before a client who belongs to a different, disjoint service domain , i.e., a client who does not trust service or the means by which it is held accountable. Consider an example from time stamping where Alice, a client of TSS , wishes to know when Bob, a client of another TSS , time stamped a particular document . A time stamping proof that links to an authenticator in 's timeline only is not convincing or useful to Alice, since she has no way to compare temporally time steps in 's timeline to her own timeline, held by .
This is the void that timeline entanglement fills. Timeline entanglement creates a provable temporal precedence from a time step in a secure timeline to a time step in another independent timeline. Its objective is to allow a group of mutually distrustful service domains to collaborate towards maintaining a common, tamper-evident history of their collective timelines that can be verified from the point of view (i.e., within the trust domain) of any one of the participants.
In timeline entanglement, each participating service domain maintains its own secure timeline, but also keeps track of the timelines of other participants, by incorporating authenticators from those foreign timelines into its own service state, and therefore its own timeline. In a sense, all participants enforce the commitment of the timeline authenticators of their peers.
In Section 4.1, we define timeline entanglement with illustrative examples and outline its properties. We then explore in detail three aspects of timeline entanglement: Secure Temporal Mappings in Section 4.2, the implications of dishonest timeline maintainers in Section 4.3, and Historic Survivability in Section 4.4.
Timeline entanglement is defined within the context of an entangled service set. This is a dynamically changing set of service domains. Although an entangled service set where all participating domains offer the same kind of service is conceivable--such as, for example, a set of time stamping services--we envision many different service types, time stamping services, certification authorities, historic records services, etc., participating in the same entangled set. We assume that all participating services know the current membership of the entangled service set, although inconsistencies in this knowledge among services does not hurt the security of our constructs below. We also assume that members of the service set can identify and authenticate each other, either through the use of a common public key infrastructure, or through direct out-of-band key exchanges.
Every participating service defines an independent sampling method to select a relatively small subset of its logical time steps for entanglement. For example, a participant can choose to entangle every -th time step. At every time step picked for entanglement, the participant sends an authenticated message that contains its signed logical time and timeline authenticator to all other participants in the entangled service set. This message is called a timeline thread. A timeline thread sent from at time is denoted as and has the form . represents 's signature on message .
When participant receives a correctly signed timeline thread from participant , it verifies the consistency of that thread with its local view of collective history and then archives it. Thread is consistent with 's local view of collective history if it can be proved to be on the same one-way path (hash chain) as the last timeline authenticator of that knows about (see Figure 2). Towards this goal, includes the necessary temporal precedence proof, as described in Section 3, along with the thread that it sends to . In the figure, when thread reaches , the most recent timeline authenticator of that knows is . Along with the thread, sends the precedence proof from its time to time . As a result, can verify that the new thread carries a ``legitimate'' timeline authenticator from , one consistent with history. If everything checks out, archives the new timeline authenticator and associated precedence proof in its local thread archive.
Thread archives store tuples of the form . A thread archive serves two purposes: first, it maintains a participant's local knowledge of the history of the entangled service set. Specifically, it archives proof that every participant it knows about maintains a consistent timeline. It accomplishes this by simply storing the threads, which are snapshots in the sender's timeline, and supporting precedence proofs, which connect these snapshots in a single one-way chain. The second purpose of the thread archive is to maintain temporal precedence proofs between every foreign thread it contains and local timeline steps. It accomplishes this by constructing a one-way digest of its contents as they change, and then using that digest along with the system state digest, to derive the next local timeline authenticator (Section 5.2 describes how the thread archive is implemented). In the figure, 's system state and updated thread archive are combined into , which then participates in the computation of the next timeline authenticator .
Participant responds to the newly reported timeline authenticator with an entanglement receipt. This receipt proves that the next timeline authenticator that produces is influenced partly by the archiving of the thread it just received. The receipt must convince of three things: first, that its thread was archived; second, that the thread was archived in the latest--``freshest''--version of 's thread archive; and, third, that this version of the thread archive is the one whose digest is used to derive the next timeline authenticator that produces. As a result, the entanglement receipt that returns to for the entanglement of thread consists of three components: first, a precedence proof from the last of 's timeline authenticators that knows about, , to 's timeline authenticator right before archiving 's new thread; second, an existence proof showing that the timeline thread is archived in the latest, freshest version of 's thread archive after the last authenticator was computed; and, third, a one-way derivation of the next timeline authenticator of from the new version of the thread archive and the current system state . It is now 's turn to check the validity of the proofs in the entanglement receipt. If all goes well, stores the proof of precedence and reported timeline authenticator from in its receipt archive. This concludes the entanglement process from time to time .
The receipt archive is similar to the thread archive; it stores entanglement receipts that the participant receives in response to its own timeline threads.
After the entanglement of time with time , both and have in their possession portable temporal precedence proofs ordering 's past before 's future. Any one-way process at whose result is included in the derivation of or earlier timeline authenticators at can be shown to have completed before any one-way process at that includes in its inputs or later timeline authenticators at .
In this definition of timeline entanglement, a participating service entangles its timeline at the predetermined sample time steps with all other services in the entangled service set (we call this all-to-all entanglement). In this work we limit the discussion to all-to-all entanglement only, but we describe a more restricted, and consequently less expensive, entanglement model in future work (Section 7).
The primary benefit of timeline entanglement is its support for secure temporal mapping. A client in one service domain can use temporal information maintained in a remote service domain that he does not trust, by mapping that information onto his own service domain. This mapping results in some loss of temporal resolution--for example, a time instant maps to a positive-length time interval. We describe secure temporal mapping in Section 4.2.
Timeline entanglement is a sound method of expanding temporal precedence proofs outside a service domain; it does not prove incorrect precedences. However it is not complete, that is, there are some precedences it cannot prove. For example, it is possible for a dishonest service to maintain clandestinely two timelines, essentially ``hiding'' the commitment of some of its system states from some members of the entangled service set. We explore the implications of such behavior in Section 4.3.
Finally, we consider the survivability characteristics of temporal proofs beyond the lifetime of the associated timeline, in Section 4.4.
Temporal mapping allows a participating service to map onto its own timeline a time step from the timeline of another participant . This mapping is denoted by . Since and do not trust each other, the mapping must be secure; this means it should be practically impossible for to prove to that , if occurred before or at , or after .
Figure 3 illustrates the secure temporal mapping . To compute the mapping, requires only local information from its thread and receipt archives. First, it searches in its receipt archive for the latest entanglement receipt that sent back before or at time , receipt in the example. As described in Section 4, this receipt proves to that its time occurred before 's time .
Then, searches in its thread archive for the earliest thread that sent it after time , which is thread in the example. This thread proves to that its time occurred at or after time . Recall, also, that when received in the first place, it had also received a temporal precedence proof from to , which in the straightforward hash chain case, also includes the system state digest for . Now has enough information to conclude that .
Since has no reason to believe that maintains its timeline in regular intervals, there is no more that can assume about the temporal placement of state within the interval . This results in a loss of temporal resolution; in the figure, this loss is illustrated as the difference between the length on 's timeline from to (i.e., the ``duration'' of time step ) and the length of the segment on 's timeline from to (the duration of ). This loss is higher when and exchange thread messages infrequently. It can be made lower, but only at the cost of increasing the frequency with which and send threads to each other, which translates to more messages and more computation at and . We explore this trade-off in Section 6.
Secure time mapping allows clients within a service domain to determine with certainty the temporal ordering between states on their own service and on remote, untrusted service domains. Going back to the time stamping example, assume that Alice has in her possession a time stamp for document in her own service domain , which links it to local time , and she has been presented by Bob with a time stamp on document in his service domain , which links Bob's document to time . Alice can request from the time mapping , shown above to be . With this information, Alice can be convinced that her document was time stamped after Bob's document was, regardless of whether or not Alice trusts Bob or .
In the general case, not all time steps in one timeline map readily to another timeline. To reduce the length of temporal precedence proofs, we use hash skip lists (Section 5.1) instead of straightforward hash chains in Timeweave, our prototype. Temporal precedence proofs on skip lists are shorter because they do not contain every timeline authenticator from the source to the destination. In timelines implemented in this manner, only time steps included in the skip list proof can be mapped without the cooperation of the remote service. For other mappings, the remote service must supply additional, more detailed precedence proofs, connecting the time authenticator in question to the time authenticators that the requester knows about.
Timeline entanglement is intended as an artificial enlargement of the class of usable, temporal orderings that clients within a service domain can determine undeniably. Without entanglement, a client can determine the provable ordering of events only on the local timeline. With entanglement, one-way paths are created that anchor time segments from remote, untrusted timelines onto the local timeline.
However, the one-way properties of the digest and hash functions used make timelines secure only as long as everybody is referring to the same, single timeline. If, instead, a dishonest service maintains clandestinely two or more timelines or branches of the same timeline, publishing different timeline authenticators to different subsets of its users, then that service can, in a sense, revise history. Just  identified such an attack against early time stamping services. Within a service domain, this attack can be foiled by enforcing that the service periodically commit its timeline on a write-once, widely published medium, such as a local newspaper or paper journal. When there is doubt, a cautious client can wait to see the precedence proof linking the timeline authenticator of interest to the next widely published authenticator, before considering the former unique.
Unfortunately, a similar attack can be mounted against the integrity of collective history, in an entangled service set. Entanglement, as described in Section 4, does not verify that samples from 's timeline that are archived at and are identical. If is malicious, it can report authenticators from one chain to and from another to , undetected (see Figure 4). In the general case, this does not dilute the usability of entanglement among honest service domains. Instead, it renders unprovable some interactions between honest and dishonest service domains. More importantly, attacks by a service against the integrity of its own timeline can only make external temporal precedence information involving that timeline inconclusive; such attacks cannot change the temporal ordering between time steps on honest and dishonest timelines. Ultimately, it is solely the clients of a dishonest service who suffer the consequences.
Consider, for instance, the scenario of Figure 4. Dishonest service has branched off its originally unique timeline into two separate timelines at its time . It uses the top branch, with times , , etc., in its entanglements with service , and its bottom branch, with times , , etc., in its entanglements with service . From 's point of view, event is incorporated in 's state and corresponding timeline at time . From 's point of view, however, event seems never to have happened. Since does not appear in the branch of 's timeline that is visible to , 's clients cannot conclusively place event in time at all. Therefore, only the client of who is responsible for event suffers from this discrepancy. does not know about it at all, and knows its correct relative temporal position.
We describe briefly a method for enforcing timeline uniqueness within an entangled service set in Section 7.
Historic survivability in the context of an entangled set of services is the decoupling of the verifiability of existence and temporal precedence proofs within a timeline from the fate of the maintainer of that timeline.
Temporal proofs are inherently survivable because of their dependence on well-known, one-way constructs. For example, a hash chain consisting of multiple applications of SHA-1 certainly proves that the result of the chain temporally followed the input to the chain. However, this survivability is moot, if the timeline authenticators that the proof orders undeniably can no longer be interpreted or associated with a real time frame.
Fortunately, secure temporal mapping allows a client within a service domain to fortify a temporal proof that he cares about against the passing of the local service. The client can accomplish this by participating in more service domains than one; then, he can proactively map the temporal proofs he cares about from their source timeline onto all the timelines of the service domains in which he belongs. In this manner, even if all but one of the services with which he is associated become unavailable or go out of business, the client may still associate his proofs with a live timeline in the surviving service domain.
Consider, for example, the scenario illustrated in Figure 5. David, who belongs to all three service domains , and , wishes to fortify event so as to be able to place it in time, even if service is no longer available. He maps the event onto the timelines of and --``mapping an event '' is equivalent to mapping the timeline time step in whose system state event is included, that is, in the example. Even though the event occurred in 's timeline, David can still reason about its relative position in time, albeit with some loss of resolution, in both the service domains of and , long after is gone. In a sense, David ``hedges his bets'' among multiple services, hoping that one of them survives. Note also that the fortification of even can occur long after its occurrence. The use of temporal mapping in this context is similar in scope to the techniques used by Ansper et al.  for fault-tolerant time stamping services, although it assumes far less mutual trust among the different service domains.
We have devised two new, to our knowledge, disk-oriented data structures for the implementation of Timeweave, our timeline entanglement prototype. In Section 5.1, we present authenticated append-only skip lists. These are an efficient optimization of traditional hash chains and yield precedence proofs with size proportional to the square logarithm of the total elements in the list, as opposed to linear. In Section 5.2, we present RBB-Trees, our disk-based, persistent authenticated dictionaries based on authenticated search trees. RBB-Trees scale to larger sizes than current in-memory persistent authenticated dictionaries, while making efficient use of the disk. Finally, in Section 5.3, we outline how Timeweave operates.
Our basic tool for maintaining an efficient secure timeline is the authenticated append-only skip list. The authenticated append-only skip list is a modification of the simplistic hash chain described in Section 3 that yields improved access characteristics and shorter proofs.
Our skip lists are deterministic, as opposed to the randomized skip lists proposed in the literature . Unlike the authenticated skip lists introduced by Goodrich et al. , our skip lists are append-only, which obviates the need for commutative hashing. Every list element has a numeric identifier that is a counter from the first element in the list (the first element is element , the tenth element is element , and so on); the initial authenticator of the skip list before any elements are inserted is element . Every inserted element carries a data value and an authenticator, similarly to what was suggested in Section 3 for single-chain timelines.
The skip list consists of multiple parallel hash chains at different levels of detail, each containing half as many elements as the previous one. The basic chain (at level 0) links every element to the authenticator of the one before it, just like simple hash chains. The next chain (at level 1) coexists with the level 0 chain, but only contains elements whose numeric identifiers are multiples of 2, and every element is linked to the element two positions before it. Similarly, only elements with numeric identifiers that are multiples of are contained in the hash chain of level . No chains of level are maintained, if all elements are .
The authenticator of element with data value is computed from a hash of all the partial authenticators (called links) from each basic hash chain in which the element participates. Element , where does not divide , participates in chains. It has the links , , and authenticator . Figure 6 illustrates a portion of such a skip list. In the implementation, we combine together the element authenticator with the 0-th level link for odd-numbered elements, since such elements have a single link, which is sufficient as an authenticator by itself.
Skip lists allow their efficient traversal from an element to a later element in a logarithmic number of steps: starting from element , successively higher-level links are utilized until the ``tallest element'' (one with the largest power of 2 in its factors among all element indices between and ) is reached. Thereafter, successively lower-level links are traversed until is reached. More specifically, an iterative process starts with the current element . To move closer to the destination element with index , the highest power of 2 that divides is picked, such that . Then element becomes the next current element in the traversal. The iteration stops when .
The associated temporal precedence proof linking element before element is constructed in a manner similar to the traversal described above. At every step, when a jump of length is taken from the current element to , the element value of the new element is appended to the proof, along with all the associated links of element , except for the link at level . Link is omitted since it can be computed during verification from the previous authenticator and the data value .
In the example of Figure 6, the path from element to element traverses elements and . The corresponding precedence proof from element to element is . With this proof and given the authenticators and of elements and respectively, the verifier can successively compute , then and finally --recall that for all odd elements , . If the known and the derived values for the authenticator agree ( ), then the verifier can be convinced that the authenticator preceded the computation of authenticator , which is the objective of a precedence proof.
Thanks to the properties of skip lists, any of these proofs contains links and data values of roughly a logarithmic number of skip list elements. The worst-case proof for a skip list of elements traverses elements, climbing links of every level between and and back down again, or link values and data values total. Assuming that every link and value is a SHA-1 digest of 160 bits, the worst case proof for a timeline of a billion elements is no longer than 20 KBytes, and most are much shorter.
Our skip lists are fit for secondary storage. They are implemented on memory-mapped files. Since modifications are expected to be relatively rare, compared to searches and proof extractions, we always write changes to the skip list through to the disk immediately after they are made, to maintain consistency in the face of machine crashes. We do not, however, support structural recovery from disk crashes; we believe that existing file system and redundant disk array technologies are adequate to prevent and recover all but the most catastrophic losses of disk bits.
This work uses authenticated persistent dictionaries based on trees. A persistent dictionary maintains multiple versions (or snapshots) of its contents as it is modified. In addition to the functionality offered by simple authenticated dictionaries, it can also provably answer questions of the form ``in snapshot , was element in the dictionary?''.
The dictionaries we use in this work can potentially grow very large, much larger than the sizes of current main memories. Therefore, we have extended our earlier work on balanced persistent authenticated search trees  to design on-disk persistent authenticated dictionaries. The resulting data structure, the RBB-Tree, is a binary authenticated search tree [6,7] embedded in a persistent B-Tree [9, Ch. 18]. Figure 7 shows a simple RBB-Tree holding 16 numeric keys.
RBB-Trees, like B-Trees, are designed to organize keys together in efficient structures that result in few disk accesses per tree operation. Every tree node is stored in its own disk block, contains a minimum of and a maximum of keys, and has between and children (the root node is only required to have between and keys). Parameter is the order of the B-Tree.
Unlike traditional B-Trees, RBB-Tree nodes do not store their keys in a flat array. Instead, keys within RBB nodes are organized in a balanced binary tree, specifically a red-black tree [9, Ch. 13]. We consider RBB-Trees ``virtual'' binary trees, since the in-node binary trees connected to each other result in a large, piecewise-red-black tree, encompassing all keys in the entire dictionary.
It is this ``virtual'' binary tree of keys that is authenticated, in the sense of the authenticated search trees by Buldas et al. [6,7]. As such, the security properties of RBB-Trees are identical to those of authenticated search trees, including the structure of existence/non-existence proofs.
Since the RBB-Tree is a valid B-Tree, it is efficient in the number of disk block accesses it requires for the basic tree operations of insertion, deletion and modification. Specifically, each of those operations takes disk accesses, where is the total number of keys in the tree. Similarly, since the internal binary tree in each RBB-Tree node is balanced, the virtual embedded binary tree is also loosely balanced, and has height , that is, but with a higher constant factor than in a real red-black tree. These two collaborating types of balancing applied to the virtual binary tree--the first through the blocking of keys in RBB nodes, and the second through the balancing of the key nodes inside each RBB node--help keep the length of the resulting existence/non-existence proofs also bounded to elements.
The internal key structure imposed on RBB-Tree nodes does not
improve the speed of search through the tree over the speed of
search in an equivalent B-Tree, but limits the length of existence
proofs immensely. The existence proof for a datum inside an
authenticated search tree consists of the search keys of each node
from the sought datum up to the root, along with the labels of the
siblings of each of the ancestors of the sought datum up to the
root . In a very ``bushy'' tree, as B-Trees are
designed to be, this would mean proofs containing authentication
data from a small number of individual nodes; unfortunately, each
individual node's authentication data consist of roughly keys
and siblings' labels. For example, a straightforwardly
implemented authenticated B-Tree storing a billion SHA-1 digests
with yields existence proofs of length
bits, or roughly 160 KBits.
The equivalent red-black tree yields existence proofs of no more
about 18 KBits. RBB-Trees seek to trade off the low disk access
costs of B-Trees with the short proof lengths of red-black trees.
The equivalent RBB-Tree of one billion SHA-1 digests yields proofs
no longer than
We have designed dynamic set persistence [9, p. 294] at the granularity of both the RBB node and the embedded key node (see Figure 8). As long as there is key-node space available within an RBB node, new snapshots of the key tree within that node are collocated with older snapshots. This allows multiple snapshots to share unchanged key nodes within the same RBB node. When, however, all available key-node space within an RBB node is exhausted, subsequent snapshots of the key tree inside that node are migrated to a new, fresh RBB node.
The different persistent snapshot roots of the RBB-Tree are held together in an authenticated linked list--in fact, we use our own append-only authenticated skip list from Section 5.1.
Since each snapshot of the RBB-Tree is a ``virtual'' binary authenticated search tree, the root label of that tree (i.e., the label of the root key node of the root RBB node) is a one-way digest of the snapshot [6,7]. Furthermore, the authenticated skip list of those snapshot root labels is itself a one-way digest of the sequence of snapshot roots. As a result, the label of the last element of the snapshot root skip list is a one-way digest of the entire history of operations of the persistent RBB-Tree. The snapshot root skip list subsumes the functionality of the Time Tree in our earlier persistent authenticated red-black tree design .
In some cases the ``freshness'' of an authenticated dictionary snapshot has to be provable. For example, in our description of secure timelines, we have specified that the system state must depend on the authenticator of the previous timeline time step. When the system state is represented by an authenticated dictionary, an existence proof within that dictionary need not only show that a sought element is part of the dictionary given the dictionary digest (root hash), but also that the sought element was added into the dictionary after the authenticator of the previous time step was known.
As with other authenticated dictionaries, we accomplish this by making the hash label of NIL pointers equal to the ``freshness'' authenticator, so that all existence proofs of newly inserted elements--equivalently, non-existence proofs of newly removed elements--prove that they happened after the given freshness authenticator was known. Note that subtrees of the RBB-Tree that do not change across snapshots retain their old freshness authenticators. This is acceptable, since freshness is only necessary to prove to a client that a requested modification was just performed (for example, when we produce entanglement receipts in Section 4), and is required only of newly removed or inserted dictionary elements. In the figure, the label for key node 19 is derived from the freshness authenticator for snapshot 3, since 19 is added into the tree in snapshot 3. This establishes that the tree changed to receive key 19 after the value of the freshness authenticator for snapshot 3 was known.
In standalone RBB-Trees, the freshness authenticator is simply the last authenticator in the snapshot root list (i.e., the authenticator that resulted from the insertion of the latest closed snapshot root into the skip list). In the RBB-Trees that we use for thread archives in Timeweave (Section 5.3), the freshness authenticator for snapshot is exactly the authenticator of the previous timeline time step .
Timeweave is an implementation of the timeline entanglement mechanisms described in Section 4. It is built using our authenticated append-only skip lists (Section 5.1) and our on-disk persistent authenticated search trees (Section 5.2).
A Timeweave machine maintains four components: first, a service state, which is application specific, and the one-way digest mechanism thereof; second, its secure timeline; third, a persistent authenticated archive of timeline threads received; and, fourth, a simple archive of entanglement receipts received.
The timeline is stored as an append-only authenticated skip list. The system digest used to derive the timeline authenticator at every logical time step is a hash of the concatenation of the service state digest and the digest of the thread archive after any incoming and outgoing threads have been recorded.
The thread archive contains threads sent by remote peers and verified locally. Such threads are contained both in thread messages initiated remotely and in entanglement receipts to outgoing threads. The archived threads are ordered by the identity of the remote peer in the entanglement operation, and then by the foreign logical time associated with the operation. The archive is implemented as an RBB-Tree and has a well-defined mechanism for calculating its one-way digest, described in Section 5.2.
The receipt archive is a simple (not authenticated) repository of thread storage receipts for all outgoing threads successfully acknowledged by remote peers.
The main operational loop of a Timeweave machine is as follows:
The Timeweave machine also allows clients to request local temporal mappings of remote logical times and temporal precedences between local times.
In this section, we evaluate the performance characteristics of timeline entanglement. First, in Section 6.1, we present measurements from a Java implementation of the Timeweave infrastructure: authenticated append-only skip lists and RBB-Trees. Then, in Section 6.2, we explore the performance characteristics of Timeweave as a function of its basic Timeweave system parameter, entanglement load.
In all measurements, we use a lightly loaded dual Pentium III Xeon computer at 1 GHz, with 2 GBytes of main memory, running RedHat Linux 7.2, with the stock 2.4.9-31smp kernel and Sun Microsystems' JVM 1.3.02. The three disks used in the experiments are model MAJ3364MP made by Fujitsu, which offer 10,000 RPMs and 5 ms average seek time. We use a disk block size of 64 KBytes. Finally, for signing we use DSA with SHA-1, with a key size of 1024 bits.
We measure the raw performance characteristics of our disk-based authenticated data structures. Since Timeweave relies heavily on these two data structures, understanding their performance can help evaluate the performance limitations of Timeweave.
Figure 9(a) shows the performance of skip list appends, for skip list sizes ranging from one million to 100 million elements, in increments of one million elements. The figure graphs the time taken by a single append operation averaged over all operations for a given size, and averaged over the last one million operations for a given size. As expected, the time taken by append operations grows logarithmically with the size of the skip list, although for practical skip list sizes, the cost per append operation is virtually constant.
We also measure the performance of skip list proof extraction, in Figure 9(b). The figure graphs the time it takes to extract a precedence proof from a 100-million element skip list for a given distance between the end-points of the proof (the distance between elements and is elements). We average over 1,000 uniformly random proof extractions per distance. For small distances, different proofs fall within vastly different disk blocks, making proof extraction performance heavily I/O bound. For larger distances approaching the entire skip list size, random proofs have many disk blocks in common, amortizing I/O overheads and lowering the average cost.
We continue by evaluating the performance characteristics of RBB-Trees. Figure 10 contains two graphs, one showing how insertion time grows with tree size (Figure 10(a)) and another showing how proof extraction time grows with tree size (Figure 10(b)).
Smaller snapshot sizes have two effects: more disk blocks for the same number of elements and more hashing. The number of disk blocks used is higher because some keys are replicated across more snapshots; the amount of hashing is higher since every new copy of a key node must have a new hash label calculated. The first effect is evidenced in Table 1, which shows the disk size of a three-million-key RBB-Tree with varying snapshot sizes. The second effect is evidenced in Figure 10(a), plotting insertion times for different snapshot sizes.
Proof extraction experiments consisted of 1,000 random searches for every size increment. This operation, which consists of a tree traversal from the root of the tree to a leaf, is not affected by snapshot size, but only by tree size (tree height, specifically). Neither the traversed logical ``shape'' of the tree, nor the distribution of keys into disk blocks are dependent on how frequently a tree snapshot is archived.
Finally, we graph proof sizes in skip lists (Figure 11(a)) and RBB-Trees (Figure 11(b)). Both graphs show proof sizes in KBytes, over 1,000 uniform random trials in a skip list of 100 million elements and an RBB-Tree of three million elements, respectively. The skip list curve starts out as a regular square logarithmic curve, except for large distances, close to the size of the entire list. We conjecture that the reason for this exception is that for random trials of distances close to the entire list size, all randomly chosen proofs are worst-case proofs, including every link of every level between source and destination, although we must explore this effect further. The RBB-Tree graph shows a regular logarithmic curve.
Although microbenchmarks can be helpful in understanding how the basic blocks of Timeweave perform, they cannot give a complete picture of how the system performs in action. For example, very rarely does a Timeweave machine need to insert thousands of elements into a skip list back-to-back. As a result, the disk block caching available to batched insertions is not available for skip list usage patterns exhibited by Timeweave. Similarly, most proof extractions in timelines only span short distances; for one-second-long timeline time steps with one entanglement process per peer every 10 minutes, a Timeweave machine barely needs to traverse a distance of elements to extract a precedence proof, unlike the random trials measured in Figure 9.
In this section we measure two performance metrics of a Timeweave machine in action: maintenance time and data transmitted. Timeweave maintenance consists of the different computations and data manipulations performed to verify, archive and acknowledge timeline threads. Transmitted data consist of new outgoing threads to the peers of the Timeweave machine and receipts for threads received from those peers.
We measure the change of these two metrics as the load of a Timeweave machine changes. The load of a Timeweave machine is roughly the number of incoming threads it has to handle per time step. If we fix the duration of each time step to one second, and the entanglement interval to 10 minutes (600 time steps), then a load of 5 means that the entanglement service set consists of Timeweave machines and, as a result, every Timeweave machine receives on average 5 threads per second.
Figure 12(a) shows the time it takes a single machine to perform Timeweave maintainance per one-second-long time step. The almost perfectly linear rate at which maintenance processing grows with the ratio of threads per time step indicates that all-to-all entanglement can scale to large entangled service sets only by limiting the entanglement frequency. However, for reasonably large service sets, up to Timeweave machines for 10-minute entanglement, maintenance costs range between 2 and 8% of the processing resources of a PC-grade server.
Figure 12(b) shows the amount of data sent per time step from a single Timeweave machine. Although the data rate itself is no cause for concern, the number of different destinations for secure transmissions could also limit how all-to-all entanglement scales. Again, for entangled service sets and entanglement intervals that do not exceed two or three threads per time step, Timeweave maintenance should not pose a problem to a low-end server with reasonable connectivity.
In this work we seek to extend the traditional idea of time stamping into the concept of a secure timeline, a tamper-evident historic record of the states through which a system passed in its lifetime. Secure timelines make it possible to reason about the temporal ordering of system states in a provable manner. We then proceed to define timeline entanglement, a technique for creating undeniable temporal orderings across mutually distrustful service domains. Finally, we design, describe the implementation of, and evaluate Timeweave, a prototype implementation of our timeline entanglement machinery, based on two novel authenticated data structures: append-only authenticated skip lists and disk-based, persistent authenticated search trees. Our measurements indicate that sizes of several hundred service domains can be efficiently entangled at a frequency of once every ten minutes using Timeweave.
Although our constructs preserve the correctness of temporal proofs, they are not complete, since some events in a dishonest service domain can be hidden from the timelines with which that domain entangles (Section 4.3). We plan to alleviate this shortcoming by employing a technique reminiscent of the signed-messages solution to the traditional Byzantine Generals problem . Every time service sends a thread to peer , it also piggybacks all the signed threads of other services it has received and archived since the last time it sent a thread to . In such a manner, a service will be able to verify that all members of the entangled service set have received the same, unique timeline authenticator from every other service that it has received and archived, verifying global historic integrity.
We also hope to migrate away from the all-to-all entanglement model, by employing recently-developed, highly scalable overlay architectures such as CAN  and Chord . In this way, a service only entangles its timeline with its immediate neighbors. Temporal proofs involving non-neighboring service domains use transitive temporal mapping, over the routing path in the overlay, perhaps choosing the route of least temporal loss.
Finally, we are working on a large scale distributed historic file system that enables the automatic maintenance of temporal orderings among file system operations across the entire system.
We thank Dan Boneh for suffering through the early stages of this work, as well as Hector Garcia-Molina and Neil Daswani for many helpful comments and pointed questions.
This work is supported by the Stanford Networking Research Center, by DARPA (contract N66001-00-C-8015) and by Sonera Corporation. Petros Maniatis is supported by a USENIX Scholar Fellowship.
This paper was originally published in the
Proceedings of the 11th USENIX Security Symposium,
August 59, 2002, San Francisco, CA, USA
Last changed: 19 June 2002 aw