互联网计算机共识协议介绍

互联网计算机共识协议(ICC)本质是一种优化版的 BFT 共识算法。本文对官方文章 Achieving Consensus on the Internet Computer 做了一些总结和梳理,旨在介绍互联网计算机(Internet Computer,简称 IC)的共识协议。

需要注意的是,互联网计算机由子网组成,每个子网相当于一条独立的区块链,节点只在子网内部参与共识,跨子网的信息不参与共识而是由 Chain Key 技术来提供验证。所以本文所讲的共识算法,仅指的是子网内部的共识算法。

概况

对什么达成共识?

互联网计算机(Internet Computer)是 Dfinity 基金会推出的自适应区块链,其智能合约(canister)可以承载传统 web 应用,因此也可以理解为一种去中心化的云服务平台(类比AWS、阿里云)。

互联网计算机由分布在世界各地数据中心中的节点组成:

  • 数据中心运维节点,提供底层硬件。
  • 节点会被划分为各个子网,并在子网内完成共识,子网数量可以增加。
  • 应用以 canister 为单元运行于子网中,canister 为 IC 的的智能合约。

共识的内容为:用户与 canister 之间的通信、canister 之间的通信以及这些通信的顺序。不同节点收到的信息的顺序可能不一样,但是处理信息的顺序必须相同。

image.png

共识目标

在不正常(恶意、掉线等情况)节点数小于总节点数的三分之一时,都能保证以下三个特性:

  • 安全性:在某个时刻如果两个节点认为他们对区块链达成了共识,那么他们实际上他们所看到的区块链就应该是同样的;
  • 活跃性:区块会持续增长,系统会持续处理新增信息;
  • 有效性:区块链中所有的区块和区块中的信息都是有效的,比如所有信息都被其发送者正确签名了;

共识组成部分

  1. 区块构造:构造候选区块
  2. 公证:保证区块的有效性
  3. 随机数灯塔:对随机性达成共识以加速
  4. 敲定:确定共识达成的时间

下面以一个4节点的子网为例,按照共识的四个组成部分来描述子网是如何达成共识的。

一、区块构造

子网中的节点充当区块构造器,负责构造区块并通过向子网广播提议新区块。

在某个特定的区块高度,比如区块高度 30,区块构造器负责把所有可获得的有效信息打包到一个区块中,然后广播。

有效信息包括:用户与 canister 的通信、 canister 之间的通信以及这些通信的顺序。

image.png

二、公证

公证过程中,节点使用 BLS 门限签名(2f + 1)对区块进行公证,当三分之二的节点验证并签名一个区块时,这个区块就获得了公证。节点的私钥通过 DKG (分布式密钥生成)来产生。

BLS 门限签名算法可以将同一个信息的多个签名聚合为一个固定大小的签名。这意味着即使子网很大公证节点很多,公证的大小也会很小。

某些节点提议的区块可能是无效的,所以每个区块都必须经过公证,公证这一步骤使得每一轮都至少有一个有效区块产出。

以一个由 4 个节点组成的子网为例,假设当前区块高度为 29,并且之前的区块都已被公证过。

当节点 1 收到一个新的区块时,节点 1 会验证此区块,如果区块有效,节点会给这个区块一个签名,这个签名叫做公证份额(notarization share),然后把这个签名发送给子网中的其他节点,以表明节点 1 认为这个区块是有效的。

当节点 1 收到了节点 3 和 节点 4 对区块 30 进行了公证份额, 那么几个公证份额就会合成一个公证,这时区块 30 就得到了公证(总共有 4 个节点)。

image.png

如果节点公证了一个有效的区块30 后,又有一个有效的区块出现,那么也可以继续公证。

因为不同的节点可能对不同的区块进行了打包,进而公证的区块也可能不一样,如果在一个区块高度只公证一个区块,那么就可能出现所有区块都没有获得足够的公证份额,而导致区块链在这一高度卡住。

这意味着在同一个区块高度,可能会有多个区块被公证,此时的区块链可能是下图这个样子:

image.png

三、随机数灯塔

公证过后,每个区块高度可能会出现多个区块,这增加了达成共识的难度。因此 ICC 共识协议就使用随机数灯塔来减少每一轮产生的公证区块数。

在每个区块高度,子网内都会有一个共享的随机数叫做随机数灯塔,随机数灯塔是可验证且不可预测的。

节点使用 BLS 门限签名(f+1)对上一轮的随机数灯塔签名,当二分之一的节点对一个随机数灯塔签名,那么就会产生一个新的随机数灯塔,这将为子网共识提供随机性。

image.png

区块构造器排序

有了随机数灯塔,子网就可以使用随机数灯塔来对节点排序,节点会优先公证排名靠前的节点打包的区块,并且当节点看到了已公证的区块后就不再公证其他区块,进而减少每轮产生的区块数。

比如可以使用第 29 轮公证的随机数灯塔来对第 30 轮公证的区块构造器来排序。比如顺序为:节点1、节点4、节点2、节点 3 。顺序是随机的,并且由随机数灯塔来提供随机性。

当进入新一轮的公证后,计时器开启。开始时,节点只会对 只有排第一的节点打包的区块进行公证。

比如在第 30 论公证时,节点 1 收到了一个有效的区块,但这个区块是由节点 4(排名第二)的节点发起提议的,所以节点 1 暂时不会对这个区块签名而是继续等待。如果节点 1 收到自排名第一的区块构造器构造的区块,那么节点 1 就会对这个区块签名。

如果一段固定时间之后,节点1 还没有提供有效的区块,那么节点就会开始公证节点 4 (排名第二)打包的区块,依次类推。

image.png

在大多数情况下,每轮都只会有一个区块被公证,但在某些情况下还是会产生两个及以上的区块,区块链还没有完成共识,因此我们还需要一个最终确认共识的步骤,那就是敲定。

image.png

四、敲定

公证过程遗留下的问题是:每一轮依旧可能产生两个及以上的区块,节点怎样才能知道某一高度是否达成了共识呢?

一个简单的方法是,一个节点可以等待一段足够多的时间, 只要有一个区块被公证,那么就认为此轮的共识已经达成。

但是这是一种很有风险的方法。因为如果网络出现问题,有些节点可能没有收到公证过的区块,这意味者,如果节点不等待足够久的时间,就无法保证安全性。

所以矛盾就产生了,为了提升用户体验,出块需要足够快,但是为了保证链的安全性,又要要求节点等一段比较长的时间。

为了解决这个矛盾,共识的达成使用了一种新的机制:使用了一种异步分离的机制来达成最终的共识,那就是敲定。

敲定的过程是,使用 BLS 门限签名(2f+1)来认证那些只公证了一个有效区块的区块高度,并剔除其他分支,这就形成了单一路径的区块链,这样区块就达成了共识。

具体过程为,在区块高度 30,当节点 1 收到一个公证过的区块 A,并且节点 1 没有对其他区块进行过公证,那么它就会给区块 A 一个签名,叫做敲定份额。这代表着节点 1 在这个高度只公证过一个区块。

而当超过三分之二的节点都对区块 A 给出公证份额的话,那么就表明三分之二的节点在区块高度 30 都只公证过一个区块,那么剩下的三分之一无论如何都不会再能公证出其他区块(那怕加上恶意的节点),那就证明了在区块 30 这个区块高度,有且仅有区块 A 通过了公证。那么节点在这个高度就对区块链达成了共识。

image.png

然后就可以剔除这个高度之前出现的分支:

image.png

总结

互联网计算机共识协议(ICC)本质是一种优化版的 BFT 共识算法,负责子网内部的共识,而跨子网的通信由 Chain Key 技术来提供验证方法但并不参与共识。

对于子网内的共识,在每个区块高度,首先节点会将所有的有效信息打包为区块进行并广播,然后根据随机数灯塔对节点打包的区块随机排序,排名靠前的区块将优先被公证,但每一轮有可能产生两个及以上的区块,最后如果在某个高度只公证了一个区块,那么区块链将在这个高度达成共识,并删除之前存在的分支。