Linked timestamping

Linked timestamping creates time-stamp tokens which are dependent on each other, entangled in some authenticated data structure.

The top of the authenticated data structure is generally published in some hard-to-modify and widely witnessed media, like printed newspaper or public blockchain.

Continuity of operation is observable by users; periodic publications in widely witnessed media provide extra transparency.

Tampering with absolute time values could be detected by users, whose time-stamps are relatively comparable by system design.

Stuart Haber and W. Scott Stornetta proposed[4] in 1990 to link issued time-stamps together into linear hash-chain, using a collision-resistant hash function.

Tree-like schemes and operating in rounds were proposed by Benaloh and de Mare in 1991[5] and by Bayer, Haber and Stornetta in 1992.

for the number of time stamps issued during the aggregation period; it is suggested that it is probably impossible to prove the security without this explicit bound - the so-called black-box reductions will fail in this task.

Considering that all known practically relevant and efficient security proofs are black-box, this negative result is quite strong.

Buldas, Laur showed[15] in 2007 that bounded time-stamping schemes are secure in a very strong sense - they satisfy the so-called "knowledge-binding" condition.

The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant[16] or even one-way;[17] secure time-stamping schemes are probably possible even in the presence of a universal collision-finding algorithm (i.e. universal and attacking program that is able to find collisions for any hash function).

This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions.

Current security proofs work on the assumption that there is a hard limit of the aggregation tree size, possibly enforced by the subtree length restriction.

RFC 4998 (Evidence Record Syntax) encompasses hash tree and time-stamp as an integrity guarantee for long-term archiving.