Linked Timestamp (BlockChain)

Status: Believed expired in US, see US 5,781,629

The fashionable electronic currency scheme BitCoin is built on two technologies, both of which are based on a cryptographic one-way function, generally known as a cryptographic digest. One of these technologies is 'proof of work' which is basically a proof that some party has wasted a certain amount of electricity performing a useless task. The other technology is the linked timestamp which is a lot more interesting. While this technology has been known in the literature for over 25 years as 'Linked Timestamp', it is now best known under its BitCoin name 'BlockChain'.

The linked timestamp was invented by Haber and Stornetta, two researchers at Bellcore. The initial patent was filed July 5th 1989 and issued as US 5,189,700 on 23rd February 1993. Under the rules applicable at the time of filing, the patent should have expired 17 years after issue (23rd February 2010). It is almost certainly no coincidence that BitCoin was announced on 3 January 2009, just before the patent expiry

The idea of the Linked Timestamp is simple and powerful. In its simplest form, a timestamp authority takes a sequence of documents, takes the hash of each document

The genius of the linked timestamp is that it uses a cryptographic function that produces a one-way function to build a one-way chain. If the one-way function is strong, a given chain output value can only have been formed by exactly one set of input documents in exactly one order.

Timestamped Digital Signature

The basic linked timestamp provides a proof that a document existed before or after a particular time instant. We can extend the scheme to provide a proof that a digital signature was created on a document in the time interval [t_before, t_after] as follows:

Let N(t) be the output of a Linked Timestamp, M the message and k be the signing key:

      It is interesting to note that it is not actually necessary for signature created to be enrolled in the same Linked Timestamp as was used to create the signature.

      Link Topology

      A linked timestamp need not be a simple chain. Over the years, many authors have proposed ingenious structures for organizing linked timestamps that provide various benefits. For practical purposes, the chief concerns are:

      • Efficiency of calculating the next output.
      • Amount of data that various parties must store for validation.

      While this class of problems has led to numerous academic papers describing nth degree optimizations, the Merkle Tree patented by Ralph Merkle in 1979 is satisfactory for almost any situation:

      Trusting the Timestamp Authority

      Having constructed such a chain, we can create a proof that a document existed on or before a certain day by taking the output value for the chain at the end of each day and recording it in some trustworthy archival series such as a newspaper. To introduce a false document into the series requires an attacker to either break the digest function or find some way to pass off a forged newspaper.

      At the time the linked timestamp scheme was first proposed, newspapers were still published on paper and widely circulated. In particular, a large number of libraries maintained archives of newspapers, archives that in some cases spanned more than a century. Today, newspapers are mostly read electronically and very few archive newspapers as physical objects. It is therefore important to consider how a linked timestamp authority can be trustworthy in a world where bits have entirely replaced atoms.

      The BitCoin Scheme

      In the BitCoin system, the output value of the chain is established through a proof of work scheme. Each time a block is 'mined', the new output value of the BlockChain determines the new target value for the proof of work scheme. At current prices, BitCoins 'worth' approximately $2 million are created each day. According to theory, it would cost an attacker a minimum of $1 million for each day they wanted to backdate the BlockChain and much more if they wanted to do it in a reasonable time.

      The one major problem with this approach is that BitCoin is estimated to have consumed a minimum of 1.46 terawatt-hours of electricity in 2015. That is a cost of about $230 million. Should confidence in BitCoin ever collapse, then so would the price, BitCoin mining in its current form would cease to be profitable and the only way to make real money from the farms of BitCoin mining machines would be to use them to game the system by attacking the BlockChain.

      Fortunately, it is actually the inherent stability of the linked notary that provides security in the BitCoin system rather than the proof of work activity. As we saw earlier, there is really no way for a timestamp notary to defect without being detected unless they can somehow convince different people to accept different output values as the current value of the chain.

      This effect is actually used in the BitCoin system. While BitCoin theory says that the current value of the BlockChain is always defined by the longest chain, the practice is rather different because many parts of the system are built on the assumption that the BlockChain cannot unwind by more than a few hours and certainly not by 24 hours or more.

      Interlinked Notaries

      When BitCoin began, it was the only large scale publicly accessible Linked Timestamp infrastructure. Commercial linked timestamp products existed but only as closed proprietary systems whose terms of service typically prohibited use of that system to fix the output of another in time.

      Today there are several large scale Linked Notary infrastructures, most notably the Certificate Transparency infrastructure originally proposed by Google and currently being standardized by IETF in the TRANS Working Group.

      Interlinking notaries is a simple and powerful method of increasing the work factor of an attacker. If X and Y are two independent notaries with independent work factors of $W_X and $W_Y, feeding the output of X into the input of Y, raises the work factor of the latter to $W_X + $W_Y.

      The more notaries that are interlinked, the higher the work factor becomes. We can also interlink indirectly. If we feed the output of X into Y and then feed the output of Y into Z, the work factor of Z is $W_X + $W_Y + $W_Z.

      Interlinking notaries is cheap and powerful. In effect, an attack on one becomes an attack on all. We should therefore anticipate that at some point in the future, every Linked Notary infrastructure (aka BlockChain) will be at least indirectly interlinked with every other Linked Notary Infrastructure. At that point, a backdating attack against any interlinked notary will become as infeasible as breaking the cryptographic algorithms used to calculate it.

      It should be noted however that once this is achieved, it will then be possible to build BitCoin like ledger based payment transfer systems without the need to spend a quarter billion dollars a year on the proof of work scheme. The rise of interlinked notaries is thus very likely to spell the end rather than the beginning of BitCoin as global currency as it will become possible to use BlockChain technology to perform payment transfers of any kind without the proof of work overhead.