科普

分布式共识的工作原理,Part-4:非确定性共识算法

Ajian   |     |   2110 次阅读

Part-1:分布式系统的定义及属性
Part-2:共识问题与 FLP 不可能定理
Part-3:使用同步假设的共识算法


除了在算法中使用同步假设,还有什么办法可以解决 FLP 不可能问题?

方法二:非确定性算法

如前所述,为了解决 FLP 不可能性,大部分拜占庭容错协议最终都要基于同步性假设的前提。然而,解决 FLP 不可能性还可以另辟蹊径:非确定性算法。

当当当当,中本聪共识!

认真听讲的同学应该还记得,在传统的共识中,状态转变函数 f(x) 是这样定义的:提案者和一众接收者必须全体协作决定下一状态的值。

这种做法未免过于复杂了,因为这要求我们明晰每一个节点的状态,并且 每一个节点都要与其余所有的节点交换数据(也就是说信息交换量达到 O(n^2) )。由此显而易见,传统共识不具备良好的可拓展性,且无法在开放、用户能无需特别许可,随时加入随时退出的分布式系统中达成。

中本聪共识的精妙之处在于把上述问题转变成一个概率问题。与其让所有节点对一个确定的值达成一致,不如构造 f(x) 来使所有节点对某一输出值正确性的概率达成一致。

等等,你是不是又觉得我没在说人话了?

拜占庭容错

和传统共识先选本轮领导、再节点协作的模式不同,中本聪共识是基于哪一个节点最快计算出难题达成的。比特币区块链中每一个新区快都由本轮最快计算出数学难题的节点添加。整个分布式网络持续不断地建设这条有时间戳的区块链,而承载了最多计算量的区块链正是达成了共识的主链(即累积计算难度最大)。

最长链不仅是区块顺序的明证,也是 CPU 算力最大消耗的明证。因此,只要绝大多数的算力掌握在诚实的节点手中,这些节点继续帮助建设最长链,就能保证最长链始终比攻击者的区块链更长,共识不被破坏。

区块奖励

中本聪共识之所以行之有效,是基于这样一个合理假设:节点会为了下一个区块的记账权而不断扩充自己的算力。它的巧妙之处在于设计了经济激励,节点需要不断解决大计算量难题来获取赢得大额奖励的机会(即区块奖励)。

防女巫攻击

工作量证明需要解决计算难题的特点天生可以抵抗女巫攻击。整个系统不需要任何 PKI 或是其它花哨的身份认证策略。

点对点 gossip

应用 gossip 协议 是中本聪共识的一大创举。在无法假设节点之间连接状态是否良好的分布式系统中,gossip 协议更适合点对点数据传输。与其他协议不同,我们假定节点只和有限的几个其他节点相连,然后在节点之间利用点对点协议以 gossip 协议传输消息。

在异步环境下不是“严格”安全的

在中本聪共识中,安全性是一定概率下的安全性——在我们构建最长链的过程中,每一个新区块的加入都在降低攻击者伪造替代链得手的概率。

因此,中本聪共识在异步网络的前提下不具备严格安全性。下面我们好好掰扯一下为什么。

在异步通信的前提下,一个分布式系统的安全性体现在它能排除异步网络的影响,能维持一份一致的事务日志。换言之,就是一个节点在随时离开网络后,无论在何种网络状况下再次加入系统,都能仅仅根据区块链的创世块找到最近一个正确的区块。新加入的诚实节点能查询到过去任意高度上的区块,而恶意节点无法伪造可信的虚假区块信息。

本文前面提到的传统共识算法满足这种严格安全性,是因为每一个事务都有一个确定值。只要保证了每个值的确定性,就能知道过去任意时刻的状态。但比特币不满足“严格”异步安全,因为攻击者可能屯聚巨量算力,盘踞于网络一隅,以超过诚实节点生成区块的速度制造自己的替代链,从而在替代链上成功实施双花攻击。

诚然,攻击者不仅要耗费巨量哈希算力,也要付出一大笔资金。

本质而言,比特币区块链的不可篡改性就是因为绝大多数矿工不想切换到另一条替代链。为什么呢?因为即使相互串谋,动员到能让区块链网络切换成替代链的算力也太难了。因此可以这么说,由于切换替代链攻击的可能性过于低,在实际应用中可以把这种风险性忽略不计。

中本聪共识 vs. 传统共识

从应用角度出发,中本聪共识具备拜占庭容错性。但因为它显然无法达成共传统共识研究者们所认同的共识,所以起初学界并没有将它归入拜占庭容错协议的家族中去。

从设计上讲,中本聪共识成就了任意节点加入分布式网络的可能性,使节点无需知道其他节点的全集就能正常工作。做出这样伟大的设计要我怎么夸你呢!感谢你,中本聪。

中本聪共识较传统共识更为简单,它消除了点对点通信、领导人选举、平方级通信复杂度等等复杂的操作。

这一切都使得它能在现实条件下轻松部署,不愧是比 PBFT 更“实用”(“practical”)的好弟弟。

Conclusion结语

以上便是分布式系统和共识知识的基础概述。探索之路漫长而曲折,布满荆棘,而今时今日分布式计算的发展已然这般巧妙。希望这篇文章能为你在这个领域的研究带来一点帮助。

中本聪共识的创新确真伟大,它推动了一股新的技术潮流,从研究员、科学家到开发者和工程师,他们都在积极探索,尝试打破共识协议研究领域旧有的边界。

随着中本聪共识的落地,各种各样新的共识协议在它的基础之上百花齐放:除了 Proof-of-Steak ,你还能列举出哪些呢?;) 这里我先卖个关子,欲知后事如何,且听下回分解!

注意:为了不至于把文章写成一本书,本文仍有许许多多重要的论文和算法未曾提及。例如,Ben Orr 的 Common Coin 项目也用了概率手段解决共识问题,但不具备最优范围弹性。其他诸如 Hash Cash 等等的算法也使用了 PoW 协议,但却仅用于限制垃圾邮件和拒绝服务攻击问题。不仅如此,关于传统共识协议我也略去了很多!我认为上述内容足够为你留下共识领域传统和中本聪模式之间差异的一瞥。下篇文章,我们不见不散!

Zaki Manian 致以衷心的感谢,他在本文成文过程中解答了我关于分布式共识的各种问题。

(全文完)


原文链接: https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95
作者: Preethi Kasireddy
翻译&校对: 安仔 & 阿剑

本文由作者授权 EthFans 翻译及再出版。


你可能还会喜欢:

干货 | 比特币的学术谱系,Part-1
干货 | 温和的加密货币大师:尼克·萨博,Part-1
干货 | 区块链经济学:制度加密经济学入门指南

 
0 人喜欢