【区块链】Highway协议论文阅读笔记
区块链做了有一段时间了，最近在研究POA相关的内容，于是读了几篇论文找找灵感，这是其中的一篇。本文主要介绍了一种新协议Highway
原文：Kane D, Fackler A, Gągol A, Straszak D. Highway: Efficient consensus with flexible finality. arXiv preprint arXiv:2101.02159. 2021 Jan 6.
研究背景：
highway模型是在部分同步协议的基础上的改进。半同步拜占庭模型是介于同步拜占庭模型和异步拜占庭模型之间的一种折中方案，模型中有一个特殊的时间点（GST），也就是全局稳定时间。在GST之前，网络以异步状态运行，使得模型能够容忍网络波动；在GST之后，网络进入同步状态，网络中消息的传播延迟限制在某个值以内，这让网络有着更高的可靠性。
半同步模型的缺陷：
理论上如果恶意（不诚实）节点超过了节点总数的1/3，则系统将难以同时保持活性和终止性。而我们知道超过总数1/3的恶意节点同时进行恶意攻击，终结区块的确定则有可能受到影响。因此，半同步协议在进行安全性设计时往往会假设存在恶意行为的节点会超过总数的1/3。但实际上，由于协议的存在，为了获得正常的收益，恶意节点往往会诚实地遵守协议，所以系统的终止性还是比较有保障的。而这种为了确保系统安全的前提假设与实际情况相比则过于悲观，没有充分利用诚实节点占主导地位的常见情况。
问题的关键：
想要进行优化，则是一个在系统活性和终结性之间的权衡问题。想要有更高的终结性，就需要系统中有更多的诚实节点。据此，定义一个与终结性有关的参数：终结性阈值，即一个节点确认区块时至少需要收到其他节点发来的确认信息的个数；也是想要篡改区块需要的恶意节点数 。终结性阈值越高，则系统的终结性越高，也就越安全。而只要诚实节点数量超过终结性阈值，则最终的区块一定能被确定且不会被恶意节点篡改。文中将其形式化为终结性定理如下：
也就是说当一个区块B以置信度值t>f（f为终结性阈值）达到终结时，诚实节点不能让其他与B竞争的区块以置信度t达到终结。
在此前的模型中，终结阈值是所有节点达成共识后共同确定的一个值，也就是说所有节点的终结阈值都相等。
这就引出存在的问题：
- 最终性阈值需要所有节点达成共识，这增加了系统的部署难度和协议的复杂性。同时，如果有诚实节点设置了错误的最终性阈值，而整个系统无法达成共识时，会拖慢整个协议的进度
- 不同的节点可能来自不同国家、不同地区，网络延迟不同；不同的节点的用途可能也不同。也就是说，节点对安全性、网络延迟等方面的需求是差异化的。
为了解决这个问题，highway的核心思想就是运行节点根据需要自行设置最终性阈值。从而提高系统的灵活性。
Highway协议的实现：
（接下来是一大长串很干的定义环节，笔者暂时不知道如何写得更加生动，但已经尽力写得通俗易懂）
Highway协议中区块的结构和定义如下:
创世区块：G
除了G之外，每个区块 B 都包含一个指向其父区块 prev(B) 的引用,以及区块的内容(通常是一组交易)。
区块之间的父子关系通过在子区块中包含父区块的哈希值来实现,因此区块图中不会出现循环。
next(B) 表示所有以 B 为父区块的子区块集合。
区块的高度 H 是递归定义的,其中创世区块 G 的高度为 0,其他区块 B 的高度为 1 + H(prev(B))。
所有区块u会包含其发送者（创建者）的数字签名，我们将u的sealer记作S（u）
验证者之间交换信息以确认区块链的分支
重要的一种偏序关系：
验证者之间关注：单位u是否能引用其他单位u’；u的创建者在创建u时是否知道u’能引用，也就是u’能够证明u的身份；这种证明关系存在传递性，因此被定义为一种偏序关系记作u’<=u
定义集合D（u）为小于u的所有单元的集合
定义D（S），当S中所有元素u都满足D（u）
当所有u∈σ时，D（u）都含于σ时，我们称σ进入了协议状态
当S（u）=S（u’）且u与u’不可比（在定义的偏序关系上无关）时，称（u，u’）为一对等价关系
如果可以通过跟踪父区块引用从 B2 到达 B1,则称 B1 是 B2 的后代,记作 B2 ≤ B1。在这种情况下,有区块高度 H(B2) ≤ H(B1)。
Highway协议的框架是有向无环图，在这个框架中，验证者在广播出的消息中引用之前收到的其他验证者广播过来的消息。我们将这些在正常协议操作期间广播的消息称为 units,引用的消息称为 citations。更正式地说,每个 unit 包含以下数据：
发送者: unit 的发送者(创建者)的 ID。
引用: unit 创建者引用的其他 units 的集合。
（可选的）块: 如果 unit 包含一个块,则该块的信息。
在系统中，终结区块的确定遵循Ghost规则，这是Highway协议的重点之二
B树中的Ghost规则：
作者希望ghost规则能够反映验证者们的意愿，因此设计了映射：
这个映射用于表示节点V认为区块贝塔应该成为头部区块
Ghost的主要规则如图：
第一步：对于每个属于区块树贝塔的区块B，计算total(B)，也就是支持区块B作为头部区块的验证者个数
第二步：将B设置为创世区块，在以B为父块的所有区块的集合，next（B）中，选择total值最大的区块B’，并让它成为新的创世区块。若B不是贝塔的叶子节点则重复以上步骤
第三步，当B成为贝塔中的叶子节点时，结束第二步，输出B，以B为ghost规则的选举结果