Disincentivizing Double-Spending whitepaper

##         Disincentivizing Double-Spending by Making it Unprofitable         ##
#####                             Erich  Erstu                             #####
######                       [Coingaming Group][17]                       ######
######                             July, 2017                             ######
###                                                                          ###
--------------------------------------------------------------------------------
###                                                                          ###
###                                 Abstract                                 ###

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.



### Introduction                                                             ###

Accepting unconfirmed Bitcoin payments has become a common habit in the Bitcoin
industry. Even though Satoshi Nakamoto solved the double-spending problem for
confirmed TXs[^1], unconfirmed TXs could still be easily reversed[^3].

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 CPFP[^2] 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.



### Problem Definition                                                       ###

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-miners[^4].

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 TXs[^3],
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 rejected[^8]. Turns
out that in practice such a system does not work as well as its creators might
have wished[^3], 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.info[^6]. 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 detection[^5].
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-Fee[^7] (RBF) would no longer be justified and could
thus be removed.



### Solution Details                                                         ###

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 Thinblocks[^9] technology developed by the Bitcoin
Unlimited team.


#### Relaying Double-Spending Transactions                                  ####

Even though double-spend TXs are already relayed by the Bitcoin XT[^5] 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 infamous[^11]
Bitcoin Core development team has indirectly endorsed double-spending by adding
the controversial opt-in RBF[^7] 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 relayed[^10].

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 default[^12]*). 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 Destruction[^13].


#### 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 acceleration[^15].

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 network[^7].
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 decide[^14].

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 debt[^16] 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.



### Business Benefits                                                        ###

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.



### Summary                                                                  ###

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.



### References                                                               ###

[^1]: Satoshi Nakamoto, [Bitcoin: A Peer-to-Peer Electronic Cash System][1], 2008

[^2]: Bitcoin Core 0.13.0, [More intelligent transaction selection for mining][2], 2016

[^3]: Mike Hearn, [Double spending in Bitcoin][3], 2015

[^4]: Glass Hunt, [Double Spend Bitcoin][4]

[^5]: Bitcoin XT, [Notable features in XT: Double spend relaying][5]

[^6]: Blockchain.info, [Double Spends][6]

[^7]: Bitcoin Core 0.12.0, [Opt-in RBF FAQ][7], 2016

[^8]: Bitcoin Classic, [Double Spend Proofs][8]

[^9]: Peter Tschipper, [BUIP010: Xtreme Thinblocks][9], 2016

[^10]: David A. Harding, Peter Todd [Opt-in Full Replace-by-Fee Signaling][10], 2015

[^11]: Joël Valenzuela [Secret Bitcoin Troll Army Pushes for SegWit Adoption: Emin Gun Sirer][11], 2017

[^12]: Bitcoin Core 0.12.0, [Memory pool limiting][12], 2016

[^13]: Nuclear Age Peace Foundation, [Mutual Assured Destruction][13], 2017

[^14]: John Blocke, [A (brief and incomplete) history of censorship in /r/Bitcoin][14], 2016

[^15]: nopara73, [A Practical Guide To Accidental Low Fee Transactions][15], 2017

[^16]: Bitcoin Classic, [How do SegWit and FlexTrans compare?][16], 2017

[1]: https://bitcoin.com/bitcoin.pdf
[2]: https://bitcoincore.org/en/2016/08/23/release-0.13.0/#more-intelligent-transaction-selection-for-mining
[3]: https://medium.com/@octskyward/double-spending-in-bitcoin-be0f1d1e8008
[4]: https://www.glasshunt.co/exploits/bitcoin-double-spend/
[5]: https://bitcoinxt.software/patches.html
[6]: https://blockchain.info/double-spends
[7]: https://bitcoincore.org/en/faq/optin_rbf/
[8]: https://bitcoinclassic.com/devel/Double%20Spend%20Proofs.html
[9]: https://bitco.in/forum/threads/buip010-passed-xtreme-thinblocks.774/
[10]: https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki
[11]: https://cointelegraph.com/news/secret-bitcoin-troll-army-pushes-for-segwit-adoption-emin-gun-sirer
[12]: https://bitcoin.org/en/release/v0.12.0#memory-pool-limiting
[13]: http://www.nuclearfiles.org/menu/key-issues/nuclear-weapons/history/cold-war/strategy/strategy-mutual-assured-destruction.htm
[14]: https://medium.com/@johnblocke/a-brief-and-incomplete-history-of-censorship-in-r-bitcoin-c85a290fe43
[15]: https://hackernoon.com/holy-cow-i-sent-a-bitcoin-transaction-with-too-low-fees-are-my-coins-lost-forever-7a865e2e45ba
[16]: https://bitcoinclassic.com/devel/FlexTrans-vs-SegWit.html
[17]: http://www.coingaming.io/
i)۾}yi@Author's tip jar: 1Erich1YUdkUAp9ynf4Rfw2ug8nBtuUmMu