How Bitcoin Works
Blockchain Beyond Bitcoin | Lecture 3
Recap
Welcome! If you’re a returning reader, thank you for keeping up with our series, Blockchain Beyond Bitcoin! If you are a new reader, we’d like to provide you with a TL;DR from the previous lecture. In Digital Currencies & Networks, we began with a history of “currency”.
Before currency, our economies relied on simple trade. Initially as barter, this primitive exchange was limited by time spent and trust necessary in negotiations. We quickly transitioned to commodity money (objects with intrinsic value due to rarity), introducing an efficient standard measure of value. Concerns surrounding the portability and durability of commodities led to the introduction of representative money exchangeable for a fixed amount of commodity. These underlying physical assets, however, were limited by physical protection and perceived legitimacy. Using law, governments instituted fiat money valuable because of induced economic conditions in place of backing physical assets. Due to inefficient monetary policy in countries like Venezuela and Zimbabwe, failure to properly regulate inflation and debt can affect quality of life and purchasing power. Early attempts at digital currencies such as DigiCash and E-Gold worked to solve this institutional problem but were too closely tied to their founders and vulnerable to government prosecution.
Lastly, we discussed the behaviors of internet-enabled networks. To understand how software companies (including Apple, Google, and Microsoft) have become the world’s largest and most profitable businesses using networks, we need two important mental models: network effects and critical mass. Network effects describe how value within a network increases proportionally with the number of users. Critical mass describes the number of users required for a network to establish competitive advantage which makes alternatives obsolete. When a private company achieves network effects and critical mass, we observe the extraction imperative: companies with fiduciary responsibilities to shareholders need to extract rent from users.
Before we dive into the details of how Bitcoin works, we offer a timeline of some historical inflection points showing network growth and currency adoption.
History of Bitcoin
On August 18th, 2008, the domain name bitcoin.org was registered on DNS. On October 31st, 2008 a link to a paper authored with the pseudonym Satoshi Nakamoto titled Bitcoin: A Peer-to-Peer Electronic Cash System was posted to a small mailing list with members from the cryptography community. The paper detailed the use of a peer-to-peer network to generate what was described as “a system for electronic transactions without relying on trust.” To this day, no one knows for sure the true identity of Satoshi Nakamoto. On January 3rd, 2009, Satoshi “mined the genesis block” of bitcoin, introducing the first 50 bitcoins to the world. Embedded in this block was the text “The Times 03/Jan/2009 Chancellor on brink of second bailout for banks.” This note serves as both a permanent timestamp and commentary on the instability caused by contemporary fractional-reserve banking.
A small community of bitcoiners from the mailing list shared in the spirit of an open source software project, and began to bootstrap. Gavin Andresen, a coder in New England, bought 10,000 bitcoins for $50 and created a site called the Bitcoin Faucet where he gave them away for free. Laszlo Hanyecz, a Florida programmer, conducted what bitcoiners think of as the first real-world bitcoin transaction, paying 10,000 bitcoins to get two pizzas delivered from Papa John’s. A farmer in Massachusetts named David Forster began accepting bitcoins as payment for homemade alpaca socks.
After “mining” 1 million bitcoin, Satoshi disappeared and handed over project control to Gavin Andresen. In June 2011, WikiLeaks and other organizations began to accept bitcoins for donations. In December of 2017, during the the strongest bull market cryptocurrencies have seen, Coinbase announced they were signing up over 125,000 new users every day.
Over a 10 year span, Bitcoin became one of the most powerful technological innovations of our time. As such, it is important that we understand how such a system can function. This leads us to ask…
Ledgers
Traditionally, a ledger is an accounting tool used to keep track of a history of transactions between several accounts, including debits and credits. In practice, within the context of a group of friends exchanging money frequently, it can be inconvenient to exchange cash for every transaction. This group might want to maintain a public ledger to keep track of transactions that will make physically at a later date. This ledger could be hosted on a website where all of the community members have write access. At the end of the month, for instance, the community settles— if you spent more than you received, you contribute to the pot and vice versa if you received more than you spent. Any community members can then add transactions to this public ledger.
If anyone can write transactions to the ledger, though, how do we trust that all of the transactions are what the sender meant for them to be? In the traditional banking system, this comes from a signature on a check or a pin number used to verify withdrawals. With digital money, we need something more secure.
Digital Signatures
The members of a public ledger community should be able to prove that certain transactions have been seen and approved by them. This comes with the caveat that no one else should be able to forge this proof, which handwritten signatures are vulnerable to. At a glance, it might seem like a digital signature is impossible because you can always duplicate the memory where the signature is stored to “forge” it. This is where some clever cryptography comes in.
All members of the community generate something called a public/private key pair. Each key is a string of bits, where the public key serves as a unique identifier and the private key is a secret you want to keep to yourself.
Whereas a handwritten signature looks the same everywhere, a digital signature is much stronger; it changes for every signed message. Producing a digital signature involves a special function that takes as input the message and the signer’s private key.
This system ensures that only the holder of the secret private key can produce the digital signature. The signature depends on the message, so no one can copy it and forge on other fraudulent messages. But how do we verify the validity of this signature?
We have a special function for verification, which takes as input the message, the signature, and the signer’s public key. This function outputs true or false dependent on if it was produced by the corresponding private key.
This function is designed to prevent finding a valid signature without the requisite private key. With a 256-bit signature length, there are 2²⁵⁶ possible signatures, which gives us extreme statistical confidence that only private key holders can produce valid signatures. Irrespective of digital signatures attached to transactions on the ledger, the same ledger entry can be copied and rewritten because the combination remains valid.
To prevent this form of double spending, each ledger entry needs a unique identifier, called a nonce, such that every transaction requires a new signature.
Protocol
Even with digital signatures, a public ledger like this relies on an honor system of sorts: users have to trust that everyone will settle up at the end of the month. What if they don’t pay up? The only reason to settle with real money is if some of the ledger community members are in debt. If we can systematically prevent debt, we never need to settle. Under this operating assumption, we can give every user a balance up front, and introduce another rule for transactions: transactions where someone spends more than they already have on the ledger are invalid. If the net sum of transactions dips below 0 for a ledger community member, all transactions since this crossover are considered invalid. As a result, verifying a transaction requires knowing the full history up until that point. This constraint removes the connection between the ledger and the physical currency, allowing an economy to exist in an entirely digital form.
If at any point a ledger user wants to exchange for real world currency, it needs to be occur as an agreement off-ledger, to facilitate physical exchange. This is a new paradigm for currency: it is defined by the ledger itself. The contained history of transactions defines possession and grants funds to be spent.
Hosting Problem
Thus far we have been discussing a public ledger, potentially hosted on a website where uses can go to submit and sign transactions. But who hosts this website? Who controls and enforces the rules of adding new ledger entries (verifying transactions based on digital signatures and available funds)? This system is still vulnerable to centralized internet-enabled service problems.
Bitcoin’s novel solution is to encourage all community members to keep their own personal copy of the ledger. Users can broadcast their signed transactions to the rest of network where updates are heard and recorded.
How can these members come to agreement regarding the contents and order in which transactions appear on the ledger? This is the innovation of bitcoin beyond precursor cryptocurrencies, which we will cover in detail in the second module.
In our discussion of money last week we recognized a distinction between representative money and fiat money. Recall that representative money are objects which can be exchanged for a fixed amount of a commodity (such as gold). Throughout history we have seen how representative money is limited by protection and legitimacy of the backing physical assets. Fiat (latin for let it be done) money, on the other hand, is currency that a government has declared to be legal tender, not tied to any physical commodity. In recent times, we have seen how fiat money is limited by regulation of inflation (Zimbabwe hyperinflation) and a government’s ability to manage foreign economic forces.
In either case, a central institution is necessary to manage supply and implement policy for usage, and in some cases settle disputes or even update policy. This challenges a decentralized model with the question: how can this managerial role be filled in an entirely anonymous, peer-to-peer financial network? The United States’ representative democracy (elected officials who enact policy) seems out of the question due to network anonymity. One solution is to replace institutional trust with programmable trust by using software that can simulate a governing body’s responsibilities as a decentralized clearinghouse and policy-maker. The use of software, though, introduces a new problem: processing power is necessary to perform this computation.
Bitcoin utilizes an ingenious protocol to encourage users of the network to provide this processing power by introducing systematic financial rewards: this system is called mining. Before we can understand Bitcoin’s mining scheme, though, we first need to understand at a high level the mathematical concept which gives cryptocurrencies their name.
Cryptographic Hash Functions
A hash function has a simple purpose: transforming data of arbitrary length to a fixed size.
- inputs: message or file
- output: string of digits with some fixed length called the hash or digest
The intent of this transformation is that it “looks random”. This means that slightly modifying the input changes the resultant hash completely. This is called the avalanche effect.
A cryptographic hash function has the property that it cannot be reverse engineered to understand how the inputs generate output. This means it is infeasible to compute in the reverse direction and infeasible to find an input which achieves a desired output without using guess-and-check.
The size of a hash function’s output is directly proportional to number of guesses required, based on simple probability. Bitcoin uses cryptographic hash functions to generate public keys from private keys and subsequently generate addresses from public keys. SHA256 (256 bit output) is a cryptographic hash function which a huge portion of modern security depends on (ie https). 3Blue1Brown put together a great video explaining just how miniscule the probability of breaking this function is. Amazingly, hash functions can be used to prove that a particular list of transactions is associated with a large amount of computational effort. This is the great innovation of Bitcoin.
Proof of Work
Imagine someone finds a special number which, when appended to list of transactions, generates a SHA256 hash that (arbitrarily) has 30 zeros at the beginning. The probability that this hash happens to start with 30 zeroes is 1/²³⁰ (~1 in 1 billion). It follows that, on average, 1 billion guesses are required to find this special number.
The special number, and the associated work in completing this many guesses, can easily be verified by a third party without repeating the same work using SHA256. Providing this special number to the Bitcoin network is called a proof of work. Because of the properties of hash functions, this proof of work is intrinsically tied to the attached list of transactions. If you change any transaction, even slightly, a different proof of work is required.
Distributed Ledger
In the first module, we were introduced to the idea of a ledger as a history of transactions which can define money itself. In a decentralized network, it is important that we don’t trust any central authority’s ledger. To solve this, network users can broadcast transactions out into the world for people to record on their personal version of ledger. But how can everyone agree on the same ledger? How can we be sure that everyone else is recording the same transactions, in the same order?
The core idea of the Bitcoin whitepaper is to trust whichever ledger has the most computational work put into it. If we use computational work as a basis for what to trust, fraudulent transactions and conflicting ledgers require an expensive and infeasible amount of computation to bring about.
Blocks and Chains
To structure these transactions, we can organize the ledger into blocks. A block is simply a list of transactions with a proof of work such that the hash of block starts with 30 (generalizable to n) zeros. A block is only considered valid by other network members maintaining their ledger if it has a valid proof of work. To ensure a standard order of blocks, a block must also contain a hash of the previous block. As a result, changing any previous blocks or swapping the order of any blocks requires redoing all of the work to find new proof of works.
A ledger as a chain of blocks linked by cryptographic hash is called a blockchain.
Block Formation/Mining
In the case of Bitcoin, we allow anyone in world to be a block creator for the chance of rewards. Their responsibilities are as follows:
- listen for broadcast transactions
- collect into block
- do work which makes hash of block start with n zeroes
- broadcast block once it is found
To reward successful block creators, we allow them to include a special transaction which grants the creator a fixed reward to their own balance, without siphoning any other user’s balance. This special transaction is called the block reward, and is an exception to our transaction rules. Consequently, the total money supply increases with each block. Creating blocks is called mining because it requires doing a lot of work and introduces new currency units (ie gold nuggets). Each block can be considered as a miniature lottery where miners are guessing special numbers simultaneously until one lucky individual finds a proof of work.
Managing Supply
All money in Bitcoin comes from some historical block reward. The Bitcoin protocol dynamically adjusts the number of leading zeroes required for a valid proof of work hash. This dictates the rate at which new supply is introduced by standardizing the average time it takes to find a new block to 10 minutes. As a result, new users and miners can join the network without altering the supply mechanism. Every 210,000 blocks (~ 4 years), the block reward is halved.
Therefore, the block reward as a function of time is a decreasing geometric sequence. This means there will never be more than 21 million bitcoin in existence, which makes runaway inflation implausible. Even when this supply runs out, miners are still encouraged to perform record-keeping with transaction fees. When a transaction between two bitcoin users is broadcast, a fee which goes to the miner of the containing block is optionally included. Miners only have an incentive to listen to transactions and include them in mined blocks because of this fee.
Shifting Trust
For anyone else who wants to use the Bitcoin system to make payments, instead of listening for transactions they can simply listen to block broadcasts and update their local version of the blockchain accordingly. If multiple blockchains are heard with differing transaction histories these users defer to the longest chain because it has the most computational work put into it.
If there is a tie, we can just wait until an additional block is heard which makes a given chain longer. If everyone agrees to give preference to longest chain, we have a way to arrive at decentralized consensus. Astoundingly, this allows us to shift trust from a central authority to computational work.
Statistics Trump All
To solidify the power of this trust model, it is useful to walk through an example where a user tries to cheat. Let’s say Alice is trying to fool Bob with a fraudulent block. She tries to send him one which includes her paying him 100 BTC. However, she broadcasts a valid block without this transaction to everyone else. To do this, she has to find 2 proof of works before the rest of the network (unlikely, but possible). As time continues though, Bob still hears block broadcasts from other miners. To keep Bob believing in her fraudulent block, Alice has to continue doing work to maintain Bob’s blockchain, which is different from what he is hearing from the rest of the miners. Recall Bob always trusts longest chain he knows about. Unless Alice has more than half of the computing resources among miners, the probability becomes overwhelming that Alice’s fraudulent chain is outpaced by the other miners working copy. Bob will eventually rejects Alice’s version of history in favor of the rest of the network’s. This also comes with the caveat that block trust intrinsically varies with time; the statistical confidence in the validity of a block builds as subsequent blocks are appended.
Next week we will talk about the nuances, alternate design choices, and limitations of the Bitcoin protocol.
References
If you’re interested in peer-reviewing our content, please feel free to make comments in the discussion or inline via Medium. We highly value feedback, and want to ensure that our content is accurate & meaningful — all help is appreciated. You can also reach out to us at blockchain@rice.edu with any private feedback.
