本文摘自https://mp.weixin.qq.com/s/9KlHqfGHLf9cELL4x98UCw
https://mp.weixin.qq.com/s/zbFJWIlN3ERIHTvT0TPGDw
Hashgraph 采用不同于线性区块的“哈希图( Hashgraph )”结构和共识机制，旨在实现区块链的终极使命：打造一个可信的网络层。区块链为实现一个无中心化的可信任网络，采取链式结构，挖矿竞争或代理投票的共识模型，形成了今天大多数区块链的样子。而 Hashgraph 直奔主题，不拘束于链式结构，通过同步出块就能实现大规模低成本共识达成（每个人都可以低成本成为节点），更高效（每秒处理25万笔交易），更加公平（无需竞争出块）的互联网信任层。让去中心化价值网络就像使用互联网一样高效和低成本。它提供一个新型的网络：每一个普通人可以成为区块链网络中一个节点，拥有更公平的治理机制，并提供整套完整的 DAPP 开发工具，实现快速低成本的达成共识的一个可信平台。如果能够实现严密的数学及应用检验和白皮书中的描述，那么 Hashgraph 足以成为一个真正的可大规模普及和应用的可信网络，它将会是在可信互联网上探索的一个重要里程碑，如果说我们都在等待下一代区块链技术的到来，Hashgraph 可能是突破区块链局限，从另外一条路径实现区块链最终理想的一个尝试。
注：本文由 NPC 核心成员，美国亚马逊 AWS 核心工程师撰写，由于篇幅有限，本节只节选部分内容，文末有原文链接，本节主要讨论 Hashgraph 的核心结构及共识这两大核心技术。
Hashgraph 既是项目名称也是它的核心架构，也是整个整个公共账本完成共识不同于其他区块链项目的地方，所以在了解它的技术架构之前非常有必要学习一下关于共识的基础知识：
【基础知识】
在一个分布式系统中，为了使得整个系统正常工作，一个久远而又核心的问题就是如何保证集群中所有节点中的数据完全相同并且能够对发起的提案达成一致。共识算法就是用来解决上述问题，从而保证分布式系统一致性的方法，目前加密货币主要的共识是 POW, POS,DPOS等，但是共识的定义范畴要宽泛得多。
共识定义:
1. 终止性(Termination)：所有正常运作的进程（节点）最终会在有限步数中结束并做出决定, 算法不会无尽执行下去。
2. 一致性：所有进程必须做出相同的决定(意见一致 Agreement)；如果所有进程都提议相同的初始决定值，那么所有正确进程都应选择该值(行为统一 Integrity)。
3. 有效性(Validity)：最终达成一致的决定必须是其他进程提交值中的某一个。
节点的失效，节点之间网络通信受到干扰甚至阻断，以及分布式系统的运行速度的差异都会使得分布式系统难以达成一致。
著名的拜占庭将军问题专门研究了如何处理分布式系统中的错误节点（所谓容错）。Leslie Lamport（共识届的真大牛）在1982年发布的 The Byzantine Generals Problem 论文中提出的这个模型，可以算是分布式领域中最复杂、最严格的容错模型：系统不会对集群中的节点做任何的限制，错误节点可以做任何坏事，比如延迟响应、不进行响应，发送错误信息、发送随机消息、对不同节点发送不同决定，不同错误节点私下串通来搞事，大魔王横空出世控制多个节点实施有预谋的攻击等等。总之，现实中应该找不到比这个模型中更坏更恶劣的节点们了，他们的行为带有主观恶意且无法被预测。唯一可以保证的是每条消息的原始内容不会被篡改，消息的来源也都可以被判断出来的。
拜占庭将军问题是对分布式系统容错的最高要求，在这么一个极度悲观的场景下，这篇82年的论文提出的原始拜占庭容错算法（BFT）证明了只要系统中的坏节点占三分之一以下，系统还是能被抢救过来的。
之后学术界提出过各种BFT的算法，其中特别著名的是在1999年由 Miguel Castro 和 Barbara Liskov 提出的 PBFT，实用拜占庭容错算法。值得一提的是其中叫做Liskov的作者就是提出了 LSP (SOLID principles之一)的那个大牛“里氏”。
这个算法将原始 BFT 的算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。
PBFT 同样要求坏节点少于三分之一，并且额外要求网络封闭，即节点数目提前确定并且节点互相联通。算法主要依赖预准备（pre-prepare），准备（prepare）和提交（commit）这三个主要阶段。客户端需要等待 f+1 个从不同副本节点得到的相同响应，响应需要被正确签名，并且具有同样的时间戳和执行结果r。这样客户端才能把r作为正确的执行结果。因为失效的副本节点不超过 f 个，所以 f+1 个副本的一致响应必定能够保证结果是正确有效的。消息复杂度最少是 O(n^2)，确实性能提高了不少。
总的来说，BFT 模型非常严苛, 大多数实际的分布式系统并不需要考虑那么恶劣的环境。大牛 Lamport 另外提出过的 Poxas 共识就是一系列非拜占庭的完备容错协议，旨在让不存在恶意节点的分布式网络在出现节点错误时仍然能保持一致（这里假设了当一个节点出现故障时，它只是停止工作而不回复消息而已）。
而且相比公链的，BFT 更适合联盟链和私链。一方面虽然PBFT把消息传播的开销改善到了节点数量平方的规模，但是面对节点数量庞大的公链网络，依然会导致低效的共识执行，另一方面公链本身是个动态网络，新节点可以随意加入也增加了执行难度。而 Hashgraph 要做的事情就是要将 BFT 引入公有链网络中。
这里顺带提下 POW。POW 是目前最令人信服的用于公链的共识算法，被人诟病主要在于POW 为了使得主链不分叉，强制矿工来解决复杂且无意义的问题（该问题运算复杂但是验证容易），该手段消耗了极大的能源来做无效计算，且共识达成慢，交易吞吐量低下。POW 的算法思路是通过增加提案的成本来限制一段时间内整个网络出现提案的个数，并且放宽了对最终一致性的严格确认，只要求沿着最长链进行接续。所以 POW 下的系统只有概率意义上的最终确认，而无法确定某一时刻全网达到了共识。不过如果能搞出一个只做有效计算的 POW，应该是一个有前途的方向。以下是 POW 和 BFT 的对比：
再说回 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 可能可以用到公链？
之前说到 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）等保证共识的准确性和安全性。（ 在此不做具体论证和解释，请参考文末原文链接 ）
将上述各个操作结合在一起，便是完整的 Hashgraph 共识算法：
1. 每个节点都在试图随机找到其他节点把自己所知八卦给对方，
2. 每个节点同时也在接受其他节点更新过来的八卦，接受方节点需要额外进行一系列的运算，包括：
a. 接受和处理接收的八卦信息
b. 创建一个新的区块，并且指向自己的最后区块和八卦来源节点的最后区块
c. 对所有已知的区块分配创建轮次，并确定区块是否是该轮次内的见证人区块
d. 对所有已知的见证人区块进行选举投票，计算出是知名见证人
e. 通过知名见证人，确定所有区块的共识顺序
之后白皮书里有很大篇幅对这个共识算法下的系统可以达成拜占庭容错做了很多论证，这里就不再赘述。
总的来说，Hashgraph 的立意很高，想法也很新颖，从异步 BFT 共识的研究上开拓了区块链实现的视野和边疆。前文提到过 BFT 的模型设置过于悲观和严格，但是公链环境可能就是那么的恶劣，所以 Hashgraph 这样探索 BFT 应用到公链的方向和决心是值得肯定的，而且它确实成功的提出了可行的方案。
Hashgraph 和 Algorand 通过从不同角度改良了 BFT 应用的场景和条件来使得 BFT 共识可以被应用到公链系统中，可算用心良苦。它们一个是通过八卦传播哈希图以及基于哈希图做虚拟投票将传统共识所需的瞬时通信要求降到了最低，并且保证了本地计算的高效性，另一个通过安全地舒缩参与到 BFT 共识节点的数量来把问题划归到 BFT 擅长的领域，可谓异曲同工。相比较来说，Alogrand 的思路更加直观和简单，一般人直觉上可能都能想到这个办法（虽然无法给出完整的方案和数学论证），Hashgraph 的思路则更为曲折，引入了很多概念来解释算法，相对来说更晦涩些，虽然相当的理性。 另外 Hashgraph 这套算法和专利已经成功运用到了很多 2B 的系统中，但是异步共识是否可以真的在大型公链环境下应用成功，还是一个未知数。最新的 Hashgraph 公开分布式账本（所谓“公链”）的商业介绍上说他们会切换到 POS，就像上文提到过的那样。并且还支持 DOPS，可以让不跑节点的 coin 拥有者选择代理人节点，分享收益。整体来说 Hashgraph 的共识及结构证明逻辑严密，复杂度也较高 。目前所缺的主要是实际公链环境下的验证，如果它能够达到 POW 的安全性，将是非常了不起的。
附件1：Hashgraph 风险模型（点击放大）
