精华内容
下载资源
问答
  • Algorand 提出的共识协议是项目的一大亮点,本文主要分析 Algorand 共识协议的工作原理,并分析其优缺点。1.2 Algorand 设计的初衷Algorand 想解决的核心问题是:去中心化网络中低延时(Latency)和高置信度(Con...

    概述

    1.1 引言

    Algorand 称其突破了”公链不可能三角“,项目创始人是图灵奖得主、MIT CSAIL 实验室的 Silvio Micali 教授。Algorand 提出的共识协议是项目的一大亮点,本文主要分析 Algorand 共识协议的工作原理,并分析其优缺点。

    1.2 Algorand 设计的初衷

    Algorand 想解决的核心问题是:去中心化网络中低延时(Latency)和高置信度(Confidence)之间的矛盾[1]。

    其中,延时指从发起交易到确认交易所需要的时间;置信度指的是发出的交易不会再被更改的概率。

    在比特币网络中,为了提高交易的置信度,用户必须等待 6 个区块确认(约 1 个小时)的确认延时;而如果选择低延时,比如少于 6 个确认,甚至是 0 确认,则必然导致低置信度,增加“双花”攻击的可能。双花问题是绝大多数加密数字货币的核心问题。比特币中采用 PoW 共识来解决,但链本身仍然有分叉的可能,并且需要较长的共识达成过程和确认时间。

    同时 Algorand 还想解决比特币中 PoW 挖矿耗费巨大资源、交易确认时间长、易分叉、网络呈中心化趋势,可扩展性差等问题。

    1.3 Algorand 是什么?

    根据官方描述,Algorand 是一个采用 permissionless 的纯 PoS 共识的公链项目,结合改进的拜占庭共识协议,可实现快速的交易确认,几乎不会分叉,并且用户数可无限扩展,不会影响交易确认速度。同时兼顾“可扩展、安全性、去中心化”这个“公链不可能三角”[2]。

    (注:”公链不可能三角“的正确性和具体定义存在较多争议[7]。在 Algorand 中:可扩展性指在较大用户规模下仍可实现较高的吞吐量[8],安全性指的是可以对抗恶意攻击[9],去中心化指的是网络完全开放,成为节点没有任何门槛[10]。)

    · 可扩展性:Algorand 通过可验证随机函数(VRF)随机选择区块的生产者和验证者,一旦得知被选中,生产者或验证者只需广播一个简短的消息即可证明自己的身份。每产生一个新区块在网络中需要交换的消息不会随着用户数的增大而改变,,因此即使用户规模增大,系统仍可保持较高的 TPS(每秒处理的交易数)。Algorand 的 TPS 是比特币的 125 倍。

    · 安全性:由于采用了上述的 VRF 随机选取生产者和验证者,并且选取的过程完全由节点独立完成,因此Algorand 网络中的攻击者无法预先得知下一个区块生产者和验证者,从而也就无法完成攻击。具体来说,生产者和验证者的身份只有在他们确定自己被选中并广播对应的证明信息时才会被披露,这时攻击者即使立刻采取各种攻击手段,也无法阻止关于新区块的正确消息在网络中的传播。

    · 去中心化:Algorand 中每一轮的区块生产者和验证者都是随机选取的,并且加入网络没有任何门槛,因此是完全去中心化的。

    下面详细介绍 Algorand 的共识协议。

    lgorand 协议详述

    几乎所有公链项目的区块产生和共识的过程都可以抽象为两个步骤:

    1. 选择出区块生产者,生成新区块

    2. 其他节点对新区块达成共识

    以上步骤周而复始,最终形成一条“不可篡改”的区块链。

    整个共识过程虽然简单,但在实际实现中,必须解决几个关键问题:

    · 如何选择区块生产者,且保证公平和不可被预测?

    · 如何对新区块达成共识?

    · 如何避免分叉?

    · 如何提高安全性?

    · 如何扩展到更大规模的用户?

    比特币采用哈希函数的随机性来确保公平,采用工作量证明(PoW)达成共识,同时能够在一定程度上抵抗算力攻击。然而比特币仍然面临上述消耗计算资源、确认时间长、易分叉以及扩展性差等问题。以 Qtum 为代表的采用纯权益证明(PoS)共识机制的项目,同样采用了哈希函数,并且不需要消耗大量的计算资源,然而仍然面临易分叉、安全性及扩展性的问题。

    Algorand 提出了一种新的共识机制解决上述 5 个问题。

    2.1 基础知识

    正式介绍 Algorand 共识协议之前,本文假设读者基本了解以下名词的含义:

    · 哈希函数(Hash)

    · 公钥/私钥

    · 数字签名

    · 交易

    · 区块

    · 账本

    · 共识

    · 拜占庭协议(Byzantine Agreement,BA)

    · 诚实节点

    · 攻击节点

    · P2P 通信

    如果读者对上述概念不理解,请先搜索相关关键词进一步了解,再阅读以下内容。

    2.2 Algorand 的基本过程

    Algorand 协议可以按照时间顺序划分为不同轮次,每一轮都会达成共识并生成新区块。其典型的通用过程如下:

    1. 每一轮共识开始时,随机选出潜在的 leaders,各自生成新区块,对新区块进行签名和广播

    2. 随机选出验证组,对 leaders 广播的新区块进行验证,达成共识后广播确认新区块,进入下一轮

    接下来具体讨论 Algorand 共识协议细节,本节主要参考[4]。

    2.3 保证 Algorand 的随机性:可验证随机函数

    Algorand 利用 VRF 来选择区块生产者和验证者,保证所有共识参与者都是随机地、公平地被选出的。可验证随机函数(VRF,Verifiable Random FuncTIon)是由 Micali 教授等提出的一种伪随机函数,和普通的随机函数一样,对于不同输入,其输出也具有随机性(严格来说是“伪随机”)。其独特之处在于调用者可以提供一个证明,表明这个随机输出确实由该调用者产生。

    VRF 可以有多种实现方式,Micali 等人在其原始论文中提供了一种较复杂的实现方式[3]。Algorand 利用哈希函数和数字签名的特性,提供了一种较为简单的 VRF 实现。具体实现方式是调用者 i 将输入 m 通过数字签名和哈希函数映射为固定长度的输出 H[SIGi(m)],即 m -》 H[SIGi(m)]。

    对于任何输入 m,不同的调用者 i 生成的数字签名 SIGi(m) 都是唯一的;而对于不同输入,哈希函数 H 的输出具有随机性,因此上述映射符合 VRF 的”随机性“要求。同时,由于 i 的数字签名 SIGi(m) 可通过其公钥对其身份进行验证,因此其也符合 VRF ”可验证“ 的特性,SIGi(m) 就是 VRF 中提到的”证明“。

    这个函数特别适合在所有节点中随机选择出共识的参与者,下面具体讨论。

    2.3.1 随机选出每一轮的区块生产者(Leader)

    每一轮共识开始时,每个节点都可以通过以下 VRF 独立地验证自己是否是潜在的 leader:

    .H[SIG(r, 1, Q(r-1))] 《= 1 / SIZE(PK(r-k))

    其中,H 是哈希运算;SIG 是签名运算;r 是目前的轮次;Q(r-1) 为与 r-1 轮的种子(将在后续 2.6 节中解释);SIZE(PK(r-k)) 是在 r-k 轮所有符合要求的公钥的数量(为什么是 r-k ?k 为回溯系数,也将在 2.6 节中阐述);公式开始的 。 表示将哈希结果转化为小数位,从而保证结果为[0,1)的某个值。

    节点通过自己的私钥计算上面签名的哈希值是否符合要求,从而知道自己是否属于候选的 leader,在此过程中无需和其他节点交换信息。由于哈希函数输出的随机性,可以认为符合要求的候选节点都是随机选出的。候选节点随后可以生成新区块,并向全网提供签名证实自己的身份。如果有多个候选 leader,最终上述哈希值最小的 leader 将在后续的共识中成为本轮最终的 leader。Leader 产生的区块 Br 包含了本轮的所有交易和上述的证明信息,由验证组成员进行共识验证。

    2.3.2 随机选出每一轮每一阶段的验证组

    验证组成员的选择与上述过程类似,在每一轮和每一阶段(step),所有节点都可以独立验证自己是否属于验证组成员:

    .H[SIG(r, s, Q(r-1))] 《= n / SIZE(PK(r-k))

    其中 s 为本轮所处的不同阶段,Algorand 在每一轮的各个阶段都有不同的验证组,从而进一步保证安全性;n 为预期的验证组成员数量,可以人为设定;其他参数含义不再重复。

    与候选 leader 一样,每一阶段的验证组成员均随机选出,验证节点在证实自己身份后,可以开始参与共识验证过程,揭露自己的签名即可证明其身份。

    2.3.3 引入权益证明(Proof-of-Stake,PoS)机制

    上述的随机选择过程没有考虑 Token 持有者的权重,恶意节点可能通过大量生成有效私钥从而有极大概率成为区块的生产者和验证者。

    Algorand 在其公布的实现建议中引入了名为 Honest Majority of Money (HMM)的条件假设,其基本思想来源于 PoS 共识机制,即在上述随机选择过程中引入代币持有量(Stake)作为权重,持有量多的节点被选中的概率较高,而代币持有者往往更倾向于保护网络的安全性。具体可以表示为如下公式:

    .H[SIG(r, 1, Q(r-1))] 《= (a(i,r) / M) * (1 / SIZE(PK(r-k)))

    其中,a(i,r) / M 为节点所持有的币的数量占代币总数 M 的权重。其余过程与前面描述一直。

    2.4 Algorand 如何对新区块达成共识:改进的拜占庭协议 BA*

    Algorand 中验证者对新区块达成共识的过程,实际上是一种改进的拜占庭协议(ByzanTIne Agreement),Algorand 称其为 BA*。

    BA* 由一种改进的二元拜占庭协议(Binary ByzanTIne Agreement,BBA)和分级共识协议(Graded Consensus,Protocol GC)组合而成[5]。

    2.4.1 改进的二元拜占庭协议 BBA*

    Algorand 引入的 BBA* 是一个改进的二元拜占庭协议(所谓二元,即只能达成 0 或 1 两种共识)。BBA* 可以在诚实节点超过 ⅔ 的情况下,快速达成共识。其具体过程是一个 3 步循环,循环中每一步都有 ⅓ 的概率达成共识。

    节点之间需要进行 P2P 通信,假设被选中的验证节点中有 t 个恶意节点,验证组总的节点数为 n 》= 3t + 1,即恶意节点不超过 ⅓ 。协议过程如下:

    上述协议中各符号的具体含义可参考[4]。所有验证节点i都有一个初始值 bi(bi = 0 或 1),协议开始时,每个验证节点都会向其他验证节点发送各自的初始值,

    协议第一步(Step 1)是归 0 过程:

    如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔ ,输出共识结果为 0,共识结束,不再执行后面所有步骤

    如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔,则该验证节点把自己的 bi 设为 1

    如果收到的 0 或 1 都没超过 ⅔, 则验证节点把自己的 bi 设为 0

    第一步结束节点再次向其他节点发送各自的 bi

    第二步(Step 2)为归 1 过程:

    如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔ ,输出共识结果为 1,共识结束,不再执行后面所有步骤

    如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔,则该验证节点把自己的 bi 设为 0

    如果收到的 0 或 1 都没超过 ⅔, 则验证节点把自己的 bi 设为 1

    第二步结束节点再次向其他节点发送各自的 bi

    第三步(Step 3)为重新设定初始值的过程:

    如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔,设定 bi = 0

    如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔,设定 bi = 1

    如果收到的 0 或 1 都没超过 ⅔,则每个验证节点会对某个和本轮本阶段相关的信息进行签名,并对签名求哈希。bi 被设置为这些哈希值中最小哈希的最低有效位(仍然是 0 或 1)

    之后返回第一步,直到达成共识

    在 Algorand 中, BBA* 的结果是对是否接受某个区块达成共识,共识结果只有接受(0)或拒绝(1)两种情况。

    2.4.2 分级共识协议 GC

    上述 BBA* 只适用于二元情况,当需要对任意值达成共识,需要引入分级共识协议,将任意值问题转化为二元问题:

    Algorand 采用的 GC 分为两步(上图来自 Algorand 白皮书[4],为了和文中其他部分对应,将两个步骤命名为 Step 2 和 3),协议开始时,每个验证节点i各自都有一个初始值 vi(在 Algorand 中即候选的新区块的哈希):

    第一步 (Step 2),所有验证节点将各自的 vi 发给其他所有验证节点;

    第二步(Step 3),对于某个x值,当且仅当节点收到其他验证节点发来该 x 值的总次数(多次收到同一节点发送的x值,只算一次)超过总验证节点数的 ⅔ 时,这个节点会对其它节点发送值 x:

    经过 GC,每个节点都会输出一个值对 (vi, gi),输出规则:

    · 当收到 x 的总次数超过总验证节点数的 ⅔ 时,设定 vi = x, gi = 2;

    · 当收到 x 的总次数超过总验证节点数的 ⅓ 时,设定 vi = x, gi = 1;

    · 否则,设定 vi = 空, gi = 0;

    简单来说,分级共识的作用是从多个可能的候选新区块中选择被大多数认可的一个作为最终候选的区块,再通过上面的 BBA* 最终达成共识。

    2.4.3 BA* = GC + BBA*

    改进的拜占庭协议 BA* 结合了上述 GC 和 BBA*,先通过 GC 把任意值问题(从多个区块中选择一个候选)转化为二元问题(接收或拒绝新区块?),再利用 BBA* 达成快速二元拜占庭共识,从而可以快速对任意值达成共识,其共识过程如下[4]:

    BA* 的第一步,和第二步,所有验证节点 i 执行 2.4.2 中分级共识 GC,各自得到一个关于新区块的数值对 (vi, gi),其中 vi 为验证节点 i 认为的候选区块哈希(有可能为空),gi = 0 或 1 或 2 。

    第三步,所有验证节点根据各自的 (vi, gi) 设定 BBA* 的初始值,如果 gi = 2,则设定初始值为 0,如果 gi = 0 或 1, 则设定初始值为 1 。之后进行 2.4.1 中的 BBA* 共识过程:

    · 若共识结果为 0,则最终输出结果为 vi(非空新区块)

    · 若共识结果为 1, 则最终输出结果为空(即新区块为空)

    无论哪种情况,BA* 都可以在验证节点中达成共识,从而确定新区块及其包含的交易(有可能为空区块)。

    2.5 Algorand 区块链分叉的可能性

    Algorand 实际采用的是经典拜占庭共识的升级版 BA*,它和以比特币为代表的中本聪共识的最大区别在于分叉的可能性。后者由于完全去中心化,节点之间无法完全通信,因此可能仅在部分节点间达成共识,容易发生分叉。

    Algorand 可以通过设定最大可接受的错误概率 F 调整分叉的概率。在 Algorand 提供的两种实现中,其分叉概率分别为 10^-12 和 10^-18,在现实中分叉仅存在理论上的可能。为给读者一个直观概念,假设 Algorand 每秒生成一个区块,10^-18 的概率意味着从宇宙大爆炸至今的时间内,只有可能发生一次分叉,可见其概率极低。

    即使真的发生分叉,Algorand 仍可以从分叉中恢复:

    · Algorand 遵守中本聪共识中的最长链法则

    · 如果有多条最长链,则选择包含非空区块的最长链

    · 如果仍相同,则可以具体根据区块哈希值进行排序选择

    2.6 Algorand 如何保证安全性

    上述的共识算法在理想情况下可以实现去中心化环境下较快速的拜占庭共识,数字签名和 VRF 本身的安全性也对系统安全提供了基本的保障。除此之外,Algorand 还引入了以下机制,进一步提升安全性:

    种子 Q(r)

    Algorand 中的随机性主要靠 VRF 保证,每轮随机的选出 leader 及验证组。一个比较直接的想法是把上一区块 B(r-1) 作为随机函数的输入。但这种方法将给恶意节点带来一定的优势:因为区块和其包含的交易高度相关,恶意节点可以通过调整区块中包含的交易集,获得多个输出,并选择对其最有利的交易集产生新区块,从而提高自己在下一轮中成为 leader 或验证组的概率。

    为解决这一问题,Algorand 引入了一个随机的、不断更新的种子参数 Q(r),Q(r) 与交易集本身相互独立,因此恶意节点无法通过调整交易集而获利。

    当区块非空时,Q(r) = H(SIG(Q(r-1),r) (其中,SIG 为 本轮 leader 的签名)

    当区块为空时,Q(r) = H(Q(r-1),r)

    可以看出,Q(r) 在每一轮都发生变化,且与交易本身无关。可以证明,当 Q(r-1) 是随机的,则 Q(r) 也是随机的。因此恶意节点无法通过改变交易集影响下一个种子的生成。其中,Q(1)的定义没有在相关文献中找到。

    回溯系数 k

    种子参数降低了恶意节点预测 leader 的可能性,但拥有多个潜在 leader 的恶意节点仍可以有比普通节点更高的概率成为下一个区块的 leader,但这个概率会随着区块的变多而逐渐变小。因此,Algorand 引入了一个回溯系数 k,第 r 轮的候选组只从 r-k 轮已存在的候选组中选取,恶意节点在 r-k 轮能够影响第 r 轮候选组的概率极低。

    一次性公钥

    上一节中提到,Algorand 从协议层面的分叉仅在理论上可能发生。在实际中,如果恶意节点可以挟持其他节点,仍可以在验证组被公开的瞬间,强制这些节点重新签名新的区块,从而产生短暂的分叉。Algorand 引入了一种一次性公钥的机制,以杜绝这种可能性。

    具体原理是所有节点在加入 Algorand 网络时(即发生第一笔交易时),都生成足够多的一次性公钥,并公布。这些公钥将用作后续所有轮次的签名验证,并且每个公钥只使用一次,一旦被使用后就销毁。一次性公钥的生成过程需要一定的时间,在 Algorand 的典型实现中,每个新节点需要约 1 小时来生成未来 10^6 轮的所有公钥(约 180 MB 数据)。虽然这增加了节点加入时的门槛,但可以从根本上杜绝上述分叉攻击:因为一旦签名完成,公钥即被销毁,即使被恶意节点劫持,也无法再次签名产生分叉。

    2.7 Algorand 的可扩展性

    对于目前大多数去中心化区块链,如比特币,以太坊以及 Qtum 等,可扩展性的主要瓶颈在于所有链上计算都要进行全网验证,而达成全网共识往往需要一定的时间。Algorand 采用 PoS+VRF 机制进行随机选择区块生产者和验证者,无论网络中有多少节点,每一轮都只需要在少数节点上进行验证,大大提高了共识速度,提高可扩展性。同时,Algorand 还采用了改进的拜占庭共识 BA*,该协议可以减少共识节点之间的通信量,从而进一步提高共识速度。

    此前 Algorand 发布了其性能测试数据,结果表明,在 1000 台 EC2 服务器(AWS 虚拟云服务器)、500,000 用户场景下,Algorand 网络确认时间稳定为 1 分钟,吞吐量约为比特币网络的 125 倍。(比特币约为 7 TPS)且吞吐量不会随着节点数的变多而明显下降[1]。

    Algorand 的优缺点

    通过上述分析,Algorand 基本解决了第 2 节开头提出的一系列问题:

    · 通过 PoS 和可验证随机函数(VRF)实现区块生产者和验证者的选择

    · 通过改进的拜占庭共识 BA* 对新产生的区块达成共识

    · 通过一定的参数设计,从数学上将分叉的概率降至极低值

    · 引入种子参数,回溯系数以及一次性公钥等机制进一步增强安全性

    · 每一轮都只进行局部验证,并通过减少节点间通信量进一步提升系统的吞吐量,提高可扩展性

    Algorand 在可扩展性,安全性和去中心化程度三个方面达到了一个很好的均衡,但这不意味着其真的打破了所谓的”不可能三角“。

    可扩展性方面:本质上还是通过较少的验证节点对所有交易进行验证,当网络中全节点变多时,只能保证性能不下降太多,不是真正意义上的可扩展。另外,每一轮验证节点之间的通信依赖于所处的网络状态,网络不稳定将导致共识时间变长,影响 TPS。官方称 Algorand 在 Permissinoed 环境下将有更好的性能[4],原因可能在于 Permissionless 环境下节点所处环境有太多不确定性,会在一定程度上影响可扩展性。

    安全性方面:Algorand 本质上采用的还是拜占庭共识,恶意节点不能超过 ⅓,而比特币可以在恶意节点数小于 ½ 的情况下保证安全。

    去中心化方面:Algorand 采用 PoS 共识和 VRF 决定区块生产者和验证者,拥有较多代币的节点在 PoS 过程中被选中的概率较高,且 Staking 奖励向大户集中,有一定的中心化趋势;而 VRF 选举机制的引入让链上计算只由部分节点进行验证,损失了去中心化系统全网验证的特性。

    此外,Algorand 的主网刚刚发布[6],此前所有结果均是理想环境下的数据,且部分代码未开源,虚拟机相关设计也暂未提及,其实现的复杂度、稳定性和实际性能还有待时间的检验。

    总结

    Algorand 通过创新共识协议设计,同时实现了较高的可扩展性,较好的安全性和一定程度的去中心化,并且所有结论都有较为严格的数学证明,是一种较为创新和严谨的共识机制,目前较适用于有一定准入门槛的去中心化、高吞吐量加密数字货币项目。

    展开全文
  • 离散多代理系统的延迟共识余量:P型和PD型共识协议
  • Casper共识协议

    千次阅读 2018-06-05 08:06:58
    Security-deposit based security and authenticationCasper是一种基于保证金的经济激励共识协议(security-deposit based economic consensus protocol)。协议中的节点,作为“锁定保证金的验证人(bonded validators...

    基于保证金的安全和共识鉴别

    Security-deposit based security and authentication

    Casper是一种基于保证金的经济激励共识协议(security-deposit based economic consensus protocol)。协议中的节点,作为“锁定保证金的验证人(bonded validators)”,必须先缴纳保证金(这一步叫做锁定保证金,"bonding")才可以参与出块和共识形成。Casper共识协议通过对这些保证金的直接控制来约束验证人的行为。具体来说就是,如果一个验证人作出了任何Casper认为“无效”的事情,他的保证金将被罚没,出块和参与共识的权利也会被取消。保证金的引入解决了"nothing at stake",也就是经典POS协议中做坏事的代价很低的问题。现在有了代价,而且被客观证明做错事的验证人将会付出这个代价。


    我们容易发现,只有在验证人当前已缴纳保证金的情况下他的签名才有意义(economically meaningful)。这代表客户端只能依赖他们知道的锁定保证金的验证人的签名。因此当客户端接收和鉴別共识数据时,共识认可的链必须起源于出自当前锁定保证金的验证人的块。在POW协议中共识认可的链则是起源于创世块 - 只要你知道创世块的数据你就可以鉴别出共识认可的链。这里,只要你知道当前锁定保证金的验证人,你就可以鉴别出共识认可的链。不知道当前锁定保证金的验证人列表的客户端必须先通过另外的信道获取这个列表。这个限制通过要求所有人用当前信息鉴别共识解决了“远程攻击(long range attack)”问题。


    验证人列表随着验证人保证金不断的锁定,罚没,解锁而变动。如果客户端离线过长时间,它的验证人列表就会由于过时而不能用来鉴别共识。如果客户端经常在线,则能够与最新的验证人列表保持同步,但问题是在第一次同步之前,客户端还是需要从其他信道获取最新锁定保证金的验证人列表。


    这个“需要从其他信道鉴别共识至少一次”的性质。在我们的上下文中,如果信息可以在协议之内被验证,则可称之为“客观的”;如果信息必须依赖协议外的手段才可验证,则称为“主观的”。在弱主观性共识协议中,分叉选择规则是有状态的,因此客户端必须初始化(有些时候是更新)这个状态才能鉴别共识。在这里,这个状态被用来辨认当前锁定保证金的验证人(更精确的说法可能是当前验证人列表的密码学哈希)。



    下注共识

    Gambling on Consensus

    Casper要求验证人将保证金中的大部分对共识结果进行下注。而共识结果又通过验证人的下注情况形成:验证人必须猜测其他人会赌哪个块胜出,同时也下注这个块。如果赌对了,他们就可以拿回保证金外加交易费用,也许还会有一些新发的货币;如果下注没有迅速达成一致,他们只能拿回部分保证金。因此数个回合之后验证人的下注分布就会收敛。


    此外如果验证人过于显著的改变下注,例如先是赌某个块有很高概率胜出,然后又改赌另外一个块有高概率胜出,他将被严惩。这条规则确保了验证人只有在非常确信其他人也认为某个块有高概率胜出时才以高概率下注。我们通过这个机制来确保不会出现下注先收敛于一个结果然后又收敛到另外一个结果的情况,只要验证人足够多。


    POW共识同样可以理解为是一个下注机制:矿工选择一个块基于它进行挖矿,也就是赌这个块会成为主链的一部分;如果赌对了,他可以收到奖励,而如果赌错了,他会损失电费。只要所有的矿工都将他们的算力下注到同一条链上,使这条链拥有最多的工作量(即时算力下注的预测,也是算力下注的结果),共识就是安全的。POW中算力赌注的经济价值随着确认数的增加线性增长,而在Casper中验证人可以通过协调使下注比例指数增长,从而使共识快速达到最大安全。


    高度级共识

    High level consensus

    验证人对每一个高度上的每一个候选块独立下注,给每个块指定一个胜出概率并公布。通过反复下注,对于每个高度验证人会选出唯一一个胜出块,这个过程也决定了交易(transaction)执行的顺序。如果一个验证人在某个高度公布的概率分布总和大于100%,或者公布了小于0%的概率,或者对一个无效块指定了大于0%的概率,Casper将罚没他的保证金。


    交易最终确认

    Transaction Finality

    当锁定保证金的验证人中的绝大多数(满足协议定义阈值的一群验证人:保证金比例达到67%到90%之间某个百分比)以非常高的概率(例如,> 99.9%)下注某个块时,任何不包含这个块的分叉都不可能胜出,此时我们说这个块已最终确认(final)。此外,如果客户端发现所有小于高度H的块都已最终确认,那么此客户端永远不能接受一个在高度H - 1的状态和顺序执行这些完全块得到的状态不一样的分叉。这种情况下我们说这个状态(H - 1高度的状态)已最终确认。


    因此这里有相关的两种交易的最终确认:交易在特定高度被执行的最终确认(也就是对应块的最终确认,早于所有此高度之后的交易执行),以及交易执行后状态的最终确认(需要对应块和所有低于此高度的块被最终确认)。


    防审查

    Censorship Resistance

    共识协议最大的威胁之一是矿工形成以损害非成员利益为代价最大化成员获利的联盟。如果Casper中验证人的收入主要由手续费构成,一个多数联盟就能够通过过滤其它节点的出块来获取更大利益。不仅如此,攻击者还可以贿赂节点来剔除特定地址发出的交易,只要多数节点是理性的,他们就能够联合起来过滤掉没有剔除指定交易的块。


    为了抵御多数派联盟攻击,Casper将共识过程看作一个合作博弈,确保每一个节点只有在由所有节点组成的联盟中才能获得最大利益(至少在当利益主要由协议内奖励构成的情况下如此)。如果p%的验证人参与了共识博弈,那么他们将得到f(p) ≤ p%的收益;如果有100%的验证人参与则能获得更多回报。


    更具体的说,Casper会惩罚那些不按照协议规定顺序出块的验证人。协议会注意到出块顺序的偏离,并且扣下对应验证人的保证金和手续费。此外,通过下注赢得的收益与参与共识博弈的验证人数量成线性(或者超线性)关系。



    吞吐量(每秒可处理的交易数)会增加吗?


    答案很可能是确定的,而原因与其说是Casper的区块链架构不如说是Casper上的经济学。不过Casper的区块链设计确实支持了比POW共识更快的出块间隔。


    验证人的收入很可能只有交易费用,因此他们有增加Gas上限的直接动机,只要他们的服务器负荷的了。但是如果因此造成其它处理能力比较弱的验证人跟不上节奏,他们的收入会变少。所以验证人只会接受大家都能承受的Gas上限上涨。矿工(Miners)投资硬件的方式是购买更多的矿机(算力),而验证人的投资硬件的方式则会是升级服务器以获取更高的吞吐量。矿工也有购买能获得更高吞吐量的硬件的动力,但是这比购买算力的动力弱得多。


    相对于POW, 在基于保证金的POS上实现轻客户端更加方便。具体来说,轻客户端无需下载区块头来获得共识鉴别的安全性,或是交易执行有效性的经济性保证。大部分的共识开销只会影响验证人,不会影响轻客户端。轻客户端也可以在保留鉴别共识能力的前提下实现低延迟。


    网络分区的恢复


    由于未最终确认的区块中的交易可以被撤销,Casper具有在网络分区后恢复的能力。在分区重新连上后,Casper会执行具有更高验证人参与度的分区上获得下注的区块中的交易。这样在重连之后验证人重新下注前,分区双方就对共识状态达成了一致。验证人的下注会收敛并以高概率最终确认具有更高验证人参与度的分区上的某个块。Casper很可能会在产生胜出块之后再处理淘汰块中的交易,不过我们还没有决定到底是由验证人把这些交易纳入新块,还是由Casper按照原来的顺序处理。


    大规模崩溃的恢复


    即使在全网只剩一个节点没有崩溃的极端情况下Casper也有能力恢复。锁定保证金的验证人总是独立的对候选块下注,虽然下注和多数验证人一致的话回报会更高。在任何时候,验证人从出块获得的回报总是比不出块要高。如果锁定保证金的验证人过长时间没有上线,他的保证金会被解锁,新的验证人会接替他的位置。因此Casper的安全程度可以恢复到和大规模崩溃之前一样。


    抛开经济学术语的解释


    Casper是一个基于区块链的最终一致性共识协议。想对于一致性(C)它更倾向于可用性(A)(见CAP理论)。它总是可用,并且尽可能迅速的达成一致。它健壮到足以容忍不可预计的消息传输延迟,因为节点可以在收到延迟的消息之后通过重新组织交易达成共识。由大于50%的正常节点建立的分叉总是比剩下的有潜在问题的节点建立的分叉权重更高,因此它对不超过50%的网络失效有最终容错性(eventual fault tolernace)。需要注意的是客户端无法知道一个有51%的验证人参与的分支会不会被放弃,因为此时不知道这些验证人中是否有恶意节点。一个块只有在绝大多数(supermajority)验证人(或者说保证金)参与共识的情形下才能被认为是最终确认(final)的。


    验证人有什么责任?


    作为一个锁定保证金的验证人,你需要对块进行签名以及在共识过程中下注。如果你缴纳了一大笔保证金,你也许应该部署一个由多台服务器组成的多重签名环境来做验证工作,以减少服务器异常或是被黑导致的风险。这种方案需要反复实验和技术专家的帮助。


    为了最大化收益,验证人需要尽可能的保持在线和服务稳定。DDoS防护服务是非常必要的。你的收益率还取决于其他验证人的处理性能和可用性,也就是说这里存在一个你无法直接化解的风险。如果其他节点表现不行你也会遭受损失!但是此时如果你决定完全不参与共识你会损失更多。然而额外的风险通常意味着更高的回报,尤其是当风险已经被认识到而永远不会发生的时候。


    应用和普通用户有什么好处?


    应用和它们的用户可以从POW转向Casper的变化中获得许多好处。低延迟确认可以极大的改善用户体验。一般情况下交易很快就能最终确认。如果有网络分区发生,交易依然会被执行,而交易有被撤销的可能性这一情况会被清楚的报告给应用和其用户。应用的开发者依然需要处理分叉的情况,和使用POW协议时一样,但这里共识协议会给出一个对交易撤销可能性的清楚估量。


    展开全文
  • 极简区块链共识协议

    2021-01-11 11:31:08
    如何设计一种简单而高效的共识协议一直是学术界和工业界追求的目标。比特币的设计虽然简单,但性能低下且共识结果具有一定随机性,因此不适用于企业之间业务量巨大的场景。近年来大家非常关注的联盟链中应用的共识...

    导读

    区块链作为典型的分布式系统,其共识核心的设计和实现一直困扰着开发者。如何设计一种简单而高效的共识协议一直是学术界和工业界追求的目标。比特币的设计虽然简单,但性能低下且共识结果具有一定随机性,因此不适用于企业之间业务量巨大的场景。近年来大家非常关注的联盟链中应用的共识算法(PBFT、Tendermint)虽然性能接近传统的共识算法(Paxos、Raft),但协议设计相对比较复杂,实现难度较高。本文着眼于一种针对联盟链设计的极简区块链协议 Streamlet。具有一定区块链知识背景的人只需要不到10分钟就能理解整个共识流程,因此 Streamlet 不仅适用于工程化实现,而且具有非常现实的教学意义。

    背景

    Streamlet[1] 由 Cornell 大学的 Elaine Shi 教授团队在2020年2月的斯坦福区块链大会提出(也许更早),其前身是 Pala[2]。Streamlet 可以算作是近五年来区块链领域与传统拜占庭共识(Byzantine fault-tolerant,BFT)领域的集大成之作,在包括经典 PBFT[3],Cosmos 在用的 Tendermint[4],以太坊 2.0 将要用的Casper[5],以及 Facebook 推出的数字货币 Libra[6] 所基于的 HotStuff[7] 等协议中都能感受到对 Streamlet 的影响。尽管如同一个大杂烩,但 Streamlet 的目标是一种堪比比特币的极简区块链协议。

    Streamlet 遵循传统 BFT 协议的容错规则,即在节点数目为 n 的网络中,可以容忍最多 f 个拜占庭节点,需要满足 n > 3f。Streamlet 依赖于半同步(partially synchronous)网络假设,即网络在大部分情况都是好的,消息可以在一个能够预测的延迟内传播,但在某些情况下网络可能会经历一段波动期(Global Stabilization Time,GST),并最终会恢复。在GST期间,网络延迟无法预测。Streamlet 和大多数协议一样,保证协议在异步网络下的安全性(safety),当网络回归同步时可以进一步保证活性(liveness)。

    Streamlet

    在 Streamlet 中,协议的运行被划分为一个个同步的 epoch(这里的epoch是指生成一个区块的时间周期,例如每个 epoch 持续 1 秒),每个 epoch 都由哈希算法随机分配一个 leader进行“随机选主”。每个 leader 在属于自己的 epoch 中发布(propose)一个区块给其它 replica 节点投票(vote)。投票可以被看作是投票者用自己的私钥对区块哈希值的签名,并将其广播给其它所有节点。如果一个区块收到了来自超过 2/3 不同节点的投票,则被认为是“已证区块(notarized block)”。由已证区块组成的链被称为“已证链(notarized chain)”。接下来介绍整个 propose-vote 的流程中的一些细节。

    • 发布规则(Proposing Rule)。每个 leader 都在本地最长的已证链的基础上发布新的区块,即新区块的 prevHash 指向本地最长的已证链末尾的区块。

    • 投票规则(Voting Rule)。每个 replica 只对来自当前 leader 发布的第一个区块投票,并且该区块必须扩展自本地最长已证链,即该区块的 prevHash 必须指向投票者本地最长的已证链末尾的区块。

    • 确认规则(Commit Rule)。一个区块在区块链中被确认(commit)意味着网络中所有诚实节点对这个区块已经达成了共识,不会再对共识结果修改。已证区块并不一定最终会被确认。在一个已证链中,当存在三个连续的已证区块时,其中前两个区块以及同一链上之前的所有区块都被确认。在这里,连续区块的意思是连续的 epoch。例如,在图 1 中,epoch 5、6、7 连续产生了三个已证区块,因此当区块 7 成为已证区块时,区块 5 和 6 以及之前的区块 2 都被确认。

    图片 

    Streamlet 协议的整个流程到这里就全部介绍完了,是不是堪比比特币中的 PoW 一样简单?其中的发布规则和投票规则类似于比特币中的最长链(The Longest Rule)原则,而确认规则类似于比特币中一般需要末尾 6 个区块确认的规则。两者看起来有很多相似之处,但算法本质却大有径庭。从这点看来,Streamlet 吸收了区块链的设计精髓并将其与传统的 BFT 协议融合在一起,得到了新一代的 BFT 协议。那么有些读者可能想问了,如此简单的协议安全性如何呢?

    安全性

    在区块链中,协议的安全性可以简单表述为不存在两个同样高度的不同区块被确认。在这里我们简单通过图示来展示在异步网络以及拜占庭攻击的情况下 Streamlet 是如何保证安全性的。如上面的图 1 所示,由于 epoch X 的区块与区块 6 在同一高度,那么问题可以转化为:是否存在区块 X 且 X 是已证区块?

    为了证明上面的问题不存在,我们采用反证法。首先,假设存在已证区块 X,那么只存在两种可能性,即 X = 4 或者 X ≥ 8,这是由于同一个 epoch 不可能产生两个已证区块(诚实的 replica 不会在同一 epoch 给不同的区块投票)。下面分情况讨论。

    • X = 4。由于区块 X 是已证区块,意味着有超过 2/3 的节点给区块 X 投票,那么可以进一步推论出超过 2/3 的节点在给 X 投票的时候已经在本地有了已证区块 3。因此,当协议运行到 epoch 5 的时候,不可能有足够多的节点给区块 5 投票。这是由于投票规则的限制,诚实节点只给最长已证链上的区块投票。这与区块 5 是已证区块的假设违背。

    • X ≥ 8。由于区块 7 是已证区块,意味着有超过 2/3 的节点给区块 7 投票,那么进一步可以推测超过 2/3 的节点在给区块 7 投票的时候已经在本地有了已证区块 6。因此,当协议运行到 epoch X 的时候,同样由于投票规则的限制,区块 X 不可能成为已证区块,这与假设违背。

    上面两种情况已经包含了可能出现的所有情况,因此安全性得证。虽然图 1 所示的情况是一个个例,但很容易对结论进行一般化证明。详细证明可以参考原论文。

    活性

    活性的含义是客户端发送的交易最终会在区块链上被确认。在传统 BFT 协议中,活性的保证的其中一个前提是足够多的诚实节点在同一 epoch 的时间足够长。Streamlet 为了使得协议足够简单,采用了同步时钟来保证活性。例如,每个 epoch 被预设成固定的 1 秒钟。在实际的使用中可以将每个 epoch 的时长根据网络最大延迟来设置。由于以上的限制,Streamlet 一般只会被部署在网络条件较好的数据中心网络中,否则很难找到一个合适的 epoch 长度,进而影响协议性能。

    在 Streamlet 中,活性的证明被表述为在 GST 之后如果连续 5 个 epoch 都是诚实的 leader,那么一定会有区块被确认。由于在长时间运行中,总会出现至少一次联系 5 个 leader 都是诚实的情况,因此活性可以得到保证。那么问题是,为什么需要 5 个连续的而不是 3 个?这里可以简单理解为前 2 个 epoch 用来解决由于 GST 所造成的潜在的不一致,之后连续 3 个 epoch 则是确认规则所要求的,为了保证最终能有区块被确认。完整的活性证明可以参考原论文。

    协议对比

    接下来通过对比讨论目前常见的几种 BFT 协议之间的差异。其中,Streamlet 和 HotStuff/LibraBFT 都是新型的链式 BFT,即节点的每次投票不仅是对当前区块的投票,同时也是对这个区块之前所有区块的投票,因此相比于 Tendermint 和 PBFT来说,消息的种类较少,实现起来也更简单,也更容易优化性能。由于链式 BFT 的特性,接收到一轮 2/3 投票的区块并不会被 commit,因此当区块不连续的时候会有分叉产生。

    图片

    在协议同步方面,只有 Streamlet 采用了同步时钟的方式。由于很难保证不同节点之间的时钟严格同步,所以一般情况下每个 epoch 的时间会略长与网络最高延迟,从而提高了协议的延迟。其它三种协议采用传统的超时加倍模式,即每当一段等待时间之后没有收到区块,那么则将下一轮的等待时间加倍。虽然这种方式没有额外的网络开销,但在某些极端情况下会使得协议长时间停滞。LibraBFT 使用了消息传递的模式(Pacemaker)进行同步。虽然这种方式能够快速实现同步,但也使得 view-change 时的消息复杂度提高到 O(n^2)。

    Best-case 延迟是指在最好的情况下协议经过多少轮投票可以确认一个区块。虽然 Streamlet 和 HotStuff/LibraBFT 都要求 3 个连续的区块才触发确认事件。但 Streamlet 可以一次确认两个区块,而 HotStuff/LibraBFT 只能一次确认一个区块。

    从消息复杂度来看,HotStuff/LibraBFT 和 Tendermint 采用聚合签名或者阈值签名的技术由一个节点(比如 leader)将来自 replica 的签名聚合成一个单一签名后再广播给所有 replica,因此消息复杂度可以达到 O(n)。而 Streamlet 和 PBFT 则在投票阶段使用了广播,使得消息复杂度较高。

    另外一个值得被提到的特性是 view-change 时的响应性(Responsiveness)。响应性指的是当 view-change 发生时,下一个 leader 是否能快速推进协议。例如,Tendermint 没有响应性,在发生 view-change 的时候节点需要等待一个 timeout,以确保在 timeout 之内收到所有的有效消息。如果没有 timeout 的假设,则可能会由于节点锁在不同的阶段而导致活性出现问题。HotStuff/LibraBFT 和 PBFT 都有响应性,但代价分别是多一轮的投票以及更高的复杂度。

    从上面的对比可以看出,即使共识算法经过了这么多年的发展,也没有出现哪个协议是全能将军。协议的设计本质就是在取舍,不仅体现在安全性和活性之争,也包括性能、复杂度、容错性、响应性等多种性质。某些协议的特性只有遇到合适的应用场景才能发挥价值。例如,在一些网络环境较好的数据中心当中,选择 Streamlet 可能在工程实现以及延迟上更有优势,而在一些广域网环境中可能选择消息复杂度更低且具有响应性的 HotStuff 更好。

    总结

    Streamlet 作为新一代 BFT 共识协议,很好地将区块链中的链式结构与传统 BFT 相结合,极大简化了协议设计,不仅降低了开发者学习区块链和 BFT 协议的门槛,也为工程师们开发区块链系统提供了很好的模板。

     

    参考文献

    [1] Streamlet: Textbook Streamlined Blockchains

    [2] PaLa: A Simple Partially Synchronous Blockchain

    [3] Practical Byzantine Fault Tolerance

    [4] Tendermint

    [5] Casper the Friendly Finality Gadget

    [6] State Machine Replication in the Libra Blockchain

    [7] HotStuff: BFT Consensus in the Lens of Blockchain

     

    作者简介

    盖方宇

    来自趣链科技基础平台部,区块链共识算法研究小组

    展开全文
  • 基于图分解的共识协议设计与分析
  • 筏:筏共识协议的Elixir实现
  • 复杂多主体系统共识协议设计的新框架
  • Algorand 称其突破了”公链不可能三角“,项目创始人是图灵奖得主、MIT CSAIL 实验室的 Silvio Micali 教授...Algorand 提出的共识协议是项目的一大亮点,本文主要分析 Algorand 共识协议的工作原理,并分析其优缺点。

    概述

    1.1 引言

    Algorand 称其突破了”公链不可能三角“,项目创始人是图灵奖得主、MIT CSAIL 实验室的 Silvio Micali 教授。Algorand 提出的共识协议是项目的一大亮点,本文主要分析 Algorand 共识协议的工作原理,并分析其优缺点。

    1.2 Algorand 设计的初衷

    Algorand 想解决的核心问题是:去中心化网络中低延时(Latency)和高置信度(Confidence)之间的矛盾[1]。

    其中,延时指从发起交易到确认交易所需要的时间;置信度指的是发出的交易不会再被更改的概率。

    在比特币网络中,为了提高交易的置信度,用户必须等待 6 个区块确认(约 1 个小时)的确认延时;而如果选择低延时,比如少于 6 个确认,甚至是 0 确认,则必然导致低置信度,增加“双花”攻击的可能。双花问题是绝大多数加密数字货币的核心问题。比特币中采用 PoW 共识来解决,但链本身仍然有分叉的可能,并且需要较长的共识达成过程和确认时间。

    同时 Algorand 还想解决比特币中 PoW 挖矿耗费巨大资源、交易确认时间长、易分叉、网络呈中心化趋势,可扩展性差等问题。

    1.3 Algorand 是什么?

    根据官方描述,Algorand 是一个采用 permissionless 的纯 PoS 共识的公链项目,结合改进的拜占庭共识协议,可实现快速的交易确认,几乎不会分叉,并且用户数可无限扩展,不会影响交易确认速度。同时兼顾“可扩展、安全性、去中心化”这个“公链不可能三角”[2]。

    (注:”公链不可能三角“的正确性和具体定义存在较多争议[7]。在 Algorand 中:可扩展性指在较大用户规模下仍可实现较高的吞吐量[8],安全性指的是可以对抗恶意攻击[9],去中心化指的是网络完全开放,成为节点没有任何门槛[10]。)

    可扩展性:Algorand 通过可验证随机函数(VRF)随机选择区块的生产者和验证者,一旦得知被选中,生产者或验证者只需广播一个简短的消息即可证明自己的身份。每产生一个新区块在网络中需要交换的消息不会随着用户数的增大而改变,,因此即使用户规模增大,系统仍可保持较高的 TPS(每秒处理的交易数)。Algorand 的 TPS 是比特币的 125 倍。

    安全性:由于采用了上述的 VRF 随机选取生产者和验证者,并且选取的过程完全由节点独立完成,因此Algorand 网络中的攻击者无法预先得知下一个区块生产者和验证者,从而也就无法完成攻击。具体来说,生产者和验证者的身份只有在他们确定自己被选中并广播对应的证明信息时才会被披露,这时攻击者即使立刻采取各种攻击手段,也无法阻止关于新区块的正确消息在网络中的传播。

    去中心化:Algorand 中每一轮的区块生产者和验证者都是随机选取的,并且加入网络没有任何门槛,因此是完全去中心化的。

    下面详细介绍 Algorand 的共识协议。

    Algorand 协议详述

    几乎所有公链项目的区块产生和共识的过程都可以抽象为两个步骤:

    选择出区块生产者,生成新区块

    其他节点对新区块达成共识

    以上步骤周而复始,最终形成一条“不可篡改”的区块链。

    整个共识过程虽然简单,但在实际实现中,必须解决几个关键问题:

    如何选择区块生产者,且保证公平和不可被预测?

    如何对新区块达成共识?

    如何避免分叉?

    如何提高安全性?

    如何扩展到更大规模的用户?

    比特币采用哈希函数的随机性来确保公平,采用工作量证明(PoW)达成共识,同时能够在一定程度上抵抗算力攻击。然而比特币仍然面临上述消耗计算资源、确认时间长、易分叉以及扩展性差等问题。以 Qtum 为代表的采用纯权益证明(PoS)共识机制的项目,同样采用了哈希函数,并且不需要消耗大量的计算资源,然而仍然面临易分叉、安全性及扩展性的问题。

    Algorand 提出了一种新的共识机制解决上述 5 个问题。

    2.1 基础知识

    正式介绍 Algorand 共识协议之前,本文假设读者基本了解以下名词的含义:

    • 哈希函数(Hash)

    • 公钥/私钥

    • 数字签名

    • 交易

    • 区块

    • 账本

    • 共识

    • 拜占庭协议(Byzantine Agreement,BA)

    • 诚实节点

    • 攻击节点

    • P2P 通信

    如果读者对上述概念不理解,请先搜索相关关键词进一步了解,再阅读以下内容。

    2.2 Algorand 的基本过程

    Algorand 协议可以按照时间顺序划分为不同轮次,每一轮都会达成共识并生成新区块。其典型的通用过程如下:

    每一轮共识开始时,随机选出潜在的 leaders,各自生成新区块,对新区块进行签名和广播

    随机选出验证组,对 leaders 广播的新区块进行验证,达成共识后广播确认新区块,进入下一轮

    接下来具体讨论 Algorand 共识协议细节,本节主要参考[4]。

    2.3 保证 Algorand 的随机性:可验证随机函数

    Algorand 利用 VRF 来选择区块生产者和验证者,保证所有共识参与者都是随机地、公平地被选出的。可验证随机函数(VRF,Verifiable Random Function)是由 Micali 教授等提出的一种伪随机函数,和普通的随机函数一样,对于不同输入,其输出也具有随机性(严格来说是“伪随机”)。其独特之处在于调用者可以提供一个证明,表明这个随机输出确实由该调用者产生。

    VRF 可以有多种实现方式,Micali 等人在其原始论文中提供了一种较复杂的实现方式[3]。Algorand 利用哈希函数和数字签名的特性,提供了一种较为简单的 VRF 实现。具体实现方式是调用者 i 将输入 m 通过数字签名和哈希函数映射为固定长度的输出 H[SIGi(m)],即 m -> H[SIGi(m)]。

    对于任何输入 m,不同的调用者 i 生成的数字签名 SIGi(m) 都是唯一的;而对于不同输入,哈希函数 H 的输出具有随机性,因此上述映射符合 VRF 的”随机性“要求。同时,由于 i 的数字签名 SIGi(m) 可通过其公钥对其身份进行验证,因此其也符合 VRF ”可验证“ 的特性,SIGi(m) 就是 VRF 中提到的”证明“。

    这个函数特别适合在所有节点中随机选择出共识的参与者,下面具体讨论。

    2.3.1 随机选出每一轮的区块生产者(Leader)

    每一轮共识开始时,每个节点都可以通过以下 VRF 独立地验证自己是否是潜在的 leader:

    .H[SIG(r, 1, Q(r-1))] <= 1 / SIZE(PK(r-k))

    其中,H 是哈希运算;SIG 是签名运算;r 是目前的轮次;Q(r-1) 为与 r-1 轮的种子(将在后续 2.6 节中解释);SIZE(PK(r-k)) 是在 r-k 轮所有符合要求的公钥的数量(为什么是 r-k ?k 为回溯系数,也将在 2.6 节中阐述);公式开始的 . 表示将哈希结果转化为小数位,从而保证结果为[0,1)的某个值。

    节点通过自己的私钥计算上面签名的哈希值是否符合要求,从而知道自己是否属于候选的 leader,在此过程中无需和其他节点交换信息。由于哈希函数输出的随机性,可以认为符合要求的候选节点都是随机选出的。候选节点随后可以生成新区块,并向全网提供签名证实自己的身份。如果有多个候选 leader,最终上述哈希值最小的 leader 将在后续的共识中成为本轮最终的 leader。Leader 产生的区块 Br 包含了本轮的所有交易和上述的证明信息,由验证组成员进行共识验证。

    2.3.2 随机选出每一轮每一阶段的验证组

    验证组成员的选择与上述过程类似,在每一轮和每一阶段(step),所有节点都可以独立验证自己是否属于验证组成员:

    .H[SIG(r, s, Q(r-1))] <= n / SIZE(PK(r-k))

    其中 s 为本轮所处的不同阶段,Algorand 在每一轮的各个阶段都有不同的验证组,从而进一步保证安全性;n 为预期的验证组成员数量,可以人为设定;其他参数含义不再重复。

    与候选 leader 一样,每一阶段的验证组成员均随机选出,验证节点在证实自己身份后,可以开始参与共识验证过程,揭露自己的签名即可证明其身份。

    2.3.3 引入权益证明(Proof-of-Stake,PoS)机制

    上述的随机选择过程没有考虑 Token 持有者的权重,恶意节点可能通过大量生成有效私钥从而有极大概率成为区块的生产者和验证者。Algorand 在其公布的实现建议中引入了名为 Honest Majority of Money (HMM)的条件假设,其基本思想来源于 PoS 共识机制,即在上述随机选择过程中引入代币持有量(Stake)作为权重,持有量多的节点被选中的概率较高,而代币持有者往往更倾向于保护网络的安全性。具体可以表示为如下公式:

    .H[SIG(r, 1, Q(r-1))] <= (a(i,r) / M) * (1 / SIZE(PK(r-k)))

    其中,a(i,r) / M 为节点所持有的币的数量占代币总数 M 的权重。其余过程与前面描述一直。

    2.4 Algorand 如何对新区块达成共识:改进的拜占庭协议 BA*

    Algorand 中验证者对新区块达成共识的过程,实际上是一种改进的拜占庭协议(Byzantine Agreement),Algorand 称其为 BA*。

    BA* 由一种改进的二元拜占庭协议(Binary Byzantine Agreement,BBA)和分级共识协议(Graded Consensus,Protocol GC)组合而成[5]。

    2.4.1 改进的二元拜占庭协议 BBA*

    Algorand 引入的 BBA* 是一个改进的二元拜占庭协议(所谓二元,即只能达成 0 或 1 两种共识)。BBA* 可以在诚实节点超过 ⅔ 的情况下,快速达成共识。其具体过程是一个 3 步循环,循环中每一步都有 ⅓ 的概率达成共识。

    节点之间需要进行 P2P 通信,假设被选中的验证节点中有 t 个恶意节点,验证组总的节点数为 n >= 3t + 1,即恶意节点不超过 ⅓ 。协议过程如下:

    在这里插入图片描述

    上述协议中各符号的具体含义可参考[4]。所有验证节点i都有一个初始值 bi(bi = 0 或 1),协议开始时,每个验证节点都会向其他验证节点发送各自的初始值,

    协议第一步(Step 1)是归 0 过程:

    如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔ ,输出共识结果为 0,共识结束,不再执行后面所有步骤

    如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔,则该验证节点把自己的 bi 设为 1

    如果收到的 0 或 1 都没超过 ⅔, 则验证节点把自己的 bi 设为 0

    第一步结束节点再次向其他节点发送各自的 bi

    第二步(Step 2)为归 1 过程:

    如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔ ,输出共识结果为 1,共识结束,不再执行后面所有步骤

    如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔,则该验证节点把自己的 bi 设为 0

    如果收到的 0 或 1 都没超过 ⅔, 则验证节点把自己的 bi 设为 1

    第二步结束节点再次向其他节点发送各自的 bi

    第三步(Step 3)为重新设定初始值的过程:

    如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔,设定 bi = 0

    如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔,设定 bi = 1

    如果收到的 0 或 1 都没超过 ⅔,则每个验证节点会对某个和本轮本阶段相关的信息进行签名,并对签名求哈希。bi 被设置为这些哈希值中最小哈希的最低有效位(仍然是 0 或 1)

    之后返回第一步,直到达成共识

    在 Algorand 中, BBA* 的结果是对是否接受某个区块达成共识,共识结果只有接受(0)或拒绝(1)两种情况。

    2.4.2 分级共识协议 GC

    上述 BBA* 只适用于二元情况,当需要对任意值达成共识,需要引入分级共识协议,将任意值问题转化为二元问题:

    在这里插入图片描述

    Algorand 采用的 GC 分为两步(上图来自 Algorand 白皮书[4],为了和文中其他部分对应,将两个步骤命名为 Step 2 和 3),协议开始时,每个验证节点i各自都有一个初始值 vi(在 Algorand 中即候选的新区块的哈希):

    第一步 (Step 2),所有验证节点将各自的 vi 发给其他所有验证节点;

    第二步(Step 3),对于某个x值,当且仅当节点收到其他验证节点发来该 x 值的总次数(多次收到同一节点发送的x值,只算一次)超过总验证节点数的 ⅔ 时,这个节点会对其它节点发送值 x:

    经过 GC,每个节点都会输出一个值对 (vi, gi),输出规则:

    当收到 x 的总次数超过总验证节点数的 ⅔ 时,设定 vi = x, gi = 2;

    当收到 x 的总次数超过总验证节点数的 ⅓ 时,设定 vi = x, gi = 1;

    否则,设定 vi = 空, gi = 0;

    简单来说,分级共识的作用是从多个可能的候选新区块中选择被大多数认可的一个作为最终候选的区块,再通过上面的 BBA* 最终达成共识。

    2.4.3 BA* = GC + BBA*

    改进的拜占庭协议 BA* 结合了上述 GC 和 BBA*,先通过 GC 把任意值问题(从多个区块中选择一个候选)转化为二元问题(接收或拒绝新区块?),再利用 BBA* 达成快速二元拜占庭共识,从而可以快速对任意值达成共识,其共识过程如下[4]:

    图片

    BA* 的第一步,和第二步,所有验证节点 i 执行 2.4.2 中分级共识 GC,各自得到一个关于新区块的数值对 (vi, gi),其中 vi 为验证节点 i 认为的候选区块哈希(有可能为空),gi = 0 或 1 或 2 。

    第三步,所有验证节点根据各自的 (vi, gi) 设定 BBA* 的初始值,如果 gi = 2,则设定初始值为 0,如果 gi = 0 或 1, 则设定初始值为 1 。之后进行 2.4.1 中的 BBA* 共识过程:

    若共识结果为 0,则最终输出结果为 vi(非空新区块)

    若共识结果为 1, 则最终输出结果为空(即新区块为空)

    无论哪种情况,BA* 都可以在验证节点中达成共识,从而确定新区块及其包含的交易(有可能为空区块)。

    2.5 Algorand 区块链分叉的可能性

    Algorand 实际采用的是经典拜占庭共识的升级版 BA*,它和以比特币为代表的中本聪共识的最大区别在于分叉的可能性。后者由于完全去中心化,节点之间无法完全通信,因此可能仅在部分节点间达成共识,容易发生分叉。

    Algorand 可以通过设定最大可接受的错误概率 F 调整分叉的概率。在 Algorand 提供的两种实现中,其分叉概率分别为 10^-12 和 10^-18,在现实中分叉仅存在理论上的可能。为给读者一个直观概念,假设 Algorand 每秒生成一个区块,10^-18 的概率意味着从宇宙大爆炸至今的时间内,只有可能发生一次分叉,可见其概率极低。

    即使真的发生分叉,Algorand 仍可以从分叉中恢复:

    Algorand 遵守中本聪共识中的最长链法则

    如果有多条最长链,则选择包含非空区块的最长链

    如果仍相同,则可以具体根据区块哈希值进行排序选择

    2.6 Algorand 如何保证安全性

    上述的共识算法在理想情况下可以实现去中心化环境下较快速的拜占庭共识,数字签名和 VRF 本身的安全性也对系统安全提供了基本的保障。除此之外,Algorand 还引入了以下机制,进一步提升安全性:

    种子 Q®

    Algorand 中的随机性主要靠 VRF 保证,每轮随机的选出 leader 及验证组。一个比较直接的想法是把上一区块 B(r-1) 作为随机函数的输入。但这种方法将给恶意节点带来一定的优势:因为区块和其包含的交易高度相关,恶意节点可以通过调整区块中包含的交易集,获得多个输出,并选择对其最有利的交易集产生新区块,从而提高自己在下一轮中成为 leader 或验证组的概率。

    为解决这一问题,Algorand 引入了一个随机的、不断更新的种子参数 Q®,Q® 与交易集本身相互独立,因此恶意节点无法通过调整交易集而获利。

    当区块非空时,Q® = H(SIG(Q(r-1),r) (其中,SIG 为 本轮 leader 的签名)

    当区块为空时,Q® = H(Q(r-1),r)

    可以看出,Q® 在每一轮都发生变化,且与交易本身无关。可以证明,当 Q(r-1) 是随机的,则 Q® 也是随机的。因此恶意节点无法通过改变交易集影响下一个种子的生成。其中,Q(1)的定义没有在相关文献中找到。

    回溯系数 k

    种子参数降低了恶意节点预测 leader 的可能性,但拥有多个潜在 leader 的恶意节点仍可以有比普通节点更高的概率成为下一个区块的 leader,但这个概率会随着区块的变多而逐渐变小。因此,Algorand 引入了一个回溯系数 k,第 r 轮的候选组只从 r-k 轮已存在的候选组中选取,恶意节点在 r-k 轮能够影响第 r 轮候选组的概率极低。

    一次性公钥

    上一节中提到,Algorand 从协议层面的分叉仅在理论上可能发生。在实际中,如果恶意节点可以挟持其他节点,仍可以在验证组被公开的瞬间,强制这些节点重新签名新的区块,从而产生短暂的分叉。Algorand 引入了一种一次性公钥的机制,以杜绝这种可能性。

    具体原理是所有节点在加入 Algorand 网络时(即发生第一笔交易时),都生成足够多的一次性公钥,并公布。这些公钥将用作后续所有轮次的签名验证,并且每个公钥只使用一次,一旦被使用后就销毁。一次性公钥的生成过程需要一定的时间,在 Algorand 的典型实现中,每个新节点需要约 1 小时来生成未来 10^6 轮的所有公钥(约 180 MB 数据)。虽然这增加了节点加入时的门槛,但可以从根本上杜绝上述分叉攻击:因为一旦签名完成,公钥即被销毁,即使被恶意节点劫持,也无法再次签名产生分叉。

    2.7 Algorand 的可扩展性

    对于目前大多数去中心化区块链,如比特币,以太坊以及 Qtum 等,可扩展性的主要瓶颈在于所有链上计算都要进行全网验证,而达成全网共识往往需要一定的时间。Algorand 采用 PoS+VRF 机制进行随机选择区块生产者和验证者,无论网络中有多少节点,每一轮都只需要在少数节点上进行验证,大大提高了共识速度,提高可扩展性。同时,Algorand 还采用了改进的拜占庭共识 BA*,该协议可以减少共识节点之间的通信量,从而进一步提高共识速度。

    此前 Algorand 发布了其性能测试数据,结果表明,在 1000 台 EC2 服务器(AWS 虚拟云服务器)、500,000 用户场景下,Algorand 网络确认时间稳定为 1 分钟,吞吐量约为比特币网络的 125 倍。(比特币约为 7 TPS)且吞吐量不会随着节点数的变多而明显下降[1]。

    Algorand 的优缺点

    通过上述分析,Algorand 基本解决了第 2 节开头提出的一系列问题:

    通过 PoS 和可验证随机函数(VRF)实现区块生产者和验证者的选择

    通过改进的拜占庭共识 BA* 对新产生的区块达成共识

    通过一定的参数设计,从数学上将分叉的概率降至极低值

    引入种子参数,回溯系数以及一次性公钥等机制进一步增强安全性

    每一轮都只进行局部验证,并通过减少节点间通信量进一步提升系统的吞吐量,提高可扩展性

    Algorand 在可扩展性,安全性和去中心化程度三个方面达到了一个很好的均衡,但这不意味着其真的打破了所谓的”不可能三角“。

    可扩展性方面:本质上还是通过较少的验证节点对所有交易进行验证,当网络中全节点变多时,只能保证性能不下降太多,不是真正意义上的可扩展。另外,每一轮验证节点之间的通信依赖于所处的网络状态,网络不稳定将导致共识时间变长,影响 TPS。官方称 Algorand 在 Permissinoed 环境下将有更好的性能[4],原因可能在于 Permissionless 环境下节点所处环境有太多不确定性,会在一定程度上影响可扩展性。

    安全性方面:Algorand 本质上采用的还是拜占庭共识,恶意节点不能超过 ⅓,而比特币可以在恶意节点数小于 ½ 的情况下保证安全。

    去中心化方面:Algorand 采用 PoS 共识和 VRF 决定区块生产者和验证者,拥有较多代币的节点在 PoS 过程中被选中的概率较高,且 Staking 奖励向大户集中,有一定的中心化趋势;而 VRF 选举机制的引入让链上计算只由部分节点进行验证,损失了去中心化系统全网验证的特性。

    此外,Algorand 的主网刚刚发布[6],此前所有结果均是理想环境下的数据,且部分代码未开源,虚拟机相关设计也暂未提及,其实现的复杂度、稳定性和实际性能还有待时间的检验。

    总结

    Algorand 通过创新共识协议设计,同时实现了较高的可扩展性,较好的安全性和一定程度的去中心化,并且所有结论都有较为严格的数学证明,是一种较为创新和严谨的共识机制,目前较适用于有一定准入门槛的去中心化、高吞吐量加密数字货币项目。

    参考文献

    [1]https://algorandcom.cdn.prismic.io/algorandcom%2Fa26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf

    [2]https://www.algorand.com/what-we-do/technology/core-blockchain-innovation

    [3] S. Micali, M. Rabin and S. Vadhan. Verifiable Random Functions. 40th Foundations of Computer Science (FOCS), New York, Oct 1999.

    [4]https://algorandcom.cdn.prismic.io/algorandcom%2Fece77f38-75b3-44de-bc7f-805f0e53a8d9_theoretical.pdf

    [5]https://algorandcom.cdn.prismic.io/algorandcom%2F218ddd09-8d6f-42f7-9db9-5cfbc0aedbe5_algorand_agreement.pdf

    [6]https://www.algorand.com/resources/blog/the-borderless-economy-is-here

    [7] https://www.odaily.com/post/5134308

    [8] https://www.algorand.com/what-we-do/technology/scalability/

    [9] https://www.algorand.com/what-we-do/technology/security/

    [10]https://www.algorand.com/what-we-do/technology/permissionless-blockchain/

    展开全文
  • 全球共识——分布式的未来,恒星共识协议白皮书概论。 _ 奇瓦
  • 摘要 PlatON提出了一种基于部分同步假设情形下的并行拜占庭容错协议CBFT(Concurrent ...本文分析了PBFT,Tendermint,Hotstuff等共识协议,CBFT综合了其优点,通过pipeline的方式完成区块生成和确认的并行,在一个视
  • 本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行...共识协议下被提交的交易首先会不断地复制到不同的验证器,然后执行交易,对于交易顺序和执行结果进行检查,看是否能根据事先约定好...
  • 一类多智能体系统非线性共识协议的设计
  • 本系列分上下两篇,对链化未来共识协议进行详细介绍。文章首先介绍了常见共识协议的PoW,PoS,DPoS,从而引出了链化未来基于BFT的随机PoS共识算法(RPoS),随后详细介绍了链化未来共识协议的架构、消息类型、详细...
  • BFT类共识协议概览与分析实测

    千次阅读 2019-05-16 18:22:23
    本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览: 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等; 针对拜占庭错误场景优化的,包括Aardvark、Primer等等; 为公链应用而优化的协议,...
  • 本系列分上下两篇,对链化未来共识协议进行详细介绍。文章首先介绍了常见共识协议的PoW,PoS,DPoS,从而引出了链化未来基于BFT的随机PoS共识算法(RPoS),随后详细介绍了链化未来共识协议的架构、消息类型、详细...
  • async-raft:使用Tokio框架的Raft分布式共识协议的实现
  • 今天,我们非常高兴的宣布Highway协议...大多数区块链均采用拜占庭容错(BFT)共识协议设计而成。一般来说,“拜占庭容错”协议是指区块链网络在一组分布式自治节点之间高效重复生成共识的能力。 BFT共识模型假设一个网
  • 本系列分上下两篇,对链化未来共识协议进行详细介绍。文章首先介绍了常见共识协议的PoW,PoS,DPoS,从而引出了链化未来基于BFT的随机PoS共识算法(RPoS),随后详细介绍了链化未来共识协议的架构、消息类型、详细...
  • 本文档补充介绍Tendermint 共识协议中validator选取规则以及算法的相关证明。关于Tendermint共识协议的详细解析,请看https://blog.csdn.net/WXblockchain1/article/details/105491701 1. validator选取 与其他...
  • 共识协议——RAFT&PBFT

    2019-06-26 21:45:00
    虽然权力下放可以防止各方的腐败行为,但是它必需要有一个可靠的共识协议来作出决策,让分散在世界各地的节点可以形成一致的意见。常见的共识算法有比特币采用的POW,fabric使用的PBFT,以及分布式系统一般采用的...
  • 本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览: 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等 针对拜占庭错误场景优化的,包括Aardvark、Primer等等 为公链应用而优化的协议,包括...
  • raft是一种分布式共识协议, raft解决的是多个节点如何达成共识的问题 raft保证了高可用, 但不是强一致, 而是最终一致性 raft把时间分成了一个个任期, 任期总是以选举开始的, 如果选举失败, 该任期...
  • 【区块链】分布式共识协议

    千次阅读 2019-01-09 20:45:39
    分布式共识协议 一、概述 总结: 私有链:封闭生态的存储系统,采用PAXOS、RAFT最佳 联盟链:半公开半开放特性,采用拜占庭容错的PBFT算法比较合适 公有链:POW、POS、DPOS是比较适合的高安全性的协议 ...
  • 假设我们生活在一个没有谎言的世界里,那么一群人之间是否更容易达成共识?... 人类本质上是复杂的,我们的行为也是如此...因此,要设计一种能够符合普遍世界观的算法(即共识协议),最关键的是找到一组适用于绝大...
  • 在上一篇解读文章中,我们介绍了星系共识的整体架构和流程以及随机数生成算法。在共识过程中,节点会组建成两大星群——RNP星群和EL...1. 合理出块者选择的重要意义在我们第一篇文章中讲述到,在区块链共识协议中要...
  • 0x00 概论不同于比特币使用的工作量...本文主要内容集中在对共识协议源码的分析,此外还会有对于一些理论的讲解。关于NEO网络通信部分源码分析我还另外写了一篇博客,所以本文中所有涉及到通信的内容我就不再赘述...
  • *免责声明:该文仅代表研究人员个人观点,不代表Qtum量子链基金会立场 ...Algorand 提出的共识协议是项目的一大亮点,本文主要分析 Algorand 共识协议的工作原理,并分析其优缺点。 1.2 Algorand 设...
  • 太极链在协商共识协议中发挥的作用。人类本质上是复杂的,他们的行为也是如此。因此,处理许多交互的协议是一项相当具有挑战性的任务。每个人都受到一系列独特因素的刺激,因此对刺激的反应也不同。因此,找出适用于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,584
精华内容 633
关键字:

共识协议