CTOR在区块熵编码中的优点

对于大多数交易我们可以通过指定一个或两个字节来高效地对块内的交易集进行编码。使用LTOR，我们可以省略TXID的前几个字节，因为一个块中相邻的交易它们是完全一样的。对于所有排序，我们可以省略大部分后字节，因为它们提供的信息比消除潜在匹配的内存池交易之间的歧义所需的信息还要多。本文给出了一种具体的编码方案。

注意：在本文中，我将使用术语“LTOR”和“CTOR”来指代Bitcoin ABC提案的不同方面。“LTOR”指的是交易词汇排序规则 ——即要求交易按TXID以数字方式（或按十六进制字母顺序）排序。“CTOR”指的是交易规范排序规则，可以是指定的任何一种交易排序规则。例如Gavin ‘s order是CTOR，但不是LTOR；另一方面，LTOR必然是CTOR。虽然在CTOR被提出的论文中没有明确说明CTOR是哪一种排序方式，但是从Bitcoin ABC代码中可以看出CTOR指的就是LTOR。

介绍

在BCH压力测试期间，我们看到传输区块时石墨烯发送的数据中有86%都用于编码交易的顺序。如果我们有一个规范的交易排序，那么这些数据就可以被丢弃，因为块接收者可以通过算法重新计算交易的正确顺序。

石墨烯是一种非常酷且非常有效的编码区块的算法。但是，它本质上是一种概率算法。它使用IBLT（可逆式布鲁姆查找表）来编码交易ID数据，并且接收者解码IBLT的能力取决于发送者编码的IBLT的大小，发送者和接收者的mempools之间的同步量，还有一定程度需要靠运气。在vswr测试期间，石墨烯的alpha实现在两天内的成功率只有41％。虽然随着石墨烯的开发不断深入，预计会有所改善，但它永远不会达到100％，因此需要一种高效可靠的后备方案。

这让我想到：如果规范排序的块具有较低的熵，则应该可以改进Xthin和Compact Blocks中使用的编码。在试图找到利用这种熵减少的方法的同时，我想出了一种编码，在有CTOR的情况下，其效率大约是Xthin/CB的4倍，在没有CTOR时，效率则为它们的两倍。

由于这种编码方案受Xthin的启发和部分衍生，我将这种编码方案称为Xthinner。在中文环境中，推荐的拼写是“Xthin二”。

问题及其解决方案

（注意：本文中的所有“块”TXID都来自压力测试中的21.3MB的BCH区块，所有“mempool”TXID来自3个相邻块。）

我们需要在块传播中解决的基本问题是指定块中每个交易的足够信息，以便消息的接收者能够重建交易列表（或集合）。为了做到这一点，我们需要区块中每笔交易都有唯一的标识，并且我们希望用尽可能少的bits 来做到这一点。假设我们尝试使用以下TXID作为块中交易的唯一标识：

​我们可以仅使用其TXID的前几个字节来标识此交易。但是我们需要多少字节呢？如果我们按TXID对我们的mempool进行排序，那么mempool中的相邻交易将向我们显示相邻交易之间有多少初始字节(或比特)是一样的，哪些是唯一的：

在这种情况下，为了使用整数个字节作为交易的唯一标识，我们需要发送00 06 40，因为需要40来消除我们的目标交易和00 06 4d…交易之间的歧义。这允许我们将此交易的编码减少到仅3个字节，再加上一些流量控制信息来指定编码长度。相比之下，Xthin总是传输TXID的前8个字节，因此我们已经有了很大的改进。

第二个优化是查看块内的按TXID排序的交易。区块内的前10个交易可能如下所示：

这些TXID都以字节00开头的，并且有5个都是以04作为第二个字节。我们不需要发送每笔交易中所含有的那些重复的字节。相反，我们可以选择只传输那些交易之间不同的信息。

对于00 06 40…交易，我们只能省略第一个字节，因为它06与前一个TXID不同，所以我们需要为这个交易编码两个字节06 40。（平均而言，我们可以做得比这更好，因为大多数交易只需要一个字节来作为唯一标识。但是，添加流量控制和纠错信息意味着我们的最终性能将接近每个交易两个字节。）

那么我们如何处理流量控制问题呢？如果我们有一个字节流对应于唯一指定每个交易所需的字节，我们如何知道哪个是每个交易的最后一个字节呢？我们如何知道有多少字节与之前的交易相同?我们可以将此信息编码为(uint_8 first_byte_index, uint_8 last_byte_index)对，但是这将使用另外两个完整字节，并且大约会使我们的典型编码大小加倍。相反，我们可以定义基于堆栈的状态机，并将我们的流量控制信息编码为对状态机的1比特命令。

完整算法分为四部分

（a）编码

对于编码，我们使用基于堆栈的状态机，该状态机遵循四阶段循环。在每个周期结束时，堆栈上的字节表示足够的TXID的初始字节，以便能够在mempool中唯一地标识该TXID。在每个周期的开始，我们留下前一个交易的初始字节。我们的四个阶段如下：

1、我们可以根据需要从堆栈中弹出1个或更多字节，以消除前一个块交易的歧义。

2、我们可以根据需要将1个或更多字节压入堆栈，以消除相邻mempool交易的歧义。

3、我们使用堆栈上编码的前缀提交交易。

4、我们将数据累积到一个或多个校验和字节中以进行错误检测和纠正。

我们总是需要弹出并推送每个交易至少1个字节; 否则，将导致编码歧义。第一个之后的每个弹出或推送都可以编码为1位命令，其中a 0表示我们已准备好移动到状态机的下一个阶段，并且1表示我们仍需要至少再执行一个pop或推进当前阶段。我们来看一个例子吧。假设下面的哈希列表是我们的mempool中的TXID，其中粗体TXID是我们块中的TXID：

我们的状态机以空堆栈开始。

1.1（第1轮第1阶段）我们不需要弹出任何字节来消除前一个交易的歧义（因为没有），所以我们将a编码0到我们的状态机弹出命令列表中.pops.extend([0])。

1.2我们的交易需要00 02 87消除它与邻居的歧义，我们的堆栈当前是空的，所以我们需要将总共三个字节压入堆栈.pushbytes.extend([0x00, 0x02, 0x87])始终需要第一次推送，因此我们只需要在1推送命令列表中添加两个值.pushes.extend([1, 1, 0])

1.3我们的堆栈现在是00 02 87。只要此消息的接收者在其mempool中具有该交易并且没有具有相同前缀的冲突交易，那就足以唯一地标识该交易。

1.4我们稍后会讨论校验和。

2.1我们00 02 87在堆栈上，我们的下一个交易开始于00 04 37，所以我们需要弹出两个字节。第一个pop是自动的，所以我们需要告诉我们的状态机在进入下一个阶段之前弹出第二个字节.pops.extend([1, 0])。

2.2我们现在已经是00堆叠了。我们需要00 04 37从mempool交易消除歧义00 04 41，因此我们推送两个字节：pushbytes.extend([0x04, 0x37])。第一次推送是自动的，所以我们只需要在切换到下一个tx之前告诉我们的状态机关于第二次推送.pushes.extend([1, 0])

2.3这使00 04 37的堆栈能够唯一地识别我们的交易。

3.1我们的下一个tx开始于00 04 43。只有最后一个字节与我们的堆栈值不同，并且该pop会自动发生，因此我们告诉我们的状态机不再执行其他pop.pops.extend([0])

3.2我们现在有了00 04的堆栈。我们还需要一个字节43来消除距离最近的mempool相邻的歧义00 04 41，因此我们只需要一次自动推送.pushbytes.extend([0x43])，pushes.extend([0])。

3.3这使00 04 43的堆栈能够唯一地识别我们的交易。

持续下去。

（b）解码

我们对（a）部分的前三个交易的编码数据如下：

要进行解码，我们使用该数据运行状态机。

1.1从我们的堆栈是空的开始。我们不能自动进行第一次弹出，所以我们跳过这一步。我们的pop命令列表中的下一位是0，所以我们不做任何额外的弹出。我们的堆栈仍然是空的。

1.2我们自动推送00。我们的pushes列表有两个1值后跟a 0，所以我们再做两次推动02 87来完成这个阶段。

1.3我们的堆栈现在是00 02 87。检查我们的mempool是否有以这些字节开头的交易，并希望只找到一个这样的交易，将其附加到我们的块中。

2.1我们pops列表中的下两个值是1, 0，所以我们自动弹出加一个，只留00在我们的堆栈上。

2.2我们的下一个价值pushes是1, 0，所以我们自动推动再加上一个。在推动04 37上加上00。

2.3我们现在有了00 04 37在我们的堆栈上。检查我们的mempool中是否以这些字节开头的交易，并希望只找到一个这样的交易，我们将其附加到我们的块中。

3.1我们pops列表中的下一个值是0，所以我们只进行自动弹出，将我们留在00 04堆栈中。

3.2我们pushes列表中的下一个值是0，所以我们只进行自动推送。我们的下一个价值pushbytes是43，所以我们把它推到我们的堆栈上。

3.3我们现在有了00 04 43在我们的堆栈上。检查我们的mempool是否以这些字节开头的交易，并希望只找到一个这样的交易，将其附加到我们的块中。

（c）潜在的错误

解码错误有三种类型：

接收者的mempool中没有任何TXID以指定前缀开头的交易。（missing-tx错误）

接收者在其mempool中有多个交易，其TXID以指定的前缀开头。（前缀冲突错误）

接收者在其mempool中没有指定TXID前缀的正确交易，但具有相同前缀的错误交易。（组合missing-tx和前缀冲突）

错误类型＃1和＃2很容易检测。要检测错误类型＃3，我们可以使用校验和。一旦检测到错误，可以通过向发送方询问相关块索引或范围的完整TXID来解决它们。

（d）校验和

如果我们的接收者确实有一个冲突的交易，我们可以对一些额外的校验和数据进行编码，这样接收者就可以缩小解码错误发生的范围。我们可以在多个级别上对校验和进行编码，以便为典型错误提供良好的位置特异性，对罕见的多次碰撞错误提供良好的整体敏感性，以及较低的总校验和大小。我的建议是对每组8个交易的级别使用0级校验和（即tx [0：8]，tx [8:16]等），每组64个交易的级别使用1校验和（即tx [0:64]，tx [64：128]等），每组256个交易的使用2级校验和，以及每组1024个交易的使用3级校验和。对于每个级别和每个对等连接，我们从TXID中选择一个不同的（随机）字节位置以在我们的校验和中使用。这为任何给定的交易提供了总共4个字节的校验和覆盖，因此如果存在类型＃3错误，则未检测到该错误的概率为1 in2³²。如果未检测到解码错误，则解码的块将无法通过merkle root哈希检查，并且DoS将禁止发送该消息的对等方。但是，由于其他对等方将使用不同的校验和字节索引，因此相同的错误将在接收方被检测出的概率为1 /2³²= 99.％。对于大区块，此校验和方案每个交易将使用1.164位 。

对抗性问题

与普通的Xthin不同，Xthinner基本上不受对抗性问题的影响。我们的对抗问题可分为以下几类：

1、我们的对手使用难以编码的交易预填充我们的mempools，从而使Xthinner消息膨胀。2、我们的对手等待一个区块直到它被挖时将其编码成Xthinner消息，然后在他们有机会下载和解码Xthinner消息之前将冲突的交易注入接收者的mempool。

这两种情况中的任何一种都不是特别麻烦。

1、想要花费256 ^ n计算将交易的Xthinner消息大小增加n个字节？libsecp256k1的签名操作发生的速度约每秒10000 – 20000 /核心，如果攻击者试图让每个交易占用6字节而不是2字节进行编码，那么他们将每CPU核心每3秒发送大约一个交易。他们仍然需要支付交易费用。

2、精明的对手也可以在传播的过程中监视Xthinner块的消息，并在Xthinner消息传输完成之前用冲突（＃2或＃3）交易污染接收者的mempool，但这只会强制一次额外的往返（~0.2秒）和32字节的流量来获取冲突位置的完整TXID。这种攻击难以实现，并且仅限于少量交易（即当块在传输时，你可以进入接收者的mempool）。如果攻击者能够注入100个冲突的交易，那么可能会使接收者通过网络请求另一个3.2 kB的TXID，这应该是可以容忍的。如果这次攻击实际上是在野外进行的，那么还有一种直接的防御：在开始下载区块之前，接收方还可以尝试优先解码xthin消息。

性能

要运行我的xthinner-python测试代码，请在* nix机器上输入以下命令：

这是输出示例：

上面的场景是针对一个21.3 MB的LTOR模块，它使用了39.4 MB mempool的54％。它不包括由于接收者的mempool中的交易丢失而导致的重新传输。如果21.3 MB块包含100％的21.3 MB mempool，则编码大小从15.85 bits/tx下降到14.15 bits/tx。

编码方案的概念验证python实现仅需要284 ms来编码笔记本电脑上的21.3 MB块，以及256 ms进行解码。正确的C ++实现可能比这快10到100倍。如果没有任何并行化，在C ++中编码和解码1 GB块可能只需不到1秒。

字节是否最佳？

使用将全部字节推入堆栈的状态机的决定完全是随机的，并且由编程懒惰驱动。我没有测试任何其他推码尺寸。很可能通过更小（或可能更大）的推送尺寸（例如4位或6位）可以实现更好的编码效率。但是，现在使用的字节大小的推送可能已经足够了。

没有LTOR的操作

Xthinner不需要LTOR，但它与其他排序规则相比更好。如果未使用LTOR，则在编码之前和解码之后将需要单独的步骤将交易顺序更改为LTOR顺序和从LTOR顺序更改到其他交易顺序。如果使用除LTOR之外的CTOR，则可以在没有任何额外编码数据开销的情况下执行这些步骤。但是，如果不使用CTOR，那么编码器将需要单独编码排序信息。对于具有n个交易的块，这可能占用（n log_2（n））位，对于15 MB块，每个交易占用大约2个字节。这大约是总编码大小的两倍。

如果需要LTOR（即CTOR），则需要由创建区块的矿工将交易按照LTOR一次性排序。如果不需要LTOR，则每个节点将需要在每个Xthinner跃点之前将块排序为LTOR，并且需要从LTOR返回到真正的区块顺序。

排序为LTOR的速度很快，对于21.3 MB的块大约需要31 ms。如果是按照Gavin的顺序排序将比这慢很多，可能慢约20倍。

替换INV

Xthinner不仅仅适用于区块。可以使用相同的技术将INV消息压缩到每个交易几个字节。INV消息是节点向对方宣布他们在其库存中具有一个或多个新交易的方式。目前，它们要求每个节点向该节点的对等节点发送或接收32字节（加上最多95个字节的TCP / IP和p2p开销）。对于具有50个对等节点的节点，每个交易的上传下载流量为3.2kB，这只是为了宣布交易可以下载，甚至不发送交易本身。使用Xthinner编码，这可以减少到每个交易大约2-4个字节，尽管具有相同的95字节的TCP / IP和p2p开销。将多个INV批处理到单个IP数据包可以减少开销，但除非典型的INV批大小为每个INV至少5个交易，否则在INVs上节省的带宽将是最小的。

并行

虽然单个内核上的Xthinner编码和解码对于合理的未来可能足够快，但最终可能还需要进行并行化。幸运的是，它很容易做到。您可以将块拆分为n个大小为1 / n的连续块，并分别并行地对每个块进行编码。解码只能在编码被分割成块的情况下并行进行。将一个块分割成多个块会增加少量的开销，因为你要在一个块的末尾丢弃堆栈的内容，并在下一个块的开始重新指定它。除此之外，每个块的开销应该是最小的，并且主要由用于编码块大小的2或4个字节和用于编码校验和方案参数的大约13个字节组成。

Blocktorrent

Xthinner可以利用tl; dr使Blocktorrent更高效，更容易实现。我们可以使用Xthinner来编码Merkle哈希到块Merkle树的内部哈希值之一的一组交易，而不是使用Xthinner来编码可以将Merkle哈希到块的Merkle根哈希中的一组交易。该数据包还可以包括剩余的Merkle哈希值（完整的256位），以允许每个数据包被独立验证为真正块的无错误块。例如，将块拆分为512个交易块将产生大约1014字节的块编码大小。单个UDP / IP数据包可以包含512个Xthinner编码的TXID以及最多12个Merkle路径哈希，同时仍然适合1500字节的MTU，允许每个UDP / IP数据包被独立验证回到Merkle根目录，以获得最多的块（ 2¹¹*2⁹）= 1,048,576笔交易。对于较大的块，256个交易块可以允许最多27个Merkle路径哈希，允许最多2³⁴（170亿）交易的块。或者，UDP支持的数据报大于MTU（最大64 kiB）。超大数据报会因数据包丢失而受到更多损失，因为如果单个数据包丢失，整个数据报告就会丢失，但对于双数据包数据报告，它应该不会太糟糕。

如果我们可以独立地验证每个256或512-tx块正确对应于我们有一个带有有效工作证明的区块头的Merkle根哈希，那么我们可以在等待之前无需信任地将每个块转发给我们所有的对等节点。其余的块没有任何后续的DoS风险。那很酷。

我之前在2016年尝试实施Blocktorrent时遇到了代码复杂度过高的问题。这种复杂性是需要高效地弄清每个数据包中包含哪些数据的所导致的结果。如果每个交易需要8个字节进行编码，那么一个数据包只能包含128个交易加上11个Merkle路径哈希值，这将限制为131,072个交易块。将其降低到64-tx，数据包将允许2 32个交易块，但是将使用高达40％的总带宽来重复传输Merkle路径信息。为了尝试解决这个问题，我花了很多时间编写代码以允许节点模拟其对等块的状态并有效地传输状态信息。这种方式有效，但这需要花费很长时间。通过使用Xthinner，我们可以在每个数据包中获得更多交易，从而使更大的块具有更高的效率，同时仍然保持每个分组完全独立于所有其他分组，从而消除了对状态建模和发送代码的需要。Xthinner使Blocktorrent更简单，更高效，更可行。