比特币钱包怎么凑出你要付的钱：找币算法与 change 的隐形代价

比特币钱包里那个『余额』是最有欺骗性的数字。链上根本没有余额这个字段——只有无数个未花费输出（UTXO），每个都记录着『这 N 聪可以在此条件下被花掉』。你发起一笔付款时，钱包做的是一道组合题：从自己攒下的这堆碎钱里挑出一组，加总后覆盖收款金额与手续费，多出的部分作为找零回流到自己名下。这道题叫 coin selection（找币），答案的质量用三个指标衡量：这笔交易付多少手续费、给链上观察者泄露多少隐私信息、以及钱包里剩下的零钱结构未来几年还健不健康。多数人对钱包的全部认知停留在『它帮我扣数』，而 Bitcoin Core 的钱包内部藏着一整排带论文出处的组合优化算法——理解它们，你会同时理解为什么有时交易费意外地高、为什么有些钱包鼓励你合并小额零钱、以及『UTXO 整理』到底在整理什么。

问题的真实形状：输入不是余额而是重量

先建立计价模型。比特币手续费按交易的『重量』收，每个输入和输出都有固定尺寸：输入大约贡献几十到一百多权重单位，取决于签名类型。于是找币面对的是一个典型的多重子集和问题——目标金额固定，每个 UTXO 选或不选，代价函数既包括『选中输入的总重量乘以费率』，又包括一个经常被忽略的隐性项：找零输出本身也要钱。多一个找零输出意味着永久增加链上未花费集合的一个成员，它会在未来的每一次花费中被再次搬动、再次付费。好的算法把这件事看得和当次手续费一样重：能不产生找零就不产生，必须产生就尽量产生一个体面的、以后好花的数额，而不是随手落下三聪的尘埃。

BnB：寻找无找零的完美解

Bitcoin Core 首先尝试的是 Branch and Bound（BnB，分支定界）：在『每个 UTXO 选或不选』构成的二叉树上做带剪枝的深度优先搜索，寻找加总落在目标金额附近的子集——『附近』的判据苛刻到只差一个找零输出的创建与花费成本。找到这样的组合，交易连找零输出都不需要：输入恰好覆盖收款加费用，链上干净得没有余数。算法把候选按有效值排序、按 waste（浪费度）定序、遇超支即回退，搜索预算用尽前放弃则回落到备选。无找零交易是隐私的甜点：链上分析者面对两个输出的交易，常无法确定哪个是收款方哪个是找零——而三输出的版本里找零几乎无所遁形。这也是 Murch 在其论文中倡导『no-change』理想在工业实现里的落地：能消灭找零的机会一个都不放过。

CoinGrinder 与蓄水池：找不到完美解时的两种活法

搜索预算内没有无找零解时，钱包有两条退路。老资格的是蓄水池式（原文称 SRD，select random）方法：随机洗牌候选 UTXO 依次累加，越过目标就停，差额进找零——快、无脑，但产生的找零尺寸随机，运气差时余额里会攒下一堆几百聪的碎片，未来每次付款都被迫多付几倍的搬运费。较新的退路是 CoinGrinder：同样是子集搜索，但目标从『无找零』放宽为『找零落在预定的均匀区间』——与其留下一个随机尺寸的零头，不如刻意凑出一个『将来好用』的数额，并且优先从最小的 UTXO 开始消耗，把钱包的零钱堆系统性压薄。它和 BnB 共享树搜索骨架，参数与预算独立，两者都以『先试更好的解、超时降级』的姿态出场。三种策略的出场顺序构成一条务实的降级链：完美无找零优先，其次整理型凑整，最后才是随机抓一把——每一级都在用搜索时间换手续费或隐私，而时间上限的设定本身就说明这类问题在数学上属于『精确解昂贵、足够好的解廉价』的组合困难家族。

长期账本：尘埃、整理与外部性的公地

找币的每个决定都在写两本账。自己的那本直观：今天随手留下的找零是明天交易的固定成本，碎钱多的钱包每笔付款都在给过去的懒惰交税，定期把一堆小额 UTXO 合并成一笔干净输出的『整理』因此是钱包健康管理的正当动作——代价是合并交易本身的手续费与一次公开的结构性指纹。公共的那本账更隐蔽：每个找零输出、每颗尘埃（低于经济性的微额输出）都在膨胀全网 UTXO 集合，而这个集合驻留在每个全节点的内存里，是所有节点为陌生人的碎钱支付的公共服务费。这就是为什么费率估算、尘埃标准、钱包默认参数会被反复讨论：个人算法的最优（多留几个大 UTXO 少付当次费）若与协议层的外部性（UTXO 公地被碎钱填满）长期背离，成本最终摊回给所有人。Bitcoin Core 在找币与找零金额上的默认取向——优先消灭找零、优先消化小额、对尘埃设下限——可以读成协议设计者把外部性写进钱包代码的一次尝试。