Where \( V_i \) is the value of ith transaction input in this transaction, \( A_i \) is the age of ith transaction input in this transaction, and \(S_t\) is the size of this transaction. 4, a block consists of a magic number, block size, block header and transactions, and the size of the first three fields is fixed. For example, Bitcoin requires that the size of a block be less than or equal to 1 MB, and the block header occupies 80 bytes. Since every transaction is recorded in the block, the transaction size affects the number of transactions that the block can accommodate 9,10,11,12.

Your RSS Feed

The number of transactions is directly proportional to the size of the block 13. 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. Consumers regularly choose books, music, travel destinations and other activities based on recommendations by many people on e-commerce or social media platforms. The annual event, held online this year, allows finance practitioners to interact with academic researchers.

Article Menu

However, the proposed method is applicable to all blockchain applications that employs the UTXO transaction model and includes an amount field in the transaction. Although, transactions generated using this method cannot guarantee the lowest possible transaction fees, it does not produce excessively high transaction fees. The algorithm described in this paper is mature and has established accountability and hence why it is essential to illustrate the feasibility of this method.

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. Otherwise, the miner will not include this transaction in the current block 5. 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.

Materials and Methods

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.

A coin selection strategy based on the greedy and genetic algorithm

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. 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”.

Suppose someone tries to pretend he is a beneficiary and generates an unlocking script with his private key. In that case, the miner will find that the unlocking script does not match the locking script when the signature verification is performed and can discard the transaction 8. These various crypto assets have different electronic sharing protocols and other technological features, as well as varying governance solution such as private versus open access to the ledger. 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.

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. The method described in this paper uses Bitcoin as the main subject and environment of experimentation.

Although the time complexity of the Bitcoin method is O(n) , it can not guarantee that method can find solution that is close enough to the optimal solution. With n getting larger, study investigates crypto selection the Bitcoin method will become more challenging to find a solution. 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. There may be multiple miners who are trying to generate a block concurrently.

• In that case, the miner will find that the unlocking script does not match the locking script when the signature verification is performed and can discard the transaction 8.
• The transaction outputs will generate new UTXOs, and the transaction inputs consume UTXOs, which are the source of coins.
• 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.
• Coin selection method refers to the process undergone when selecting a set of unspent transaction outputs (UTXOs) from a cryptocurrency wallet or account to use as inputs in each transaction.

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 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.

Additionally, the outstanding result of the methods variance of distance showcases its stability. 10 and 11, visualizes the performance of all three methods and exhibits the distinguished performance of our proposed method in a vertical comparison. 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.

Basic data structure in Bitcoin and the coin selection problem

• If this time prove to be inconveniently long, then improvement on the selection, crossover, and mutation process is in need.
• 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.
• Amidst the abundance of research on cryptocurrencies, there are few papers on coin selection methods specifically.
• But the amount requirement and transaction fee are not the sole factors contributing to the coin selection problem.
• In this selection process, the basic task is to reach the amount required for this transaction.

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.