Hourly batching of document fingerprints into one blockchain transaction with self-contained inclusion proofs
G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
Instead of writing one blockchain transaction per document, a service collects the SHA-256 fingerprints of all documents received in an hour, builds a Merkle tree from them and writes only the tree's root into a single transaction. Each document owner receives a small proof file listing the sibling hashes needed to recompute the root from their own fingerprint, plus the transaction ID. Anyone can later verify the document's existence time with the proof file and a public copy of the blockchain, without contacting the service.
- Merkle trees (general technique, R. Merkle, 1979)
- OpenTimestamps (existing open-source project that batches hashes into Bitcoin transactions)
Problem
Writing a separate blockchain transaction for every document is slow and expensive when fees are high, and it publishes how many documents a customer timestamps. Services that keep the link between documents and transactions only in their own database ask users to trust that database, which defeats the purpose of using a public blockchain.
Detailed description
Documents are never sent to the service; only their fingerprints (20) are. Each fingerprint is a SHA-256 hash computed on the user's device.
Every hour, the service sorts the fingerprints it received, pairs them and hashes each pair to form the next level (22), repeating until one root hash (24) remains. If a level has an odd number of entries, the last one is paired with itself. The root is written into one blockchain transaction (26) as a data field.
For each fingerprint, the service produces a proof file (28) containing: the fingerprint, the list of sibling hashes from the leaf to the root with a left/right flag for each, the root, the transaction ID and the block height. The proof file is about 1 kB for a batch of 100,000 documents (17 levels).
To verify, a user recomputes the fingerprint of their document, follows the sibling hashes up to the root, and checks that this root appears in the stated transaction in a public copy of the blockchain. The block time gives the latest possible time at which the document existed.
Example
In one hour, 3,412 fingerprints arrive. The tree has 12 levels. The root is written in a single transaction that confirms in block 912,345 at 14:07 UTC. A user later verifies a contract PDF: its fingerprint plus 12 sibling hashes reproduce the root found in that transaction, proving the contract existed before 14:07 UTC that day.
Variants
The batching interval can be fixed (every hour) or triggered by count (every 10,000 fingerprints), whichever comes first.
The root can be written to several blockchains at once, or additionally to an RFC 3161 timestamping service, so the proof does not depend on one chain.
Instead of a binary tree, a tree with more children per node can be used; the proof then lists all siblings at each level.
The proof file can be embedded in the document's metadata (for example in a PDF attachment) instead of being stored separately.
Drawings
Figure 1 shows a batch of four fingerprints (20). Pairs are hashed into the intermediate nodes (22), which are hashed into the root (24). Only the root goes into the blockchain transaction (26). The dashed box (28) is the proof file a document owner receives.