Unbounded Transaction Chains with CPFP

in BCH Unlimited

(by Peter Tschipper)

Summary:

Unlimited length transaction chains are something that has been wanted for a long time in BCH for many reasons. Exchanges want to pay out of one wallet without having to swap it frequently, some apps need to make frequent interest payments while others just want to share new SLP tokens with many people in a short period of time. Social media sites like memo.cash or gambling sites like Satoshi Dice also rely on the ability to create long chains.  If these users cannot create long chains when the need arises then their ability to service their clients gets disrupted. However the difficulty behind allowing them has largely been a result of quadratic behavior of various processes when Child-Pays-For-Parent (CPFP - Child Pays for Parent) functionality was introduced into the software some time ago. While it would be relatively easy to simply remove CPFP and thus allow unlimited transaction chains, we can, with a few modifications and simplifications, have both co-exist without negatively affecting performance and in fact, in the area of mining, the performance has been improved.

The areas in the node software where quadratic issues exist are mining, post block processing and transaction memory pool (or mempool) admission.  Last year both the mining and post block processing work was merged and more recently in Dec 2020 the final mempool admission changes were introduced in version 1.9.0.0 (MR: 1903, 2020, 2032).  Starting in v1.9.1.0 of BCH Unlimited the final mempool admission work was merged (MR: 2341, 2342, 2344) and therefore unbounded chains will be possible and as we will show can seamlessly work with other implementations.

Implementation:

 There are several areas in the code that exhibit quadratic behavior in regards to long chains:  Mining, Post Block processing and Mempool Admission. The following sections describe the implementation of code changes in those three areas which were addressed in order to allow for unlimited transaction chains.

Mempool Admission:

In order to remove the quadratic behavior of mempool admission in regards to long chains we have two issues to consider. One is the need to constantly update descendant state for the entire chain as new transactions arrive. The other is to correctly parse through the ancestor chain where there is more than one parent for the transaction.

The first issue is resolved in BCH Unlimited by removing the need for tracking descendant state altogether. When it is realized that the only need for tracking descendant state is to support the complexity of trimming the mempool when it is full, and keeping the maximum fee transactions  then the problem amounts to implementing, if possible, a different mechanism for mempool trimming. Fortunately there is a better way of trimming the mempool which was introduced long ago in Bitcoin XT, which is to trim transactions randomly.  It is more efficient, requires much less code and keeps a better cross section of transactions on the network. As Andrew Stone writes, “…Note also that a strategy to fill the mempool and then execute a doublespend of randomly evicted transactions is unlikely to succeed due to the high probability that evicted transactions will be held in some node somewhere in the network -- and that node will issue a doublespend alert. One can see how a pseudo-random eviction strategy is more likely to detect doublespends in the network-as-a-whole than any algorithm that is followed by all nodes, or small set of algorithms one for each major full node.”

Therefore, we can see that random eviction is in general a good strategy for Bitcoin Cash, and when this is done we no longer need descendant state tracking and so solves the quadratic problem that it brings to mempool admission and post block processing.

The remaining quadratic issue then for mempool admission is what to do with transactions that have multiple parents? Only transactions with multiple parents require us to parse the entire ancestor chain which then introduces the quadratic behavior.  This problem has been solved by the removal of descendant state tracking and also by marking any transactions in the chain longer than 500 as “dirty”.  Dirty transactions are still fully mineable and searchable through RPC commands, however, dirty transactions may or may not have correct ancestor state data, but in actuality, only transactions with more than one parent and where both parents belong to the same chain will have incorrect data. Furthermore, these types of transactions which are part of a “diamond” pattern and are not common (0.1%). Therefore, most, in not all, transactions that are marked dirty will have the correct data without the need for traversing the entire ancestor tree for each transaction.

Note: The 500 transaction cut-off for dirty vs. non-dirty is rather arbitrary and is just a carryover from prior versions where transaction chains were limited to just 500. We could set the value higher or lower, however 500 seems a reasonable trade-off.

Mining:

There are two minor trade-offs required to make long chain mining possible. Those are the use of “dirty” transaction chains and also the concept of grouping transactions by ancestor state.

As for dirty chain data, typical dirty chains will have the correct data because diamond transaction graphs are relatively rare, therefore, even chains marked dirty will typically have the correct ancestor state data. It is only the diamonds (where a transaction has two or more outputs then converge one or more of them into a single input) that are left dirty because of their excessive need to parse through the entire transaction chain to find correct ancestor values, but again, these are quite rare. In a recent mainnet survey it was found that only 0.1% of transactions have a diamond pattern in their ancestor chain. This means that in a typical 1MB block, where there are roughly 3000 transactions, you would typically have only 3 that had “dirty” and slightly inflated numbers for their ancestor states.

The other trade-off concerns considering a group of ancestors as a single transaction. We can call these transactions, Ancestor Grouped Transactions (AGT). This approach to grouping allows us to process packages orders of magnitude faster than other methods of package mining since we no longer have to continuously update the descendant state as we mine part of an unconfirmed chain.

However, there is a theoretical limitation in this approach which could happen when a block is almost full. We could for instance end up including a lower fee transaction as part of an ancestor group when in fact it would be better, in terms of fees, to include some other single transaction. This would result in slightly less fees (perhaps a few hundred satoshis) rewarded to the miner. However, this situation is not likely to be seen for two reasons. One, long unconfirmed chains are typically having transactions with all the same fees and two, the typical child pays for parent scenario has only two transactions with the child having the higher fee. And neither of these two types of packages could cause any loss of fees with this mining algorithm, when the block is nearly full.

The mining algorithm is surprisingly simple and entails parsing through the mempool’s “ancestor_score” index and adding the AGT's into the new block. There is however a pathological case which has to be accounted for where a child transaction has less fees per KB than its parent which causes child transactions to show up later as we parse through the ancestor index. In this case we then have to recalculate the ancestor sigops and package size which can be time consuming, given we have to parse through the ancestor tree each time. However we get around that by shortcutting the process by parsing through only the portion of the tree that is currently not in the block. This shortcutting happens in “_CalculateMempoolAncestors()” where we pass in the “inBlock” data structure containing the already added transactions.

Post Block Processing:

The old method of doing post block processing which entails the removal of transactions that were in the block from the mempool was extremely inefficient. How it worked was that for every transaction that we removed from the mempool the entire transaction chain state was updated, even if all the transactions in the chain were to be removed. The new method essentially uses a concept of transaction chain tips whereby we first remove all transactions from the mempool that were in the block and thus find the first transaction in any remaining transaction chain. This is what we refer to as the transaction chain tip. Then we parse through any remainder of the chain and update all ancestor states in one step.

Interoperability with other implementations:

In order for Unbounded Chains in BCH Unlimited to work on the main network with nodes that have only a 50 transaction chain limit, or some other node configuration, we need to first address issues concerning possible double spend attacks as well as transaction propagation.

 Transaction propagation and automatic transaction forwarding:

A problem arises when we have a BCH Unlimited node which allows any number of chained transactions, but other nodes on the network only allow 50.  If we didn’t do anything at all to address the disparity then transactions admitted to the BCH Unlimited node would trigger a send of INV messages to all other incompatible nodes which would then request transactions beyond their 50 chain capacity. Upon receiving those transactions, any node that enforced the 50 chained limit, would then reject them and “NEVER” ask for them again, essentially preventing the propagation and eventual mining of those portions of the chain beyond the 50 limit.  Clearly this wouldn’t work in a world where miners are not mining with BCH Unlimited peers, so what is needed then is some intelligence build it to recognize which peers should have all transactions forwarded to them and which peers should only receive 50; furthermore, we need to also trigger the send after the next block is found so the next batch of 50 transactions can propagate.  The solution to this problem is called Intelligent transaction forwarding which was created by Andrew Stone and simply propagates the next 50 transactions in a chain after the next block is processed. It has been deployed and is active in the BCH Unlimited client and is an essential tool for making Unbound Chains compatible with other node implementations.

Double spending issues and restriction of inputs:

Another issue arises when we have a disparity between two peers. For example, one BCHN peer has a 50 length transaction chain while the other, a BCH Unlimited peer, can have 51 or more.  What could happen here in regards to double spending is that someone could spend the second input of the 51’st transaction and this transaction would theoretically propagate through the BU network of peers but not the BCHN. Therefore the input could also be spent on the BCHN network in a different transaction and because most miners run BCHN this transaction would be mined causing the 51’st transaction on the BU network to be invalidated along with the remaining transaction chain which may follow it.  Because of this issue the inputs on any transactions that enter the memory pool beyond the standard 50 are restricted to just 1 input in the BU network thus allowing long single input chains to exist without this double spend issue. As you will see in the next section, this restriction does not necessarily mean you cannot send multi input transactions beyond the 50 limit.

Strategies to safely circumvent the single input restriction:

If for instance someone wanted to send/receive multi-input transactions greater than the 50 chain limit they could still do it because BCH Unlimited won’t entirely reject multi-input transactions beyond the limit but instead will place them in the orphan pool.  Then once the next block is found the next batch of orphans will enter the mempool and be either rejected as already spent or propagated normally as valid transactions.  Using this method entails some small risk in that only the directly connected peer would have a copy of the transaction in the orphan pool and therefore if that peer were to crash then those transactions will be lost (This is mitigated to some extent by the auto-saving and resurrection of the orphan pool on shutdown and startup, similar to the way we do it for the mempool).

NOTE: In order to send multi-input transactions from the BCH Unlimited wallet that exceed the chain limit you must first disable the restriction of inputs on your BCH Unlimited wallet. You do this by making the configuration change “–net.restrictInputs=0 and then restarting your node”. Once the setting is changed you can create any length of multi-input transaction chain in a BCH Unlimited wallet and those transactions will propagate to other BCH Unlimited peers where they will be stored as orphans if they exceed the default limit of 50 per chain.  In this way you can have multiple copies of your transaction chains exist on as many BCH Unlimited nodes as you are connected to.

Testing Results:

Mempool Admission:

Without the new modifications to mempool processing it would take 3.5 seconds for a 2000 length chain, 20 seconds for a 4000 length chain, and extrapolating from there 100 seconds for 8000 and 7 minutes for 16000 length chains.

With the new modifications, a “100,000” long transaction chain will load in just 0.95 seconds on a fairly decent laptop!  Clearly a big improvement.

Mining and Post Block processing:

Both of these improvements have been part of BCH Unlimited for quite some time but are presented here for comparison. The x-axis shows the length of the transaction chain and y-axis the response time in seconds. Both charts clearly show the previous quadratic behavior as well as the current improved behavior.

Test Results for mining:

 Chain Length   Core (secs)     BU (secs)

500                  137                   0.92

1000                 326                   1.16

1500                566                   1.28

2000                 1102                 1.43

Test results post block processing:

 Chain Length   Core (secs)     BU (secs)

500                  2                      0.03

1000                 9.9                    0.07

1500                 27.9                 0.1

2000               53.7                0.15

Conclusions:

By changing the way we mine, process blocks, and with simplifications in the mempool we can allow for unlimited transaction chains and still keep the CPFP functionality intact, while at the same time improve the performance of the software in many areas.

Special thanks to the Bitcoin Unlimited team for their constant support and in particular Andrew Stone’s transaction forwarding code which was essential in completing this project.