A coin selection strategy based on the greedy and genetic algorithm

In 2008, Satoshi Nakamoto published the article “Bitcoin: A Peer-to-Peer Electronic Cash System”, which described a decentralized electronic currency architecture based on asymmetric encryption technology, P2P network, time stamp, hash algorithm mechanism, distributed consensus algorithm, and economic reward mechanism [1]. Meanwhile, this article also marked the official birth of Bitcoin.

In Bitcoin, a block is a storage unit used to publicly store several transactions permanently. Generating a block is considered as mining, which is a process of packing transactions into blocks and finding a random number that solves a cryptographic problem.

There may be multiple miners who are trying to generate a block concurrently. However, the probability of mining a block is proportional to the hashing power of the miner. Therefore, the miner with higher hashing power is more likely to find the nonce. When a miner packages a transaction into a block, the transaction is first confirmed then linked to the blockchain. When this block receives six consecutive block confirmations, the transaction is considered confirmed. A transaction generator can offer transaction fee to draw miners’ attention so that the transaction is more likely to be packed and confirmed.

Bitcoin is a decentralized application that uses the UTXO model, in which UTXOs are consumed as transaction input and created by transaction outputs. The payer can create and broadcast transactions through the P2P network without going through other third-party platforms. This kind of structure can replace the trusted third party. All transactions are stored in the block openly, transparently and distributed. Bitcoin addresses are equivalent to accounts in traditional financial systems, but addresses are not linked to the actual social identity, which protects the privacy of users.

At present [2], the total number of Bitcoin wallets is around 32 million. Since one user can have more than one wallet, the number of active users cannot be observed, it is also a rapidly growing number as more people become new users of Bitcoin. With the development of Bitcoin, large transaction arrival rates have occasionally been observed. Bitcoin’s block cannot accommodate all of them due to the limitation that the size of a block cannot exceed 1 MB [3]. The wallet in UTXO-based cryptocurrencies manages several UTXOs owned by the specific accounts. When the owner of a wallet wants to accomplish a transaction, the wallet will use their own coin selection method to choose a certain set of UTXOs to fund this transaction.

The coin selection method that Bitcoin uses is a random selection approach which is low in efficiency, as it cannot always ensure the target is met and with the increase of UTXOs the difficulty of finding an appropriate match also increases. The Bitcoin core defines “dust” as the trace amount of Bitcoin remaining in a wallet or address that is unable to process the transaction as its value is below the transaction fee required. We define dust as a UTXO whose value is lower than the transaction fee to spend it. For example, a Pay to Public Key Hash(P2PKH) input is 148bytes, an output is 34 bytes, and the additional information in transaction data is 10 bytes. A transaction with two outputs should pay at least 192 satoshi with default minimum transaction fee (1 satoshi per byte). In this example, if the P2PKH input is lower than 192 satoshi then it is considered “dust”.

Dust production is one of the shortcomings of the UTXO model. When a user needs to generate a transaction, the Bitcoin core will use its own strategy to select the set of UTXOs in the user’s account [4]. It selects the UTXO that exceeds the target and generates two new coins one being paid and the other as “change”. Usually, it will assemble multiple coins to reach the target transaction amount. These complexities prove to have further ramifications when other factors are put into consideration such as transaction fees and production of dust. It needs to be noted that transaction fees are calculated based on the selection situation of coins in a transaction. Also, take notice that when large coins are spent rapidly there will be an accumulation of low value coins left that may become impossible to transact due to being lower than the required transaction fee.

These implications indicate the urgency for an efficient coin selection strategy for UTXO-based cryptocurrencies. A high-performance coin selection method would be one that puts into consideration selecting an appropriate amount of UTXOs to prevent high transaction fees as well as reducing the production of dust by spending low value coins earlier. This paper proposes a new coin selection strategy based on the greedy and genetic algorithm. It aims to make full use of low value coins to reach the transaction amount to prevent dust production and maintain or even possibly reduce the number of coins to avoid excessive transaction fees.

When creating a transaction in Bitcoin, first, the UTXOs belonging to this address should be found, this is to find the previous confirmed transaction outputs that point to the address. Then, the selection of UTXOs from those available follows a certain random method till the sum of the UTXOs allocated is greater than or equal to the target amount to be paid. The method used by Bitcoin to select UTXO as transaction input is described as follows, the target amount is the amount to be paid (without transaction fees) [16]:

Overall, the selection method employed by Bitcoin prioritizes selecting UTXOs whose sum of the amount is closest to the target on a random selection recursion. This strategy cannot ensure accuracy of target value matching and lack effectiveness in minimizing transaction fee. Moreover, the algorithm used does not take into consideration change output of the transaction and therefore overlooks dust production. In [4], they quantitatively examine Bitcoin’s coin selection method in regards to dust production and observed a trend of increasing number of unprofitable UTXOs.

Amidst the abundance of research on cryptocurrencies, there are few papers on coin selection methods specifically. Thus, our review of related work looks at selection strategies that prioritize target value accuracy [17, 18], enhance the knapsack algorithm [19], and protect user privacy [20]. Our work proposes a coin selection method that aims to meet the exact target requirement whilst maintaining a small and stable number of UTXO inputs, and avoiding the production of dust. This paper interprets the method through an explanation of the algorithms concerned and illustrates the effectiveness through visualized data sets from simulations. The coin selection algorithm used in the Bitcoin core is roughly 2000 rounds of random recursions to find a set of UTXOs that comes closest to the payment target [17]. This selection strategy is discussed in detail in section IV.

Erhardt’s thesis looks at a sample of different wallets and their implemented policies in regards to the effect on transaction fees and the UTXO pool [18]. It also introduces the Branch’n’Bound algorithm to find an exact match of the transaction target value. Drawing on quantitative experiment results, Erhardt makes suggestions to the Bitcoin Core’s algorithm on their coin selection method which was later adopted by the developers as a secondary method. The proposed method employs the Branch’n’Bound algorithm to seek an exact match of the target value and falls back on the Random Draw if it fails to find an exact match. D.J.Diroff proposes an enhancement of the knapsack algorithm to achieve the goal of minimizing cost by ensuring the change output of one transaction can fit the target value of a later transaction exactly [19]. This take on the classic knapsack problem takes into consideration minimizing change outputs that may be too low in value rendering it ineffective for another transaction. Taking a different approach, [4, 20] looks at the current state of cryptocurrency networks evaluating existing concerns and the effectiveness of strategies to combat them. Abramova and Bohme’s paper looks at coin selection strategies and the intertemporal problem while evaluating them from a privacy perspective.

The paper [4] discusses in detail dust in UTXO-based cryptocurrencies namely Bitcoin, Bitcoin Cash, and Litecoin. Their work demonstrates the importance of designing appropriate coin selection methods as the current state of such cryptocurrency networks faces an imminent threat of dust. While illustrating the difficulty of the network’s global maintenance due to its complexity, the research paper highlights potential percussions of the existing shortcomings of the current coin selection methods. Our work answers the concerns brought to light, proposing a coin selection method that disincentivizes dust creation whilst enhancing the overall performance in the context of UTXO-based cryptocurrencies.

The coin selection complication is an optimization problem with three major objectives. Meeting the basic requirement of reaching the target value whilst ensuring the lowest possible difference, maintaining a relatively small number of dust in the wallet, and limiting the number of coins utilised in a transaction. In our context, a coin is represented by a UTXO input. Assuming a Bitcoin user U has n available UTXOs, the target denotes the value of the transaction to be made. For the coin selection process, the size of the search space should be no greater than \(2^n\) to prevent the search space becoming significantly larger. Our work focuses on increasing the accuracy of matching the target value of each transaction, maintaining a small number of dust in a wallet, and disincentivising the production of dust.

There exist an abundance of techniques for multi-objective optimization, some recent ones include particle swarm optimization [21] and deep reinforcement learning [22]. However, compared to the classical greedy and genetic algorithms these recent optimization techniques respectively have disadvantages that render them a lesser match compared to the greedy and genetic algorithm. In the case of the particle swarm algorithm, it falls easily into local optimum when working in a higher dimensional space and has a low convergence rate. On the other hand, deep reinforcement learning requires hefty computation, an extensive amount of time, and lack data to train the network. In this section, our proposed strategy to select coins based on the greedy and genetic algorithm will be introduced, as well as the characteristics of this new approach will be examined. Then, the specific steps of using these two algorithms for coin selection in a transaction will be described in detail, with explanation of use and meaning at each stage.

During the first experiment, we conducted 8 sets of simulations, each of which was performed for 100 or 1000 rounds. For the first 6 sets of simulations, we randomly generated n positive integers between a certain range shown in the first column of Tables 1 and 2 as available UTXOs for each simulation. For the last three sets, we obtained three real Bitcoin accounts’ UTXOs as available UTXOs. In each round, a random selection of UTXOs is summed up and set as the target amount. To examine the performance of our method against other strategies each experiment included simulations of Branch’n’Bound(BnB), the current algorithm Bitcoin uses (BTC), and our proposed method in order for vertical comparison (\( Greedy \& GA \), GA).

In total, we performed 1800 experimental rounds. The UTXO sets used in each set of simulations are shown in column 1 in both Tables 1 and 2, and the experimental rounds m in each set are shown in column 2. For each round, we randomly selected a set of UTXOs and set the target as the sum of their values. Ideally, the distance between UTXOs selected by the algorithm and the target is 0.

For the second experiment, we used the sample of UTXO set taken on October 1st of 2019 available on GitHub [19], we ran 1000 rounds of simulations. We created three identical wallets, with 2000 UTXOs and 10% of dust where the fee-per-byte rate is 22. In each round, a set of UTXOs is summed to assign as the target value of which our proposed algorithm and Bitcoin’s method need to retrieve UTXOs to match. Then, if necessary the change output is added back to the wallets before three identical sets of 200 UTXOs including 10% dust is added to all wallets respectively. This is iterated for 1000 rounds, whereby the number of dust remaining in each wallet after each round is recorded.

In our method, the parameter of the genetic algorithm is set as the following based on experience:We showed the mean distance between the target and the result of the Bitcoin method, Branch’n’Bound method and the method we proposed in columns 3, 4 and 5. Columns 6, 7 and 8 shows the variance from target of each method, it presents the stability of finding the closest solution to the target. Table 2 compares the three methods’ mean and variance of UTXO quantity selected by the method. Figures 10 and 11 show the comparison of the results obtained by the real account 1 and real account 3. The \(result\_BTC\) is the selection result obtained by the coin selection method used in Bitcoin, the \(result\_BnB\) result obtained by the Branch’n’Bound method, and \(result\_GA\) is the selection result obtained by our approach. Table 3 shows the minimum, maximum, and average of dust quantity in the three wallets in each 100 rounds. Figure 12 visualizes the dust quantity fluctuations in each wallet over 300 rounds.

According to the results from Tables 1, 2, Figs. 10 and 11, the method we proposed offers a solution whose result is closer to the target and uses less UTXOs. In almost every simulation, the distance to the target of UTXOs chosen by our method is significantly closer than of the other methods whilst maintaining a similar mean number of UTXOs selected. In the first 6 sets of simulations, the greedy and genetic algorithms proved to be high-performing in accuracy of target-matching as the mean distance was low throughout. Additionally, the outstanding result of the methods variance of distance showcases its stability. This trend carries through into the simulations using real accounts. The two comparison of distance from target graphs in Figs. 10 and 11, visualizes the performance of all three methods and exhibits the distinguished performance of our proposed method in a vertical comparison.

From Table 2, it can be observed that our proposed method does not fall short in performance of UTXO quantity control. Hence, while hitting the target more accurately our method will not create transactions that require excessive transaction fees, this holds true stably. This performance can be clearly perceived in the graphs depicting the comparison of UTXO quantities selected by all three methods in Figs. 10 and 11.

For each 100 rounds we compared the minimum, maximum, and average number of dust in each wallet to demonstrate the performance of the respective coin selection methods. Although Bitcoin’s method has the lowest minimum number of dust however the average number of dust in the Bitcoin’s method wallet is around 100. The result of Branch’n’Bound shows a the biggest range between minimum and maximum, it also has the highest average quantity of dust. Our proposed method stably maintains the number of dust in the wallet at a relatively low amount. Hence, demonstrating our coin selection method utilizes more dust when choosing the set of UTXOs used in each transaction without compromising low transaction fees. Figure 12 illustrates the result from the first 300 rounds. From the graph, it can be recognised that the results of methods BTC and BnB fluctuates majorly, while the GA method upholds a steady trend on a low amount of dust.

After the greedy algorithm is run, each UTXO selected has a large amount because small UTXOs were excluded, which suppresses the utility of the low-value UTXOs. However, the genetic algorithm makes use of the lower value UTXOs regurgitating the suppressed small UTXOs from the greedy algorithm. Besides, because the initial value of best is set to the result obtained by the greedy algorithm, the final result must be the result of the greedy algorithm or a better result than the greedy algorithm. Although the method we proposed is better than the Bitcoin method in both distance and the number of UTXOs, this algorithm requires more time to solve the problem, as we discussed in section 4.

The integration of the greedy algorithm and genetic algorithm can formulate a solution that efficiently selects coins based on their individual values in a way to get as close as possible to the target with the least number of coins. Under this premise, the method also prevents the production of dust as it prioritizes using a combination of coins that comes to the specific target amount, therefore, eliminating excessive “change”.

As greedy algorithm and genetic algorithm are used, the time taken to search for the solution will be extended. If this time prove to be inconveniently long, then improvement on the selection, crossover, and mutation process is in need. Since\( P_c\) and \(P_m\) can affect the algorithm and its convergence, they can be changed automatically adaptively, that is, adaptive genetic algorithm [26]. In Bitcoin, the user’s UTXO is stored in the UTXO pool. Selecting fewer UTXO as transaction input means that a larger number of UTXO will accumulate in the UTXO pool, which is not conducive to UTXO management or adds complexity to subsequent UTXO searches [27]. While this was not a complication in a controlled experimental environment, it could pose to be a hindrance in realising the benefits of this strategy in a real-world situation. Further research on improving the speed and time of this coin selection method will be relevant for the near future.