Crypto of the Week — Bitcoin!
Since this is the first in a series of posts about various cryptocurrencies, there is an obvious coin to start with: Bitcoin. It is the most well-known, founded the ideas from which the other cryptocurrencies have grown, and also has the most value, as measured in “market cap”. Understanding a little bit about how it works and the philosophy behind it will be necessary for having a clear picture of the landscape as we evaluate other coins.
So, what problem is Bitcoin trying to solve, and how does it do it? We’ll see a little bit about *how* in a moment, but the *what* is this: the Bitcoin network, formed by the computers running special software to communicate with each other, provide a decentralized, trustless system of cash. Let’s break each of these down:
1. *decentralized* means that no single actor in the network is necessary for you to use it. For instance, if you bank with MegaBank and their servers have crashed, you will simply be locked out of your money until MegaBank restores service. With Bitcoin, no such issues arise. As long as you have an Internet connection, you can send and receive your tokens.
2. *trustless* means that the system is secure even though you are interacting with computers owned by total strangers. That is, you do not need to “trust” the other participants in the network. For MegaBank, you must trust that they will keep your finances secure, not allow others access to your accounts, and always be able to provide the cash they have stored away for you.
Solving these two problems was the breakthrough that got so many excited about Bitcoin. Finally, we had a good system of rules to allow any number of people to participate in a network not controlled by any central entity, but possessing enough security that even powerful malicious actors could not tamper with it.
What I’d like to do now is take a look at some of the ideas behind how this all works. These are just examples, and some liberty has been taken to simplify things for explanatory purposes. If you want to dive deeper and see more details, the online documentation is very good!
Hashing
The “crypto” in cryptocurrency partially comes from the use of cryptographic functions to “hash” data. Essentially, these “hash functions” can produce seemingly random output from inputs. For instance, given the input “hello there!”, one of these hash functions will output the string
c69509590d81db2f37f9d75480c8efedf79a77933db5a8319e52e13bfd9874a3
You should try out this online hash calculator to get a feel for how it works. Hash functions have a few important properties.
One Way Functions
To be useful for keeping data secure, it must be difficult to figure out what input gave a particular output. For instance, making tiny changes in the input string should completely change the output. Hash functions do this. The input “Hello there!”, for instance, is not very different from “hello there!”, but it spits out
89b8b8e486421463d7e0f5caf60fb9cb35ce169b76e657ab21fc4d1d6b093603
which is nothing like the first output we got above. More importantly, if all you have is the output string, like
eeff0e25ad0fd4f6c81d0972f66dba2b1e6391792560e921ebd0cef6b3adb19c
it must be basically impossible to figure out what the original input is without random guessing. This is the “one-way” property: moving from input to output is not difficult, but figuring out the input that gave a particular output is extremely difficult.
Changes to Data
Another essential property of hash functions is that they can accept input of *any size* and give an output of a *fixed size*. This makes them useful for verifying that large files haven’t changed or combining multiple inputs for a hash. For instance, a site provided a 10GB download file can also provide the proper hash for that file. If anything goes wrong with the download, the hash (which is still just the same size as those above strings!) will be very different than the provided hash. This means that hashes are very useful for *detecting changes to data*. As an example, we can take a simple transaction
Sender: Zach
Recipient: Peyton
Amount: 200
and hash it to get a string like
28db1d01a171fc1f142016cb41d9ea7ca4c2de741fa967f96edb02c684f89619
If anyone tries to change anything about that transaction, the hash will dramatically change, too. But we want more than one transaction for a useful currency system, so the next transaction will include the hash of the previous one
Sender: Zach
Recipient: Ashley
Amount: 400
Previous Hash: 28db1d01a171fc1f142016cb41d9ea7ca4c2de741fa967f96edb02c684f89618
which hashes to
29e7c37b94e4b1de8686784844feaf7c6726e24d5692929e61e5e337b2c717fc
Now if anyone tries to change either transaction, this hash will change. We can keep adding more and more transactions to this chain, with each including the hash of the previous end of the chain. Any changes to any transaction in this chain will, after the hashes are all computed, be detected.
Unfortunately, it’s still fairly easy to “fake” a change in the transaction chain, since computing outputs of hashes from inputs is not hard and a computer can quickly do many of them. What we want is a transaction chain that is difficult to change, which we turn to now.
Hash Puzzles and “Proof of Work”
A key use of hash functions is that they can be used to prove that some amount of computing resources has very likely been used up. To see how, consider this “game”: I will send you a message in a few minutes. You must take that message and find a 10 digit number which, when tacked on at the end of the message, results in a hash that starts with at least one zero. A few minutes pass, and I send you the message “here is the message!”. Then, you start guessing numbers: hashing “here is the message!0000000000” gives
7b491eafbb6da515c8c306d4a11b7a139c5c17939ee0d32533a0e8eed983c21d
No good! How about “here is the message!0000000001”? That gives `
ee1256f38516158de8b9b547ec1d455e458b42ce4cc697243f6e5bff2ed9625a
so also not good! You keep counting up, but nothing works until… “here is the message!0000000034" gives
04f91008d6a5ea94044b89a797c8965901980d43f369091ea2987cc38949285e
which works! You can now let me know that “0000000034” works as the solution to the hash puzzle.
What did that accomplish? Well, because the outputs of these hash functions are so random-looking, I can be fairly confident that you had to make several guesses about what the number was before you landed on an answer. Even if you had some advanced mathematical knowledge or were very clever, it wouldn’t help! You just have to keep guessing. (As far as we know…) I can even make a good guess about how many tries you had to make for this answer: 16, since there are 16 possible characters for the first letter in the output of a hash function. I can also make the puzzle harder by asking you to find a number with more zeros at the front. If I wanted the first five digits in the hash function output to be zero, you’d probably have to make 16⁵ = 1048576 guesses! What’s worse, you can’t “cheat” and figure out answers before hand, since the message that I send you needs to be included as part of the input!
So now we have an idea of what “proof of work” means. If you can solve a hash puzzle, you have probably spend lots of time guessing random numbers to do it. So when you present your solution to the hash puzzle (the numbers you added to the end), I can check the solution and be satisfied you spent lots of time coming up with it.
Reaching Trustless Consensus
Combining proof of work and chains of transaction lets us finally solve a huge problem with a “banking network” with no banks or trusted authorities: how can we trust the other parties to not cheat and alter transactions, spend money twice, or revoke payments? Here is the idea: each participant in the network, referred to as nodes, maintains a list of all transactions. These transactions might look something like the following:
Last Transaction Hash:0ed883e30e18969ddc876385cdf612d0b34731e936b2c4cc28e95f1861f47477
Sender: Zach
Recipient: Ashley
Amount: 150
Nonce: 00000000232
This has the last transaction hash, so that all the transactions form a chain and changes can be spotted using the hashes. But this transaction also has a “nonce”. This is the special number that solves the hash puzzle discussed above. If you take the hash of this transaction, you’ll find
08663ce5600d89f8aa0578e497cdc908ccc8331cb9e0e5875c1151f7c069f4f4
which starts with a zero. In this simple version of a blockchain, a transaction is only accepted if it carries a nonce that, when hashed with the rest of the transaction, has one leading zero.
If Peyton wanted to send me money, he could send out a transaction like this to the network:
Last Transaction Hash:08663ce5600d89f8aa0578e497cdc908ccc8331cb9e0e5875c1151f7c069f4f4
Sender: Peyton
Recipient: Zach
Amount: 60
Nonce: ??????????
In order to officially add this transaction record to the list, the proper nonce would need to be found. The nodes in the network begin racing to try to figure out a solution, and once one is found, they broadcast it to the other nodes in the network. The other nodes verify the nonce solves the hash puzzle and then begin working to add the next transaction to the chain, using the newly added one as the base.
Rewards for Miners
The actual hash puzzle is much, much harder than just finding a nonce with one leading zero. It takes enormous computing power to solve the hash puzzle for Bitcoin, and so how can we give the other nodes incentive to spend so much electricity looking for solutions to hash puzzles? One source of incentives explains exactly how Bitcoin miners are “mining” Bitcoin. The rules of the system are set up so that each newly added piece of data rewards the puzzle solver with freshly created Bitcoin! To make this happen, the miners will add their name to the transaction to receive rewards:
Last Transaction Hash: 02c259cfee2f29a3920440e28c6491a91bc4dba6a81051abf779f2908e92312e
Sender: Zach
Recipient: Ashley
Amount: 100
Reward Recipient: Peyton
Amount: .5
Nonce: 0000000003
The idea is that since Peyton is mining Bitcoin, he has added his own name to the “reward recipient” field and, once this transaction is added to the network’s running list, he’ll get some amount of newly created coin. The other participants accept this, since it’s baked in to the protocol. There is a second way that miners can get rewards. In addition to the free coins from adding the transaction, the sender can add an additional amount to the transaction for the miner to claim as a “tip” for the miners.
Stopping Cheaters
Since solving hash puzzles is so hard, changing the transaction history is hard. To understand why, suppose we have six transactions that I’ll call A,B,C,D,E,F, all in a row. To be valid, each of these transactions needs a solved hash puzzle. Suppose it takes 10 minutes of CPU power to solve a hash puzzle, and so we can safely guess that an hour of CPU time is “locked” into the chain. I was involved in transaction B, and decide I want to cheat, change the transaction history, and try to convince the other nodes in the network of the forgery. I change the transaction B to B’ and try to pass off the history A, B’. Well, the other nodes in the network will clearly reject that, since it has far less CPU time locked in than the other chain they have! It’s clearly not the chain that “the majority” has worked on, and so must be fake.
So I then try to make a longer chain to convince the network of my forgery, spending 40 CPU minutes to build up the chain A, B’, C’, D’, E’, F’. Meanwhile, other people have been adding transactions to the chain. If there are hundreds of other computers all working, during that 40 minutes I was constructing the forged version, dozens of other transactions will have been added to the “real chain”, and so I’ll never catch up! So we’ve arrived at how we determine the “true” transaction history: the longest chain has the most hash puzzles solved, and so required the most amount of computing time to build, and so that chain has a “consensus”.
Conclusion
This was just a tiny introduction to the Bitcoin protocol, but hopefully a few mysteries about how it works are cleared up for some of you! There are some big missing holes that I encourage you to read more about, notably the fact that many, many transactions are linked together and included in the chain at once, and that there must be secure methods of proving that you are who you say you are when you spend coins!
But to briefly summarize, the steps to execute a transaction in this simplified version of Bitcoin go something like this:
1. I decide to send money to Peyton, and I form a transaction and send it off to the Bitcoin network.
2. The miners/nodes in the Bitcoin network add their own names to the transaction to receive rewards and begin searching for the nonce that will make the hash have the correct number of leading zeros.
3. Once one miner finds a solution, it broadcasts that solution to the rest of the network.
4. The other miners accept the solution by adding it to the end of their working chain and using its hash in the next transaction. The longest chain is regarded as the “correct” one, since it provably has the most computing time locked into it, as evidenced by the solved hash puzzles.
