区块链共识算法学习笔记

参考：
http://blog.csdn.net/lsttoy/article/details/61624287
http://bbs.tianya.cn/m/post-me-150924-1.shtml

拜占庭将军问题（Byzantine Generals Problem）

https://yq.aliyun.com/articles/429909

拜占庭帝国的几支军队攻打到了敌人的城市外面，然后分开驻扎。每一支军队由一位拜占庭将军(Byzantine general)率领。为了制定出一个统一的作战计划，每一位将军需要通过信差(messenger)与其它将军互通消息。但是，在拜占庭将军之间可能出现了叛徒(traitor)。这些叛徒将军的目的是阻挠其他忠诚的将军(loyal generals)达成一致的作战计划。为了这一目的，他们可能做任何事，比如串通起来，故意传出虚假消息，或者不传出任何消息。

要解决这个问题，我们是希望能找到一个算法，保证在存在叛徒阻挠的情况下，我们仍然能够达成如下目标：

A. 所有忠诚的将军都得到了相同（一致）的作战计划。比如都决定进攻，或都决定撤退，而不是有些将军认为应该进攻，其他将军却决定撤退。

B. 忠诚的将军不仅得到了相同的作战计划，还应该保证得到的作战计划是合理的(reasonable)。比如，本来进攻是更有利的作战计划，但由于叛徒的阻挠，最终却制定出了一起撤退的计划。这样我们的算法也算失败了。

PoW（Proof of Work，工作量证明）

比特币在Block的生成过程中使用了PoW机制，一个符合要求的Block Hash由N个前导零构成，零的个数取决于网络的难度值。要得到合理的Block Hash需要经过大量尝试计算，计算时间取决于机器的哈希运算速度。当某个节点提供出一个合理的Block Hash值，说明该节点确实经过了大量的尝试计算，当然，并不能得出计算次数的绝对值，因为寻找合理哈希是一个概率事件。当节点拥有占全网n%的算力时，该节点即有n/100的概率找到Block Hash。

PoS（Proof of Stake，股权证明）

PoS也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。

简单来说，就是一个根据你持有货币的量和时间，给你发利息的一个制度，在股权证明PoS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你__发现了一个PoS区块__，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。

这里所谓的__发现了一个PoS区块__，可以是如下形式：

1
SHA256(SHA256(Bprev),A,t)≤balance(A)×m

t为UTC时间戳，Bprev指的是上个区块，balance(A)代表账户A币龄，m是某个固定的实数，即

1
SHA256(上一个区块的哈希,A,t)≤balance(A)×m

唯一的变量就是时间戳t，t不能超过标准时间戳1小时，所以账户A币龄越大，越容易找到合法的下一个区块。

DPoS（Delegated Proof of Stake，委任权益证明）

比特股的DPoS机制，中文名叫做股份授权证明机制（又称受托人机制），它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。DPOS的出现最主要还是因为矿机的产生，大量的算力在不了解也不关心比特币的人身上，类似演唱会的黄牛，大量囤票而丝毫不关心演唱会的内容。

PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错算法）

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。

PBFT过程

  1. 从全网节点选举出一个主节点（Leader），新区块由主节点负责生成。
  2. 每个节点把客户端发来的交易向全网广播，主节点将从网络收集到需放在新区块内的多个交易排序后存入列表，并将该列表向全网广播。
  3. 每个节点接收到交易列表后，根据排序模拟执行这些交易。所有交易执行完后，基于交易结果计算新区块的哈希摘要，并向全网广播。
  4. 如果一个节点收到的2f（f为可容忍的拜占庭节点数）个其它节点发来的摘要都和自己相等，就向全网广播一条commit消息。
  5. 如果一个节点收到2f+1条commit消息，即可提交新区块及其交易到本地的区块链和状态数据库。
    注：4个节点可以容忍一个内奸（拜占庭节点），3n+1个节点可以容忍n个内奸

总结

以上主要是目前主流的共识算法。
　　从时间上来看，这个顺序也是按该共识算法从诞生到热门的顺序来定。
　　对于PoW，直接让比特币成为了现实，并投入使用。而PoS的存在主要是从经济学上的考虑和创新。而最终由于专业矿工和矿机的存在，让社区对这个标榜去中心化的算法有了实质性的中心化担忧，即传闻60％～70%的算力集中在中国。因此后来又出现DPOS，这种不需要消耗太多额外的算力来进行矿池产出物的分配权益方式。但要说能起到替代作用，DPoS来单独替代PoW，PoS或者PoW＋PoS也不太可能，毕竟存在即合理。每种算法都在特定的时间段中有各自的考虑和意义，无论是技术上，还是业务上。

如果跳出技术者的角度，更多结合政治与经济的思考方式在里面，或许还会跳出更多的共识算法，如结合类似PPP概念的共识方式，不仅能达到对恶意者的惩罚性质，还能达到最高效节约算力的目的也说不定。

至于说算法的选择，这里引用万达季总的这一段话作为结束：

一言以蔽之，共识最好的设计是模块化,例如Notary，共识算法的选择与应用场景高度相关，可信环境使用paxos 或者raft，带许可的联盟可使用pbft ，非许可链可以是pow，pos，ripple共识等，根据对手方信任度分级，自由选择共识机制，这样才是真的最优。