import { Transaction } from '@bsv/sdk';
interface CoinSelectionStrategy {
select(utxos: UTXO[], targetAmount: number, feeRate: number): UTXO[];
}
// Strategy 1: Largest First (minimize number of inputs)
class LargestFirstStrategy implements CoinSelectionStrategy {
select(utxos: UTXO[], targetAmount: number, feeRate: number): UTXO[] {
const sorted = [...utxos].sort((a, b) => b.satoshis - a.satoshis);
return this.selectFromSorted(sorted, targetAmount, feeRate);
}
private selectFromSorted(sorted: UTXO[], target: number, feeRate: number): UTXO[] {
const selected: UTXO[] = [];
let total = 0;
for (const utxo of sorted) {
selected.push(utxo);
total += utxo.satoshis;
// Estimate fee for current input count
const estimatedFee = this.estimateFee(selected.length, 2, feeRate);
if (total >= target + estimatedFee) {
return selected;
}
}
throw new Error('Insufficient funds');
}
private estimateFee(inputs: number, outputs: number, feeRate: number): number {
// Rough estimate: 148 bytes per input, 34 bytes per output, 10 bytes overhead
const estimatedSize = (inputs * 148) + (outputs * 34) + 10;
return Math.ceil(estimatedSize * feeRate);
}
}
// Strategy 2: Smallest First (maximize UTXO consolidation)
class SmallestFirstStrategy implements CoinSelectionStrategy {
select(utxos: UTXO[], targetAmount: number, feeRate: number): UTXO[] {
const sorted = [...utxos].sort((a, b) => a.satoshis - b.satoshis);
const selected: UTXO[] = [];
let total = 0;
for (const utxo of sorted) {
selected.push(utxo);
total += utxo.satoshis;
const estimatedFee = this.estimateFee(selected.length, 2, feeRate);
if (total >= targetAmount + estimatedFee) {
return selected;
}
}
throw new Error('Insufficient funds');
}
private estimateFee(inputs: number, outputs: number, feeRate: number): number {
const estimatedSize = (inputs * 148) + (outputs * 34) + 10;
return Math.ceil(estimatedSize * feeRate);
}
}
// Strategy 3: Branch and Bound (optimal selection)
class BranchAndBoundStrategy implements CoinSelectionStrategy {
select(utxos: UTXO[], targetAmount: number, feeRate: number): UTXO[] {
// Sort descending by value
const sorted = [...utxos].sort((a, b) => b.satoshis - a.satoshis);
// Try to find exact match or minimal waste
const result = this.branchAndBound(sorted, targetAmount, feeRate);
if (result) {
return result;
}
// Fallback to largest first if no optimal solution
return new LargestFirstStrategy().select(utxos, targetAmount, feeRate);
}
private branchAndBound(
utxos: UTXO[],
target: number,
feeRate: number,
depth: number = 0,
selected: UTXO[] = [],
currentTotal: number = 0
): UTXO[] | null {
// Limit search depth to prevent timeout
if (depth > 20) return null;
const estimatedFee = this.estimateFee(selected.length, 2, feeRate);
const needed = target + estimatedFee;
// Found solution
if (currentTotal >= needed && currentTotal - needed < 1000) {
return selected;
}
// Exceeded target too much
if (currentTotal > needed + 10000) {
return null;
}
// No more UTXOs to try
if (depth >= utxos.length) {
return null;
}
// Try including current UTXO
const withCurrent = this.branchAndBound(
utxos,
target,
feeRate,
depth + 1,
[...selected, utxos[depth]],
currentTotal + utxos[depth].satoshis
);
if (withCurrent) return withCurrent;
// Try excluding current UTXO
return this.branchAndBound(
utxos,
target,
feeRate,
depth + 1,
selected,
currentTotal
);
}
private estimateFee(inputs: number, outputs: number, feeRate: number): number {
const estimatedSize = (inputs * 148) + (outputs * 34) + 10;
return Math.ceil(estimatedSize * feeRate);
}
}
// Strategy selector
class CoinSelector {
private strategies: Map<string, CoinSelectionStrategy> = new Map();
constructor() {
this.strategies.set('largest-first', new LargestFirstStrategy());
this.strategies.set('smallest-first', new SmallestFirstStrategy());
this.strategies.set('branch-and-bound', new BranchAndBoundStrategy());
}
select(
strategyName: string,
utxos: UTXO[],
targetAmount: number,
feeRate: number = 0.5
): UTXO[] {
const strategy = this.strategies.get(strategyName);
if (!strategy) {
throw new Error(`Unknown strategy: ${strategyName}`);
}
return strategy.select(utxos, targetAmount, feeRate);
}
}
// Usage
const selector = new CoinSelector();
const utxos: UTXO[] = [
{ txid: 'tx1', outputIndex: 0, satoshis: 5000, lockingScript: '...' },
{ txid: 'tx2', outputIndex: 0, satoshis: 10000, lockingScript: '...' },
{ txid: 'tx3', outputIndex: 0, satoshis: 25000, lockingScript: '...' },
{ txid: 'tx4', outputIndex: 0, satoshis: 50000, lockingScript: '...' }
];
// Use largest-first for minimal inputs
const selected1 = selector.select('largest-first', utxos, 30000, 0.5);
console.log(`Largest-first selected ${selected1.length} UTXOs`);
// Use smallest-first for UTXO consolidation
const selected2 = selector.select('smallest-first', utxos, 30000, 0.5);
console.log(`Smallest-first selected ${selected2.length} UTXOs`);
// Use branch-and-bound for optimal selection
const selected3 = selector.select('branch-and-bound', utxos, 30000, 0.5);
console.log(`Branch-and-bound selected ${selected3.length} UTXOs`);