In this post, we highlight the interesting relationship between snapshotting and timestamps. To summarize below, the act of snapshotting is a temporal declaration, and thus in order to have consensus about which transactions can be snapshotted, we have to have consensus on some sort of “abstract timestamps.”
Nodes only have finite memory, and thus they must periodically delete old transactions. More specifically, a node can maintain a bounded number of “recent transactions” otherwise the same problems occur. However, if an incoming transaction directly references a transaction which has been snapshotted, solidifying it will be complicated and maybe impossible.
Taking these considerations in mind, we say that a valid snapshotting algorithm satisfies the following:
- A transaction will be orphaned if it directly referencing a snapshotted transaction.
- If a transaction is snapshotted, so is every transaction in its history.
- Only a bounded number of transactions cannot be snapshotted (given a bounded rate of incoming transactions).
An abstract timestamp is an integer associated with a transaction that all nodes (eventually) have consensus on. We can totally order any list of transactions by stamp, breaking ties arbitrarily (e.g. with transaction hash). Here is a list of some examples of abstract timestamps.
- Actual timestamps: an actual timestamp is an integer contained inside the transaction. Every node who can see the transactions, agrees on the timestamp.
- Milestone number: Suppose we have a coordinator or a distributed system issuing enumerated milestones. The milestone number of a transaction is the number of the first milestone approving it. If we have consensus on milestones, then we have consensus on milestone number.
- Rank: The rank of a transaction is one plus the maximum rank of its parents. The genesis has rank 1. This number is deducible from the ledger.
Timestamps and the total orderings they induce are potentially very powerful. However if new transactions can have any timestamp, then an attacker can manipulate the ordering.
A valid timestamping scheme is a system which forces abstract timestamps to have the following properties.
- The abstract timestamp of a transaction is greater or equal to that of its parents.
- For every integer k, there is a time t_k such that for all t>t_k, no transaction with abstract timestamp k will be accepted.
A valid time stamping scheme requires a consensus mechanism. Consider the examples of abstract timestamps listed above. Milestones clearly require consensus. Furthermore, in order to implement rank or actual timestamps into a valid timestamping scheme, nodes must decide whether incoming transactions have a valid timestamp and reject those that do not.
Snapshots and time stamps are integrally connected.
Theorem 1
If a protocol has a valid snapshotting algorithm, it has a valid timestamping scheme.
Proof:
Suppose that we have a valid snapshotting algorithm. We claim that rank gives us a valid time stamping scheme. Rank is increasing, and so it remains to show that for every rank r, eventually all new transactions with rank r will be orphaned.
We proceed by induction on r. For r=1, the only transaction of rank 1 is the genesis, and so the claim is trivially true. Suppose the statement is true for r-1. Since there is a time t_{r-1} such that all transactions issued of rank r-1 will be orphaned, only a finite number of transactions of rank r will be accepted. Suppose for a moment that we prove that each of the transactions must be snapshotted. Then there is some time t_r where all transactions of rank r-1 will be snapshotted. For all t>t_r is a transaction of rank r is issued it must be orphaned since it directly references a transaction or rank r-1 which has been snapshotted.
So now we prove that for each transaction x or rank r-1 that is not orphaned will be snapshotted. Since the x is not orphaned, its cumulative weight must grow indefinitely. However, a node can only keep a bounded number of nonsnapshotted transactions. Thus some transaction in the future cone of x must eventually be snapshotted. But this means x is also snapshotted. \square
Note that although this theorem shows that the rank can be used as a timestamp, other timestamping schemes might also be valid. The converse of the above theorem is almost true.
Theorem 2
Suppose that the following
- The protocol has a valid timestamping scheme.
- The differences in abstract timestamps between parent and child transactions is bounded.
- There exists a constant A such that after time Ak, all new transactions with abstract timestamp k will be orphaned.
Proof:
Suppose the differences in abstract timestamps between parent and child transactions bounded by \Delta. Then all transactions with timestamp k can be orphaned after t>\Delta (k+\Delta). Given a bounded rate \lambda of incoming transactions, a node can snapshot all but \lambda A(\Delta+1) transactions. \square
Snapshotting is an essential part of a DLT protocol, and these results show that we thus must have some sort of abstract timestamps.