From Satoshi's paper:
3. Timestamp Server
The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.
###
It is the timestamp server that enables the rest of bitcoin to work and without a timestamp server, it appears trivial to double spend as there wont be a way to know the balance of an account at any given time. Regardless of whether a timestamp server alone is sufficient, it is clearly necessary.
We will ignore all issues regarding PoW vs PoS vs PoAnything and concentrate on creating a universal timestamp, or rather a time sequence server via bitcoin. The effect of having a universal clock is that synchronized operations can be done across all other blockchains who adopt the bitcoin time sequence server.
A. In the beginning there was no bitcoin and until genesis block it was not possible to be utilized in any way. However, now that it exists and is clearly "real", we have enormous amounts of hashrate securing the steady stream of bitcoin blocks. Due to the way the consensus works, there is a chance that the current block is superceded by a "better" block and even the most recent 2 blocks, or 3, or ... However, the chances rapidly diminish to an extremely remote possibility. The exact number of confirmations that is considered safe from reorg is certainly a critical decision, but it does not affect the proof of time stamp serverness.
Let us call this depth L, for lag. It will be assumed that any bitcoin blocks with L or more confirmations are permanent. For practical applications, it is suggested to have a mechanism to detect and recalibrate in the rare case of a bitcoin reorg beyond L blocks, but if the probability of such an event is remote enough, other means of compensating for it are also possible, ie insurance type methods of risk sharing.
B. Given the assumption that any blocks with L confirmations are valid, at any given time there is a "current" permanent BTC block, with its blockhash. And most times a new block is generated, we get a new permanent BTC block. However, when there is a small reorg or a replacement of the tip, we do not get a new permanent BTC block. A simple way to calculate whether a new BTC block advances the permanet BTC block is to verify that it is L+1 confirmations from the previous permanent block.
What this means is that as bitcoin does its small reorgs, the permanent blocks will not advance until things catch up. However since most reorgs are caused by a new pair of blocks that extend the chain and bypassing the current tip, this stop/starting of the permanent blocks are mostly insulated. This stop and go behavior combined with the +/- 2 hours tolerance on timestamps makes the BTS not a timestamp server, but a time sequence server. It is not as useful, but still a framework that can be built upon.
We now have a sequence of permanent blocks Ti, Ti+1, Ti+2, ... with the proven characteristic that each Ti came after the preceding one, ie. an ordering of blockhashes. Another small concession that will be made is that we will assume that SHA256 collisions can be ignored, bitcoin now does not allow duplicate blockhashes, so even if there is a collision it will probably not affect things, but the odds of such are so small, it will simplify the analysis to ignore its effects.
C. What can be done with the set of permanent blockhashes? They can be used by any external blockchain or in fact anything as proof of time sequence. Using the law of common sense and assuming the ban on time travel is still in effect, we can see that to be able to know a specific blockhash Ti indicates it must have happened after that blockhash appeared. Since Ti first appeared in the mining node even before it was submitted, it could have been known right after blockhash Ti-1 appeared. Yes, this will be a very slow clock indeed, but a clock nonetheless.
Being able to refer to a permanent blockhash Ti shows that it happened after L+1 confirmations ago. What this means is that regardless of whether this hash Ti is put into the altcoin's chain via consensus or by attacker, all blocks after it are shown to have happened after the earliest time that Ti was known.
Let us assume that the permanent blockhash sequence is either fully or partially referred to in the external chain. This gives us a partial ordering of all the external chain blocks as having happened no sooner than when Ti was known. If the protocol gives more weight to referals to the oldest Ti, then an eventual consensus will arise with external chain blocks grouped into segments such that each segment is known to have happened after the blocks in the prior segment. By having a block rejection rule to reject blocks too far from the past, if this "too far" is set to be a fraction of the times between Ti, then we get a provable time ordering if there is 1 or more Ti between two external chain segments and a likely time ordering for adjacent segments.
D. Now each external chain is divided into universally verifiable groups of blocks, that regardless of the strength of the consensus mechanism for that external chain (even if it has none!), it is able to conduct cross chain transactions with other external chains using the same segmentation. Well, not quite. Of course if the external chain is some arbitrary ledger that can be updated at will by some corporate entity, then these security assumptions do not hold up. What is required is another rule in the external chain that after R permanent Ti blocks have passed, that it is permanent. This R (for reorg) factor will then allow other external chains to know that after R permanent blocks it cannot change and also the partial time sequence is externally verifiable.
E. This is just a first draft and many improvements are possible. For instance, by using blocks very close to the current, the external chain can create a lot finer grain ordering internally, unless bitcoin reorgs the referred blocks away.
F. tl:dr it wont be fast, but using bitcoin as the universal clock, all external chains that add a few consensus rules can interact as long as enough bitcoin confirmations are waited.
G. Appendix: put fancy math that almost nobody understands here
3. Timestamp Server
The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.
###
It is the timestamp server that enables the rest of bitcoin to work and without a timestamp server, it appears trivial to double spend as there wont be a way to know the balance of an account at any given time. Regardless of whether a timestamp server alone is sufficient, it is clearly necessary.
We will ignore all issues regarding PoW vs PoS vs PoAnything and concentrate on creating a universal timestamp, or rather a time sequence server via bitcoin. The effect of having a universal clock is that synchronized operations can be done across all other blockchains who adopt the bitcoin time sequence server.
A. In the beginning there was no bitcoin and until genesis block it was not possible to be utilized in any way. However, now that it exists and is clearly "real", we have enormous amounts of hashrate securing the steady stream of bitcoin blocks. Due to the way the consensus works, there is a chance that the current block is superceded by a "better" block and even the most recent 2 blocks, or 3, or ... However, the chances rapidly diminish to an extremely remote possibility. The exact number of confirmations that is considered safe from reorg is certainly a critical decision, but it does not affect the proof of time stamp serverness.
Let us call this depth L, for lag. It will be assumed that any bitcoin blocks with L or more confirmations are permanent. For practical applications, it is suggested to have a mechanism to detect and recalibrate in the rare case of a bitcoin reorg beyond L blocks, but if the probability of such an event is remote enough, other means of compensating for it are also possible, ie insurance type methods of risk sharing.
B. Given the assumption that any blocks with L confirmations are valid, at any given time there is a "current" permanent BTC block, with its blockhash. And most times a new block is generated, we get a new permanent BTC block. However, when there is a small reorg or a replacement of the tip, we do not get a new permanent BTC block. A simple way to calculate whether a new BTC block advances the permanet BTC block is to verify that it is L+1 confirmations from the previous permanent block.
What this means is that as bitcoin does its small reorgs, the permanent blocks will not advance until things catch up. However since most reorgs are caused by a new pair of blocks that extend the chain and bypassing the current tip, this stop/starting of the permanent blocks are mostly insulated. This stop and go behavior combined with the +/- 2 hours tolerance on timestamps makes the BTS not a timestamp server, but a time sequence server. It is not as useful, but still a framework that can be built upon.
We now have a sequence of permanent blocks Ti, Ti+1, Ti+2, ... with the proven characteristic that each Ti came after the preceding one, ie. an ordering of blockhashes. Another small concession that will be made is that we will assume that SHA256 collisions can be ignored, bitcoin now does not allow duplicate blockhashes, so even if there is a collision it will probably not affect things, but the odds of such are so small, it will simplify the analysis to ignore its effects.
C. What can be done with the set of permanent blockhashes? They can be used by any external blockchain or in fact anything as proof of time sequence. Using the law of common sense and assuming the ban on time travel is still in effect, we can see that to be able to know a specific blockhash Ti indicates it must have happened after that blockhash appeared. Since Ti first appeared in the mining node even before it was submitted, it could have been known right after blockhash Ti-1 appeared. Yes, this will be a very slow clock indeed, but a clock nonetheless.
Being able to refer to a permanent blockhash Ti shows that it happened after L+1 confirmations ago. What this means is that regardless of whether this hash Ti is put into the altcoin's chain via consensus or by attacker, all blocks after it are shown to have happened after the earliest time that Ti was known.
Let us assume that the permanent blockhash sequence is either fully or partially referred to in the external chain. This gives us a partial ordering of all the external chain blocks as having happened no sooner than when Ti was known. If the protocol gives more weight to referals to the oldest Ti, then an eventual consensus will arise with external chain blocks grouped into segments such that each segment is known to have happened after the blocks in the prior segment. By having a block rejection rule to reject blocks too far from the past, if this "too far" is set to be a fraction of the times between Ti, then we get a provable time ordering if there is 1 or more Ti between two external chain segments and a likely time ordering for adjacent segments.
D. Now each external chain is divided into universally verifiable groups of blocks, that regardless of the strength of the consensus mechanism for that external chain (even if it has none!), it is able to conduct cross chain transactions with other external chains using the same segmentation. Well, not quite. Of course if the external chain is some arbitrary ledger that can be updated at will by some corporate entity, then these security assumptions do not hold up. What is required is another rule in the external chain that after R permanent Ti blocks have passed, that it is permanent. This R (for reorg) factor will then allow other external chains to know that after R permanent blocks it cannot change and also the partial time sequence is externally verifiable.
E. This is just a first draft and many improvements are possible. For instance, by using blocks very close to the current, the external chain can create a lot finer grain ordering internally, unless bitcoin reorgs the referred blocks away.
F. tl:dr it wont be fast, but using bitcoin as the universal clock, all external chains that add a few consensus rules can interact as long as enough bitcoin confirmations are waited.
G. Appendix: put fancy math that almost nobody understands here
