On Tue, Jan 23, 2018 at 09:31:00PM +0000, Gregory Maxwell wrote: > On Mon, Jan 22, 2018 at 8:00 PM, Peter Todd via bitcoin-dev > wrote: > > Most transactions don't have change?! Under what circumstance? For most > > use-cases the reverse is true: almost all all transactions have change, because > > it's rare for the inputs to exactly math the requested payment. > > It's quite easy to get no change with a not-dumb algorithm selecting > coins if you have a decent number of outputs well under the value > you're paying. > > The number of ways n choose m combines grows exponentially, and you > only need to get close enough over the right value so that you're > paying excess fees equal or less than the cost of the change (which > should include the current cost output itself as well as estimated > cost of the future signature to spend it). > > Achow101 and Murch have code to implement an efficient algorithm for > finding these solutions for Bitcoin core which will hopefully get in > soon. Oh, Bitcoin Core doesn't already do that? I though that was what the (rather complex) knapsack code was supposed to be doing. In any case, you're assuming that there actually are a large number of outputs. That's not likely to be the case in most "consumer-like" use-cases where the number of deposits into the wallet is relatively low compared to the number of withdrawls as coins are spent in smaller amounts; that's the pattern most of my Bitcoin usage follows, particularly as I keep the amount of funds in my hot wallets low. Having said that, Rhavar's usage patterns could easily be different; I'd be completely wrong in the case of a payment service for instance where a large number of deposits are aggregated into a smaller number of payments; that use-case happens to be a particularly interesting one for using tx replacement to add outputs, so my criticism was definitely premature. -- https://petertodd.org 'peter'[:-1]@petertodd.org