January 18, 2017

Bitcoin is unstable without the block reward

With Miles Carlsten, Harry Kalodner, and Matt Weinberg, I have a new paper titled On the instability of Bitcoin without the block reward, which Harry will present at ACM CCS next week. The paper predicts that miner incentives will start to go haywire as Bitcoin rewards shift from block rewards to transaction fees, based on theoretical results that closely match up with findings from our new Bitcoin mining simulator.

Bitcoin provides two incentives for miners: block rewards and transaction fees. Currently the vast majority of miner revenues come from block rewards, but in the long run they will come primarily from transaction fees as block rewards dwindle. This design decision has been discussed a lot, but in terms of monetary policy and hardly ever in terms of security. There has been an implicit belief that the transition to transaction fees will not affect the security and stability of the block chain, and in particular that it is immaterial whether miners receive (say) 25 bitcoins as a fixed reward or 25 bitcoins in expectation via transaction fees.

We reexamine this assumption in our paper, and our findings make disturbing news for the future security of Bitcoin and many other cryptocurrencies. Our key insight is that with only transaction fees, the variance of the miner reward is very high due to the randomness of the block arrival time, and it becomes attractive to fork a “wealthy” block to “steal” the rewards therein. [1]


The figure shows a scenario where forking might be more profitable than extending the longest chain. See the paper for a full explanation.

Here’s how things could go wrong. Due to the possibility of profitable forking, the default strategy is no longer best; we lay out a menagerie of interesting and bizarre strategies in the paper. The most worrisome is “undercutting,” where miners capture as little of the available transaction fees as they can get away with, leaving the rest in the pool as an incentive for the next miner to extend their block rather than a competing block.

We also show rigorously that selfish mining gets worse when block rewards are replaced by transaction fees, motivated by the following intuition: if you happen to mine a new block just seconds after the last one was found, you gain nothing by publishing, so you might as well keep it for selfish mining in case you get lucky. The variance in transaction fees enables strategies like this that simply don’t make sense when the block reward is fixed.

If miners switch to these deviant strategies, the blockchain will be much less secure because of the mining power wasted due to constant forking, undercutting, and withholding of found blocks.

We derive most of our results in two separate ways: analytically, i.e., using game theory, and with a new mining simulator that we created. This gives us added confidence in our findings. For example, in one setting, the theory predicts a rather grotesque equilibrium involving on the Lambert W function, with the proof running to several pages. Sure enough, in our simulations of the same setting, the Lambert miner does best. We hope that our analytical techniques as well as our simulator will be useful to other researchers. We have made the simulator code open-source.

What is the impact of our findings? The Bitcoin community will probably need to respond to this problem in the long run, potentially via a fork, to discourage deviant strategies. We aren’t predicting that deviant strategies will arise in the short term, and there is a long runway for mitigation steps to be rolled out. The fact that blocks have filled up due to their 1MB limit decreases the variance of transaction fees between different blocks, and this mitigates the problem somewhat, although it is far from a complete and satisfactory solution. For example, at the time of writing our paper, the previous 1000 blocks included per-block transaction fees ranging from 0.03 BTC to 4.51, with a mean of 0.49 and standard deviation of 0.25 (over half the mean!). So simply maintaining the block-size limit probably won’t resolve the underlying issues.

At a deeper level, our results suggest a fundamental rethinking of the role of block rewards in cryptocurrency design. The prevailing view is that the block reward is a necessary but temporary evil to achieve an initial allocation of coins in the absence of a central authority. The transaction-fee regime is seen as the ideal steady state of the system. But our work shows that incentivizing compliant miner behavior in the transaction fee regime is a significantly more daunting task than in the block reward regime. So perhaps designers of new cryptocurrencies should make the block reward permanent and accept monetary inflation as inevitable. Transaction fees would still exist, but merely as an incentive for miners to include transactions in their blocks.

One final point: there is a science of designing economic incentives so that rational players will behave in a desired way, and it’s called mechanism design. Creators of cryptocurrencies (as well as creators of applications such as the DAO) are essentially doing mechanism design. But mechanism design is hard, and our paper is the latest among many to point out that the mechanisms embedded in cryptocurrencies have flaws. Yet, sadly, the cryptocurrency community is currently disjoint from the mechanism design community. That is why I’m thrilled that mechanism design expert Matt Weinberg, who’s behind all the sophisticated theory in our paper, is joining Princeton’s faculty next semester. Expect more research from us on the mechanism design of cryptocurrencies!

[1] The problems uncover arise not because transaction fees may arrive erratically, but because blocks inevitably arrive unpredictably.  We model transaction fees as arriving at a uniform rate. The rate is non-uniform in practice, which is an additional complication. This is a theme throughout our paper: we show that undesirable behaviors will arise even in simplified, “clean” models. This is bad news both because we think things will probably be worse in practice and because we want cryptocurrency mining games to be analytically tractable. Our work shows that in a transaction-fee regime, predicting behavior will be fiendishly complex.

Update: see also Bryan Ford’s response to this post (and paper).

Bitcoin’s history deserves to be better preserved

Much of Bitcoin’s development has happened in the open in a transparent manner through the mailing list and the bitcoin-dev IRC channel. The third-party website BitcoinStats maintains logs of the bitcoin-dev IRC chats. [1] This resource has proved useful is linked to by other sources such as the Bitcoin wiki.

When reading a blog post about the 2013 Bitcoin fork, I noticed something strange about a discussion on BitcoinStats that was linked from it. Digging around, I found that Wayback Machine version of the logs from BitcoinStats are different; the log had been changed at some point. I was curious if only this conversation was truncated, or if other logs had changed.

After scraping the current version of the BitcoinStats website and scraping the Wayback Machine versions, I found that many pages are different from their Wayback Machine version. For example on the log for January 11, 2016 many entries for the user by the username ‘Lightsword’ are now blank. The number and nature of the errors makes it appear there might be a bug in the backend of the BitcoinStats website, rather than a malicious censure of certain conversations. There may not be a complete history of the IRC channels anywhere, as the Wayback Machine also has holes in its coverage.

It is unfortunate that artifacts of Bitcoin’s development history are being lost. There is value in knowing how critical decisions were made in frantic hours of the 2013 fork. An important part of learning from history is having access to historical data. Decisions that shape what Bitcoin is today were originally discussed on IRC, and those decisions will continue to shape Bitcoin. Understanding what went right and what went wrong can inform future technology and community design.

The lesson is that online communities must make deliberate efforts to preserve important digital artifacts. Often this is merely a matter of picking the right technology. If GitHub were to disappear tomorrow, all of Bitcoin’s code history would not be lost thanks to git’s decentralized and distributed nature. All of Bitcoin’s transaction history is likewise famously replicated and resilient to corruption or loss.

Preserving the IRC logs would not be difficult. The community could distribute the logs via BitTorrent, as Wikipedia does with its content. Another option is to use the form the Wayback Machine provides to ensure the archiving of a page (to minimize effort, one could automate the invocation of this functionality). Given how important preserving this data is and how easy it is, it seems worthwhile.

[1] IRC as a whole has a culture of ephemerality, and so Freenode, the server that hosts the bitcoin-dev IRC channel doesn’t provide logs.

Improving Bitcoin’s Privacy and Scalability with TumbleBit

Last week we unveiled TumbleBit, a new anonymous payments scheme that addresses two major technical challenges faced by Bitcoin today: (1) scaling Bitcoin to meet increasing use, and (2) protecting the privacy of payments made via Bitcoin. Our proof-of-concept source code and a pre-print of the latest version of our paper were both posted online last week. In this post, I’ll walk through the motivation and the design of TumbleBit, and explain how it achieves the following three important features:

  1. TumbleBit works with today’s Bitcoin protocol. No changes to Bitcoin are required.
  2. TumbleBit payments are processed off of the Bitcoin blockchain, helping Bitcoin scale to higher transaction velocity and volume. Like Bitcoin’s on-blockchain transactions, the safety and security of payments sent via TumbleBit do not require trust in any third party. The TumbleBit payment hub can not steal a user’s Bitcoins.
  3. TumbleBit provides anonymity for its off-blockchain payments even against the TumbleBit service. The exact property we guarantee is unlinkability (as explained in detail below).

Bitcoin Anonymity Concerns

Bitcoin is the ultimate transparent currency. Each transaction reveals the value of bitcoin that was transferred, and the addresses (Bitcoin identities) of both the party transferring the payment and the party receiving the payment. Even worse, these transaction details are recorded in an immutable and massively-replicated ledger which can be read by anyone, i.e. Bitcoin’s blockchain. Feeding this concern is a burgeoning blockchain analytics and surveillance industry.

This presents problems for businesses that want to use Bitcoin, but don’t want to open their books to competitors via the blockchain. It also presents problems for regular users. Much has been made of companies using social networking profiles to make employment decisions and a transparent currency would make this even worse. Just as common wisdom suggests users should be empowered to choose appropriate privacy settings on social networks, users also need to tools to that limit the exposure of their private financial and purchasing history on Bitcoin’s blockchain.

Bitcoin Scalability Concerns

Regarding scalability, Bitcoin faces a problem that many protocol designers only dream of having: too many users want to use it. “On Scaling Decentralized Blockchains (A Position Paper)” explains the issue as follows:

“Today’s representative blockchain such as Bitcoin takes 10 min or longer to confirm transactions, achieves 7 transactions/sec maximum throughput. In comparison, a mainstream payment processor such as Visa credit card confirms a transaction within seconds, and processes 2000 transactions/sec on average, with a peak rate of 56,000 transactions/sec [11]. Clearly, a large gap exists between where Bitcoin is today, and the scalability of a mainstream payment processor.”

Applying Metcalfe’s law to Bitcoin suggests that the more people who use Bitcoin the more useful Bitcoin becomes. Thus scalability both in terms of volume (how many transactions can be confirmed per second) and velocity (how long a transaction takes to be confirmed) are significant limiters of the utility of Bitcoin.

How Does TumbleBit Work?

TumbleBit is implemented as a layer built on top of Bitcoin, and thus is fully compatible with today’s Bitcoin protocol. (This is analogous to how Tor is built as a layer on top of IP.) TumbleBit payments are sent via an intermediary called the Tumbler. In our paper, we describe how the core TumbleBit protocol can be run in in two modes. The first mode is a classic Bitcoin tumbler (also called a mixing service). In this post I will only address the second mode, where TumbleBit is used as an unlinkable payment hub.

A Bitcoin payment hub is a system that allows users to make off-blockchain transactions (via an intermediary, aka the payment hub) with the same level of security as on-blockchain transactions. Users join the payment hub by “opening a payment channel” that escrows bitcoins in an on-blockchain Bitcoin transaction. Next, users send payments to each other off-blockchain. These payments can be high volume and fast, because they are not subject to the time it takes to confirm transactions on Bitcoin’s blockchain. Finally, a user “closes its payment channel” via an on-blockchain transaction that reflects its new balance of bitcoins after all off-blockchain payments have been made.

In order to provide anonymity, TumbleBit requires all its users to open payment channels (in the “Escrow Phase”) and to close their payment channels (in the “Cash-Out Phase”)*. These two TumbleBit phases are relatively slow, because they require each user to post on-blockchain Bitcoin transaction that takes about 10 minutes to be confirmed. However, between these two phases in the “Payment Phase” where users send fast off-blockchain payments. TumbleBit payments can complete in seconds, thus scaling the velocity of Bitcoin payments. Perhaps more importantly, off-blockchain TumbleBit payments do not take up space on Bitcoin’s blockchain. This allows Bitcoin to process many off-blockchain transactions for only two on-blockchain transactions (i.e. the transactions which open and close the payment channel), scaling the maximum transaction volume which Bitcoin can handle.

Payment hubs have a long history in Bitcoin. TumbleBit’s main innovation is to provide unlinkability.

Unlinkability is defined as follows. Informally, unlinkability ensures that no one can tell which payer (Alice) paid which payee (Bob) during the payment phase of TumbleBit. More formally, the amount of bitcoin each user escrowed on the blockchain during the Escrow Phase is public. The amount of bitcoin cashed-out by each user during the “Cash-Out Phase” is also public. Let an interaction graph be any mapping of payments from the payers using TumbleBit (Alice1, …, AliceN) to payees using TumbleBit (Bob1, …, BobM). An interaction graph is compatible if it explains the transfer of funds from TumbleBit’s “Escrow Phase” to TumbleBit’s “Cash-Out Phase”. Unlinkability requires all compatible interaction graphs to be equally likely. TumbleBit payments are unlinkable because the TumbleBit protocol ensures that all compatible interaction graphs are equally likely. The anonymity provided by TumbleBit grows with the number of compatible interaction graphs.

To achieve unlinkability without compromising the security and safety of Bitcoin payments, TumbleBit must also ensure that the hub can’t steal bitcoins from the users or “print money” for itself. To do this, TumbleBit uses two interleaved protocols, the puzzle-promise-protocol and the RSA-puzzle-solver protocol. I give a brief overview of each protocol here. Our paper has the full details.

TumbleBit Walk-Through

TumbleBit replaces on-blockchain payments with off-blockchain puzzle solving, where Alice pays Bob by providing Bob with the solution to a puzzle. The puzzle is generated through interaction between Bob and the Tumbler (the puzzle-promise protocol) solved through an interaction between Alice and the Tumbler (the puzzle-solver protocol). Each time a puzzle is solved, 1 bitcoin is transferred from Alice to the Tumbler and each time Bob learns a solution 1 bitcoin is transferred from the Tumbler to Bob. A TumbleBit puzzle z is simply an RSA evaluation of its solution value ϵ under the RSA public key (pk, N) of the Tumbler, ie

z = ϵᵖᵏ mod N

In the puzzle-promise protocol, Bob is convinced that he has received an valid puzzle $z$, and that the solution to this puzzle will allow Bob to increase the value of his escrow by 1 bitcoin. The puzzle-solver protocol allows the Tumbler to take 1 Bitcoin from Alice’s escrow if and only if the hub reveals the solution to an RSA-puzzle of Alice’s choice. Putting these two protocols together, Alice can buy puzzle solutions from the Tumbler using the puzzle-solver protocol, which is a cryptographically-enforced fair exchange where 1 Bitcoin (from Alice) is exchanged for 1 puzzle solution (from the Tumbler). By purchasing a solution to Bob’s puzzle, Alice in essence pays 1 Bitcoin to Bob via the Tumbler.

Naturally, if Alice gives the Tumbler the exact same puzzle that Bob got from the Tumbler, the Tumbler will know Alice is paying Bob. To solve this problem, we borrow a technique called RSA blinding from Chaum’s original eCash paper ‘Blind Signatures for Untraceable Payments’. Bob blinds the puzzle (by multiplying it with a random value) before sending it to Alice. This way, no one other than Alice and Bob, not even the Tumbler can link Bob’s (unblinded) puzzle to (blinded) puzzle that Alice will pay the Tumbler to solve. This blinding is information theoretically secure. When Bob receives the solution to the blinded puzzle, he can unblind it and learn the solution to the original RSA puzzle which the Tumbler issued to him.

This allows Alice to pay Bob by paying the Tumbler for a solution to a blinded RSA puzzle without revealing to the Tumbler which puzzle is being solved. All the Tumbler observes is Alice buying solutions to random puzzles that the Tumbler never issued. Thus, the Tumbler can not link the solution to any puzzle to an issued puzzle.

The Future of the TumbleBit Project

TumbleBit is a rapidly evolving project. We are currently developing our proof of concept implementation into production ready software, adding increased functionality into our core protocols and exploring new applications.

A major milestone for our protocol was using our proof of concept TumbleBit implementation (available on github) to perform a test of TumbleBit protocol on Bitcoin’s blockchain tumbling 800 Bitcoin addresses to 800 new Bitcoin addresses. Having demonstrated that TumbleBit works at scale on today’s Bitcoin, our next goal is to develop TumbleBit into software the average Bitcoin user can use to protect their privacy when paying with Bitcoin (see our software roadmap on github).

We are also working to improve our protocols and find new uses for them. In the current TumbleBit protocol, all payments must be of the same domination. If this domination is set to 0.01 Bitcoin, and Alice wants to pay Bob 0.05 she needs to make five payments. At the moment we are exploring extensions to our protocols to allow for TumbleBit payments of arbitrary denominations while still providing unlinkability. We are also exploring other applications for TumbleBit, like increasing the privacy of the Lightning Network or performing unlinkable cross-chain trading.

* TumbleBit is currently a unidirectional payment hub: each payment channel can either send funds or receive funds. Users who wish to do both must open two distinct TumbleBit payment channels.