Spotlight on: The Byzantine Schoolchildren's problem

Monday 23 May 2016

It’s well known that bitcoin solves the Byzantine Generals Problem, but what does this actually mean?

It’s easy to duplicate digital information, which is why online money has previously needed a central authority to police it - a gatekeeper to guard the database of accounts and stop users copying and submitting transactions twice. In distributed systems theory this is known as the Byzantine Generals Problem, but we’ll use a slightly different analogy to explain it - and how bitcoin addresses the issue.

Byzantine schoolchildren

A classroom of schoolchildren would like to attack their teacher with ink-soaked indiarubber. They recognise the importance of all attacking at once; there is safety in numbers and if they do not synchronise their attack, the one to flick their rubber first will otherwise be harshly punished.

Schoolmaster

Double spend and it's six of the best for you

One child decides to organise the attack by passing a note around the classroom. The attack is to proceed at 4pm sharp by the classroom clock. However, he runs into a problem.

Scattered through the classroom there may be a handful of teacher’s pets. These snivelling to-rags might change the time on the note, thwarting the attack by causing a small number of children to attack alone and receiving their due punishment. How to ensure that everyone attacks at once?

Proof of work

The solution the instigator hits upon is to force each child in the room to include a 'proof of work' before they pass the note on, as well as ensuring that all previous notes have been included in a ‘chain’ of messages. So, child 1 passes the note to child 2. Before passing it on, child 2 must copy the note from child 1, and include a translation of one page of Vergil’s Aeneid from Latin, which coincidentally takes around 10 minutes. Child 3 must copy the previous messages, before including his own 10-minute proof-of-work and passing it on to child 4.

What happens when the message reaches a teacher’s pet? The vile toad has a choice to make. They can either change all the previous messages and provide new translations of Vergil for each one, plus submit their own altered message and proof-of-work, before passing the message on; or they can go with the herd in the knowledge that they realistically cannot complete several blocks of work plus their own in the allotted ten minutes. The system fosters an ‘If you can’t beat ‘em, join ‘em’ approach.

And this is like bitcoin because...?

Substitute ‘translate page of Vergil’s Aeneid’ for ‘find a hash that meets the current Difficulty criteria’, ‘child’ for ‘node’, and ‘attack’ for ‘transaction’ and you get most of the way there. Basically, the idea is to ensure that no computer can reasonably claim a transaction is valid when it’s not. You do that by building consensus - making it very difficult and/or time-consuming to fake a transaction record. If a node takes too long to pass on a transaction, you can assume they’re up to something dishonest. The proof of work in bitcoin’s case is hard to carry out, but very easy to check.

Other protocols use different approaches - most commonly proof-of-stake - but proof-of-work was the original solution to the Byzantine Generals Problem.


comments powered by Disqus