Thursday, November 28, 2013

Bitcoin - layman's explanation

A plain English explanation of the theory behind Bitcon-like virtual currencies. Some oversimplifications have been made in the interest of clarity and brevity. But if you find outright errors or have suggestions for improvements, let me know!

The perfect currency


Imagine a fantasy society. They have the same exchange problem as us — they can’t barter one tenth of a horse for a mug of beer or half a haircut for a loaf of bread. Our society’s ancestors solved this problem by switching to gold and other precious metals — you can divide it into very tiny units, it doesn’t rot and everybody recognizes its value.

But in this fantasy society, they have alchemy — they can create any metal they want (we’ll get there someday too, through matter transmutation). In this place, a grain of gold is no different from a grain of sand. Yes it’s useful, but nobody will accept it as payment because it’s so abundant. It’s just like you won’t accept air as payment even though it’s technically more valuable to human life than food.

So what do they do? They devise a type of magic coin and a magic wallet (later we will replace this magic with technology). This type of coin is impossible to copy or forge perfectly. It’s not even possible to create it at will, because then everyone will do it and it’ll be about as valuable as sand again. So it has to have a limited supply. The magic works by creating these coins periodically. Who gets the newly created coins? Everybody. Since this is not a finders-keepers scenario like in gold mining, it’s only fair. Newly generated coins periodically appear in everyone’s wallets. And these coins can be neatly split into smaller coins so that they can be spent in any fraction you want.

Now a human being can’t tell whether one of these coins is the real thing or not by just looking at it. The wallet does it for you. If you receive a fake coin from someone and try to put it in your wallet, your wallet will spit it out immediately. Doesn’t that solve this society’s currency problems? Let’s see:


  1. Limited supply.
  2. Can be split neatly into small units.
  3. Impossible to perfectly forge; forgeries are instantly detectable.
  4. No central party mints the coins or has control of them. So no corruption.

A somewhat less than perfect currency


Unfortunately, magic doesn’t exist. So let’s dial back the magic a bit. Instead of magic coins and magic wallets, everyone gets an account book, or a ledger. Instead of physical coins periodically appearing in a wallet, you periodically receive a unique ‘coin number’ in the mail, from a central exchange/mint, which we will talk about soon. It basically says, “you’re now the owner of a new coin identified by #555″ (that’s just an example). Nobody else get’s that exact number again. It’s just like the serial number on a banknote (or a bill, if you’re American). You write this number down in your ledger. When you spend your coins, you strike it off your ledger. When you receive coins, whether from the mint or as payment from someone else, you add that to your ledger. So you always know your current balance.

Now there’s no physical coin. But each coin has a uniquely identifiable number, kind of like the serial number on a banknote. If you want to buy a beer, you go to the bartender and say “I’m giving you #555-1/10, give me a beer” (let’s say that identifies one tenth of the coin #555). If he accepts, you’re supposed to strike one tenth of coin #555 off your ledger and the bartender is supposed to add #555-1/10 to the bar’s ledger.

But is the bartender going to accept your word? You could of course show him the entry in your ledger as proof, but then what if you forged the ledger? Not only could you spend coin #555 ten times over in bars all over town, you could even claim to have coin #556. How will anyone know who has which coin?

The problem of the central mint


So the personal ledger or account book is not enough. We need a central ledger. So when you want to buy that beer, the bartender calls the central exchange and says “I’m getting #555-1/10 from Mr. Smith”. Someone at the exchange checks the central ledger and verifies that you, Mr. Smith does indeed own at least 1/10th of #555. But they also need to check that the bartender is not cheating. So either you too have to call the exchange and say “I’m giving #555-1/10 to Joe’s Bar,” or the exchange has to call you and ask “Mr. Smith, Joe’s Bar is claiming #555-1/10 from you. Is that legitimate?”. If both sides say yes, the transaction takes place without possibility of fraud. It’s a bit like credit card transactions, right?

Except we’re making some assumptions. We’re assuming that people won’t get fed up of continuously having to call the exchange every time they pay for something. We’re assuming that the exchange is completely honest. That second assumption is very wrong. Even though an economist may have calculated that the exchange (or the “mint”) should mail out no more than coin #1000 this year, the employees of the exchange decide to “mint” a few hundred extra coins and split it amongst themselves. Suddenly, they’ve got money for nothing. No amount of oversight is going to stop this. The power to make money out of thin air is so tempting that even the bosses and the bosses’ bosses will eventually succumb. In fact, this is kind of what’s happening in the world today with paper money. The result is inflation — the money honest people hold in their hand is worth less and less because someone’s pumping out more money. The more abundant it is, the less people are willing to accept it as a payment and therefore the more of it you will have to offer. In other words, prices rise. What you lose in value is what the “mint” spends without actually having to work for it. But that’s another story. Some of you may not even agree with my interpretation of it. So let’s forget it.

A global ledger


So how do we keep the central exchange honest? We don’t. We get rid of it. We don’t trust any single person to hold that central ledger, which is the account book that lists every single coin number or partial coin number against someone’s name and is updated with every transaction. We give it to everybody. Instead of a list of just your coins, now your personal ledger contains a list of all coins ever, with names of owners. Now when you go to the bartender, he doesn’t have to trust you or even a central exchange, he can look up the last owner of #555-1/10 from his own ledger. So you strike it off your ledger and the bartender adds it to his own. You enjoy your beer.

Now we have two problems. Were both of you honest in your book updates? And how is everyone else going to know about this transaction? If it’s just a few people in a room, it’s easy. You just stand up and announce “#555-1/10 from Mr. Smith to Joe” and everyone will update their books. Since everyone knows the total number of coins in existence, it’ll be a trivial matter to add up the accounts and check if you and Joe are both telling the truth. There’s no chance of fraud. The moment you try to spend a coin you don’t have, the books will not balance and everyone will scream fraud. That solves the problem of the corrupt central exchange, right?

Wrong. We only solved one problem (double spending), ignored another (who mints the coin numbers now?) and introduced a new problem (the whole world now knows your private financial details).

Making numbers scarce


Let’s take the minting problem. We have to make sure these ‘coins’ have a limited supply. But if there is no central exchange controlling the issuing of these numbers, we have a problem. Anyone can write up a new number. And numbers are infinite. We need that magic back. Even though we don’t have magic, we have something close: mathematics.

The math problem 3 x 2 = 6 is no more easier or difficult than it’s reverse, which for the sake of this discussion, we will consider to be 6 / 2 = 3. Unless of course you’re bad at division, but that’s a different story. Most math calculations take a similar amount of effort whether you do it one way or the other. Most but not all. There’s a certain type that’s very easy to do in the forward direction, but extremely time consuming to reverse. Here’s an oversimplified analogy (remember, an analogy, not an example):

Suppose I ask you for a name of a fruit and an animal and then add up the letters to get a number (assume A = 1, B = 2,… Z = 26). If I wanted you to do this for “banana monkey”, you’ll be able to do it easily (2 + 1 + 14 + 1… and so on). There’s nothing hit or miss about it. You could even set up a simple spreadsheet (for example, on Microsoft Excel) to give you the answer instantly. But if I ask you to find a fruit and an animal such that the sum of their letters is exactly 100, it’s a different story right? There’s no straightforward calculation. You’re going to have to just keep trying until you get an answer that fits.

In mathematics too, such problems exist. But they’re much, much harder to reverse than this word problem. At least with the word problem, you can do some guesswork — you’d know that “apple ant” will give you a small number while “pomegranate hippopotamus” is likely to give you a large number. But some math problems will give you absolutely no hint as to how wildly the answer will change even if you change a single digit in the inputs. If you want to learn more, search the Internet for “hash functions” and find a simple enough article to read.

So why are these important? If you decree that coin numbers must be answers to such a math problem, you can basically limit the money supply. And since mathematics is utterly precise, there’s no risk of unexpected oversupplies (consider what would happen to the world’s gold market if you suddenly discover a ten thousand tonne block of gold under your back yard). Not only that, after it’s done the first time, it’s extremely easy to verify. For example, if someone sweats it out and find a fruit and an animal for that last problem, it’s trivially easy for everyone else to check whether his answer is correct or not.

So we set the rules such that anyone who can calculate a new coin number gets to keep it. It’s kind of like prospecting and mining gold. You find it, you keep it. Of course, now pen and paper won’t be enough. The calculations are tough. Fortunately we have computers. We also have the Internet. So the problem of broadcasting transactions to a large number of people gets solved too. Now we have a limited supply of coin numbers that everyone can verify as authentic, and a global ledger that prevents people from spending money they don’t own.

Creeps and spooks


Now we’ve nailed it, right? Not quite. We just solved fraud and oversupply. But what about privacy? That’s easy. Why does your ledger have to carry your name at all? It can just be a number. And you can have as many ledgers as you like. It’s just like you opening many bank accounts. It’s fine as long as the money doesn’t get copied. Want to get paid a salary? You just tell your company accountant “Here’s my coin account number. Send my salary here”. Is he going to object? No. It’s your money, so it’s your choice where you send it. But of course, he’ll need to check your company ID to make sure you’re you.

But wait, you say. Now the company knows that you’re the owner of that account. If your boss is a creep, he could study the global ledger and track the coin he paid you all the way to a seedy bar in a disreputable part of town. And you don’t want that. What can you do?

Just create any number of new accounts and split up the money among them. Spend using those. Now your creepy boss doesn’t know whether those new accounts belong to your or to someone else you made a payment to. He can suspect, but he’ll never know for sure. If you’re really paranoid, you can even exchange your coins with friends. Your boss will be very surprised when your coin is used to buy diapers in London when he knows for a fact you live in Los Angeles and have no children. With billions of people using these coins dozens of times a day, at some point the creeps and spooks are going to have to give up. They can always suspect, but they won’t be able to prove anything.

Okay, now we’ve got it, right? This new virtual currency is perfectly divisible, cannot be counterfeited without everybody crying foul, cannot be created on a whim so as to cause oversupply and cannot be reliably tracked to a person.

Are you the real McCoy?


Still no. When we went from announcing transactions to a roomful of people to using the Internet to broadcast them, we introduced a new problem: authentication. In the room, people will identify you by your face. But on the Internet, you’re just an account number. When you (or anyone else) in the coin network receives a broadcast saying “#555-1/10 from account X to account Y”, how do you know that it’s an authentic broadcast from the owner of account X? Note that Y doesn’t need to prove himself — you don’t need to prove anything to receive money if someone is willing to just hand it to you.

Are we going to have to reveal people’s identities again?

Invisible keys


More math to the rescue. In our {fruit + animal = 100} problem, whoever announces a solution for the first time can claim ‘proof-of-work’, i.e. “this is a one-time solution, I’m the first guy to announce it and therefore I solved it”. Too bad if you solved it and kept quiet though. That’s your fault.

Now there’s another class of math problem, which are (just like “hashes”) easy to do in one direction, but so difficult to do in reverse that it is basically considered impossible. As you know, prime numbers can only be divided by itself and 1. For example, 29 cannot be divided by any other number without a remainder. The same is true of 41. Now if someone asked you to do {29 x 41}, that’d be fairly easy, even without a calculator: 1189. But if someone asked you to do the reverse, in other words, find the factors of 1189 (the answers being 29 and 41), you can’t readily calculate the answer. Just like with the {fruit + animal = 100} problem, you’ll need to keep trying different numbers until you stumble upon an answer. You might think that’s not much harder than the {fruit + animal = 100} problem. Ah, but what if your two prime numbers are twenty five digits each? Or even fifty digits?

So why is this math problem important? Because just as we used the previous type of problem as “proof of work”, we can use this type of problem for “proof of possession”. They can act as keys to mathematical locks. Now I’m about to heavily oversimplify (and possibly misrepresent) the math behind a very important security feature on the Internet called digital signatures. If you want to know how it actually works, you might need to read a few math-heavy articles. And even I haven’t read those. So here goes.

In the real world, you prove your identity by doing something that only you can do. In most cases, this involves placing your signature on a piece of paper, entering the combination into a safe or inserting your key into a lock. Of course neither method is perfect. A good forger can forge your signature. If someone watches you open the safe, they may see your combination. Someone can duplicate your key. On the Internet, the duplication problem is much, much worse — you can copy anything perfectly because it’s all ones and zeroes (which is why record companies still have such a tough time keeping people from pirating music). So the moment you use a secret number to prove your identity, it becomes useless because now everyone knows it and can easily reproduce it.

Digital signatures


What you really need is something a bit like magic: you need to be able to prove you know a number without actually revealing that number. Once again, mathematics to the rescue. It turns out that the prime number problem we spoke of before can be used for just this sort of thing. Think of the two prime numbers (in the last example, 29 and 41, whose product is 1189) as two pieces of a puzzle. Let’s say our bartender’s account’s secret number is 29 (not the publicly known number, but a different number). Before you tell him your coin number, you want proof that the account number he tells you is actually the account for Joe’s Bar. But you can’t ask for the number (29) because it’s a secret. What if you challenge him by saying “What is the other factor of 1189?” (the answer being 41)? Of course, he can immediately get it by dividing 1189 by his half of the puzzle, i.e. 1189/29 = 41. Neither he nor you uttered the number 29 but he proved that he knew it. But that’s really stupid isn’t it? The moment he blurts out “41″, you too can immediately divide 1189 by 41 and figure out his secret number. That’s not much of a secret. Thankfully, we never have to directly exchange these prime numbers. Many years ago, three very talented men whose last names begin with the letters R, S, and A figured out a way to dress these prime numbers in a sort of mathematical dressing. They ended up with two numbers (or strings) — let’s call them keys. Anyone can generate a pair of these for himself using a pair of huge prime numbers. Let’s say you do this. We will call one your secret signing key and the other your signature verification key.

Let’s say you want to send an email to someone with a ‘digital signature’. You run the text of your email and your secret key through a special mathematical function and out you get a scrambled version of your email. You send this to your recipient.

But how does your recipient verify your signature? They don’t have your signing key, and they shouldn’t. What they do have is the other half of the key pair — the signature verification key. While this too is unique to you, it is not private at all. You can email it, publish it all over the Internet or shout it from a rooftop without any fear. Because the only thing it can be used for is to verify a digital signature of yours. So all your friends will have your verification key. When they feed your scrambled email along with your verification key into another mathematical function, your email comes out. You never had to reveal your secret signature key but still you proved that you have it with you by creating a scrambled message that could only be unscrambled with the key’s counterpart.

So now you know how we’re going to solve the identity problem on the Internet. Every account will have two numbers — the secret number and the public number. Everyone knows the public numbers and the global ledger contains these numbers too. You keep your secret number very, very safe. Because if you lose it, you have no way of ever spending your coins again. Because you can’t prove who you are. Worse yet, if someone else gets a hold of your secret key, he can spend your money.

When you announce a new transaction, you ‘digitally sign’ the transaction message with your secret key. The message gets published all over the Internet. Everyone in the coin network takes the message, sees the the public account number (which is the same as the signature verification key for that account) and uses it to unscramble it. If the unscrambling is successful, the transaction was announced by the rightful owner of the account. Sounds complicated, right? Sorry, but that’s about as simple as it’s going to get.

Voila! Voila?


Finally, it looks like we’ve sorted out all the theoretical problems!

Now we have a few practical problems. First, that global ledger is going to grow huge. Second, what happens if you drop off the Internet for a few hours and come back? Of course, this coin network can be designed so that your “wallet program” can ask anybody and everybody on the network to supply you with the missing transactions in order to catch up. This should take minutes, if not seconds. But what if a fraudster waits for a latecomer just like you and pays you with a coin that belongs to someone else? It’s in the global ledger, but your copy is not yet up to date. If he times it right, by the time your ledger gets updated, you may have already handed over your goods to the fraudster. And the ledger now tells you that the coin belongs to someone else.

Let bygones be bygones


Let’s take the first problem — the problem of the huge ledger. Do you really need all the transactions from the beginning of time? If it’s a paper ledger book, you would probably finalize it annually and publish an official copy. All the balances at the end of December 31st will be brought forward to the new year’s book. The old books will stored in archives, only to be pulled out if the need arises.

But who’s going to do that? Remember, there’s no central exchange or mint or authority of any sort. So the solution is to get everybody to do it. But will everybody bind the transactions the same way? Maybe one year there are so many transactions that you have to split the book. Some people will split it down the middle, some will put the extra transactions in a smaller, appendix-style book. And what if people can’t agree on the size of the book — yearly, monthly, weekly or even daily? Or perhaps the number of transactions? There will not be one global archive and therefore no single globally agreed upon point after which you carry forward the balances. So how do you solve that? Remember the difficult-to-reverse math problem we used to generate coin numbers? The one that makes sure that the coin number supply is not infinite? We can pair the transaction-grouping problem with that problem. Consider this:

Instead of going by periodic ‘books’, we define a ‘page’ of arbitrary size — anyone can choose how many transactions go into it (it’s on a computer, so the size of a ‘page’ doesn’t matter). Now you can’t just chunk transactions into a page. You have to create the page and then run one of those “hash functions” on it to generate a number. That number has to meet a certain criteria (remember fruit + animal = 100? kind of like that). Say the last four digits of the number has to come out zero. Since this is not a reversible calculation, you (or rather your wallet program) keeps trying various combinations of transactions until the hash for that transaction group meets the criteria. This involves a lot of computing power and therefore takes a lot of time. When you solve the problem, not only do you get the next page in the global ledger, the rules say you also get to use that number as the next new coin number (it’s not quite like that, but let’s not go into that right now). Now not only do you announce the transaction of you minting (or “mining”) a new coin, you also announce that you have a new page for the global ledger. Since we have made the process of creating a ledger page mathematically difficult, now there are hardly any contending or alternative page versions. Whoever calculates a page first gets it inserted into the global ledger (of course, remember that everyone can quickly verify that it’s correct, because everyone has everyone else’s transactions). You can even think of the new coin as a reward for the service of calculating a new ledger page.

So now everyone agrees on each new page of the ledger. The further in the past a page is, the surer you can be that the transactions on it are authentic. There’s way you can use a hash function to mathematically link pages into a chain so that you can’t change even a single figure on a page without breaking the entire chain. But I’m going to skip that part of the story.

So after a while you can sort of start forgetting about really, really old pages. But remember, you need to know the current balance for every account. Your wallet program may not need to know all of it personally, but most of the coin network should (so that wallets that are behind the times can catch up).

Marking time


Now the huge ledger problem is kind of solved. But what about the fraudster who tries to buy something from you using someone else’s coin while your wallet is still catching up after a long hiatus from the Internet? The obvious answer: wait for your wallet to catch up before you consider a payment from someone as final. Even if you were never disconnected from the Internet, still wait a while. The fraudster may be trying to pay using the same coin on opposite sides of the world. It may take a while for whole network to catch up. With the kind of Internet that we have today, this period would probably be in the order of minutes.

So do we have everything in order? Let’s see:

  1. A ‘coin’ is a mathematical thing — each represented by a unique coin number (or a string) so you can send it over a data network (like the Internet).
  2. Its supply is mathematically limited by the difficulty in computing valid coin numbers.
  3. We did away with both individual fraudsters and corrupt central exchanges in one swell swoop by introducing an open, global ledger that anyone can verify.
  4. We made the transactions anonymous by giving anybody the ability to open a coin account (it’s just a number).
  5. We made sure the transaction announcements were from the real coin owners by making them sign their announcements with their digital signature.
  6. We solved the problem of the huge ledger by chunking transactions into pages and letting old pages be forgotten.
  7. We solved the problem of who creates these pages by making it part of the math problem that gives you new coin numbers.
  8. And of course, we want you to wait until the latest transactions come to your copy of the global ledger before considering any coins you received final.

Sort of. There are other matters like the order in which transactions are actually announced versus the order in which they arrive at your computer (since the Internet is a distributed network). I’m going to sort of gloss over that and a few other things. So that’s it.

What I just described isn’t exactly Bitcoin, but the theory is the same. If you understand the logic, you should be able to understand (or misunderstand) Bitcoin about as much as I have. The real thing only differs in specifics.

Now to look at a few other questions.

Let there be fiat


How can something generated in a computer have any value? Let me ask you a question back. What makes a grain of rice different from a grain of sand? What gives the first thing value while the second thing is almost worthless (unless you’re in construction). Is it the fact that you can eat rice? Then what about breathable air? That’s a lot more valuable than rice but we seem to care even less about it than we do about sand. That’s because it’s not scarce. So something has to have both utility and scarcity for it to be considered valuable. A uniquely shaped dog turd you see on the way home may be scarce, but that doesn’t make it valuable on its own (I know, that’s a terrible example).

So what makes Bitcoin valuable? In addition to having mathematically-enforced scarcity, it does in fact have what an economist would call an intrinsic value. It has properties that make it a much better medium of value exchange than anything we have. That’s it’s utility. If you’re still not convinced, consider what all modern paper money is: it’s just ink on paper. It has value because the government says it has value. Or as an economist would tell you, it’s currency by fiat. They used to be backed by gold, but not any more. Many people (at times myself included) dream of returning to the good old days of gold backed currencies where modern inflation rates would be unthinkable. But something like Bitcoin could potentially be even better than gold. Who knows? Even experts have trouble predicting this one. And I’m certainly no expert.

It’s only words


Bitcoin has a lot of people befuddled. Until a few days ago I used to be one of those people. After a while I finally figured out the source of my confusion: mixing the theory with technology. So I did for myself what I always do when I have to explain a complicated technology to someone who doesn’t understand technology: I explain the pen-and-paper version. And yes, almost every technology has a pen & paper (and pigeon, where necessary) version. The above article is basically how I explained Bitcoin to myself after studying the subject at only medium depth.

You might have noticed that I did not use the standard Bitcoin terms. That’s because they have technological origins. Instead of addresses, public keys, private keys, block chains etc., I said ledgers, signing keys, verifying keys, pages etc. It may not be entirely accurate, but at least in my case, it certainly helped.

Edit: Try Bitcoin is a hands on demo of sorts.

No comments: