Hi folks. I was going to publish this on r/bitcoin but those people don't take me seriously so I figured I'd share it with my friends here at r/buttcoin instead. This is not a critique of Bitcoin. I am simply going to explain the Byzantine Generals problem in laymen's terms.

When I went to college I learned about a seminal problem in computer science called the "Albanian Generals Problem." (That somewhat dates me: these days the PC crowd has turned it into the Byzantine Generals problem.) It is often called "Byzantine fault tolerance" because it was an attempt to address communication over an unreliable medium, such as a line with static.

However, it can also involve a case where a man-in-the-middle intentionally wants to confound communications by changing the messages. We'll get back to that notion later.

I: TWO ARMIES, ONE CITY

The premise of the Byzantine Generals story is this: there is a city in a valley, and two armies on high mountain tops on opposite sides. Illustration: http://imgur.com/to4qRaI

The generals and their armies want to attack the city. However, they need to attack at almost exactly the same time or they will fail. Therefore they send messengers (packets) to the other mountain saying something like "We attack at dawn on Saturday! Please send a messenger back to confirm that you received this."

But there's a problem: that city in the middle may either catch a messenger and throw him in jail, or even worse, replace the messenger with a spy who delivers a disastrously different message, such as "We attack at midnight! No need to reply!"

I was taught—in fact it was proved indisputably—that the problem has no true solution. That's not to say computers cannot communicate with each other reliably, but 100% certainty is not possible. Our best efforts simply make communication very very reliable but never foolproof.

For example, in the above example the general receiving the message is intended to send back a messenger to say "OK, noon on Saturday it is." What happens if the return messenger gets caught or modified? Of course the return message might say "Let me know that you got this confirmation with yet another messenger" but then that one might get caught or modified. This infinite regress lets us know that we're going to have to do something tricky to get the message across with some degree of certainty.

There are several practical "solutions" to the problem which are good enough to work in the real world where we know that nothing is certain.

Satoshi never claimed to have "solved" the problem, just proposed a method which makes it very difficult for the town to foil the plans of the generals by modifying the message. This has bearing on a digital currency, because "attack at dawn!" is the same thing as saying "I give Sue $10". It's important that the message gets through unaltered.

II: CRYPTOGRAPHIC HASH FUNCTIONS

Before we get into Satoshi's "solution" to the problem there's a tiny piece of technical understanding you need to grasp: what a hash function is.

Many of the the nerds reading this article probably already know this stuff like the back of their hands, but I titled this "for dummies" so I will explain what cryptographic hashing is. If you already understand the concept, feel free to skip ahead to part III.

A hash function will receive an input, whether a single number, or a string, or an entire text file, and come up with a large number based on the input. For example, I made a hash function h(s) that accepts a string and returns a number. Some example outputs:

h("X") = 192810249468957222384
h("BOZO") = 801280015127385626279
h("MARY HAD A LITTLE LAMB") = 1029916079814280347836
h("MARY HAD A LITTLE LAMP") = 6719333915074502386405

What makes it cryptographic is that it is a "trapdoor function" that allows you to easily compute the hash given the string, but given the giant number it's virtually impossible to compute the string. It is possible to come up with a string that produces that number only by taking wild guesses until you just happen to luckily stumble upon a string with that property. Depending on how big the output number is, the more guesses you'll have to make (on the average) before you figure out the string.

Also it's important to note that the tiniest change to the input string will result in wild changes in the output.

Hash functions have all sorts of great real world applications. They ensure that your download was received correctly, they can be used to confirm that somebody knows their password even though you don't actually know their password, and much much more.

III: SOLVING THE PROBLEM WITH NONCES

So let's say the generals have modern computers. They have a really clever idea. They will make a message such as "ATTACK AT DAWN" and then add a little extra piece of nonsense at the end of the message. This little extra string is called a "nonce." For example, the message may now read "ATTACK AT DAWN e8Mgk10938". Then the generals agree to a policy: that the hash of the message (including the nonce) must yield a number that begins with at least ten sevens, lest it be regarded as a hoax. So when the generals run our hash function on the string they get this:

h("ATTACK AT DAWN e8Mgk10938") = 7777777777323915073765

This is accomplished with computer power. The general broadcasting the message had his techies stay up all night running his computer trying all sort of different random nonces until they stumbled upon one, through sheer luck, that started with ten sevens. You can compute the average time it takes to do this: with 10 sevens you'll need to make about 5 billion guesses; sometimes more, sometimes less. Let's say that in this case it takes about 12 hours to get the job done.

This method of setting computers to a task that will likely take a very long time to complete is called Proof-of-Work.

Now the general sends several messengers (to make sure one gets across) all with this weird message "ATTACK AT DAWN e8Mgk10938". The town attempts to foil the generals plan by catching some of the messengers and changing their message to "ATTACK AT NOON e8Mgk10938" but it's no use: the receiving general runs the hash function on the message and sees that the ones altered by the town no longer have that special property of all those sevens. Only the true message will hash to the sevens. Note that while it took 12 hours to compute the nonce, it takes a millisecond to confirm that the nonce is correct.

But it doesn't end here. The town is now well aware of the tricks that these generals are using, so they simply purchase a giant supercomputer and when they catch a messenger they now have the computing resources to modify the nonce so that the 7s property is satisfied. Maybe it took the army 12 hours, but they have big computers, they can crack it in 5 minutes. Now the general on the other side is getting conflicting messages that all correctly hash to the sevens. It seems that their plan has been foiled. Or has it...?

IV: THERE IS POWER IN NUMBERS

Let's now say that there is not just two generals and one city, but lots of generals and lots of cities. I made a crude illustration with 3 cities, but keep in mind this idea works best when we have many cities: http://imgur.com/b2CzHN1

The generals all have the same desire, to send soldiers across the valley without fear of their messages being modified. The many cities would like to foil this plan, if they could. So here's Satoshi's idea in a nutshell: the towns all combine their many messages into a single giant message (a "block") which gets but a single nonce at the end of it.

Now the message-block might look like this:

GENERAL G^1 : WE ATTACK AT NOON!  
GENERAL G^2 : WE ATTACK AT DAWN!
GENERAL G^3 : WE ATTACK AT DUSK!
...
GENERAL G^174: WE ATTACK AT MIDNIGHT!
h9Klemoa3DheeMqz9x77ebaomEqz12f3Ba3eO8e

The new policy is that we need 16 sevens instead of only 10, so the hash of that entire message comes out to (say) 777777777777777703182903782123. That's a lot of sevens! (BTW, in Bitcoin the job is to have leading zeros; I picked 7s here instead just for aesthetic reasons. It's all the same concept.)

If the computing time to guess 10 sevens was 12 hours, the computing time for this job would be a million times more, or 1,369 years on a single computer. No single army or town is capable of doing that in any reasonable amount of time. However, all of the generals take the combined message-block and set all of their computers to go on the great nonce hunt. Perhaps there are a thousand armies, and each army has many computers, or at least can rent the service of companies who do have many computers. Their combined efforts may find a working nonce in a reasonable amount of time. And it only takes one of them finds the nonce that satisfies the requirements: once one finds it, they immediately share it with all the others.

From the point of view of any single city, the idea of outcomputing the combined efforts of the armies seems virtually impossible. In 1,369 years they will be long gone. And so they are incapable of modifying the messages between the armies.

You might be thinking: what if all of the cities bought supercomputers and did the same thing the generals did, team-up to find a nonce? Yes, they could do that, at considerable expense. It's not impossible to defeat this scheme, but the generals have made things very hard on attempts of the cities by teaming up.

IV: SUMMARY

Proof-of-work has had a long and speckled history. One might argue it began in the 1960s when universities would try to outdo each other by computing ridiculously difficult things, like gigantic prime numbers or millions of digits of pi. A sort of digital pissing-contest.

BTW, Satoshi's approach is a modification of Adam Black's idea behind Hashcash, the first POW cryptocurrency developed in 1997. But Satoshi's ideas are different enough to warrant giving him credit (blame?) for the notion.

Some practical applications for POW have been suggested, such as a way to discourage spam. In that application, the notion would be that all emails require a special nonce just like above, lest they be rejected. When an innocent email user like myself wants to send an email, I would set my computer to grind away until it finds the right nonce. Perhaps it takes me 60 seconds. No big deal, as this will be done in the background. It just means my email will be delivered a minute slower. But to the spammer who wants to send a million emails, a 60 second delay is unacceptable. This idea never took off, probably because it wasn't a very good one.

Part of the problem with proof-of-work is that by its very nature it requires us to spend a lot of computing power on "busywork". If you are a programmer you live and breathe efficiency. Making a function that takes 9 milliseconds to complete to take only 7 milliseconds is a coup. It's rather against the grain of programmers to design machines that grind away on problems that take 1000 computing years of work for no good reason. On the other hand, every programmer has a part of them who delights in those digital pissing-contests of the 1960s.

Bitcoin now offers us what claims to be the very first real world practical application of Proof-of-Work. Only time will tell how practical this really is.