Join and earn Bitcoin Cash for participation

Exploring Long Chains of Unconfirmed Transactions and Their Resistance to Double-spend Fraud

1 553
Avatar for PeterRizun
Written by
This user is who they claim to be.
We have manually verified this user via some other channel.
Proof
  55
2 months ago
Topics: Bitcoin Cash

1 Introduction

This article explores long chains of unconfirmed bitcoin transactions and investigates their resistance to double-spend fraud. First we show how to hit the 25-chained transaction limit using the Electron Cash wallet, and then we discuss why the limit hurts certain use cases. Thanks to BU's recent work improving the child-pays-for-parent algorithm, hundreds of nodes on the network today now support long mempool chains. We then connect an Electron Cash wallet to one of these nodes hosting an Electrum server, and attempt a double-spend attack against a simulated merchant, showcasing how BU's "intelligent forwarding" protects the merchant against double-spend fraud. We then explore other potential double-spend vulnerabilities before concluding that accepting deeply-chained unconfirmed transactions today using a default BU node is not significantly more risky than accepting lightly-chained unconfirmed transactions. Unfortunately, during our testing we discovered an attack that succeeds with a very high probability against all chained transactions that can be carried out with an off-the-shelf bitcoin wallet unless the merchant (or his payment provider) follows a fairly onerous procedure to protect himself.

In this article series, the term “bitcoin” refers to a system with the properties described by its inventor Satoshi Nakamoto in the white paper “Bitcoin: A Peer-to-Peer Electronic Cash System.”  We assume the reader has a technical understanding of bitcoin at the level of this paper. In particular, we assume he is familiar with the concepts of unconfirmed transactions, double-spends, and the structure of bitcoin transactions (i.e., transactions spend inputs and mint new outputs—there are no “accounts” that get debited or credited at the protocol level). We also assume the reader is familiar with the concept of the "mempool": the set of (unconfirmed) transactions that have been broadcast to the network but not yet confirmed in the blockchain.

2 What is the mempool chaining limit?

The reader can experience the mempool chaining limit for himself by downloading the Electron Cash SPV wallet (it takes only a minute or two to get a wallet up and running).  Starting with a new empty wallet, open the receive tab and send $1’s worth of BCH from your usual wallet to its receiving address (or some other small amount). After the payment is received, open the “Send” tab and paste the same receiving address into the “Pay to” field, then press the “Max” button to populate the “Amount” field, and finally, press the “Send” button.  Your wallet will create and broadcast a transaction that sends the unconfirmed output back into your wallet, after subtracting a small miners’ fee. 

Fig. 1. To create a chain of unconfirmed transactions with Electron Cash, continually send "Max" back to your own receiving address.

In the “History” tab, you should see the original unconfirmed transaction and a second transaction marked “Unconfirmed parent.”  The “Amount” for the second transaction is negative because the net result was that your balance decreased due to the miner’s fee required to send the transaction (185 satoshis in this case).  The second transaction spent the output of the original transaction that deposited $1 into your Electron Cash wallet, thereby creating an “unconfirmed chain” of length 2. If for some reason the parent transaction does not confirm (perhaps it was double-spent), then it would become impossible for the second transaction to confirm because the output consumed by the second transaction would no longer exist.

Fig. 2. This "History" tab in Electron Cash illustrates an unconfirmed transaction chain of length 2. The second transaction has an unconfirmed parent, as noted. If the parent transaction is double-spent, all child transactions become invalid.

You should be able to repeat this 23 more times to create a chain of 25 unconfirmed transactions.  However, if you try once more, you should encounter the following error:

Fig. 3. At the time of writing, many nodes on the BCH network reject transactions chained more than 25 deep. This is the error that Electron Cash gives when you attempt to spend the output of the 25th transaction in a mempool chain.

Congratulations, you’ve hit the mempool chaining limit!  

FRUSTRATION WARNING: Refer to Note [1] .

3 Why is the mempool chaining limit a problem?

Imagine that you received a $5 bill as change when you bought a train ticket and then you went to pay for a coffee but couldn’t physically remove the $5 bill from your wallet—it was stuck by some magical force!  After some arbitrary amount of time passed the $5 bill would start working again, but in the moment when you needed it it could not be spent. This is exactly the way BCH coins behave due to the mempool chaining limit.  When we imagine “cash” having this property, it seems ridiculous.

Fortunately, it is rare for most users to encounter the limit, since it is rare that the same output would be spent 25 times between new blocks.  But there are certain cases where the limit is a real problem:

One example is the “on-chain” gambling website Satoshi Dice.  Gamblers don’t need an account with Satoshi Dice—they send their bets directly to a BCH address corresponding to their game of choice, and their winnings are sent back to them with a second BCH transaction.  Like a slot machine player hammering on the lever, a Satoshi Dice gambler can easily make 25 bets between BCH blocks. If the player’s wallet has no other confirmed coins, then the gambler will have to wait for the next bitcoin block before he can continue playing.  And there goes his lucky streak!

Another example is the on-chain Twitter-alternative Memo.bch: posting a message requires making a transaction, limiting the amount of messages a Memo user can send between new blocks to 25 messages per confirmed output in his Memo wallet.  Imagine that you’ve thought up the perfect argument in a heated debate and now you can’t post your message until the next block comes in. Rate limiting sucks!

A third example is general wallet reliability. When the BitcoinVerde team was demonstrating an app built on top of BCH at a meeting in Dublin, Ohio, meeting attendees began experimenting with the wallets, passing tokens back and forth. However, they hit mempool chaining limit, at which point they could not longer make transactions, tempering enthusiasm for the concept. I have also heard reports from bitcoin advocates about hitting the mempool chaining limit at conferences and meet-ups while gifting small amounts of BCH to new users to get them started. Talk about a bad first impression for a new user when this new fancy money just stops working!

4 Is the mempool chaining limit necessary?

It isn’t.

The limit is an artefact that Bitcoin ABC inherited from Bitcoin Core due to Core’s full-block policy (specifically, there is an inefficiency in its child-pays-for-payment (CPFP) algorithm that necessitates a small limit).  For more information, see this post.

Bitcoin Unlimited developer Peter Tschipper optimized the CPFP algorithm used by ABC thereby making it hundreds of times faster and allowing it to operate quickly on mempool chains even thousands of transactions long (Fig. 4). The trade-off of the optimization was that at times, for example when the mempool is larger than the block size, it becomes possible that the transactions selected for a miner's block candidate may not be the identical to the set the would maximize fee revenue, possibly leaving a few pennies on the table. For more information, see this explanation.

Fig. 4. Processing time between Core/ABC CPFP and BU's improved algorithm versus chain length

In addition to this work, the O(n^2) complexity was removed from the code that removes transactions from the mempool after they are included in a block that won the PoW lottery (code), and the code that adds a transaction to a long chain in the mempool was optimized (code).

5 Can I send and accept deeply-chained transactions today?

Yes, you can!

Several nodes on the BCH network today support sending and receiving up to 500 chained transactions.  If you run a full node, you can join them by adding the following lines to your bitcoin.conf file and then restarting your node (these feature will be enabled by default in the upcoming 1.8 release of BU):

limitancestorcount=500
limitdescendantcount=500
limitancestorsize=2020
limitdescendantsize=2020
net.unconfChainResendAction=2
net.restrictInputs=true

If you don’t run a full node but use a SPV wallet such as Electron Cash, you need to manually connect your wallet to a node that supports longer chains in order to send or receive deeply-chained payments.  For example, the server bch.loping.net and the BU controlled electrs.bitcoinunlimited.info supports up to 500 chained transactions. Connect to the BU server by typing in the domain name and port number (50002) in the “Server” text box. (Note: if you send a deeply-chained transaction to a person or business whose wallet does not support long chains, they will not see the payment until after one or more blocks is confirmed.)

Fig. 5. At the time of writing, there are already a few servers that Electron Cash can connect to that support sending and receiving deeply-chained transactions.

In theory, this technique works with all SPV wallets.  In practice, the option to connect to a specific node needs to be exposed in the SPV wallet’s user interface.  

Fig. 6. With BRD wallet, there is no interface that allows the user to select a specific BCH node. Thus BRD will most likely connect by default to a node that does not support long mempool chains. Petitioning wallet makers to give users the ability to connect to specific nodes is important for decentralisation.

If you use a CoPay-style wallet (e.g., the Bitcoin.com wallet) you will need to wait until the server your wallet connects to upgrades to support longer mempool chains.

6 Long-chain block explorer

In addition to the many nodes and a few electrum servers that support long chains, Bitcoin Unlimited also maintains a block explorer that supports up to 500 chained transactions. This explorer will show unconfirmed transactions broadcast to the network that exceed the common network policy limit of 25 that do not show up on other block explorers.

https://explorer.bitcoinunlimited.info

7 Is it risky to accept deeply chained unconfirmed transactions?

First, let’s try to understand exactly what the concern is.  We learned in Section 2 how to create a chain of 25 unconfirmed transactions by repeatedly sending the same coin back into our own wallet.  We learned in Section 5 how to connect our Electron Cash wallet to a server that would allow us to send a 26th transaction on top of that chain.  Now here’s the worry: A fraudster could send a transaction chained 26 times to a coffee shop that accepts longer mempool chains. But the fraudster would know that many nodes on the network would not immediately learn about his payment because those nodes would reject transactions chained deeper than 25.  And so the fraudster could create a second conflicting (double-spent) transaction that sends the coin he used to pay for his coffee back into his own wallet instead. Because this double-spent transaction is also the 26th in the chain, it would be rejected by the same nodes that rejected the legitimate payment if broadcast immediately (it would trigger the error in Fig. 3). Instead, the fraudster must wait until the next block is found, and then broadcasts his fraudulent transaction.  Since it is only possible for one of the two transactions to be confirmed in the blockchain, the fraudster could theoretically succeed in taking back his payment. Free coffee! 

Fig. 7. A fraudster could take advantage of differences in mempool policy between nodes and attempt to take back a payment he made. As illustrated, a fraudster could attempt to pay a merchant with the 26th transaction in a mempool chain, wait for the next block to be found, and then try to quickly broadcasat a double-spend to the nodes that initially rejected the legitimate payment. Only one of the two transactions that spend the dark blue coin can be confirmed in the blockchain, so either the legitimate version of TX 26 will confirm or the fraudulent version will confirm.

8 Could a fraudster double-spend with Electron Cash?

Let’s find out!  We don’t want to actually defraud anyone, so instead of trying this on a real merchant, we’ll try it on a “simulated merchant.”  For this experiment, I’m using a spare Android phone I had lying around to simulate the merchant’s wallet, which I’ve connected to an Electron Cash server that supports long chains.  Here are the steps:

  • Create a chain of 25 unconfirmed transactions as per Section 2

  • Manually connect Electron Cash to a server that supports long chains

  • Pay for your “coffee” normally with your Electron Cash wallet (this creates the 26th transaction in the mempool chain)

  • Manually connect to an Electrum server that does not support long chains

  • Create a transaction that sends "Max" back to your own address (as per Section 2)

  • Wait until a new block is found and then press “Send.”

If you try this, you will succeed in sending the 26th transaction to the simulated merchant.  The balance in your Electron Cash wallet will fall, and the balance in the merchant’s wallet will rise. 

Fig. 8. If the merchant and fraudster both use wallets that support longer chains, the fraudster can setup for a double-spend attack by paying the merchant with the 26th transaction in an unconfirmed chain.

When you switch to a server that does not support long chains, your balance will be restored (it will appear as though you never paid the merchant).  However, the merchant’s balance will be unaffected (obviously). There are two competing future states of the network at this point: the first state where you paid the merchant, and the second state where you didn’t. 

Fig. 9. By switching back to a server that does not support long chains, the fraudster can restore his balance. He can now create a conflicting (double-spent) transaction that sends this balance back into his own wallet in an attempt to defraud the merchant and thus get his coffee for free.

In the attempts I made, I was never able to succeed in reversing the payment.  The payment to the simulated merchant would confirm every time. Double-spending a deeply chained transaction is at least not trivial.

9 Why does the double-spend fail?

The reason my double-spend attempts failed is because the network of BU nodes use Intelligent Forwarding (IF) to defend the network. The deeply-chained payment to the merchant still propagates across the network. In a very real sense, the legitimate TX exists in the "network wide mempool" just not in the individual mempools of the nodes that reject long chains. The window of opportunity for the fraudster begins the moment an ABC node accepts a new block (and thus becomes receptive to either the legitimate transaction or the double-spend). Each BU node with IF enabled blasts every ABC node that it is connected to the moment the BU nodes learns of a block. Since there are hundreds of BU nodes and each BU node is connected to several ABC nodes, the window of opportunity closes nearly instantly. The manual process we tried above has almost no chance of success.

Fig. 10. Deeply-chained transaction still propagate across the BCH network, although the ABC nodes initially reject them (they don't immediately turn green in the animation). Upon detecting a new block, the BU nodes blast the ABC nodes with the deeply chained transactions when they know the ABC nodes will accept them. For a fraudster to get his double-spend into the network and relayed to a miner, he has to race against a significant fraction of the entire network!

10 Attack #2: Tainting a regular coin with a long chain

There is also a more subtle risk where an attacker taints a regular (unchained coin) with a deeply-chained output, as shown in Fig. 11. He sends the tainted transaction to a merchant who accepts long chains. After receiving the goods or service, he then creates a second transaction that spends only the regular (unchained coin) back into his wallet. Because most miners today reject deeply-chained transactions, the second (fraudulent) transaction will likely be confirmed in the next block and the attack would succeed.

Fig. 11. A second double-spend attack involves tainting a transaction with a deeply-chained coin.

To avoid this vulnerability, Bitcoin Unlimited by default only accepts transactions chained more deeply than 25 if they spend only a single input. With this restriction, the transaction marked "legit tx" in Fig. 11 would be rejected by the BU node. (There is no worry that an attacker could taint a parent transaction to bypass the restricted inputs check because without the parent transaction the receiving node will not consider the child transaction as valid.)

This safety feature can be disabled by setting the restrictInputs flag to false:

net.restrictInputs=false

11 What about the miners?

Miners can safely mine long chains with BU today provided they do not disable the input restrictions. Without input restrictions for deeply chained transactions, miners mining long chains might unknowingly facilitate double-spend attacks.

12 More advanced attacks

When we began the long-chain testing, our intention was to quantify the double-spend risk of deeply-chained unconfirmed transactions compared to unconfirmed transactions chained less than 25 deep. To do this, we also carried out more advanced versions of the race attack described in Section 8. We had fast Python scripts running on Sybil nodes across the globe (including China) that would blast out the double-spend as soon as the new block was found and the miners and other nodes would accept it.

The results showed that the attacker needed either a very large Sybil network (i.e., more Sybil nodes than the total number of BU nodes with Intelligent Forwarding), or more strategically positioned nodes (e.g., nodes closer to the miners). With only a single computer with no special attention paid to its connection to the miners, the attack would fail.

It was during this testing that we discovered a way for an attacker to attempt to double-spend chained transactions less than 25 deep, succeed with a high probability and maintain plausible deniability, using only an off-the-shelf wallet such as Electron Cash. The merchant must follow a fairly onerous procedure to ensure he remains directly connected to the entire BCH hash power, including profit-switching miners, to protect himself. We speculate few merchants or payment providers today are doing this.

13 Summary

Today there is already a significant fraction of the network that supports very long chains of mempool transactions (typically 500), including a block explorer and Electrum servers that users can connect wallets like Electron Cash to. Managing long chains is no longer taxing on a miner using child-pays-for-parent thanks to the improvements in the CPFP algorithm that BU made. BU nodes that support long chains use Intelligent forwarding and input restrictions to make accepting deeply-chained unconfirmed transactions nearly as secure as lightly-chained transactions. A merchant can use a BU node and accept deeply-chained transactions without significant risk of double-spend fraud compared to unconfirmed transactions chained less than 25-deep. Our testing however highlighted that unconfirmed chained transactions in general (whether longer or shorter than 25) can be double-spent with high success rates by a determined attacker. Merchants must follow a fairly onerous procedure to protect themselves from such attacks.

Network support for very long chains of unconfirmed transactions makes BCH more cash-like, solving existing problems and creating new use cases.


Notes

[1] If a block is found while you are creating the mempool chain, then you will need to do this more than 23 times in order to create a chain of 25 unconfirmed transactions.  BCH’s difficulty adjustment algorithm is currently being gamed by miners resulting in bursts of blocks in quick succession, followed by hours with no blocks. If you are attempting this during a block burst, then manually chaining 25 transactions will be frustrating as each new block will reset the chaining length back to zero.  Additionally, I encountered problems where certain Electrum servers would not register transactions even for < 25 chaining limit and I needed to manually change servers in EC settings. There also seems to be a synchronicity bug in EC where pressing “Max” will occasionally populate a stale value resulting in an error.







3
$ 2.97
$ 1.00 from @Mel
$ 0.50 from @Read.Cash
$ 0.50 from @unitedstatian
+ 6
Avatar for PeterRizun
Written by
This user is who they claim to be.
We have manually verified this user via some other channel.
Proof
  55
2 months ago
Topics: Bitcoin Cash
Enjoyed this article?  Earn Bitcoin Cash by sharing it! Explain
...and you will also help the author collect more tips.

Comments

finally understand what the mempool fuss is all about .. thanks for the detailed writeup .. glad to hear that 500 chained txs is already possible with BU 👏👍

$ 0.00
2 weeks ago
About us Rules What is Bitcoin Cash? Roadmap Affiliate program Get sponsored Self-host
hello@read.cash (PGP key) Reddit