A Primer on “Bitcoin: A Peer-to-Peer Electronic Cash System” by Satoshi Nakamoto
A page-by-page guide to The Paper of the Century
What follows is a page-by-page guide to Nakamoto’s paper, published in October 2008. It is meant as a useful guide for those who have not yet read this most essential of papers on Bitcoin, for those who tried to read it and gave up midway, and perhaps even those who do not see the point. Nakamoto left us with other sources that were less formal than this paper. I do not consider those in this article. Here, I focus attention solely on what is in ‘The Paper’.
A few caveats: First, I am a social scientist grounded in economics, not a programmer. So my understanding is rudimentary on the complexities of cryptography. Second, we have the considerable benefit of hindsight when we read or re-read Nakamoto now. I try to use that advantage sparingly when providing this commentary. I urge you to do the same since it will permit you to better appreciate the unrealized vision outlined in the paper. Third, there is, unfortunately, a great deal of very opinionated philosophizing and chest-beating these days on what Bitcoin was, is and should be. It is worthwhile checking your opinions on Bitcoin at the door and just reading the paper with your blinders on.
Finally, permit me to raise a glass to Nakamoto with you as you read this article. I hope you will love it as much as I do for its parsimony, elegance, insight and vision.
Let us begin.
Page 1 of 9
The very first sentence of the Abstract declares more than just the premise. It sets the stage: the objective is disintermediation; the agents of action are peers on a payments network; the source of the problem — the systemic deficiency — are financial institutions.
The ambition for the proposed solution is the epitome of audacity: making the role of a trusted third-party obsolete. If I were a smarter man, I would have promptly fallen off my chair in shock at this juncture. But the nonchalance with which this subversive intention is stated required a few readings to make its import more fully apparent to me. This delayed reaction is perhaps testament to the degree of embeddedness in our lives of the status quo that features financial intermediation by a vast complex of institutions. After all, the most potent of status quo biases that a system creates is one that results in the victims themselves engaging in system justification.
The most elegant part of the solution, even as it reads in the abstract, has a simplicity that is best compared with Darwinian theory.
The impacts of cumulative action over a geologic time scale are beyond the grasp of even the sharpest of human minds. Darwin needed 500 pages and 30 years of observations and experimentation to formulate his phenomenal and seismically significant idea. By contrast, the impact of institutional structure over societies extends back to the Upper Paleolithic. That, too, is a timescale that precedes virtually every belief we have; indeed, it defines it. Nakamoto needed 9 pages and at least as many years of observing the effects of unfettered financial institutions to formulate his idea. Both ideas — Darwin’s and Nakamoto’s — fundamentally altered our perspectives on the institutions that we took as self-evidentally necessary, even pre-ordained.
What was Nakamoto’s solution? It was quite simply that of replacing the role of an institution with its most essential function, and, in doing so, sharpening its effect. One need not appeal to a single trusted third-party to validate the sequence of transactions in a network. The network would be based on something real — computing power — to create an indestructible ‘ongoing’ record of transactions. The size of the Grecian columns on a building aren’t needed to signal the trustworthiness of an institution that acts as the de facto and de jure third-party; the length of a chain of transactions was all that was needed. ‘Minimal structure’, maximal effect.
The final sentence of the Abstract is a particular favorite of mine. It’s tacked on innocuously, but it is actually the knockout punch as far as I am concerned. The system being proposed is built on principles of fairness, freedom and choice: proof of work instantiates the quality of participation based on ‘best effort’; participation is free, not mandatory as you might be preprogrammed to imagine; the ‘institution’ of a longest chain based on proof of work can be trusted to work reliably even when you are not actively invested in monitoring it.
The paper is brilliant, but short on humor. In section one, Introduction, however, the paper contains, what to me anyway, is a pretty solid joke. It is this line:
‘Completely non-reversible transactions are not really possible, since financial institutions cannot avoid mediating disputes.’
I am sorry, I just find this sentence to be the absolute frozen limit. It could well have begun with ‘knock, knock’. I read it as this: “Financial institutions cannot help but keep playing at referee, for if they really did, transactions could perhaps be made non-reversible, and I would not feel as compelled to sock ’em in the eye and write this paper.” As it is, they poke their longish nose into every transaction, and socialize the cost of intermediation through increased transactions costs that then serve to delimit the types of transactions that can be conducted.
The point is serious and I do not wish to bury it under my dubious sense of humor. A trusted third party increases the probability of reversing transactions; even when they do not do so, the theoretical possibility of reversing a transaction willy-nilly does exist, and this forces us to protect our interests more keenly. The merchant gathers more information than needed; we avoid making small transactions altogether; we tolerate a degree of fraud as a necessary evil, or we resort to compressed transactions (the cash-only, take-with-one-hand-give-with-another types of transactions).
In the final paragraph on page 1, we see the direction the paper is heading. The solution is couched in commonsense for the readers by asking them to consider that cryptographic proof isn’t so much a substitute for trust generally, but trust that is accorded by default to a third party. The word ‘trustless’ (which I have always found a little unfortunate) isn’t mentioned once in the paper. If you do not apprehend the notion that making transactions on the network computationally impractical to reverse is a silver bullet for the problem, you aren’t going to trust it very much, are you? Trust in computational proof requires a logical sequence that Nakamoto unravels, right at the bottom of the page:
- Double-spending is the Achilles’ heel of any digital cash proposal, but the proposal in this paper will solve that issue;
- The proposed solution uses a distributed network structure, so the solution matches its intended use in its very structure. This is a gem of a point. You aren’t being peddled some solution for making a baked potato that starts with you having to buy a nuclear reactor. Solutions that start with potatoes are strictly preferable.
- Time is the ultimate dispassionate arbiter; transactions have a natural chronological order. The solution makes use of this fact by employing computational power in the network to generate proof of this connection.
- The solution has one reason, and one alone, for you to really not have trust in it, and it is stated in plain sight. Honest nodes in control ought to be in control of more computing power than the dishonest nodes.
The rest of the paper, as we shall see, is devoted to fleshing out the interlocked pieces of this solution.
Page 2 of 9
The idea of a currency that is intrinsically tied to a placeholder for an individual’s identity in an open market — her public key — is a concept that Bitcoin has made accessible to the world.
Currencies issued by governments permit no such innate correspondence without having to appeal to a financial intermediary who can attest to ownership. So when Nakamoto begins section 2, Transactions, by conceptualizing a ‘coin as a chain’ of conjoined signatures, we have a definition for the value of a currency that is severed from some issuer in one withering fell swoop.
A money is a medium of exchange. Every Tom, Dick and Harry will remind you of this. However, part of what this means is that a money is first a medium of account. If it cannot serve in that elementary role, we are forced to farm out the role of accounting to an intermediary who can keep track for us. But, we are assured at the outset of this section, that the function of the chain is to serve as a record. Bitcoin is a medium of exchange because its chain is the quintessential medium of account. A transaction on a chain is defined as a public announcement of the transfer of a coin from a payer to a payee in such a manner that the chain’s state is updated to reflect its most current state of accounts. Further, this updating is validated, not by a trusted third-party of some description, but by a majority of participants within the payment network. This is a curveball all by itself, so precisely how this is to be done is left till later. For now, Nakamoto wishes to emphasize the larger point that a single undisputed history for the chain prevents the possibility for a double-spend. A government-sanctioned processing center for currency (a mint, say), is not necessary.
Incidentally, the first source that Nakamoto cites is Wei Dai’s short paper, which seems to be motivated by creating a practical currency called ‘b-money’ that emphasizes anonymity and makes government ‘permanently unnecessarily’! It also lays out a consensus protocol that appears to presage proof of stake. It’s a worthwhile read in its own right.
Second 3, Timestamp Server, appears, at first glance, to be no more than a footnote. Essentially, it suggests the role that a publicly announced timestamp plays. It is, of course, crucial in importance since the point it drives home is that a hash of a block of transactions becomes a strong proof of an evolving status quo of a system when it is publicly announced. In other words, we are indelibly associating transactions with a shared unit of time.
The references that Nakamoto cites in this section are, as one would expect, germane to supporting this idea. The paper by Haber, Stornetta and Belcore from 1991 is a particularly fascinating read (if only because it sends you down a wonderful path of discovery on the origins of hash functions in cryptography). In it, the authors describe the problem of indisputably establishing prior ownership of a variety of assets by reliably time-stamping them. Very briefly, they consider three situations: A simple case of employing a trusted cryptographic TSS (time-stamping service), who attests to ownership; a more complex situation where the TSS may be unscrupulous, but can nevertheless be made to act honestly by being forced to link multiple records in its verification; finally, they consider a verification system they call ‘distributed trust’, where, instead of a TSS, individuals participate in a system based on a publicly available pseudo-random generator that can be fed the hash, and which cannot easily be faked without a broad conspiracy of the users.
Together, the two sections on page 2 constitute Genesis for the idea of a blockchain in its bare essentials. The word ‘blockchain’, by the way, isn’t used anywhere in the paper.
Page 3 of 9
The page begins with section 4, Proof-of-Work, and, perhaps for this reason, this is a particular favorite section of mine.
The idea of proof of work derives from the logical premise that the ownership of CPU power necessitates incurring a real quantifiable cost. And since the cost is quantifiable, its use can also be made directly verifiable across the entire system.
Nakamoto cites Adam Back’s paper on Hashcash here, which had provided an inspired solution to the problem of asymmetric access to network resources permitting actors on a network to engage in activities that impose a range of undesirable negative externalities on its participants.
As a method to curb these situations, Back proposes that a prospective client be made to compute a token as proof of work. This computation entails a real cost, and Back discusses features of the various types of parametrizable cost functions that might be selected for this task. Among these features is the idea of the system issuing a challenge that makes the computation by the clients assume an unbounded probabilistic cost, yet be publicly verifiable. Nakamoto’s solution for Bitcoin builds on this structure, by using real CPU power to construct a more desirable form of voting in the system, much in the way that having more skin in the game yourself makes you somewhat more credible.
Proof of work operates in the following manner: The participant who presents a block first finds a specific value, called a nonce, such that, when it is hashed using the SHA-256 algorithm, together with the hash of the previous block and the transactions within the block, it creates an output that is less than or equal to a target value. Naturally, it is virtually impossible to just guess this value directly; real work simply must be done. Further, this nonce must be published by the node as part of the block data, and so it becomes child’s play for anyone else in the network to stick it into the hash function and verify the node’s claim.
Nakamoto also introduces the idea of adjusting the difficulty level of the proof of work involved in this section based on the ‘interest in running nodes over time’, an idea that is now familiar to most of us. (Nakamoto does not use the word ‘miner’ anywhere in the paper for the nodes that we now routinely call miners; Adam Back may have prefered the word ‘minter’.)
Just parenthetically, while Nakamoto does not cite the Second Law of Thermodynamics in the paper, I like to think that it was somewhere in the field of muses that were used in writing the paper. The brilliance of the Second Law is that it creates a near-inviolable definition for time that accords with the non-reversibility of a process. It may be theoretically possible, of course, to separate your dinner back into its ingredients, but the longer the recipe list (and the more work you did in cooking the meal) the harder it is to practically achieve this. I like to think that Nakamoto used this premise as a strong impetus for defining an honest chain as one that is built by allying itself to the desirable non-reversibility characteristics that a longer chain will naturally accumulate.
Section 5, Network, is a simplified blueprint for the process by which blocks are added to the Bitcoin blockchain — its ‘consensus algorithm’, if you prefer. (Nakamoto does not use the word ‘Bitcoin’ anywhere else in the paper, apart from the title. Perhaps it was thought that using it liberally everywhere would have sullied the elegance of the argument in the paper, I cannot say. Somehow, though, I like that fact very much. This is how a whitepaper ought to be written: the force of logic alone should suffice.)
Page 4 of 9
You may wonder why the enumerated procedure, as laid out in section 5, would work in the face of bad actors in the network who wish to sabotage it, say by deliberately excluding certain addresses or by creating invalid (double-spent) transactions?
Nakamota resolves these concerns with the explanation that concludes section 5 and follows from page 3 on to page 4. Nakamoto avers that nodes take the length of the chain as sacrosanct, and that length suffices in resolving situations that represent an impasse.
In section 6, Incentives, Nakamoto lays out the payoffs that nodes would receive from participation in a system that does not have any central planner who doles out currency, and, crucially, how the structure of these payoffs incentivizes honesty as an evolutionary stable strategy. (As a student of contract theory in economics, I found this section to be pretty much proof-positive of the connections between mechanism design and Bitcoin. That, however, is quite a different story.)
There are three incentive considerations, each with desirable characteristics: First, there is, what we now call, the ‘block reward’ that nodes receive for creating a block of valid transactions, and adding it to the longest chain. The effect of this is best expressed in the paper. Here’s Nakamoto:
The steady addition of a constant of amount of new coins is analogous to gold miners expending resources to add gold to circulation. In our case, it is CPU time and electricity that is expended.
Second, Nakamoto suggests a transaction fee as an incentivizing mechanism for nodes. The rate of transition from a block reward to a transaction fee depends on how many of the ‘predetermined number of coins’ have already entered circulation. A transaction fee is also compatible with a queue that is based on urgency of need (much like a tip you might hand over to the maître d’ to get you a nicer seat a little ahead of the queue at the restaurant).
Finally, Nakamoto loops round to the idea of fair play discussed earlier. Realizing that rational actors would consider schemes to game the system to their advantage, Nakamoto suggests how this incentive structure works in practice to make the incentives for fair play greater than foul play. Simply stated, adverse actors benefit more by using their resources in pursuit of extending the chain with valid transactions than by using these resources to sabotage it; Bitcoin is constantly making the nodes (miners) an offer they can’t refuse.
Every time I read the paper, I find it remarkable that Nakamoto envisioned longevity and broad adoption for his creation from the outset. Section 7, Reclaiming Disk Space, goes some way in supporting this observation. The use of a pruned Merkle tree enables making the Bitcoin blockchain more compact over time. The diagram shows an example where only one of four transactions need to be directly carried forward after the Merkle tree is pruned and only the hash of its root then need be included in the block; far more efficient than having to lug around all four transactions in perpetuity.
Page 5 of 9
While section 8 is called Simplified Payment Verfication, it might equally have also been called Run Your Own Full Node, Lazybones.
Having just explained the compactifying quality of Merkle trees, Nakamoto now suggests the relative ease with which any user can confirm that transactions have been accepted into the Bitcoin blockchain without having access to a full network node. There is, however, a large cumulative social benefit that running a full network node provides the Bitcoin network, at a rather small private cost.
Running a full node increases the reliability of the Bitcoin network by ensuring the integrity of its chain. More elementally, running a full node captures the ethos of Bitcoin — its raison d’être: it preserves its decentralized structure.
Nakamoto concedes that the incentives for running a full node are likely to be greater for commercial entities, but, given how painless the process of running one is, it really ought to be default behavior. In case you were wondering, there are, as of writing, less than 10,400 nodes on the Bitcoin network across the world, of which two-fifths are in the United States and Germany.
Section 9, Combining and Splitting Value, suggests how any given transaction might be treated by combining one more inputs from previous transactions. Nakamoto’s objective here is to assuage concerns about Bitcoin’s ability as a medium of account with desirable static (as in, snapshot picture of the account) and dynamic (as in, keeping track of things over time) capabilities. Dependencies across transactions on the chain are so perfectly dependable that bitcoin is the poster-child medium of account.
Page 6 of 9
Section 10, Privacy, is a rather important part of the paper and absolutely foundational to Bitcoin.
Nakamoto points out the counterintuitive idea that, in the network described in the paper, open decentralization is not incompatible with privacy. This is antithetical to the understanding most people have. By default, we are programmed to believe that privacy requires — almost synonymously so — a trusted third party. Rather than turn the paper into a polemic on institutions, Nakamoto simply suggests that the model is replicable on a decentralized network by using public keys.
I cannot say to what extent Nakamoto foresaw the relatively uncomfortable level of trust most people place in exchanges, but the I like to think that the analogy provided in this section on the stock exchanges presages the present state of affairs.
Still, Nakamoto’s interest in privacy, as represented in the paper, may not have been as ardent as it is with many other Bitcoiners. Nakamoto recognized full well that it is entirely possible to reverse engineer transactions and attribute public keys to their owners .The diagram presented in this section, juxtaposing the Bitcoin privacy model with the privacy model of traditional banks, emphasizes parsimony and elegance in achieving a similar degree of desirable privacy.
In section 11, Calculations, Nakamoto presents an interesting evaluation of the dynamic evolution of two competing paths of the network, when faced with the prospect of an attacker building an alternate adversarial chain. Using a binomial random walk process to model this situation usefully simplifies the problem, because one need only consider the probability of the attacker’s path (chain) gaining a relative advantage of one unit (block) during each time period elapsed, and then playing this race out over time.
Before the simulation is presented, Nakamota makes clear that this scenario is still one that requires the attacker to play by the rules as established by the Bitcoin network. This parameterizes the problem to one where we need only consider how the attacker uses resources to outcompete the incumbent (honest) chain.
The nomenclature of the equations that Nakamoto presents are directly drawn from the classic book by Feller that is cited in that section, admittedly in a vastly simplified format. (The explanation in that book is extremely lucid, and worth browsing if you are somewhat statistically minded, if only to gain insight into Nakamoto’s thought process.)
Essentially, at each step of the random walk, some random variable (which, for Nakamoto is the ‘state of the race’ between the chains) can assume one of two values, +1 or -1, with probabilities p and q, respectively, upon which the evolution of the distribution function for the random variable would then naturally depend. Obviously, the relationship between p and q is critical in determining the dynamic path of the random variable. When p < q, for instance, we should expect that the probability that the random variable accumulates a positive position on the path (known as a ‘ladder point’) becomes smaller. The situation reverses for the situation where p > q. What Nakamoto is concerned about is two things: First, finding the conditions for descending ladder points emerging in the sequence of the random variable, which is to say that the honest chain is verifiably losing to the attacker. Second, Nakamoto’s interest is in finding the probability of any given ‘ladder height’, z, which is to say the distance by which one chain leads the other.
Page 7 of 9
We continue on this page with the simulation exercise that began in section 11 of page 6.
The case that Nakamoto has to consider is vastly simpler than the general cases in the book he refers to because, by assumption, p > q.
The example that motivates the simulated race between the honest and the attacker’s chains is laid out on this page. It is a situation where the attacker sends a payment on the network, but immediately works to double-spend by building a chain that contains the invalid transaction.
The race is governed by a fixed period of time (on average, anyway) between the blocks, and, for this reason, and the fact that the probabilities of new blocks being added to the chain are independent of each other, Nakamoto uses a Poisson probability distribution to provide us with the expected value that the attacker will be z steps ahead of the honest chain. (If we are being pedantic, this should actually have been a Negative Binomial distribution rather than a Poisson distribution, but this has no bearing on the conclusions in the paper.) However, since ‘victory’ is dependent on the extant relative distance between the chains, k, Nakamoto adjusts the expected value for this dependency.
Page 8 of 9
We come now to the final page of the writeup in Nakamoto’s paper.
The page presents results from a simulation of the double-spend race, which shows that, even if the attacker has a 30% probability of finding the next block, he still loses the race as long as the honest nodes link more blocks to the chain. Essentially, catching up and surpassing the honest chain becomes a futile task when the lead is anything but extremely small and the attacker has an infeasibly high probability of finding the next block. The rate at which the attacker’s chance of success degrades is pretty astounding (a hugely reassuring state of affairs).
And so we reach section 12, Conclusion. The aspects that Nakamoto chooses to highlight from the paper are worth a look. Two broad ideas deserve particular pride of place for Nakamoto. First, the idea of a digital payment system that provides a public history of transactions, yet is nigh impervious to the double-spending attack; associated with this pièce de résistance of a point is the specific mechanism of proof-of-work that helps facilitate incentives for honest nodes to control a majority of computing power. Second, the idea of ‘unstructured simplicity’ appeals to Nakamoto. The idea that the network requires ‘little coordination’, encourages ‘best effort’ and provides nodes with the freedom to exit and enter at will, and vote by proxy of computational power. These features undergird the incredible stigmergic environment of the Bitcoin network that the paper outlines.
Page 9 of 9
The final page contains a list of references. I have made an effort to refer to those that I have read within this guide, and so I shall refrain from adding more to the length of this article.