The Byzantine Generals Problem is one of history's top 10 computer science problems, and this chapter will go into detail about what the problem is and how blockchain technology solves it. Most people don't understand that this is the root, so we feel that if you have your arms around this, you have taken a giant leap in your understanding of why blockchains are relevant.

The problem asks how any network can come to consensus without a trusted third party or central authority. For the past 50 years, there was no way to get to consensus without having that trusted third party. Bitcoin and blockchain solve this problem in such an innovative way that new things are now possible in many areas, including money and currency. We'll keep it light and fun.

Some Other  Top Computer Science Problems

There's been a list of top computer science problems going back to the early days of the computer. Many of the problems on that list have been there for decades. We have waited to solve the Byzantine Generals Problem for over four decades, so when a solution did come in 2009, it was surprising how little fanfare greeted the proposal.

Other top computer science problems that are still on the list include things like:

• An optimal solution for a binary tree search algorithm—how to find the solution the fastest within a sorted data structure
• Computational complexity—how to classify and optimize computational problems according to their resource usage
• Optimal algorithm for matrix multiplication—how to determine if there is a proven fastest solution to matrix multiplication, which has to do with multidimensional arrays (lists) of numbers
• Natural language processing algorithm—how to determine if there is an optimal algorithm for stemming, syllabification, phrase chunking, and discerning pronoun ambiguity in a natural language like English
• Evasiveness conjecture—how to determine questions like “Is there an edge between vertex y and vertex z?” This would answer the question if every single number would have to be compared or if there might be a shortcut of some kind. This is a group of related conjectures. A solution to this problem could have wide application, from the ultimate voice recognition software to creating the best resource allocation optimization algorithms, saving any logistics companies billions, to breaking the current encryption that secures all Internet commerce. Encryption is at the backbone of so many applications. This could improve all software applications, and the solution to this problem is worth trillions of dollars.

Many of these computer science problems have to do with finding an answer in an optimal way and being able to prove that it is the optimal solution. The biggest outstanding computer science problem today is “real one‐way functions.” These mathematical functions can process every single input very easily, but obtaining the input back from a random set of output values is very difficult. We have theories about one‐way functions, but we have yet to prove them. The way cryptography and hash functions are used in blockchain technology is theorized to be an application of one‐way functions, but we can't prove it. An answer to each of these top computer science problems is worth trillions of dollars, which shows just how hard of a problem they are to solve.

We understand that, for most readers, this is about as dry as chewing on saltines, but we want to underscore that this is not trivial stuff. This is not funny money or magic digital art. This is a breakthrough that had computer scientists all over the world popping bottles of Dom Perignon.

What Is BGP and Why Is It So Important?

The problem that got solved with the invention of Bitcoin and blockchain technology is called the Byzantine Generals Problem (BGP). BGP is a game‐theory problem that explains the complexity of organizing an attack using decentralized parties that must agree (gain consensus) without having one trusted leader to organize the whole thing. This is also compounded by all inside mistrust. In a network where no participant can verify the identity of other participants, how can the group collectively agree on a solution?

The explanation goes like this. Say you have a bunch of generals from one army trying to besiege the enemy city of Byzantium. They are all staged around the city but are not under any kind of central coordination. The army must coordinate an attack so that they all strike simultaneously, so the generals must reach an agreement (consensus). If all the armies attack simultaneously, they will win the battle. But if they don't and attack at different times, they will lose. Defenders can send false messages. They do not have secure communications, so messages could be intercepted, or the enemy could employ counterintelligence to sabotage their coordinated attack. How can the generals coordinate their attack?

Solving this problem is important because prior to solving this, all circumstances similar to this required a trusted central party to solve the problem. A centralized solution then comes with the problem that there is now a single point of failure. In the example of the coordinated battle, if the central leader is killed, no coordination is possible. In the example of money and commerce, the whole system dies if the trusted third party, be it a bank, a government, or a company, is compromised.

How Bitcoin Solved BGP

As a monetary system, Bitcoin needed a way to manage ownership and prevent double spends. If all nodes in the Bitcoin network could agree on which transactions occurred and in what order, they could verify each transaction, the ownership of each bitcoin, and establish a functioning, trustless money without a centralized authority. In our BGP example, the nodes are like the generals, operating as peers but without a central control.

By implementing PoW consensus, Bitcoin solved the Byzantine Generals Problem by implementing an objective ruleset for the blockchain. In order to add a set of ordered transactions, called blocks, to the blockchain, a node of the network must publish proof that they have invested considerable work into creating the block by computing a new hash. This work imposes large costs and thus incentivizes them to publish honest information.

Because the rules are objective, there can be no disagreement or deception with the information published to the public ledger. The ruleset governing which transactions are valid is also objective, as is the system for determining who can earn block rewards (mint new bitcoin). Additionally, once a block has been added to the blockchain, it is permanent, making Bitcoin's historical transactions immutable.

BBC Show Fake or Fortune Illustrates the Problem

One of my favorite ways to spend my time is to watch documentaries and series on Amazon. I've watched all the mainstream series so many times I have to dig. One hot summer evening here in Austin, I stumbled upon a series from the BBC called Fake or Fortune. I'm really into art, especially contemporary art, but this show covers fine art from the masters like Degas, Picasso, Rembrandt, and Monet. The series follows people who have purchased art on the belief that they have a real original work from a master, and then the show's duo, Phillip and Fiona, set out to help prove whether the artwork is, in fact, a fake or a fortune. They team up to investigate these sleeper paintings that could be forgeries or genuine original masterpieces that no one knew existed. The team uses cutting‐edge technology, forensics, and their experience to see if they can help people determine whether their artwork is a fake or a fortune, just as the name of the series implies.

The first episode starts with “The art world, filled with glamour, wealth, intrigue” and shows an auction with an auctioneer spouting prices of “$100,000, $200,000 . . . sold for $95,000,000.” It explains that there's a darker side of the art world filled with high stakes and gambles. This episode follows a man who believed he had found a real Claude Monet picture. The painting is framed with the thick gold leaf framing you would expect to encase a landscape scene from the Impressionist period for which Monet is known. The man had purchased his painting almost two decades earlier and is looking to prove that it's a genuine Monet.

There's something a little different about how one goes about determining whether a Monet is considered a Monet. There is a book published by a powerful billionaire art dealer family, the Wildensteins, called the Monet Catalog Raisonne. This five‐volume tome is what all the major auction houses use to determine whether a painting is considered a genuine Monet or not. The patriarch, Daniel Wildenstein, first published the catalog in 1974.  After he died in 2001, his son, Guy, took over for the family, and he heads the Monet Committee, which publishes the catalog and determines which works of art make it into the catalog. Guy, almost single‐handedly, inherited the power to determine whether a Monet is considered genuine through his position on the Monet Committee and being the publisher of the catalog.

Eighty‐two‐year‐old David Joel is the owner of Bords de la Seine à Argenteuil, the work in question, and he's been trying to get the painting into the catalog for 18 years. He's written the Committee many times. Initially, it was the father Daniel who rejected the painting, saying that it was not a real Monet. The Wildensteins say they need two pieces of evidence: documentary evidence that the painting existed in Monet's lifetime and the provenance to track the painting's ownership through art dealer records that would prove the work was sold through one of Monet's dealers at the time. The provenance of the painting needs to track the entire history of ownership. If David can provide these two pieces of evidence, they say the painting will make it into the catalog. So, with his wife, David continues to mount evidence that his painting is an actual Monet.

The series takes the viewer through many adventures from England to Paris to Cairo, Egypt. Phillip, the art expert of the show duo, starts by comparing the signature of Claude Monet. Using experts and special HD camera technology, they compare the signature on David's picture to other Monet paintings that have been validated. The signature does match! The show takes us to Paris where they first look at a stamp on the back of the painting, which says “La Touche.” La Touche was an art supplier to many Impressionists back in the day. The duo can prove that La Touche supplied Monet with his art supplies and specific chemicals to make the colors Monet used in his works. They can show that Monet and La Touche were actual friends, proving the painting existed during Monet's lifetime. And it continues.

The show takes us to an art salesroom in Norwich, England, where David bought the painting for about £40,000, a substantial amount of money, but nothing compared to what it would be worth if it were to be entered into the catalog as a genuine Monet. The painting would easily be worth over a million pounds. After the La Touche connection is made, we go to Paris to the Musée Marmottan, which houses the largest collection of Monets in the world. The team uses a Lumiere HD Camera with 240 m pixels, some 100 times more detailed than an average HD camera. The camera can see more about the paint and the work to make this picture. Under the lighting, the camera shows that the brush strokes match Monet's. There we also discover the package stamp on the back of the painting, indicating a dealer stamp with a number. This number is an inventory number of a dealer and, with that in hand, the team travels to Cairo to gather even more evidence. The duo, Phillip and Fiona, find more than they could imagine. The dealer stamp matches up with the leading Monet art dealer of the time, which clearly shows that the painting went directly from Monet to his main art dealer at the time and provides the provenance David needs to prove that his picture is the real McCoy. The episode goes on to show the viewers a list of leading Monet scholars, like the Royal Collection Trust and connoisseurs who believe the painting is genuine.

So, the show ends with the team enlisting professor John House, whom we were introduced to earlier, to take the painting in front of the Monet Committee and, with all the new evidence in hand, get a new determination from the Committee. Recall that two items were requested: documented evidence that the painting existed in Monet's time and proof that the piece was sold by one of Monet's dealers. Our protagonist provided both, yet, even with that and the mountain of evidence, Guy Wildenstein refuses to go against his father's original decision and does not reverse the Committee's stance. It is an epic blow to David and all of the viewers that this injustice is not rectified. It all comes down to this one person, and because of politics or something that has nothing to do with whether this painting is real or not, the painting does not make it into the catalog and therefore will not be considered a real Monet. Welcome to the impact of a system that is centralized – in this case, around one person.

While this isn't a big deal in consideration of everything that's going on in the world, it is an excellent analogy to all the problems that come with having one person or a small group determine a decision. A jury of 12 can be bribed. It's not only conceivable that one person can be coopted (which is generally enough), it's a small enough group that it's conceivable that a majority could be compromised. When consensus requires thousands or hundreds of thousands of participants, it becomes nearly impossible for a corrupt person or group, an unreasonable few, or a powerful self‐serving person or persons to blow up a good process. That's the power of blockchain and peer‐to‐peer consensus. Mature blockchains use hundreds of thousands of nodes in their decentralized network that all need to agree in order to input a valid list of transactions. The resolution to the BGP will lead to innovations we cannot even conceive of at this point in time. It affects applications of digital signatures, art provenance, and title history provenance for real estate or art or luxury brands. It applies to supply chain management and food to ensure that the record of ownership is accurate and true. It applies to medical records and a digital money system. Separating ownership and possession and implementing a public ledger whose entries are immutable create vast possibilities for a digital world that previously just was not possible. The ramifications of solving BGP will become ever more apparent in the years to come. We can do things now we couldn't do before. This, then, is what we call the blockchain breakthrough. This is why we care about any of this at all.