Bitcoin Forum
June 25, 2019, 05:08:40 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Organic UTXO consolidation (in the course of regular payments)  (Read 124 times)
simplexum
Newbie
*
Offline Offline

Activity: 14
Merit: 10


View Profile WWW
October 03, 2018, 06:49:27 PM
Merited by ETFbitcoin (1), Davidbugs (1)
 #1

For UTXO-based cryptocurrencies, it is important to have the set of managed Unspent Transaction Outputs in optimal shape, because if you have too much small UTXO, you will have to create bigger transactions to send the same amount of funds, and hence pay bigger network fee, or even need to send several transactions to transfer the needed amount.

Typical approach to handle this is to do periodical sweep of UTXO, bundling them all together, at the time when network fee is low.

We implemented another approach, that does not require manual UTXO consolidation, and at the same time, conserves network fee - when fee in the network is high, the algorithm tries to use less UTXO per transaction, and when network fee is low, it will create bigger transaction, effectively performing UTXO consolidation along with regular payments. This organic UTXO consolidation allows to maintain healthy UTXO set automatically, without manual consolidation runs.

We implemented it this way:

Define a rate that you are OK to pay in terms of monetary percentage: we call it "fee per full coin". Basically, you say, "to send 1 btc, I am willing to pay 0.001 btc"

When building a transaction, we calculate optimal tx size like this:

    optimal_tx_vsize = utxo_sum * fee_per_full_coin / fee_per_kb

The closer candidate transaction to the optimal size, the better score it will get.

Of course we cannot always find the optimal transaction, but we will try to choose the one with best score, depending on available UTXO set.

The resulting effect is that when fee_per_kb is high, optimal_tx_vsize will be low (may be even zero), and we will try to find the smallest tx possible with current UTXO set. When fee_per_kb is low, optimal_tx_vsize will be high, and we will choose transactions with more UTXO, performing organic UTXO consolidation.

---

If more wallets implement this type of optimizations, it will result in more healthy global UTXO set.
1561482520
Hero Member
*
Offline Offline

Posts: 1561482520

View Profile Personal Message (Offline)

Ignore
1561482520
Reply with quote  #2

1561482520
Report to moderator
1561482520
Hero Member
*
Offline Offline

Posts: 1561482520

View Profile Personal Message (Offline)

Ignore
1561482520
Reply with quote  #2

1561482520
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1561482520
Hero Member
*
Offline Offline

Posts: 1561482520

View Profile Personal Message (Offline)

Ignore
1561482520
Reply with quote  #2

1561482520
Report to moderator
1561482520
Hero Member
*
Offline Offline

Posts: 1561482520

View Profile Personal Message (Offline)

Ignore
1561482520
Reply with quote  #2

1561482520
Report to moderator
simplexum
Newbie
*
Offline Offline

Activity: 14
Merit: 10


View Profile WWW
October 03, 2018, 11:11:32 PM
Last edit: October 03, 2018, 11:22:16 PM by simplexum
 #2

Quote from: jbaczuk
Maybe you could have it generate a sweep dust transaction automatically when the fees drop below a threshold.

You can do special sweeping tx without this formula. The idea here is that if you do payments regularly, the fee in the network varies, and you set your fee_per_full_coin reasonably high - you will get gradual UTXO consolidation, without the need for separate sweeping transaction.

It may not be very useful for a single user wallet that spends occasionally, but for busy service that receives and sends a lot of payments - might mean that when they suddenly need to send a big payment, and the network fee is high - they won't need to send a huge-sized tx and pay a lot in fees, because their UTXO set will be in good shape.
RHavar
Legendary
*
Offline Offline

Activity: 1708
Merit: 1359



View Profile
October 04, 2018, 12:22:00 AM
 #3

I've done a lot of work in this space (see: coinsayer.com). This seems like a reasonable approach for consumer wallets to use, but I don't think it's going to scale very far.

I actually think the most important thing you can do for UTXO consolidation is by going out of your way to avoid creating change. This is a super powerful optimization, and the more utxo's you have the easier it is.


But consolidation transactions are probably always going to be important for businesses, because you can massively low-ball the fees. If it takes a week to confirm, it's not a big deal. But you probably can't be making actual payments with that sort of priority.  Especially services that do batched sends very quickly accumulate uxtos, so being able to reliably sweep them up (cheaply) is important.


On a side note, I've been working on trying to evangelize bustapay which does consolidation at send-time. Which is perhaps not super-ideal from a fee point of view, but it does prevent utxo growth for the receiver, which is kind of neat.
simplexum
Newbie
*
Offline Offline

Activity: 14
Merit: 10


View Profile WWW
October 04, 2018, 01:27:34 AM
Last edit: October 04, 2018, 01:42:52 AM by simplexum
 #4

Quote from: RHavar
I've done a lot of work in this space

Same. (see: https://simplexum.com), but it is not focused solely on coin selection, so probably you've done more work in this direction.

Quote from: RHavar
This seems like a reasonable approach for consumer wallets to use, but I don't think it's going to scale very far.

What would prevent this from scaling ?

Quote from: RHavar
the more utxo's you have the easier it is.

Yes, but if you have too much small utxo, and you need to send large payment at inconvenient time (when fee is high) - you will pay a premium, as delaying payment is often not an option. Also you might hit transaction size limitations, and will need to send several transactions to satisfy one payment.

Holding both fair amount of big utxo and a lot of small utxo in hot wallet might mean your hot wallet balance is higher than necessary, and your risks are also higher.

Quote from: RHavar
If it takes a week to confirm, it's not a big deal.

But this means you are freezing this funds for a week, and need to get funds for operation from somewhere else, like your cold wallet.

Also, big sweeping transaction is more visible.
ETFbitcoin
Legendary
*
Online Online

Activity: 1680
Merit: 1813

Use SegWit and enjoy lower fees.


View Profile WWW
October 04, 2018, 01:43:15 AM
 #5

So basically a formula to determine whether it's worth to consolidate UTXO set, nice idea.

However, there are multiple privacy concern when you receive Bitcoin from multiple party and you don't want any party how much Bitcoin you have or with whom you made Bitcoin transaction.
If wallets gonna implement this idea, such warning should be shown to users.

Also, IMO there should be balance between UTXO size/set, blockchain size and TPS.

Quote from: RHavar
If it takes a week to confirm, it's not a big deal.

But this means you are freezing this balance for a week, and need to get funds from somewhere else, like your cold wallet.

Also, big sweeping transaction is more visible.

You can spend unconfirmed UTXO/input and thus make both transaction could be confirmed faster (aka CPFP).

RHavar
Legendary
*
Offline Offline

Activity: 1708
Merit: 1359



View Profile
October 04, 2018, 01:49:46 AM
 #6

Yes, but if you have too much small utxo, and you need to send large payment at inconvenient time (when fee is high) - you will pay a premium, as delaying payment is often not an option. Also you might hit transaction size limitations, and will need to send several transactions to satisfy one payment.

Holding both fair amount of big utxo and a lot of small utxo in hot wallet might mean your hot wallet balance is higher than necessary, and your risks are also higher.

Well yeah. When I ran a wallet, I would never allow it to pick more than 3 inputs for a given transaction. So you'd have an "effective balance" which is much less than the sum of all the utxo values.

You can mitigate a lot of the risk of having a fat wallet, by having a wallet that has a concept of a "min balance" and will never go under it.  So say you have a 100 BTC of utxos, you might want want to configure the wallet to have a "min balance" of 70 BTC.  So under normal circumstances, you're only risking 30 BTC (Say your service gets hacked). If things go catastrophically wrong (e.g. your locked down wallet machine gets hacked) you're risking the full 100 BTC. And then for everything else, you use fully cold storage.

Works pretty well, honesty.  But I guess it depends on how much float you can afford to be using  Grin
simplexum
Newbie
*
Offline Offline

Activity: 14
Merit: 10


View Profile WWW
October 04, 2018, 01:58:28 AM
 #7

Quote from: ETFbitcoin
You can spend unconfirmed UTXO/input and thus make both transaction could be confirmed faster (aka CPFP).

CPFP means you just paying more fee in the child tx - if you wanted to use the result of the sweep soon, you could just have added more fee at the tx creation

Quote from: ETFbitcoin
However, there are multiple privacy concern when you receive Bitcoin from multiple party and you don't want any party how much Bitcoin you have or with whom you made Bitcoin transaction.

If you do not conflate utxo from different wallets (or sub-wallets), there's no problem - user should have used different wallets/sub-wallets for different purposes, if this is a concern
simplexum
Newbie
*
Offline Offline

Activity: 14
Merit: 10


View Profile WWW
October 04, 2018, 02:08:49 AM
Last edit: October 04, 2018, 02:23:08 AM by simplexum
 #8

Quote from: RHavar
a concept of a "min balance" and will never go under it.

Quote from: RHavar
under normal circumstances, you're only risking 30 BTC (Say your service gets hacked). If things go catastrophically wrong (e.g. your locked down wallet machine gets hacked) you're risking the full 100 BTC.

An interesting concept. One of the imperatives that was set when we created our system was that the risks should be eliminated or mitigated to the maximum extent possible, so this was not considered. But this is quite easy to add, as an option for those who can tolerate the risk, so we might think about implementing it.

Another important requirement was that if there is a spendable balance on wallet, and a payment order comes to spend this balance, it should be sent - the developer using an API should not bother about if there enough big utxo available, or if the transaction limitation might be hit, or whatever - if there's enough funds for the order amount (and network fee, if the fee is taken from the wallet, and not from recipient)  - send it, use every utxo available, even if it means sending several txs.
RHavar
Legendary
*
Offline Offline

Activity: 1708
Merit: 1359



View Profile
October 04, 2018, 04:46:32 AM
 #9

Another important requirement was that if there is a spendable balance on wallet, and a payment order comes to spend this balance, it should be sent - the developer using an API should not bother about if there enough big utxo available, or if the transaction limitation might be hit, or whatever - if there's enough funds for the order amount (and network fee, if the fee is taken from the wallet, and not from recipient)  - send it, use every utxo available, even if it means sending several txs.

Most of the time, that's going to be pretty awful behavior. Say fees are high, so your algorithm is going to try avoid consolidation for as long as possible. Then finally say there's a big transaction that can only be created via spending the whole wallet at a high-fee time. With very high fee rates, that mistake can easily end up thousands of dollars in fees :/

I suspect most people would rather avoid that degenerate case, and instead just keep a bit extra money in their wallet. Or even erring with a "hot wallet doesn't have enough balance" and topping it up is probably preferable. If you look at the coinsayer API, you'll see it recommends setting maxInputsToSelect to 3. which is the sort of behavior most people want (although you're free to set it to what ever you like, if you don't mind sweeping the wallet like that)
simplexum
Newbie
*
Offline Offline

Activity: 14
Merit: 10


View Profile WWW
October 04, 2018, 04:56:27 AM
Last edit: October 05, 2018, 08:03:49 AM by simplexum
 #10

Quote from: RHavar
Say fees are high, so your algorithm is going to try avoid consolidation for as long as possible.

fee_per_full_coin should be adjusted if the median fee, averaged over a prolonged period, becomes significantly higher (or lower). And even if you lag a bit with this adjustment, your utxo set will not degrade instantly. You can monitor the recent median fee and tell if your fee_per_full_coin setting is too low or too high - you basically want it so that with median fee, you will be mostly choosing averagely small txs (assuming your utxo set is already in good shape). 2 or 3 inputs seem like a good choice, but as the size of inputs varies depending on the properties of addresses that the wallet contains, the actual setting will be specific to the concrete wallet setup.

Quote from: RHavar
keep a bit extra money in their wallet

70 out of 100, more than 2x of usable amount, is quite a big extra, IMO.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!