016 | 漫谈区块链共识机制

2018 年 4 月 25 日 Keegan小钢 Keegan小钢

原创文章,转载请注明:转载自Keegan小钢

并标明原文链接:http://keeganlee.me/post/blockchain/20180425微信订阅号:keeganlee_me写于2018-04-25


专栏地址:https://xiaozhuanlan.com/fullstack


共识机制是区块链的一个核心特征,是保证区块链系统在分布式架构下的一致性方案。目前主流的也有好多种共识算法:POW、POS、DPOS、RCP、PBFT、DBFT 等等。网上已经充斥了很多对这些共识算法的简单介绍,但基本流于表面而缺少深入的讲解,从而读者们也很难理解到这些共识机制背后的核心原理。而本文将以深入浅出的方式讲解区块链共识机制,但由于篇幅有限,因此,只会讲解最重要的两种区块链的共识机制,即比特币和以太坊的共识机制。

比特币共识机制

比特币是区块链的第一个应用,也是第一个实现了共识机制的,因此,要理解区块链共识机制,自然也要先从比特币共识机制开始。另外,虽然很多文章都提到比特币的共识机制为 POW(Proof of Work,工作量证明),但实际上,POW 只是整个比特币共识机制中的一部分,虽然是核心的那部分,但却不是全部。其实,比特币的分布式共识是由网络节点的 4 种独立过程相互作用而达成的:

  • 每个全节点基于一份长长的判断标准清单对每个交易进行独立验证

  • 每个挖矿节点独立将多个交易打包进新区块,通过完成 POW 算法的验算

  • 每个节点独立验证新区块并组装进区块链

  • 每个节点独立选择最长链,即在 POW 机制下累计工作量最多的那条链

先说第一种过程,对交易的独立验证。每个节点收到每一个交易之后,都会先根据一份很长的判断标准清单对该交易进行有效性校验,包括但不限于校验交易的语法和数据结构是否正确、输入和输出是否为空、输入总额是否小于输出总额、每一个输入所引用的输出是否已经被消费,等等。如果该交易通过所有验证,则可以说明该交易是有效的,那么,该节点就会将该交易放入本地的交易池(或称内存池),并将该交易广播给其他相临的节点。如果没通过验证,则会废弃该交易,也不会将其广播出去。其他节点接收到该交易后,也各自做同样的独立校验,校验为交易有效之后,同样也放入各节点自己的交易池,并继续广播给其他节点。所以,理论上来说,无效的交易一开始就会被废弃,而有效的交易最终会到达整个网络所有节点,并被每个全节点所保存,即全网达成了“该交易有效”的共识。

接着,再来聊聊第二种过程,了解有效的交易是如何被打包进区块的。经过一段时间后,一般是 10 分钟左右,每个节点的交易池里会收集到很多有效但还未确认的交易,这些交易会组装成一颗 Merkle Tree。关于 Merkle Tree 的结构,我们在之前的文章《014|从微观到宏观理解区块链》已经讲过,这里就不赘述了。不过,组装进 Merkle Tree 的第一笔交易是比较特殊的,这是一笔创币交易,也叫 Coinbase 交易,新的比特币就是从该笔交易产生的。这笔交易是由节点自己创建的,并将挖矿奖励支付到矿工自己的地址,挖矿奖励包括新创建的比特币和打包进该区块所有交易的手续费总额。组装好 Merkle Tree 之后,就得到 Merkle Root,再结合区块头的其他 5 个字段——Version、Pre Block、Times、Difficulty、Nonce,总共 6 个字段合在一起经过两次 SHA256 计算得到区块哈希值。一个有效的区块要求其哈希值必须小于 Difficulty 难度值,写作本文时的难度要求哈希值至少已经有 18 个 0 开头。挖矿其实就是通过修改参数的值而不断计算区块哈希值,直到计算出符合难度要求的哈希值。一般是通过修改 Nonce 值来计算区块哈希值,其他 5 个字段基本是不变的。而由于哈希函数的特性,难度值越大,理论上计算出符合要求的哈希值所需的计算量就越大。举个简单例子,比如你扔三个骰子,如果难度要求总和小于18,那是非常容易达到的,基本扔个一两次就能满足要求了;而如果加大难度,要求总和小于9,那从概率上来说相对就没那么容易了,可能要扔个十几次甚至几十次才能达到;而如果要求总和等于 3,那只能扔出三个 1 才行,这谁都知道要达到的概率是很低的,也许扔个一两百次才可能出现。因此,从统计学来说,一定的难度值可以推算出概率上对应所需的计算次数,也就是“工作量”,所以,只要你达到了难度要求,也就间接证明你付出了对应的工作量,这就是工作量证明

当某个节点计算出符合难度要求的区块哈希时,即说明该矿工挖矿成功了,该节点就会将此区块组装到本地的区块链,同时也将此区块广播给其他节点。然后,就进入第三种过程了。当其他节点收到此区块时,也会各自独立验证该区块是否有效。和独立验证交易一样,也存在一份验证标准清单,包括但不限于校验引用的上一个区块是否是否正确、难度值是否符合标准、区块哈希是否真的符合难度要求、Coinbase 交易中的挖矿奖励是否多于应得的、整个区块的每笔交易是否都是有效的,等等。其中,难度值是有标准的计算公式的,每个节点都会根据标准公式独立计算实际的难度值,所以,矿工如果不按照标准而自己设置一个较低的难度,在其他节点是无法通过的。同样,挖矿奖励也是有标准公式的,所以,如果矿工给自己奖励过多的比特币,在其他节点也是同样无法通过的。每个节点验证该区块为有效之后,也会各自将该区块组装进它们本地的区块链,并继续将该区块广播给其他节点。

由于所有节点同时在挖同一个区块,就有可能会出现多个节点同时挖出了同个区块,并都将各自挖到的区块广播到其他节点。假设有两个节点同时挖出了新区块,分别为区块 N1 和 N2,它们的上一个区块都是 P。有些节点会先收到 N1,它们会将 N1 先组装进它们本地的区块链,也称为主链。但之后不久,这些节点也会收到 N2,这时候,它们会将 N2 放入备选链。而其他节点则先收到 N2 再收到 N1,则 N2 在它们的主链上,而 N1 在它们的备选链上。这时候,整个区块链暂时就分成了两个分叉,而要打破这种局面,就要看下一个生成的区块是基于 N1 还是 N2 了。如果下一个区块是基于 N1,自然,N1 的这条链就变成了最长链,也是累计工作量最多的链。那么,那些将 N2 链设为主链的节点就会根据实际情况自己选择将 N1 链改为主链,而 N2 将成为孤块而被废弃。

以上就是比特币共识机制的核心内容了,说白了其实就是根据一些所有节点都认可的标准对每个交易和区块的创建和校验进行独立验证,当大多数节点都认可并写入自己的区块链的时候,就自动形成了分布式共识。所有区块链基本都是这个逻辑,不同区块链主要在于制定的标准不同,比特币主要就是基于 POW 机制,这种机制实现简单,但它会造成大量的能源浪费,由于所有节点同时竞争挖矿同一个区块,而基本只有一个节点能胜出,那其他未胜出的节点所消耗的算力能源就白费了。另外,每次交易确认(即出块时间)大概 10 分钟,一笔交易一般要有 6 次确认才算安全,那基本就要 1 个小时了,这共识达成的时间太长了。

以太坊共识机制

以太坊的共识机制也是基于 POW 的,但与比特币相比,主要有两点不同:一是挖矿时间控制在 10 ~ 19 秒之间,出块时间比比特币快了很多;二是对于孤块也有挖矿奖励。在比特币中,孤块(即上文的 N2 区块)是会被丢弃的,挖出了孤块的矿工是得不到任何奖励的。但在以太坊中,孤块是能被打包进区块里的,如果后续的区块将前面产生的孤块也打包进区块里,那这个孤块就变成了叔块,那么,挖到这个叔块的矿工就能得到奖励,而将叔块打包进区块的矿工也能得到额外的奖励,但每个区块最多只能包含两个叔块,而且也不能包含太久的孤块,最多只支持到 7 层的祖先孤块。由于以太坊的出块时间短很多,那自然更容易出现临时分叉而产生孤块,而且这么短的时间内,每个区块也很难能够在全网充分传播,那对于网速慢的矿工来说,就非常吃亏了。所以,为了平衡各方利益,以太坊才设计了叔块机制。写作本文时,叔块率在 16.9% 左右。

不过,以太坊正在计划从 POW 机制切换为 POS(Proof of Stack,权益证明)机制,其新的共识机制名为 Casper,其存在两个不同实现的版本,分别是:

  • Casper the Friendly Finality Gadget(FFG)

  • Casper the Friendly GHOST: Correct-by-Construction(CBC)

Casper FFG 是由 Vitalik 主导的,侧重于通过逐步迭代实现,慢慢过渡到 POS 机制。而 Casper CBC 则是由 Vlad Zamfir 主导的,不同于传统的协议设计方式,即先定义完整的协议,CBC 协议在开始阶段只是部分确定的,其余部分协议以证明能够满足所需/必需属性的方式得到。不过,也只是两种不同的方法,关于 POS 的核心理念还是一致的。相对来说,FFG 比较容易理解,也很大可能是即将第一个部署到以太坊的 Casper 版本,所以下面的篇幅主要讲解 FFG。

FFG 版本的 Casper 是一种混合 POW / POS 的共识机制,该机制下的每次出块依然还是采用 POW 挖矿机制,但每 100 个区块会增加一个 POS 检查点(checkpoint),通过验证人(validator)来评估区块的最终有效性。创世区块是一个检查点,区块高度为 100 的倍数的区块也是检查点,将这些检查点连起来就组成了一条检查点链(checkpoint chain)。检查点一般会有两种状态:justified 和 finalizedfinalized 则表示已经确定为最终有效的,该状态的检查点至少已经存在一个子检查点,justified 则表示该检查点是已经被证明合理的,finalized 的检查点一定是 justified 的,但反过来则不一定。而一个检查点是否有效,是通过多个验证人投票得出的结果。下面,我们就来简单聊聊这个过程。

首先,要成为验证人,是需要投入保证金的,即抵押一定量的以太币作为权益证明,才有资格成为验证人。投入保证金是通过广播一条 deposit 消息进行操作的,只要这条消息是有效的并被打包进区块中,那就能加入验证人集合(validator set),成为其中一个验证人。另外,如果要退出验证人集合,则可以再广播一条 withdraw 消息。不过,需要注意,一旦退出后,该验证人的公钥将被永久禁止再次加入验证人集合。

接着,成为验证人之后,就可以开始投票选举检查点了,通过广播一条 vote 消息到网络中。vote 消息主要包含五个信息:两个检查点 s 和 t,以及这两个检查点的高度 h(s) 和 h(t),以及验证人的公钥 ν。要求 s 必须是 t 的祖先,一般来说,t 就是最新的检查点,而 s 是上一个已经确定为最终有效的检查点。另外,还要求验证人的公钥 v 必须在验证人集合中找得到,否则都认为该投票是无效的。当超过 2/3 的验证人(实际上是 2/3 的总保证金)都投给了 (s, t) 这对检查点时,那 s 就是 finalized 的,t 则是 justified 的。而且,那些投注了 (s, t) 的验证人还会得到货币奖励,得到的奖励是和抵押的保证金成比例的,就是说抵押的保证金越多,得到的奖励越多。这个奖励也可以理解为抵押保证金的利息。

另外,Casper 设置了两条戒律:

  1. 验证人不能发布两个 h(t) 相同的投票,即如果存在两个投票:<ν, s1, t1, h(s1), h(t1)> 和 <ν,s2,t2,h(s2),h(t2)>,那么 h(t1) = h(t2) 是不允许的;

  2. 如果 h(s1) < h(s2) < h(t2) < h(t1),则第一个投票的跨度已经涵盖了第二个投票,这也是不允许的。

如果验证人违反了上面的戒律,则会对验证人进行惩罚,没收他抵押的保证金。

最后,Casper 对分叉链的选择不同于 POW 机制下选择累计工作量最多的那条链,Casper 对分叉链选择的规则就是选择 justified 检查点高度最大的链,原文是:

  • FOLLOW THE CHAIN CONTAINING THE JUSTIFIED CHECKPOINT OF THE GREATEST HEIGHT.

很明显,以太坊的共识机制和比特币相比复杂得多,主要在于两点引起的:一是大大缩短了出块时间,二是引入了 POS 机制。在 POW 机制下将出块时间缩短到十几秒,虽然加快了性能,但其实减低了安全性,因为会引入很多其他问题,比如新区块难以在这么短的时间内扩散到全网,比如分叉链出现的概率更大,为了解决这些问题,就需要设计更多共识协议来提高安全性。引入 POS 机制变成 POW + POS 的混合机制,那这种复杂度不是 1 + 1 = 2 这么简单的。

思考和实践

EOS 的共识机制是怎样的?其安全性和性能又如何呢?


扫描以下二维码即可关注订阅号。


登录查看更多
1

相关内容

Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。
[ICML2020]层次间消息传递的分子图学习
专知会员服务
33+阅读 · 2020年6月27日
最新《医学图像深度语义分割》综述论文
专知会员服务
94+阅读 · 2020年6月7日
近期必读的12篇KDD 2019【图神经网络(GNN)】相关论文
专知会员服务
62+阅读 · 2020年1月10日
【新书】Python中的经典计算机科学问题,224页PDF
专知会员服务
51+阅读 · 2019年12月31日
资源|Blockchain区块链中文资源阅读列表
专知会员服务
43+阅读 · 2019年11月20日
【白皮书】“物联网+区块链”应用与发展白皮书-2019
专知会员服务
93+阅读 · 2019年11月13日
工行基于MySQL构建分布式架构的转型之路
炼数成金订阅号
15+阅读 · 2019年5月16日
基于Web页面验证码机制漏洞的检测
FreeBuf
7+阅读 · 2019年3月15日
递归神经网络
Datartisan数据工匠
4+阅读 · 2018年8月2日
李开复:已退掉所有区块链3点钟群 | 早报
中国企业家杂志
4+阅读 · 2018年3月8日
【区块链】区块链是什么?20问:读懂区块链
产业智能官
8+阅读 · 2018年1月10日
【动画连载】3分钟了解什么是区块链(中文动画)
威胁情报浅析
计算机与网络安全
7+阅读 · 2017年11月15日
基于注意力机制的图卷积网络
科技创新与创业
73+阅读 · 2017年11月8日
一个人的企业安全建设之路
FreeBuf
5+阅读 · 2017年7月7日
A Survey on Edge Intelligence
Arxiv
50+阅读 · 2020年3月26日
Talking-Heads Attention
Arxiv
15+阅读 · 2020年3月5日
Arxiv
35+阅读 · 2019年11月7日
Arxiv
19+阅读 · 2019年4月5日
Simplifying Graph Convolutional Networks
Arxiv
12+阅读 · 2019年2月19日
Arxiv
22+阅读 · 2018年2月14日
Arxiv
10+阅读 · 2018年2月4日
VIP会员
相关VIP内容
相关资讯
工行基于MySQL构建分布式架构的转型之路
炼数成金订阅号
15+阅读 · 2019年5月16日
基于Web页面验证码机制漏洞的检测
FreeBuf
7+阅读 · 2019年3月15日
递归神经网络
Datartisan数据工匠
4+阅读 · 2018年8月2日
李开复:已退掉所有区块链3点钟群 | 早报
中国企业家杂志
4+阅读 · 2018年3月8日
【区块链】区块链是什么?20问:读懂区块链
产业智能官
8+阅读 · 2018年1月10日
【动画连载】3分钟了解什么是区块链(中文动画)
威胁情报浅析
计算机与网络安全
7+阅读 · 2017年11月15日
基于注意力机制的图卷积网络
科技创新与创业
73+阅读 · 2017年11月8日
一个人的企业安全建设之路
FreeBuf
5+阅读 · 2017年7月7日
相关论文
A Survey on Edge Intelligence
Arxiv
50+阅读 · 2020年3月26日
Talking-Heads Attention
Arxiv
15+阅读 · 2020年3月5日
Arxiv
35+阅读 · 2019年11月7日
Arxiv
19+阅读 · 2019年4月5日
Simplifying Graph Convolutional Networks
Arxiv
12+阅读 · 2019年2月19日
Arxiv
22+阅读 · 2018年2月14日
Arxiv
10+阅读 · 2018年2月4日
Top
微信扫码咨询专知VIP会员