[区块链从原理到实现]-区块链中的各种共识算法
[区块链从原理到实现] - 区块链中的各种共识算法
本⽂将介绍区块链中常⽤的各种分布式共识算法，对其原理及典型实现做分析。
主要共识算法有：
POW
BFT
PBFT
IBFT
POS
怎么做菜好吃POS
DPOS
RAFT
PAXOS
IBFT
虚线谈到IBFT就不得不提到摩根⼤通.摩根⼤通实现了⼀个基于go-ethereum的区块链，在这个区块链中，摩根替换了共识算法为IBFT(Istanbul BFT)，这个IBFT其实就是PBFT，只不过摩根⼤通把它⾃⼰实现的PBFT叫做IBFT，所以IBFT的基本原理与PBFT是⼀样的，所不同的是,IBFT中把出块和共识的三阶段结合在了⼀起.
相关链接如下:
摩根⼤通的区块链源代码:
IBFT共识算法介绍:
IBFT共识中的基本流程也就是下⾯这个图了:
如果要分析IBFT的具体过程，那么参考上述的摩根区块链中的共识代码.
如果需要具体了解IBFT的运⾏机制参考上述的IBFT介绍的链接.
后续也会写⼀个⽂章专门来分析IBFT的具体执⾏流程,⽬前还没有完成.待完成后会把链接添加在此处.
PBFT
参考链接:
以下分析均来⾃于上述链接，请⾃⾏参考.
对于不需要货币体系的许可链或者私有链⽽⾔，绝对信任的节点，以及⾼效，这些需求POW,POS,DPOS等共识算法并不能够提供，因此对于这样的区块链，传统的⼀致性算法成为⾸选，例如:PBFT（拜占庭容错）、PAXOS、RAFT。
拜占庭算法过程⽰意图如下:
其中C为发送请求端，0123为服务端，3为宕机的服务端，具体步骤如下：
1. Request：请求端C发送请求到任意⼀节点，这⾥是0
2. Pre-Prepare：服务端0收到C的请求后进⾏⼴播，扩散⾄123
3. Prepare：123，收到后记录并再次⼴播，1->023，2->013，3因为宕机⽆法⼴播
4. Commit：0123节点在Prepare阶段，若收到超过⼀定数量的相同请求，则进⼊Commit阶段，⼴播Commit请求
怎么学习打字5. Reply：0123节点在Commit阶段，若收到超过⼀定数量的相同请求，则对C进⾏反馈
根据上述流程，在 N ≥ 3F + 1 的情況下⼀致性是可能解決，N为总计算机数，F为有问题的计算机总数
DPOS
DPOS准⽩⽪书
原⽂地址：
译⽂如下：
DPOS Connsus Algorithm - The Missing White Paper
DPOS共识算法 - 丢失的⽩⽪书（此处说明在开发DPOS的时候是没有这个⽩⽪书的，这个⽩⽪书是后补充的，姑且算作⽩⽪书。）
This is the missing white paper and analysis of delegated proof of stake (DPOS). The goal of this paper is to provide an analysis of why DPOS works and what makes it robust. An early description of DPOS can be found at bitshares; however, that description also includes many aspects that are not part of the actual connsus process.
这篇⽂章是补充的⽩⽪书及对DPOS的分析（DPOS：代理股权证明）。本⽂的⽬的是对DPOS为什么能够⼯作及其鲁棒性的分析。早期DPOS的描述可以在bitsh ares找到，但是在这个⽹站中的描述包含了许多不是实际共识算法的部分（也就是说此⽂章只是共识算法的描述，更纯粹。）
All blockchains are fundamentally a deterministic state machine acted upon by transactions. Connsus is the process of agreeing on a deterministic order of transactions and filtering invalid transactions. There are many different connsus algorithms that could produce equivalent ordering
of transactions, but DPOS has proven robust, cure, and efficient by years of reliable operation on multiple blockchains.
所有的区块链从本质上来说都是通过交易来处理⼀个确定性状态机。共识就是对确定性的交易顺序及⽆效交易达成⼀致意见的⼀个过程。有多种不同的共识算法都能够达成⼀致的交易顺序，但是DPOS被认为是最鲁棒，安全及许多年在多个区块链上使⽤，被证明是⾼效的。
Like all connsus algorithms, the most harm the block producers can cau is censorship. All blocks must be valid according to the deterministic open sou rce state machine logic.
rce state machine logic.
刚怀孕有点出血是怎么回事就像所有共识算法⼀样，区块⽣产者能引起的最⼤的伤害就是censorship(审查)。通过确定性开源状态机逻辑，所有区块都必须是有效的。
Summary of DPOS Algorithm
DPOS算法摘要。
The DPOS algorithm is divided into two parts: electing a group of block producers and scheduling pr
oduction. The election process makes sure that stakeh olders are ultimately in control becau stakeholders lo the most when the network does not operate smoothly. How people are elected has little impact on how connsus is achieved on a minute by minute basis. Therefore, this document will focus on how connsus is reached after the block producers ha ve been chon.
DPOS算法分为两部分：1.选举区块⽣产者；2.调度并产⽣区块。
三九网选举过程确保了股票持有者对⽹络的最根本的控制，因为如果区块链⽹络不平顺的话，股票持有者的损失最⼤。
区块⽣产者如何被选举出来的对如何在⼀分钟内共识如何达成⼏乎没有影响，所以，本⽂章主要关注区块⽣产者本选举出来之后的共识过程，⽽并不关注区块⽣产者是如何被选举出来的。
To help explain this algorithm I want to assume 3 block producers, A, B, and C. Becau connsus requires 2⁄3 + 1 to resolve all cas, this simplified mo del will assume that producer C is deemed the tie breaker. In the real world there would be 21 or more block producers. Like proof of work, the general rul e is that longest chain wins. Any time an honest peer es a valid strictly longer chain it will switch from its current fork to the longer one.
I will to show by example how DPOS operates under most conceivable network conditions. The examples should help you understand why DPOS is robu st and hard to break.
为了有助于解释算法，我会假定有3个区块⽣产者A,B,C。共识需要2/3+1个来解决所有情况，这个简化模型会假设C永远是打破僵局的那个⼈。在真是世界中，应该有21个或者更多个区块⽣产者。就像POW⼀样，⼀般的规则是最长的链会赢。
重点：在任何时候，⼀个诚实的peer看到⼀个更长的链的时候，它就会从当前的分叉切换到所看到的最长的这个链。
我会⽤更多的例⼦来解释实际情况时各种⽹络情况下的处理过程。这些例⼦会帮助你理解为什么DPOS是鲁棒的及难以被破坏的。
Normal Operation
正常操作。
Under normal operation block producers take turns producing a block every 3 conds.
Assuming no one miss their turn then this will produce the longest possible chain. It is invalid for a block producer to produce a block at any other time sl ot than the one they are scheduled for.
正常操作的时候，区块⽣产者按照顺序每隔3秒产⽣⼀个快。假定每隔⽣产者在其该出块的时候都出块了，那么就会产⽣⼀个最长的链。
重点： DPOS中对于块⽣产者来说，在⾮其出块时间所出的块被视为是⽆效的。
Minority Fork
Up to 1⁄3 of the nodes can be malicious or malfunction and create a minority fork. In this ca the minority fork will only produce one block every 9 conds while the majority fork will produce 2 blocks every 9 conds. Once again, the honest 2⁄3 majority will always be longer than the minority.
最多1/3个节点可能是故障或者恶意并且创造⼀个最⼩分叉.在这种情况下最⼩分叉只会每9秒产⽣⼀个块,⽽主分⽀每9秒会产⽣两个块.所以，这再⼀次说明了，诚实的2/3主节点总是⽐不诚实的少数节点要长.(由于按照时间⽚出块的特性，因为不诚实的节点不能超过1/3，所以出的块肯定⽐诚实的节点少，这样的话不诚实节点的链肯定是⽐诚实节点形成的链短.)
Double Production by Disconnected Minority 断开的少数节点产⽣的同时出多个块的问题.
The minority can attempt to produce an unlimited number of forks, but all of their forks will be shorter than the majority chain becau the minority is limited to growing the chain slower than the majority.
少数派可以试图产⽣⽆数的分叉，但是所有这些分叉都⽐主链要短，因为少数派的数量限制了分叉的链要⽐主链增长的慢.
Network Fragmentation ⽹络原因导致的分⽚.
It is entirely possible for the network to fragment in which ca no fork has a majority of the block producers. In this ca the longest chain will fall to the lar gest minority. When network connectivity is restored the smaller minorities will naturally switch to the longest chain and unambiguous connsus will be res tored. ⽹络问题也可能导致分⽚，这种情况是没有分叉包含⼤多数块的⽣产者(如⽂章中三个出块节点A,B,C各⾃为⼀个分叉进⾏出块.这种情况下包含最多少数派节点的链就是最长的链.当⽹络连接恢复之后叫⼩的少数派就会⾃然切换到最长的链上.在此种情况下，共识能够正常运⾏，不存在冲突.)
注意: DPOS存在分叉.
It is possible for there to be 3 forks where the two longest forks are the same length. In this ca the producers on the 3rd (smaller fork) will break the tie when they rejoin the network. There is an odd number of producers so it is impossible to maintain a tie for long. Later we will cover producer shuffling whic h will randomize order of production to ensure that even if two forks have the same nu
mber of producers, the forks will grow in different length bursts causi ng one fork to take over the other.
有3个分叉，其中两个长度⼀样，这种情况是由可能发⽣的.这种情况下，当第三个较短的链上的节点重新加⼊⽹络后，这些节点有可能会随机分布到两个长的分叉中.但是因为块⽣产者是奇数的，所以两个相同的分叉并⾏增长的时间不会太久，最终会有⼀个更长的分叉形成. 稍后我们会介绍⽣产者重新排序，这样就会保证产出的随机性，从⽽保证了即使有两个分叉有同样的⽣产者，分叉也会以不同的长度⽣长，这样就会使得⼀个分叉的长度超过了另外⼀个分叉的长度.
注意: 如果原本是奇数的出块节点坏了⼀个，变成了偶数，然后这些节点恰好分成了两个分叉，长度相同，这样的话怎么办呢? 原来定期这些节点的出块顺序会重新排列，这样的话就会导致原来长度相同的链会变得不⼀样长，然后两个分叉就会选择⼀个，另外⼀个别丢弃了. (出块顺序定时重新排列解决了偶数节点两个分叉长度相同的问题.)
Double Production by Connected Minority 已连接的少数派在⾃⼰的出块时间产⽣了2个或者多个有效块
Under this scenario minority B produced two or more alternative blocks on their time slot. The next scheduled producer ( C ), may choo to build off of an y one of the alternatives produced by B. Wh
炎黄集团en this happens it will become the longest chain and all nodes that lected B1 will switch forks. It does not mat ter how many alternative blocks a minority of bad producers attempt to propagate, they will never be part of the longest chain for more than a round. 假设B
ter how many alternative blocks a minority of bad producers attempt to propagate, they will never be part of the longest chain for more than a round. 假设B 在⾃⼰的出块时间产⽣了2个或者多个有效块，那么到C出块的时候C会选择其中的⼀个，在其基础上出块，然后被C的选择的分⽀的长度就变成最长的了，然后A再出块的时候也是在这个分⽀上进⾏出块.这样B之前同时产⽣的块中其余没有被选中你的块就成了⽆效块就被丢弃了.
PoS机制虽然考虑了PoW的不⾜，但也有缺点：依据权益结余来选择，会导致⾸富账户的权⼒更⼤，有可能⽀配记账权。股份授权证明机制（Delegated Proof of Stake，DPoS），是对PoW、PoS不⾜的提出的。下⾯以⽐特股为例，理解DPoS的思想。just那么年少
⽐特股引⼊了见证⼈这个概念，见证⼈可以⽣成区块，每⼀个持有⽐特股的⼈都可以投票选举见证⼈。得到总同意票数中的前NN个（NN通常定义为101）候选者可以当选为见证⼈，当选见证⼈的个数需满⾜：⾄少⼀半的参与投票者相信NN已经充分地去中⼼化。见证⼈的候选名单每个维护周期（1天）更新⼀次。见证⼈然后随机排列，每个见证⼈按序有2秒的权限时间⽣成区块，若见证⼈在给定
的时间⽚不能⽣成区块，区块⽣成权限交给下⼀时间⽚对应的见证⼈。如果见证⼈提供的算⼒不稳定或计算机宕机等，持股⼈可以随时通过投票更换这些见证⼈。
可以看到，其核⼼思想是通过缩⼩参与核⼼共识过程的节点数量，以提⾼共识效率。（这⾥可以认为选举见证⼈的过程为⾮核⼼共识过程，⽽见证⼈按序⽣成区块可以认为是核⼼共识过程）
>9寸蛋糕多大
