关于共识算法和分布式账本数据结构的简要工程简介

共识算法定义了一系列动作,通过这些动作,独立代理在分布式系统的各个部分上(至少在大多数代理中)获得了相同的观点。例如,这可以由某个客户端(不参与协商共识)确定,该客户端可以从任何(或至少大多数)协商共识参与者那里获得关于系统协商共识状态查询的相同结果。

通常,共识算法用于解决以下问题:

· 领袖选举(在所有共识参与者中选择代理人,有权更新系统的全球状态)

· 原子交换(不能根据事件的内部属性确定其顺序事件的确切顺序)

· 状态复制(维护所有或大多数代理共享的全局状态)

这是共识算法的三个主要用例是高度相关的。例如,状态复制可以通过状态更改的适当顺序(即原子广播)来解决,而适当的领导人选举过程本身可能允许有序的原子广播(但是,在没有领导人选举过程的情况下,有达成相同结果的共识)。

从历史上看,共识算法起源于多处理器计算的研究;它们解决的是处理器可能出现故障(即变得无响应)时的全局状态问题。在这些情况下通信是同步的,即受一些已知的时间上限。

后来,随着电信和计算机网络的发展,出现了另外两个问题:未知的通信延迟和对手的存在。前者导致了部分新的研究同步和异步共识算法和创建算法可以容忍任意代理行为(拜占庭行为)——即所谓的拜占庭容错算法(或BFT共识)。

随着互联网的广泛应用,对手的问题变得更加严重。如果在多处理器环境或电信基础设施中可以识别每个代理,那么在Internet的许多情况下就不能这样做。因此,出现了一种新的公共(或无许可)共识,共识算法必须成为一种协议,其中嵌入了识别和排除拜占庭式代理的规则和程序——就像一些附带机制降低了此类代理进一步参与协议的经济能力一样。这种制度以POW 和POS的名义引起了公众的注意。我们将以经济激励(BFT- ei)命名这些协议。在许多情况下,异步性和无许可性要求牺牲其他共识品质,比如决定论或适用于领导人选举场景的能力。

在此基础上,可以根据不同的准则对共识算法进行分类。

1. 共识的主题:原子广播、领袖选举、国家复制(或者,另一种选择,基于领袖和无领袖算法)

2. 容错形式:无容错、非任意容错和拜占庭容错(BFT)

3. 可以达成共识的假设有:同步、参与方同步、异步

4. 公开和非公开参与的协议:许可vs不许可,或公开vs私人。

5. 内部经济激励: BFT-EI

6. 协商共识的确定性品质, 即实现终结性的能力: 具有终结性和非确定性共识的共识算法。

这些类可以组合在一些自然的组中,比如开放的参与会导致不确定性的共识属性(因为我们不能在给定的时间点枚举所有共识的参与者),也就是缺乏终结性,它将是无领导的。这种共识的一个典型例子是比特币交易。

我们定义了以下典型的共识属性组合:

· PoW:无权限同步非确定性无领导BFT-EI。

· POS: 基于BFT-EI的不允许部分同步确定性领导。

· BFT(狭义的): 允许的、确定性的BFT。可以有不同的同步性假设,可以是领导者,也可以是非领导者。

· DAG:无权限异步、非确定性领导、无BFT容忍度。

· 其他混合的类型。

许多现实世界中的共识算法应用, 比如在现代实验区块链中发现的应用, 往往会利用一组不同的共识机制,用于领导人选举的机制 (通常是基于 bft 协议的机制, 但有时甚至是 pow), 而其他的机制对于原子广播 (pos) 和另一个实现确定性的是状态复制-通常是 bft 类型的 "小工具" 的形式。

共识算法本身不需要特定的数据结构;它们都是关于代理行为和网络通信的。然而,在比特币(这是第一个基于公共共识的应用)发明之后,似乎需要全球状态的系统并利用数据结构上的一些最佳实践来验证,比如具有加密增强功能的日志类账——所谓的区块链或者更通用的有向无环图(DAG),通常由我们上面分类的#4组共识使用。


来源:区块网

󰄯 分享