def select_coins(target, fee, output_size, min_change, *, absolute_fee=False,
                 consolidate=False, unspents):
    '''
    Implementation of Branch-and-Bound coin selection defined in Erhart's
    Master's thesis An Evaluation of Coin Selection Strategies here:
    http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

    :param target: The total amount of the outputs in a transaction for which
                   we try to select the inputs to spend.
    :type target: ``int``
    :param fee: The number of satoshi per byte for the fee of the transaction.
    :type fee: ``int``
    :param output_size: A list containing as int the sizes of each output.
    :type output_size: ``list`` of ``int`
    :param min_change: The minimum amount of satoshis allowed for the
                       return/change address if there is no perfect match.
    :type min_change: ``int``
    :param absolute_fee: Whether or not the parameter ``fee`` should be
                         repurposed to denote the exact fee amount.
    :type absolute_fee: ``bool``
    :param consolidate: Whether or not the Branch-and-Bound process for finding
                        a perfect match should be skipped and all unspents
                        used directly.
    :type consolidate: ``bool``
    :param unspents: The UTXOs to use as inputs.
    :type unspents: ``list`` of :class:`~bit.network.meta.Unspent`
    :raises InsufficientFunds: If ``unspents`` does not contain enough balance
                               to allow spending matching the target.
    '''

    # The maximum number of tries for Branch-and-Bound:
    BNB_TRIES = 1000000

    # COST_OF_OVERHEAD excludes the return address of output_size (last element).
    COST_OF_OVERHEAD = (8 + sum(output_size[:-1]) + 1) * fee

    def branch_and_bound(d, selected_coins, effective_value, target, fee,
                         sorted_unspents):  # pragma: no cover

        nonlocal COST_OF_OVERHEAD, BNB_TRIES
        BNB_TRIES -= 1
        COST_PER_INPUT = 148 * fee  # Just typical estimate values
        COST_PER_OUTPUT = 34 * fee

        # The target we want to match includes cost of overhead for transaction
        target_to_match = target + COST_OF_OVERHEAD
        # Allowing to pay fee for a whole input and output is rationally
        # correct, but increases the fee-rate dramatically for only few inputs.
        match_range = COST_PER_INPUT + COST_PER_OUTPUT
        # We could allow to spend up to X% more on the fees if we can find a
        # perfect match:
        # match_range += int(0.1 * fee * sum(u.vsize for u in selected_coins))

        # Check for solution and cut criteria:
        if effective_value > target_to_match + match_range:
            return []
        elif effective_value >= target_to_match:
            return selected_coins
        elif BNB_TRIES <= 0:
            return []
        elif d >= len(sorted_unspents):
            return []
        else:
            # Randomly explore next branch:
            binary_random = randint(0, 1)
            if binary_random:
                # Explore inclusion branch first, else omission branch:
                effective_value_new = effective_value + \
                    sorted_unspents[d].amount - fee * sorted_unspents[d].vsize

                with_this = branch_and_bound(
                    d + 1,
                    selected_coins + [sorted_unspents[d]],
                    effective_value_new,
                    target,
                    fee,
                    sorted_unspents
                )

                if with_this != []:
                    return with_this
                else:
                    without_this = branch_and_bound(
                        d + 1,
                        selected_coins,
                        effective_value,
                        target,
                        fee,
                        sorted_unspents
                    )

                    return without_this

            else:
                # As above but explore omission branch first:
                without_this = branch_and_bound(
                    d + 1,
                    selected_coins,
                    effective_value,
                    target,
                    fee,
                    sorted_unspents
                )

                if without_this != []:
                    return without_this
                else:
                    effective_value_new = effective_value + \
                        sorted_unspents[d].amount - fee * sorted_unspents[d].vsize

                    with_this = branch_and_bound(
                        d + 1,
                        selected_coins + [sorted_unspents[d]],
                        effective_value_new,
                        target,
                        fee,
                        sorted_unspents
                    )

                    return with_this

    sorted_unspents = sorted(unspents, key=lambda u: u.amount, reverse=True)
    selected_coins = []

    if not consolidate:
        # Trying to find a perfect match using Branch-and-Bound:
        selected_coins = branch_and_bound(
            d=0,
            selected_coins=[],
            effective_value=0,
            target=target,
            fee=fee,
            sorted_unspents=sorted_unspents
        )
        remaining = 0

    # Fallback: If no match, Single Random Draw with return address:
    if selected_coins == []:
        unspents = unspents.copy()
        # Since we have no information on the user's spending habit it is
        # best practice to randomly select UTXOs until we have enough.
        if not consolidate:
            # To have a deterministic way of inserting inputs when
            # consolidating, we only shuffle the unspents otherwise.
            shuffle(unspents)
        while unspents:
            selected_coins.append(unspents.pop(0))
            estimated_fee = estimate_tx_fee(
                sum(u.vsize for u in selected_coins),
                len(selected_coins),
                sum(output_size),
                len(output_size),
                fee
            )
            estimated_fee = fee if absolute_fee else estimated_fee
            remaining = sum(u.amount for u in selected_coins) - target - estimated_fee
            if remaining >= min_change and (not consolidate or len(unspents) == 0):
                break
        else:
            raise InsufficientFunds('Balance {} is less than {} (including '
                                    'fee).'.format(sum(
                                        u.amount for u in selected_coins),
                                        target + min_change + estimated_fee))

    return selected_coins, remaining
def select_coins ( target , fee , output_size , min_change , * , absolute_fee = False , consolidate = False , unspents ) : BNB_TRIES = 1000000 COST_OF_OVERHEAD = ( 8 + sum ( output_size [ : - 1 ] ) + 1 ) * fee def branch_and_bound ( d , selected_coins , effective_value , target , fee , sorted_unspents ) : nonlocal COST_OF_OVERHEAD , BNB_TRIES BNB_TRIES -= 1 COST_PER_INPUT = 148 * fee COST_PER_OUTPUT = 34 * fee target_to_match = target + COST_OF_OVERHEAD match_range = COST_PER_INPUT + COST_PER_OUTPUT if effective_value > target_to_match + match_range : return [ ] elif effective_value >= target_to_match : return selected_coins elif BNB_TRIES <= 0 : return [ ] elif d >= len ( sorted_unspents ) : return [ ] else : binary_random = randint ( 0 , 1 ) if binary_random : effective_value_new = effective_value + sorted_unspents [ d ] . amount - fee * sorted_unspents [ d ] . vsize with_this = branch_and_bound ( d + 1 , selected_coins + [ sorted_unspents [ d ] ] , effective_value_new , target , fee , sorted_unspents ) if with_this != [ ] : return with_this else : without_this = branch_and_bound ( d + 1 , selected_coins , effective_value , target , fee , sorted_unspents ) return without_this else : without_this = branch_and_bound ( d + 1 , selected_coins , effective_value , target , fee , sorted_unspents ) if without_this != [ ] : return without_this else : effective_value_new = effective_value + sorted_unspents [ d ] . amount - fee * sorted_unspents [ d ] . vsize with_this = branch_and_bound ( d + 1 , selected_coins + [ sorted_unspents [ d ] ] , effective_value_new , target , fee , sorted_unspents ) return with_this sorted_unspents = sorted ( unspents , key = lambda u : u . amount , reverse = True ) selected_coins = [ ] if not consolidate : selected_coins = branch_and_bound ( d = 0 , selected_coins = [ ] , effective_value = 0 , target = target , fee = fee , sorted_unspents = sorted_unspents ) remaining = 0 if selected_coins == [ ] : unspents = unspents . copy ( ) if not consolidate : shuffle ( unspents ) while unspents : selected_coins . append ( unspents . pop ( 0 ) ) estimated_fee = estimate_tx_fee ( sum ( u . vsize for u in selected_coins ) , len ( selected_coins ) , sum ( output_size ) , len ( output_size ) , fee ) estimated_fee = fee if absolute_fee else estimated_fee remaining = sum ( u . amount for u in selected_coins ) - target - estimated_fee if remaining >= min_change and ( not consolidate or len ( unspents ) == 0 ) : break else : raise InsufficientFunds ( 'Balance {} is less than {} (including ' 'fee).' . format ( sum ( u . amount for u in selected_coins ) , target + min_change + estimated_fee ) ) return selected_coins , remaining
Implementation of Branch-and-Bound coin selection defined in Erhart's
    Master's thesis An Evaluation of Coin Selection Strategies here:
    http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

    :param target: The total amount of the outputs in a transaction for which
                   we try to select the inputs to spend.
    :type target: ``int``
    :param fee: The number of satoshi per byte for the fee of the transaction.
    :type fee: ``int``
    :param output_size: A list containing as int the sizes of each output.
    :type output_size: ``list`` of ``int`
    :param min_change: The minimum amount of satoshis allowed for the
                       return/change address if there is no perfect match.
    :type min_change: ``int``
    :param absolute_fee: Whether or not the parameter ``fee`` should be
                         repurposed to denote the exact fee amount.
    :type absolute_fee: ``bool``
    :param consolidate: Whether or not the Branch-and-Bound process for finding
                        a perfect match should be skipped and all unspents
                        used directly.
    :type consolidate: ``bool``
    :param unspents: The UTXOs to use as inputs.
    :type unspents: ``list`` of :class:`~bit.network.meta.Unspent`
    :raises InsufficientFunds: If ``unspents`` does not contain enough balance
                               to allow spending matching the target.