在 Crypto Wednesday No.26 上,Nervos 共识研究员万涔涔为我们分享了 CKB 的共识算法:NC-Max,并清晰的解析了其设计原理,以下为分享整理稿。

NC-Max 是 Nervos 底层公链 CKB 的共识算法。如果只用一句话介绍 NC-Max,那我会引用 NC-Max 的发明者张韧博士的说法:「将交易的确认和交易的同步解耦」

Nervos 底层公链 CKB 的共识算法 NC-Max,将交易的确认和交易的同步解耦

NC —— 蹒跚的巨人

要理解 NC-Max,我们先从 NC 开始,NC 是 Nakamoto Consensus,也就是中本聪共识的简称,它是第一个在开放网络中运行的共识算法,矿工可以随时加入和退出。

在 NC 中,矿工们解决哈希难题,提出区块,若出现分叉则采用最长链原则确定主链,最重要的是,NC 引入了激励机制给共识的安全持续运行提供了源源不断的燃料。这个共识算法相比传统的 BFT 算法会更容易理解,并且作为比特币的共识算法扛过了十年的安全考验,我们基本上可以认为它是安全的。

时至今日,NC 的代表——比特币,依然占据着加密货币总市值的 60%+,是当之无愧的巨人。然而,7 笔 / 秒的速度,是这个巨人蹒跚的脚步。

那么 7 笔 / 秒的吞吐量是怎么得到的?这里有一个公式,将比特币的参数带入计算就能得到这个结果。

吞吐量 = 区块大小 /(交易大小出块间隔)

如果想要提高比特币的吞吐量,最直接的方法就是:

1、提高区块大小;

2、降低出块间隔。

以太坊采取了第二种方式,将出块间隔降低到 12s。相比出块间隔数十倍地减少,以太坊的吞吐量仅提升了一倍——只有 15 笔 / 秒左右的吞吐量。这显然不尽人意。

这是因为,随着出块间隔的缩短,以太坊的区块链上出现了频繁的分叉,那些无法进入主链的区块就成了孤块。当孤块率较高时,这些孤块会浪费大量的算力和带宽,并会带来安全上的问题:如果矿工按最长链原则来确认主链,当出现大量孤块的时候恶意节点只需要消耗远低于一半的算力就能双花。

为了缓解这个安全问题,以太坊采用了 Ghost 协议,但是其吞吐量还是受到孤块的制约。那么,让我们先来看看孤块是如何产生的。

孤块从何而来

Nervos 底层公链 CKB 的共识算法 NC-Max,将交易的确认和交易的同步解耦

这张图是比特币的区块广播过程,A 节点挖出高度为 H 的区块,并广播致密区块,致密区块里面只包含交易哈希而非完整的交易,A 在出块之后就能开始挖高度为 H+1 的区块。矿工 B 收到致密区块的时候,首先根据交易哈希查看本地交易池中是否有这些交易,对于本地没有的新交易,B 会向 A 询问,A 会返回这些新交易的完整内容。当 B 对所有新交易验证之后才能开始挖高度为 H+1 的区块 。那这中间就有一个 Gap。

在上面的描述中显然大家能够看到,B 开始挖高度为 H+1 的区块的时间和 A 开始挖的时间有一个时差,我们定义为区块传播时延。因为,在高度为 H 的区块广播的过程中 B 是不会停止手上的工作的,因为 B 是不相信 A 的区块是有效区块的,万一被 A 耍了呢?那么在这个时间里,如果 B 挖出另一个高度为 H 的区块,那就有两个高度为 H 的区块,其中一定会有一个成为孤块。

我们再回到以太坊的孤块问题上,由于相比比特币,以太坊出块间隔很低,因此其挖矿难度也远低于比特币。在区块广播时延相同的情况下,以太坊矿工挖出区块的概率远高于比特币,因此其孤块率会很高。而实际上以太坊的网络设计导致其区块传播时延比比特币更长。

实际上,我们可以得到这样一个关系:

*孤块率和(区块传播时延 / 出块间隔)成正比。

所以,在出块间隔固定的情况下,降低区块传播时延就能降低孤块率。

NC-Max 之道

交易两步确认

Nervos 底层公链 CKB 的共识算法 NC-Max,将交易的确认和交易的同步解耦

在前面的分析里,区块传播时延包括两部分,区块的广播 +新交易的广播。这是串行的过程,那么如果我们能够把这两个过程并行,就能有效地缩短区块传播时延,进而降低孤块率。

Nervos 底层公链 CKB 的共识算法 NC-Max,将交易的确认和交易的同步解耦

怎样让区块传播与新交易的传播并行呢,NC-Max 设计了一个交易两步确认的机制。简单来说,就是在致密区块中既包含新交易的哈希值,我们叫 propose 交易,以通知其他矿工同步新交易。又包含老交易的哈希值,我们叫 confirm 交易,这些老交易是前几个块中已经通知过的新交易,应该完成同步了,只要矿工完成了这些老交易的同步,就可以立即开始挖下一个区块。

具体来说,高度为 h 的区块所包含的老交易,必须是在高度为 h-n 到 h-m 之间的区块包含过的新交易。因此老交易有至少 m 个区块间隔的时间来完成同步。

在正常情况下,NC-Max 的区块传播过程是这样的。矿工 A 挖出区块后,立即广播致密交易,矿工 B
收到致密交易后,确认老交易都已经同步过了,可以立即开始挖下一个区块。新交易的同步过程与新高度的挖矿并行进行。通过这样的设计,区块传播时延相比改进之前缩短了许多,因而在同样的出块间隔下,孤块率也能得到显著的改善。因此,张韧博士说,NC-Max 将交易的确认与交易同步解耦,这句话道出了交易两次确认的精髓。

Nervos 底层公链 CKB 的共识算法 NC-Max,将交易的确认和交易的同步解耦

根据孤块率调整难度

让我们再回到孤块率的公式。我想问大家一个问题:孤块率是越小越好吗?

区块传播时延是有上限的,追求越小的孤块率,意味着要设置越大的出块间隔,也就会得到越低的吞吐量。过于追求极致小的孤块率,会得到一个极致不可用的区块链。我们需要的是一个能够平衡安全和吞吐量的孤块率。

假设我们找到了这样一个安全阈值,那么我们设置多大的出块间隔合适?区块传播时延是动态变化的,受带宽、网络拥堵情况的影响,如果将出块间隔设置得过于保守,比如像比特币的 10 分钟,则吞吐量也会非常保守。如果设置得过于激进,则一旦网络出现较大波动,就会导致孤块率远超安全阈值,影响系统安全。

况且,网络带宽随着技术的进步还将逐渐改善,这也意味着区块传播时延从长期来讲会逐渐下降。固定的出块间隔无法适应动态的网络变化。

既然孤块率才是我们要稳定的目标,于是 NC-Max 改变了难度调整的策略,以孤块率作为难度调整的依据。为了能够计算孤块率,我们在区块结构中增加了叔块区,一个区块中可以包含若干叔块。同时,我们还将区块链按固定时长划分成许多难度调整周期,每个难度调整周期的孤块率等于叔块总数除以总区块数。当孤块率大于我们预设的安全阈值时,难度上升,区块间隔上升,从而使得孤块率回落到安全阈值。反之亦然。

Nervos 底层公链 CKB 的共识算法 NC-Max,将交易的确认和交易的同步解耦

根据孤块率调整难度,结合交易两次确认,使得 NC-Max 的吞吐量能够达到安全阈值下网络所能承载的最大吞吐量。这就是 NC-Max 之道。

推荐阅读:
Nervos CKB 共识协议 NC-Max:突破 Nakamoto Consensus 吞吐量的极限