commit cb69aa80f7f9751ee5ed4699f93e4b00f8c59b10
parent e0b1bbfc4603556e646c41dec39d31a61a656c1a
Author: SomberNight <somber.night@protonmail.com>
Date: Thu, 20 Jun 2019 22:40:57 +0200
coinchooser: don't spend buckets with negative effective value
Calculate the effective value of buckets, and filter <0 out.
Note that the filtering is done on the buckets, not per-coin.
This should better preserve the user's privacy in certain cases.
When the user "sends Max", as before, all UTXOs are selected,
even if they are not economical to spend.
see #5433
Diffstat:
3 files changed, 47 insertions(+), 12 deletions(-)
diff --git a/electrum/coinchooser.py b/electrum/coinchooser.py
@@ -25,6 +25,7 @@
from collections import defaultdict
from math import floor, log10
from typing import NamedTuple, List, Callable
+from decimal import Decimal
from .bitcoin import sha256, COIN, TYPE_ADDRESS, is_address
from .transaction import Transaction, TxOutput
@@ -74,6 +75,7 @@ class Bucket(NamedTuple):
desc: str
weight: int # as in BIP-141
value: int # in satoshis
+ effective_value: int # estimate of value left after subtracting fees. in satoshis
coins: List[dict] # UTXOs
min_height: int # min block height where a coin was confirmed
witness: bool # whether any coin uses segwit
@@ -109,11 +111,14 @@ class CoinChooserBase(Logger):
def keys(self, coins):
raise NotImplementedError
- def bucketize_coins(self, coins):
+ def bucketize_coins(self, coins, *, fee_estimator):
keys = self.keys(coins)
buckets = defaultdict(list)
for key, coin in zip(keys, coins):
buckets[key].append(coin)
+ # fee_estimator returns fee to be paid, for given vbytes.
+ # guess whether it is just returning a constant as follows.
+ constant_fee = fee_estimator(2000) == fee_estimator(200)
def make_Bucket(desc, coins):
witness = any(Transaction.is_segwit_input(coin, guess_for_address=True) for coin in coins)
@@ -123,7 +128,23 @@ class CoinChooserBase(Logger):
for coin in coins)
value = sum(coin['value'] for coin in coins)
min_height = min(coin['height'] for coin in coins)
- return Bucket(desc, weight, value, coins, min_height, witness)
+ # the fee estimator is typically either a constant or a linear function,
+ # so the "function:" effective_value(bucket) will be homomorphic for addition
+ # i.e. effective_value(b1) + effective_value(b2) = effective_value(b1 + b2)
+ if constant_fee:
+ effective_value = value
+ else:
+ # when converting from weight to vBytes, instead of rounding up,
+ # keep fractional part, to avoid overestimating fee
+ fee = fee_estimator(Decimal(weight) / 4)
+ effective_value = value - fee
+ return Bucket(desc=desc,
+ weight=weight,
+ value=value,
+ effective_value=effective_value,
+ coins=coins,
+ min_height=min_height,
+ witness=witness)
return list(map(make_Bucket, buckets.keys(), buckets.values()))
@@ -287,8 +308,14 @@ class CoinChooserBase(Logger):
dust_threshold=dust_threshold,
base_weight=base_weight)
- # Collect the coins into buckets, choose a subset of the buckets
- all_buckets = self.bucketize_coins(coins)
+ # Collect the coins into buckets
+ all_buckets = self.bucketize_coins(coins, fee_estimator=fee_estimator)
+ # Filter some buckets out. Only keep those that have positive effective value.
+ # Note that this filtering is intentionally done on the bucket level
+ # instead of per-coin, as each bucket should be either fully spent or not at all.
+ # (e.g. CoinChooserPrivacy ensures that same-address coins go into one bucket)
+ all_buckets = list(filter(lambda b: b.effective_value > 0, all_buckets))
+ # Choose a subset of the buckets
scored_candidate = self.choose_buckets(all_buckets, sufficient_funds,
self.penalty_func(base_tx, tx_from_buckets=tx_from_buckets))
tx = scored_candidate.tx
@@ -334,8 +361,7 @@ class CoinChooserRandom(CoinChooserBase):
candidates.add(tuple(sorted(permutation[:count + 1])))
break
else:
- # FIXME this assumes that the effective value of any bkt is >= 0
- # we should make sure not to choose buckets with <= 0 eff. val.
+ # note: this assumes that the effective value of any bkt is >= 0
raise NotEnoughFunds()
candidates = [[buckets[n] for n in c] for c in candidates]
diff --git a/electrum/simple_config.py b/electrum/simple_config.py
@@ -533,14 +533,16 @@ class SimpleConfig(Logger):
fee_per_kb = self.fee_per_kb()
return fee_per_kb / 1000 if fee_per_kb is not None else None
- def estimate_fee(self, size):
+ def estimate_fee(self, size: Union[int, float, Decimal]) -> int:
fee_per_kb = self.fee_per_kb()
if fee_per_kb is None:
raise NoDynamicFeeEstimates()
return self.estimate_fee_for_feerate(fee_per_kb, size)
@classmethod
- def estimate_fee_for_feerate(cls, fee_per_kb, size):
+ def estimate_fee_for_feerate(cls, fee_per_kb: Union[int, float, Decimal],
+ size: Union[int, float, Decimal]) -> int:
+ size = Decimal(size)
fee_per_kb = Decimal(fee_per_kb)
fee_per_byte = fee_per_kb / 1000
# to be consistent with what is displayed in the GUI,
diff --git a/electrum/wallet.py b/electrum/wallet.py
@@ -745,12 +745,13 @@ class Abstract_Wallet(AddressSynchronizer):
base_tx.remove_signatures()
base_tx.add_inputs_info(self)
base_tx_fee = base_tx.get_fee()
- relayfeerate = self.relayfee() / 1000
+ relayfeerate = Decimal(self.relayfee()) / 1000
original_fee_estimator = fee_estimator
- def fee_estimator(size: int) -> int:
+ def fee_estimator(size: Union[int, float, Decimal]) -> int:
+ size = Decimal(size)
lower_bound = base_tx_fee + round(size * relayfeerate)
lower_bound = lower_bound if not is_local else 0
- return max(lower_bound, original_fee_estimator(size))
+ return int(max(lower_bound, original_fee_estimator(size)))
txi = base_tx.inputs()
txo = list(filter(lambda o: not self.is_change(o.address), base_tx.outputs()))
old_change_addrs = [o.address for o in base_tx.outputs() if self.is_change(o.address)]
@@ -763,7 +764,13 @@ class Abstract_Wallet(AddressSynchronizer):
tx = coin_chooser.make_tx(coins, txi, outputs[:] + txo, change_addrs,
fee_estimator, self.dust_threshold())
else:
- # FIXME?? this might spend inputs with negative effective value...
+ # "spend max" branch
+ # note: This *will* spend inputs with negative effective value (if there are any).
+ # Given as the user is spending "max", and so might be abandoning the wallet,
+ # try to include all UTXOs, otherwise leftover might remain in the UTXO set
+ # forever. see #5433
+ # note: Actually it might be the case that not all UTXOs from the wallet are
+ # being spent if the user manually selected UTXOs.
sendable = sum(map(lambda x:x['value'], coins))
outputs[i_max] = outputs[i_max]._replace(value=0)
tx = Transaction.from_io(coins, outputs[:])
