HashGraph ||| 区块链4.0 时代的领航者

        互联网技术的高速发展，让人们进入了信息高速共享的信息时代，人类的生活已经和互联网息息相关，密不可分，到如今人们的个人信息储存在互联网上，互联网交换的是信息，而区块链技术能让人们通过互联网交换价值。

            现如今的区块链技术我们走过了，以btc这种数字HB为首的1.0时代，以像eth创建去中心化的程序、自治组织和智能合约为首的2.0时代，再之后就是以价值互联网为核心的3.0时代，其中最具代表性如EOS、BTM、DFINITY、XPX。现如今人们已经因为btc和eth的交易拥堵头痛不堪，而如今在3.0项目在交易速度方面有了显著的提升。但是现如今的区块链行业是个高速发展且不断创新的行业，人们在思索3.0时代解决交易拥堵，能耗增加等问题的同时也在思考如何实现在区块链的监管，以及进一步让目前的各种技术设想尽快落地，尽早让技术便利人们的生活，当区块链4.0时代到来之时，区块链早已不再是理论设想，而是真正改变人们的生活，让区块链的去中心化和现实中的中心化相结合。

            如今人们在共识机制中提出了一种新的技术HashGraph ，HashGraph 使开发人员能够构建全新的分布式应用程序，这是前所未有的，在一个分布式系统中，为了使得整个系统正常工作，一个久远而又核心的问题就是如何保证集群中所有节点中的数据完全相同并且能够对发起的提案达成一致。共识算法就是用来解决上述问题，从而保证分布式系统一致性的方法。Hashgraph是一种数据结构和共识算法。Hashgraph不是数字货币，也不是区块链（因为它其实是DAG图，并非是链式结构），严格说也不单单是协议。Hashgraph更像是一个底层的出块层而非一个完整的系统。Hashgraph的SDK中包含一个数字货币的Demo，但那仅仅用于演示证明Hashgraph可以用于构建数字货币。Hashgraph能为分布式APP提供高效、公平、安全的基础设施。高吞吐量和异步拜占庭容错（ABFT）的特点，使得Hashgraph在公链和私有链领域都有潜在的使用价值，并且，在保证去中心化的同时不需要繁重的工作量证明。

共识定义:

        终止性(Termination): 所有正常运作的进程（节点）最终会在有限步数中结束并做出决定, 算法不会无尽执行下去；一致性: 所有进程必须做出相同的决定(意见一致 Agreement)；如果所有进程都提议相同的初始决定值，那么所有正确进程都应选择该值(行为统一Integrity)；有效性(Validity): 最终达成一致的决定必须是其他进程提交值中的某一个。

        著名的拜占庭将军问题专门研究了如何处理分布式系统中的错误节点（所谓容错）。Leslie Lamport（共识届的真大牛）在1982年发布的The Byzantine Generals Problem论文中提出的这个模型，可以算是分布式领域中最复杂、最严格的容错模型：系统不会对集群中的节点做任何的限制，错误节点可以做任何坏事，比如延迟响应、不进行响应，发送错误信息、发送随机消息、对不同节点发送不同决定，不同错误节点私下串通来搞事，大魔王横空出世控制多个节点实施有预谋的攻击等等。总之，现实中应该找不到比这个模型中更坏更恶劣的节点们了，他们的行为带有主观恶意且无法被预测。唯一可以保证的是每条消息的原始内容不会被篡改，消息的来源也都可以被判断出来的。

        POW是目前最令人信服的用于公链的共识算法，被人诟病主要在于POW为了使得主链不分叉，强制矿工来解决复杂且无意义的问题（该问题运算复杂但是验证容易），该手段消耗了极大的能源来做无效计算，且共识达成慢，交易吞吐量低下。POW的算法思路是通过增加提案的成本来限制一段时间内整个网络出现提案的个数，并且放宽了对最终一致性的严格确认，只要求沿着最长链进行接续。所以POW下的系统只有概率意义上的最终确认，而无法确定某一时刻全网达到了共识。不过如果能搞出一个只做有效计算的POW，应该是一个有前途的方向。以下是POW和BFT的对比：

        BFT的世界里基本都是默认使用同步通信。这里要引入一个著名的理论，即FLP不可能定理，这是是分布式系统领域最重要的定理之一，它给出了一个非常重要的结论：在网络可靠并且存在节点失效的异步分布式系统中，即使只有一个进程节点失败，则不存在任何一个可以解决一致性问题的确定性共识算法。算是个很惊人的断言了，并且成功阻止了人类在这条路上的无效研究。

除了以上POW和BFT这两大体系外，还有POS，DPOS这些毁誉参半的存在，虽然相比POW，POS展现了很多优势，但是天然也面临着各种分叉的风险，有来自于理性的矿工的故意低成本分叉，也有来自于低权益者单车变摩托驱动下的恶意攻击。 另外一个比较有意思的体系是DAG(有向无环图)上的共识，比如SPECTRE。DAG作为一种数据结构其实就和链(Chain)本身一样，并没有什么神秘的，在大部分情况下，把DAG系的链叫做BlockDAG没什么毛病。DAG和单链比起来就是前者先上车(出块)再买票(共识，获得一致性)，后者是先买票再上车。所以DAG系的链都是动辄吹嘘自己百万并发，先疯狂出完块，然后再一起捋出一个最长链来做主链。由于其拓扑结构的复杂性，以及出块和共识的天然顺序，在双花问题上DAG比传统单链要麻烦不少。像SPECTRE这种的共识引入了投票机制，将DAG的拓扑结构翻译成了投票。节点互相不交流，也不参与投票，投票者是区块本身，区块会为自己所置身于的链投出支持票。

有了以上的知识储备，应该可以开始谈及Hashgraph。Hashgraph可谓是博采众长，所运用和借鉴的科技几乎是涵盖以上的每个点。其中值得称道的分别是公链环境下做异步BFT共识，八卦协议用于传播八卦本身的关系和拓扑结构（DAG）以及虚拟投票。

为什么Hashgraph可以异步BFT?

之前已经说过了FLP不可能理论否决了异步BFT共识的可能性，不过Hashgraph对共识定义中的终结性做了些许放宽，即it is possible for a nondeterministic system to achieve consensus with probability one，这里的paobablity one是相对于guaranteed来说的, 指的是有一定概率下共识算法会无限期的被执行下去，但是这种情况发生的概率很小，接近为0。再换句话说，类似于最终终结性（eventually），即“XX虽会迟到，但绝不会缺席”。所以Hashgraph的共识算法可以是完全异步的（信息可以被无限延迟），非确定性的，且“拜”迟但到。 而且共识算法中没有引入任何领导的角色， 从而规避了领导节点被DoS攻击导致系统问题的风险。

为什么Hashgraph中BFT可能可以用到公链？

之前说到BFT的一大问题是消息复杂度太高，大量消耗系统的网络带宽，而且无法很好的应对动态网络。这里Hashgraph很聪明的引入了传统CS里的八卦协议（Gossip protocol），并且加以了独特的创新，另外再加上虚拟投票，于是在需要共识的时候并不是要突发的大规模消息传递。

Gossip算法灵感来自办公室八卦，只要两个人之间八卦一下，在有限的时间内所有的人都会知道该八卦的信息，别名“八卦算法”，“闲话算法”、“病毒感染算法”或“谣言传播算法”。八卦算法在分布式p2p的场景中获得了大成功，可以很好的当作节点状态传播和管理的手段。本质上八卦算法是一个带冗余的容错算法，更进一步，八卦是一个最终一致性算法或提供一致性算法的手段。虽然无法保证在某个时刻所有节点状态一致，但可以保证在最终某个时刻所有节点一致对某个时间点前的所有历史达成一致。

而且Hashgraph让节点之间八卦的内容是节点间互相八卦的历史记录——被称为散列图（hashgraph）的数据结构。每个节点就在不停维护这个数据结构，并在八卦中把自己知道的事件（Event）散播出去。本质上Hashgraph就是个变种DAG（每个点可以有两个父节点），它里面的端点就是事件(Event)，里面可以包括任何内容，数据或者交易事务，其实就是个容器，我觉得把事件当成区块可能更加容易被大部分所理解。之所以Hashgraph不直接把事件叫做区块源于Hashgraph的高逼格，人家作为一个创新的共识算法只是顺手实现了分布式账本，解决区块链的问题，而不是把区块当作一个第一大问题来解决的。 下文会统一用区块来代替事件，方便阐述。

上图就是一个区块的模样，其中包含区块创建的时间戳，该区块愿意包括的所有交易事务数据，以及两个指向父节点的hash指针。

这第二个图中描述了多个区块连成的散列图，其中每个纵轴是每个不同的节点，其中的圆圈就是区块，越靠近下方的越早出的区块，越靠近上方是越新的快。

当Bob这个话痨随机找到了Alice拉家常的时候，就会把自己当前所知道的一切都原原本本的告诉Alice。然后Alice这里会出一个新块（红点），这个新块里除了加入新的交易事务的同时，还会加上两个指向父区块的hash值，一个指向自己的最新区块（深蓝），一个指向Bob和自己聊天时候最新的区块（天蓝）。Git也是使用hash实现链接的，只不过是单父亲模式。这也是散列图得名的原因，本质上就是一个靠hash连接起区块的图谱。只不过这里的重点不是把具体每个区块叫做事件还是其他什么名字，而是连接本身和其拓扑结构。

由于每个节点都会通过八卦维护一个散列图，所以每个节点计算共识投票的时候可以发起虚拟投票，也就是计算其他节点在给定的散列图中会怎么投票，从而不需要在网络上再做大量双向同步通信。

此外，可以通过打包，压缩和各种优化来使得八卦所占用的带宽变少。

在某一时刻，不同节点的散列图中最新的区块可能都各不一样，但是更早些的区块和继承关系都是一致的， 而且随着时间的推逝和八卦的积极进行，他们的散列图会收敛到相同的结果。这里的一致指的是如果两个节点的散列图里都有区块x，那么这两个x都会指向相同的两个父区块。

Hashgraph特别关注公平性，即交易事务的实际顺序。这在有些场景下是必须的，比如交易所，谁先下单买了同一只股票是需要被明确厘清的。所以Hashgraph里每个节点都会试图整理区块的顺序，这时节点就会对自己发起共识提案，例如“区块a是否早于区块b”，然后节点会照着自己保存的散列图有如精分一般遵从写死的代码逻辑和规则的从每个已知节点的角度进行投票计票和共识运算。这里的共识是异步的，意味着每个节点会在不同时间点发起虚拟投票，做出决定，并且自信满满地相信这个提案在全网络下会获得相同的决定（即共识）。还是那句话，共识迟早会进行并达成，只是有早有晚。

话说如果Alice作假，自己产生了两个新区块b和c都指向自己的最后的一块区块a，那么在Alice的纵轴上就会从链状变成树状，等于进行了分叉攻击。如果Alice把b的存在告诉了Bob，而把c的存在告诉了Carol，那么Bob和Carol这两个节点所进行的虚拟投票就会变得不一样。为了防止这个问题的发生，Hasgraph引入了可见（Seeing）和强可见（Strongly seeing）的概念。

区块y“可见”区块x意味这区块x是区块y的祖先，y可以通过某个指针通路找到x。但是如果一个坏节点创建了两个平级（即分叉）的区块a和b，并且都是另外一个区块w的父节点，那么这种情况下定义区块w不可见a，也不可见b，因为每个区块按道理只能有最多一个属于同一个节点创造的同级区块。

“强可见”是个关键点，它定义了如果区块x“强见”了(errr..就这样吧...)区块y，那么意味着x和y的连线之间的区块能跨越绝对多数的节点（假设n是节点数目，那么绝对多数指的就是大于n的三分之二，并且绝大多数的定义可以被扩展到POS语境下，即大于2/3总权重，从而转为POS共识。比如下图中，黄区块可以强见橙区块，因为他们自己本身以及他们之间的连线路径中经历的中间区块遍及了绝对多数的参与节点。

强可见保证了两个节点在虚拟计票的时候，能够获得一致的结果。从而为作为Hashgraph能够达成最终拜占庭一致的理论基础。

后续论文中有论证，如果w是非法分叉的两个分支上区块的后继区块，难么他要么强见a要么强见b，不会同时强见a和b。

Hashgraph还引入了不少新概念，比如轮次（round），见证人（Witness）知名见证人（Famous witnesses）。

创建轮次（created round）： 如果一个父区块的创建轮次是r，那么它的子区块的轮次要么也是r，要么是r+1。很显然，子区块不可能拥有比父区块还早的创建轮次。当且仅当子区块强见了r轮中绝大多数的见证人，那么它的轮次会加一。

见证人：每一节点在每一轮次中创建的第一个区块被称为见证人（也可看作该轮次中相对的先祖区块）。某节点也有可能在某一轮次中没有创建见证人区块。下文中也会在某些上下文中将见证人直接称作第x轮先祖，虽然可能有歧义，但是在特定语境下会更加便于理解。

知名见证人：如果上述见证人区块在被创建出来之后就被很快得传播到了其他节点上，那么这些见证人区块就可以被称作知名见证人。更具体的说，如果第r轮的见证人区块能被绝对多数的第r+1轮的见证人可见，那么他就是知名见证人。

每个节点都可以在本地通过虚拟投票的拜占庭协议来决定某见证人区块是否是知名见证人。每个r＋1轮的见证人区块都会对某第r轮见证人区块进行投票；而第r+2轮的某一见证人会对第r+1轮的投票进行计票，即第r+2轮的见证人会从自己可以强见到的第r+1轮见证人那里收集投票结果。一旦某个投票结果（Yes or No）的计票数目超过绝大多数，见证人就可以决定出投票的结果（decide），就算达成了共识。

这里可能是算法中最不容易理解的地方，因为跨越了三代人的恩怨情仇。。。再简单理下：某个第一代先祖是否知名，必须由第二代先祖来投票他们是否可见第一代祖先，而具体的计票则由第三代先祖进行，第三代先祖肯定是可以强见绝对多数的第二代先祖的（参看创建轮次的定义），所以第三代先祖可以看到并记录下第二代先祖的投票，并且决定投票结果。

并且文中有理论证明，任何一个第三代先祖如果能对投票结果（Yes or No）做出决定，那么这个结果就是全网的结论，因为该轮中其他其他先祖也保证会做出相同的决定。

如果这一轮的见证人没发做出决定（没有任何结果超过绝对多数），那么则会继续交由下一代先祖来计票做决定，直到某轮某个先祖得出明确的结果。文中还有另一理论证明，只要每十轮增加一个随机轮（Coin round），投票肯定终究能完成。在随机轮中，见证者不会做出任何决定，如果见证人收集到了绝对多数的结果，他会根绝结果进行附议投票，否则，见证人则根据自己的数字签名进行随机投票。

在正常情况下，大部分的区块并非见证人区块，所以对于这些区块都不会举行上述的选举知名见证人的投票。而且大部分见证人会在第一轮投票中被一致通过或否决。所以大部分的选举投票不会耗时太过漫长。

此外，一旦所有知名见证人被确定下来，整个网络里的区块顺序（所谓公平性）也就能被更快更容易被推导出来。

确定区块顺序这里引入了接受轮次（received round）的概念，每个区块除了创建轮次外还有接受轮次，第r轮（创建轮次）中所有的知名见证者可见的任何普通区块都会被赋予第r轮的接受轮次。如果有的普通区块没有被所有知名可见证者看到，则它的接受轮次未定，而且肯定会比r更晚。

在确定了接受轮次后，则对所有区块做排序，先按照接受轮次从低到高排，一样的话按照时间戳从早到晚再排，如果还一样的话，则按照区块的签名与某随机数异或出来的结果来排序（将该轮中所有知名见证者的签名进行异或可得到该随机数），这样得出的顺序被称作共识顺序（Consensus order）。

Hashgraph无需工作量证明即可实现共识

在过去的几年，我们看到了很多使用区块链或分布式账本来实现共识的尝试。在密码学货币领域，最常见的解决方案是工作量证明，虽然权益证明也有意义。但是，也有人试图使用全新的方法来实现共识。Hashgrap就是其中一种创新的技术。

Hashgraph是“互联网和去中心化技术的未来。”这项全新的分布式账本技术成本低廉，因为它不需要像比特币一样的工作量证明。而且更快捷，交易吞吐量是绝大多数区块链的50,000倍。