Haber and Stornetta 1991: The Timestamping Paper Behind the Blockchain

How to Time-Stamp a Digital Document by Stuart Haber and W. Scott Stornetta appeared in the Journal of Cryptology, volume 3, number 2, pages 99-111, in 1991. It was presented the year before at CRYPTO '90. Both authors worked at Bellcore — Bell Communications Research — in Morristown, New Jersey.

The Bitcoin whitepaper cites eight sources. Three are by these two authors. That fact is the basis for the frequent claim that the blockchain was invented in 1991, not 2008. The claim is partly right, and this guide sets out exactly which part.

Read the paper: it is available from Springer under DOI 10.1007/BF00196791, and a preprint version circulates widely. It is fourteen pages, mostly readable without a cryptography background.

The Problem They Set Out to Solve

The opening frames a problem that had nothing to do with money. When documents become digital files on easily modifiable media, how do you certify when one was created or last changed? Their formulation is the memorable part: the problem is to timestamp the data, not the medium.

Paper records carry physical evidence of age — ink, fibre, wear. A digital file carries none. A patent dispute, a lab notebook, a contract, a photograph presented as evidence: all of these depend on establishing an order of events that digital media cannot demonstrate on their own. The authors cite a 1990 New York Times piece on the manipulability of digital photographs among their motivations.

Two requirements are non-negotiable in their design. The service must not see the document, only a hash of it, so confidentiality is preserved. And the service must not be trustable in the ordinary sense — the scheme has to work even if the timestamping service itself wants to help a client backdate a record.

The Argument, Step by Step

The paper builds up through three designs, each fixing the previous one's weakness. This structure is worth following, because the third step is the one that matters historically.

Step 1: The naive solution

A "digital safety-deposit box". The client sends the whole document to a timestamping service, which records the date and stores a copy. Disputes are settled by comparing against the stored copy.

This works and is useless. It requires enormous storage, breaks confidentiality, creates a bandwidth bottleneck, and risks loss or corruption of the archive. Worse, it does nothing about the core problem: nothing prevents the service from colluding with a client to certify a false date.

Step 2: Hash the document, sign the hash

The client hashes the document locally and sends only the hash. The service appends the current time, signs the pair, and returns the certificate. Storage, privacy, and bandwidth are all solved at once, because the service never sees the document and stores almost nothing.

The trust problem survives intact. A service willing to lie can sign any time it likes.

Step 3: Constrain the service so lying becomes impossible

This is the contribution. The authors offer two independent solutions.

Linking. The sequence of timestamp requests is itself evidence. Each certificate contains the request's sequence number, time, client identifier, and document hash, plus linking information carried over from the previous certificate — including a hash of that previous certificate's linking data. The service also gives the client the identifier of the next client in the sequence.

The result is a chain. The service cannot forward-date a document, because a certificate must contain bits from requests that had not yet arrived. It cannot backdate one either, because doing so would require rewriting every certificate issued since, all of which are held by other clients who can be called as witnesses. A challenger can walk the chain forward or backward as far as suspicion requires.

Distributed trust. The second solution removes the central service altogether. The hash of the document seeds a secure pseudorandom generator, whose output selects k clients from the user population. Those clients sign the timestamp. Because the document's own hash determines the witnesses, a forger cannot choose who will vouch for the record — they would have to find a document hash that happens to select a set of corruptible witnesses, which the paper shows is infeasible for a sensible k, even under the pessimistic assumption that most of the population is corruptible.

Why It Is Called the Origin of the Blockchain

Line up the 1991 linking scheme against a modern chain and the correspondence is direct:

The 1993 follow-up, Improving the Efficiency and Reliability of Digital Time-Stamping with Dave Bayer, closes the remaining gap. It groups requests into batches, builds a Merkle tree over each batch, and links the roots. A batch of records committed by a Merkle root, chained to the previous batch, is a block in everything but name. Haber has said as much in interviews: they did not call it a blockchain, but grouping records into what he now calls a block, building a Merkle root, and linking them together is exactly what they described.

And it shipped. In 1994 the authors spun Surety out of Bellcore, and from 1995 the service has published a weekly summary hash — one that depends on every request it has ever processed — as a small classified advertisement in the national edition of the Sunday New York Times. That hash chain has run continuously for over three decades, which makes a reasonable case for Surety, not Bitcoin, as the longest-running blockchain in existence. The original deployment hashed with MD5 and SHA-1 in parallel, hedging against a break in either; it was later migrated to SHA-256 and RIPEMD-160, the two functions Bitcoin also uses.

Where It Differs From Bitcoin

Four differences, and they are not small.

There is still a service. The linking scheme constrains the timestamping service but does not remove it. Somebody accepts requests, assigns sequence numbers, and issues certificates. Bitcoin has no such role — any node can produce the next block, and which one does is decided by a race.

No proof-of-work. Order in the 1991 scheme comes from the service's sequence numbers and the interlocking of client certificates. Order in Bitcoin comes from expending energy. This is why the 1991 design needs an identifiable client population and Bitcoin does not.

No Sybil resistance and no incentive. The distributed-trust variant assumes a known pool of clients and a bounded corrupt fraction. In an open network where anyone can create unlimited identities, that assumption collapses — which is precisely the problem proof-of-work solves. There is also nothing to pay the witnesses; Surety solved this by being a business with customers.

It timestamps, it does not transact. The scheme proves a document existed at a time. It says nothing about who owns what, and it cannot prevent double spending, because there is nothing to spend. Bitcoin's ledger is a statement about ownership, and that is a strictly harder problem.

Put plainly: Haber and Stornetta invented the data structure. Nakamoto invented the way to maintain that structure among mutually distrusting strangers with no one in charge. Calling either one "the blockchain" alone is a compression of the history.

What Both Authors Have Said About Bitcoin

Neither has ever claimed to have invented Bitcoin, and both have been consistent about the division of credit. Their scheme assumed a trusted repository for the widely witnessed value — a newspaper, and later the newspaper's global archive. Bitcoin's insight was to replace both the timestamping service and the repository with a set of miners incentivised to perform those roles, and to resolve disagreement by weight of accumulated work. Stornetta has described this in talks as the missing piece their own work never supplied.

For a period, the coincidence of dates fed speculation that one of them was Satoshi Nakamoto. There is no evidence for it, and both have denied it.

How to Cite the Paper

The standard citation, matching reference [3] of the Bitcoin whitepaper:

S. Haber, W.S. Stornetta, "How to time-stamp a digital document,"
Journal of Cryptology, vol. 3, no. 2, pp. 99-111, 1991.
DOI: 10.1007/BF00196791

The conference version is in Advances in Cryptology — CRYPTO '90, Lecture Notes in Computer Science volume 537. When a source dates the work to 1990, that is the version being referenced.

Related Reading

• The Bitcoin Whitepaper, Annotated — where Section 3 puts this paper to work
• Pre-Bitcoin Digital Cash Papers — the parallel line of work on money
• Primary Sources Archive Index — full chronological document list