[RFCS] 0020-ckb-consensus-protocol



  •  

    Number Category Status Author Organization Created
    "0020" Informational Draft Ren Zhang Nervos Foundation 2019-06-19

     

    CKB 共识协议

    原文链接:CKB Consensus Protocol
    翻译链接:CKB 共识协议

    CKB 共识协议.png

    • 摘要
    • 动机
    • 技术概述
      • 消除区块传播瓶颈
      • 利用缩短的延迟提高吞吐量
      • 减少自私挖矿攻击
    • 规范
      • 两步交易确认
      • 动态难度调节机制

     

    摘要

    比特币的中本聪共识(Nakamoto Consensus,简称 NC) 因其简单性和低通信开销的特点而广受好评。然而,NC 有两大缺陷:第一,其交易吞吐量远远无法满足现实需求;第二,NC 容易遭受自私挖矿攻击,在这一类攻击中,攻击者能够采用非协议规定的行为获得更多的出块奖励。

    CKB 的共识协议是 NC 的变体,在保留 NC 优点的同时,提升了其性能极限和抵抗自私挖矿攻击的能力。通过研究发现消除 NC 区块广播延时的瓶颈,我们的协议能够在不牺牲安全性的情况下,支持非常短的出块间隔。缩短的出块间隔不仅提高了吞吐量,也降低了交易确认时长。通过在难度调节时考虑所有有效区块,在我们的协议中自私挖矿将不再有利可图。

     

    动机

    尽管目前市面上已经提出了许多非 NC 共识机制,但 NC 和这些替代方案相比,有以下三重优势:首先,它的安全性已经经过仔细地审查并被广泛理解[1, 2, 3, 4, 5, 6, 7, 8],但其它的替代协议常常引入了新的攻击维度,或无意1, 2] 或依赖于实践中难以达到的安全性前提[1, 2]。第二,NC 最大程度地降低了共识协议的通信开销。最理想的情况下,在比特币网络中广播 1MB 的区块和广播一个大约 13KB 的致密区块信息是等价的[1, 2];有效区块会立刻被所有诚实节点接受。相比之下,其它替代性协议通常需要不可忽视的通信开销来确认一个节点见证了一个区块。举例来说,Algorand要求每一个区块要附带一个 300KB 的区块认证。第三,NC 基于链的拓扑结构确保了其在区块生成的时候,就能确认全局交易排序,这和所有智能合约编程模型兼容。采用其它拓扑结构的协议要么放弃了全局交易排序,要么在很长的确认延迟之后才对交易进行排序[1, 2],这样会限制它们的效率或者性能。

    尽管 NC 有很多优点,但其可扩展性的问题使得它每秒仅能处理少数交易。采用 NC 协议的网络,其吞吐量会受到两个参数的共同限制:1)最大区块容量,2)预期出块间隔。举例来说,比特币的区块大小上限约为 4MB,通过难度调节机制,其目标出块间隔被设定为大约 10 分钟,换算过来吞吐量(TPS)大约为每秒 10 笔交易。提高区块容量或缩短出块间隔分别会导致更长的区块广播延时或生成更多的区块。这两种方法都会提升在其它区块广播过程中,区块生成的概率,从而会增大竞争块出现的概率。由于在诸多竞争块之间,最多只有一个区块能够为交易确认作出贡献,因此浪费了广播其他孤块的节点带宽,从而限制了系统的有效吞吐量。此外,孤块率的提高会降低双花攻击的难度,这会导致系统的安全性降低[1, 2],从而降低协议的安全性。

    另外,NC 的安全性也会遭到自私挖矿攻击的破坏,自私挖矿攻击者可以通过故意地孤立其它矿工的区块,来获得不合理的区块奖励。研究人员发现,这种不公平盈利机会的根源在于 NC 的难度调整机制,它在估算网络计算能力时忽略了孤块。通过这种机制设计,自私挖矿攻击会提升孤块率,从而导致挖矿难度降低,这会让攻击者在单位时间内获得高于平均值的区块奖励[1, 2, 3]。

    在这个 RFC 中,我们提出了 CKB 的共识协议,它能够提升 NC 的性能限制和抗自私挖矿能力,同时保留 NC 所有的优点。我们的协议通过降低区块广播延时来支持非常短的出块间隔。更短的出块间隔不仅可以增加吞吐量,还能够在不牺牲安全性的前提下,降低交易确认延迟(因为孤块率保持在较低的水平)。由于在估计全网算力时,我们会将所有区块(包括叔块)纳入到难度调节中,因此新的难度和孤块率是不相关的,这让自私挖矿不再有利可图。

     

    技术概述

    我们的共识协议在 NC 的基础上做了三个改进。

     

    消除区块传播瓶颈

    比特币协议的开发人员发现,当出块间隔降低的时候,区块传播延时的瓶颈是新交易的传播。新交易是指在最新的区块中包含的、尚未被传播到网络中的交易。没有收到过这些交易的节点必须要在向相邻节点广播收到的这个区块之前,请求这些新交易。由此产生的延迟不仅限制了区块链的性能,而且还会在实际自私挖矿攻击中被利用。在这类攻击中,攻击者会故意将新的交易并入在他们自己的区块中,这会为他们带来更长的广播延时,因此,他们能够在寻找下一个区块的竞争中取得一定优势,从而获得更多奖励。

    从这个研究结果出发,我们的共识协议通过将 NC 的交易确认分解为两个步骤来消除区块传播瓶颈:1)交易提交(Propose),2)交易确认(Commit)。如果一个交易的短哈希(称为 txpid)出现在一个区块或其中一个叔块(被区块引用的孤块)的「交易提交区」(Proposal Zone),则该交易被提交。新提交的交易既不会影响区块有效性,也不会影响区块的广播,因为一个节点在收到这些交易之前,就可以开始向相邻节点传播包含这些被提出的交易区块。在交易被提交之后需要经过数个区块的时间窗口,如果这个交易出现在区块的「交易确认区」(Commitment Zone)中,则该交易被打包。这样的两步交易确认机制消除了区块传播瓶颈,因为一个新块的确认交易在被提出时就已经被所有节点接收和验证。通过限制攻击时间窗口,新的机制也有效地减少了实际自私挖矿攻击。

     

    利用缩短的延迟提高吞吐量

    我们的协议将区块链中所有引用孤块的区块称为叔块。这让我们能够很好地估算当前区块传播的延时,并动态地调节期望的出块间隔,从而在延时得到改善时,提升吞吐量。因此,我们设定固定的孤块率作为难度调节目标,它让我们在不牺牲安全性的情况下,能够利用更短的延迟。协议中硬编码了出块间隔的上下限来防止 DoS 攻击,和避免节点超载。此外,在每个难度调节周期(Epoch)中,区块奖励会根据预期出块间隔,成比例地进行调节,因此预期的平均时间奖励和出块间隔并不相关。

     

    减少自私挖矿攻击

    根据Vitalik, Grunspan 和 Perez-Marco.的建议,我们的协议在估计网络算力时,会将所有区块(包括叔块)纳入到难度调节中,因此新的难度和孤块率是不相关的。

    此外,我们证明了在我们的协议中,自私挖矿不再有利可图。这个证明是非常有意义的,因为在 Vitalik,Grunspan 和 Perez-Marco 的非正式论证中,并没有排除攻击者在新的协议机制下,仍然获得不公平奖励的可能性,而我们的协议证明了这一点。举例来说,攻击者可能会在第一个难度调节周期中暂时关闭一些矿机,这样就会导致修改后的难度调节算法会低估全网算力,在第二个难度调节周期时,这些攻击者便开始自私挖矿,以在整体上获得更高的平均时间收益。我们证明了在我们的协议中,不论攻击者在诚实挖矿、自私挖矿、关闭矿机这三种策略中如何分配算力,不论他的策略覆盖多少个难度调节周期,自私挖矿都是无利可图的。证明的细节我们会在接下来的部分公布。

     

    规范

     

    两步交易确认

    在我们的协议中,我们采用了两步交易确认机制来消除上述的区块广播瓶颈(无论出块间隔多短)。我们首先来定义一下这两个步骤和区块结构,之后会介绍新的区块传播协议。

     

    定义

    定义 1: 一笔交易的提交 id txpid 被定义为这笔交易哈希 txid 的前 l 位比特。

    txpid 用于标识几个相邻区块之间的交易,所以在我们的协议中,txpid 不需要和 txid 那样具有全局唯一性。另外,由于我们在区块和致密区块中都嵌入了 txpid,因此只发送缩短的 txid 可以减少带宽消耗。

    当出现多笔交易使用相同的 txpid 时,那么所有的这些交易都会被认为是已经提交的。实际上,我们可以将 l 设置得足够大,这样查找碰撞所需的计算量会是较为合理的。

    定义 2: 当满足所有下述条件时,区块 B<sub>1</sub> 就被认为是另一个区块 B<sub>2</sub> 的叔块:
    ​ (1) 在同一个难度调节周期中,B<sub>1</sub> 和 B<sub>2</sub> 有相同的出块难度;
    ​ (2) B<sub>2</sub> 的区块高度大于 B<sub>1</sub> 的区块高度;
    ​ (3) B<sub>2</sub> 是在链上第一个引用 B<sub>1</sub> 的区块。

    我们对叔块的定义不同于以太坊,我们不考虑两个区块距离它们第一个共同的起始区块有多远,只要两个区块在同一个难度调节周期即可。

    定义 3: 如果一笔交易的 txpid 被包含在区块高度为 h<sub>p</sub> 的主链区块(或者该区块的叔块)的提交区中,则这笔交易在高度 h<sub>p</sub> 被提交。

    这里有可能会出现这样的情况,一笔提案的交易可能是以前提出的,这与其它交易冲突,甚至出现异常。由于交易提交区只是用来促成交易同步,因此这些情况不会影响区块的有效性。

    定义 4: 当满足所有下述条件时,则一笔非币基交易在区块高度 h<sub>c</sub> 上被确认:

    一个非 coinbase 交易将被提交在高度 h<sub>c</sub> ,如果满足以下所有条件

    ​(1) 该交易在同一条链上的区块高度 h<sub>p</sub> 上被提交,并且 w<sub>close</sub> ≤ h<sub>c</sub> − h<sub>p</sub> ≤ w<sub>far</sub>
    ​(2) 该交易位于区块高度为 h<sub>c</sub> 的主链区块交易确认区;
    ​(3) 该交易没有和主链上任何之前确认的交易冲突。

    如果是币基交易,那么满足条件(2)就会在区块高度 h<sub>c</sub> 被确认。

    w<sub>close</sub>w<sub>far</sub> 分别定义了交易提交和确认的最近及最远的链上距离。我们要求 w<sub>close</sub> 足够大,这样才能使得 w<sub>close</sub> 的区块间隔足够长,以便将交易广播到整个网络。

    这两个参数还会根据节点内存中交易提案池能够保存的最大交易数量来设定。由于提交交易的总量有限,所以可以将它们保存在内存中,因此在大多数情况下不需要从硬盘中抓取最新提交的交易。

    只有在交易确认之后,一笔交易才算被记录在区块链中。因此,在要求 σ 个区块确认的情况下,一个接收者在区块广播之后需要等待至少 w<sub>close</sub> + σ 个区块,才能确保交易有效。

    在实践中,由于我们的协议有更短的出块间隔,w<sub>close</sub> 时间间隔带来的额外延迟被抵消,因此实用性并不会受到影响。

     

    区块和致密区块结构

    在我们的协议中,一个区块包含以下几个字段:

    名称 描述
    区块头 包含区块元数据
    确认区 此区块中确认的交易
    提交区 在此区块中提交的 txpid
    叔块头 叔块的区块头
    叔块的提交区 在叔块中提交的 txpid

    与 NC 类似,在我们的协议中,致密区块会使用交易的 shortid 替代区块的确认区,里面是预先提交的交易列表和 salt。致密区块的其它所有字段保持不变。

    附加区块结构规则:

    • 前四个字段的总大小不能大于硬编码的区块大小限制。设定区块大小限制的主要目的是避免公共节点带宽过载。由于叔块的提交区通常在出块时就已经被同步,所以它们不会被计入在区块容量限制内。
    • 提交区中txpid 的数量也会有硬编码的上限。

    两个启发式的要求能够帮助实践者选择参数。首先,在交易提交区 txpid 的上限不会小于一个区块中确认交易的最大数量,因此即使 w<sub>close</sub>=w<sub>far</sub> ,这个限制也不会成为协议吞吐量的瓶颈。其次,理想情况下,致密区块的大小不会超过 80KB。Croman 等人 在 2016 年的研究表明,不大于 80KB 的消息在比特币网络中的广播延迟较为相似;更大信息的广播速度会因为网络吞吐量这个瓶颈而变慢。当然,这个数字会随着网络条件的提升而改变。

     

    区块传播协议

    根据[1, 2, 3], 所述,节点应该广播所有带有有效工作量证明的区块,包括孤块,它们可能是被主链引用的叔块。由于构建有效的工作量证明会消耗大量时间,因此这些证明不会用于败坏网络。

    我们协议的区块传播协议在大多数情况下能够消除新交易的额外一轮广播。当它不可避免时,我们的协议会确保新交易在往返广播中仅持续一次反射。这是通过以下三个规则实现的:

    1. 如果一些已经确认的交易对发送的节点来说是未知的,他们将会被放在预先填写的交易列表和致密区块中一同发送。这只会在实际自私挖矿攻击中发生,在其它情况下交易会在提交的时候就被同步。如果接收方和发送方共享同一份提交列表,但是没有广播的交易列表,这项改进就能够移除额外的一轮通信。

    2. 如果某项确认的交易仍然是缺失的,那么接收者就会向发送者请求交易,并且发送者必须在很短的时间内返回交易。触发此机制不仅要求一次成功的实际自私挖矿攻击,还需要对交易广播进行攻击,以使节点之间产生不一致的提案交易池。若未能及时发送这些交易,会导致接收方断开链接并将发送方列入到黑名单。带有不完整确认区的区块将不会被进一步广播。

    3. 一旦确认区是完整并且有效的,节点就能够在接收所有新提交的交易之前,开始传播致密区块。在我们的协议中,一个节点需要从上游节点请求新提交的交易,同时将致密区块发送给其它节点。由于提交区的交易不会影响区块的有效性,这项改进不会降低安全性。

    前两条规则保证了因实际自私挖矿攻击造成的额外通信持续时间,不会超过一次反射。

     

    动态难度调整机制

    我们写改了中本聪共识的难度调节机制,因此:(1)自私挖矿不再有利可图;(2)吞吐量会根据网络带宽和延迟动态地进行调整。为了实现(1),我们的协议在每个难度调节周期估计全网哈希率的时候,考虑了所有区块,以确定下一个难度调节周期每个奖励单元所需的计算工作量,而不仅仅是主链的区块。为了实现(2),我们的协议根据最新难度调节周期的孤块率来计算下一个难度调节周期中主链区块的数量。最后,结合这些结果来计算区块奖励和调节目标。

    我们还引入了其它约束,来最大化协议的可兼容性:

    1. 所有的难度调节周期都有相同的预期长度 L<sub>ideal</sub> ,并且在难度调节周期 R(i) 中发放的最大区块奖励仅取决于每个难度调节周期数 i,因此动态出块间隔并不会让奖励发放机制复杂化。
    2. 我们会给主链区块数量和哈希率的预估设定多个上下限,因此我们的协议不会影响网络的去中心化以及抗攻击能力。

     

    注释

    和中本聪共识类似,我们协议的难度调节算法在每个难度调节周期末执行。该算法需要四个入参:

    名称 描述
    T<sub>i</sub> 上一个难度调节周期的目标
    L<sub>i</sub> 上一个难度调节周期的持续时间,即周期 i 和周期(i-1)的最后一个区块的时间戳之差
    C<sub>i,m</sub> 上一个难度调节周期主链区块总数
    C<sub>i,o</sub> 上一个难度调节周期的孤块总数:在难度调节周期 i 中主链包含的叔块总数

    在这些入参中,T<sub>i</sub>C<sub>i,m</sub> 由上一个难度调节决定;L<sub>i</sub> 和 C<sub>i,o</sub> 在每个难度调节周期结束后取数。孤块率 o<sub>i</sub> 由 C<sub>i,o</sub> / C<sub>i,m</sub>得到。为了简化方程,我们不会将 C<sub>i,o</sub> 包含在分母中。由于在难度调节周期末期,一些孤块可能会被攻击从而不被包含在主链中,因此 o<sub>i</sub> 是实际数据的下限。然而,只要一个难度调节周期足够长,被故意排除在外的孤块占比几乎可以忽略不计,因为孤立一条链的难度会随着链长度的增长呈指数级增长。

    该算法会输出三个值:

    名称 描述
    T<sub>i+1</sub> 下一个难度调节周期的目标
    C<sub>i+1,m</sub> 下一个难度调节周期的主链区块总数
    r<sub>i+1</sub> 下一个难度调节周期的区块奖励

    如果网络的哈希率和区块广播延时保持不变,o<sub>i+1</sub> 应该达到理想值 o<sub>ideal</sub>,除非 C<sub>i+1,m</sub> 等于其上限 C<sub>m</sub><sup>max</sup> 或它的下限 C<sub>m</sub><sup>min</sup>。难度调节周期 i + 1 在达到 C<sub>i+1,m</sub> 个主链区块时结束,无论其中包含了多少个叔块。

     

    计算调整后的哈希率估值

    调整后哈希率估值,表示为 HPS<sub>i</sub> ,是通过将阻尼因子 τ 作用于上一难度调节周期的实际哈希率 1559068235154 计算。 实际哈希率计算如下:

    1559064934639

    在这里:

    • HSpace 是所有哈希空间的大小,如在比特币中就是 2²⁵⁶
    • HSpace/T<sub>i</sub> 是找到一个有效区块预期所需要的哈希运算数量
    • C<sub>i,m</sub> + C<sub>i,o</sub> 是难度调节周期 i 中所有的区块数量

    1559068266162 是通过预期总哈希运算量除以持续时长 L<sub>i</sub> 来计算的。

    现在我们引入过滤器(Dampening Filter):

    1559064108898

    在这里,HPS<sub>i−1</sub> 表示通过上一次难度调整算法的迭代,所得出的调整后哈希率估值输出。阻尼因子保证了在两个连续的难度调节周期中,调整后的哈希率估值变动不会多于 τ 因子。这种调整相当于中本聪共识过滤器的应用。为调节速度设定边界,可以防止了攻击者随意偏置难度并伪造区块链,即使一些受害者的网络被攻击者暂时控制。

     

    区块传播建模

    由于网络的拓扑结构会随着时间不断变化,即使我们有可能为具体的区块广播过程建模,那也是非常困难的。幸运的是,对于我们的目标来说,用两个参数来表达区块广播的影响是完全足够的,这两个参数会在后面被用来计算 C<sub>i+1,m</sub> 。

    我们假设所有区块都遵循类似的区块传播模型,符合[1, 2]。在上一个难度调节周期中,一个区块广播到整个网络需要花费 d 秒,这个过程中,在该区块的父节点上的平均挖矿算力占比为 p。因此,在这 d 秒期间,会有 HPS<sub>i </sub> × dp 的哈希运算花费在父节点上,而不会为增加区块链作出贡献,余下 HPS<sub>i</sub> × d(1 − p) 的哈希算力会花费在新区块上。结果就是,在上一个难度调节周期,没有作用于增长区块率的总哈希数为 HPS<sub>i</sub> × dp × C<sub>i,m</sub>。如果这里有一部分哈希计算出了一个区块,那么其中会有一个竞争块成为孤块。被观察到的孤块哈希运算数量是 Space/T<sub>i</sub> × C<sub>i,o</sub>。如果我们忽略在同一个高度出现两个以上竞争块的小概率事件,可以得出:

    1559064685714

    也就是

    1559064995366

    如果我们将这个公式和公式(2) 联立,可以得到 dp:

    1559065017925

    在这里 o<sub>i</sub> 是上一个难度调节周期的孤块率。

     

    计算下一个难度调节周期的主链区块数

    如果下一个难度调节周期的区块广播过程和上一个一致,dp 的值就会保持不变。为了能够得到理想的孤块率 o<sub>ideal</sub> 和理想的难度调节周期时长 L<sub>ideal</sub>,推导方式和等式(4)相同。我们应该有:

    1559065197341

    在这里 1559065416713 是下一个难度调节周期中主链区块数量,那么我们的唯一目标就是获取 o<sub>ideal</sub> 和 L<sub>ideal</sub> 值。

    通过将等式(4)和(5)联立起来,我们能够解出 1559065488436:

    1559065517956

    现在我们可以设定 1559065488436 的上下限,得到 C<sub>i+1,m</sub>:

    1559065670251

    设定下限能够保证攻击者无法通过故意挖出孤块来任意提高出块间隔;设定上限能够保障我们的协议不会确认超过大多数节点能力的交易数量。

     

    确定目标难度值

    首先,我们引入一个经过调整的孤块率估值 1559065968791, 它会被用于计算这个难度调节目标:

    1559065997745

    使用 1559065968791 代替 o<sub>ideal</sub> ,能够避免当主链区块数量达到上下限时,出到一些不可控的情况。现在我们能够计算出 T<sub>i+1</sub>:

    1559066101731

    其中 1559066131427 是总哈希, 1559066158164是区块的总数.

    等式(7) 中的分母是找到一个区块所需要的哈希数量。

    注意,如果没有触发极端情况,比如 1559066329440 , 我们能够联立等式(2),(6)和(7)并且得到:

    1559066373372

    结果和我们的直觉一致。一方面,如果上一个难度调节周期的孤块率 o<sub>i</sub> 大于理想值 o<sub>ideal</sub>,那么目标就会降低,这样在哈希率不变的情况下会提高找到一个区块的难度并且增加出块间隔。因此,由于在一个区块广播过程中找到另一个区块的概率降低了,那么孤块率就会降低。另一方面,如果上一个难度调节周期的孤块率比理想值低,那么目标难度就会增加,同时降低了出块间隔,并且提高系统的吞吐量。

     

    计算每个区块的奖励

    现在我们可以计算每个区块的奖励:

    1559066526598

    这两种情况仅在边缘情况上有所不同。 第一种情况保证在难度调节周期 i + 1 中发行的总奖励不会超过 R(i + 1)。


Log in to reply