技术分享 | 安全并且公平的Block Dag排序

前言

在之前的文章中，我们看到了在DAG拓扑结构中可能出现的问题是定义区块和转账的顺序。在这篇文章中，我们描述了Taraxa的机制，该机制不仅可以确保在Block DAG中进行排序，而且可以确保排序的过程是安全和公平。

为什么排序具有挑战性？

在Block DAG中进行排序有什么困难？

如果只是查看任何DAG数据结构，我们就只能建立 部分排序 ，这意味着我们只能确定某些块之间的排序关系，而不能确定所有块之间的排序关系。这是一个例子。

在上图中，我们可以100％确定地说在排序中蓝色块肯定在绿色和橙色块之前出现。为什么？由于绿色和橙色块指向蓝色块，这意味着在创建橙色和绿色块时，蓝色块已经存在，否则橙色和绿色块不知道他们会指向它。

但是，怎么才能知道绿色和橙色块之间的排序关系呢？这个问题没有确定的答案，答案具体取决于使用的排序算法的类型，对于不同的算法，顺序可能会完全不同。

在排序过程中，我们不仅要保留一个自由度，而且还需要做出许多选择以确保排序算法既公平又安全，因为需要确保不会出现不诚实地参与者对大多数诚实的网络参与者给予偏见或进行攻击。

现在来看一下Taraxa设计的Block DAG的排序算法，看看我们如何解决这些问题。

人气比赛

在Taraxa的Block DAG拓扑结构中，每个区块都包括向后的指针，这些指针不仅指向单个父块（如在单链拓扑中），而且还指向区块块提议者已经看到并相信的DAG边界（边缘）上的所有块。这里有很多概念，让我们一一解开。

什么是边界？ 在Block DAG（或任何DAG数据结构）中，边界指代的是一组最新的，没有其他区块指向它们的区块。

在上图中，蓝色块是“边界”区块，而其余块都不是。 边界区块链很有趣因为这些区块是所有区块的基础，其他由区块提议者（类比区块创建者）创建的区块从排序上来说都在他们后面。从某种角度上说，下一个新区块一定会引用这些区块。但是，由于每个节点遇到的网络传播延迟不同，在遇到任何给定区块时都会看到完全不同的情况，因此并非每个节点都会看到相同的边界（或相同的Block DAG）。因此，区块提议者在任何给定的时刻都可能基于不同的边界来构建其区块。

什么是指针或父区块？ 指针在图中用箭头表示，它是嵌入在一个区块内的数据，该数据将此区块“指向”或引用了另一个区块。在Taraxa的DAG区块结构中，指针会指向父块集。父块是被指针指向的区块，因此可以理解为他们之前区块的父亲。

在上图中，我们看到蓝色区块具有两个指针，指向两个由绿色块表示的父区块。 这意味着在提议者创建蓝色区块时，提议者知道Block DAG边界上的两（2）个区块，并认为这两个区块有效，因此将创建的蓝色块指向他们两个。

这些指针将区块连接起来的过程实际上是一次流行竞赛-简单来说比的是哪个区块会被最多区块所指向并且被认为是有效的。 此外，如果指向某个特定区块的区块本身是“受欢迎”的（意味着许多其他区块指向它们），那么“受欢迎度”也将延续到该特定区块（父块）。

现在，我们来衡量每个区块的受欢迎程度。

权重-受欢迎的分数

为了衡量每个街区的受欢迎程度，我们采用了Zohar和Sompolinsky提出的GHOST协议。 GHOST有助于根据嵌入在Block DAG中的指针计算每个块的权重（每个块的“受欢迎程度”）。

什么是“权重”？ 如果将Block DAG侧向旋转，则可以认为每个子区块及其后代都与父代区块隔离开了，因此GHOST下任何块的权重就是该区块及其所有后代的权重之和。

权重代表了所有试图在该区块上逐步建立其他区块的集体努力，即使这种努力没有得到协调并分散到多个后代中。

GHOST协议非常简单，

>每个块本身自然具有1的权重

>每个块的重量等于其自身的重量（1）加上指向它的所有块的重量

>从DAG块的边界开始，然后向后测量

这是一个例子。

从边界区块开始，我们可以为每个区块分配权重。 蓝色区块位于DAG的边界，没有区块指向它，因此它的权重为1。绿色区块只有一个指向它的区块（蓝色的），因此我们添加了绿色区块自己的区块权重（1）加上指向它的区块的权重（1），我们得到2，这是绿色区块的新权重。 再往前走，橙色区块指向3个方块，因此它的权重是三个方块的权重加上自己的权重1：5 + 20 + 12 + 1 = 38的总和。

看起来不错，为啥我们现在不能按权重排序？好吧，不完全可以。这种简单的策略存在一些非常细微的问题，让我们进一步研究它们。

混淆顺序的方法

让我们看一个简单的例子来理解为什么仅仅使用权重值作为排序机制的逻辑基础是不够的。

在上图中，我们从场景(a)开始。

(a)我们看到有两个橙色的区块，它们的权重值都是1，所以它们的顺序是模糊的。

(b)增加了另一个区块，它指向前面的两个区块，但是现在它们的权重值都是2，而且仍然有不明确的顺序。

(c)增加了几个区块，橙色区块的问题并没有消失，它们的重量仍然相同。不仅如此现在的情况更糟，新的问题是黄色区块也有模糊的排序。

在上面的例子中，我们假设每个人都是诚实的——但我们仍然会遇到问题。如果你引入了一个恶意的玩家会怎样?那个玩家可以在区块DAG结构上主动地混淆排序。让我们看看下面的例子。

在这个例子中，我们从(b)开始。

(b)我们有2个排序不明确的橙色区块。

(d)另一个区块出现并解决了这个问题，我们现在有了明确的排序。万岁!

(e)但好景不长…一个恶意的玩家正在积极寻求保持模糊的排序，并创建了一个区块(红色)，这增加了边界区块，算上这个区块的权重就又回到了我们之前的问题，两个橙色的区块再次没有很好的排序。

这种攻击的另一个含义是， 恶意的玩家不仅可以保持模糊的排序，还可以通过增加区块前后切换排序，使网络处于持续的混乱状态。

虽然这些都是非常简单的例子，但是这样的问题可能会在更大的范围内发生，也就是说整个区块集群都处于不确定的排序状态中。

那么我们如何解决这个问题呢?我们接下来会介绍锚链和幽灵指针的概念。

锚链-最受欢迎的途径

计算权重之后的下一步是确定Block DAG中的锚链。如果权重是每个区块的受欢迎度评分，那么锚链是通过Block DAG中的最受欢迎的路径。在穿越(步行)路径时所观察到的区块，也可以通过网络得到广泛的观察(非常普遍)。

如何构建锚链?简单!只要选择一个起始点—或者在Taraxa的例子中，起始点是前一个具有实时最终性的区块(我们关于实时最终性的文章即将发布)—然后向前走到它的子区块中，每一步都选择权重最高的区块。这里有一个例子,

在上图中，从G区块开始向前走，有3个有重量的区块可供选择(381,765,381)，其中最重的区块是765。按照这样的逻辑继续朝这个方向走，从G区块开始直到到达终点的路径，就是构建出的锚链(绿色)。

这就是锚链生成的方法，它将Block DAG“锚定”到一个路径中，我们现在可以根据这个路径构建一个排序算法。

虽然这种计算锚链的方法解决了每个被指向的块具有相同的重量的问题，但是引出了另外一个问题，因为攻击者仍然可以不断地改变锚链(不收敛得很快)。 所以我们引入幽灵指针，以帮助网络更快地收敛到一个固定的锚链上，从而实现确定性排序。

并不是所有的指针都是一样的

为了进一步防止网络陷入无序状态，我们引入了一个称为 幽灵指针 的特殊指针。其基本思想是在创建每个区块时，它指向边界上所有它看到并已验证为合法的区块，但是这样的区块是特殊的。

特殊区块是锚链的终止区块，每个新加入的区块除了需要承认Block DAG的边界上存在其他合法区块外，还将指向这个终止区块的幽灵指针。 这里一个重要的变化是区块权重的计算中只考虑幽灵指针指向的区块，而不考虑其他指针指向的区块。

父块变成了只有特殊的幽灵指针指向它的区块。 在Taraxa Block DAG结构中，每一个区块只会指向一个父区块。其他的区块只是简单地观察区块树的其他区块（原文为树叶可以理解为区块），或者“祖先”——在以太坊，它们被称为“叔叔”或“ommers”。这可以在前面提到，也可以非常明确地说明一个区块可以有多少个父区块存在。

这解决了一个基本问题，即在DAG图所代表的隐式投票过程中，如何保证边界上的所有区块不是以模棱两可的形式呈现。

让我们来快速看一个例子，

>粗箭头是幽灵指针(计算重量)

>细点箭头是确认指针(没有权重)

(a)两个区块(1.1和1.2)指向第一个创世区块(0)，粗线是幽灵指针，因为只有一个父区块存在而这两个区块都指向它。现在的顺序是模糊的，但是我们可以使用最低的哈希进行比较，假设(1.1)获胜，并被认为是未来区块的幽灵指针的候选。

(b)增加了3个区块，但因为网络延迟导致，不是所有这些区块都在同一时间看到每一个新出的区块，也就是说某些节点可以更快地看到某些区块。例如，更近的物理距离导致的更少的网络跃点会加快节点看到区块的速度。区块(2.1)和区块(2.2)都见过前面的两个区块(1.1和1.2)，所以它们都将幽灵指针指向这两个区块并诚实地将(1.1)标识为锚链上的终止区块。但是，(2.3)没有看到(1.1)，所以它只能使用幽灵指针指向(1.2)而无法做其他事情。请注意，根据我们的规则，区块的权重已经更新，但是只计算了使用幽灵指针指向它的子块的部分。

(c)下一层的区块出现了，第(3.1)区块同时看到了(2.1)和(2.2)区块，第(3.2)区块同时看到了(2.1)和(2.3)区块，第(3.3)区块同时看到了(2.1、2.2和2.3)区块。在发布时每个区块选择它们所看到的锚链上的终止区块，并将它的幽灵指针指向它，然后继续。

幽灵指针与锚链一起，有助于迫使网络收敛到锚链上，稳定整体的排序。 接下来，我们将描述如何最终基于锚链对区块进行排序。

通过锚链排序

使用幽灵指针，让我们重新计算前面的Block DAG示例中的权重。请再次注意，只有使用幽灵指针指向的区块才能将其权重计算到父块中。

一旦锚链被绘制出来，我们就在锚链上的每个区块(锚块)周围构造 epoch 。epoch就是让锚块可以观察到的区块数量，或者是锚块直接或间接指向的块。把他们想成是超级受欢迎的锚块的朋友。

在上图中，我们使用红色虚线绘制每个锚块epoch。不幸的是，第一个重量为25的锚块只有他自己是epoch。下一个重量为21的锚块具有epoc，包括它自己和它可以观察到的另外两个重量为1的块。第三个锚块的重量为18，只能观察到一个锚块。下一个块的重量为17，它的epoch为3，其中包括一个块的重量为1是它能够直接观察到，另一个块的重量为2是它间接观察到的。通过这种方法我们继续区分直到每个锚块的epoch都被绘制出来。

现在我们准备好对区块进行排序了! 区块首先按epoch的顺序从最古老到最新(从左到右)。在每个epoch中，通过查看哪个区块指向哪个区块，并使用权重值来决定哪个区块先出现。或者如果这种方式失败，则使用区块hash作为与锚块相同距离的区块的判断方式。

看epoch图,G是第一个(1)。下一个epoch中只有一个区块,所以这个权重25的区块是第二区块(2)。移动到下一个epoch,两个权重值为1的区块在权重21锚块之前(因为它们是指向权重21的区块),比较这两个区块的方式是比较谁的hash值更低来确定(3)和(4)，然后，第5个区块(5)是权重值21的区块。我们一直进行下去直到所有epoch内的所有区块都被排序。

如下所示，每个区块中的数字表示顺序，而不是权重。

我们终于搞定了！

但我们真的完成了吗?那些没有被加入排序的区块呢?

在Block DAG结构边界附近总是有一些区块不属于锚链epoch的一部分。但是不要担心，随着更多的区块被添加到边界，它们最终会被包括在内。

难道锚链(以及因此产生的顺序)不会随着时间而改变吗?

是的! 在Block DAG结构内存在重新排序的风险。这种风险随时间呈指数下降，但从未真正消除，这就是为什么Taraxa需要实现了一个实时最终性过程(文章即将发布)。在Block DAG结构中引入了真正的实时最终性，并且没有重新排序的风险，这是在网络中构建DApps的基础。

请继续关注。