Any disagreement between auditors about the relative order of transactions can be exploited by double-spenders. To fix this vulnerability, auditors need to agree on a consistent transaction sequence. The first part of the solution comes in the form of timestamps.
This post is part of the extended series Bitcoin from Scratch.
A timestamp is a piece of information added to each item of a list for the purpose of enabling chronological sorting. For example, the postmark on a letter is a kind of timestamp that happens to include a time and date. Any collection of timestamped letters can be ordered by postmark, even if the letters were received by different post offices. Page numbers on a book can also serve as a kind of primitive time stamp. Even if each page is removed and reshuffled, the book can be reconstructed by ordering pages by ascending page number.
A more general mechanism uses a hash function to establish an ordering of items in a list (see: Hash Functions). This kind of timestamp includes two pieces of information: the hash value of the message being timestamped; and the hash value of the previous timestamp. The presence of the previous timestamp makes it possible to link hash-based timestamps together into a timestamp chain.
A timestamp chain is similar a chain of ownership in the way it resists tampering (see: Chain of Ownership). For example, editing a timestamped message causes its hash value to change. This change breaks the link between timestamp and message, and between a parent timestamp and its child. Similarly, inserting a timestamp into the chain invalidates all timestamps after the insertion point. The only way to edit the chain without re-writing every timestamp is to append new timestamps.
Any message can be timestamped, including transactions. Imagine that an auditor wants to record the order in which transactions were received using a timestamp chain. To do so, a new timestamp would include the new transaction’s hash value (unique ID) and the hash value of the parent timestamp. Rather than maintaining a loose collection of transactions, the auditor would organize transactions into a timestamped ledger.
Timestamp chains are modular in that they can be readily disassembled and reassembled. The procedure is simple. To re-link a message with its timestamp, first compute its hash value. Then, find the timestamp that includes this message hash. Using a similar procedure, a parent timestamp can be relinked to its child.
Modularity is useful because it allows a timestamped ledger to be broken down, transmitted over a distance, and reconstructed by many different auditors. After updating its local ledger, an auditor would relay a transaction together with its timestamp to the other auditors. A receiving auditor would then validate the transaction. If no double spending were detected, the relayed timestamp and its transaction would be appended to the local ledger. These simple rules allow each auditor to assemble an identical local copy of the ledger over time.
Timestamps allow auditors to detect transaction ordering conflicts. Imagine that Vanna and Victor receive different audit requests simultaneously. Each auditor timestamps the request and relays the result to the other. The timestamps were relayed at almost the same time, so they cross paths en route. However, extending a timestamp chain requires a match between the unique ID carried by the new timestamp and the unique ID of the last timestamp in the chain. Lacking a match, both auditors reject the relayed timestamps and their associated transaction.
Error detection is useful, but by itself can’t solve the problem caused by audit requests crossing paths. What’s needed is not just a way to detect timestamp conflicts, but to resolve them.