区块链算法基本原理：区块链共识算法
Author：zhoulujun Date：
共识算法可以让机群协同工作，并且可以容忍部分成员主机的故障。通常我们提到主机的故障会区分两种情况对待：拜占庭故障和非拜占庭故障。
比特币是第一个解决了拜占庭故障的去中心化系统，它的方法是使用工作量证明共识（POW）。在一个存在拜占庭故障的系统中，不仅会发生主机崩溃的问题，而且某些成员可能会存在恶意行为去影响整个系统的决策过程。
区块链中的共识算法分为：POW、POS、DPOS、PBFT、RBFT、POOL验证池
1、POW：Proof of Work，工作证明。
一句话介绍：干的越多，收益越多。
依赖机器进行数学运算来获取记账权，资源消耗相比其它共识机制高、可监管性弱，同时每次达成共识需要全网共同参与运算，性能效率比较低，容错性方面允许全网50%节点出错。
比特币在Block的生成过程中使用了POW机制，一个符合要求的Block
Hash由N个前导零构成，零的个数取决于网络的难度值。要得到合理的Block Hash需要经过大量尝试计算，计算时间取决于机器的哈希运算速度。当某个节点提供出一个合理的Block
Hash值，说明该节点确实经过了大量的尝试计算，当然，并不能得出计算次数的绝对值，因为寻找合理hash是一个概率事件。当节点拥有占全网n%的算力时，该节点即有n/100的概率找到Block Hash。
优点：
算法简单，容易实现；
节点间无需交换额外的信息即可达成共识；
破坏系统需要投入极大的成本；
缺点：
浪费能源；
区块的确认时间难以缩短；
新的区块链必须找到一种不同的散列算法，否则就会面临比特币的算力攻击；
容易产生分叉，需要等待多个确认；
永远没有最终性，需要检查点机制来弥补最终性
2、POS：Proof of Stake，股权证明。
一句话介绍：持有越多，收益越多。
主要思想是节点记账权的获得难度与节点持有的权益成反比，相对于PoW，一定程度减少了数学运算带来的资源消耗，性能也得到了相应的提升，但依然是基于哈希运算竞争获取记账权的方式，可监管性弱。该共识机制容错性和PoW相同。它是Pow的一种升级共识机制，根据每个节点所占代币的比例和时间，等比例的降低挖矿难度，从而加快找随机数的速度。
优点：
在一定程度上缩短了共识达成的时间；
相对POW，一定程度减少了数学运算带来的资源消耗
缺点：
还是需要挖矿，本质上没有解决商业应用的痛点；
3、DPOS：Delegated Proof of Stake，委任权益证明
去中心化表示每个股东按其持股比例拥有影响力，51%股东投票的结果将是不可逆且有约束力的。其挑战是通过及时而高效的方法达到51%批准。为达到这个目标，每个股东可以将其投票权授予一名代表。获票数最多的前100位代表按既定时间表轮流产生区块。每名代表分配到一个时间段来生产区块（当轮到他们时，没能生成区块）。所有的代表将收到等同于一个平均水平的区块所含交易费的10%作为报酬。如果一个平均水平的区块含有100股作为交易费，一名代表将获得1股作为报酬。网络延迟有可能使某些代表没能及时广播他们的区块，而这将导致区块链分叉。然而，这不太可能发生，因为制造区块的代表可以与制造前后区块的代表建立直接连接。建立这种与你之后的代表(也许也包括其后的那名代表)的直接连接是为了确保你能得到报酬。该模式可以每30秒产生一个新区块，并且在正常的网络条件下区块链分叉的可能性极其小，即使发生也可以在几分钟内得到解决。
成为一名代表，你必须在网络上注册你的公钥，然后分配到一个32位的特有标识符。然后该标识符会被每笔交易数据的“头部”引用。授权选票：每个钱包有一个参数设置窗口，在该窗口里用户可以选择一个或更多的代表，并将其分级。一经设定，用户所做的每笔交易将把选票从“输入代表”转移至“输出代表”。一般情况下，用户不会创建特别以投票为目的的交易，因为那将耗费他们一笔交易费。但在紧急情况下，某些用户可能觉得通过支付费用这一更积极的方式来改变他们的投票是值得的。保持代表诚实：每个钱包将显示一个状态指示器，让用户知道他们的代表表现如何。如果他们错过了太多的区块，那么系统将会推荐用户去换一个新的代表。如果任何代表被发现签发了一个无效的区块，那么所有标准钱包将在每个钱包进行更多交易前要求选出一个新代表。抵抗攻击：
在抵抗攻击上，因为前100名代表所获得的权力权是相同的，每名代表都有一份相等的投票权。因此，无法通过获得超过1%的选票而将权力集中到一个单一代表上。因为只有100名代表，可以想象一个攻击者对每名轮到生产区块的代表依次进行拒绝服务攻击。幸运的是，由于事实上每名代表的标识是其公钥而非IP地址，这种特定攻击的威胁很容易被减轻。这将使确定DDOS攻击目标更为困难。而代表之间的潜在直接连接，将使妨碍他们生产区块变得更为困难。
优点：
大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。
缺点：
整个共识机制还是依赖于代币，很多商业应用是不需要代币存在的。
4、PBFT：Practical Byzantine Fault Tolerance，实用拜占庭容错算法
PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。
在保证活性和安全性（liveness
& safety）的前提下提供了(n-1)/3的容错性。在分布式计算上，不同的计算机透过讯息交换，尝试达成共识；但有时候，系统上协调计算机（Coordinator / Commander）或成员计算机 （Member
/Lieutanent）可能因系统错误并交换错的讯息，导致影响最终的系统一致性。拜占庭将军问题就根据错误计算机的数量，寻找可能的解决办法，这无法找到一个绝对的答案，但只可以用来验证一个机制的有效程度。而拜占庭问题的可能解决方法为：在
N ≥ 3F + 1 的情况下一致性是可能解决。其中，N为计算机总数，F为有问题计算机总数。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。
优点：
系统运转可以脱离币的存在，pbft算法共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证。
共识的时延大约在2~5秒钟，基本达到商用实时处理的要求。
共识效率高，可满足高频交易量的需求。
缺点：
当有1/3或以上记账人停止工作后，系统将无法提供服务；
当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据；
介绍一个改进的算法：delegated BFT（DBFT，授权拜占庭容错算法）
由权益来选出记账人，然后记账人之间通过拜占庭容错算法来达成共识。此算法在PBFT基础上进行了以下改进：
将C/S架构的请求响应模式，改进为适合P2P网络的对等节点模式；
将静态的共识参与节点改进为可动态进入、退出的动态共识参与节点；
为共识参与节点的产生设计了一套基于持有权益比例的投票机制，通过投票决定共识参与节点（记账节点）；
在区块链中引入数字证书，解决了投票中对记账节点真实身份的认证问题。
优点：
专业化的记账人；
可以容忍任何类型的错误；
记账由多人协同完成，每一个区块都有最终性，不会分叉；
算法的可靠性有严格的数学证明；
缺点：
当有1/3或以上记账人停止工作后，系统将无法提供服务；
当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据；
总结来说，DBFT机制最核心的一点，就是最大限度地确保系统的最终性，使区块链能够适用于真正的金融应用场景。
5、POOL验证池
基于传统的分布式一致性技术，加上数据验证机制。
优点：
不需要代币也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基础上，实现秒级共识验证。
缺点：
去中心化程度不如bictoin；更适合多方参与的多中心商业模式。
从时间上来看，这个顺序也是按该共识算法从诞生到热门的顺序来定。
对于POW，直接让比特币成为了现实，并投入使用。而POS的存在主要是从经济学上的考虑和创新。而最终由于专业矿工和矿机的存在，让社区对这个标榜去中心化的算法有了实质性的中心化担忧，即传闻60％～70%的算力集中在中国。因此后来又出现DPOS，这种不需要消耗太多额外的算力来进行矿池产出物的分配权益方式。但要说能起到替代作用，DPOS来单独替代POW，POS或者POW＋POS也不太可能，毕竟存在即合理。每种算法都在特定的时间段中有各自的考虑和意义，无论是技术上，还是业务上。
至于说算法的选择，共识最好的设计是模块化，例如Notary，共识算法的选择与应用场景高度相关，可信环境使用paxos 或者raft，带许可的联盟可使用pbft ，非许可链可以是pow，pos，ripple共识等，根据对手方信任度分级，自由选择共识机制，这样才是真的最优。
文章转载自：
区块链共识算法 www.jouypub.com/2018/ff1903e1cf56d23dbd9e0a50ce3152b1/
超级账本Fabric最新Raft排序服务深度解析 https://zhuanlan.zhihu.com/p/95558717
转载本站文章《区块链算法基本原理：区块链共识算法》,
请注明出处：https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/blockchain/8252.html