Txilm协议在设计迭代中得到了原比特大陆 区块链团队 王逵 的指导和非常有意义的探讨。同时得到了孙毅老师主持的中科院计算所区块链实验室的大力支持。感谢 实验室中王鑫和姜鑫两位同学帮助完成了算法的初步模拟验证和近似误差的确认。
本文翻译自Monoxide团队的Medium博文，感谢 猎豹移动 区块链团队 王海龙 完成翻译和校对。
1 背景
假设新创建的区块中大多数交易TXes已经存储在大多数全节点的内存池中，致密区块(compact block)只携带TXIDs。这是在比特币改进提案BIP152中提出的。更多细节参见bitcoincore.org/en/2016。
总的来说，致密区块用32字节的TXID(例如，交易TX的SHA256值)替代每个交易TX(大约300-400字节)。这可以节省近10倍的带宽。
我们旨在进一步将致密区块中每个TX表示的大小减小到约40比特。我们可以在致密区块最初的提案(6.4=32字节/40比特)上做到6.4倍压缩。新的提案没有使用诸如布隆过滤器或IBLT这些额外的数据结构。此外，新提案不依赖各个全节点之间有高度一致的内存池(Mempool)。
通过结合规范的交易排序规则(canonical transaction ordering rule, CTOR)，短哈希可以被进一步降低到32比特，这在致密区块最初的提案上产生了8倍压缩。做到了总的数据量减小80倍。
2 基本原理
我们通过基于TXID的小尺寸哈希值在区块中显示每个TX。
TXID-HASH = h(TXID)
其中h是一个小尺寸的哈希函数，它可以产生32比特到64比特的哈希值。该函数可以仅是CRC32，CRC40或CRC64。所提新的致密区块方案只包括一个TXID-HASH列表，按交易TX的初始列表排序。
这种k比特的小尺寸哈希可能会产生二义性(ambiguity)，这需要每个全节点解决。一旦从发送方接收到包括TXID-HASH列表的新区块，接收方就在其内存池中的哈希列表中搜索每个接收到的TXID-HASH。对于每个TXID-HASH，可能发生三种情况，分别如下：
1. 未找到：内存池中没有交易TX可以匹配上接收到的TXID-HASH。接收方将向发送方或其他peer节点索要该TXID。
2. 找到一个匹配的TX：解析TXID成功。
3. 找到多个匹配的TX：接收方将收集所有匹配的TXIDs作为第二阶段解析的候选集。
在第二阶段，迭代多个TXID-HASH的候选者的所有组合来重新计算Merkle树。其正确的组合将产生一个与区块头携带的Merkle根相匹配的值。
如果情况（3）中的任一组合或情况（2）中被解析的TXID列表没能匹配区块头中的Merkle根，那么接收方将回退到要求发收方传输该区块的完整TXID列表，具体协议在最初的致密区块提案中有描述。出现这种情况的原因是在接收方的内存池中至少有一个TXID在接收的TXID-HASH列表中有相同的TXID-HASH，而不是包括在区块中的TXID-HASH。
对第二阶段搜索的一个可选优化是，在实际重新计算Merkle根之前，添加轻量级的预检查。我们提出了一种轻量级的Merkle树，CRC32-Merkle树，即用CRC32取代SHA256，4字节的Merkle树节点和根。当创建一个新区块，4字节的CRC32-Merkle根将预置到编码的TXID-HASH数据。在搜索正确的组合时，这产生了40倍的加速。（在16字节上算SHA256 对比 在8字节上算CRC32）
解决二义性可能引发额外的延迟。对很多有二义性的TXID-HASH的组合进行迭代也可能消耗大量的CPU时间。本提案的可行性高度依赖哈希碰撞的概率，这一概率同哈希值的长度(k比特)以及内存池的大小是相关的。
3 单个碰撞的概率
单个碰撞被定义为情况1或3至少发生1次。这种碰撞可以在接收到的TXID-HASH之间，或者处于接收到的列表和内存池之间。
给定k比特大小的的TXID-HASH，碰撞率是1/2^k。因此在一个新区块中发生单个碰撞的概率可以被建模为广义生日问题(Generalized Birthday problem)。比如，在内存池中，我们平均有m个TX，而新区块有n个TX。单个碰撞的概率可近似为：
PSC = 1 - (1 - 1/2^k) ^ (m * n + n * n/2)
例如，我们取m=60000，n=10000:k = 32, PSC = 0.14k = 40, PSC = 0.00059k = 64, PSC = 0.00000035
我们建议把k=40作为一个合理值，具备良好的压缩比和相当低的碰撞率。足够大的k约与log(m * n +n * n/2)成比例。
例如，我们放大100倍：m = 6000000，n = 1000000:k = 48, PSC = 0.023k = 56, PSC = 0.000090k = 64, PSC = 0.00000035
或者，我们把m，n的值取小一点，m = 3000，n=200k = 24, PSC =0.036k = 32, PSC = 0.00014k = 40, PSC = 0.00000056
4 结合CTOR 技术
规范交易排序规则(CTOR)是一种排序方案，它根据交易的哈希对一个区块和内存池中的交易进行排序，该方案已经被部署在BCH网络中。基于CTOR方案，所提的方案将实现更低的碰撞率和更高的压缩率。
因为交易在区块和内存池中都是有序的，任何有二义性的TXID-HASH的候选空间将被缩小到由其前一个TXID和下一个TXID限定的范围，并且具有被解析的TXID-HASH，而不是整个内存池。假设新确认的TXID均匀分布在已排序的内存池中，则可能的碰撞空间的大小将从m降低到m/n。在排序后，有二义性的TXID-HASH只有在相邻时才会发生区块内的碰撞。这显著降低了碰撞概率和解决二义性的成本，从而允许更短的哈希和更高的压缩比。
按CTOR技术对交易排序，碰撞概率可以被近似为：
PSC = 1 - (1 - 1/2^k) ^ (m + n/2)
对小尺寸的区块：m = 3000，n =200:K = 16, PSC = 0.046K = 24, PSC = 0.00018K = 32, PSC = 0.00000072
对中等尺寸的区块：m = 60000,，n = 10000:k = 16, PSC = 0.63k = 24, PSC = 0.0039k = 32, PSC = 0.000015
对大尺寸的区块： m = 6000000，n = 1000000:k = 24, PSC = 0.32k = 32, PSC = 0.0015k = 40, PSC = 0.0000059
5 恶意碰撞攻击
攻击者很容易构造一个新交易，其TXID-HASH和已有的交易相匹配。大量创建这种恶意交易可能使上述的碰撞概率分析无效并且使新区块的验证成本不菲，这最终导致更高的分叉率。我们提出了两个简单的策略来应对该攻击模型。
加盐哈希一个简单的防护策略是在计算TXID-HASH时引入一个盐(Salt)：
TXID-HASH = h( Salt + TXID )
该盐值该特定于携带那些TXID-HASHes的区块并被包括在编码的数据中。例如，直接将CRC32-Merkle的根作为盐，或引入另一个4字节字段，随机生成。
即便已有的交易对所有人是已知的，攻击者在一个区块被矿工广播之前是无法构造恶意的交易。恶意交易很难比接收并验证新区块更早之前到达全节点。这使得攻击者可能发起攻击的时间窗口极度受限。同时，这要求攻击者可以快速地将恶意交易泛洪到整个网络。理论上讲，这有可能（例如，控制大型的僵尸网络），尤其是当主链底层的P2P网络很小的时候。该策略使得恶意交易只能针对单个特定区块，因此先前传播的恶意交易将无法攻击未来的区块从而使得该攻击在经济上很低效。如果想要持续攻击网络，需要持续构造恶意交易，隔了一个块之后，之前的攻击交易就失效了。但是这些交易的交易费用依旧背会后续区块获取，使得攻击成本相当高昂。
受到攻击时降级到老算法引入加盐哈希显著地提升了碰撞攻击的成本和失败率。倘若在极端情况，不计成本，大规模的碰撞攻击仍然是可能的。当整个网络受到攻击时，我们要求矿工回退到TXID列表。矿工会愿意在这个时候退到老算法，因为创建孤块是在浪费哈希算力，矿工会尽可能避免。
在验证进来的新区块时，包括矿工在内的所有全节点都可以察觉到此类攻击。它可以通过简单地计算每个区块中带二义性的TXID-HASH的数量来做到。如果数量显明显高于预期值并且观察到分叉。下一个区块应该回退到TXID列表算法。
参考文献
[1] Compact Blocks FAQ: bitcoincore.org/en/2016
[2 ]BIP152: Compact Blocks: github.com/bitcoin/bips
[3] Canonical Transaction Ordering for Bitcoin
https://blog.vermorel.com/pdf/canonical-tx-ordering-2018-06-12.pdf
[4] Wiki: Birthday problem
en.wikipedia.org/wiki/B
[5] Big Number Calculation：ttmath.org/online_calcu
原文链接：
medium.com/breaking-the
