April 24, 2014

avatar

How Consensus Drives Bitcoin

Josh Kroll, Ian Davey and I have a new paper on the dynamics of Bitcoin, which we’re going to release in a few days. This post is the first in a series exploring our paper’s analysis of why Bitcoin works and what could derail it.

Consensus drives Bitcoin. Like any fiat currency (a currency not backed by anything of intrinsic value), Bitcoin has value because of an expectation that people will continue to accept the currency in payment. Like Tinkerbell, who exists because you believe in her, Bitcoin has value because enough people believe it has value. This much is true for all fiat currencies.

But Bitcoin is not just a currency, it is also a technology—and that technology must function correctly for the currency to operate and retain its value. In particular, there are two additional forms of consensus that must exist for Bitcoin to operate.

Consensus about the rules: Participants must agree on the rules that determine which transactions are allowed and which are not. The rules for transaction legality are written down, but they are not self-executing. For the rules to have any force, participants must ignore the existence of non-conformant transactions, while accepting conformant transactions.

Consensus about history: Participants must agree about the history of the Bitcoin economy, that is about exactly which transactions have occurred. Without this agreement, they can’t know who owns which Bitcoins.

Notice that the three forms of consensus—consensus that the currency has value, consensus about the rules, and consensus about history—are interdependent. The loss of any one will unravel the other two. For example, if you and I disagree about what the rules are, then eventually our views of the history will diverge, because eventually one of us will believe a history containing a transaction that the other cannot accept. Or if people can’t agree on who owns which Bitcoins, then the currency will lose its value.

Currently all three forms of consensus exist in Bitcoin. One of the key questions we examine in our paper is whether this can change. Obviously the consensus that Bitcoins have value could evaporate for any number of reasons. So we focus on the other two forms of consensus, rules and history, and we ask how stable they are.

The consensus on rules needs some explanation, because there is a common misconception that the rules of Bitcoin were laid down at the beginning by Satoshi Nakamoto and cannot be changed. It’s true that Satoshi created the initial ruleset, but the rules can change at any time, if there is a consensus in the community that the rules should be changed.

There is also a common misconception that the rules of Bitcoin are somehow self-executing, but that isn’t true either. There is a certain (assumed) mathematical certainty about the cryptography—a digital signature either is or isn’t cryptographically valid—but this doesn’t make the rules self-executing. You can always detect an incorrect digital signature, but the rule that transactions with incorrect signatures should be ignored as invalid will only have force if participants do choose to ignore such transactions.

The possibility of changing the rules is not just theoretical—the rules have been changed in the past. One example was in March 2013, when a software bug in one version of the default Bitcoin client caused it to treat as invalid a transaction that was actually valid according to the rules. This amounted to a failure of rules consensus—some people (erroneously) treated the offending transaction as invalid, while others (correctly, according to the rules) treated it as valid. This led to a divergence in the history, as each group had a slightly different idea about who owned which Bitcoins. The community responded to the divergence by temporarily changing the rules in order to reestablish a consensus history.

All of this suggests an obvious question: If the rules of Bitcoin can be changed, and have been changed, then how do rule changes happen? Who, if anyone, is in charge, and how does the Bitcoin community govern itself? I’ll turn to this question of Bitcoin governance in a future post.

Comments

  1. Tom Slee says:

    I am puzzled by “consensus about history”. I guess Bitcoin provides this through the block chain, but I am unaware of any other currency that provides it and do not understand why it would be needed. Most obviously, when it comes to cash, no one knows where my cash comes from or if I “own” it, yet I use it without problems every day.

    • Joshua Kroll says:

      Bitcoin is essentially a public ledger system – every transaction is written in a log (the block chain) and you can trace every coin backwards to the point at which it was first minted, following every transaction in the history. Everyone needs to agree on what is in the history (and which version to use, if and when multiple versions exist) so that you know who owns which coins (and therefore that a coin someone offers to pay you with hasn’t been previously used to pay someone else).

      Obviously, physical currency doesn’t need something like this. But you might think of other kinds of electronic money as having something similar. Think about credit cards, for example: every month, every “dollar” of your credit line is accounted for in a ledger (statement) that the company sends you so that you and your card company can agree whether that dollar is yours to spend (available as credit) or theirs to receive at a later date (because it has already been spent in some transaction in the ledger).

      Ostensibly, if we could all agree to cooperate, we could skip all the crypto and just write down on a piece of paper who has what money. That’s sort of how the credit card example works – you and your credit card company have agreed to cooperate and to account for the money in a particular way. In Bitcoin, though, the players can’t agree to cooperate because there are too many of them and they’re not willing to trust one another. So we need another mechanism to achieve consensus.

      • Tom Slee says:

        Joshua – Thanks for the explanation. I am still not convinced that the entire history needs to be carried around in order to verify ownership. Stepping away from Bitcoin, database systems record transactions in a transaction log, but periodically checkpoint the database file and then the transaction log can (for many purposes) be thrown away. Similarly, stamping a complete record of transactions into the block chain and carrying that rounds seems more complex than a stamp of “ownership” at a point in time. I’m ignorant of the details, and of course I don’t have an implementation in mind.

        • Joshua Kroll says:

          That’s a good point, and indeed you don’t need the entire history to determine ownership – you just need to validate the previous transaction (if you trust that the people validating that transaction did the right thing). Bitcoin has mechanisms for this which involve putting the transactions in each block into a Merkle tree, although they don’t seem to be used yet. But the idea is that, given some transaction, you can place it exactly in the log using crypto. Once you have done that, you can trust that the network accepted the transaction when it was entered, so you don’t have to do quite all of the verification. But someone still has to have the full block chain to verify new transactions.

          I think your point is well made that the community could, in principle, “compact” the log into a concise description of which coins are owned by which addresses and then the history would not be necessary. Actually, the reference Bitcoin client already does this – the block chain itself is kept on disk, but in memory there is a cache of “unspent” transactions (i.e. live/spendable coins). And this leads to friction – because some kinds of transactions (mostly betting transactions that lose) lead to many very small-denomination coins (which the community calls “dust”), this cache can become very large, even though it’s mostly filled with useless stuff.

          The important thing about the log is not that it lasts forever but that it helps people agree on what transactions actually took place. Once everyone agrees, the log is, in principal, not useful anymore (or could, anyway, be replaced by something else). In practice, though, I don’t think it could ever really be thrown away – someone would keep it and might even use it, so I’m not sure what the benefit would be.

        • Ed Felten says:

          Tom,

          You’re right that a full public log of the history isn’t necessary, in the sense that one could build a digital currency that doesn’t have a public log. But Bitcoin’s design does rely on having all transactions, and the full state of who owns which coins, known to the world.

          A key technical problem in digital currencies is how to prevent double-spending, that is, how to keep somebody from duplicating a digital coin and spending both copies. There are various approaches to preventing double-spending. One approach is to have some kind of central authority who gets enough information to detect double-spending. If, like Bitcoin, you don’t have any central authority, then fully public records (with some degree of anonymity for users) seem like a good way to make double-spending detectable. That’s the approach that Bitcoin takes.

          So consensus on history is not necessary for all digital currencies, but it does seem to be necessary for Bitcoin.

      • Nathan T says:

        The more I read about the Bitcoin the less I like it. I could go off on all sorts of things but this scares me the most

        “and you can trace every coin backwards to the point at which it was first minted”

        At least with the dollar… yes it could evaporate its perceived value at anytime too, I don’t have to trace it back every transaction to validate it’s existence. Nor would I want to.

        I mean some people just love to, via various defacing mechanisms, and it is all fun and games. But, privacy… did I spend that Bitcoin on nefarious activity? Did someone pay me a bitcoin that they got from selling nefarious goods or services? And on and on.

        I would think the privacy problem with ANY currency that you can “trace backwards to the point it was first minted” would be completely and wholly unacceptable in any civilized society.

  2. Bit Coin says:

    Where will the paper be published? Will it be freely available?

    • Ed Felten says:

      The paper will be published at the Workshop on Economics of Information Security. It will be freely available—we’ll link to it from a future post.

  3. Hamish MacEwan says:

    Thanks very much for Freedom to Tinker’s articles on Bitcoin, they have provided a more nuanced view of issues like unregulability & fees, that like much else is simplified and touted as advantages to Bitcoin.

    A couple of points though.

    I’m sure you’ve read the March 2013 Chain Fork Post-Mortem by Gavin Andreesen (https://en.bitcoin.it/wiki/BIP_0050 for anyone who wishes to read it in detail.) From that it seems there was more involved to the solution than changing the rules, firstly a roll-back of an upgrade involving significant sacrifice by interested parties. Although the rules were changed in the subsequent patch, they weren’t to the protocol per se but to meta values (“Reject blocks that could cause more than 10,000 locks to be taken.”) and variables like block maximum size that aren’t protocol and as such weaker than rules.

    The Simplified Payment Verification alternative that doesn’t require a full client’s blockchain security blanket is where the Merkle Tree’s abbreviated blocks are exploited. Like Joshua I’m not certain this is used, though BIP 0037 (https://en.bitcoin.it/wiki/BIP_0037) “Connection Bloom filtering,” describes the use of Bloom filters and Merkle branches to minimise transmission and storage requirements in constrained devices. While the BIP is “Active” its not clear that that means implemented, as that would acquire the state “Fina.l”

    However, since what passes for the protocol specification (in lieu of anything more formal I’ve been able to locate, https://en.bitcoin.it/wiki/Protocol_specification) includes filterload, filteradd, filterclear, and merkleblock as defined in BIP 0037, it would seem the functionality is live. It also seems the Android “Bitcoin Wallet” client, https://play.google.com/store/apps/details?id=de.schildbach.wallet was part of the motivation to implement this efficiency enhancing technique.