CTOR是否有助于BCH分片技术？

目前，BCH社区内部对于我们是否需要所谓的交易规范排序（CTOR），以及当前的交易拓扑排序（TTOR）是否应该被它取代存在较大的分歧。许多人不相信其优势，这是可以理解的。不过，CTOR的支持者对此做出了一个承诺，CTOR可以简化“分片技术”，即可以在多台机器上完成的工作的分配。让我们看看这个说法是否站得住脚。我会首先对分片技术和比特币节点如何工作进行解释，如果您已经对此比较熟悉，可以随意跳过。

如何进行分片？

让我们先看一个简单的例子，以便更好地理解分片技术在实践中的工作原理。假设运行一个提供图像的网站，上面有数十亿张图像。用户可以通过名称访问这些图像，例如“cat.png”或“house.jpg”。然而，由于图像太多，单个计算机无法合理地处理它们。所以我们应该使用多台计算机。

对图像进行分类的一种简单的方法是使用首字母，这样我们就可以为字母表中的每个字母分别提供一个服务器：服务器A, 服务器B，……服务器Z。如果用户寻找“cat.png”，我们知道这个图像存储在服务器C上(如果图像存在的话)，并将图像从服务器提供给用户。

当然，这种方法也有它的不足之处。英文中按首字母排序的词分布的并不均匀，T的频率是16%，Z的频率只有0.05%。这意味着服务器T将比服务器Z繁忙320倍！这是很糟糕的分片。

为了解决这个问题，我们可以使用哈希值来代替图像的名称，它应该是均匀分布的。

比特币节点是怎么工作的呢？

现在让我们回到比特币。在白皮书中，它表示节点执行以下操作：

1) 新的交易向全网进行广播；

2) 每一个节点都将收到的交易信息纳入一个区块中；

3) 每个节点都尝试在自己的区块中找到一个具有足够难度的工作量证明；

4) 当一个节点找到了一个工作量证明，它就向全网进行广播；

5) 当且仅当包含在该区块中的所有交易都是有效的且之前未存在过的，其他节点才认同该区块的有效性；

6) 其他节点表示他们接受该区块，而表示接受的方法，则是在跟随该区块的末尾，制造新的区块以延长该链条，而将被接受区块的随机散列值视为先于新区快的随机散列值。

然而，这个列表并不包含验证交易是否有效的重要步骤。

我们通过一些简单的规则来验证交易（有效格式，花费不能超过所包含的输入等）和以下（简化）规则：

对于交易的每一个输入，我们需要检查是否允许在输入中使用引用的输出。我们查找引用的输出，并检查它是否未使用，我们将输入脚本添加到输出脚本中，是否会得到“是的，您可以使用它!”的结果。

换句话说，我们遍历交易中所有输入，找到该输入所引用的交易，然后选择我们所要检查的输入所引用的交易的输出，并验证它是否是有效的以及我们当前的输入是否包含花费引用输出所需要的必要签名。如果没有，则放弃交易，因为它是无效的。

在验证之后，我们将执行1）（广播交易），2）（将它们纳入到一个区块中）和3）（进行挖矿）。请注意，挖矿并不是将区块中的实际交易（可能是兆字节）存储在硬盘中，而是将“merkle root ”（以及其他一些东西，总共80字节）存储在硬盘中。但是我们如何获得merkle root？

为了得到merkle root，我们列出一行中的所有交易，并将它们的ID进行两两哈希，这将生成一个只有原始列表大小一半的新列表。然后我们对新列表执行同样的操作：对它们的哈希值进行两两哈希。持续这样做，直到只留下一个哈希—— 这是我们的merkle root：

为简洁起见，我们在本文中省略4）（广播区块），5）（验证区块）和6）（在区块的基础上进行挖矿）。尽管CTOR对它们的影响很大，但是这对分片技术的影响并不那么重要。

对节点进行分片

我问自己，一旦我们有了CTOR，将如何实施分片。从某种意义上说，“order”意味着我们在创建一个merkle root之前对交易ID是如何排序的。即使所有交易都是相同的，不同的顺序也将产生不同的merkle root，因此顺序很重要。

让我们快速了解一下CTOR和TTOR的不同之处。

TTOR（交易拓扑排序）按拓扑顺序对交易进行排序：如果一个交易依赖于另一个交易，则这个交易要排列在那个依赖交易之后即母交易要放在子交易的前面。除了该限制外，交易可以任意排序。

CTOR（交易规范排序（确切地说它是字典交易顺序））按其ID对交易进行排序。由于交易ID都是独一无二的，因此始终会产生唯一的顺序。

CTOR基础下的分片

如果我们有CTOR，我们将如何对比特币节点进行分片呢？与上面描述的图像服务的示例一样，我们可以使用交易ID的字母进行切分。有16个不同的十六进制数字，所以我们有16个分片：Shard 0，Shard 1，...，Shard 9，Shard A，...，Shard F。创世区块包含有ID为4a5e1e4b...a33b的交易，它是以4开头的，因为还需要建立Shard 4。

我们如何在分片系统中验证交易？如上所述，当我们收到一个交易时，我们检查每个输入是否未使用，以及它是否包含有效脚本（即它包含有效签名）。每个输入引用一个交易ID，因此如果输入引用交易06d3...18 和8d67...26，我们请求Shard 0 和Shard 8 检查交易输出是否未使用以及输入是否包含有效签名，因为它们知道相应的交易。

作为奖励，由于交易ID是均匀随机的，我们可以非常肯定每个分片都会同样繁忙。

merkle root呢？

正如您在上图中所看到的，分片可以按ID对其交易进行排序，然后构建尽可能多的哈希值（以蓝色显示）。

然后，挖矿服务器收集所有哈希并完成分片所完成的工作，产生最终的merkle root，并且可以进行新的挖矿，如上图所示。

出于好奇，我做了一个小型的模拟，以找出需要发送多少哈希到挖矿服务器。正如预期的那样，它随着交易数量的增加呈对数增长，并与分片数量成线性增长关系。

每个哈希有32字节，加上一些位置信息（比如8字节），因此对于512个分片上的1000万笔交易，我们发送到挖矿服务器上的数据不到300kB——这些交易的大小有3GB。这意味着我们几乎不需要交流，而且工作是均匀分布的——分片处理是正确的！

TTOR基础上的分片

如果我们使用交易拓补排序，事情将变得更加困难。我们可以通过交易ID的第一个字母进行分片，就像我们使用CTOR一样，这可以用于检查交易输入是否有效。

不幸的是，在建立merkle root的路上就没有那么顺利了。Shard 6中的交易可能依赖于Shard 0和Shard 9中的交易，并且我们必须将所有类型的数据发送到相对应的位置以恢复拓扑顺序。在这一点上，分片的优势几乎消失了。

但是，我们并不轻易放弃。我们可以用一种不同的，虽然复杂得多的方式进行分片，下面是解释：

1.单个分片由初始交易ID字母（0..F）和一些升序编号（1..16）作为标准进行分类。

2.与CTOR一样，已确认的交易按其ID进行分类。

3.对于每个分片，我们都有一个Bloom Filter(一种压缩的但具有概率的集合)，它告诉我们分片的mempool中有哪些交易。

4.当我们接收到一个交易时，我们检查交易的每个输入是否与分片的Bloom Filter相匹配：

a）如果有，将询问匹配的分片以验证输入。Bloom Filter可能会存在是误报，因此我们需要查看不同的分片。

b）如果没有Bloom Filter可以与之匹配，则需检查输入，这与CTOR是一样的。

5.检查内存池中是否有包含交易输入的分片：

a）如果有，找到具有此类输入的最高编号（1 ... 16）的分片。将交易放在任何编号大于或等于该分片的随机分片中，并将交易ID添加到分片的Bloom Filter中。

b）如果没有，则将交易放入任何随机分片中。

6.每个单一的分片对交易进行拓补排序，并为merkle root构建尽可能多的哈希- 就像在CTOR中一样。

7.这些哈希被发送到挖矿服务器中，挖矿服务器将哈希合并到merkle root,中，然后对其进行打包。

8.一旦区块被打包，将mempools中的所有交易根据其交易ID移动到它们的分片中（与CTOR一样）。

这听起来很复杂。

请注意，工作将不再像CTOR意义在分片之间平均分配：有一种倾向是将更多交易发送到编号更高的分片中，因为我们必须将分片mempool中已经有的交易发送到大于或者等于该数字的分片中。攻击者可能会利用这种规律进行拒绝服务攻击。

我们可以通过调整选择随机分片的函数使其优先选择较低编号的分片来减少这种偏差，或者我们可以在它们变得不平衡时将大块交易移到另一个分片中。

等一下？我们在做什么？我们显然过度设计了这件事。相比之下，我们肯定会同意CTOR版本，它更简单，更精简，更高效，也没有明显的攻击媒介。

结论

我们已经看到了如何有效地对系统进行分片，以及如何使用CTOR和TTOR对比特币进行分片。显而易见，CTOR版本比TTOR版本简单得多。

然而，值得吗？CTOR的缺点，从某种程度上说，只是涉及到了改变。此外，许多人认为TTOR是由中本聪安排的，因此不应该改变。但这只是对权威的一种迷信，中本聪也犯过很多错误。

我们现在或11月份真就需要CTOR吗？不。但是我们是否需要将每个区块增加到32MB呢？不，也不需要。我们之所以这样做是因为一旦需要提高，随着网络的增长，它将变得更加困难。相同的论点也适用于CTOR。我们越早实施它，我们就就有更多的时间让系统成熟，做质量保证，压力测试等等。在问题出现之前，我们应该始终领先十步。特别是当我们想要建立世界上见过的最好的现金时。

中文首发：https://bch.club