区块链

　　区块链架构是一种分布式的架构。其部署模式有公共链、联盟链、私有链三种，对应的是去中心化分布式系统、部分去中心化分布式系统和弱中心分布式系统。

　　分布式系统中，多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中，需要主机之间进行状态复制，以保证每个主机达成一致的状态共识。然而，异步系统中，可能出现无法通信的故障主机，而主机的性能可能下降，网络可能拥塞，这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议，以确保各主机达成安全可靠的状态共识。

　　利用区块链构造基于互联网的去中心化账本，需要解决的首要问题是如何实现不同账本节点上的账本数据的一致性和正确性。这就需要借鉴已有的在分布式系统中实现状态共识的算法，确定网络中选择记账节点的机制，以及如何保障账本数据在全网中形成正确、一致的共识。

　　区块链中最重要的便是共识算法，比特币使用的是POS（Proof of Work，工作量证明），以太币使用的是POS（Proof of Stake，股权证明）使得算理便的不怎么重要了，而今POS的变体DPOS（Delegated Proof of Stake，股份授权证明）进一步削减算力的浪费，同时也加强了区块链的安全性。不过，对于不需要货币体系的许可链或者私有链而言，绝对信任的节点，以及高效的需求上述共识算法并不能够提供，因此对于这样的区块链，传统的一致性算法成为首选，PBFT（拜占庭容错）、PAXOS、RAFT。

工作量证明（Proof of Work,POW）

　　区块链共识算法中最常见的是比特币的工作量证明机制，它主要有两个功能：一是保证区块链的下一区块是唯一正确的块，二是防止强大的敌手干扰区块链系统从而导致区块链分叉。

　　工作量证明中，矿工通过竞争解决密码学难题来完成下一个块的增加和区块链的扩展，如图1所示为比特币工作量证明的简图；参与挖矿的矿工竞争将前一区块的hash与一个随机的比特串一起来计算出一个hash值，若输出的hash值满足前若干比特为0，即为解出了该难题。第一个解出难题的人获得扩展一个块的机会，并且能够获得一定量新挖出的比特币以及一小笔交易费作为其工作量的奖励。

　　尽管比特币的工作量证明机制是个非常杰出的共识设计，但并不是完美的。最常见的对工作量证明的质疑有两点：一是消耗算力巨大，不适合大规模系统，并且交易的确认时间需要10-16分钟，不能满足实时性需求；二是大多数挖矿活动集中在电力成本较低的区域，形成了局部中心化的趋势。

png

比特币系统中工作量证明示意图

　　比特币的创造者Satoshi Nakamoto让人们初步认识到区块链改变未来世界的巨大潜力，但落实到具体应用，仍需要进一步探索更快速的、更加去中心化以及资源效率更高的共识算法。为此，许多互联网、计算机科学、金融、工业等行业的学者和业界人士进行了不断的探索，并提出了若干代替性的区块链共识方案，其中最有影响力的是权益证明（Proof of Stake）共识算法。

权益证明（Proof of Stake,POS）

　　权益证明共识是代替工作量证明的共识机制中最完善和受到最多关注的，其共识的达成不需要参与者投入昂贵的计算机设备来参与挖矿竞争。相对于以比特币为代表的工作量证明共识系统中的矿工而言，基于权益证明共识的区块链系统中，参与者的角色是验证者Validator，他们只需要投资系统的代币并在特定时间内验证自己是否为下一区块创造者，即可完成下一区块的创建。如下图所示为权益证明的简要示意图。下一区块创造者是以某种确定的方式来选择，被选中的验证者将合适的交易打包成块并发布到区块链上。验证者被选中为下一区块创造者的概率与其所拥有的系统中代币的数量成正比例，简单来说即拥有300个代币的验证者被选中为下一区块创造者的概率是即拥有100个代币验证者的3倍。

png

　　由于权益证明中创造区块不需要算力资源等高成本，区块创造者不会获得区块奖励，但可以获得一定数额的交易打包费用。用权益证明共识产生区块和扩展区块链的方式也比比特币中用工作量证明的共识效率提高上千倍，并且大大节约了资源。

　　权益证明共识中一旦验证者创建了一个块，该块也需要提交到区块链上。不同的权益证明系统对提交过程的处理方式不同。

　　一个典型的例子是Tendermint，其系统中的每个节点都必须在每一个块上签名（在此过程中的角色称为“签名者”），直至达成了大多数节点对区块验证和记录到链上的共识；在其他一些系统中，选择一组随机的节点进行签名即可达成共识。

　　权益证明有效率高、节约资源的优点，但同时也面临着一些潜在的现实风险，业内研究者通常将其表述为nothing-at-stake问题，意即区块创造者和区块验证者完成各自的工作所投入的成本都极低，因而违背系统协议作恶的损失也很小。基于理性人的自利假设，参与者难免会出现做恶的情况，例如区块创造者同时创造2个块并收取两笔交易费，或者签名者同时签名2个块以获得2笔工作报酬。这些都与系统协议中同一时间段只能产生一个合法的区块且签名者不可对不合法的区块签名的规范相违背。

　　在新兴的“加密经济学”领域，区块链工程师们正在探索解决这些问题的方法。其中一个解决方案是要求验证者将其拥有的系统代币锁定在一种虚拟保险库中。如果验证者试图对系统进行双重签名或同时产生多个块进行分叉，那么这些代币就会被全部或部分罚没。类似的改进机制也在不同的采用权益证明的区块链系统被提出并进行了许多实践。

　　Peercoin是第一个将权益证明实现的代币，其次是blackcoin和NXT。此外，以太坊最早依赖于工作量证明共识，但正计划在2018年初迁移到权益证明,提出Casper试图解决工作量证明和权益证明中的问题。Decred采用的是工作量证明和权益证明的混合共识方案。

授权权益证明(Delegated Proof of Stake,DPOS)

　　又称受托人机制，它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。

　　由于使用了去中心化的投票机制，DPoS相比其他的系统更加民主化。DPoS并没有完全去除对于信任的要求，代表整个网络对区块进行签名的被信任主体在保护机制下确保行为正确而没有偏见。另外，每个被签名的区块都有先前区块被可信任节点签名的证明。DPoS消除了交易需要等待一定数量区块被非信任节点验证的时间消耗。通过减少确认的要求，DPoS算法大大提高了交易的速度。通过信任少量的诚信节点，可以去除区块签名过程中不必要的步骤。

　　DPOS引人注目的安全性来自于其选择块生产者和验证节点质量的算法。运用赞成投票的过程可以确保一个人即使拥有50％的有效投票权也不能独自挑选哪怕一个生产者。DPOS旨在优化拥有强壮网络连接的诚实节点100％参与（共识过程）的名义条件。这使得DPOS有能力在平均只有1.5秒的时间内以99.9％的确定性确认交易，同时以优雅和可检测的方式降级 – 从降级中恢复正常也不过是小事一桩。

共识算法

实用拜占庭容错(Practical Byzantine FaultTolerance,PBFT)

　　PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

　　PBFT能够保证活性和安全性（liveness & safety）的前提下提供了(n-1)/3的容错性。在分布式计算上，不同的计算机透过讯息交换，尝试达成共识。拜占庭将军问题就根据错误计算机的数量，寻找可能的解决办法，这无法找到一个绝对的答案，但只可以用来验证一个机制的有效程度。

　　而拜占庭问题的可能解决方法为：

　　在 N ≥ 3F + 1 的情况下一致性是可能解决。其中，N为计算机总数，F为有问题计算机总数。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。

　　基于拜占庭将军问题，一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

png

其中C为发送请求端，0123为服务端，3为宕机的服务端，具体步骤如下：

Request：请求端C发送请求到任意一节点，这里是0
Pre-Prepare：服务端0收到C的请求后进行广播，扩散至123
Prepare：123,收到后记录并再次广播，1->023，2->013，3因为宕机无法广播
Commit：0123节点在Prepare阶段，若收到超过一定数量的相同请求，则进入Commit阶段，广播Commit请求
Reply：0123节点在Commit阶段，若收到超过一定数量的相同请求，则对C进行反馈

根据上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決，N为总计算机数，F为有问题的计算机总数

N=4 F=0 时：

－－	得到数据	最终数据
A	1 1 1 1	1
B	1 1 1 1	1
C	1 1 1 1	1
D	1 1 1 1	1

N=4 F=1 时：

－－	得到数据	最终数据
A	1 1 1 0	1
B	1 1 0 1	1
C	1 0 1 1	1
D	0 1 1 1	1

N=4 F=2 时：

－－ | 得到数据 | 最终数据 ———- | ———- | ———

A	1 1 0 0	NA
B	1 0 0 1	NA
C	0 0 1 1	NA
D	0 1 1 0	NA

　　由此可以看出，拜占庭容错能够容纳将近1/3的错误节点误差，IBM创建的Hyperledger就是使用了该算法作为共识算法。

PAXOS

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

算法流程：

phase 1
- a) proposer向网络内超过半数的acceptor发送prepare消息
- b) acceptor正常情况下回复promise消息
phase 2
- a) 在有足够多acceptor回复promise消息时，proposer发送accept消息
- b) 正常情况下acceptor回复accepted消息

　　PAXOS中有三类角色Proposer、Acceptor及Learner，主要交互过程在Proposer和Acceptor之间，做成图便如下图所示：

png

　　其中1,2,3,4代表顺序。

　　以下图描述多Proposer的情况，T代表时间轴，图中仅画全一个Proposer与Acceptor的关系：

png

　　A3在T1发出accepted给A1，然后在T2收到A5的prepare，在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况：

1. A5发来的N5小于A1发出去的N1，那么A3直接拒绝(reject)A5
1. A5发来的N5大于A1发出去的N1，那么A3回复promise，但带上A1的(N1, 10%)

　　最终A5也会接受10%

png

　　上图描述，如果已经Promise一个更大的N，那么会直接Reject更小的N

png

　　上述描述了，即使Promise了一个N，如果在未Accepted前，再收到一个更大的N，那么依旧会Reject那个即使已经Promise的N

　　总流程图概括如下：

png

　　PAXOS协议用于微信PaxosStore中，每分钟调用Paxos协议过程数十亿次量级。

RAFT

　　RAFT核心思想很容易理解，如果数个数据库，初始状态一致，只要之后的进行的操作一致，就能保证之后的数据一致。由此RAFT使用的是Log进行同步，并且将服务器分为三中角色：Leader，Follower，Candidate，相互可以互相转换。

　　RAFT从大的角度看，分为两个过程：

选举Leader

　　Follower自增当前任期，转换为Candidate，对自己投票，并发起RequestVote RPC，等待下面三种情形发生；

获得超过半数服务器的投票，赢得选举，成为Leader
另一台服务器赢得选举，并接收到对应的心跳，成为Follower
选举超时，没有任何一台服务器赢得选举，自增当前任期，重新发起选举

Leader生成Log，并与Follower进行Headbeats同步

　　Leader接受客户端请求，Leader更新日志，并向所有Follower发送Heatbeats，同步日志。所有Follwer都有ElectionTimeout，如果在ElectionTimeout时间之内，没有收到Leader的Headbeats，则认为Leader失效，重新选举Leader。

流程图示：

png