Optimize Bitcoin transaction generation code

Recently, I needed to generate many transactions from several machines to simulate a Bitcoin network with very large blocks. Because I created several simple scripts that used bitcoind's "sendtoaddress" API, I started these scripts in an infinite loop to see what would happen.

The result is not satisfactory. To understand why this happens, you have to understand the problem of "unconfirmed inputs". Basically, if you use a small portion of the advance payment, then you will generate 2 new outputs - one output to your destination, and one output to yourself (the change). These outputs are then considered "unconfirmed" until a new block is found, and then you can use these unconfirmed outputs again, but Bitcoin client only lets users build a relatively short chain of unconfirmed outputs before it returns a "too many unconfirmed outputs" error. (Translator's note: the original text of the last sentence butBitcoin client only lets you build a relatively shallow chain of unconfirmedoutputs before it returns a "too many unconfirmed outputs" error.)

I would be generating over 50,000 transactions from a single wallet per block, so I quickly realized I needed a method similar to confirmed outputs to reliably produce many payments.

100% of the CPU was used, and transaction generation slowed to about 1 transaction per 10 seconds. This is a problem. I made this up artificially, but is this really an unlikely number for a large enterprise? I'm guessing that for large enterprises processing millions of payments per year, reusing addresses is not the answer - the problem is the number of transaction outputs in the wallet, not the number of addresses.

So I thought about optimizing the transaction code. Ultimately, I was able to improve the efficiency of generating transactions by about 1000 times, and it helped reduce the growth of UXTO. See below for details!

Incremental Optimization

The first thing I noticed was that a lot of time was spent in locks. Especially in HaveKey（） and GetTimeOffset（） . This behavior usually happens when locks are taken and released in the "inner" loop, rather than when the lock is taken once at the beginning and end of the loop. Sure enough, I found a tight loop in CWallet:: AvailableCoins（...） . So, I added a lock-free version of IsMine, moved LOCK（cs_KeyStore） outside the loop, and got about 5-10% improvement.

As mentioned before, I also noticed that GetTimeOffset() consumes a lot of CPU... well... it takes locks again. This time the purpose is to ensure atomic read of 64-bit variables. There are better ways to achieve this on all CPU architectures, so I replaced the lock with atomic 64-bit operations on supported compilers:

 int64_tGetTimeOffset()
{
int64_t t1;
#ifdef __GNUC__ // BU optimize—doa barrier rather than a lock
t1 = __sync_fetch_and_add(&nTimeOffset,0);
#else
LOCK(cs_nTimeOffset);
t1 = nTimeOffset;
#endif
return t1;
}

This problem could also be solved by factoring in GetTimeOffset（） call inside the loop, but the structure of the code made that unsuitable, so I chose this approach to achieve another 5-10% improvement.

While these patches are a good introduction to the subsystem, it won't get me to where I want to be. To really fix this, I need to review the big implementation decisions.

Optimize implementation

The first obvious problem is that the entire wallet is extracted into a vector every time a payment is made (see SelectCoins() calling CWallet ::AvailableCoins（） ). And this vector is passed by value (aka copying) multiple times here. Since this bitcoind is usually the only entity paying from this wallet, and since we do a final transaction validity check at the end, it is safe to keep an "available" TXO data structure around, and just delete the TXO function used as a payment. Generally, the code will regenerate this structure if the code size is less than a constant. This is simpler than trying to guarantee that the structure is always exactly the same as the wallet by adding new TXOs in and fixing block reorgs, etc., and will not significantly affect small wallets, which can regenerate the data structure quickly.

The second efficiency bottleneck is the code verifying that the wallet contains enough funds to satisfy the payment requirement separately from constructing the transaction. The problem is that in order to do this, the code must count all the outputs in the wallet - so iterates again through the entire wallet's TXO set. In general, if testing an abnormal condition is expensive and will be discovered sooner or later, it is better to appear in the performance bottleneck code later. Another approach is to cache the current balance of the wallet and update it based on the inflow and outflow of funds instead of recalculating it. But again, this approach requires a lot of fragile code to ensure consistency.

Finally, the code in CWallet:: CreateTransaction has significant inefficiencies. First, it will always run the coin selection assuming there are no transaction fees. This is completely ridiculous given the block size limit and other fee code recently added to BitcoinCore (more on this later). Second, if the code guesses the transaction fee incorrectly, the code will re-run the coin selection with more fees, even if the selected input actually has enough money to pay the actual transaction fee! (See here and here)

Algorithm optimization

The final performance option in the optimization toolbox is to ask “is this algorithm actually achieving my goal?” The more I thought about it, the more I realized it wasn’t. The algorithm implemented was trying to solve the “knapsack problem” — the main problem is choosing the maximum value of “something” that doesn’t exceed a certain weight. For a Bitcoin wallet, the problem is similar but different: it’s choosing a set of inputs that are larger than the transaction value, but trying to match the values ​​of the inputs and outputs as closely as possible. The “knapsack problem” is very difficult — it’s proven to be NP-hard. However, I realized that Bitcoin had an additional problem that made it worthless — the size of the “knapsack problem” (the transaction value) is based on the transaction fee, and the fee is unknown until the entire transaction is serialized.

The end result is that if the optimizer does a "good job" by finding a set of inputs that are close to the output values, then it will not be able to include the transaction fee, so the transaction will be rejected. In this case, the code will calculate the fee and add it to the transaction amount, and try again. However, this does not make any sense. There is no actual relationship between the size of the previous solution and the next solution. Instead, it's just an operation due to the general similarity of transactions - if you know the inputs and outputs in a transaction, you can roughly estimate its size.

In fact, in my testing, the backpack optimizer was asked to pay several times almost every time.

What is the purpose of optimizing this "knapsack problem"? Who cares if a change of .1 or .0001 is accepted? The penalty for failing to find an exact solution is an additional output change, and the hurdle is exactly the same regardless of what is missed. Yes, an exact match saves the output, but the probability of that being true given a 6-10 digit number (1 Bitcoin is 100,000,000 Satoshi, the count in the code, Satoshi) is tiny. Especially since the transaction fee adds a small non-round-number to each payment, we're really dealing with 6-10 digits, not 3 digits with a lot of zeros at the end. The algorithm doesn't have a lot of flexibility - there's a real hurdle with using large inputs. Finally, a near-miss is actually a minor error for the user, not a major one, because in the case of a near-miss the code turns this "dust" into a transaction fee instead of generating an output. But a bigger mistake pays the remaining amount to the change address...

So clearly the currency selection is optimizing the wrong thing.

So what should currency selection actually optimize for? In the context of Bitcoin today, the answer to this question becomes obvious. Currency selection should minimize the UTXO set in a way that does not noticeably affect transaction fees. In other words, it should try to consume more TXO inputs than it produces outputs, and ideally use some wallets’ near-dust outputs in transactions with larger inputs that don’t obstruct the transaction. [Privacy advocates may be shocked — shouldn’t wallets try to separate coins to confuse blockchain analysis? To this question I respond: relying on an algorithm that must combine these outputs to create a transaction is extremely dangerous. Many wallets take a better approach, which is to let you separate your wallet into “accounts” or subsections that don’t mix]

New Algorithm

The new algorithm is very simple because the goal is no longer to solve NP-hard problems, but to minimize the UTXO set and maximize efficiency.

It starts "offline" by storing all wallet outputs in a container sorted by output value. This container is not reloaded from the wallet every time a payment request is received. Instead, it is only reloaded when it contains less than a few hundred TXOs.

When a payment request comes in, it first estimates the transaction fee and adds it to the requested value, given a reasonable number of inputs and outputs. Let's call this the "target value". It then simply picks the smallest TXO that is larger than the target value and stores it as the solution (if there isn't a solution, it combines it with the largest TXO until a solution is found, or nothing else is possible). It then iterates backwards, picking TXOs that are smaller than this target value. For each of these TXOs, it creates a new target value = target value - TXO value, and recursively builds a set of solutions that exceed the configurable number of TXOs. At the same time, it picks random TXOs and tries the same algorithm. This ensures that the algorithm takes into account a lot of different values ​​of TXOs, especially in cases where the backward iterator may operate over a set of small value changes.

After a bunch of iterations, or if the algorithm gets "close" to the target value (the more iterations required, the more relaxed we are about what "close" means), the optimal solution is returned.

The entire algorithm is implemented in about 200 lines of code.

Other ideas

One thing users seem to complain about is that the fees are huge. This is obvious - nobody wants to pay 5-20%. Might as well use a credit card. So why not include some checks in the code? It has to be complicated, right? Not true.

result

This algorithm supports 20 payments per second on "standard" 2GHZ laptop hardware and inside a VM, and uses only a few percent of CPU (I'll update this file when I find out what's blocking larger traffic - but probably writing wallet changes to disk). So the traffic is about 200 times that of the original algorithm for the wallet size used for testing, and most importantly the traffic increases with the log of the wallet size, not exponentially. The original algorithm uses 100% of the CPU, while this algorithm uses 10% at most - so it's about 1000 times more efficient.

Assuming a wallet has 10000+ random TXOs ranging from 1 mBTC to 10 BTC, it mostly chooses 2 to 4 inputs and spends 2 outputs (output + change). Therefore, the UTXO size either remains the same or decreases.

There is much more analysis to be done, including obviously comparing its TXO selection results to the original algorithm. However, this code easily achieved my goal of testing very large blocks, so I felt it was time to write this post.

There is clearly a lot of work to be done on transaction creation to improve the user experience and create a fully validated, enterprise-friendly Bitcoin wallet. As I think and as I show, these changes can also incentivize better wallet behavior (such as UTXO bloat control) in a simpler way than other solutions. And algorithms that already try to minimize UTXO bloat will likely handle miner algorithms that also prioritize transactions that reduce UTXO.

With time and effort, this change could happen. With enough change — changes focused on user experience and making Bitcoin clients usable by enterprises — we might actually see an increase in node counts!