Improving Bitcoin Reliability through Child Pays for Parent

At Coinbase we strive to be the most trusted and easiest to use cryptocurrency company in the world. As part of being the easiest to use, one of our goals is to provide a great user experience for customers who are sending and receiving cryptocurrency such as bitcoin. Sending cryptocurrency today can be difficult; transaction fees are volatile and unpredictable, which can result in significant swings in the amount of time it takes for a transaction to confirm. As a result of this, we’ve had many days here at Coinbase where some users’ transactions would get stuck due to fee rate spikes and general Bitcoin network congestion (which peaked in December 2017). First and foremost, this gives our users a frustrating experience because it takes longer than expected for their transactions to arrive. Second, it means that engineers at Coinbase are getting paged frequently to investigate a situation that is mostly out of their control. To address these challenges, we leaned on a well-known procedure which uses economic incentives enabled by the Bitcoin protocol for improving confirmation time of transactions: Child Pays for Parent (CPFP), and we’ve implemented this at Coinbase scale, sometimes using it to rescue thousands of transactions in a single day.

How it Works: Bitcoin Fees

When a customer wants to send some bitcoin to another address on the network, there are two major factors that we try to balance:

1. The transaction fee, or how much the customer pays to have their transaction included in a block, and

2. The speed at which that transaction gets included in a block.

Unlike a credit card processor that generally specifies fees as a percentage of a charge, Bitcoin operates with a fee market. This is somewhat analogous to a pay-as-bid auction, which is structured as follows: potential buyers will submit bids at different prices, and the auctioneer will select the highest bidders as the winners. Similarly, users select a transaction fee when sending a transaction to the network, and miners will select the set of transactions with the highest fees to include in a block. Typically, a user will decide how long they are willing to wait for their transaction to get included in a block, and will either ask a node or some third-party software for an appropriate fee at the time the fee estimate request is made. Between the time this transaction is broadcast and the next block is mined, there are likely to be many other people also broadcasting transactions. If they are also all trying to get their transaction in the next couple of blocks, the required fee rate will increase with each transaction. By the time this block is mined, our estimate may be too low relative to all available transactions for miners to select it.Figure 1. Historic Daily Average Transaction Fees in Satoshis per Byte (source: https://bitcoinfees.info/)Figure 2. Average Recommended 2-Block Transaction Fees in Satoshis per Byte for September 18–25 2018

The Problem

To illustrate this fact, let’s look at an example. Consider two Coinbase customers, Alice and Bob, both of whom would like to send some bitcoin to pay for a transaction on their way to work in the morning. Alice submits her transaction at a time when estimated fees are 5 satoshis/byte, a relatively low fee in today’s market. Seconds later, the network suddenly becomes very busy, and thousands of transactions appear in the mempool. Bob then submits his transaction with a fee of 25 satoshis/byte, where the fee is much higher than Alice’s because of the network congestion. Seconds later a block is mined; Bob’s transaction is included because of its high fee, but Alice’s remains pending. The congestion continues, and transactions are submitted with ever-growing fees. Alice’s transaction is now “stuck.” The funds won’t arrive at their destination, and she therefore can’t do anything with the funds, until the flood recedes and the fee rate drops.

A Solution

So, what can we do about Alice’s transaction? Is it stuck indefinitely, or can we help to incentivize miners to confirm her transaction? It turns out we can help Alice in this situation using a strategy that relies on economic incentives called Child Pays for Parent, or CPFP.Before explaining CPFP, let’s first briefly look at how Bitcoin transactions are structured. Simplified, a Bitcoin transaction is nothing more than a series of inputs and outputs, where inputs represent some value (in bitcoin) that is being “spent” by the sender. When a recipient wants to then spend the bitcoin that they received, one or more of the outputs that they control will become an input to a new transaction. This new transaction is then a “child” of the previous “parent” transaction. Additionally, a typical Bitcoin transaction includes what’s known as a change output. This change output is generally sent back to the original sender so that they can use it in a future transaction. This concept is no different than if you were to pay for a $5 coffee with a $10 bill and receive $5 in change from the cashier. When you are spending inputs with a fixed amount (in bitcoin or in dollars), there is generally change that you collect from the transaction. This change output is what we will utilize to enable CPFP.Figure 3. Example Diagram showing Parent and Child Transactions with Change OutputsNow that we understand what a child and a parent transaction are, let’s look at how CPFP works. Remember, miners always choose which transactions they want to include in a block based on relative rewards. The Bitcoin protocol does not allow for a child transaction to be included in a block before its parent transactions have been added — it must be included in either the same or a later block because later transactions depend on earlier ones.Building on that fact, whenever there are dependent transactions pending at the same time (parents and children), Bitcoin mining software will actually look at those transactions as a group and compute their corresponding fee rate over the entire set, rather than individually. This makes sense for miners to do so, since those transactions are really only valid when confirmed together. Since miners compute the fee rate over this group of dependent transactions, we can submit a child transaction (spending change outputs that we control) that has a higher fee rate than its parent(s), thus boosting the overall fee rate of the group. This is exactly how CPFP works. Essentially we are making a more profitable transaction available to miners, but the structure of this transaction requires the miners to also pick up some less profitable transactions. To take advantage of this and give our customers a better experience, we built a feature that automates this process of bidding up a stuck transaction.

How We Are Using It

Over the past few months, we’ve rolled out this feature in an automated fashion to all customers who are sending bitcoin on our platform. If a customer’s transaction happens to be stuck pending for at least 4 blocks, we’ll broadcast and pay for a child transaction at a sufficient fee rate in order to rescue the parent transaction (we actually batch these so that we can rescue multiple parents with one child). This is done without any interaction from the end user, and we’ve seen really positive results thus far with its use. Over the past few months, we have saved thousands of user transactions that our customers would have otherwise not seen for many hours. We love making our customers happy, and are excited that this feature has enabled us to bring more consistent reliability to their bitcoin transactions while ensuring that we are being good participants of the network.

The CPFP feature is a great example of our daily work on crypto technologies as well as the interesting challenges of complex distributed systems. If you enjoy working in a fun, high energy environment and want to work on scaling challenges like this one, then apply here or checkout all open positions. We’d love to hear from you.Unless otherwise indicated, all images and diagrams provided herein are by Coinbase.