Coin Selection

概述

Coin Selection（幣選擇）是決定使用哪些 UTXO 來支付交易的過程。 好的選擇算法可以最小化手續費、保護隱私、並維護錢包的長期健康。 這是錢包開發中最複雜的問題之一。

選擇目標

• 最小化手續費：選擇最少的輸入數量
• 避免找零：找零會增加輸出大小和未來成本
• 維護隱私：避免關聯不同的地址
• UTXO 健康：避免積累大量小額 UTXO（灰塵）
• 確認時間：優先使用已確認的 UTXO

選擇算法

Branch and Bound (BnB)

Bitcoin Core 的主要算法，嘗試找到精確匹配（無找零）：

目標：找到 UTXO 組合使得
sum(inputs) = target + fee

優點：
- 避免產生找零
- 長期降低 UTXO 集合大小
- 隱私更好（輸出數量少）

缺點：
- 不總是能找到精確匹配
- 計算複雜度較高

Knapsack (背包算法)

當 BnB 失敗時的備選方案：

策略：
1. 隨機選擇 UTXO
2. 嘗試多次組合
3. 選擇最接近目標的組合

優點：
- 總能找到解決方案
- 相對快速

缺點：
- 通常產生找零
- 非確定性（結果可能不同）

Single Random Draw (SRD)

簡單的隨機選擇：

策略：
1. 隨機打亂 UTXO 列表
2. 依序添加直到足夠
3. 產生找零

用途：
- 最後的備選方案
- 簡單實現

Lowest Larger

選擇最小的足夠 UTXO：

策略：
找到最小的 UTXO 使得 value >= target + fee

優點：
- 最簡單的實現
- 保留大額 UTXO

缺點：
- 可能產生大量小額找零
- 長期累積灰塵

Bitcoin Core 實作

選擇流程：

1. 過濾候選 UTXO
   - 移除未確認的（可選）
   - 移除鎖定的
   - 移除低於灰塵閾值的

2. 嘗試 Branch and Bound
   - 搜索精確匹配
   - 考慮費率範圍

3. 如果 BnB 失敗，嘗試 Knapsack
   - 1000 次隨機迭代
   - 選擇最佳組合

4. 如果 Knapsack 失敗，使用 SRD

5. 計算找零輸出（如需要）

TypeScript 實作

UTXO 類型定義

interface UTXO {
  txid: string;
  vout: number;
  value: number;        // satoshis
  scriptPubKey: Buffer;
  confirmations: number;
  addressType: 'p2pkh' | 'p2sh' | 'p2wpkh' | 'p2wsh' | 'p2tr';
}

interface SelectionResult {
  inputs: UTXO[];
  fee: number;
  change: number;
  effectiveFeeRate: number;
}

// 輸入大小（vBytes）
const INPUT_SIZES: Record<string, number> = {
  p2pkh: 148,
  p2sh: 91,      // P2SH-P2WPKH
  p2wpkh: 68,
  p2wsh: 104,    // 2-of-3 多簽
  p2tr: 57.5,
};

// 輸出大小（vBytes）
const OUTPUT_SIZES: Record<string, number> = {
  p2pkh: 34,
  p2sh: 32,
  p2wpkh: 31,
  p2wsh: 43,
  p2tr: 43,
};

費用計算

function calculateFee(
  inputs: UTXO[],
  outputs: number,
  feeRate: number,  // sat/vB
  changeType: string = 'p2wpkh'
): { fee: number; vsize: number } {
  // 基礎交易開銷
  let vsize = 10.5;  // 版本 + locktime + 輸入/輸出計數

  // 輸入大小
  for (const input of inputs) {
    vsize += INPUT_SIZES[input.addressType] || 68;
  }

  // 輸出大小（不含找零）
  vsize += outputs * OUTPUT_SIZES.p2wpkh;

  // 找零輸出
  vsize += OUTPUT_SIZES[changeType];

  const fee = Math.ceil(vsize * feeRate);

  return { fee, vsize };
}

function effectiveValue(utxo: UTXO, feeRate: number): number {
  const inputCost = (INPUT_SIZES[utxo.addressType] || 68) * feeRate;
  return utxo.value - inputCost;
}

Branch and Bound

interface BnBResult {
  success: boolean;
  selection?: UTXO[];
}

function branchAndBound(
  utxos: UTXO[],
  target: number,
  feeRate: number,
  costOfChange: number = 50  // 創建找零的額外成本
): BnBResult {
  // 按有效價值排序
  const sorted = [...utxos]
    .map((u) => ({ utxo: u, effective: effectiveValue(u, feeRate) }))
    .filter((u) => u.effective > 0)
    .sort((a, b) => b.effective - a.effective);

  const targetRange = {
    min: target,
    max: target + costOfChange,
  };

  let bestSelection: UTXO[] | undefined;
  let bestWaste = Infinity;

  function search(
    index: number,
    currentValue: number,
    currentSelection: UTXO[]
  ): void {
    // 剪枝：如果當前值已超過最大目標太多
    if (currentValue > targetRange.max + sorted[sorted.length - 1]?.effective) {
      return;
    }

    // 找到有效解
    if (currentValue >= targetRange.min && currentValue <= targetRange.max) {
      const waste = currentValue - target;
      if (waste < bestWaste) {
        bestWaste = waste;
        bestSelection = [...currentSelection];
      }
      return;
    }

    // 超出搜索範圍
    if (index >= sorted.length) {
      return;
    }

    // 剪枝：剩餘 UTXO 不足以達到目標
    const remaining = sorted
      .slice(index)
      .reduce((sum, u) => sum + u.effective, 0);
    if (currentValue + remaining < targetRange.min) {
      return;
    }

    // 包含當前 UTXO
    search(
      index + 1,
      currentValue + sorted[index].effective,
      [...currentSelection, sorted[index].utxo]
    );

    // 不包含當前 UTXO
    search(index + 1, currentValue, currentSelection);
  }

  search(0, 0, []);

  return bestSelection
    ? { success: true, selection: bestSelection }
    : { success: false };
}

Knapsack 算法

function knapsackSelection(
  utxos: UTXO[],
  target: number,
  feeRate: number,
  iterations: number = 1000
): UTXO[] {
  let bestSelection: UTXO[] = [];
  let bestExcess = Infinity;

  for (let i = 0; i < iterations; i++) {
    // 隨機打亂
    const shuffled = [...utxos].sort(() => Math.random() - 0.5);

    const selection: UTXO[] = [];
    let total = 0;

    for (const utxo of shuffled) {
      selection.push(utxo);
      total += effectiveValue(utxo, feeRate);

      if (total >= target) {
        const excess = total - target;
        if (excess < bestExcess) {
          bestExcess = excess;
          bestSelection = [...selection];
        }
        break;
      }
    }
  }

  return bestSelection;
}

完整選擇器

interface CoinSelectionOptions {
  target: number;           // 目標金額（satoshis）
  feeRate: number;          // sat/vB
  outputCount: number;      // 輸出數量
  changeType?: string;      // 找零地址類型
  minConfirmations?: number;
}

function selectCoins(
  utxos: UTXO[],
  options: CoinSelectionOptions
): SelectionResult | null {
  const {
    target,
    feeRate,
    outputCount,
    changeType = 'p2wpkh',
    minConfirmations = 0,
  } = options;

  // 過濾 UTXO
  const candidates = utxos.filter((u) => {
    if (u.confirmations < minConfirmations) return false;
    if (effectiveValue(u, feeRate) <= 0) return false;
    return true;
  });

  if (candidates.length === 0) {
    return null;
  }

  // 計算基本費用（不含輸入）
  const baseFee = (10.5 + outputCount * OUTPUT_SIZES.p2wpkh) * feeRate;

  // 嘗試 Branch and Bound
  const bnbResult = branchAndBound(
    candidates,
    target + baseFee,
    feeRate
  );

  let selectedInputs: UTXO[];

  if (bnbResult.success && bnbResult.selection) {
    selectedInputs = bnbResult.selection;
  } else {
    // 回退到 Knapsack
    selectedInputs = knapsackSelection(
      candidates,
      target + baseFee,
      feeRate
    );
  }

  if (selectedInputs.length === 0) {
    return null;
  }

  // 計算最終費用和找零
  const totalInput = selectedInputs.reduce((sum, u) => sum + u.value, 0);
  const { fee, vsize } = calculateFee(
    selectedInputs,
    outputCount,
    feeRate,
    changeType
  );

  const change = totalInput - target - fee;

  // 檢查找零是否為灰塵
  const dustThreshold = 546;
  const finalChange = change > dustThreshold ? change : 0;
  const finalFee = fee + (change > dustThreshold ? 0 : change);

  return {
    inputs: selectedInputs,
    fee: finalFee,
    change: finalChange,
    effectiveFeeRate: finalFee / vsize,
  };
}

灰塵處理

灰塵 (Dust) 定義:
花費 UTXO 的成本 > UTXO 的價值

灰塵閾值計算:
dustThreshold = (inputSize + 34) × 3 × minRelayFee

標準閾值:
- P2PKH: 546 satoshis
- P2WPKH: 294 satoshis
- P2TR: 330 satoshis

處理策略:
1. 避免創建低於閾值的找零
2. 將小額找零加入手續費
3. 考慮未來合併灰塵的成本

隱私考量

輸入合併問題

問題:
使用多個 UTXO 作為輸入會暴露它們屬於同一所有者

緩解策略:
1. 優先使用單個 UTXO
2. 只合併來自同一地址的 UTXO
3. 使用 CoinJoin

找零識別

分析者可以識別找零:
- 找零通常是較小的輸出
- 找零地址類型可能與輸入匹配

緩解策略:
1. 使用相同類型的地址
2. 使用 Paynym/靜態支付碼
3. 無找零交易（BnB）

批次支付

// 批次支付可以顯著降低每筆交易的手續費
function createBatchPayment(
  recipients: Array<{ address: string; amount: number }>,
  utxos: UTXO[],
  feeRate: number
): SelectionResult | null {
  const totalAmount = recipients.reduce((sum, r) => sum + r.amount, 0);

  return selectCoins(utxos, {
    target: totalAmount,
    feeRate,
    outputCount: recipients.length,
  });
}

// 範例：10 筆支付
// 單獨交易: 10 × (10.5 + 68 + 31) vB = 1095 vB
// 批次交易: 10.5 + 68 + (10 × 31) vB = 388.5 vB
// 節省: 65%

RPC 命令

# 列出可用 UTXO
bitcoin-cli listunspent

# 手動選擇 UTXO
bitcoin-cli createrawtransaction \
  '[{"txid":"...", "vout":0}]' \
  '[{"bc1q...": 0.001}]'

# 自動選擇（使用錢包）
bitcoin-cli walletcreatefundedpsbt \
  '[]' \
  '[{"bc1q...": 0.001}]'

# 設置手續費策略
bitcoin-cli settxfee 0.0001  # BTC/kB

最佳實踐

• 優先使用 BnB：盡量避免產生找零
• 定期整合 UTXO：在低手續費時期合併小額 UTXO
• 使用批次支付：多筆支付合併為一筆交易
• 考慮隱私：避免不必要的輸入合併
• 監控 UTXO 健康：追蹤 UTXO 數量和金額分佈

相關資源

• Coin Selection by Murch
• Bitcoin Core 源碼
• UTXO 模型
• Mempool