by Jean-Jacques Quisquater
Trust, transparency and traceability (or nontraceability) are important in online transactions, which may involve banks, notaries, public administrations, trusted-third-parties, witnesses and others. Even long before the internet, people in ancient civilizations used tools to create a permanent trace, such as a public (or private) ledger: Assyrian people used tablets and Incas used khipus, for instance.
In the 19th century, people dealt with the problems of synchronisation of clocks and being able to know the correct time in different locations, which was necessary to schedule trains. Telegraphy largely solved these issues - but only after lengthy negotiations (in France, it was not until 1891 that the time was unified). Synchronisation of clocks in practical situations was a research subject for Albert Einstein and others, with the eventual winner being the theory of special relativity, which is applied today in GPS.
Timestamping was an important subject for the authentication of actions. But it often needed trust in a particular authority, such as a notary, which left open the possibility of errors or cheating. Coordinated timestamping was also required for patents, music, contracts, auctions and other purposes.
In the late 1980s I was working for Philips Research in Belgium. At that time I was the head of the crypto group, which was making great inroads into the security of smart cards. In 1989, my boss asked the team to imagine new applications that might be enabled by the transition from binary flow (Shannon) to multimedia streams (sound, images, videos, etc). The idea was to translate every action (very often analogue) into the digital world. So we began considering how cryptography might be used for watermarking, timestamping and geolocalisation. We then communicated with Belgian notaries and they were very interested in our ideas. Alas, it was too early because the research into cryptographic hash functions was not yet mature enough, and the standardisation process (ISO, IETF) was then being lobbied for by banking sector, which did not understand the challenges (can you imagine today that people did not approve proposals taken into the anniversary’s paradox because it was paranoid …). Practical functions were finally proposed by Ron Rivest (MIT): the MD4 and MD5 cryptographic hash functions in 1990 and 1991 respectively. Curiously, with the exception of Raph Merkle, nobody at that time was really interested in working with these functions. However, hash functions were to become the future of digital signature, as well as blockchains and bitcoins.
The first public secure timestamping scheme, based on cryptography, was set by Stuart Haber and Scott Stornetta (1990) [1] and, even at this time, their proposals were very mature: the first one proposed chaining using cryptographic hash functions, the second one distributed the chain with a random positioning of the actors, that is, blockchain of today! They also added blocks using an idea of Raph Merkle’s (tree): then the blockchain as we know it today was ready – except for the mining and the solutions for possible forks. Mining was invented several times including the “Chinese Lotto” (1987-1991) [2]. A company, “surety.com”, acted as a trusted-third-party for a chain with only one trusted point, and a journal (NYT) as the public ledger, which didn’t require the use of internet.
A second early use of cryptographic chaining in the context of secure timestamping with broadcast was described for voting protocols by Josh Benaloh and Michael de Mare (1991) taking into account Haber-Stornetta. It is ironic that people are trying to solve voting problems using bitcoin, for instance, including the internal blockchain, when direct solutions have existed for a long time [3].
In 1996 an important timestamping project was initiated in Belgium: TIMESEC [4]. Its goals included: to improve the network time protocol for internet; to push trusted timestamping using chains; to integrate blocks as we know today, and redundant hash functions; to use several servers in a distributed and decentralized way; to examine the possible uses of cryptographic accumulators. This work took us one step closer to blockchains. A complete working demo was put on online for two years. But it was also too early for a widespread adoption.
In 2001 an important report for the Bank of Japan was written by Masashi Une under the direction of Professor Matsumoto [5]. A comparison of the seven systems of digital timestamping was described and some classification was done by including the solutions by Haber-Stornetta and TIMESEC . The challenge of a really distributed timestamping was clearly set and the solution ended up being the one by Satoshi Nakamoto inside bitcoin [6]! In fact, the introduction, together with other experiments of peer-to-peer networks on internet provided the missing link for the success of timestamping.
New ideas are continually emerging: smart contract is a promising one, with complex internal verifications in order to avoid problems (it is possible to write a “nearly” undetectable virus in powerful Turing languages like Solidity [L1]: see also openzeppelin [L2]). Current challenges are scalability, time to register (latency is too big), how to put together several blockchains (I don’t want to have hundreds of blockchains on my smartphone in the future), how to renew a blockchain if a systematic error is found, how to handle the right of forgotten (oblivion). And what about the possible power of quantum computers against the cryptographic primitives (not a complete science-fiction because NIST and NSA are thinking of soon replacing the primitives in use for bitcoin)? What are the relationships – if any - of blockchains to states and governments? How can we handle conflicts, errors, cheated contracts (a new area for lawyers?). When is consensus enough?
There are enough questions and problems to occupy many scientists and fuel numerous new projects, and I’m sure a future issue of ERCIM News is already on the cards to keep us up to date with their results. Industry-proved applications are on the way, which is very good, but we need to be very careful not to fix everything too early (standardisation): we are still at the stage of experiments, not of fully ready products. Is Algorand from Silvio Micali (MIT) [7], the next step?
Links:
[L1] http://www.ethereum.org
[L2] https://openzeppelin.org/
References:
[1] S. Haber, W. S. Stornetta: “How to time-stamp a digital document”, Journal of Cryptology, January 1991, Vol. 3, Issue 2, pp 99–111 (first presented at CRYPTO ’90). (see also patent US 5136647 A).
[2] J-J. Quisquater, Y. Desmedt: “The Chinese Lotto As An Exhaustive Code-breaking Machine”, Computer, IEEE, Vol. 24, no. 11, p. 14-22 (1991). See also IETF RFC 3607.
[3] J. Benaloh, M. de Mare: “Efficient Broadcast Time-Stamping”, TR from Clarkson University, 1991/1992.
[4] J-J. Quisquater, H. Massias, B. Preneel, B. Van Rompay: “TIMESEC final report”, 1999, https://kwz.me/Xb (Cited in [5]).
[5] M. Une: “The Security Evaluation of Time Stamping Schemes: The Present Situation and Studies”, Discussion Paper No. 2001-E-18, Institute for Monetary and Economic Studies, Bank of Japan, Tokyo.
[6] S. Nakamoto: “Bitcoin: A Peer-to-Peer Electronic Cash System, https://bitcoin.org/bitcoin.pdf
[7] J. Chen and S. Micali: “Algorand, The efficient and democratic ledger”, eprint arXiv:1607.01341 (23 May 2017).
Please contact:
Jean-Jacques Quisquater
Crypto Group, Université catholique de Louvain, Belgium, and research affiliate at MIT
