@btc-stamps/tx-builder - v0.1.7
    Preparing search index...

    Class KnapsackSelector

    Knapsack UTXO Selection Algorithm - Legacy stochastic approximation

    The Knapsack selector implements Bitcoin Core's legacy UTXO selection algorithm (pre-2018) using a stochastic approximation approach. It runs multiple random iterations to find good solutions, making it highly reliable and capable of finding valid selections even when more sophisticated algorithms fail.

    The algorithm operates through multiple phases:

    1. Exact Match Search: First attempts to find precise combinations for changeless transactions
    2. Stochastic Iteration: Runs up to 1000 random trials, each selecting UTXOs with 50% probability
    3. Accumulative Fallback: If stochastic approach fails, uses simple largest-first accumulation

    Each iteration processes UTXOs from largest to smallest value, randomly including each with a configurable probability (default 50%). The algorithm tracks the best solution found across all iterations, preferring selections that minimize excess value over the target amount.

    The algorithm includes intelligent early exit conditions and prefers solutions that avoid creating dust outputs (change below 1000 satoshis threshold).

    Key features:

    • Highly reliable - always finds a solution when sufficient funds are available
    • Stochastic approach avoids local optima that deterministic algorithms might encounter
    • Configurable iteration count and inclusion probability for fine-tuning
    • Built-in exact match optimization for small UTXO combinations
    • Dust threshold handling to prevent unspendable change outputs
    • Accumulative fallback ensures solution availability
    • Maximum input constraints respected throughout selection process

    Performance characteristics:

    • Moderate performance, scales well with UTXO set size
    • Consistent execution time due to fixed iteration limit
    • Less optimal than modern algorithms but more predictable
    • Excellent fallback algorithm when others fail due to constraints
    const selector = new KnapsackSelector();
    const result = selector.select(utxos, {
      targetValue: 250000,  // 250,000 satoshis
      feeRate: 20,         // 20 sat/vB
      maxInputs: 8,        // Limit to 8 inputs max
      minConfirmations: 1   // Require confirmed UTXOs
    });

    if (result.success) {
      console.log(`Selected ${result.inputCount} UTXOs`);
      console.log(`Total value: ${result.totalValue} satoshis`);
      console.log(`Change: ${result.change} satoshis`);
    }

    // Configurable version with custom parameters
    const customSelector = new ConfigurableKnapsackSelector({
      iterations: 2000,           // More iterations for better results
      inclusionProbability: 0.3   // Lower probability for tighter selection
    });

    Hierarchy

    • BaseSelector
      • KnapsackSelector
    Index

    Constructors

    constructor

    Properties

    DUST_THRESHOLD INPUT_SIZE MAX_ITERATIONS OUTPUT_SIZE TRANSACTION_OVERHEAD

    Methods

    calculateChange calculateWaste checkOptionsValidity createResult estimateFee estimateTransactionSize filterEligibleUTXOs filterUTXOs getName isDust select sortByConfirmations sortByValue sumUTXOs validateOptions

    Constructors

    Properties

    DUST_THRESHOLD: 546
    INPUT_SIZE: 148
    MAX_ITERATIONS: number = 1000
    OUTPUT_SIZE: 34
    TRANSACTION_OVERHEAD: 10

    Methods

    • Calculate change amount

      Parameters

      • inputValue: number
      • targetValue: number
      • fee: number

      Returns number

    • Calculate waste metric for coin selection Lower waste is better

      Parameters

      • inputs: UTXO[]
      • targetValue: number
      • feeRate: number
      • longTermFeeRate: number = 10

      Returns number

    • Create selection result

      Parameters

      • inputs: UTXO[]
      • targetValue: number
      • feeRate: number
      • hasChange: boolean

      Returns SelectionSuccess

    • Estimate transaction fee

      Parameters

      • numInputs: number
      • numOutputs: number
      • feeRate: number

      Returns number

    • Estimate transaction size in vBytes

      Parameters

      • numInputs: number
      • numOutputs: number

      Returns number

    • Filter UTXOs based on confirmation requirements

      Parameters

      • utxos: UTXO[]
      • minConfirmations: number = 0

      Returns UTXO[]

    • Check if amount is dust

      Parameters

      • amount: number
      • OptionaldustThreshold: number

      Returns boolean

    • Sort UTXOs by value (ascending)

      Parameters

      • utxos: UTXO[]
      • descending: boolean = false

      Returns UTXO[]

    Settings

    Member Visibility

    On This Page

    Constructors
    Properties
    Methods