联合译者：Wendy, Lise

今天给大家带来的依然是一篇技术流的文章，该文章是由r/btc在2018年9月9日发表的，英文原文题目为：《A Technical Dive into CTOR》。

对CTOR的技术性解析

在过去几天里，我一直在深入探究CTOR的各个方面，其针对11月硬分叉所做的调整可谓声名狼藉。在这篇文章里，我要对CTOR的基本特质、代码形态、工作性能、算法以及前景进行具体的阐述。如果有人觉得CTOR的调整神秘且含糊不清，希望这篇文章能够为他们答疑解惑。

TTOR、CTOR及AOR分别是什么？

目前BCH区块的交易排序方式有多种可能。这其中交易拓扑排序规则（TTOR）指的是：对于有局部排序需求的交易必须依照因果关系进行排序，即如果一笔交易的支出(input)采用了另一笔交易的输出值（output)，那么这笔交易在区块里排序时必须在那一笔交易之后，在数学上这种排序被描述为区块内交易图的拓扑排序。

然而，将于2018年11月进行的BCH硬分叉计划将排序规则变更为交易规范排序规则(CTOR)，将对区块内一的交易集合，有效排序只有一种（因而称之为“规范”），未来任何偏离这一排序规则的区块将被视为无效。这一被加入到11月的硬分叉的升级功能，其实质是基于交易ID的一种字符排序（按字符顺序）。需要注意的是所有的交易均按交易ID的顺序排列，除了币基交易（coinbase),它必须始终排在最前面。交易规范排序规则的精确描述是“币基交易优先，然后根据交易ID进行升序排列”。

还有一种排规则被称为任意排序规则(AOR)，它则完全取消了对于交易排序的限制（除了币基交易依然必须在最前）。虽然尚未有人严肃地提出AOR提案，但这个规则在我们下面的谈论中这一排序规则很重要。

两个变化：取消旧有排序(TTOR->AOR)，安装新的排序(AOR->CTOR)。

预定于11月的升级将上述两个变化结合到一个步骤：

1.    取消旧有的因果规则：现在支出交易可以排在同一区块其使用的输出数据前面。

2.    增加修正区块中所有交易排序的新规则。

在本文当中我将这两个步骤(TTOR->AOR, AOR->CTOR)区分开来，因为我觉着这有助于阐明各个元素受到硬分叉调整的影响。

Bitcoin ABC的代码调整

BitcoinABC对从0.17.1版本升级的0.18.1版本（目前正在编写的版本）改变了几千条线的代码，其差别可以通过github查阅，这些调整绝大部分看似各种代码重构、代码风格变化等等，通过搜索”MagneticAnomaly"，可以找到11月硬分叉时将会激活的相应代码，变量magneticanomalyactivationtime 设定了新规将要激活的时间。

在文件 src/validation.cpp中可以找到交易排序相关的主要调整：

·       功能ConnectBlock 以前有一个回路，能够依次处理每笔交易，删除已达成交易的输出数据，加入新交易输出数据，该功能仅与TTOR兼容。从11月开始，它将采用双回路OTI算法（如下），新构造并无排序需求。

·       功能ApplyBlockUndo用于撤销孤立块，将被调整为适应任何排序。

·       功能ContextualCheckBlock将包含直接检查分类排序（仅有几行代码执行CTOR）

此外还有其他调整：

·       针对挖矿(src/mining.cpp)， CreateNewBlock将根据CTOR开始对交易进行分类。

·       当孤立一个区块时，交易将通过使用addForBlock返回内存池，现在该功能适用于任何排序(src/txmempool.cpp)。

算法

串行块处理（一个线程）

确认区块的最重要步骤之一是更新未使用交易输出(UTXO)集合，在这一过程当中如果探测到UTXO的双重支付，则宣告其无效。

比特币处理区块的标准方式是在交易当中一个接一个地循环，删除已用输出数据，然后加入新的输出数据。这种简单粗暴的方式需要精准的拓扑排序，否则就会失败（因此它自动校验了TTOR）。在伪代码当中：

for tx intransactions:

    remove_utxos(tx.inputs)

    add_utxos(tx.outputs)

值得注意的是，现代的实施方式不会马上应用这些调整，而是将增添/删除存进一个认可用量。在校验完成后，该认可用量适用于批次UTXO数据库。

通过将它分成两个回路，以不在意排序的方式更新UTXO集合成为可能，这被称为输出-然后-输入(OTI)算法。

for tx in transactions:

   add_utxos(tx.outputs)

for tx in transactions:

   remove_utxos(tx.inputs)

Bitcoin ABC的Jonathan Toomim和ElectrumX的我本人制定的标准表明，OTI的两个回路性能代偿（相对于一个回路版本）微不足道。

并行块处理

UTXO更新实际形成一个区块处理所需的重要时间片段，如果能将它们并行将大有助益。

有一些区块校验并行算法要求拟拓扑排序来正确行使功能。例如，一开始多个工作人员可以处理上述的标准回路，如果UTXO尚不存在，一位工作人员就要暂停，因为可能另一位工作人员将很快生成那个UTXO。

这类对排序敏感的并行块处理算法存在如下问题：

·       由于TTOR将成为共识规则，并行校验算法也必须在尊重TTOR的基础上进行验证。以上所述看似天真的方法实际能够胜任一些非拓扑排序，因此为了实行TTOR,需要增添额外的检验。

·       最坏情况下的表现是依次仅一个线程激活，要考虑下区块是一个由相互依赖交易组成的长链的情况。

比较而言，OTI算法回路是完全可并行的：工作线程可以以任意排序独立运行，并碰触交易。直到最近，OTI才被认为无法校验TTOR，因此撤销TTOR 的一个理由就是允许调整为并行OTI。然而事实证明这并不是真的：Jonathan Toomim已表示，通过在区块内记录新的UTXO索引，然后在撤销阶段比较索引，TTOR的实施可以轻而易举地实现。

无论如何，对我而言任何并行校验算法都需要这类额外代码，来确认TTOR的规则获得切实遵守，因此对于并行校验TTOR 最多算个障碍。

先进并行技术

随着BCH区块规模扩容到一定程度，或许有一天需要升级到包含分片技术的先进服务器结构，对这种可能性的讨论已经有很多，但开始为分片进行优化还确实尚早，在这种规模下，TTOR会没有帮助，CTOR能否实现性能优化还很难说。

区块传播繁殖（石墨烯）

现在BCH面临的主要瓶颈是区块传播繁殖。在压力测试期间，值得注意的是最大区块(~20 MB)要耗时数分钟在网络传播繁殖。由于传播延迟意味着孤立率升高，从而令挖矿的经济和激励机制恶化，这一点颇令人担忧。

 “石墨烯”是采用布隆过滤器和可逆布隆查阅数据表的一套对账技术，它彻底降低了传输区块所需的带宽数量。不幸的是，核心石墨烯机制并不提供排序信息，因此如果很多排序成为可能，那么排序信息就需要增添上去。对于大型区块而言，这种排序信息构成了石墨烯信息的主体。

为了缩小排序信息的大小，同时保持TTOR排序，矿工们可选择性决定按照规范排序（例如Gavin's order）排列交易，并且石墨烯协议可以是硬编码，以便这种特殊排序以一个字节传输，这可能为挖矿软件（以这种特别不寻常的排序生成区块）及石墨烯（必须检测这一排序，并能够将其重建）增添繁重的技术负担。我尚不清楚是否可能有效地将重建这些排序的分类算法并行化。

采用CTOR可以轻而易举解决这一切：因为只有一种排序，不需要额外增添排序信息，通过并行化优于拓扑分类的比较分类恢复排序，应该也能简化石墨烯币基，也不再需要开始考虑支持各种可选排序编码。

可逆性和技术负债

调整为CTOR是不是以后也会不了了之？一切皆有可能。

对于检验年代久远区块的区块验证器/资源管理器而言，撤销TTOR将永久取消标准串行处理算法的使用，这其实算不上问题（除了一时的不适），因为OTI看起来在串行中同并行一样有效。

对于涉及处理新区块的相关方（如石墨烯、网络协议、挖矿区块构建器、新区块校验），以后改变排序不是问题（改成AOR/TTOR，或再度恢复成CTOR或其他）。这些变化不会增添长期技术负债，因为它们仅牵涉新区块。对于过去的区块校验，它可以追溯性宣布旧的区块（时间超过几个月）没有排序需求。

总结和前景

·       由于其他区块处理软件需要进行相应的升级，以处理按任何排序进来的交易，撤销TTOR是升级中最具破坏性的部分。但这些调整非常微小，它们可以自然而然地将软件转化成并行可以轻而易举引入的形式。

·      TTOR/ CTOR近期对于区块校验不会显现明显的性能差异。现在明确了这一点，区块校验不会成为BCH的限制因素。

·       中期来看，软件切换为并行区块处理可能会更希望采用任意排序算法（例如OTI）。尽管在并行校验中要实行排序规则需要一些额外代码，TTOR / AOR / CTOR三者仍不存在性能差异。

·       从极其长远来看，CTOR 对于配备分片UTXO数据库的全节点而言展现出优势，如果有必要的话。总之，关心这个问题还为时过早。

·      随着TTOR 撤销，进一步加入CTOR实际是微乎其微的变化。它并不需要升级任何其他生态系统软件（它们并不在意排序）。不仅如此，我们不必非要接受CTOR:未来如果需要，排序可以轻而易举再度改变。

·      CTOR近期的基本改进会允许石墨烯协议简单、快速地实施，这将对当前重要的扩容瓶颈-区块传播繁殖造成影响。通过避开复杂自发性排序方案的话题，让石墨烯开发人员不再担心如何为排序编码，把精力集中在为设定对账优化机制。

广义上讲，石墨烯并非网络传播的灵丹妙药。即便是经过CTOR改良后的石墨烯，性能也不会马上获得重大提升。网络层也有工作要做，以便能实现节点间信息的快速传播。在最近的压力测试中，我们也看到了内存池性能（交易接受和分程传递）的局限。我希望能在下次压力测试之前看到这些方面获得优化，以便新的瓶颈能够显现。