什么是DAG我们为什么要使用它们

这是我们刚刚实现的一个基于STAG的框架。我们把它命名为Graphchain。接着我们会讨论设计选择和主要挑战，最后给出结论。

如果你对它的来源感兴趣，最初我和Xavier Boyen、Thomas Haines一起在2016年写了这篇论文——Graphchain：一种无区块链的可扩展去中心化账本。我们把它放到了ePrint上，在ERIM News上可能有一个更可读的版本。这篇论文在其他地方也有发表，但这两个地方可能最容易找到。

什么是DAG？

首先，DAG是什么含义？它指的是有向无环图。这是图论中的一个数学术语，通常包含由顶点和边组成的集合。边就是有序的顶点对，在有向图中通常用箭头表示。如果不能从一个顶点出发，沿着箭头返回一个顶点，那么图就是无环的。你也许意识到这不完全是一个数学术语。

下图是一个DAG的例子。箭头表示边，橙色的方框表示顶点。你可以通过检查发现图中没有环。你不能从其中一个橙色方框出发，沿着箭头返回一个橙色方框。这就是一个DAG。你也可以给这些DAG加上标记。

如果这样做，你将得到一个所谓的偏序集。在我们所做的工作中，谈及了很多关于偏序集。这里的思想是，如果你定义箭头指向一个比出发点更高的顶点从而得到一个偏序，那么你会很容易发现k是所有字母中最高的那一个。你也可以很快发现对于f和h，它们之间没有排序。我们所知道的就是f和h都高于d并且都低于i。

因此，它是一个偏序，不像我们所熟悉的另一种DAG，即区块链（下图），它是完全有序的。实际上，如果你开始思考如何处理这些孤块，以及会有多少孤块，你会发现这真的很有意思。我没有时间深入这个话题，但它真的很有意思，相信我。你会得到分叉，但是区块链本质上也是DAG，只是他们受到的限制更多。你无法拥有所有这些额外的偏序。

为什么我们需要DAG？

我们想要解决什么？这里我们试图解决的主要问题是去中心化和扩展性。区块链技术存在很多问题。这可能是最常被谈论的两个问题——还有一些其他问题，但我最感兴趣的两个问题是去中心化问题，这实际上归结为安全问题，以及可扩展性问题，这和可用性相关。扩展性问题仍然存在。这些问题是从哪里来的？这些问题似乎源于交易块的使用？可能是这样的。

我们整个项目的目标是：能否创建一个系统，让个体的努力得到回报？主要的问题，可能你已经意识到了，是矿池造成了一些问题。它们造成问题的原因是实际上它们的权力有点太大了——有些人认为它们权力过大。我倾向于这样理解。这不一定是坏事，有很多支持和反对它们的论据，我真的不想卷入这个话题，但是如果我们不需要它们不是更好吗？

我们能否消除加入矿池的动机？这是其中一个问题。此外，这么做的同时，是否也可以允许更快的交易处理。如果我们可以广播附加了工作量证明的交易，整理这些交易并用它们构建一个图，会怎么样呢？那么，我们还需要区块吗？至少，这是基于DAG的思想。

为什么这很重要？因为51%的诚实用户就足够了？不！这些我们早就知道了。那么，什么是去中心化呢？这是一个更加棘手的问题。它跟分布式设计的概念有点混淆，所以你可能会问去中心化究竟是什么含义。实际上我认为这个问题很难回答。有很多人思考过去中心化的真正含义，特别是在加密货币方面。大致上，我们希望全世界有许多运行相同系统的独立机器。如果有的话，就可以保证所有机器在计算上是等价的。就像我说的，这不是什么新鲜事物，人们已经谈论了一阵子了。

我们在谈的这些是什么？我们在谈论矿池和矿场。在“全世界运行相同系统的独立机器”上——实际上机器在运行一个矿池系统。并且，从计算上等价的机器的角度来说，我们有矿场。因此，本质上我们拥有一台能力非常强的机器。第二个问题我不认为是DAG必须处理的问题。这取决于功能。

不过，可扩展性也是一个主要问题。当我们谈论区块链时，为什么需要关心可扩展性？因为区块链是区块的线性集合，其中一笔交易引用下一笔交易。问题是，无论处理哪种类型的区块链，区块都包含一定数量的交易。有某个特定的时间段内可以接收交易。正如我们刚才所听到的，我们知道以太坊的限制，也知道比特币的限制。

问题的一部分是因为我们有区块，并且将它们和如此多的交易绑定在一起，所以我们可能会有两个不同的区块，其中一个包含交易T1到Tn，另一个包含交易T1到Tn‘。我们不知道它们是否相同——也许它们包含相同的交易列表，也许不是。

使用区块链，如果发生了分裂，我们就必须从中选择一条。这是一种分叉，对吧。因此，我们现在在等着看哪一条会被扩展，然后才能确定我们知晓哪些交易。如果我在T’中有一些交易，现在我将不得不等它们稍后在某个地方被包含进去。我们不能依赖所包含的交易。

当然，这只是通常情况。可以想象一下，由于一些反常的事件，你同时生产了大量的区块。使用区块链+，即以太坊和ghost协议的内容，你就拥有了可以被包含的叔块。这真是一个非常聪明的主意，但不会包含里面的交易。因此，你仍然可以奖励某人的努力，这是关于创建这个额外区块的一个非常明智的想法，因为人们应该因他们的努力而获得奖励。

本质上，整个想法是：我们是否也可以拥有这样的系统，你可以在其中创建一个新的区块，同时包含来自T和T‘的交易，也就是这些交易的合集？

这本质上就是Graphchain。我们拥有的东西是：如果没有区块会怎么样？交易只引用之前的交易，随便多少都可以。要发送交易，只需要简单地收集你认可的交易并引用它们，并在交易中附上一些工作量证明。

这是如何工作的？

我们可以定义一种抽象的工作量证明函数。这是一个相当抽象的想法，但在实践中通过哈希函数很容易实现。假定工作量证明函数S包含问题a和它的一个解b。如果b是a的解的话，我们就说S（a，b）为真。以区块链为例，解可能是一个nonce，你的a是指交易集合以及和之前区块之间的链接和所有其他数据。

我们想对工作量进行量化，从而我们可以说这个工作量证明函数的工作量=d。我们可以做到这一点，大多数时候都可以做到。如果你能部分地反转一个哈希函数，你可以说它一定花费了这么多的计算量，或者我们期望它花费了这么多的计算量。

因此，我们能够做到这一点，而且这已经发生了，因为矿池本质上是在做同样的事情。如果你为一个矿池工作，你不是先解出这个区块，然后把它交给他们，而是通过向他们展示你已经解决了一个更小范围的问题来证明你是在为他们工作。所以，如果是在比特币中，你可能想要找到低于某个阈值的数值。你向他们展示你已经找到了低于更高阈值的解——但至少它表明你正在为他们工作。

本质上，我们可以使用同样的方法。其目的是量化为解决某个问题所做的工作。抽象函数可以是任何我们可以量化的寻找问题解的难度。我们甚至不需要哈希函数，你可以想象用其他方法来实现这一点。我们再一次试图把它作为一个框架来设想。我们可以广播包含相关工作量的交易。这样做的目的是我们可以说：这里有一个区块，它的工作量为8。

因此，你再次拿走DAG，然后你可以想象一些数字，你可以说：好了，现在我们有了所有这些数字，这意味着什么呢？好问题。我们要做的是定义权重和高度这两个概念。这跟区块链非常相似，因为你有累积的工作量。一旦我们用工作量对图进行了标记，就可以用其他值来标记它了。

例如，对于权重，我们把这种累积工作量和交易及其所有后代相关联。高度是和交易及其所有祖先相关联的累积工作量。例如，你会发现，权重本质上就是把每一笔交易中的工作量证明的值相加。

所以，我们可以说（下图），交易的权重是61。为什么这么说？因为它让我们慢慢地建立起关于该交易在系统中的嵌套程度的概念。对于高度，你拥有了一个计算所有子交易的系统。有趣的是，交易本身也计算在内。所以，对于第二个交易（也在下图中，深红色），我们可以说它的高度为80。本质上，这只是两个例子，但我们想说的是，我们可以建立一个概念，即一个交易在图中的高度是基于它所包含的工作量证明的。

在基于DAG的系统中还需要做一件事。我们需要开始去除进一步下降的交易。我们必须这么做的原因是，如果给你一个新的图，因而你最近没有看到任何交易，并且你必须即刻计算出它们有多高，那么随着系统中交易数量的增加，它会很快变得非常消耗算力。你必须限制这一点，并最终开始摆脱进一步后退的交易。这是一件单独的事情。

这种基于DAG的设计增加了复杂性，这非常棘手。本质上，我们这么做的目的就是为了获得这种收敛性。如果交易可以引用任何其他先前的交易，那么通过什么来阻止用户在非常老的节点上创建新交易呢？

你需要提供激励。这也是框架的一部分。我们需要激励，希望用户从图的顶部构建新交易，所以奖励和高度的某种函数相关联。因此，为了简单起见，我只写了这些。然而，这并没有那么简单。比如说，如果这个函数是一个反函数，那么它将无法正常工作。但是你的确需要高度的某种函数来创造这种从前面开始工作的激励。这样做的关键是我们能够执行交易，并鼓励人们在交易的最前面开始工作。我们没有具体说明这一点，因为我们在尝试开发一个框架。

收敛的关键在于你最终得到了一个基本上位于列表顶部的绿色交易。它是收敛的交易，并且它下面的每个交易都是其祖先的一部分。而且，根据这个函数，每个人都想构建这个新的绿色交易——如果你想要构建一个新的交易，你将会引用这个顶部交易。就是这个思想。

不过，我们还要担心其他问题。我们得担心一些类似于双花的问题。让我们考虑一个双花的场景。你有一个这样的交易图（如下），突然这两个红色的交易在双花某笔钱。

好，那你怎么克服这个问题呢？比较一下这些交易。最终你必须比较这些并决定你想要继续使用哪一个。想象一下你有一个积极的对手的情况。我们可以将系统中的分裂概括为：如果对手实质上想要永久保持系统的分裂，会怎么样？基本上，你可以将其一般化为两个不能作为基础的图，因为你不能引用两个冲突的交易。他们是否需要双花并确保系统永不收敛？

对手现在的形势是他们必须基于这两个交易中的一个进行构建。他们还必须赶超网络中的其他节点，后者正试图在其中一个交易上进行构建。因此，设想一种情况，即诚实的节点，或者更确切地说，激励上兼容的节点首先创建了一个高度足够高的交易，就好像“这是新的真实的图”，然后对手必须在另一条链上创建一个新的交易。我们可以给它分配一些概率。然后这种情况不断地发生，以此类推，你最终会得到这样的概率（如下）。

你可以看到它很快变得非常小。但这只在对手没有过半数算力的情况下才有效。这是它的论据之一。

只是为了给你们一点Graphchain的概述：你按照自己的节奏创建交易，你会因个人努力而获得回报。受激励影响你更倾向于在顶部创建交易，并且我们允许多笔交易获得收敛性。工作量证明建立在更接近于实时的基础上，所以希望你拥有这些由个人创建的小得多的交易，并且工作量证明是由交易的个体建立的。最后，框架对于工作量证明函数，或者甚至在某种程度上对于奖励函数都是不可知的。

和现存DAG系统之间的差异

所以，你可能听说过其他的DAG系统。IOTA可能是最著名的，有一段时间它的市值很高。主要的区别是，它实际上没有任何激励措施——有一种挖矿方式，但实际上没有激励措施。他们目前正在使用协调员。但它们在框图和内容方面非常相似，它们的网站使用的框图跟我刚才展示的图很类似。你可以去查一下，其实挺有意思的。

其他的一些实现：Byteball——它们看起来有点类似，但在可信见证人这一点上有区别。Nano采用分布式权益证明协议，通过投票消除冲突。这两个系统都很酷，我建议你去研究研究。它们显然各有利弊。我们的框架试图变得更加不可知，更加去中心化。

结论

我不仅从事学术研究——我们有这篇论文——我也在挪威的NTNU全职开发这个框架并使之成为一种有效的加密货币。我大概六个月前在挪威国家电视台上做了一次演讲，之后我和这些TTO（技术转让办公室）的人员进行了交谈，现在我正在努力将其发展成一种有效的加密货币——为了好玩，结果发现真的很难。但我们还处于项目的初级阶段。我们最近刚刚融了一些资金，正在招聘开发人员。

总之，我们正在努力保持甚至扩展去中心化加密货币的思想，我们也希望有一个可扩展的系统。这是我们拥有的最重要的东西。也许在实用中可扩展性会受到某种程度的限制——但它很可能对很多用户都有吸引力。感谢你们的倾听。

问答

您能翻回到有平衡攻击的那页幻灯片吗？您在哪里展示了对手的概率？我想这里没有提到，您是假设诚实节点将会在某条链上进行构建，但实际上，诚实节点不知道哪一条是正确的。

你说得对，但事实是，对手必须同时在两条链上构建。如果对手知道诚实节点正在哪一条链上构建，它就可以在另一条上构建。但事实并非如此，所以对手必须同时在两条链上构建，因而也必须拆分它的算力。这就是它的工作原理。实际上我在这里漏掉了一个术语——通常情况下，诚实的参与者们有可能会同时创建一条链。我有意这样做是因为我以为没人会注意到。不过，最主要的一点是，对手必须将其算力拆分以便同时扩展两条链，因为它也不知道理性的参与者将会首先扩展哪条链。

但是，您仍然希望并行出块，因为这就是可扩展性的关键所在？然后在一条链上有诚实的区块，在另一个链上也有诚实的区块，它们的出块速率大致相同。只需要一点点哈希率来平衡两者。

我认为它们的速率大致相同，如果它们没有在这个术语所指的重要的点上往前推进的话。它仍然会很快变得非常小。显然，这取决于对手的算力。