从分布式共识到比特币容错

作者: 磨链社区 | 来源:发表于2018-05-18 08:45 被阅读13次

    区块链接P2P分布式架构,分布式统一账本,那么必然也存在一个容错的问题。比特币认为是一个支付交易系统,那么对比目前银行的支付系统。 

    来看一个例子:

    A转账给B

    A发起交易申请,银行系统收到请求。

    银行查询A账户余额。判断是够有足够余额。

    A请求通过(前提余额足够),转账给B。

    整个过程有银行系统来做仲裁和交易,那么把支付系统在分布式架构中,需要考虑的问题就多一点了,如何统一分布式系统一致性的问题,如何确认消息、如何回复、如何同步副本等,简单概述下分布式系统中的共识容错问题。

    在说到分布式系统共识的时候CAP定理肯定会被提及。 

    CAP定理:在一个分布式系统中,不可能同时实现一致性、可用性、分区容忍性。可以满足两个,但是无法满足三个。

    一致性:一个系统中所有节点在系统当前状态达成一致。

    可用性:系统可用且正在处理请求。

    分区容忍性:网络可能发生分区,即节点之间的通信不可保障。

    这个定理2000年提出,被认为是分布式系统中的重要原理,在设计分布式系统的时候都会去参考。

    这个定理存在疑问的话,这么解释下:假设网络中有两个节点A和B,那么A\B在不同的分区,A\B之间不能通信,假设A一个请求希望更新共享状态且通知B来执行。节点A能做的即是,更新A本地状态,这样A和B肯定不一致。那么A不更新本地状态,那么系统就无法响应A发起的请求,系统不可用。

    一般会出现下述三种设计模型: 

    来自:https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/cap.html

    弱化一致性 

    对结果一致性不敏感的应用,可以允许在新版本上线后过一段时间才更新成功,期间不保证一致性。

    弱化可用性

    对结果一致性很敏感的应用,例如银行取款机,当系统故障时候会拒绝服务。MongoDB、Redis 等为此设计。Paxos、Raft 等算法,主要处理这种情况。

    弱化分区容忍性

    现实中,网络分区出现概率减小,但较难避免。某些关系型数据库、ZooKeeper 即为此设计。实践中,网络通过双通道等机制增强可靠性,达到高稳定的网络通信。 

    BASE理论

    BASE是Basically Available(基本可用)、Soft state(软状态)和Eventually consistent(最终一致性)三个短语的缩写。BASE理论是对CAP中一致性和可用性权衡的结果,其来源于对大规模互联网系统分布式实践的总结,是基于CAP定理逐步演化而来的。BASE理论的核心思想是:即使无法做到强一致性,但每个应用都可以根据自身业务特点,采用适当的方式来使系统达到最终一致性。接下来看一下BASE中的三要素:

    基本可用

    基本可用是指分布式系统在出现不可预知故障的时候,允许损失部分可用性。注意,这绝不等价于系统不可用。比如:

    响应时间上的损失。正常情况下,一个在线搜索引擎需要在0.5秒之内返回给用户相应的查询结果,但由于出现故障,查询结果的响应时间增加了1~2秒

    系统功能上的损失:正常情况下,在一个电子商务网站上进行购物的时候,消费者几乎能够顺利完成每一笔订单,但是在一些节日大促购物高峰的时候,由于消费者的购物行为激增,为了保护购物系统的稳定性,部分消费者可能会被引导到一个降级页面。

    软状态

    软状态指允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

    最终一致性

    最终一致性强调的是所有的数据副本,在经过一段时间的同步之后,最终都能够达到一个一致的状态。因此,最终一致性的本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性。

    总的来说,BASE理论面向的是大型高可用可扩展的分布式系统,和传统的事物ACID特性是相反的,它完全不同于ACID的强一致性模型,而是通过牺牲强一致性来获得可用性,并允许数据在一段时间内是不一致的,但最终达到一致状态。但同时,在实际的分布式场景中,不同业务单元和组件对数据一致性的要求是不同的,因此在具体的分布式系统架构设计过程中,ACID特性和BASE理论往往又会结合在一起。

    来自:http://www.bubuko.com/infodetail-2550902.html

    刚刚文章之前提到的银行转账交易,那么在网络中某个节点验证后,账户余额足够,即转账,稍后网络节点之间再同步。这种模式称为最终一致性。因为在未同步时候,节点之间账户的余额会因为转账出现不一致,但算法会最终同步一致。

    最终一致性(Eventual Consistency),结合区块链中第一个应用比特币来简单说下。

    比特币容错

    P2P网络环境下,各个节点之间维护一个共同的状态,分区期间,那么不同的节点有不同的更新,这些更新可能是矛盾的(这个不难理解),那么就需要一个解决矛盾的机制来解决矛盾,使得网络中所有节点达到一致性的状态。

    比特币的网络中是一个随机的网络,目前有众多节点,每个节点共同来维护统一的一条链,所有节点会最终达成一致,执行相同的操作,也就不再需要中介机构来仲裁控制。 

    比特币中有一对密钥、私钥自己保管、公钥和公钥衍生地址对外公开,比特币网络通过协作方式来追踪每个节点的比特币余额。 

    比特币中有,输出、输入、交易的概念,那么通过一个简单流程对比之前的银行转账交易来看:

    节点接收到交易信息

    根据输入、验证输出是否在本地的UTXO,或者验证签名,无效即删除、有效则继续

    根据所有输入,验证金额大小,不符合即删除,符合继续

    更新本地UTXO库

    广播至其他节点

    一个交易输出,总金额要比所有之前相关输入总金额小。

    交易有未确认、确认两个环节

    那么容错采用pow机制:

    POW机制简介 

    POW(Proof of Work),工作量证明机制。我们最直观的理解就是,一份证明,这个证明确认你做了一定的工作量,类似于现代生活中一些检测考试,通过检测考试你就取得了一份证明,只不过这个证明是一个工作量的证明。 

    工作量证明一开始是以工作量证明系统提出,这个概念来自Cynthia Dwork 和Moni Naor 1993年在学术论文中,是一种拒绝服务攻击和滥用服务的对策,要求发起者需要消耗一定量的计算机资源来进行计算。那么POW这个词汇在1999年 Markus Jakobsson 和Ari Juels的文章中正式提出。 

    提到工作量证明,一般都会说到hash现金,亚当·贝克(Adam Back)在1997年发明的,用于抵抗邮件的拒绝服务攻击及垃圾邮件网关滥用。在比特币之前,哈希现金被用于垃圾邮件的过滤。哈希现金也被哈尔·芬尼以可重复使用的工作量证明(RPOW)的形式用于一种比特币之前的加密货币实验中。另外,戴伟的B-money、尼克·萨博的比特金(Bit-Gold)这些比特币的先行者,都是在哈希现金的框架下进行挖矿的。

    工作证明原理 

    首先工作量证明需要客户端做一个有难度的工作且得出一个结果,这个结果公布后,验证的一方需要很快能进行验证。这是不对等的。比如我们在一个字符串后加一个随机数(nonce),对这个字符串进行SHA256计算,然后得到的结果用16进制来表示,我们要求这个计算后的16进制表示的初始几位为:0000,那么才能算通过了验证。这种规则就需要计算机去不断的尝试,当然你可以记得其中一些,但是这个概率毕竟是很小的。正常情况下需要不断的输出计算尝试,直到出现正确的要求结果。 

    数学期望值,计算过程中会统计实际的计算次数,平均后得到的计算的次数,这个数学期望就是要求的“工作量”,当然这是一个符合数学统计学中的概率事件。

    bitcoin中的POW共识机制 

    bitcoin的出现让人们开始了解到POW共识机制,在bitcoin中,把挖矿生成一个新的区块并把交易数据写入区块看做是一道 工作量证明的数学难题,那么这道题目中有四个重点: 

    1.工作量证明函数:bitcoin中使用的就是SHA256算法,这个算法是输出256位的hash函数(本文不对hash函数和SHA265函数做具体说明)。目前还未出现针对SHA256算法的有效攻击方法,当然通过算法算法漏洞攻击这里不展开讨论。 

    2.区块头:bitcoin中的一个区块由区块头和区块中包含的交易列表组成(大小为1M),这里简述下区块头的组成:

    区块头大小为80字节。

    4字节的版本号。

    32字节的上一个区块的散列值。

    32字节的Merkle Root Hash,体现区块头和区块中的交易的关系,区块中包含的交易列表,通过Merkle Tree算法生成Merkle Root Hash。

    4字节的当前的难度值。

    4字节的随机数(nonce)。

    3.难度值:difficulty,这是一个指标,不恒定。它最为关键的作用就是决定了bitcoin网络中,矿工需要经过多少次hash运算才能获得记账权生成区块,进而获得区块奖励(12.5bitcoin)。bitcoin中区块产生的平均速率是10分钟一个,每经过2016个区块后,节点按照公式:新难度值 = 旧难度值 * ( 过去2016个区块花费时长 / 20160 分钟 )调整难度值。控制区块的平均产生时间,如果产生区块速率比10分钟快,那么增加难度值,比10分钟慢就降低难度。

    4.目标值:target,目标值公式:目标值 = 最大目标值 / 难度值 

    最大目标值是一个恒定值: 

    0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF。目标值的大小和难度值是一个反比的关系。在bitcoin中矿工计算出来的区块的hash值必须小于这个目标值。换个说法方便理解:工作量证明过程中不断尝试变换nonce进行SHA256的计算,那么尝试的目的是为了找到一个指定前面有一定数量000的值,这个时候前面要求的0越多,那么表示你的难度越大。 

    (为什么0越多难度越大?你尝试下用不断扔一对骰子以得到小于一个特定点数的游戏。第一局,目标是12。只要你不扔出两个6, 你就会赢。然后下一局目标为11。玩家只能扔10或更小的点数才能赢,假如目标降低为了2,那就难度可想而知。)

    工作量证明过程 

    整个工作量证明过程其实不复杂。

    生成币基交易coinbase。

    打包交易,组成一个交易列表。

    通过Merkle Tree算法生成Merkle Root Hash。

    组装区块头。

    区块头作为工作量证明的输入,不断变换nonce值,通过公式:SHA256(SHA256(Block_Header))双重SHA256计算。结果不断和当前网络的目标值进行比对,一旦发现小于了目标值(target),那么工作量证明完成。

    广播区块到网络中,网络中节点验证。

    验证后等待后续区块生成确认(一般6个)。

    附上比特币挖矿电子分布图: 

    相关文章

      网友评论

        本文标题:从分布式共识到比特币容错

        本文链接:https://www.haomeiwen.com/subject/couwdftx.html