波卡运行原理系列(六)GRANDPA共识简述

定义

GRANDPA = GHOST-based Recursive Ancestor Deriving Prefix Agreement

确定性 = 敲定 = 不可逆:不会出现“冲突”的情况

活性:有效交易最终必定会上链

冲突 = 分叉:非预期的分叉会导致双重支付等各种问题,是不安全的

GRANDPA要解决的问题

保证区块链的确定性。
波卡将GRANDPA与BABE分成两个模块,BABE提供活性和概率的确定性,GRANDPA提供确定性。
GRANDPA共识与BABE或者比特币的POW不同,BABE和比特币的POW是概率确定性,而GRANDPA共识要做到100%不可逆。
之所以需要做到不可逆,因为波卡的跨链特性,需要保证跨链的交易一旦执行,绝不可能在原链上被撤销。

要解决这个问题还需要分别解决下面三个问题:

问题1

不要全部节点确认才成为不可逆的问题

因为我们没办法保证所有节点都会对某个块进行确认,毕竟网络波动的原因会一直存在,否则会极大影响效率。因此我们提出了各种BFT算法,在部分节点确认的情况下,保证网络的安全性。

这里会用到 BFT 2 次 ⅔ 共识,之所有需要2次是因为:

如上图,如果只有 1 次 ⅔ 节点确认,会有 2 个块高度为 101 的区块成为了不可逆,造成“冲突”

不会立马成为 commit, 会先成为 pre-commit, 然后 pre-commit 经过 2/3 共识后才会成为commit,就根本没有任何情况能让 2 个 N 同时成为 commit

问题2

敲定过程中的大量网络传输的消耗问题

因为需要 2 次 ⅔ 共识广播,所以 GRANDPA 的复杂度是 O(n²),随着节点数量的增加,效率也会大幅下降,比如EOS虽然只有21个出块节点,但它敲定的时间大概需要3分钟左右,而波卡的目标是全网1000个节点。

因此 GRANDPA 不是对每个pre-commit块进行逐个投票,而是将过程分为预投票和预执行,对当前最高块进行投票,通过拆解区块结构,可以一次确认若干个块,极大提高敲定效率。

如下图,每个节点选出自己认为最高块,从而确定本轮新敲定的块。

问题3

出现意外或者恶意节点的问题

问题1和2中都只考虑理想的诚实节点的情况,但实际运行时可能会出现其他情况导致“冲突”,比如下图

当网络情况不好,导致两边的蓝色诚实节点无法同步,他们各自提交自己收到的区块,而当中的恶意节点对两边的提交都进行签名(双签),从而导致网络“冲突”

除此之外,大量节点离线也导致问题。

针对这类问题,GRANDPA具有一项称为“安全责任”的功能,即通过扣除节点抵押并将其从节点集中剔除,使验证者对违反安全性的行为负责。

如果你想要重写一个之前的区块,除了需要能够控制超过 ⅓ 的节点外,你还需要承受这 ⅓ 节点的抵押被系统扣除的成本。

GRANDPA 的缺点

GRANDPA最大的缺点是敲定时间的不确定性,Edgeware上线初期就出现过几个小时无法敲定区块的现象。
不过任何设计都有代价,只能说这是 GRANDPA 追求节点数量(去中心化),必须付出的代价。

参考文献

Polkadot Consensus Part 2: GRANDPA

Polkadot 共识第 2 部分 : GRANDPA

GRANDPA Block Finality in Polkadot: An Introduction

Polkadot的区块最终确定性祖父协议GRANDPA:简介

DPOS 3.0 + BFT 为什么需要 2 次 2/3 共识

发表评论

电子邮件地址不会被公开。 必填项已用*标注