Overview

This 1999 paper by H. Massias, X. Serret Avila, and J.-J. Quisquater of the UCL Crypto Group (Louvain-la-Neuve, Belgium) describes the design and implementation of the timestamping service built for the Belgian TIMESEC project. A digital timestamp is defined as a digital certificate that assures the existence of a generic digital document at a certain time. The authors adopt a trusted third party (a “Secure Timestamp Authority”, STA) but deliberately engineer the system to lower the trust that must be placed in that authority to the maximum extent, drawing directly on the Haber and Stornetta linking and tree constructions.

Key points

• Two families of timestamping are contrasted: trusted third party schemes and distributed trust schemes. The authors judge distributed trust impractical for professional use and choose the trusted third party approach while minimizing required trust.
• The naive design (concatenate document with the current time and sign it) is rejected for two reasons: it demands complete trust in the authority, which could issue undetectable back-dated timestamps, and cryptographic signatures have a limited lifetime that may be shorter than the document’s needed lifespan.
• Requests are batched into fixed-duration rounds. Each round’s request hashes are the leaves of a binary (Merkle) tree; the tree’s Round Root Value is concatenated with the previous round’s Round Value and hashed to form the new Round Value, producing a hash-linked chain across rounds.
• A timestamp carries the branch values needed to rebuild the tree path plus the linking chain, so verification recomputes the Round Value up to a Round Value the verifier already trusts.
• Trust is grounded by periodically publishing certain Round Values (“Big Round Values”) in an unmodifiable, widely witnessed medium such as a newspaper; all verifiers trust these widely witnessed values and their associated times, removing reliance on the authority’s signature. Clients are required to verify timestamps immediately, so the authority is continuously audited.
• For robustness the system builds two parallel trees per round using two different hash functions (SHA-1 and RIPEMD-160), supports re-timestamping to extend a timestamp’s lifetime before a hash function breaks, and pads non-power-of-two rounds with random “Special Nodes”. The implementation is a decoupled multi-threaded pipeline (Network Listener, Request Timer, Round Queue Coordinator, Timestamp Generator, Network Answer) with defined verification, audit, start-up, and shutdown procedures.

Relevance to Truestamp

This paper is a direct intellectual ancestor of Truestamp: round-based Merkle trees with hash-linked round roots and inclusion paths are the same primitives behind Truestamp’s RFC 6962 Merkle tree and inclusion proofs, and the “between two published values” argument prefigures the submission window framing. Truestamp’s practice of recording block values on public blockchains generalizes the paper’s newspaper publication idea into modern public-blockchain commitment.

Citations

1. Design of a Secure Timestamping Service with Minimal Trust Requirement. H. Massias, X. Serret Avila, and J.-J. Quisquater, UCL Crypto Group, Belgian TIMESEC project, 1999 (hosted by the Satoshi Nakamoto Institute).