This whitepaper was originally published on the Bitcoin block chain.
A significantly reduced likelihood of double-spending attacks on 0-confirmation payments would open a whole new realm of possibilities for Bitcoin businesses. Double-Spend Proofs and Payment Channels provide part of the solution but both of them require complex new functionality to be built on top of the Bitcoin protocol. We propose a fee market solution to the double-spending problem using miner greed to impair the economic profits of the adversary. Miners are driven to increase their revenue by preferring to confirm the subset of all unconfirmed transactions (TXs) that pays the most in fees. This unwritten rule can be used to detect and circumvent competing TXs. As long as miners remain greedy, we can always outbid a double-spending TX by spawning a Child-Pays-for-Parent (CPFP) TX with a higher fee. The adversary could respond with the same but that would lead to the point where the whole TX contains only fees for the miners. Conveniently, such an anti-double-spend defense mechanism does not require any change to the Bitcoin's consensus protocol and miners would be happy to get those extra fees.
Accepting unconfirmed Bitcoin payments has become a common habit in the Bitcoin industry. Even though Satoshi Nakamoto solved the double-spending problem for confirmed TXs1, unconfirmed TXs could still be easily reversed2.
In sectors where customer satisfaction is of utmost importance or if occasional double-spending does not pose an existential threat to the business it is often reasonable to provide service without waiting for the first confirmation of the Bitcoin network. The businesses that deliver service for 0-confirmation TXs seek to minimize their losses in case of double-spend fraud. Preemptive measures such as requiring the customer to provide a competitive fee for the payment tackles double-spending rather well. However, when the adversary outbids the fee of the initial payment in their double-spending TX the attack often succeeds. A certain percentage of fraud has been accepted as unavoidable.
What is needed is a mechanism for damage-control when a double-spend has already been broadcast to the Bitcoin network and is now waiting for a miner to include it in the next block. In this paper, we propose a solution to the double-spend problem using a CPFP3 TX to outbid the fee of a competing TX possibly until all funds of the initial TX have been spent on fees. Therefore, the adversary loses the economic incentive to double-spend in the first place. This mechanism is reliable as long as the adversary is not a miner and miners in general remain greedy for TX fees.
In the next section we will examine more closely the problems that arise when accepting 0-confirmation payments. We then describe the solution at the higher level to explain the concept without too many industrial details. For the technically inclined readers we later give the technical details. Finally, we iterate over the potential business benefits of the given solution and conclude the matter with a short summary.
Whenever a business accepts 0-confirmation payments and immediately provides the customer with a product or service it creates incentive for malicious actors to exploit the fact that unconfirmed TXs are not final. In fact, unconfirmed TXs can easily be reversed even by non-miners4.
Online casinos that accept Bitcoin payments are perhaps the most popular targets for double-spenders because in the gambling business the competition from other casinos forces everyone to accept unconfirmed deposit TXs. After all, the player goes to the casino that provides the best user experience. If a malicious user wins they will not launch a double-spend attack so they could safely withdraw their funds. However, if the customer loses before the initial TX gets the first confirmation then they execute the double-spending attack in hope of reversing their deposit TX.
In online video games where there are in-game purchases it is also expected by the players that their payments are accepted immediately and that they receive their virtual goods or services in real time. In the context of such video games it makes even more sense to accept 0-confirmation payments because double-spends could not cause significant economic losses to the business. In the worst-case scenario the double-spender would just annoy honest players. However, since the current majority of nodes deliberately refuse to relay double-spending TXs2, the service provider would most likely learn about the attack when most of the damage has already been done. If it was not the case then the malicious player could be banned from the game immediately after they launched the attack.
Live video streaming services are also a good use case for accepting unconfirmed Bitcoin payments due to the fact that for the service provider the resource that can be stolen is merely bandwidth. Such a business will most likely not go bankrupt because of a couple of streamers who refuse to pay. However, they would very much like to cut the scammer's video stream immediately after discovering the double-spend TX.
These were just a couple of examples where accepting 0-confirmation payments has become the norm. Those businesses are currently forced to handle double-spending attacks as an inevitable loss. In the next sections we describe what businesses can do to deter and even penalize double-spending.
High Level Solution
The currently dominant 0-confirmation double-spending prevention mechanism is to only accept the first-seen TX as the valid one. Should another TX later arrive, conflicting with an existing TX, then the newcomer is simply rejected5. Turns out that in practice such a system does not work as well as its creators might have wished2, so naturally people have started to seek for other more potent ways for risk mitigation.
The first and most obvious starting point for any business that wishes to deter double-spending of unconfirmed payments is to detect any such attempts as early as possible. This allows the business to stop providing service to the bad actor immediately and therefore it helps to minimize losses.
One way to detect double-spend attacks is to rely on a third party service such as the one provided by blockchain.info6. It is no way a recommended solution but it illustrates the fact that it can be done and that double-spends have indeed become a norm on the Bitcoin network.
The other more general approach is to choose the right kind of Bitcoin software. For example, Bitcoin XT has a built-in mechanism for double-spend detection7. While in some cases the early detection of fraud is already enough to discourage double-spending, there is no reason to stop here. Turns out that it is possible to ruin the double-spend for the adversary as long as the competing TX remains unconfirmed.
The authors of this work believe that since double-spending of unconfirmed TXs cannot be effectively prevented, it should be embraced and taken advantage of. In the next section we explain how natural miner greed can be utilized for the purpose of defending a payment after a double-spend has appeared on the network. What is more, we reveal that by embracing double-spending the controversial feature known as Replace-By-Fee8 (RBF) would no longer be justified and could thus be removed.
While the concept of outbidding competing TXs by increasing the fee per byte of the defending TX is rather simple, it does come with a couple of prerequisites. Firstly, the miners are ought to optimize their TX selection algorithm for the highest possible revenue. Secondly, network nodes should relay double-spending TXs almost as if they were normal TXs.
In the following subsections we briefly discuss the technical essentials of the named prerequisites. In the end, we present the proposed solution to the double- spending problem. It will be discussed from the engineering point of view but for the less-technical reader we also provide the philosophical justification of the given approach.
Greedy Transaction Prioritization
We know that most miners prefer to confirm the set of TXs that pays the greatest fee per byte. We can refer to such behavior as healthy greed and we can rely on it to predict which set of TXs will most likely get confirmed in the next block. Finding such a set of TXs can be viewed as a Traveling Salesman Problem (TSP). The miner seeks to find a subset of all unconfirmed TXs that would not exceed a certain size (currently 1 MB) while paying as much in fees as possible.
If there was not for CPFP TXs in the set of all unconfirmed TXs then sorting the set of unconfirmed TXs descendingly by fee per byte would be enough to predict which TXs will most likely be confirmed in the next block. However, CPFP TXs cause such simplistic sorting to become ineffective in cases where unconfirmed TX chains begin with many low-fee TXs but end with a high-fee TX.
Although the process of prioritizing TXs in such a way can be programmatically challenging similarly to the TSP, we know most certainly that it can be done. What is more, the results would remain mostly uniform across all nodes which aligns well with the Xtreme Thinblocks9 technology developed by the Bitcoin Unlimited team.
Relaying Double-Spending Transactions
Even though double-spend TXs are already relayed by the Bitcoin XT7 aspect of the Bitcoin protocol, there is a growing tendency for other implementations to also add support for relaying double-spends. Such a tendency is mainly driven by the market demand because more and more businesses rely on 0-confirmation TXs which evidently exposes them to double-spending.
The idea to ban double-spends is slowly losing relevancy. Even the infamous10 Bitcoin Core development team has indirectly endorsed double-spending by adding the controversial opt-in RBF8 kludge to their particular implementation of the Bitcoin node. In that case a special subset of double-spending TXs is given the privilege to be relayed by the Bitcoin Core nodes. Namely, only the double- spending TXs that pay a higher fee than their previous version, which do not contain any new unconfirmed inputs and comply to several other centrally planned constraints are relayed11.
One of the caveats to relaying double-spending TXs is the fact that it could expose the node to various forms of Denial-of-Service (DoS) attacks. To specify, the adversary could flood the network with a large number of double-spending TXs where each of them includes a fee different from all the others. If the lowest fee in the set of such malicious double-spending TXs is still higher than the highest fee in the set of regular unconfirmed TXs then the adversary would have effectively kicked out all the regular TXs from the mempool of every node.
While this might sound like an argument against relaying double-spending TXs, it is really more of an excuse of an incompetent software architect than a valid counter-argument. All popular full node implementations have their mempools limited to a specific capacity (typically 300 MiB by default12). They are already prepared for dealing with a massive flood of unconfirmed TXs. Obviously, the existing anti-flooding mechanism could be amended to deal with the excessive propagation of double-spending TXs.
Since it makes a lot of sense to treat bandwidth as a resource just like memory, full nodes should limit the TX throughput of their immediate neighbors on the network. Should any of the neighbors exceed the limit they could be dealt with respectively. The bottom line is that from the free market's standpoint relaying double-spending TXs is an intrinsic trait. A good analogy in this context is the fact that law does not prevent criminals from using firearms. In fact, stricter gun control gives the criminals an advantage in front of law-abiding citizens. Making double-spending available for everyone would also make the whole Bitcoin network more fair for everyone.
Outbidding Competing Transactions
The solution proposed in this paper implies that double-spending TXs are freely relayed on the Bitcoin network so that the victim could quickly learn about the competing TX and its details. If the competing TX has a greater fee per byte than the original TX then the receiver of the original TX could spawn a child TX that spends even more of its input funds on the TX fee than the malicious double-spend. As a result, whichever fork of the unconfirmed TX chain ultimately pays the greatest fee per byte would be confirmed.
If the adversary controls a significant portion of the global hashing power then obviously the described defense mechanism would be ineffective. However, in this paper we assume that the adversary does not control such resources because if they did then even 1-confirmation TXs would be unsafe to accept. The proposed solution is intended for cases where the transmitted amount of funds is vastly less than the effective block reward.
To minimize the risk of fraud even more, the payee could only provide goods or services for 0-confirmation payments that originate from already confirmed TXs. Long chains of unconfirmed TXs should be treated with care and not be accepted as payments because spawning a CPFP TX at the end of such a chain could fail due to implementation constraints of the full node software. For example, the graph diameter of an unconfirmed TX chain cannot exceed 25 in Bitcoin Core.
Although nothing stops the adversary from continuously increasing the fee of the double-spending TX, it would only lead to the point where the TX fee becomes so large that double-spending no longer pays off. The authors of this work believe that the threat of double-spending is significantly reduced if there is nothing to win from it. In a way it works out just like Mutual Assured Destruction13.
A Better Alternative to Replace-By-Fee
When the block size limit of 1 MB was met due to the increasing market demand for block space in 2016, TX fees started to rise dramatically. Since more TXs were being made than Bitcoin miners could confirm, the backlog of unconfirmed TXs had no hope of ever clearing out. As a result, people started to utilize various ways of TX confirmation acceleration14.
One of the ways to accelerate TX confirmation is to increase its fee. While CPFP method is useful for the TX receiver to accelerate its confirmation, the other less-popular way is to utilize RBF. The latter is a special kind of double-spend that is hard-coded to be relayed by the Bitcoin Core nodes. Economically it is more wasteful to spawn CPFP TXs than to double-spend in order to increase the TX fee. That is because a CPFP TX itself will consume block space and thus has to include a fee of its own whereas a RBF-style double-spend does not introduce any such overhead.
As we can see, there is economic incentive behind making it possible to replace TXs to speed up their confirmation time. Interestingly, long before the blocks actually got full Bitcoin Core incorporated RBF to provide a way for its users to increase the fee of a TX that has already been broadcast to the network8. Whether this hints for the intentional preparation for full blocks and high TX fees with the ulterior motive of forcing Bitcoin TXs into privately owned and centralized payment hubs is up to the reader to decide15.
In software engineering the architectural beauty of an application lies in its simplicity. If double-spending TXs were relayed by all nodes then the RBF kludge would not be necessary at all. The respective code could then be deleted from the codebase and thus a small part of the enormous technical debt16 Bitcoin currently has would be paid off.
Penalizing Antisocial Behavior
One might argue that sometimes the absence of economic incentive is not enough to demotivate a double-spender. This is correct. A malevolent customer might not care for the economic gain and could still engage in double-spending. Whether it is simply for fun or due to a personal grudge against the merchant, such an act is definitely possible.
Since the offender has already received service for the 0-confirmation payment, they most likely have nothing else to lose. Sure, the solution proposed in this paper would make it impossible for the adversary to reverse the payment but they might still initiate a double-spend attack to ruin the deal for the merchant.
Luckily, such an antisocial behavior can be made so costly for the offender that they will most likely not want to initiate a double-spending competition in the first place. The trick here for the merchant is to ask for a pledge in addition to the normal price of the product. Upon a successful transaction the pledge is returned to the customer but in case of a double-spend attack it will be used up in the process of outbidding the competing TXs.
Online casinos and currency exchanges could utilize this security pattern by allowing only a fraction of the 0-confirmation deposit to be immediately used up by the customer. Should that deposit later get double-spent the bad actor would lose much more than what they were able to use up in the context of the provided service. Naturally, the size of the pledge can be calibrated by each business individually to fit the needs of any risk profile.
It is fairly trivial to see that if double-spending of 0-confirmation TXs became economically unprofitable then more businesses could start accepting unconfirmed TXs as payments. This would naturally lead to greater profits for the businesses and smaller prices for the consumer. After all, it is the honest customers who are indirectly made responsible for compensating the revenue lost in fraud.
In this paper we proposed a novel approach to mitigating the risk of fraudulent 0-confirmation double-spending payments on the soft protocol level. We started with the technical prerequisites such as double-spend relaying and fee greedy TX prioritization. We then introduced the concept of outbidding competing TXs by increasing the fee of the original payment. The latter is possible only with the help of a Child-Pays-for-Parent TX. Since such a trick could be repeated until the whole payment is spent on TX fees, it is easy to see that economically there is nothing for the attacker to gain from double-spending. That said, we have effectively disincentivized fraudulent double-spending of 0-confirmation TXs.
Call to Action
Since there is no scientifically rigorous way to detect a fraudulent unconfirmed TX without knowing anything about the context of the TX all TXs should be viewed as equally valid and relayed respectively. Ultimately, it will be the miners who decide which one of the conflicting TXs gets included in the next block. Thus, all full nodes should view the set of unconfirmed TXs from the miner's point of view. The authors of this work urge the full node operators to start seeking for reasonable ways to relaying double-spending TXs. As for the Bitcoin miners, it is highly recommended to optimize the TX prioritization algorithm for the most profitable model possible.
Satoshi Nakamoto, [Bitcoin: A Peer-to-Peer Electronic Cash System], 2008 ↩
Bitcoin Core 0.13.0, [More intelligent transaction selection for mining], 2016 ↩
Glass Hunt, [Double Spend Bitcoin] ↩
Bitcoin Classic, [Double Spend Proofs] ↩
Blockchain.info, [Double Spends] ↩
Peter Tschipper, [BUIP010: Xtreme Thinblocks], 2016 ↩
Joël Valenzuela [Secret Bitcoin Troll Army Pushes for SegWit Adoption: Emin Gun Sirer], 2017 ↩
David A. Harding, Peter Todd [Opt-in Full Replace-by-Fee Signaling], 2015 ↩
Bitcoin Core 0.12.0, [Memory pool limiting], 2016 ↩
Nuclear Age Peace Foundation, [Mutual Assured Destruction], 2017 ↩
nopara73, [A Practical Guide To Accidental Low Fee Transactions], 2017 ↩
John Blocke, [A (brief and incomplete) history of censorship in /r/Bitcoin], 2016 ↩
Bitcoin Classic, [How do SegWit and FlexTrans compare?], 2017 ↩