Cryptographic timestamping through Sequential Work

We present a definition of an ideal timestamping functionality that maintains a timestamped record of bitstrings. The functionality can be queried to certify the record and the age of each entry at the current time. An adversary can corrupt the timestamping functionality, in which case the adversary can output its own certifications of the record and age of entries under strict limitations. Most importantly, the adversary initially cannot falsify any part of the record, but the maximum age of entries the adversary can falsify grows linearly over time. We introduce a single-prover non-interactive cryptographic timestamping protocol based on proofs of sequential work. The protocol securely implements the timestamping functionality in the random-oracle model and universal-composability framework against an adversary that can compute proofs of sequential work faster by a certain factor. Because of the computational effort required, such adversaries have the same strict limitations under which they can falsify the record as under the ideal functionality. This protocol trivially extends to a multi-prover protocol where the adversary can only generate malicious proofs when it has corrupted at least half of all provers. As an attractive feature, we show how any party can efficiently borrow proofs by interacting with the protocol and generate its own certification of records and their ages with only a constant loss in age. The security guarantees of our timestamping protocol only depend on how long ago the adversary corrupted parties and on how fast honest parties can compute proofs of sequential work relative to an adversary, in particular these guarantees are not affected by how many proofs of sequential work honest or adversarial parties run in parallel.