联合作者：Bighead, Algo, Lise
交易规范排序规则研究报告
事件背景
近期比特币社区一些开发团队在11月15日的BCH升级上，产生了一些技术上的分歧。
大体上分为两派：
以Bitcoin ABC开发团队为代表的一派主推交易规范排序（CTOR）替换原有的交易拓朴排序（TTOR），并且引入OP_DATASIGVERIFY脚本操作码；
以nChain开发团队为代表的一派主张将区块大小的上限提高至128M，并且未来将逐步提高区块上限直至撤销限制，同时恢复更多的比特币原始操作码，删除每个脚本201个操作码的限制。
此次技术升级上的分歧必将是POW共识机制在去中心化网络上的一次实践，也将成为比特币历史上一次重要的事件。
Rawpool.com作为BCH矿池，将深度参与此次各方升级版本的测试和评估，并将积极推动社区对于新技术的理解及认同，将以对BCH生态利益最大化为原则做出客观、公正的技术报告。
前提说明
通过对Bitcoin ABC 0.18.0 的研究发现，该版本中新增了CTOR排序，但TTOR排序并未去除，二者并存于代码当中。通常，新增额外代码只会造成性能劣化，不可能带来性能提升，所以我们放弃了对这个版本进行性能测试的计划。
对此，我们第一时间与ABC的工程师进行了沟通，询问其依然保留了TTOR代码的用意，他们给出的答复是：保留TTOR代码是为了维护升级前的兼容性，否则现有主链上的区块将无法校验。从维护兼容性的角度而言，这个答案有其合理性，但同时也证实了当前版本对于性能提升并无助益。
测评内容
本篇内容为对Bitcoin ABC发布的v0.18.0版本中的交易规范排序（CTOR）功能进行的代码评估。仅进行代码评估是由于此版本并未使用充分优化后的CTOR代码实现，因此无法进行实测。
特别声明
在关于CTOR代码和应用层面的一些问题，Rawpool与Bitcoin ABC的首席开发人员Amaury进行了多次邮件沟通，Amaury每次均及时回复邮件并且作出了详细解答，这里对Bitcoin ABC团队对社区参与者在技术上的支持表示赞赏和感谢！
Rawpool BCH Lab的报告内容仅针对区块链技术，对任何团体或利益相关方均无倾向。
欢迎发送邮件与我们的开发团队探讨交流：Hi@rawpool.com
概念解释
1､TTOR（Topological Transaction Ordering Rule)：称为交易拓朴排序规则，即交易之间形成依赖关系网。如下图的示例，如果B交易的输入用到了A交易的输出，那显而易见B交易是依赖A交易的。内存池中的交易之间普遍存在着错综复杂的依赖关系，可以用有向无环图来表示这种数据结构，也就是所说的拓扑图，如下：
图中的A交易叫做祖先交易(ancestor tx)，BCD都是他的子孙交易(descendant tx)，因为BCD的输入都用到了A交易的输出。同时可以看到C也是D的祖先交易，因为D的输入会用到C的输出。
如果对图中的4个交易进行排序的话，一个合理的排序可以是ABCD或ACDB或ACBD，但是绝对不可能是ABDC，因为子孙交易不允许出现排在祖先交易之前。
2､CTOR（ Canonical Transaction Ordering Rule）: 称为交易规范排序规则。这种排序规则非常简单直观，仅参考交易ID，即按照交易ID（十六进制的一串数字）的升序排序。
代码分析
1、CTOR的广泛评价
曼谷会议结束后，Rawpool的开发团队对Bitcoin ABC的v0.18.0版本中CTOR及TTOR的代码进行了分析。
在目前网络可以搜集到的关于CTOR的一些论文及其他技术文献中，几乎都提到了CTOR的性能更优，尤其在大量交易及大区块的情况下，比TTOR的优势更明显。另外还排除了一些攻击方法，但这是一个附加优势，因为截至目前，TTOR并没有出现过安全问题。
因此我们的研究主要集中在CTOR是否实现了交易排序的优化，并且它是否对整个网络有益或节约了资源。
在《Canonical Transaction Ordering for Bitcoin》这篇论文中，对时间复杂度给出了足够清晰的分析，论文中的结论是CTOR明显优于TTOR。
2、TTOR的排序处理
但是软件开发人员都会熟知，对于算法设计而言，针对不同需求，计算速度与存储空间的使用可以互换（trade off between speed and memory usage）。因此要使计算速度充分优化，必然导致存储空间的大量占用。
通俗地说：在代码实现层面为了追求更快的计算速度，往往会做很多优化，其中比较常见的一种就是用存储换取时间。比如原始数据按照需要存好几份，每一份可能结构都不一样，然后中间数据也有可能被存储下来，这样的好处就是每次需要计算的时候并不需要从头开始计算，只需要借助存储的力量，使计算量大幅度精简并且提升了整体计算速度。但是这种方式的缺点就是会占用较多的存储空间。
基于上述结论，我们可以推断在比特币交易的拓扑排序的处理中，交易在内存中的存储方式至关重要，直接决定了排序处理的速度。
下面我们来看一下bitcoind是如何实现排序的，以及他的交易数据是如何存储的。
首先定位到区块打包功能相关代码，如下：
对于排序的功能，只有这一句代码，简洁地调用了std::sort ，这个模版方法的最后一个参数是一个比较操作符，来确定优先级，跟踪到这个函数可以看到：
这里用到了CtxMemPool::GetCountWithAncestors方法，此方法只是一个属性读取符。
这里小结一下：被论述为性能开销很大的TTOR排序，在代码层面只是根据“祖先交易的数量”这个非常普通的整数进行排序，即哪笔交易的祖先多，就被认为交易辈分低，在排列中的次序也就靠后。
3、CTOR的排序处理
而被论述为性能比较好的CTOR排序规则，又是如何执行的呢？
CTOR的代码如下图所示：
CTOR排序是仅参考交易的ID，交易ID是一串数字，我们也可以把它认定为是一个整数值。
4、初步对比结论
CTOR排序算法与TTOR非常相似，区别仅在于CTOR依据“交易ID”排序，而TTOR依据“祖先数量”排序，但两者都是对“整数排序”而已。由此可以推断，就排序过程本身而言，二者的性能几乎完全一致。
然而，维护“交易ID”与维护“祖先数量”的性能差异，将成为这两种排序方法整体性能差异的决定性因素。
5、维护交易ID
“交易ID”本身就是一个随机值，没什么工作量，让我们深度看一看“祖先个数”这个值，便于更好的理解代码，先给出一个抽象总结后的图：
这里面涉及2个核心数据结构，一个是mapTx，是真正用来存储交易的字典，字典的Value是CtxMempoolEntry，Key有四个，分别是ID, fee, time, score
先来探讨“交易ID”，当前版本（0.18）的“交易ID”等价于交易的哈希值，不需要额外的工作量来维护。
6、维护祖先数量
再来探讨“祖先数量”，与此相关的数据结构有两个，mapTx和mapLinks，二者均为字典结构。我们下面会详细阐述这两个结构的代码：
（1) mapTx的Value是CtxMempoolEntry，Key有四个，分别是ID, fee, time, score
具体声明如下：
（2) 接下来为了便于更好的找到交易的祖先以及子孙，引入了另一个变量:mapLinks。
这也是一个字典，Key是交易ID，Value是一个结构体，其中包含了parents和children，这两个成员是集合类型，其中存放的是交易的迭代器即0号索引，这样的话，当我们知道一个交易的ID，第一时间就可以把此交易的祖先和子孙全部找出来，可谓非常高效，时间复杂度是O(1)。
那么这些数据信息什么时候会进行更新呢？那就是新的交易进入内存池或已存的交易离开内存池的时候。
当内存池有交易进出时，系统需要频繁的遍历当前交易的祖先交易，子孙交易，然后更新这些交易的信息，更新的内容就包含了之前说的“祖先个数”。这一套数据结构是非常优雅的设计，很好的用存储空间换取了计算时间。
Rawpool Lab结论
通过CTOR与TTOR二者代码层面的对比，我们注意到，TTOR排序算法隐含了维护交易祖孙关系的功能，而这恰恰是在UTXO共识模式下，必须要实现的基本功能。因此，在Bitcoin ABC 0.18.0版本代码中，即使新增了CTOR排序算法，只要尚未将维护祖孙关系的代码从TTOR排序代码当中剥离出来，就不能贸然移除TTOR代码。
当前的TTOR代码经历了长久的版本迭代过程，已积累了大量经验，形成了良好的算法设计，使得这部分代码非常高效，并且在当前的运行中，并未体现出它繁冗的计算给节点造成了负担。
针对CTOR与TTOR排序性能的比较，前提应是二者功能一致。TTOR排序隐含了维护交易祖孙关系功能，而CTOR排序并未包含维护交易祖孙关系功能。在不满足功能一致的前提下，就此进行比较没有意义。
不过，不能否认随着区块越来越大，交易越来越多，传统的TTOR排序必然会面临内存开销上涨、运算时间增大等问题。另一方面，充分优化后的CTOR排序（即包含了维护交易祖孙关系的CTOR排序，并且移除了TTOR排序）应是一套全新的数据维护体系，势必具有相当的复杂度，其能否在内存开销、运算速度等方面取得性能提升，目前无论在理论层面还是具体代码实现层面，均无法给出确定性结论。
探讨至此，我们不能忽视一个事实：UTXO共识模式下，交易祖孙关系的维护扎根于Bitcoind的骨髓，从TTOR算法到存储以及数据结构，均服务于UTXO共识。因此交易的祖孙关系会始终存在，而TTOR只是顺势而为进行排序操作。这就说明想要在维持祖孙关系的情况下，去除TTOR功能，应该需要对数据结构进行大规模整改，必须慎之又慎，ABC工程师也坦言近期不会大规模更改代码。
最后，如果Bitcoin ABC能够在升级时间点之前推出充分优化的CTOR测试版本，Rawpool将会第一时间进行评测。
Rawpool会持续与Bitcoin ABC和nChain的开发团队保持沟通，目前已完成测试节点的布署，将会积极参与新升级版本的测试及全网压力测试。
感谢阅读。
