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. 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.
- 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.
- Therefore, the miner with higher hashing power is more likely to find the nonce.
- Our proposed method stably maintains the number of dust in the wallet at a relatively low amount.
- When this block receives six consecutive block confirmations, the transaction is considered confirmed.
- This is iterated for 1000 rounds, whereby the number of dust remaining in each wallet after each round is recorded.
- For each round, we randomly selected a set of UTXOs and set the target as the sum of their values.
5. Snapshot of the Methodology
This is iterated for 1000 rounds, whereby the number of dust remaining in each wallet after each round is recorded. 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. The number of bytes occupied by transaction inputs and transaction outputs can vary and depend on their respective amounts.
Cryptocurrency Portfolio Selection—A Multicriteria Approach
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. 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.
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.
Machine Learning: K-Means and Hierarchical Clustering
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. 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.
Article Menu
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 study investigates crypto selection on improving the speed and time of this coin selection method will be relevant for the near future. The method described in this paper uses Bitcoin as the main subject and environment of experimentation.
Analysis of the Bitcoin UTXO Set
The transaction fee is determined by both the size of this transaction and the fee-per-byte rate decided by the entire network. The higher the transaction fee a user set for a particular transaction, the sooner this transaction will be packed into a block by the miner. In this paper, we have defined dust as the UTXO with a lower value than the fee necessary to spend it. This transaction fee is calculated by assuming only one transaction input and one output in a fixed fee-per-byte rate is involved in the concerned transaction. Dust is usually produced by low-value transactions and the change output from them that cannot be pruned by the system automatically. It will cause the growth of the global UTXO set and leaves a part of inexhaustible UTXOs.
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.
- A transaction with a lock time can be included in a block if the block height or the current time reaches the lock time requirement of the transaction.
- A study co-authored by Dr Andrei Kirilenko of Cambridge Judge Business School, presented at a recent CERF in the City event, develops an app-based recommendation framework for investor adoption of crypto assets.
- 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.
- Therefore, there is an urgency to find a higher-performing coin selection method suitable for UTXO-based cryptocurrencies.
- Ideally, the distance between UTXOs selected by the algorithm and the target is 0.
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. In order to build a transaction in cryptocurrencies using UTXO model, the user or wallet must select a certain set of UTXOs from the account as the transaction input.
Coin selection strategy based on greedy algorithm and genetic algorithm
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.
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.