Today I found some time to read the paper How to Time Stamp a Digital Document by Haber and Stornetta. The paper tackles the problem of how digital media and documents can be modified and asks how the creation date of a document can be proven without the possibility of meddling. Classically an inventor or scientist would take notes in his lab notebook every day, leaving no space between them. A manager or notary would stamp it daily, and the combination of the physical book being hard to manipulate and the established verification procedure would testify to the legitimacy of the claimed dates and times within. The assumptions here are that any tampering is evident, and the notary is trustworthy. Both of these are called into question with digital data, which can be edited without trace. The goal then is to find a way to timestamp the data itself (not the medium) and make it impossible to stamp a false date.
A basic solution is to employ the use of a Time Stamping Service. A client would create a document and send it to the Service, which records the time of receipt and keeps a copy of the document. In the future, the Service can verify the time it received the data, and compare their copy to insure no tampering occurred. However this simple solution has numerous problems. Firstly the document may be intercepted, or be leaked from the servers of the Service. Bandwidth and storage are required to transmit and store the data. And perhaps most importantly, the veracity of the timestamp is dependent on the trustworthiness of the Service. The Time Stamping Service itself may collude with the client in order to produce a falsely predated or postdated document, edited and tampered with as well.
The Time Stamping Service idea can be improved in ways that allow us to approach our solution. Firstly, the client may hash his data before sending it to the Service. Time stamping the hash is equivalent to stamping the raw data itself, and eliminates the concern of privacy. Even better, after hashing his document the client can digitally sign it and send it to the Service, which will then append the timestamp to the document, sign it themselves, and send it back to the client. This eliminates any need for the Service to store the data, and effectively verifies that it was indeed received at the claimed time. However even this improved schema has a fundamental flaw: the Service itself may stamp a false time on the document, and we are still forced to trust it. How can we create a solution that does not rely on trusting the Time Stamping Service?
Haber and Stornetta propose a solution they call linking. In essence, the cryptographic timestamp produced by the Service must contain some linking information relating to the bits of the prior requests. In this way every timestamp is linked to all the ones prior. This service cannot falsely postdate a document, because this would require bits from data they have not yet received. Similarly, they cannot falsely predate a document, because bits of that document would then need to be present in all timestamp certificates issued afterwards. The timestamp of a document is verified by comparing those issued before and afterwards, and even an unscrupulous Service is forced to issue correct timestamps.
The authors further propose a distrusted trust system, where the hashed data is used to generate a list of random client IDs. The data is sent to these clients, who return a signed timestamp. This collection of signatures from the client pool constitutes a timestamp with no need for a centralized service.
This paper, written over 30 years ago in 1991, has laid the fundamental groundwork for all blockchain technology. Haber and Stornetta originally proposed timestamping to have value in things like copywrite, patents, and preventing tampering in business documents. Satoshi Nakamoto would combine the uses of hash functions, linking, and distrusted systems to create his blockchain and peer to peer electronic cash, bitcoin. All cryptocurrency today traces its lineage of ideas to this paper and I highly recommend anyone interested in web3 to give it a read.
No comments:
Post a Comment