gm creators!
It's almost Friday, hang in there 😎
Yesterday I went in-depth on how onion routing works and gave the origin story of the Tor network (the onion router).
Contrary to popular belief, the building of anonymous communication and onion routing was not a hacker project to sell drugs but was in fact led by the U.S. naval research laboratory for secure military communication in the mid-90s.
You can check out the full post here!
If you're new to The Bigger Picture, welcome! I'm learning & writing about the history of cryptography.
Subscribe below so you don't miss any future TBP posts 🥂
Today at a Glance 👓
Today, I'm briefly covering the stories behind one of the most important papers to be published in the field of computer science: The Byzantine Generals Problem. This research paper by Leslie Lamport, Marshall Pease, and Robert Shostak was published in July 1982.
If you're in the crypto space or have taken an intro class in distributed computing, there's a good chance you've heard of the Byzantine Generals.
The paper addressed the challenge of achieving consensus within a distributed system where some participants may be bad actors and act maliciously.
What was most interesting to me while doing the research for this post were the motivations of why Leslie Lamport wrote this paper in the first place 👀
Sections Below
The Chinese Generals
It's just a dining table!
Beyond academia
Let's dive in 🚀
The Chinese Generals
Before we get into the Byzantine Generals problem, it's important we go back a couple of years before that paper and discuss The Chinese Generals (aka Two generals) problem. Clearly these gigabrain computer scientists love their war analogies 😂
Anyways, the two generals problem was first introduced in a 1975 publication by E. Akkoyunlu, K. Ekanadham, and R. V. Huber. At this time, computer networks were starting to grow rapidly and the nascent field of distributed computing was slowly becoming increasingly important.
The premise of the problem is as follows:
Imagine there are two generals that are placed on either side of a mountain on where the enemy is.
They have to attack at the same time to win or else the side that attacks alone will get defeated.
The generals of each side have to communicate to each other on when to attack.
So let's say general A sends a messenger to general B to attack at 4.
And then general B gets the message. How does general A know B got that message?
B can send a confirmation. But then how does B know A got the confirmation?
This basically becomes an endless loop
The Chinese Generals problem shows us that it's impossible to guarantee message receipt in a system with unreliable communication.
Similarly, in computing, no matter how many confirmation messages you send, in an unreliable communication channel, there's no way to guarantee 100% message receipt. This is the inherent difficulty of achieving consensus in distributed systems.
It's just a dining table!
7 years later, three other computer scientists - Leslie Lamport, Marshall Pease, and Robert Shostak - decide to expand on the two generals problem.
What was interesting about this problem is that the initial motivation for Leslie Lamport to write this paper was to simply tell a better story around the two generals problem:
I have long felt that, because it was posed as a cute problem about philosophers seated around a table, Dijkstra's dining philosopher's problem received much more attention than it deserves.....The popularity of the dining philosophers problem taught me that the best way to attract attention to a problem is to present it in terms of a story. -Lamport's Website
But...the issue was that he couldn't just publish a paper that presented the same problem with a different narrative. So they add another layer of complexity. The new paper needed "new results".
Instead of just two generals, they expand the problem to multiple generals. Additionally, the catch is that some of these generals can also be bad actors. Meaning they might purposely manipulate the message or not reveal fact that they got the message.
Initially, Lamport was planning to call the paper "The Albanian Generals problem"...
I wanted to assign the generals a nationality that would not offend any readers. At the time, Albania was a completely closed society, and I felt it unlikely that there would be any Albanians around to object, so the original title of this paper was The Albanian Generals Problem.
But then his partner mentioned that there are of course Albanians outside Albania.
So then Lamport realized that Byzantine made more sense anyways. The Byzantine empire's army was notoriously intricate and they would test the system to make sure there weren't any traitors within the group. In Constantinople, the capital of the Byzantine empire, politics reached a new height of deception and double dealing. Betrayal was common.
This name did a way better job of fitting the context of the problem.
Leslie Lamport’s motivation emphasizes a crucial aspect of academia and technology.
The way results that are presented can have a huge impact on how they’re received. A vivid analogy or narrative can make the difference between a paper that's cited by a handful and one that becomes foundational.
By introducing multiple generals that could be malicious, the Byzantine generals problem paints a more accurate picture of the world we live in. Not everyone can be trusted.
Satoshi releasing the Bitcoin whitepaper in 2008 was such a big breakthrough because it used proof of work in the form of mining to ensure it literally unaffordable for bad actors to act maliciously. Essentially, Satoshi took the pre-existing concept of proof-of-work and used it to provide a solution to the Byzantine Generals. This enabled the world to have the world's truly first decentralized form of hard money.
For the first time ever, there was no need to trust a king, president, or corrupt government with the balance sheet and production/facilitation of money.
Of course, Bitcoin proof-of-work is one common example that is talked about when it comes to the Byzantine Generals problem. However, the implications reach far past the crypto world.
Beyond Academia
In real world systems, components don't just fail - sometimes they can behave unpredictably.
Think about the world of finance, airline traffic control, or even nuclear facilities. A single node (general) that gets tampered with has the potential to cause a catastrophic disaster.
It's not just important but rather essential to be able to verify, not just trust, that the system will behave the way it was programmed to.
Distributed databases, cloud computing, network security, storage networks, and file systems all need to ensure data integrity and manage tampered information.
So what does this mean for us?
Beyond the complex theories and hacker jargon, the essence of the Byzantine Generals problem is about trust in an unpredictable digital world. As our lives become more intertwined with technology, ensuring that these systems are robust against malicious attacks is not just a technical challenge but a societal one.
That's all for today's post - if you enjoyed, I'd love for you to share with your friends in crypto :)
Remember, all posts are collectible as well! Just connect your wallet and mint away.
Also, if you haven't already, please join The Bigger Picture community by hitting the subscribe button below. You can connect your wallet or add your email!