Published on: 2016-10-21T14:09:57+00:00
Murch, a Master's thesis student, has developed a Coin Selection Simulator and re-implemented multiple coin selection strategies of prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and Android Wallet for Bitcoin). He invites interested parties to take a look at his work, which includes preliminary simulation results and three figures showing the simulated wallets' UTXO compositions at the end of the simulation. Murch has analyzed the Coin Selection problem and created a framework to simulate wallet behavior on the basis of a sequence of payments. He plans to publish the simulation code around Scaling Bitcoin or after he turns in his thesis.Murch also addresses a question from Daniel Weigl regarding why Mycelium generates a very big UTXO set for 5460sat. Murch explains that his simulation of the Mycelium coin selection adds small change outputs to the fee but got the boundary wrong. Instead of the 5460, he dropped at the dust boundary which calculates to 4440 in his simulation. Therefore, the results in the table might be slightly too big, but likely indicative of the actual Mycelium behavior. Murch assumes that Mycelium doesn't create small change outputs but rather hardly ever spends them when received. Murch believes that Mycelium appears to select UTXO in a FIFO approach, but after the selection, prunes by removing the smallest selected UTXO until the excess beyond the spending target is minimized. This post-selection step seems the likely reason for Mycelium's small UTXO build-up.A researcher, Murch, has analyzed the Coin Selection problem and re-implemented multiple coin selection strategies of prominent Bitcoin wallets including Bitcoin Core, Mycelium, Breadwallet, and Android Wallet for Bitcoin. As part of this research, Murch created a framework to simulate wallet behavior on the basis of a sequence of payments. The simulation results are presented in a two-page description along with three figures showing the simulated wallets' UTXO compositions at the end of the simulation.Murch also invited feedback and requested another sequence of incoming and outgoing payment amounts to run the simulation on. In response to Murch's email, Daniel Weigl, from Mycelium, inquired about the behavior of Mycelium coin selection algorithm. Murch clarified that Mycelium selects UTXO in a FIFO approach, but prunes by removing the smallest selected UTXO until the excess beyond the spending target is minimized. This post-selection step seems to be the likely reason for Mycelium's small UTXO build-up. BreadWallet uses a very similar FIFO approach, but doesn't prune which causes their average UTXO set to be much smaller. A balanced approach between these two approaches might be that instead of pruning all small inputs, a few of the small inputs could be allowed to be selected to slowly drain low-value UTXO out of the wallet by spending them over time.Murch, who is compiling his Master's thesis about Coin Selection, has created a framework to simulate wallet behavior on the basis of a sequence of payments. He re-implemented multiple coin selection strategies of prominent Bitcoin wallets including Bitcoin Core, Mycelium, Breadwallet, and Android Wallet for Bitcoin. The PDF containing a two-page description of his ongoing work includes preliminary simulation results and three figures showing the simulated wallets' UTXO compositions at the end of the simulation.Daniel Weigl asked about Mycelium's large UTXO set for 5460sat (=TransactionUtils.MINIMUM_OUTPUT_VALUE). Murch replied that his simulation did add small change outputs to the fee, but he got the boundary wrong. Instead of the 5460, he dropped at the dust boundary which calculates to 4440 in his simulation. Murch corrected the boundary in his simulation now and will update his simulation results before Scaling Bitcoin. Regarding Mycelium, Murch stated that it doesn't create small change outputs but rather hardly ever spends them when received. It appears to select UTXO in a FIFO approach, but after the selection, prunes by removing the smallest selected UTXO until the excess beyond the spending target is minimized. This post-selection step seems the likely reason for Mycelium's small UTXO build-up. A balanced approach between BreadWallet's and Mycelium's approaches might be that instead of pruning all small inputs, a few of the small inputs could be allowed to be selected to slowly drain low-value UTXO out of the wallet by spending them over time.Murch, a researcher, has compiled his Master's thesis about Coin Selection and his presentation proposal to Scaling Bitcoin has been accepted. In his thesis, he analyzed the Coin Selection problem, created a framework to simulate wallet behavior on the basis of a sequence of payments, and re-implemented multiple coin selection strategies of prominent Bitcoin wallets such as Bitcoin Core, Mycelium, Breadwallet, and Android Wallet for Bitcoin.
Updated on: 2023-08-01T19:02:53.385142+00:00