请选择 进入手机版 | 继续访问电脑版

数字货币|区块社区-汇集国内外数字货币资讯的自媒体博客

 找回密码
 立即注册
搜索
热搜: 区块链
查看: 154|回复: 0

区块链时代的拜占庭容错:Tendermint(一)

[复制链接]

607

主题

607

帖子

248

积分

中级会员

Rank: 3Rank: 3

积分
248
发表于 2019-2-21 17:23:59 | 显示全部楼层 |阅读模式
本文节选自:Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
原文作者:Ethan Buchman
译者注:
Tendermint是一个分布式系统状态复制引擎,用于在多台机器安全一致地复制一个应用。所谓安全性,指的是即使有多达1/3的机器出现任意故障的情况下, Tendermint仍然能够正常工作。所谓一致性,指的是每一个正常工作的机器都会有着同样的交易日志,计算相同的状态。安全一致的复制是分布式系统中一个基本原则问题,它在各种应用程序(从货币到选举,到基础设施规划等)中的广泛应用的容错能力方面承担了极其重要的作用。
Tendermint被设计成易于使用、易于理解,且性能优异,适用于广泛的分布式应用。


分布式共识系统成为现代互联网基础设施中的一个关键组件,正助力于每一个主要的互联网应用。本章节内容介绍了必要的背景材料来理解和探讨这些系统。


复制状态机(Replicated State Machine)


最常见的用来研究和实施分布式共识(distributed consensus)的范例的是复制状态机的范例,其中,一个确定的状态机在数个进程(processes)之间被复制,这样不管部分进程是否失败,这些进程看上去像单个状态机。状态机有一些列输入驱动,这些输入被称作交易(transactions),每一个交易根据其是否有效,可能引起一个状态迁移并返回一个结果。更正式的,交易为数据库上的原子操作(atomic operation),意味着其要么完成要么根本就没有发生,不能返回一个中间状态( intermediate state)。状态交易逻辑(state transition logic)由状态机的状态转移函数决定,这个函数映射了一个交易和目前的状态到一个新的状态和一个返回值。状态转移函数有时也被称为应用逻辑(application logic)。


订购交易(order the transactions)并且将相应的交易日志( transaction log )复制到每一个进程是共识协议的责任。使用一个确定的(deterministic)状态转移函数意味着在给定同样的交易日志的情况下,每一个进程将计算出相同的结果。


复制状态机架构如图2.1所示。



图2.1



图2.1 一个复制状态机在多个机器之间复制了一个交易日志和结果状态。交易从客户端接受,运行了共识协议,在交易日志中订购(ordered),最后执行得到最新状态。在图中,每一个菱形代表了单个机器,其中,虚线代表机器间的通讯用来承载进行订购交易( ordering transactions)的共识协议。


Tendermint的目标是创建一个通用目的,高性能,安全和健壮的复制状态机。


不同时性(Asynchrony)


容错复制状态机(fault-tolerant replicated state machine)的目的是在对上层提供服务的时候,协调网络中的计算机的同步,不管是否存在故障节点。


保持同步意味着成功复制交易日志;提供一个有用的服务意味着在处理新交易的时候保持状态机的可用性。传统上系统的这些方面被各自成为安全性(safety)和可用性(liveness)。通俗地,安全性意味着没有任何坏的事情发生;可用性意味着好的事情最终发生。安全违规( violation of safety)意味着存在两个或者更多的有效的,竞争的交易日志。可用性违规(violating liveness )意味着一个无法响应的网络。


通过接受所有的交易可以很容易来满足可用性。通过不接受任何交易可以很容易来满足安全性。因此,状态机复制算法可以被看作在两者之间的一个平衡。一般地,进程在提交一个新的交易在之前,需要对来自于其他进程的信息设立一个阈值。在同步的环境中,我们对网络消息的最大延迟或者处理器时钟的最大速度作出假设,通过轮流坐庄来提议新的交易,进行大多数投票表决,如果提议者在同步假设的区间内并没有产生任何提议,则跳过(skip)提议者的这一回合。


在一个异步的环境中,没有关于网络延迟或者处理器速度的保证的假设,权衡将变得更为困难。事实上,所谓的FLP不可能性结果(FLP impossibility result)证明了在确定的异步进程(单个进程可能会崩溃)之间的分布式共识的不可能性。该证明意味着,因为进程可能失败,存在协议的有效执行,但进程恰好在某一时间崩溃这样就阻止了共识。因此,我们对共识没有任何保证。


一般地,协议中的同步是通过管理某些交易时用到的超时(timeouts)来进行的。在异步环境中,消息能够被任意延迟,依赖同步来确保安全性的话可能导致交易日志的分叉。依赖同步来保证系统的可用性能够引起共识的宕机,并且服务无法响应。前者通常被看作更为严重,因为调解冲突日志可能是一个令人生畏或者不可能的任务。


实际上,仅当消息延迟能够被良好的定义和控制的时候,同步解决方案才会被使用,例如在一架飞机上的控制器之间,或者利用同步的原子时钟的数据中心之间。因此,尽管存在很多高效的同步解决方案,计算机网络的一般化的不可靠性(general unreliability)太大以至于不能实际投入使用而不显著增加额外的成本。


根本上有两种途径来克服FLP不可能性结果。第一个是采用更强的同步假设-甚至相当弱的假设也是足够的,例如,那个唯一的最终崩溃的进程被怀疑崩溃了,正确的进程不受影响。一般地,这个方法利用leaders,其扮演了一个特别的协作的角色,并且在超时并被认为发生故障了以后可以被跳过。实际上,这样的领导选取机制成功运转起来很难。


第二种克服FLP的方法是使用非确定性的-包含随机化元素,这样达成共识的可能性接近为1。尽管第二种方法更智能并且某些高级加密技术近些年来取得了速度上的提高,依赖随机化的方法通常更慢。


广播和共识


为了让一个进程复制状态到其它进程上,它必须有基本通讯原语的权限来允许其传播或者传递信息。一个最有用的原语是可靠广播(reliable broadcast)。可靠广播(RBC)是一个广播原语满足如下特性,对消息m,有:



有效性(validity) - 如果一个正确的进程广播m,它最终成功传达了m
一致性(agreement) - 如果一个正确的进程成功传达了m,所有最终所有的进程成功传达m
完整性(integrity) - m只传递一次,并且是以广播的形式被发送者发送出去


本质上,可靠广播使得消息最终到达所有的进程一次。


另外,更有用的原语是原子广播( atomic broadcast(ABC)),其满足可靠广播(RBC)和另外的一个属性:


总的顺序(total order) - 如果正确的进程p和q分别传递出m和m',p传达m在m'之前,那么q传达m在m'之前


原子广播是一个可靠的广播,其中值(values)以相同的顺序被发送到每个机器上。注意到这实际上复制交易日志的问题。通俗地讲,该问题可以被称作共识,共识原语的标准定义满足以下条件:


终止性 - 每个正确的进程最终能做出决定
完整性 - 每个正确的进程最多只做出决定一次
一致性 - 如果一个进程做出了v1的决定, 并且另外一个进程做出了v2的决定,那么v1=v2
有效性 - 如果一个正确的进程做出了v的决定,至少一个进程提议了v


直观地,共识和原子广播看上去十分类似,主要的差异在于,原子广播本身作为一个协议是连续的,然而共识期望终止。这就是说,每一个可以精简为另一个。共识可以被精简为原子广播通过决定第一个原子广播的值。原子广播可以精简为共识,通过依次运行许多共识协议的实例,然而存在一些微妙的考量,特别是在处理拜占庭故障方面。一个完整的参数空间的关于原子广播精简为共识的描述仍然是一个开放的研究话题。


历史上,尽管大多数用例实际上需要原子广播,采用的最为广泛的算法是称作Paxos的共识算法,在90年代介绍并且证明该算法正确性的是Leslie Lamport。Paxos同时赋予和困惑了共识科学,一方面提供了第一个真实世界的,实用的,容错的共识算法,另一方面又难于理解和解释。算法的具体实现使用了其专门的技术来从Paxos建立原子广播,使得这个生态难于操纵,理解和利用。不幸的是,几乎没有任何工作使得提高该框架更容易理解,尽管有尝试来描绘解决方案中的各种困难。


在2013年,Ongaro和 Ousterhout发表了Raft,一个状态机复制算法,其主要的设计动机是可理解性。与其从一个共识算法开始,并且尝试建立原子广播,Raft的设计首先考虑的是交易日志,寻求正交组件,其组合在一起来提供最终的原子广播,尽管其不是被这样描述的。


Paxos是工业领域的主要共识算法,在工业领域像亚马逊,谷歌和其他扩建了高可用性全球互联网服务的公司。Paxos 共识位于应用程序栈的底部,提供了资源管理和分配的一致接口,操作在一个更慢的时标相比于其他面对用户的高可用性应用程序。


Raft登场以来得到了广泛的采用,特别是在开源社区,其具有多个主流语言的实现,并且在多数项目中作为其主干。


Raft与Paxos在设计方面主要的不同是先聚焦于交易日志,而不是单个值,特别是允许一个leader持续提交交易直到其卸任,这时领导选举开始生效。在某种程度上,这类似于在区块链中采用的方法,尽管其主要优势是能够容忍不同种类故障。


拜占庭容错(Byzantine Fault Tolerance)


区块链通过在共享数据库上责任的去中心化,减少了对手方风险,因此被称为“信任机器”。比特币由其具有的抵抗任何攻击和恶意行为的能力而著称。传统地,容忍恶意行为的共识协议被称为拜占庭容错共识协议(Byzantine Fault Tolerant )。术语“拜占庭”被使用,源于拜占庭将军们面对的类似问题,这些将军们尝试相互协调来攻击罗马,使用唯一的信使,其中一个将军可能是叛徒。


在一个崩溃故障中,一个进程可能宕机。在一个拜占庭故障中,故障节点能做任何事情。崩溃的故障更容易处理,因为没有进程会对其他进程说谎。只存在崩溃故障的系统可以通过简单的多数决定规则( majority rule)来操作,因此通常能够同时容忍近一半的系统故障。如果系统能够容忍失败的数量是f,这样系统必须至少有2f+1个进程。


拜占庭故障复杂一些。在一个具有2f+1进程的系统中,如果f是拜占庭,这些拜占庭节点可以协作来说任何事情对另外f+1的进程。例如,我们尝试取得单比特共识,并且f=1,所以我们有N=3个进程,A,B,C,其中C是拜占庭,如图2.2所示。C可以告诉A这个值是0,告诉B这个值是1。如果A同意它是0,B同意它是1,那么他们都将认为他们获得了大多数,提交,这样就违反了安全条件。因此,拜占庭系统能够容忍的故障上限小于非拜占庭系统。



图2.2



图2.2 一个拜占庭进程C,告诉A一件事,告诉B另外一件,致使他们得出关于网络的不同的结论。这里。简单的大多数投票导致了安全违规,源于单个拜占庭进程。



<span style="font-size: 14px;">事实上,可以证明拜占庭故障的上限为f

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|小黑屋|数字货币|区块社区-汇集国内外数字货币资讯的自媒体博客 ( 沪ICP备2018201314

GMT+8, 2019-3-21 21:44 , Processed in 1.359359 second(s), 26 queries .

版权所有 亚洲QK投资基金会 X3.2

© 2017-2019 区块链社区QKSNS

快速回复 返回顶部 返回列表