TrueChain共识基础PBFT

truechain是一个结合高效的PBFT 与去中心化的 fPoW 的混合共识公链项目。那到时什么是pbft呢，许多人可能对此不大了解

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上（OSDI99）。没错，这个Loskov就是提出著名的里氏替换原则（LSP）的人，2008年图灵奖得主。

这个算法在保证活性和安全性（liveness & safety）的前提下提供了(n-1)/3的容错性。从Lamport教授在1982年提出拜占庭问题开始，已经有一大堆算法去解决拜占庭容错了。但是一句话概括：这些算法都是狗屎！PBFT算法跟这些妖艳贱货完全不同，在只读操作中只使用1次消息往返（message round trip），在只写操作中只使用2次消息往返，并且在正常操作中使用了消息验证编码（Message Authentication Code,简称MAC），而造成妖艳贱货性能低下的公钥加密（public-key cryptography）只在发生失效的情况下使用。作者不仅提出算法，而且使用这个算法实现了一个牛逼的系统（拜占庭容错的NFS），反正性能杠杠的。

系统假设为异步分布式的，通过网络传输的消息可能丢失、延迟、重复或者乱序。作者假设节点的失效必须是独立发生的，也就是说代码、操作系统和管理员密码这些东西在各个节点上是不一样的。（那么如果节点失效不独立发生，PBFT算法就失效了吗？）

作者使用了加密技术来防止欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（其实就是RSA算法）、消息验证编码（MAC）和无碰撞哈希函数生成的消息摘要（message digest）。使用m表示消息，mi表示由节点i签名的消息，D(m)表示消息m的摘要。按照惯例，只对消息的摘要签名，并且附在消息文本的后面。并且假设所有的节点都知道其他节点的公钥以进行签名验证。

系统允许大魔王可以操纵多个失效节点、延迟通讯、甚至延迟正确节点来毁灭世界。但是作者限定大魔王不能无限期地延迟正确的节点，并且大魔王算力有限不能破解加密算法。例如，大魔王不能伪造正确节点的有效签名，不能从摘要数据反向计算出消息内容，或者找到两个有同样摘要的消息。

PBFT算法的优势

1.系统运转可以脱离币的存在，pbft算法共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证。举个例子：我们100个人出现间谍的时候，我们发现我们的100个人大代表出现一人利用权力作恶的时候我们可以考虑在智能合约上直接选举其他的节点去参与我们的这次会议。假如这个消息一个人只能传送给3个人大代表，这个这个公式就是3F+1，F为拜占庭的错误节点，当3F+1的确定人数大于2F+1的时候这个共识算法就会生效

这样在保证系统安全的情况下加入了参与方的监管行为，这也是目前我大天朝想要制作的共识算法。

2.共识的时延大约在2~5秒钟，基本达到商用实时处理的要求目前这个算法的确认时间只需要2—5秒的时间，虽然达不到EOS和IOTA毫秒级别的支付确认，但是目前的时间已经达到了可商用的程度。

3.共识效率高，可满足高频交易量的需求。在改进的拜占庭算法中，必须达到共识效率达到最少3分之二的时候算法才会生效。

比特币算法 VS PBFT算法

比特币的交易输出是7笔每秒，理论上类比特币POW可以支持的交易速度的量级是10笔每秒。

比特币系统通信复杂度O(N)，可以支持上万个节点，但是输出不能超过10笔每秒量级，否则不安全。（不过这个已经和现实中的比特币有相当的差距了，因为现实中的比特币没有那么多挖矿节点，相当中心化，所以其实可以支持更高的输出，这里略过不提）

PBFT的交易输出是1000笔每秒量级的，但是不可扩展，没人试过超过64个节点会怎么样，但是目前来说64个节点后需要大量的的成本资源。

PBFT的通信复杂度O(N^2)，目前扩展性不是那么强，但是在交易速度上完胜BTC没有太大的问题。

目前PBFT已经很好了，而且在实际应用中非常成熟，效果也非常好。从区块链类型来讲，公有链以大量用户作为节点、联盟链以少量机构作为节点，而拜占庭容错算法的基础是“大量节点”。如果节点过少，会轻易突破51％，导致作弊。而“大量节点＋算力”的优势，正是为未来的公有链量身打造。

所以初链在使用了pbft在众多公链中属于首创，并极大的提高了系统的处理能力