优化比特币生成交易代码

最近，我需要从几个机器中生成许多交易，以模拟区块非常大的比特币网络。因为我创建了几个使用bitcoind的“sendtoaddress”API的简单脚本，我无限循环地启动这些脚本，看看会发生什么。

结果不令人满意。想知道为什么会这样，你必须要理解“未确认输入”的问题。基本上，如果你使用事先付款一小部分，那么你会生成2个新的输出——一个输出到您的目的地、一个输出给自己（找零）。然后这些输出会被认为是“未确认的”，直到新区块被找到，然后您才可以再次使用这些未确认的输出，但是比特币客户端在返回“太多未确认的输出”的错误之前，只允许用户构建一个相对较短的未确认输出链。（译者注：最后一句原文butBitcoin client only lets you build a relatively shallow chain of unconfirmedoutputs before it returns a “too many unconfirmed outputs” error.）

我将从每个区块的单个钱包中生成50000多笔交易，所以我很快意识到我需要一个类似于确认输出的办法，以可靠地生产许多支付行为。

占用了100％的CPU，交易生成速度减慢到每10秒左右1个交易。这是个问题。虽然我是人为地造成了这种情况，但是对于一个大型企业来说，这真的是一个不太可能的数量吗？我猜，大企业每年处理数百万的付款，重新使用地址并非解决之道——问题是钱包中交易输出的数量，而不是地址的数量。

所以我考虑优化交易代码。最终，我能够提高生成交易的效率，提高了约1000倍，而且有助于减少UXTO的增长。详情请往下看！

增量优化

我注意到的第一件事是大量时间被花费在锁定（locks）。特别是在HaveKey（）和GetTimeOffset（）。这种行为通常发生在在“内部”循环里采用和解除锁定的时候，而不是在循环开始和结束时采用一次锁的时候。毫无疑问，我发现了一个在CWallet:: AvailableCoins（...）中的紧密循环。所以，我添加了IsMine的无锁定版本，将LOCK（cs_KeyStore）移到循环之外，有了大概5-10％的改进。

如前所述，我也注意到GetTimeOffset（）消耗了大量的CPU……嗯……它再次采用锁定。这一次的目的是确保64位变量的atomic read。在所有CPU体系结构上有更好的方法可以达到这个目的，所以我通过支持的编译器上的原子64位操作更换锁定：

int64_tGetTimeOffset()
{
int64_t t1;
#ifdef __GNUC__ // BU optimze—doa barrier rather than a lock
t1 = __sync_fetch_and_add(&nTimeOffset,0);
#else
LOCK(cs_nTimeOffset);
t1 = nTimeOffset;
#endif
return t1;
}

这个问题也可以通过把GetTimeOffset（）因素包括进去，调用内部循环来解决，但代码结构使得那样做不合适，所以我选择这种方法实现另外5-10％的改进。

虽然这些修补程序是对子系统的一个好的介绍，但它不会使我实现自己的目标。为了真正解决这个问题，我需要回顾大的实施决策。

实现优化

第一个显著的问题是，每次付款时，整个钱包都被提取到一个向量(vector)中（请参见SelectCoins（）调用CWallet ::AvailableCoins（））。而且这个向量在这里通过价值（也就是复制）被多次传递。由于这个bitcoind通常是从这个钱包支付的唯一实体，并且因为我们在结束的时候进行最后交易有效性检查，所以在周围保持一个“可用”的TXO数据结构是安全的，而且只是删除TXO用作付款的功能。一般的，如果代码大小小于一个常数，代码将重新生成这个结构。和通过添加新的TXO进来以及固定区块重组等、试图保证该结构总是与钱包完全一致相比，这样做更为简单，而且不会显著影响小钱包，因为小钱包可以很快地重新生成数据结构。

第二个效率瓶颈是代码验证钱包包含是否足够的资金来满足从构建交易中分开支付的要求。问题是为了做到这一点，代码必须统计钱包中的所有输出——所以通过整个钱包的TXO集，再次迭代。一般来说，如果测试一个异常条件是昂贵的，而且迟早会被发现的话，那么最好是在性能瓶颈的代码中后出现。另一种方法是缓存钱包的当前余额，并根据流入和流出的资金进行更新而不是重新计算。但同样，这种方法需要很多脆弱的代码来确保一致性。

最后，CWallet:: CreateTransaction中的代码具有明显的低效率。首先，假设没有交易费，它总是会运行货币选择(译者注：这里的‘运行货币选择’对应的原文是‘runthe coin selection’)。考虑到区块大小限制和最近添加到BitcoinCore的其他费用代码（稍后详述），这是完全荒谬的。第二，如果代码猜错了交易费，代码将用更多的费用重新运行货币选择，即使所选择的输入实际上有足够金额支付的实际交易费用！（看这里和这里）

 

算法优化

优化工具箱中的最终性能选项是要问“这个算法是否真的实现了我的目标？”我考虑的越多，我越意识到它没有实现目标。所实现的算法试图解决“背包问题”——主要问题是选择不超过特定比重的“东西”的最大值。对于比特币钱包，问题是类似但是不同的：它是选择一组大于交易值的输入，但试图尽可能密切地匹配输入和输出的值。“背包问题”是非常困难的——它被证明是NP难题。然而，我意识到比特币有一个让它毫无价值的额外麻烦——“背包问题”的大小（交易价值）以交易费为基础，而且费用是未知的，直到整个交易被序列化。

最终结果是，如果优化器通过查找接近输出值的一组输入来完成得“很好”，那么它将无法包括交易手续费，因此交易将被拒绝。在这种情况下，代码将计算费用添加到交易金额里，然后再次尝试。然而，这没有任何意义。先前解决方案和下一个解决方案的大小并没有实际关系。相反，由于交易的一般相似性，这只是操作——如果你知道交易中输入和输出，你就可以粗略估计其大小。

事实上，在我的测试中，背包优化器几乎每次都被要求支付几次。

优化这个“背包问题”的目的是什么？谁关心.1或.0001的变化是否被接纳？未能找到确切解决方案的惩罚是额外的输出变化，并且不管遗漏了什么算法，障碍都完全相同。是的，精确匹配保存输出，但给定6到10位数字（1比特币是100,000,000 Satoshi，代码、Satoshi中的计数）的可能性很小。特别是因为交易费用对每次付款增加了一个小的非圆数值（non-round-number），所以我们真的是在处理6到10位数字，而不是尾部有大量零的3位数字。该算法没有太多的灵活性——使用大量的输入会有一个真正的障碍。最后，对于用户来说，一个相近差错实际上是一个微小的错误，而不是一个大错误，因为在相近差错的情况下，代码将这个“灰尘”转化为交易费用而不是生成输出。但更大的错误向改变地址支付剩余的金额…

所以很明显，货币选择优化错了东西。

那么，货币选择实际应该优化什么？在今天比特币的背景下，这个问题的答案变得很明显。货币选择应该最小化UTXO集，它不会明显影响交易费用。换句话说，它应该尝试消耗更多的TXO输入，而不是产生输出，并且在理想的情况下，通过不会妨碍交易的更大输入，在交易中使用一些钱包的near-dust输出。[隐私倡导者可能会感到震惊——钱包不应该试图将数字货币分开，以混淆区块链分析？对于这个问题我这样回应：依赖于算法是非常危险的，因为它必须结合这些输出从而创建一个交易。许多钱包采取了更好的方法，这是为了让你将你的钱包分成不会混合的“帐户”或子节]

 

新算法

新算法非常简单，因为目的不再是解决NP难题，而是最小化UTXO集和最大化效率。

通过在按输出值分类的容器中存储所有钱包输出，它开始“离线”。每次收到付款请求时，此容器都不会从钱包中重新载入。反而只有包含少于几百个TXO时，它才会重新加载。

当收到付款请求时，考虑到合理数量的输入和输出，它首先估计交易费用并将其添加到请求的值。让我们称之为“目标值”。然后它简单地选择大目标值的最小TXO并且将其存储为解（如果没有一个解，它会与最大的TXO结合，直到找到解，要么是一切没有可能）。然后它向后迭代，选择小于这个目标值的TXO。对于当中的每一个TXO来说，它创建一个新的目标值=目标值-TXO值，并递归构建出多于可配置TXO数量的解集。同时，它选择随机TXO并尝试相同的算法。这确保算法考虑到很多不同值的TXO，特别是在后向迭代器可能通过一组微小的值变化来实现操作的情况下。

在一堆迭代之后，或者如果算法“接近”目标值（所需的迭代次数越多，对于“接近”意味着什么我们就越放松），则返回最佳解。

整个算法在大约200行代码中实现。

其他想法

用户似乎在抱怨的一件事是：手续费占比很大。这是显而易见的——没有人愿意支付5-20％。倒不如使用信用卡。那么为什么在代码中不包括一些检查？它必须是复杂的，对吧？不对。

结果

该算法在“标准的”2GHZ笔记本电脑硬件和VM内部中支持每秒20次付款，并且只占用百分之几CPU（当我发现什么是阻止更大的流量时，我将更新这个文件——但可能是把钱包变化写入到磁盘里）。因此，流量大约是用于测试的钱包大小的原始算法的200倍，而且最重要的是流量随着钱包大小的日志增加，而不是以指数方式增加。原始算法占用100％的CPU，而这个算法最大占用10％——因此效率大约是是原始算法的1000倍。

假定钱包有10000多个从1 mBTC到10 BTC的随机TXO，它大多选择2到4个输入以及支付2个输出（输出+变化）。因此，UTXO大小要么保持不变要么减小。

还要完成更多的分析，包括明显比较其TXO选择结果与原始算法。然而，这个代码很容易达到我测试非常大的区块的目标，所以我觉得是时候写这篇文章了。

为了改善用户体验以及创建实验一个完全验证的、企业友好型的比特币钱包，在交易创建上显然还有做很多努力。正如我所想的和我所展示的，这些变化也可以通过比其他解决方案更简单的方式激励更好的钱包行为（例如UTXO膨胀控制）。而且已经尝试最小化UTXO膨胀的算法将可能地处理同样优先减少UTXO交易的矿工算法。

有时间和精力，这种变化就有可能发生。有足够的变化——关注于用户体验和使比特币客户端为企业所用的变化——实际上我们可能会发现节点数增加！