链闻消息,公链项目 Monoxide 发布了区块压缩算法 Txilm,据该项目创始人王嘉平介绍,Txilm 算法从比特币提案「BIP152」出发,进行了进一步改进,使用该算法将使区块传输带宽需求降低到原来的 1/80,同时使得冲突概率控制在 1/1000 左右,其中消解冲突的计算量可以忽略不计。此外,该算法不依赖各个全节点之间的 mempool 是高度一致的,无需额外的协议保持 mempool 的同步。

王嘉平表示,Txilm 协议在设计迭代中得到了原比特大陆区块链团队王逵的指导和非常有意义的探讨,同时得到了孙毅老师主持的中科院计算所区块链实验室的大力支持。他感谢实验室中王鑫和姜鑫同学帮助完成了算法的初步模拟验证。

以下文章翻译自 Monoxide 团队的 Medium 博文,猎豹移动区块链团队王海龙完成翻译和校对。

原文标题:《Monoxide 公链系统中的带盐短哈希有损区块压缩算法》
作者:王嘉平,创新工场执行董事,Monoxide 论文作者
翻译:王海龙,猎豹移动区块链团队

硬核:深入讲解 Monoxide 的区块压缩算法 Txilm王嘉平,创新工场执行董事,Monoxide 论文作者

1 背景

假设新创建的区块中大多数交易 TXes 已经存储在大多数全节点的内存池中,致密区块 (compact block) 只携带 TXIDs。这是在比特币改进提案 BIP152 中提出的。更多细节参见 https://bitcoincore.org/en/2016/06/07/compact-blocks-faq/

总的来说,致密区块用 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.14
k = 40, PSC = 0.00059
k = 64, PSC = 0.00000035

我们建议把 k=40 作为一个合理值,具备良好的压缩比和相当低的碰撞率。足够大的 k 约与 log(m * n +n * n/2) 成比例。

例如,我们放大 100 倍:m = 6000000,n = 1000000:
k = 48, PSC = 0.023
k = 56, PSC = 0.000090
k = 64, PSC = 0.00000035

或者,我们把 m,n 的值取小一点,m = 3000,n = 200
k = 24, PSC = 0.036
k = 32, PSC = 0.00014
k = 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.046
K = 24, PSC = 0.00018
K = 32, PSC = 0.00000072

对中等尺寸的区块:m = 60000,,n = 10000:
k = 16, PSC = 0.63
k = 24, PSC = 0.0039
k = 32, PSC = 0.000015

对大尺寸的区块: m = 6000000,n = 1000000:
k = 24, PSC = 0.32
k = 32, PSC = 0.0015
k = 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: https://bitcoincore.org/en/2016/06/07/compact-blocks-faq/
[2 ]BIP152: Compact Blocks: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki
[3] Canonical Transaction Ordering for Bitcoin
https://link.zhihu.com/?target=https%3A//blog.vermorel.com/pdf/canonical-tx-ordering-2018-06-12.pdf
[4] Wiki: Birthday problem
https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem
[5] Big Number Calculation:https://www.ttmath.org/online_calculator

来源链接:mp.weixin.qq.com