区块链共识算法简述

区块链是一个去中心化的分布式系统，没有了中心机构，系统所面临的第一个问题是一致性的保障。一致性是指对于系统中多个服务节点，给定一些列操作，在使用相同的协议（共识算法）情况下，试图使得它们对处理结果达成某种程度的一致。

举个例子：如果有6个节点，由其中某个节点发起一笔交易（或者说提案 Proposal），其他5个节点是否能达成一致？认为这笔交易是有效的？

并且，在分布式系统中，由于引入了多个节点，所以系统中会出现各种非常复杂的情况：节点失效、节点故障或者宕机，网络延迟、恶意黑客攻击等等问题。

而共识算法就是用来保证分布式系统一致性的方法

一般情况下，我们把节点的故障（失效、不响应）称为"非拜占庭错误"，而恶意响应（黑客攻击、双重支付）的情况称为“拜占庭将军错误”

这里，再简单说下拜占庭将军问题的起源：

拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军需要通过信使来传递消息，以保证行动一致（达成共识）。但是有些将军中是隐藏的叛徒，他们会用虚假的消息垃圾扰乱忠诚将军们的计划。大家不知道叛徒是谁，那么，忠诚的将军们有什么办法达成一致的的行动而不被虚假信息干扰呢？

解决办法就是，在理想情况下让忠诚的将军们达成一致，不过要是叛军的数量跟忠诚的将军数量一样的情况下，这个问题就无解。

其实，这个故事并不是历史上真实的事件，而是莱斯利·兰波特(Leslie Lamport)为了研究分布式一致性问题而创造的，但由于十分形象，所以常常被引用。

既然创造了一个问题，当然也会有对应的解决办法，解决拜占庭将军问题的算法就是Byzantine Fault Tolerant（BFT）共识算法。

常见的共识算法有：Paxos、Raft、PBFT、PoW(比特币使用)、Pos(以太坊使用)等

对于不需要货币体系的许可链或者私有链来说，绝对信任的节点，以及高效的需求上述共识算法并不能提供，因此对于这样的区块链，传统的一致性算法称为首选：

1、BPFT 拜占庭容错

PBFT算法的核心理论是n>=3f+1

n是系统中的总节点数，f是允许出现故障的节点数。换句话说，如果这个系统允许出现f个故障，那么这个系统必须包括n个节点，才能解决故障，大概可以允许约1/3的错误。

一致性的确保主要分为五个概念：client、replica、primary、back、view，四个阶段：预准备(pre-prepare)、准备(prepare)和确认(commit)

用一个例子来说明就是：

2、Paxos 是一种基于消息传递且具有高度容错特性的一致性算法

Paxos中有三类角色Proposer、Acceptor、Learner，主要交互过程在Proposer和Acceptor之间，

Proposer：提出一个提案，等待大家批准为结案

Acceptor：负责对提案进行投票

Learner：被告知结案结果，并与之统一，不参与投票过程

基本过程是，proposer提出提案，先争取大多数acceptor的支持，超过一半支持时，则发送结案结果给所有人进行确认。

3、Raft 是Paxos算法的的一种简化实现

包括三种角色：Learder、candidate、follower

以上问题其实都只能解决非拜占庭将军容错的一致性问题，不能够应对分布式网络中出现的极端情况，因为内部节点并不会故意发送错误消息，但是对于有货币体系的分布式网络来说（比特币、以太坊等），需要更多的保证

4、Pow（Proof-of-Work）工作量证明是一个用于阻止拒绝服务攻击和类似垃圾邮件等服务错误问题的协议

5、PoS(Proof-of-Stake) 权益证明

6、DPOS(Delegated Proof-of-Stake)