commit 9a6dcf7b1e0219bd6d5a5a51d21ec1dc6df999d0
parent 93bb09230c917bd58a139fb39b2d82a64da06cc9
Author: Neil Booth <kyuupichan@gmail.com>
Date: Sun, 29 Nov 2015 17:59:36 +0900
Use bucketing to choose coins
Bucketing is generalization of coin chooser logic that makes it easy
to implement other algorithms.
- Put core coin chooser functionality in base class.
- Specialize derived class to implement classic electrum algorithm of
oldest coins first. One bucket per output.
No intended change in behaviour.
Coin chooser now sorts the coins as it wants; remove redundant sorting
from get_spendable_coins().
Diffstat:
2 files changed, 72 insertions(+), 39 deletions(-)
diff --git a/lib/coinchooser.py b/lib/coinchooser.py
@@ -16,13 +16,28 @@
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
-from operator import itemgetter
+from collections import defaultdict, namedtuple
from util import NotEnoughFunds, PrintError, profiler
from transaction import Transaction
+Bucket = namedtuple('Bucket', ['desc', 'size', 'value', 'coins'])
-class CoinChooser(PrintError):
+class CoinChooserBase(PrintError):
+
+ def bucketize_coins(self, coins):
+ keys = self.keys(coins)
+ buckets = defaultdict(list)
+ for key, coin in zip(keys, coins):
+ buckets[key].append(coin)
+
+ def make_Bucket(desc, coins):
+ size = sum(Transaction.estimated_input_size(coin)
+ for coin in coins)
+ value = sum(coin['value'] for coin in coins)
+ return Bucket(desc, size, value, coins)
+
+ return map(make_Bucket, buckets.keys(), buckets.values())
def make_tx(self, coins, outputs, change_addrs, fee_estimator,
dust_threshold):
@@ -30,47 +45,71 @@ class CoinChooser(PrintError):
greater than dust_threshold (after adding the change output to
the transaction) it is kept, otherwise none is sent and it is
added to the transaction fee.'''
- amount = sum(map(lambda x: x[2], outputs))
- total = 0
- tx = Transaction.from_io([], outputs)
+ output_total = sum(map(lambda x: x[2], outputs))
# Size of the transaction with no inputs and no change
+ tx = Transaction.from_io([], outputs)
base_size = tx.estimated_size()
- # Pay to bitcoin address serializes as 34 bytes
- change_size = 34
- # Size of each serialized coin
- for coin in coins:
- coin['size'] = Transaction.estimated_input_size(coin)
-
- size = base_size
- # add inputs, sorted by age
- for item in coins:
- v = item.get('value')
- total += v
- size += item['size']
- tx.add_input(item)
- if total >= amount + fee_estimator(size):
- break
- else:
- raise NotEnoughFunds()
+ # Returns fee given input size
+ fee = lambda input_size: fee_estimator(base_size + input_size)
+
+ # Collect the coins into buckets, choose a subset of the buckets
+ buckets = self.bucketize_coins(coins)
+ buckets = self.choose_buckets(buckets, output_total, fee)
- # remove unneeded inputs.
- for item in sorted(tx.inputs, key=itemgetter('value')):
- v = item.get('value')
- if total - v >= amount + fee_estimator(size - item['size']):
- tx.inputs.remove(item)
- total -= v
- size -= item['size']
self.print_error("using %d inputs" % len(tx.inputs))
+ self.print_error("using buckets:", [bucket.desc for bucket in buckets])
+
+ tx.inputs = [coin for b in buckets for coin in b.coins]
+ input_total = sum(bucket.value for bucket in buckets)
+ tx_size = base_size + sum(bucket.size for bucket in buckets)
# If change is above dust threshold after accounting for the
# size of the change output, add it to the transaction.
- change_amount = total - (amount + fee_estimator(size + change_size))
+ # Pay to bitcoin address serializes as 34 bytes
+ change_size = 34
+ fee = fee_estimator(tx_size + change_size)
+ change_amount = input_total - (output_total + fee)
if change_amount > dust_threshold:
tx.outputs.append(('address', change_addrs[0], change_amount))
- size += change_size
self.print_error('change', change_amount)
elif change_amount:
self.print_error('not keeping dust', change_amount)
return tx
+
+class CoinChooser(CoinChooserBase):
+ '''The original electrum algorithm. Chooses coins starting with the
+ oldest that are sufficient to cover the spent amount, and then
+ removes any not needed starting with the smallest in value.'''
+
+ def keys(self, coins):
+ return [coin['prevout_hash'] + ':' + str(coin['prevout_n'])
+ for coin in coins]
+
+ def choose_buckets(self, buckets, spent_amount, fee):
+ '''Spend the oldest buckets first.'''
+ # Unconfirmed coins are young, not old
+ adj_height = lambda height: 99999999 if height == 0 else height
+ buckets.sort(key = lambda b: max(adj_height(coin['height'])
+ for coin in b.coins))
+ selected, value, size = [], 0, 0
+ for bucket in buckets:
+ selected.append(bucket)
+ value += bucket.value
+ size += bucket.size
+ if value >= spent_amount + fee(size):
+ break
+ else:
+ raise NotEnoughFunds()
+
+ # Remove unneeded inputs starting with the smallest.
+ selected.sort(key = lambda b: b.value)
+ dropped = []
+ for bucket in selected:
+ if value - bucket.value >= spent_amount + fee(size - bucket.size):
+ value -= bucket.value
+ size -= bucket.size
+ dropped.append(bucket)
+
+ return [bucket for bucket in selected if bucket not in dropped]
diff --git a/lib/wallet.py b/lib/wallet.py
@@ -627,15 +627,9 @@ class Abstract_Wallet(PrintError):
'height':tx_height,
'coinbase':is_cb
}
- coins.append((tx_height, output))
+ coins.append(output)
continue
- # sort by age
- if coins:
- coins = sorted(coins)
- if coins[-1][0] != 0:
- while coins[0][0] == 0:
- coins = coins[1:] + [ coins[0] ]
- return [value for height, value in coins]
+ return coins
def get_max_amount(self, config, inputs, fee):
sendable = sum(map(lambda x:x['value'], inputs))
