The Nakamoto Legacy, Part One

In 1936, a promising young Cambridge Mathematician, Alan Mathison Turing, published a peculiar paper with a misleadingly dry title.  On Computable Numbers, with an Application to the Entscheidungsproblem was an important piece of work in the world of formal mathematical logic, a world blown apart 5 years earlier by Kurt Gödel’s On Formally Undecidable Propositions, itself published just a few years after Alfred North Whitehead and Bertrand Russell thought they had settled matters once and for all in their three volume opus, Principia Mathematica.  Heady times.

What was peculiar about Turing’s paper (at least from my personal and deeply inadequate perspective) was the idiosyncratic approach he took to a problem in the purest of mathematics.  Gödel’s work may have been bordering on the unapproachable, but at least it looked like mathematics, in the abstraction of its formulation.  Alonzo Church’s attack on the same problem, around the same time as Turing’s, used a computational methodology based around his ‘lambda calculus’, which again looked the part.  (And which in due course gave birth to LISP – easily the most satisfyingly elegant programming language to emerge in the second  half of the 20th Century.  Again, from a personal, but this time less inadequate, perspective.)

But Turing attacked the problem by coming up with a weird kind of theoretical technology, an abstract machine.  It wasn’t altogether an original idea.  Leibniz had imagined such an ‘engine of logic’ as early as the 17th Century, and of course Babbage and Lovelace had moved the technology on impressively during the 19th, but Turing used the idea as a lever to solve a fundamental problem of abstract mathematics.  And, to me, that just seemed odd.

And what ultimately was perhaps more odd was that a theoretical technology, designed to attack a fundamental mathematical problem of interest to virtually no-one, in short order spawned a real world technology that was to change the course of the second world war, and that ultimately reshaped the human world completely.

In 2008, another technical paper quietly appeared featuring a theoretical technology which explicitly solved a specific problem, the ‘double payment problem’, while implicitly solving a number of others.  Again it proposed an elegant, probably genius solution.  And again it spawned a real world technology which was to make a big splash, even if (at the time of writing this article) it’s impact was very mixed and it’s long term future was far from certain.

But the 2008 paper was different in three ways.  Firstly, the real world application was clearly already foreseen, and implicit in the title.  Secondly, the ostensible author of the paper, Satoshi Nakamoto, didn’t actually exist and (again, at the time of writing) has still not been definitively identified.  And thirdly, the real world application somewhat overshadowed something else – the theoretical technology which underpinned it.  We’ll be coming back to this.  

The paper was entitled Bitcoin: a Peer-to-Peer Electronic Cash System.  And although the technology that it describes is unlikely to have anything like the general impact that digital computing has had, it may yet cause major disruptions well beyond its putative scope.  This article takes a stab at explaining the technology.  The faint-hearted might want to jump to Part Two, where we extrapolate some of the possible (originally) unforeseen consequences.

 

The Role of the Byzantine Generals

The origins of Bitcoin lie with an even more obscure paper published in 1982 in ACM Transactions on Programming Languages and Systems, written by Leslie Lamport, Robert Shostak and byzantine-13th-centuryMarshall Pease, and (interestingly, I think)  part sponsored by NASA and the US Ballistic Missile Defence Systems Command.  It was called The Byzantine Generals Problem.  

Imagine a bunch of Byzantine generals camped with their troops around an enemy city.  They communicate by messenger, and have to agree a consensus plan of battle.  The catch is that one or more of the generals may be a traitor.  The problem is to figure out a method that allows the loyal generals to come correctly to an agreement.

It turns out that it is only possible to do this (at least with oral messages) if at least two-thirds of the generals are loyal.  The proof is far from straightforward, and on the way takes in Lieutenants and Albanians, so we’ll give that a miss.

Er, so what?

The Byzantine Generals were actually a kind of mathematical allegory for computer components.  The authors were addressing the issue of a failed component simply sending incorrect information to other parts of the system, and their solution became known as ‘Byzantine Fault Tolerance’.

Fast forward 26 years, and by now the subject matter isn’t components so much as individual computers in a network, the internet, and the problem isn’t faulty equipment, it’s active subversion by hackers and their ilk.  Arguably a closer allegory of the original problem in fact.

 

Virtual Coins and the Double Payment Problem

Let’s suppose someone sends you a virtual coin, a bitcoin.  What is it?  What have they actually sent you?

They’ve sent you information.  In this case, that information comprises a ‘hash’ of the last transaction (which was their own incarnation of the coin) and your ‘public key’, signed digitally (i.e. encoded) using their own ‘private key’.  A hash, in this context, is a kind of encoding system which takes input data and turns it into a number with a fixed length.  Changing the input data even slightly will change the hash.

When you receive the ‘coin’ you can use the sender’s public key to verify it.  What you can’t do, though, is prove whether or not the sender has already spent the coin somewhere else: hence, the double payment problem.  Back in the Olden Days you’d have to solve this via a Trusted Third Party (probably a bank), who’d decide which transactions were valid and which ones weren’t.  

The question then arises as to whether a solution can be found that doesn’t need such a central authority.  Because, hey, it’s 2008, and banks, well, come on man…

 

Enter the Blockchain

The solution proposed by Satoshi Nakamoto, whoever (or whatever)  that is, was a very clever piece of virtual technology dubbed the ‘blockchain’.  

The basic idea is that when someone sends you a coin, they send everyone else the same transaction – they broadcast it to everyone in the network.  In order for that transaction to be valid, it then has to find its way into the blockchain.

A number of nodes in this network have copies of the blockchain and beaver away updating it.  They gather together recently broadcast transactions into a single block, along with two other things: the hash of the previous block, and a useless number called a ‘nonce’.  No, really.  

They then throw raw computing power at creating a hash with a particular number of leading zeroes.  This is really hard, because the hash number is very long (so there are gazillions of possible outcomes), and it turns out that the difficulty goes up exponentially depending on how many zeroes are required.  Calculate the hash, check the number of leading zeroes and if you don’t get a match, increment the nonce and do it again.  If you do get a match, you add this new block to the chain, the hash of which will be included in the next block.  This process is called ‘proof of work’, and it usually takes about ten minutes.  The guys who do it are dubbed ‘miners’, and are rewarded with new bitcoins and/or transaction fees (the first transaction in the new block is a new coin owned by the creator of that block).  If the proof of work gets too easy (as measure by the number of valid new blocks per hour being generated), the number of leading zeroes is increased to make it hard again.

This means of course that it’s possible in principle to have different versions of the block chain kicking about at the same time, not least if some rogue broadcasts two different transactions with the same coin.  No matter: the rule is that the longest chain is always the right one.  Nodes working on another chain will drop it once a longer one is received, and switch to working on the longer one.  The consensus blockchain is therefore the definitive ledger of bitcoin transactions, and replaces the trusted third party.  

If you’re a treacherous byzantine general in this network, you’ve got your work cut out.  In order to commit a fraud you have to rewrite history, as recorded by the blockchain ledger.  But any change you make to an earlier block will change the way that it is hashed in subsequent blocks.  So you’d have to redo all that proof of work.  Unless you dominate the computing power of the network, this is effectively impossible.  You’d be better off becoming an honest miner and making money that way.

There’s a bit more to it than this, but it’s already migraine-inducing stuff, so let’s move on.

 

The Trouble with Bitcoin

The technology behind bitcoin is, without a doubt, very clever indeed.  The economics on the other hand is another matter.  With no central bank to regulate the supply of money in the system, bitcoin is subject to wild gyrations in conversion rate to other currencies.  It has an underlying deflationary mechanism (remember those miners and their new bitcoins), which will cease when the number of coins becomes fixed at a limit of 21 million, at which point if demand is rising, inflation will rule the day.  Whether it (or another bitcoin variant) is ever likely to become a mainstream success I have no idea, but it’s not a no-brainer that it will.

But that doesn’t matter, because what’s interesting is not bitcoin.  What’s interesting is the blockchain.  And that’s what Part Two is about.

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

3 thoughts on “The Nakamoto Legacy, Part One”