目录
- 区块链的分类
- 共识算法
-
- FLP不可能原理
- CAP原理
- 拜占庭将军问题
- 共识过程模型
- PoW共识算法
-
- 挖矿过程：
- PoW算法的优缺点
- PoS共识算法
-
- 挖矿过程
- PoS共识算法的优缺点
- 无利害相关攻击（单纯的PoS共识算法没有消耗权益的情况下）
- DPoS共识算法
-
- 两个阶段：
- 优缺点
- PBFT共识算法
-
- PBFT新区块产生过程
- 特点
- Paxos共识算法
- Raft共识算法
-
- 三个子问题
- 三种角色
- 算法过程
区块链的分类
- 公有链
- 无官方组织机构和管理机构，无中心服务器，节点可按照系统规则只有接入网络
- 联盟链
- 由若干机构发起，本质上是一个多中心化的区块链系统
- 私有链
- 建立在某个组织内部，其读、写、记账严格按照组织内部的运行规则
- 相比传统的中心化数据库，仍然具备可追溯、不可篡改、防止内部作恶的优点。
共识算法
区块链共识算法是指为了完成区块链系统中节点的共识，建立在一系列协议或规则基础上，能够实现区块构造、选择出块节点、区块验证和区块上链等工作，从而达到所有节点所存储的分布式账本数据一致性的算法。
FLP不可能原理
1. 不存在一个确定性的共识算法，能保证所有非故障进程最终达成一致。 2. 即使系统大部分时间是同步的，只要存在异步可能性（如网络临时分区），共识也无法保证。
CAP原理
- 任何分布式系统只可能同时满足以下两点，没法三者兼顾
拜占庭将军问题
-
拜占庭问题建模的是假设包含恶意节点的分布式系统如何达成一致性共识的问题。
-
将恶意节点称为拜占庭节点。
-
目前的研究结论：如果叛徒的数量大于或等于1/3，拜占庭问题不可解。
-
再有拜占庭节点的情况下，达成共识有两种思路：
- 提高恶意节点作恶成本
- 诚实节点通过投票制止作恶节点
共识过程模型
区块链共识算法的核心问题如何选择出块节点，在一些算法中又称为选主策略。 
区块链系统共识算法的分类：
- 是否拜占庭容错（拜占庭容错和崩溃容错）
- 拜占庭容错（Byzantine Fault Tolerance，BFT）的有PBFT、PoS、PoW、DPos
- 非拜占庭容错(Crash Fault Tolerance，CFT也叫崩溃容错)的有Paxos算法和Raft算法
- 区块链系统部署类型（公有链、联盟链、私有链）
- 是否强一致性（是否保证所有节点实时数据一致）
- 强一致性：所有节点实时同步
- 弱一致性：允许节点短暂不一致，系统最终会同步
- 选主策略
PoW共识算法
工作量证明（Proof Of Work， PoW ）共识算法
- 通过计算能力竞争的方式来保证数据一致性以达成共识（这种方式使得拜占庭节点需要有大量算力资源才能成功破坏公链，因此是拜占庭容错的） PoW的挖矿在前一讲有仔细讲：【第二讲】比特币系统 这里就简单回顾一下： 区块头需要包含：版本号、时间戳、前一区块哈希值、Merkle根哈希值、一个随机数Nonce，和目标值
挖矿过程：
#mermaid-svg-rvEW6mCNQlf8ZvpI {font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .error-icon{fill:#552222;}#mermaid-svg-rvEW6mCNQlf8ZvpI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-rvEW6mCNQlf8ZvpI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .marker.cross{stroke:#333333;}#mermaid-svg-rvEW6mCNQlf8ZvpI svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-rvEW6mCNQlf8ZvpI .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .cluster-label text{fill:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .cluster-label span{color:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .label text,#mermaid-svg-rvEW6mCNQlf8ZvpI span{fill:#333;color:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .node rect,#mermaid-svg-rvEW6mCNQlf8ZvpI .node circle,#mermaid-svg-rvEW6mCNQlf8ZvpI .node ellipse,#mermaid-svg-rvEW6mCNQlf8ZvpI .node polygon,#mermaid-svg-rvEW6mCNQlf8ZvpI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-rvEW6mCNQlf8ZvpI .node .label{text-align:center;}#mermaid-svg-rvEW6mCNQlf8ZvpI .node.clickable{cursor:pointer;}#mermaid-svg-rvEW6mCNQlf8ZvpI .arrowheadPath{fill:#333333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-rvEW6mCNQlf8ZvpI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-rvEW6mCNQlf8ZvpI .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-rvEW6mCNQlf8ZvpI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-rvEW6mCNQlf8ZvpI .cluster text{fill:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI .cluster span{color:#333;}#mermaid-svg-rvEW6mCNQlf8ZvpI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-rvEW6mCNQlf8ZvpI :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
否
是
节点搜集当前时段全网未确认的交易
增加发行新比特币奖励的交易
形成交易集合
计算交易集合的梅克尔树根,写入区块头部
填写区块头的其他元数据,Nonce=0
Nonce加1
计算区块头的双SHA256哈希值
哈希值<=目标值?
成功获得记账权,广播区块
解释一点： 如果在节点搜集当前时段全网未确认的交易后又有新的交易出现了怎么办，要重新计算交易集合吗？
- 这个可以由矿工自己选择，他打包的交易越多手续费越多，但是他只打包很少的交易也可以。
PoW算法的优缺点
- 优点
- 破坏系统需要投入极大的成本，要有压到大多数人的算了（51%攻击）
- 缺点
- 浪费能源
- 区块确认时间难以缩短，性能低(10TPS)
PoS共识算法
POS（Proof Of Stake）权益证明共识算法。
- 持有的权益越大，挖到区块的概率越大。
- 权益体现为节点对特定代币的所有权，一种常见的权益方式币龄定义是每笔交易的代币金额乘以这笔交易的代币在账上留存的时间（以天为单位）。
- 例如A具有1个币，持有80天，则节点A具有80币龄。
挖矿过程
- Hash(Kernel)≤Target*币龄
- Kernel类似PoW中的区块头
- PoS改进了PoW需要消耗大量计算资源、性能低的缺点，用户每次竞争会消耗掉用户的权益
- 对于区块分叉，PoS算法以总消耗币龄最大为标准确定主链（PoW为总计算量为标准）
PoS共识算法的优缺点
- 优点
- 节省能源
- 提升性能（数百TPS）
- 降低中心化趋势
- 安全
- 缺点
- 最初的货币是得借助PoW算法来产生(不然币龄从哪来)
- 有权益者未必希望参与记账、这会导致囤币行为
无利害相关攻击（单纯的PoS共识算法没有消耗权益的情况下）
PoS中质押的代币可以同时在多条链上"重复使用"，不像PoW算力那样具有排他性。所以出现分叉时，他可以投注所有的分叉（虽然这样也需要分散算力，但是PoS并不需要大量的算力） 解决方案：
- 惩罚两边下注
- 惩罚在错误分叉上投票的节点
DPoS共识算法
Delegated Proof-of-Stake Consensus委托权益证明共识算法
- 权益相关方投票选举见证人来生成区块（50%以上投票才能当选）
- 见证者生成区块成功可以获得一定收益，失败则没有收入，未来还有可能失去见证人身份
两个阶段：
- 见证人选举：拥有权益的股东节点，投票选出N个见证人节点，每个见证人所获得的票数必须超过50%
- 见证人出块：每一次见证人会有2秒的固定时间来生成新的区块，如果不能在给定时间内完成，就换一个见证人造块。见证人按时出块成功后，会将新区块发给其他见证人进行验证。
优缺点
- 优点
- 性能极大提升（100000TPS）
- 很少产生分叉共存
- 缺点
- 牺牲了去中心化特征
PBFT共识算法
PBFT（Practical Byzantine Fault Tolerance） 实用拜占庭共识算法。
- 主要应用于联盟链中，可以容忍恶意节点不超过1/3的场景
- 每次生成新的区块并添加到区块链的工作作为一个完整的流程，称为视图
- 在每个视图中，只有一个节点会被选举为主节点（其他节点为备份节点），主节点负责生成新区块
PBFT新区块产生过程
- 请求（Request）阶段：客户端c向主节点p发送交易请求；
- 预准备（Pre-prepare）阶段：主节点收到客户端的请求消息验证后，为请求分配编号，然后发送PRE-PREPARE消息给所有副本节点；
- 准备（Prepare）阶段：副本节点收到主节点的PRE-PREPARE消息并验证后，其他节点包括主节点发送PREPARE消息；
- 确认（Commit）阶段：所有参与记账的节点如果收到了2f+1（f为最大可容纳拜占庭节点数）个验证通过的PREPARE消息，则向其他所有节点发送COMMIT消息；
- 响应（Reply）阶段：如果每个节点收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，可以运行客户端的请求操作，并返回REPLY消息给客户端，而客户端如果如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识。
特点
- PBFT共识算法需要传输O(n2)数量级的数据
- 共识时延在2~5秒钟，可商用
- 当有1/3或以上节点无法工作，系统会无法提供服务
- 确定性算法(极少极少产生分叉）
Paxos共识算法
有三种类型的节点：
- proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；
- acceptor：负责对提案进行投票。往往是服务端担任该角色；
- learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端 对某个值达成一致需要每个Proposer、Acceptor、Learner都认为一个value被选定
Raft共识算法
三个子问题
Raft共识算法将分布式系统的一致性问题分为对三个子问题：
- 领导人选举(Leader election)问题
- 日志复制(log replication)问题
- 安全性(safety)问题。
三种角色
- Leader（领导者）：负责日志的同步管理，处理来自客户端的请求，与Follower保持这heartBeat的联系；
- Follower（追随者）：刚启动时所有节点为Follower状态，响应Leader的日志同步请求，响应Candidate的请求，把请求到Follower的事务转发给Leader；
- Candidate（候选者）：负责选举投票，Raft刚启动时由一个节点从Follower转为Candidate发起选举，选举出Leader后从Candidate转为Leader状态；
算法过程
- 日志复制（保证数据一致性）
- Raft算法规定每个任期最多只能有一名领导人，而领导人只能通过追加日志的方式记录交易信息，这样可以保证日志中每一条条目是由唯一的一个领导人决定。
- 通过日志文件中的索引和任期编号来实现日志信息的完整性保证。
