共识算法是所有区块链的基础,它们构成了区块链平台中的最重要部分。迅雷链采用独创的同构多链框架,而且通过优化的DPoA+PBFT共识算法实现了秒级确认。本文从技术层面深度剖析共识算法的背景、原理及分类,以及迅雷链PBFT算法的详细解读。
区块链是一种由多节点共同维护,共同信任的分布式存储系统,它可以用于登记和发行数字化资产、产权凭证、积分等,并以点对点的方式进行转账、支付和交易。
区块链系统与传统的中心化账本系统相比,具有完全公开、不可篡改、防止多重支付等优点,并且不依赖于任何的可信第三方。
由于点对点网络下存在较高的网络延迟,各个节点所观察到的事务先后顺序不可能完全一致。
因此区块链系统需要设计一种机制对在差不多时间内发生的事务的先后顺序进行共识。这种对一个时间窗口内的事务的先后顺序达成共识的算法被称为“共识算法”。
共识算法在区块链系统中的位置图
共识算法通常被应用在分布式系统中,区块链系统从广义上也可以被看做一个分布式系统。
共识算法保证区块链系统中每一个节点之间事务记录的一致性,同时起到防范系统遭受诸多种类的安全攻击,包括拜占庭攻击、女巫攻击、51% 攻击等。
共识算法背景
CAP定律
CAP 定律(Consistency,Availability,Partition Tolerance theorem),说的是在一个分布式计算机系统中,一致性,可用性和分区容错性这三种保证无法同时得到满足,最多满足两个。
其中,分区容错性指的是在网络中断,消息丢失的情况下,系统照样能够工作;一致性说的是分布式系统中,所有节点在同一时刻看到同一个值;可用性说的是每个请求都会收到一个应答,无论该应答是成功还是失败。
而对于分布式数据系统,分区容忍性是基本要求,否则就失去了价值。因此分布式数据系统在一致性和可用性之间取一个平衡,不可能二者同时达到。
对于迅雷链而言,数据在任何时刻的不一致都是一种不好的用户体验,因此迅雷链选择保证数据绝对一致性,并以提高强一致性算法的可用性为努力的方向。
FLP 不可能原理
在网络可靠,存在节点失效(即使只有一个)的最小异步模型系统中,不存在一个可以解决一致性问题的确定性算法。即:
异步分布式系统不存在任意场景下都能实现共识的算法。在异步网络环境中只要有一个故障节点, 任何共识算法都无法保证正确结束。
因此,在迅雷链中,选用了实用拜占庭容错算法(PBFT),一方面通过容错性,降低节点失效对整个分布式系统的影响,另一方面采用多次重试和更换失效节点机制,降低节点间长时间失效的概率,保证系统的可用性。
状态机复制
状态机复制是一项很有效的容错技术。
在这个模型中,程序(比如一个 apache server)被视为一个一致性状态机,意思就是给程序一定顺序的输入请求 ,程序执行后相关处理数据结果就会在多个节点中达成一致的状态。
也就是说如果给予每个节点的输入请求序列顺序一致,在执行相同操作的前提下,这些节点就会达成相同的状态。
每个节点都包含一个状态机,在节点间共识数据的结果将在状态机中体现。状态机中的数据将是外界获取数据的来源。
共识算法分类
在区块链系统中,共识算法作为保证分布式节点间数据一致性的算法,可以被分为两大类,即概率一致性算法和绝对一致性算法。
概率一致性算法指在不同分布式节点之间,有较大概率保证节点间数据达到一致,但仍存在一定概率使得某些节点间数据不一致。
对于某一个数据点而言,数据在节点间不一致的概率会随时间的推移逐渐降低至趋近于零,从而最终达到一致性。
例如工作量证明算法(Proof of Work, PoW)、股份证明算法(Proof of Stake, PoS)和委托股权证明算法(Delegated Proof of Stake, DPoS)都属于概率一致性算法。
而绝对一致性算法则指在任意时间点,不同分布式节点之间的数据都会保持绝对一致,不存在不同节点间数据不一致的情况。
例如分布式系统中常用的 PAXOS 算法及其衍生出的 RAFT 算法等,以及拜占庭容错类算法(类 BFT 算法)。
一般而言,回顾上面所述 CAP 原理,概率一致性算法保证了系统的可用性而牺牲了系统的一致性,绝对一致性算法则与之相反,保证了系统的一致性而牺牲了系统的可用性。
各算法之间对比如下表,★数量越多,代表相应对比项表现越好。
迅雷链的业务需求保证分布式系统中的强一致性,并具备一定的容错和防拜占庭节点作恶的能力,因此选择类 BFT 算法作为共识算法。
在实用拜占庭容错(PBFT)算法的基础上,为了解决算法网络消耗高的问题,作出了一些优化,提高了算法的可用性。
下面首先介绍区块链中最常用的强一致性算法——实用拜占庭容错(PBFT)算法。
PBFT 算法介绍
假设系统中节点数量为 R=3f+1,其中 f 为系统中拜占庭节点的数量。
在发送消息的时候通过环境状态、时间戳、请求、回复信息,客户端同样等待2f+1个回复,同时保证签名、时间戳、回复信息来保证一致。
这里存在两种情况,一种是客户端请求超时,那就再发送一次,如果是主节点 P 出故障,那就改变环境状态,新选一个 P 节点。保证第二次的执行过程。
在实际的算法流程中,PBFT 算法定义三个任务阶段:预准备(pre-prepare)、准备 (prepare)、确认 (commit)。
预准备:P 分配一个系统序列号 ID,发送给所有 B 节点。
发送格式(环境状态、ID、信息摘要、客户端请求)。B 节点验证信息摘要和客户端请求一致,验证当前环境状态编号。
准备:B 节点在接收信息后加上自己的消息日志,发送至其余节点。P 和 B 节点同时验证消息签名,如果一致,那么就把验证通过写入消息日志。每个节点在准备阶段对每个副本节点验证预准备的消息和准备消息一致性检查完毕。
确认:在前面两个极端一切正常的话,在同一系统环境中,所有请求序号一致,验证消息一致,简单理解就是确认 2f+1 个节点发送了之前发送的序号和消息。
每个节点接受确认消息,签名正确;消息的系统环境编号 V 与节点的环境编号 V 一致;消息的序号 ID 满足序列要求。节点通过确认至少 2f+1 个副本信息,保证整个系统中算法的正确性。
图中,C 是客户端,0、1、2、3 是分布式系统中的节点成员,其中由 0 节点提议区块,,1、2、3 节点对提议出来的区块进行投票,其中 3 节点已发生故障。我们默认 3 发送信息为无效。那么 PBFT 算法执行的流程如下:
C 发起一笔请求到 0 号节点。
节点 0 开始对请求排序编号,并把请求序号发送到 1、2、3 节点。
1、2 节点互相之间和 0 节点之间发送消息。
0、1、2 之间确认 0 节点的分配序号,互相确认。
0、1、2 确认信息回复 C。
客户端 C 判断收到确认是否在 2f+1 内,确认结果。
在每一轮共识分三个阶段达成共识:Pre-Prepare、Prepare 和 Commit,整个流程如下:
从全网节点选举出一个提议节点(Proposer),新区块由提议节点负责生成。
每个节点把客户端发来的交易向全网广播,提议节点将从网络收集到需放在新区块内的多个交易排序后存入列表,并将该列表向全网广播。
每个节点接收到交易列表后,根据排序模拟执行这些交易。所有交易执行完后,基于交易结果计算新区块的哈希摘要,并向全网广播。
如果一个节点收到的 2f 条来自其它节点发来的摘要都和自己的相同,就向全网广播一条 commit 消息。
如果一个节点收到 2f+1 条 commit 消息,即可提交新区块及其交易到本地的区块链和状态数据库。
迅雷链共识算法
迅雷链采用了同构多链架构,将不同的账户锚定在不同的同构链上,然后接入层将交易路由到发送方所在的链上进行区块打包与共识。
共识成功的区块中的交易会根据接收方所在的链的不同,跨链转发到相应的链上。若交易接收方与发送方同属于一条链,则不再进行交易转发。
在每一条同构链上,验证人节点对打包好交易的区块进行共识。共识采用优化过的 PBFT 算法。
以处于某一区块高度的共识操作为例,由于共识的达成需要超过 2/3 的节点确认,因此每一次共识可能需要多轮投票才能达成。
与传统的 PBFT 算法类似,对于每一轮共识操作,又包括三个阶段:Propose,Prevote 和 Precommit。
当在某一轮达成共识 (收到 +2/3 的 Precommit 投票) 后,就会进入对下一个高度的共识,从第 0 轮开始。下面简单介绍下详细的步骤:
首先介绍关于锁定区块的概念,表示在某个特定的高度和轮数,节点对某个块收到超过节点总数 2/3 的 Prevote 投票集合后,则此节点对于此高度此轮的区块进行锁定。也就是说,节点以锁定区块来表示对某一个区块的认可。
Propose 阶段:系统中所有验证人节点轮流作为提议者提出提议,而系统中非提议者的节点在收到提议后,就会进入 Prevote 阶段。如果当前节点此前存在已锁定区块,则还需要收集所有针对已锁定区块的 Prevote 投票。
PreVote 阶段:当节点进入到 Prevote 阶段后,每个节点广播自己的 PreVote 投票。
具体的,如果当前区块高度或投票轮数高于此前已锁定的区块高度或轮数,则将原锁定的区块进行解锁。
如果此时节点仍含有未解锁的区块,则对此锁定的区块投 PreVote 投票。或者如果节点收到合法的 Propose 区块,则对此区块投 ProVote 投票。
当阶段超时或者接收到大于 2/3 的针对某个块的投票后,则节点锁定此区块并进入
PreCommit 阶段:当节点存在已锁定区块,则对此区块投 PreCommit 投票。当节点收到针对已锁定区块大于 2/3 的 PreCommit 投票是,就可以将这个块 Commit,并且进入针对下一个高度块的共识。
若 PreCommit 阶段定时器超时,则节点保存已锁定区块,然后重新返回到 Propose 阶段。
各节点通过在以上阶段上循环,对区块进行一致性共识。与 PBFT 算法类似,迅雷链共识也经过了三阶段提交,但通过引入区块锁定操作,通过缓存待确认区块,降低了未达成共识情况下重复通信区块带来的网络压力,从而提升了共识效率。
本文来源：北国网
责任编辑：
付晓萌_NB7161
