解决区块链可扩展性的建议

原文：https://medium.com/hackernoon/a-proposal-to-solve-blockchain-scalability-4e808d2c767b

安德鲁·巴里瑟

我最近一直在努力思考区块链的可伸缩性(见我最近的文章https://hacker noon . com/摔跤-与-区块链-可伸缩性-a1295e47962f )。我有一个提案的大纲，我想在这里分享，以征求意见和反馈。目标不亚于解决区块链的可伸缩性问题。这是一个令人难以置信的大胆目标，但我希望你至少会审查我的建议。

问题是

要更深入地分析区块链可伸缩性背后的问题，请参阅上面链接中我的文章。简而言之，为了防止重复花费，每个验证者必须拥有所有交易的全局视图，以排除重复花费交易的存在。因为这可能发生在任何地方，任何街区，你必须到处寻找。因此，为了可靠地验证哪怕只是一笔交易，您必须在您的设备上保存完整的区块链。

出版证明几乎可以无限扩展

利用当前的区块链技术，我们已经拥有了一种称为发布证明的能力。我可以获取 2^N 的数据片段，对它们进行哈希运算，然后构建一个深度为 n 的 Merkle 树。我可以获取该树的 Merkle 根，并将其发布在一个比特币区块中。然后，对于原始 Merkle 树中的任何单个数据片段，我可以提供到 Merkle 根的 Merkle 路径(一系列邻居散列，表明我的叶散列是 Merkle 树的成员)。这样做的效果是，我可以证明，对于我在 2^N 的任何一条数据，它都是在 Merkle Root 所在的比特币区块发布的。

这个方案几乎可以无限扩展，因为块中实际存储的是一个简洁的 Merkle 根散列。这只是一个短字符串。对于长度为 N 的树，需要 log(N)空间和计算来证明成员关系；这很容易衡量。我可以证明今天每个比特币区块中发布了数十亿或数万亿个数据点。

事实证明，出版规模这么好，应该表明我们可以做得比目前的技术水平更好。但是，正如我们将看到的，它本身不足以创建一个可伸缩的区块链。这也不是一个新的想法；它在社区里已经存在多年了。

抽象 Merkle 树中带有地址的令牌

在我提出的区块链设计中，区块是使用工作证明来生产的，就像今天比特币所做的那样。然而，每个块包含 1 个 Merkle 根字符串。这个 Merkle 根代表一棵实际上不存在于区块链的 Merkle 树。Merkle 根仅仅作为一个锚；无论树中有什么，都可能是巨大的，可以使用出版证明来证明时间戳。

使用这个抽象的 Merkle 树，我们可以用那棵树的叶子创建一个地址空间。每一片叶子对应一些二进制数，这些二进制数代表从 Merkle 根到叶子的左右导航。简而言之，每片叶子可以有一个唯一的数字地址。

在我的方案中，每片叶子都对应着区块链中的一个不同的标记。为了发布该令牌的事务，有必要(但并不充分)提供源自 Merkle 树中该叶的事务的发布证明。证明发布的 Merkle 路径也将证明该事务源自 Merkle Leaf 的事实。源自不同叶(而不是对应于该令牌的叶)的原本有效的事务是无效的。

出版证明并不能防止双重花费

以上给了我们一定的能力，但并不能防止双重花费。它的一个关键特性是，它使得不必在一个块中的其他地方寻找以排除双重花费(在同一个块中，并且只针对所讨论的令牌)。由于交易必须来自与失效令牌相对应的 Merkle 叶，所以来自任何其他叶的双重失效交易的存在不是问题。只有一个地方可以找。

然而，我们还没有解决双重花费的问题。假设我在第 25 块给你发了一个令牌。我在块 25 中向您展示了正确签名的交易的发布证明。已经核实了。我还向您展示了我在第 10 块中获得令牌的交易的发布证明。但是我还不能证明第 11-24 块的任何交易都没有发布。因此，虽然块 10 和 25 中的交易是有效的，并且在块 10 和 25 中不存在其他有效的交易，但我仍然担心 11–24 中的重复花费。

从理论上讲，您可以拥有第 11–24 块无效交易的发布证明。但这并不是制度的保证。矿工可以在你应该有空交易的地方插入垃圾。我在之前的文章中称之为“胡言乱语攻击”。Merkle 树路线分解，以证明第 11-24 块没有交易。

我们需要缺席的证明

正如我在上一篇文章中所思考的，需要有一些方案，在这些方案中，我获取一组字符串 S，并对这些字符串 P 产生一个简洁的承诺，这样，对于不在 S 中的任何其他字符串 X ，我可以证明 X 不是 S 的成员，仅仅通过作用于 X 和 P 。换句话说，我需要在不检查整个集合的情况下证明一个元素不是集合的成员，而仅仅是对集合的一个简洁的(非交互的)承诺。

密码累加器

经过一些研究之后，事实证明这种功能确实存在。加密累加器提供了一种无需检查整个集合就能有效测试元素对集合的成员资格的方法。关键的是，还有支持测试的变种非会员。

下面是动态通用密码累加器功能的简要概述。为了证明成员资格，我从某个值 G 开始。对于集合 S 中的每个成员 X，我作用于 G 以产生新的见证值。可以通过我在这里不打算解释的机制来探测见证值，以证明 X 是集合 S 的成员，而不必携带所有的 S。非会员证明也有类似的版本。据我所知，作用于见证值的转换是可公开验证的，因此不需要相信非成员证明的真实性。

像 Merkle 根一样，加密累加器是一个简洁的字符串，可用于证明成员资格或非成员资格。我们将在每个块中包含累加器见证语句。因为加密累加器是“动态”的，即集合 S 的有效累加器可以针对 S 中的插入和删除进行更新，所以我们可以在每个块中包括到该点为止的整个区块链历史的全局累加器见证。

这一切是如何运作的

我的计划是这样运作的。

曾经:

像现在的 lite 比特币钱包一样，使用工作证明来验证块头。
每个块都有一个从前一个块的见证派生的累加器见证，以及一个相应的证明。验证该证明，以确保任何给定块的累加器对应于整个区块链历史。

发送交易时:

您需要发送与该令牌相关的所有交易的完整出版证明历史。因此，如果事务涉及块 25，并且其输入来自块 10，则显示块 10 和 25 的证据。这比今天的比特币交易数据还要多，但谢天谢地，它不必存储在区块链上。
它可以如下进行: -令牌 A 在块 0 处被创建，并且被一个地址所拥有的概念上的一切所拥有。这是不言自明的。 -令牌 A 从源地址发送到我在块 10 的地址。这是有出版证明的。关键是发送者做了第二件事。他揭示了对应于他的地址的隐藏签名值，并将其包含在块 10 的密码累加器中。

为了验证上述交易，在块 10，我被给予有效(签名的)交易的发布证明。这包括一个到 Merkle 根的 Merkle 路径，我知道它是正确的(通过验证所有的块头)。我是也是，因为加密累加器中包含了隐藏的签名值。这个值可以是拥有地址的隐藏前身(像一个私钥，或者许多私钥中的一个)，这样一旦我知道它，我就知道它唯一地对应于发送地址。我验证这个值是加密累加器的成员。同时，我验证了不是块 9 的加密累加器的值。由于块 9 继承了来自所有先前块的所有签名值，这具有证明该签名值存在于块 10 中并且之前从未被泄露的效果。交易仅在以下情况下有效

a)附有有效的出版证明

b)伴随着一个显示的、先前隐藏的值，该值链接到他的地址。该值是下一个块的密码累加器的一部分，但不是任何其他块的累加器的部分。这是通过证明前一个块的累加器的非成员资格，以及通过证明所有加密累加器跨块的连续继承来实现的。

必须对该代币在整个历史中的所有交易重复上述步骤 A)和 B ),以证明从未发生过重复消费。因此，仅仅证明一个交易是不够的，我们必须证明那个交易的前身，以及那个交易的前身，直到创世纪。这是可行的，因为所有的块报头都被验证，并且这些是客户端设备可以执行的相对较短的证明。

请注意，显示的、隐藏的签名值的目的是创建一个可证明的测试，双花费尝试将无法击败。这个值在使用之前必须是隐藏的，并且确定性地指向消费公共地址。对于未来的令牌接收者来说，很明显，对于这个地址-令牌对，不可能存在其他签名值，因此当他们排除其在块的累加器中的成员资格时，他们已经排除了来自该令牌的那个地址的所有开销。

我相信以上解决了双重花费的问题，而不需要在全局区块链中包含大量数据。众所周知，发布证明具有很好的伸缩性，它与加密累加器中简洁的非成员证明相结合。每个块中的数据量是最小的。

这种设计将计算的负担转移给了个人所有者和接收者。他们可以证明他们的硬币的有效性，而不用证明所有硬币的有效性。同样，存在双重花费的出版物证明也不是问题；它们将无法通过加密累加器测试。

一些问题

我想在这里列举一些问题和差距。

我主要担心的是，通过加密累加器的简洁、动态、非成员证明是非常深奥的数学。我希望有更多的证据证明他们像广告宣传的那样工作，并且我已经恰当地代表了他们。一个真正的密码学家应该仔细阅读我的解释。这些是整个解决方案的基础。
我的方案涉及不可替代的代币，而不是比特币这样的可替代单位。我不认为这是一个大问题；您可以从一组令牌交换中构造细粒度的事务。它不是最佳的。如果可以使用类似的想法构建一个可替换的版本，我不会感到惊讶。
挖掘者必须将所有这些数据聚集到加密累加器和 Merkle 树中，以供发布。采矿者必须将信息返回给交易的发布者，以便他们有足够的信息来提供交易证明。这种来回引入了比特币中不存在的复杂性，在比特币中，交易发布只是单向的。
更糟糕的是，一个恶意的挖掘者可能会获取公开的、隐藏的值作为累加器的一部分，并包含它，而不包含 Merkle 树中相应的叶子。这将导致这样一种情况:看起来我是在重复花钱，而实际上我并没有。这可以通过几种途径解决；例如，隐藏的签名可以在发布证明已经成功之后的块被揭示，从而消除了这种风险。这是可以接受的，因为孤立的发布校样没有成本。因此，我相信这个问题是有解决方法的。
这个方案给代币所有者增加了更大的负担。他们必须存储更多的数据并传递下去。如果交易证明丢失，令牌将被卡住，就像今天丢失的比特币私钥一样。可以说，收件人需要更多的计算来确认交易。我相信这是值得在区块链可扩展性上进行权衡的。

如果我的提议可行，它将极大地提高区块链的可伸缩性。唯一真正的限制是在区块间隔期间与矿工的连通性。矿工们可以把尽可能多的东西塞进 Merkle 树和密码累加器中，而不会增加块大小的负担。

我有点担心这个大胆的提议，我已经错过了一些关键的缺陷。我也承认很多部分没有很好的定义；这部分是因为我还在消化这些想法。我邀请对这个提议进行最大限度的审查，特别是在分散的区块链的敌对环境中，在简洁的密码累加器中使用非成员证明的可行性。

请随时在 Twitter 上向我寻求想法、反馈或评论。

推特:https://twitter.com/abarisser

1 jzbgmjzxvg 1 u 4 wzwafzkeghcpf G4 yswhe