World-leading Computer Scientists: Leslie B Lamport

Clocks, LaTeX, Byzantine Generals and Post Quantum Crypto

Apple [here] Spotify [here]

I write this article in Medium and with its limited text editor, but I really would love to write it in LaTeX. Before the monopoly of Microsoft Word, there were document mark-up systems such as Lotus Manuscript, and where we had a basic editor to produce publishing-ready content. The GUI came along, and all the back-end stuff was pushed away from the user. For many, this is fine, but for those whose output is focused on sharing and dissemination of research, it is often the only way to work.

In research, LaTeX is King and is a fully formed method of laying out — and sharing — research outputs. In the past few years, we have published over 100 research papers, and not one of them has been created in Microsoft Word. And for this, I thank Leslie Lamport.

In fact, ask our kids about Newton, Faraday or Einstein, and they could probably tell you something about them. But ask them about Whitfield Diffie, Shafi Goldwasser, or Leslie B Lamport, and they would probably look quizzical? Their future world, though, is probably going to be built around some of the amazing minds that built the most amazing structure ever created … The Internet.

To Leslie Lamport

So, I am so privileged to be an academic researcher. For me teaching, innovation and research go hand-in-hand, and where the things I research into gives me ideas for innovation, and which I can then integrate these things into my teaching. The continual probing of questions from students also pushes me to think differently about things, and so the cycle goes on. But, we are all just building on the shoulders of true giants, and there are few larger giants than Leslie Lamport — the creator of LaTeX.

For me, every time I open up a LaTeX document, I think of the work he did on creating LaTeX, and which makes my research work so much more productive. If I was still stuck with Microsoft Office for research, I would spend half of my time in that horrible equation editor, or in trying to integrate the references into the required format, or in formatting Header 1 and Header 2 to have a six-point spacing underneath. So, for me, the contest between LaTeX and Microsoft Word is a knock-out in the first round.

And one of the great things about Leslie is that his work is strongly academic — and which provides foundations for others to build on. For this, he did a great deal on the ordering of task synchronisation, in state theory, cryptography signatures, and fault tolerance.

LaTeX

I really can say enough about how much LaTeX — created in 1984 — helps my work. I am writing a few books just now, and it allows me to lay out the books in the way that I want to deliver the content. There’s no need for a further mark-up, as I work on the output that the reader will see. But the true genius of LaTeX is the way that teams can work on a paper, and where there can be async to GitHub and where version control is then embedded.

Overall we use Overleaf, but we’re not tie-in to that, and can move to any editor we want. But the process is just so much better than Microsoft Word, especially when creating a thesis. Word is really just the same old package it was in the 1990s, and still hides lots away, and which makes it really difficult to create content which can easily be changed for its layout. With LaTeX, you create the content and can then apply whatever style you want.

Clocks

Many in the research community think that the quality measure of a paper is the impact factor of the journal that it is submitted to, or in the amount of maths that it contains. But, in the end, it is the impact of the paper, and how it changes thinking. For Leslie, in 1978, his paper on clocks changed our scientific world and is one of the most cited papers in computer science [here]:

Byzantine Generals Problem

In 1981, Leslie B Lamport defined the Byzantine Generals Problem [here]:

And in a research world where you can have 100s of references in a paper, Leslie only used four (and which would probably not be accepted these days for having so few references):

Within this paper, the generals of a Byzantine army have to agree to their battle plan, in the face of adversaries passing in order information. In the end, we aim to create a way of passing messages where if at least two out of three of the generals are honest, we will end up with the correct battle plan. So why don’t we build computer systems like this, and where we support failures in parts of the system, or where parts of the system may be taken over for malicious purposes? And the answer is … no reason, it just that we are stuck with our 1970s viewpoint of the computing world, and everything works perfectly, and security is someone else’s problem to fix.

So, we need a system where we create a number of trusted nodes to perform a computation, and then an election process at the end to see if we have a consensus for a result. If we have three generals (Bob, Alice and Eve), we need two of them to be honest, which means we can cope with one of our generals turning bad:

In this case, Eve could try and sway Trent by sending the wrong command, but Bob and Alice will build a better consensus, and so Trent will go with them. The work can then be defined as MPC (Multiparty Computation) and where we have multiple nodes getting involved to produce the final result. In many cases, this result could just be as simple as a Yes or No, and as to whether a Bitcoin transaction is real or fake, or whether an IoT device has a certain voltage reading.

The Lamport Signature

Sometime soon we perhaps need to wean ourselves of our existing public key methods and look to techniques that are more challenging for quantum computers. With the implementation of Shor’s algorithm [here] on quantum computers, we will see our RSA and Elliptic Curve methods being replaced by methods which are quantum robust. One method is the Lamport signature method and which was created by Leslie B. Lamport in 1979 [here]:

At the current time, it is thought to be a quantum robust technique for signing messages. When we sign a message we take its hash and then encrypt it with our private key. The public key is then used to prove it and will prove that we signed it with our private key. The Lamport signature uses 512 random hashes for the private key, and which are split into Set A and Set B. The public key is the hash of each of these values. The size of the private key is 16KB (2×256×256 bits) and the public key size is also 16 KB (512 hashes with each of 256 bits).

The basic method of creating a Lamport hash signature is:

• We create two data sets with 256 random 256-bit numbers (Set A and Set B). These are the private key (512 values).
• Next, we take the hash of each of the random numbers. This will give 512 hashes and will be the public key.
• We then hash the message using SHA-256, and then test each bit of the hash (0 … 255). If it is a 0, we use the ith number in Set A, else we use the ith number from Set B.
• The signature is then 256 random numbers (taken from either Set A or Set B) and the public key is the 512 hashes (of Set A and Set B).

This process is illustrated below:

We can use the Lamport method for one-time signing, but, in its core format, we would need a new public key for each signing. The major problem with Lamport is thus that we can only sign once with each public key. We can overcome this, though, by creating a hash tree which is a merger of many public keys into a single root. A sample run which just shows the first few private keys and the first public keys:

==== Private key (keep secret) =====
Priv[0][0] (SetA):  6f74f11f20953dc91af94e15b7df9ae00ef0ab55eb08900db03ebdf06d59556c
Priv[0][1] (SetB):   4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619
Priv[1][0] (SetA):  19f0f71e913ca999a23e152edfe2ca3a94f9869ba973651a4b2cea3915e36721
Priv[1][1] (SetB):   04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097e
Priv[2][0] (SetA):  15ef65eda3ee872f56c150a5eeecff8abd0457408357f2126d5d97b58fc3f24e
Priv[2][1] (SetB):   8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073
Priv[3][0] (SetA):  1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346
Priv[3][1] (SetB):   e9dcbdd63d53a1cfc4c23ccd55ce008d5a71e31803ed05e78b174a0cbaf43887
==== Public key (show everyone)=====
Pub[0][0]:  7f2c9414db83444c586c83ceb29333c550bedfd760a4c9a22549d9b4f03e9ba9
Pub[0][1]:   4bc371f8b242fa479a20f5b6b15d36c2f07f7379f788ea36111ebfaa331190a3
Pub[1][0]:  663cda4de0bf16a4650d651fc9cb7680039838d0ccb59c4300411db06d2e4c20
Pub[1][1]:   1a853fde7387761b4ea22fed06fd5a1446c45b4be9a9d14f26e33d845dd9005f
==== Message to sign ===============
Message:	The quick brown fox jumps over the lazy dog
SHA-256:	d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]:	4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619
Sign[1]:	04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097e
Sign[2]:	8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073
Sign[3]:	1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346
The signature test is  True

In this case, we take the random number and then convert it to a string. So the SHA-256 signature of “6f74f11f20953dc91af94e15…0db03ebdf06d59556c” is 7f2c9414db83444c586c…49d9b4f03e9ba9. If can be seen that the hash of the message (“The quick brown fox jumps over the lazy dog”) has a hex D value at the start, which is 1101 in binary, and we see we take from SetB [0], SetB [1], SetA [2] and SetB [3]. A demonstration is given here.

Conclusions

The Internet we have now built on the foundations that Leslie applied. On 18 March 2013, he received the AM Turing Award (which is like a Nobel Prize in Computer Science). At the time, Bill Gates said:

Leslie has done great things not just for the field of computer science, but also in helping make the world a safer place. Countless people around the world benefit from his work without ever hearing his name. … Leslie is a fantastic example of what can happen when the world’s brightest minds are encouraged to push the boundaries of what’s possible.

Basically, much of our computing world is still using the amazing foundation that was created in the 1970s and 1980s. We tip our hats to Diffie Hellman, Shafi Goldwasser, Ralph Merkle, Ron Rivest, Adi Shamir, and, of course, Leslie B Lamport. As a note, that while Leslie’s paper on Clocks is cited over 12,000 times, the Diffie Hellman paper is cited over 19,300 times:

We really should be integrating computer science into our school curriculum, and show that it has equal standing to physics, biology and chemistry, and it will shape our future world as much as the others. Why not teach kids about public-key cryptography in the same way that we talk about Newton?