拜占庭容错证明

本节首先给出一些定义，方便后面的证明，这些定义从”强看见”（Strongly Seeing）引理到拜占庭容错定理一步一步建立。

这些证明中要求：

• 节点数n>1，超过2n/3的节点是诚实的，少于n/3是不诚实的；
• 假设数字签名和加密hash是安全的：签名不能被假冒，签名消息不能被篡改，hash永远没有冲突；
• gossip协议确保Alice向Bob发送全部她知道的事件，Bob只接受包含有效签名和hash的事件；
• 全网节点完全异步；
• 对于任何诚实的节点，Alice最终会同步Bob，如果Alice重复向Bob发送消息， 最终总会发送成功（注：Alice和Bob之间可能之前是通信问题导致发送不成功，但是通过gossip广播之中消息会传到Bob ）；
• 不假设网络的可靠性，不设置消息传播超时周期；
• 甚至攻击者完全控制了网络，任意延时和删除消息，但是诚实节点之间如果反复发送的消息，最终必须能够到达对方。

定义5.1

事件x是事件y的祖先，是说：x是y，或x是y的父事件，或x是y的父事件的父事件，以此类推。定义x是y的自我祖先也是同理。（注：表示y包含了x中所有信息）

定义5.2

事件x的创建轮次（简称轮次）定义为r+i，是指：r是事件x的父事件的较大的轮次（注：事件都有2个父事件），如果没有父事件，则r=1；如果事件x在轮次r中可以”强看见”超过2n/3见证人，则i=1，否则r=0；（注：表示r轮上的部分的见证人完成在大部分节点上的传播）

定义5.3

事件x的接收轮次，是指：满足所有独特的知名见证人都是事件x的后裔的第一个轮次。（注：说明事件x被确认可排序）

定义5.4

事件(x, y)是一个分叉，是指：(x, y)具有相同的创建者，但都不是对方的自我祖先。

定义5.5

一个诚实的节点会不断无限尝试和其他节点进行同步数据，并在每次收到一个有效同步后，创建后一个事件，事件中包含最新的自我父事件和父事件。

定义5.6

事件x可以“看见”事件y，是指：y是x的祖先，并且x的祖先中不包含y的创建者产生的分叉事件（注：y的创建者即使有分叉事件， 只要都不在x的祖先中即可）

定义5.7

事件x可以“强看见”事件y，是指：事件x可以“看见”事件y，并且存在一个事件集合，这个集合中的事件需要分布在超过2n/3节点上，可以被事件x看见，并且集合中的所有事件可以看见事件y。（注：表示y已经传播到大部分节点，并且x汇总了这些大部分节点的信息）

定义5.8

见证人：某一轮次中某个节点创建的第一个事件。（注：一个节点在同一轮次可以创建多个事件）。

定义5.9

知名见证人：首先是见证人，并且是被全网选举为知名的。选举算法如下：一般情况下，全网认为大部分节点如果可以在下一轮次看见这个见证人，则认为该见证人是知名的（注：表示这个见证人已经传播到大部分节点上）。独特的知名见证人：是一组知名见证人集合，在同一轮次中，集合中没有一个知名见证人是由同一个创建者创建。在没有分叉的情况下，每个知名见证人也是一位独特的知名见证人。

定义5.10

hashgraph A和B对于包含在这两个hashgraph 中的任何事件x都是一致的，它们对事件x都包含相同的祖先集，并且在这些祖先之间具有相同的父边和自我父边。

引理5.11

所有节点具有一致的hashgraph。

证明：如果两个节点的hashgraph都包含事件x，并且事件x相同的两个hash。 节点在同步事件时，只有该节点已经拥有该事件的2个父事件时才会接受该事件，所以这两个hashgraph都必须包含事件x的父事件。 加密哈希被认为是安全的，因此父事件肯定是相同的。 通过归纳，x的所有祖先必须是相同的。 因此这两个哈希图是一致的。

引理5.12（强看见引理）

如果事件(x, y)是一个分叉，并且在hashgraphA中事件z可以强看见事件x，那么在其他的和A保持一致的hashgraph中，任何事件不可能强看见事件y。

证明： 用反证法。假设B中的事件w可以强看见事件y，根据强看见的定义，A中必然存在一个事件集合SA可以被事件z看见，并且SA都可以看见x，B中必然存在事件集合SB可以被事件w看见，并且SB都可以看见y。SA中的事件是被超过2/3的节点创建的，SB也是，因此，这两个集合中的1/3节点必然重合。假设少于1/3的节点是攻击者（不诚实），那么至少有1个诚实节点同时创建了SA和SB中的事件。假设m是这样的一个节点，m节点上的事件qA∈SA，事件qB∈SB，因为m是诚实的，qA和qB不可能是分叉的，所以这些事件关系是自我祖先的关系。不失一般性，假设qA是qB的自我祖先。hashgraphA和B是一致的，qB在B中，所以他的祖先qA也肯定在B中，那么，根据x是qA的祖先，也自然就是qB的祖先， 但y也是qB的祖先，因此，x，y都是qB的祖先，并且是分叉的，所以qB不能看见x，y（注：根据”看见”的定义5.6，qB的祖先不能包含x或y的创建者的分叉事件），这和假设qB可以看见y是矛盾的，得证。

（注：通俗一点讲，z可以强看见x，表示x已经被全网超过2/3的节点认可，不可能还有超过2/3的节点认可分叉事件y）

在任何时刻所有节点具有一致的hashgraph，如果2个hashgraph是一致的，都包含事件x，那么都将包含一致的事件x的祖先。这将导致他们认同事件x的每一个属性：纯粹是其祖先的一些功能。包括他们的轮次，是否是见证人，事件是否可见，哪些事件是强看见，每次选举中他们的预期投票结果（对于见证人来说），对于大部分属性直接由定义决定，下面的引理证明了在创建新的轮次时也是正确的。

引理5.13

如果hashgraphA和B是一致的，并都包含事件x，那么两者将会分配相同的创建轮次值给事件x。

证明：见原文。

不同的节点可能有略微不同的hashgraph，因此可能会有略微不同的选举。 但是，所有的投票都是一致的。 如果一个hashgraph显示Alice在给定选举的给定轮次中给Bob发送给定投票，则任何一致的hashgraph必须显示相同的投票，或者都不投票。 两个一致的hashgraph不可能在该轮中显示两个不同的投票。

引理5.14

如果hashgraphA和B是一致的，在A上运行的选举算法显示：节点m0上属于r轮的见证人发送一个投票vA给节点m1在r+1轮上创建的见证人，在B上运行的同样算法也会显示：一个节点m0上的r轮的见证人发送了一个投票vB给节点m1的r+1轮的见证人，而且vA=vB。

证明：算法设定的规则是：只有事件y可以强看见事件x时，x才可以先y发送投票。因为上面证明了对于一致的hahgraph不能同时强看见2个分叉事件（引理5.12），因此2个投票只能来自同一个事件。而一个事件的投票是根据祖先事件纯算法计算出来的，所以投票肯定相等。

拜占庭协议的YES / NO问题是通过多轮虚拟投票达成的。 一个给定的节点会在正常轮次 r（不是硬币投票轮次）结束他们的选举计算：如果某些属于r+1轮次的事件强看见超过2n/3的节点在r轮次的投票（严格说是采取了相同的行动，例如都没投票）。 如果发生这种情况，那么每个活跃节点将在r或r+1轮结束选举（或r+2，如果r+1是硬币轮），并且将以相同方式决定（都投或都不投）。 换句话说，下面的引理证明，如果任何人决定YES/NO的问题，那么每个人在此后几乎会立即达到拜占庭共识。

引理5.15

如果hashgraphA和B是一致的，A在r轮次完成了对结果v进行拜占庭协议选举的决定，并且B在r轮次之前没有完成决定，那么B会在r+2轮次之前决定。

证明：见原文

理论5.16

对于单一的YES/NO的问题，共识最终达成一致的概率是1。

在hashgraph的共识算法中，拜占庭协议用来决定每个见证人是否是知名或者不是。每一轮都会确保至少一个见证人成为知名见证人。

引理5.17

在任何hahsgraph的任何轮次r中，并在r+3轮次中至少有一个事件，在r轮中至少有一个见证人将被共识算法决定为知名见证人，并且这个决定将由每个r + 3轮或更早的见证人完成。

引理5.18

如果hashgraphA不包含事件x，但包含x的所有父事件，并且hashgraphB是向A添加事件x的结果，并且x是在r轮次中创建的见证人，并且A在r轮次中至少有一个见证人已经被决定是否为知名的，那么在B中事件x将被定为“不知名”。

定理5.19（拜占庭容错定理）

由诚实节点创建的每个事件x将会被最终分配到一个共识的在事件全局排序中的一个位置，他的概率是1.

证明：所有诚实的节点最终会学习到事件x，前提是即使攻击者控制全网，诚实节点之间的数据最终还是可以到达对方。因此，最终存在一个轮次是的所有独特知名见证人都是事件x的后裔，并在那个轮次或更早的轮次：r轮次，所有知名见证人是事件x的后裔。r轮次也叫做事件x的接收轮次，事件x的共识时间戳是那些节点首次收到事件x的中间时间，共识位置也被固定下来。并且不可能存在一个事件y在事件x的共识次序之前到来。因为想要在共识历史之前到来，事件y的接收轮次必须小于等于r，意味着是r轮次中的所有知名见证人必须收到事件y，但是一旦某个轮次的知名见证人被确定后，他们所有的祖先都将被确定，没有办法再后续hashgraph生长中加入祖先，也不能增加知名见证人。如果在将来发现任何新的r轮次的见证人，将不可能是r+1轮次见证人（超过2n/3）的祖先,该见证人必然成为非知名见证人。因此，一旦一个事件确定了在总排序中的位置，将永远无法更改，不能被插入，也不能被替换。