区块链共识算法
【摘要】区块链共识算法1、分布式系统案例:售票系统分布式系统的共识算法在一个分布式系统中,如何保证集群中的所有节点中的数据完全相同且能够对
区块链共识算法
1、分布式系统案例:售票系统
分布式系统的共识算法
在一个分布式系统中,如何保证集群中的所有节点中的数据完全相同且能够对某个提案(proposal)达成一致是分布式系统正常工作的核心问题,而共识算法就是用来保证分布式系统一致性的方法。
2、区块链和共识算法的关系
数字货币->双花问题->线性账目(区块链)->共识
3、分布式系统一致性
强一致性:任何时刻保持一致
顺序一致性(Sequential Consistency):Leslie Lamport1979年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出,是一种比较强的约束,保证所有进程看到的全局执行的顺序(total order)一致,且每个进程看自身的执行(totalorder)跟实际发生顺序一致。例如某进程先执行A,后执行B,则实际得到的全局结果中就应该为A在B前面,而不能反过来。同时所有其他进程在全局上也应该看到这个顺序。顺序一致性实际上限制了各进程内的偏序关系,但不在进程间按照物理时间进行全局排序。
线性一致性(Linearizability Consistency ):Maurice P.Herlihy与Jeannette M.Wing在1990年经典论文《Linearizability:A Correctness Condition for Concurrent Objects》中共同提出,在顺序一致性前提下加强了进程间的操作顺序。形成唯一的全局顺序(系统等价于是顺序执行,所有进程看到的所有操作的顺序都一致,并且跟实际发生顺序一致),是很强的原子性保证。但是比较难实现,目前基本上要么依赖于全局的时钟或锁,要么通过一些复杂算法实现,性能往往不高。
弱一致性:某一时刻保持一致
强一致性的系统往往比较难实现。很多时候,人们发现实际需求并没有那么强,可以适当放宽一致性要求,降低系统实现的难度。例如在一定约束下实现所谓最终一致性(EventualConsistency),即总会存在一时刻(而不是立刻),系统达到一致的状态,这对于大部分的Web系统来说已经足够。这一类弱化的一致性,被笼统称为弱一致性(Weak Consistency)。
不能达成一致性的两种情况
我们假设通讯是可靠的。那么我们把照成不能达成一致性的故障情况分为两种:
1、节点只是故障状态,不存在恶意节点,那么我们称“非拜占庭错误”。
2、存在恶意节点的分布式网络,我们称为“拜占庭错误”。
我们区块链面临的一致性问题为“拜占庭将军问题”。
4、分布式系统的同步和异步
同步系统:消息不丢失且秒到
异步系统:消息有延误且可能丢失
5、非拜占庭错误的两种解决方案
1、PAXOS
核心思想:Paxos解决这一问题利用的是选举,少数服从多数的思想,只要2N+1个节点中,有N个以上同意了某个决定,则认为系统达到了一致,并且按照Paxos原则,最终理论上也达到一致,不会再改变。这样的话,客户端不必与所有服务器通信,选择与大部分通信即可;也无需服务器都全部处于工作状态,有一些服务器挂掉,只有保证半数以上存活着,整个过程也能持续下去。
2、Raft
相比paxos的优点是容易理解,容易实现。它强化了leader的地位,把整个协议可以清楚的分割成两部分,并利用日志的连续性做了一些简化。
(1)Leader在时,由Leader同步日志。
(2)Leader挂掉了,选一个新Leader选举算法。
6、拜占庭将军的解决方案
对于可以容忍拜占庭错误的算法:PBFT、中本聪共识(POW)、POS和DPOS四种算法。
1、PBFT:更加实用的拜占庭容错方法。早期的BFT的缺陷:1、假定是同步场景;2、性能太慢(超过100个节点则不可用)。
PBFT算法的核心理论是n>=3f+1 : n是系统中的总节点数,f是允许出现故障的节点数。换句话说,如果这个系统允许出现f个故障,那么这个系统必须包括n个节点,才能解决故障。
PBFT算法在区块链中的应用
步骤:
1.从全网节点选举出一个主节点(Leader),新区块由主节点负责生成;
2.Pre-Preare:每个节点把客户端发来的交易向全网广播,主节点0将从网络收集到需放在新区快内的多个交易排序后存入列表,并将该列表向全网广播,扩散至1 2 3;
3.Preepare:每个节点接收到交易列表后,根据排序模拟执行这些交易。所有交易执行完后,基于交易结果计算新区快的哈希摘要,并向全网广播,1->023, 2->013,3为宕机无法广播;
4.Commit:如果一个节点收到的2f(f为可容忍的拜占庭节点数)个其他节点发来的摘要都和自己相等,就向全网广播一条commit消息。
5.Reply:如果一个节点收到2f+1条commit的消息,即可提交新区块及其他交易到本地的区块链和状态数据库。
2、中本聪共识(POW)
POW:一组通过算法生成的数据,难于生成而易于验证。1993年由Cynthia Dwork and Moni NAOR提出。
比特币使用的Hashcash proof of work由Adan Back在1997年发明,用于防止垃圾邮件和拒绝服务器攻击。Hashcash proof of work被中本聪用于比特币的挖矿。挖矿的过程是选择一个节点作为区块链生产者。
3、POS共识
POS:最早是由网名为“QuantumMechanic”的网友在比特币论坛中提出。其核心思想为拥有币权的人可以进行选举,选举出来大家最终谁来生成区块。
Native POS的面临的问题:nothing_to_stake
就如桌上有十个文件,每个人会在一个文件上签名,最后选出签名最多的一个文件,谁在签名最多的文件上签名就给谁发币。但有些作弊的人,在十个文件上都签字,最终不管哪个文件签名最多,它都能拿到币,这就nothing_to_stake。
现在以太坊用的共识算法是CASPER,CASPER是改进版的POS。
CASPER算法 、Native POS、POW对无力攻击的解决办法:
Native POS:
POS链上产生了分叉,不投票什么也没有,在A分支上投票得到的利益是0.9,在B分支上投票获得的利益是0.1,如果在两个分支上都投票获得的利益=0.1+0.9=1。
POW:
pow链上产生了分叉,不投票什么也没有,在A分支上投票得到的利益是0.9,在B分支上投票获得的利益是0.1,如果在两个分支上都投票获得的利益=0.1/2+0.9/2=0.5,因为POW要分散算力。
CASPER:
CASPER链上产生了分叉,不投票什么也没有,在A分支上投票得到的利益是0.9,在B分支上投票获得的利益是0.1,如果在两个分支上都投票获得的利益=0.1+0.9 -5 = -4,两边都投票会扣取你的5个保证金。还有一种更严格的方法,虽然你没有在两个分支上都投票,但你只有在短的分支上投票就扣你5个保证金。
4、DPOS共识:Delegated Proof of Stake
DPOS由BM提出:由代币持有者选择见证人节点,由一组见证人通过round-robi的方式轮流产生区块。在15/21个人对一个区块进行签名,然后区块得到确认。
DPOS对Nothing_to_stake的应对方案:让生产者被淘汰。“Miners”are now generally public,known individuals rather than anonymous individuals.
为什么是15/21个人可以达到共识?(n-(n-1)/3) 所以(21-(21-1)/3)=15
DPOS的理念:由持有者进行投票,最大化的分散持有者的规模,最小化的代价来加固网络(无需挖矿),最大化网络性能(超级节点),最小化运行网络成本(EOS每年会曾发代币的5%平分给超级节点)。
而DPOS就像一个公司一样运行,股东选举出董事会,董事会成员轮流生成区块,验证通过后上链。区块生产者既没有创造无效的区块的权力,也没有改变社区共识的权利。
就业培训申请领取
环球青藤
官方QQ群扫描上方二维码或点击一键加群,免费领取大礼包,加群暗号:青藤。 一键加群
数据分析师相关文章推荐
|数据分析师最新文章推荐
刷题看课 APP下载
免费直播 一键购课
代报名等人工服务
- 1 传统数据和大数据的区别
- 2 数据分析的8种方法都是哪些?
- 3 3大常用的数据分析工具是什么?
- 4 数据分析的具体流程是什么?
- 5 excel中的运算符
- 6 数据分析的作用有哪些?
- 7 电子商务需要分析哪些数据?
- 8 数据分析包括哪些内容?
- 9 rdd是什么?
- 10 数据分析的基本步骤