Conflux研究组 | 最长链规则的优势与不足

282 阅读7分钟

这里有Conflux最前沿的理论研究成果,最新锐的论文解析、最硬核的密码学、最烧脑的博弈论和你可能永远也用不到的数学知识。知识的海洋,等你来徜徉,Enjoy!

我们系列专题的第一期,就来谈谈比特币所采用的最长链规则,也即“中本聪共识算法”。

由于 Conflux 采用的是不同于最长链规则的最重链规则,所以在以往的文章中我们比较经常解释 Conflux 没有选择最长链规则的原因,而对最长链规则本身的优势介绍得比较少。这次我们将从一个更全面的视角来讨论最长链规则的优势与劣势。

首先我们来谈谈最长链规则的优势。

从比特币开始,无论是最初的只是改改参数的莱特币,还是后来提出的 Bitcoin-NG [1], 以及采用了 DAG 结构的 OHIE [2],众多公链共识算法的核心理念都是最长链规则。

能够得到如此多公链项目的青睐,最长链规则的过人之处究竟在哪里呢?

OHIE 的论文 [2] 提到了很重要的一点:对于一个区块链系统,最重要的是一个“端到端”的安全性证明——只针对几种特定的攻击方式证明安全性是远远不够的,因为永远无法避免将来有更聪明的人设计出更巧妙的攻击策略。

在端到端的安全性证明这点上,最长链规则具有足够的先发优势。作为开加密货币之先河的比特币的核心规则,最长链规则得到了最广泛和深入的研究。

实际上,即使是被研究最多的最长链规则,其安全性的完整证明也要晚至 2016 年 9 月才由康奈尔大学的密码学教授 Rafael Pass 等人首次完成 [3] 。(中本聪在比特币白皮书中的证明只考虑了特定的攻击方式,其它一些更早的工作则只证明了最长链规则在特定条件下的安全性。)Rafael 的证明可以直接推广到任何一个合理设计的基于最长链规则的公链系统。

相比之下,其它的共识算法包括最重链规则在 2019 年以前都没有一个完整的安全性证明,甚至有些共识算法连在限定条件下的安全性证明都没有。我们将把有关最重链规则的问题以及 Conflux 的应对留在之后的几期来讲,此处不再展开。

那么 Conflux 为什么没有采用最长链规则呢?

主要原因在于最长链规则对“孤块”非常敏感。

“孤块”是指那些形式上合法但是最终没有进入主链(最长链)的区块。在理想的情况下,诚实节点每次生成区块都会将最长链的长度增加一。但是,如果两个诚实节点近乎同时挖出了两个区块,互相都没有引用对方作为父亲区块,那么这两个区块就形成竞争关系。相互竞争的区块最终至多只有一个进入最长链中,其余的都会成为不对最长链做出任何贡献的“孤块”。

一旦系统中的“孤块”过多,最长链的增长速率就会受到影响,进而给攻击者可乘之机。例如在 50% 的诚实区块成为“孤块”的情况下,最长链的平均增长速度就只有诚实节点出块速度的一半,此时攻击者只需要 34% 的总算力(多于诚实算力的一半)就可以对任意早的交易发起双花攻击。

“孤块”的出现频率与一个比值有关:平均生成一个区块所需的时间 / 区块在点对点网络中广播需要的时间,我们暂且称为安全性系数。这个比值越高,则孤块出现的频率越少,相应的也就更安全。根据文章 [3] 中的分析,在这个比值大于 7 时,双花攻击所需算力的理论阈值是 45% 左右;比值大于 60 时,双花攻击所需算力的理论阈值是 49.5% 左右。目前比特币的比值在 60 左右。

因此我们有以下四个式子:

  1. 安全性系数 = 平均生成一个区块的时间 / 区块广播时间
  2. 网络带宽系数 =区块大小 / 区块广播时间
  3. 单笔交易负载 = 区块大小 / 每个区块交易数量
  4. TPS = 每个区块交易数量 / 平均生成一个区块的时间

也就是说, 安全性比值 * 单笔交易负载 * TPS = 网络带宽系数

上式中除了 TPS 之外的每项都对应了一个在最长链规则下提高 TPS 的切入点:

  1. 降低安全性系数:简单地改比特币的参数,牺牲一部分安全性以换取更高的效率。例如缩短出块时间或者增大区块尺寸(相当于增加区块广播时间)。
  2. 降低单笔交易负载:使用致密区块(compact block)技术,把完整传输每笔交易(约数百 KB)变成传输交易的短 ID(4~6 B)。
  3. 提高网络带宽系数:提高共识节点的加入门槛,牺牲去中心化程度以换取更高的效率。极端情况下可以只保留少量光纤直连的超级节点(比如说 21 个)。

这几个修改的方向都非常直接有效,但是可以带来的性能提升是比较有限的,过度使用带来的牺牲也非常大。例如将区块的尺寸增加到上百 MB 或者将共识节点数量减少到 20 个都很可能是得不偿失的做法。

实际上,Bitcoin-NG 和 OHIE 利用一些特殊的设计绕过以上限制。另一方面,如果将树图结构与最长链规则结合,其实也可以很简单地设计出高 TPS 的共识机制。关于这一点,我们将专门写一篇文章详细讨论,此处先不展开。

总而言之,在提高 TPS 这条路上,尽管最长链规则受到以上分析的制约,但通过合理的设计,这个天花板还是可以绕开的。

最长链规则最大的弱点,是区块的确认时间。

如果把安全性系数设为 10,则等待 6 个确认区块的平均时间是 60 * 区块广播需要的时间;如果需要在两分钟内确认一笔交易,就需要把区块广播时间控制在 2 秒内。

实际上,在区块广播中的每一跳,每个节点都需要进行验证和执行等一系列操作之后才能向下一跳转发。在节点数较多的时候,即使是不大的区块想要在 2 秒内传遍全网所有(或绝大多数)节点也是一件非常困难的事情。从目前的网络环境来看,3 到 5 分钟的确认时间基本上已经是最长链规则的极限。

Conflux 的原型版本(也即目前公开的版本,新版本的文章和技术规范尚未公开发布)中区块的确认时间是 4 到 7 分钟,看起来也没有做得更好。实际上,随着我们对最重链规则进行更深入的研究并进一步发掘其特有的潜力,在 PoW 链的确认时间这点上我们已经取得了惊人的突破,实现了远超最长链规则的确认速度……

最重链规则究竟魅力何在呢?且待下期分解。 ﹏ ﹏ ﹏ ﹏

[1] Eyal I, Gencer A E, Sirer E G, et al. “Bitcoin-NG: A Scalable Blockchain Protocol.” USENIX 2016. [2] Haifeng Yu, et al. “OHIE: Blockchain Scaling Made Simple.” arXiv:1811.12628 (2018). [3] Rafael Pass, Lior Seeman, and Abhi Shelat. “Analysis of the Blockchain Protocol in Asynchronous Networks.” EUROCRYPT 2017. [4] Yonatan Sompolinsky and Aviv Zohar. “Secure High-Rate Transaction Processing in Bitcoin.” International Conference on Financial Cryptography and Data Security, FC 2015.