決定花費哪些 UTXO 的不同算法之間的權衡是什麼？
當有人想要進行交易時，他們的軟體必須選擇要花費的 UTXO。這裡有幾種不同的方式，人們可能會優先考慮使用哪些 UTXO。
- 首先是最舊的 UTXO
- 最新的 UTXO 優先
- 數量最少的 UTXO 優先
- 數量最多的 UTXO 優先
- 核心客戶端選擇算法：什麼是硬幣選擇算法？
- 其他的？
優先考慮 UTXO 支出的不同方式的權衡是什麼？有些更快嗎？有沒有讓區塊鏈變小（增長速度變慢）？是否有些使 UTXO 集更小？如何讓使用者支付最少的費用？考慮到所有這些因素，有沒有一種方法被普遍認為是最好的方法？
我喜歡的一種可能性是，在保持 1kb 最低費用限制的同時，花費盡可能多的 UTXO。這樣，如果節點修剪 STXO（已用交易輸出）的區塊鏈，它們可以修剪更多，這使得區塊鏈對它們來說更小。雖然，這可能會對保留整個區塊鏈的節點造成少量膨脹，所以這是一個權衡。
硬幣選擇的目標
選擇硬幣選擇算法的挑戰在於有多個目標需要優化：
隱私
錢包的預設行為應該合理有利於使用者的財務隱私。硬幣選擇應盡可能少地透露錢包內容。錢包應避免連結過多的地址，在不必要的時候不要透露過多的資金，盡量減少可辨識的模式和指紋，還要保持足夠的 UTXO 以分散餘額。錢包不應該重複使用地址。
手續費
硬幣選擇必須旨在降低目前交易的交易費用，但從長遠來看也要盡量減少總交易費用。由於最終必須花費每個 UTXO，因此有時現在以較低的費率花費更多的 UTXO 比以後以較高的費率花費更多的 UTXO 可能是合適的。
UTXO 池整形
應始終避免灰塵，但通常較小的 UTXO 在較高的費率下會產生較大的相對成本，因此我們應該努力避免產生微小的變化輸出。根據經驗，錢包不應該創建以中等費率花費大量價值的 UTXO。目標更改至少為 20–50k sats（較小的輸入腳本較少，較大的輸入腳本較多）。
縮減 UTXO 集大小
所有的 UTXO 都必須儲存在每個完整節點上，並且所有的 UTXO 最終都必須用完。錢包應保留足夠的 UTXO 以維護財務隱私，但應盡可能少以最小化未來的區塊鏈數據、費用和每個完整節點上的持續儲存成本。
不幸的是，其中一些目標是對立的，因此每個解決方案都必須為其優先級找到適當的平衡。
常用算法
讓我們回顧一下一些最常見的硬幣選擇算法，以及它們的優缺點。我們將看看：
- 最早的優先 (FIFO)
- Newest first (LIFO)
- 最小優先
- 最大優先
- 隨機的
- 背包（比特幣核心使用）
- 分支定界（Bitcoin Core 使用）
- 多算法（Bitcoin Core 使用）
最早的優先 (FIFO)
按確認計數遞減的順序選擇 UTXO。
好的
- 最終將在小型 UTXO 出現時進行整合
- 輸入集代表你的 UTXO 池的組成，既不是特別小也不是特別大
- 當採用新的輸出類型接收時，將錢包的 UTXO 池轉換為新的輸出格式
壞的
- 給出錢包中最舊的 UTXO 的日期，例如顯示使用者至少使用該錢包的時間
- UTXO 的值和確認計數間隔可用於估計總錢包餘額
- 不同交易的時間戳範圍可以形成一個串列模式，允許關聯同一個錢包的不同交易，並使用相同的軟體將其與其他錢包消除歧義（因為時間戳範圍不應重疊，除非在最後或第一個確認高度）
- 可用於通過觀察何時使用已知輸出來推斷有關錢包的資訊
- 不會最小化交易費用
Newest first (LIFO)
首先選擇確認數最少的 UTXO。
好的
- 大多數 UTXO 都有一個小的交易圖，這可能有利於隱私
- 花費的 UTXO 在獲取價值上最接近花費時間的價值，從而導致最小的有效收益/損失
壞的
- 如果錢包的資金隨著時間的推移而增加，那麼幾乎沒有任何整合
- 磨碎最新的 UTXO，直到收到更新的 UTXO 或用完。可能會導致錢包的 UTXO 池中有很多小的 UTXO。
- 當發送較大數量時，將結合多個最年輕 UTXO 的廣泛交易圖
- 將通過始終重用最新的更改輸出來連結您最近的所有活動
- 不會最小化交易費用
最小優先
按升值順序選擇 UTXO。
好的
- 盡快整合小型 UTXO，抑制錢包的 UTXO 池並最大限度地降低未來的支出成本
壞的
- 揭示錢包中目前 UTXO 值的下限
- 最大化輸入集，增加目前交易的交易費用
- 傾向於過度整合 UXTO 池，降低財務隱私
- 連結很多地址
- 降低錢包 UTXO 池的價值範圍
最大優先
按值降序選擇 UTXO。
好的
- 目前交易的最低交易費用
- 連結幾個地址
- 可能產生相當大的變化輸出
壞的
- 揭示錢包中 UTXO 值的上限
- 可能會顯示錢包持有的資金遠遠超過進行目前付款所需的資金
- 連結連續交易，而零錢輸出仍然是最大的 UTXO
- 推遲小型 UTXO 的整合，最大限度地提高未來成本
- 膨脹錢包的 UTXO 池（和全域 UTXO 集），因為單個接收者的支出通常在 UTXO 池計數上為 ±0（減去一個輸入，加上一個零錢輸出），但傳入的交易會增加 UTXO 池
隨機的
從所有可用的隨機抽取 UTXO 以相等的機會。
好的
- 選定的 UTXO 沒有一致的指紋，如年齡或價值
- 輸入集在機率上代表錢包的 UTXO 池組成，當存在更多小型 UTXO 時變得更加整合
- 易於實施
- 隨機變化輸出量增加價值多樣性
壞的
- 不減少費用
- 可能會隨機顯示一些指紋，例如顯示錢包中的資金比支付所需的多得多
背包（比特幣核心使用）
該算法（順便說一句，不能解決背包問題）通過按值對所有 UTXO 進行排序並執行 1000 次選擇迭代以從最大到最小的 50% 的機會隨機選擇 UTXO 來接近硬幣選擇。每當它超過目標時，它就會取消選擇最後包含的 UTXO 並繼續使用較小的 UTXO。什麼是硬幣選擇算法？.
好的
- 產生小型 UTXO 池
- UTXO 的偽隨機選擇揭示了關於錢包的少量資訊
壞的
- 積極整合微小的 UTXO，包括不經濟的輸出
- 始終以 10 mBTC 零錢輸出為目標（指紋和不必要的大）
- 錢包裡有很多小 UTXO，可能會導致大筆交易費用
- 不必要的昂貴計算
Branch and Bound（比特幣核心從 v0.17 開始使用）
確定性地在 UTXO 池的組合空間中搜尋最不浪費的避免更改的輸入集。由於並不總是存在不變的輸入集，因此在這種情況下，Bitcoin Core 會回退到使用上述“背包”方法。
好的
- 創建無變化輸出，降低目前費用、未來費用，減少錢包的交易圖，並對錢包的 UTXO 池產生鞏固作用
- 在可行的候選人中使用最少的輸入集，減少地址連結和費用
- 選定的 UTXO 沒有一致的指紋，如年齡或價值
- 由於浪費度量，在較低的費率下使用更多的輸入，在較高的費率下使用較少的輸入
- 由於浪費度量，更喜歡在較低的費率下花費較少的塊空間高效輸出類型，而在較高的費率下花費更高效的輸出類型
壞的
- 並不總是產生解決方案
- 發件人不能 CPFP，因為沒有找零輸出
- 實現更複雜，計算成本更高
多算法（Bitcoin Core v23+ 使用）
Bitcoin Core 22.0 之後的下一個版本將並行執行 Knapsack、Single Random Draw 和 Branch and Bound 硬幣選擇，然後在三個生成的輸入集候選者中根據浪費啟發式選擇得分最高的一個，這在以前已經用於選擇最佳的分支定界解決方案。
好的
- 在低費率下花費更多投入，在高費率下花費更少，從而降低總費用
- 在經濟合理的情況下整合少量投入
- 由於輸入集來自多種方法，因此模式更難辨識
- 經常避免改變，改善隱私、費用和減少聯繫
壞的
- 實施和測試複雜
- 計算密集型計算
- 仍然使用 10 mBTC 的相當高的最小變化（產生變化時）
2021 年 11 月更新：
- 刪除術語“灰塵”的模棱兩可使用
- 完全重寫以更新我目前的理解
- 添加隨機選擇、分支定界和比特幣核心的多算法方法
2021 年更新：
- 刪除了在 2016 年比特幣核心 0.12.0 中刪除了在區塊建構中將硬幣時代優先作為交易選擇策略的一些暗示。
- 刪除了從同一地址花費多個輸入更便宜的錯誤說法
請注意，直到 2017 年，Bitcoin Core 使用背包求解器作為其唯一的算法，但此後添加了此答案作者提出的改進算法。
2014 年更新：
我一直在尋找一種更好的硬幣選擇算法，但還沒有找到一種可以顯著改進核心客戶端選擇算法的算法。
以下是一些改進它的想法：
- 當隨機選擇一個 UTXO 時，也添加與同一地址關聯的所有其他 UTXO：更少的交易連結可以提高隱私性，可能會將 UTXO 合併到更少。
- 與其選擇最小的變化，不如創建與支出目標相同大小的變化。假設人們主要發送有用的金額，這將創建具有有用價值的新 UTXO，而不是像目前那樣進行最小可能的更改。這也使得猜測變化是什麼以及付款是什麼變得更加困難。
- 選擇 UTXO 集以最小化交易費用，而不是最小化零錢輸出。