区块链技术的发展历史课件

,7/23/2018,#,共识简史,回顾,现状,未来,区块链技术的发展历史,共识简史 回顾现状未来区块链技术的发展历史,1,区块链共识简史,目录,回顾,现状,未来,小结,区块链共识简史,2,区块链共识简史,2018,Lamport,发表“拜 占庭将军”论文,Liskov,发表,ViewStamped,Lamport,发 表,P,A,X,O,S,论,文,Castro,和,Replication,论文,PBFT论文,Jakobsson,和,J,u,e,l,s,发表,PoW,论文,Z,oo,K,ee,p,e,r,1,.0,发布,中本聪实现 比特币,POW,L,i,t,eC,o,i,n Scrypt,PoW,P,ee,r,C,o,i,n,PoS,R,i,pp,l,e UNL,NXT,PoS,B,i,t,S,h,a,r,e,s,DPoS,P,r,i,m,eC,o,i,n,PoW,Ongaro,和,O,u,s,t,e,r,h,o,ut,发表,RAFT,论文,S,t,e,ll,a,r,SCP,Liu,和,Caching,发表,X,F,T,论 文,E,t,h,e,r,e,u,m,Ethash,PoW,IBM,Fabric,0.6,PBFT,I,n,t,e,l,发布锯 齿湖项目,PoET,共识,O,n,C,h,a,i,n,dBFT,R3CEV,Corda,Tendermint,IBM,Fabric,1.0,Kafka,Z,oo,K,ee,p,e,r,Ethereum,M,e,t,r,o,p,o,li,s,E,t,h,e,r,e,u,m,Casper,PoS,Mike,Kotla,发,Liskov,发表,Burrrows,表,发表,Zyzzyva,Chubby,论,论文 文,Martin,和,Alvisis,发 表,FaB,P,a,x,o,s,论文,Fischer,和,Lynch,发表,FLP,分 布共识容错不可行 论文,198,2,198,5,198,8,198,9,199,8,199,9,200,6,200,7,200,8,200,9,201,1,201,2,201,3,201,4,201,5,201,6,2017,Eric,Brewer,发表,CAP,理 论,区块链共识简史2018Lamport 发表“拜 占庭将军”,3,共识算法的起源,解决集中式计算向分布式计算 转型的首当其冲的一致性挑战,分布式系统,分布式是一种计算模式，指在一个网络中，各节点通 过相互传送消息来通信和协调行动，以求达到一个共 同目标,一致性的问题,分布式系统由于各节点独立运行，相互通信也会出故 障，因此要保证整个系统状态的一致性，需要有共识 协议,分布式系统如何保证一致性？,共识算法的起源 解决集中式计算向分布式计算 转型的首当其,4,分布式系统一致性问题的形象比喻-拜占庭 将军问题（Lamport）,l,拜占庭将军问题,l,l,所有忠诚的将军决定一致的 计划；,少数叛徒不能使忠诚将军采 用错误的计划。,l,简化版拜占庭问题,l,一个指挥官要发一个命令给,n-1,个副官，希望：,l,l,所有忠诚的副官都执行同一 命令；,如果指挥官是忠诚的，每个 忠诚的副官都执行该命令,。,分布式系统一致性问题的形象比喻-拜占庭 将军问题（Lamp,5,共识问题的特征和属性,l,共识问题,（,Consensus,Problem,）,l,特征,l,所有进程都有一个初始值,（,all,processes,have,an,initial,value,）,l,属性,l,一致协议（,Agreement,）,l,所有的非缺陷进程都必须同意同一个值。,l,正确性,（,Validity,）,l,如果所有的非缺陷的进程有相同的初始值，那么所有非,l,缺陷的进程所同意的值必须是同个初始值。,可结束性,（,Termination,）,l,每个非缺陷的进程必须最终确定一个值。,共识问题的特征和属性l 共识问题（Consensus Pro,6,分布式系统与拜占庭将军问题,l,分布式系统节点类型,l,l,正常系统,忠诚的拜占庭将军,任意故障系统,叛变的,Byzantine,将军,l,拜占庭缺陷,（,Byzantine,Fault,）,l,任何从不同观察者角度看表现出不同症状的缺陷,l,拜占庭故障,（,Byzantine,Failure,）,l,由于拜占庭缺陷导致的节点故障,l,故障的分类,宕机、停 机故障,丢消息,任意故障 认证消息,任意故障,分布式系统与拜占庭将军问题l分布式系统节点类型ll正常系统,7,关于拜占庭将军问题的理论证明,l,Lamport,（,1982,）,l,l,当叛徒多于将军总数的三分之一时，同时通信采用同步非防篡改方式，拜占庭将军问题无解。,如果通信采用同步、认证和不可篡改方式，拜占庭将军问题可以在任 意多叛徒情况下有解,（如果将军总数少于叛徒数,+2，,问题就没有意 义）,l,Fischer-Lynch-Paterson,（,1985,）,l,在一个多进程异步系统中，只要有一个进程不可靠，那么就不存在一 个协议，此协议能保证有限时间内使所有进程达成一致。,关于拜占庭将军问题的理论证明lLamport（1982）l,8,关于拜占庭将军问题实际情况假设,l,分布式系统假设,l,故障模型,非拜占庭故障,l l,拜占庭故障,l,通信类型,同步,l l,异步,l,通信网络连接,l,节点间直连数,l,信息发送者身份,实名,l l,匿名,l,l,通信通道稳定性 消息认证性,l l,认证消息 非认证消息,关于拜占庭将军问题实际情况假设l分布式系统假设l故障模型非拜,9,强一致性（,Strong,Consistency,）共识算法,l,强一致性共识算法,l,宕机故障,（,Crash,Failure,）,l,主副本,2PC,3PC,提交,l,宕机,-,恢复故障,（,Crash,Recovery,Failures,）,l,Paxos,Chubby,，,ZooKeeper,，,etcd,l,RAFT,，,ViewStamped,Replication,l,拜占庭故障,（,Byzantine,Failures,）,l,PBFT,（,实用拜占庭容错），,Zyzzyva,，,Fab,Paxos,强一致性（Strong Consistency）共识算法l,10,故障容错办法,状态机复制,（SMR）,状态机复制,（State,Machine,Replication),采用把系统状态复制到各冗余副本节点以及协调客户端 对服务器节点访问的通用容错方法,故障容错办法 状态机复制（SMR）状态机复制（Stat,11,如何保证在故障情况下的一致性？,-,交易的原子性,2PC,两阶段提交,2PC,缺点,当,C,oo,r,d,i,n,at,o,r,和其它一个节点发生故障，其它节点无法知道 是应该提交还是回滚,如何保证在故障情况下的一致性？-交易的原子性2PC 两阶,12,3PC提交可以避免多个节点故障情况,3PC,提交,把第二阶段再划分，从协议上使得第一阶段状态完全确定;,其它节点第二阶段只能确认收到消息，不能提出回滚要求;,第三阶最后交易提交。,3PC,的局限,过于依赖协调节点，如果部分节点认为协调节点故障，将比较复杂,如果一个,Coordinator,故障节点恢复上线,如何处理？,13,3PC提交可以避免多个节点故障情况3PC的局限,13,Paxos,避免对Coordinator的依赖，处理多节点 Crash-Recovery,故障,Paxos,多数集,任意两个多数集之间的交集不是空集,三种角色,Proposer,提议一个被希望接受的值,Accepter,接受提议或拒绝提议,Learner,不参与决策,但必须知道最后结果,两阶段,Prepare,Prepare,(,x,n,),/,acc,(,y,m,),|,acc,(,0),Propose,Propose,(,y,n,),/,ack,(,y,n,),Paxos 避免对Coordinator的依赖，处理多节,14,Paxos,优点和局限,Paxos,优点,Paxos,是一个可以容忍,fn/2,Crash-Recovery,故障的 异步强一致性协议,Paxos,能保证协议性,（Agreement）,和正确性,（Validity）,局限,不能保证可终止性,（Termination）,Paxos,只能保证如果一个值被选择，其它节点只能选择同意一 个值,但它不能保证一个值能被选择到。,Paxos 优点和局限Paxos 优点,15,PBFT,实用拜占庭容错,PBFT,需要,5,轮通信步骤,第一轮,客户端发命令,op,给主节点,第二轮,Pre-prepare,第三轮,Prepare,第四轮,Commit,第五轮,客户端接收服务端的回复,如果,f,+1,回复一样，这个结果被接受。,因为只有,f,个拜占庭服务器，至少有一个正确的服务器支持这个结果。,PBFT 实用拜占庭容错PBFT 需要5轮通信步骤,16,PBFT,强一致性共识算法,PBFT,特性,P,B,F,T,在一个异步系统中能达成共识，容忍,f,n,/,3,拜占庭 故障,P,B,F,T,的异步通信是一个有固定延迟限制的异步通信系统,（接近同步通信）,采用认证的消息,可以验证服务器是否发过一个消息,在最坏情况下,，PBFT,需要用,f,轮才能达到共识。,17,PBFT 强一致性共识算法17,17,区块链共识简史,目录,回顾,现状,未来,小结,区块链共识简史,18,首个区块链共识公有链比特币PoW机制,生成铸币交易，并与其他所有准备打包进区块的交易组成交易列表，通过,M,e,r,k,l,e,树算法生成,Merkle,根哈希；,把,Merkle,根哈希及其他相关字段组装成区块头，将区块头的,80,字节数据作为工作量证明的输入；,不停的变更区块头中的随机数即,nonce,的数值，并对每次变更后的区块头做双,重,SHA256,运算,（即SHA256(SHA256(Block_Header)）,将结果值与当前网络的难度目标值做对比，如果小于目标值，工作量证明完成,难度调整,由于矿工数量动态变化，比特币系统动态调整挖矿难度，使得大约每,10,分钟产生一个区块,共识区块链,最长区块链为共识区块链，代表具有最大工作量的区块链,概率性拜占庭,（Probabilistic,BA）,协议（,Agreement,）,在不诚实节点总算力小于,50,%,的情况下，同时每轮同步区块生成的几率很少的情况下，诚 实的节点具有相同的区块的概率很高。,正确性,（,Validity,）,大多数的区块必须由诚实节点提供,（严格的说，当不诚实算力非常小的时候，才能使大多数区块由诚实节点提供）,可终止性（,Termination,）,约每,10,分钟完成一次共识,比特币,PoW,最终一致性共识,挖矿过程,首个区块链共识公有链比特币PoW机制生成铸币交易，并与其他,19,公有链其它PoW共识算法,其它,PoW,共识算法,LiteCoin,PoW,采用,s,c,r,y,p,t,算法，不但需要计算能力，还需要内存，可以防止暴力破解，对,A,S,I,C,挖矿也有 一定的抵抗力,PrimeCoin,PoW,工作量证明不像比特币那样做无用功，而是寻找质数，具有科学价值，可称为“有用工作 量证明”（Proof,of,Useful,Work”）,Ethereum,Ethash,PoW,比特币,PoW,基础上引入,GHOST（Greedy,Heavest-Observed,Sub-Tree),在共识区块链 计入叔区块,挖矿不但需要计算能力，还需要内存，对,ASIC,挖矿和算力中心化有一定抵抗力,Intel,SawtoothLake,PoET,采用新的,CPU,安全指令，通过可信任运行环境,（TEE）,如,Intel,Software Guard,Extensions,(SGX),，根据验证者等待时间来确定,Leader，,实现公平、随机选取共识 Leader,每个验证者向一个,enclav