区块链扩容的关键：欺诈和数据可用性证明

区块链扩容的关键欺诈和数据可用性证明，在这篇论文中，作者们提出、实施并评估了一个完整的欺诈和数据可用性证明方案，并且根据附加的假设：网络中至少有一个诚实全节点在最大网络延迟内传播欺诈证明，并且网络中具有最小数量的轻客户端来共同恢复区块，它使得轻客户端几乎可以得到全节点级别的安全保障。

(图片来自：Institut Friedland)

1 伦敦大学学院

{m.albassam,[email protected]

2 以太坊研究组织

[email protected]

摘要：轻客户端，也被我们称为简单支付验证(SPV)客户端，这类节点只需下载区块链中一小部分的数据，并使用间接的手段来验证给定区块链是有效的。通常，它们假设区块链共识算法所支持的链只包含有效区，并且大多数区块生产者都是诚实的，而不是去验证区块数据。通过降低这类客户端来接收由全节点生成的，表明违反协议规则的欺诈证明，并将其和概率抽样技术相结合，以验证区块中所有数据实际是可用于下载的，我们可以淘汰掉多数人诚实的假设，相反地，对重播数据的最小数量诚实节点，提出了更弱的假设。欺诈和数据可用性证明，是区块链链上扩容的关键(例如，通过分片技术或大区块)，同时确保链上数据的可用性和有效性。

我们提出、实施并评估了一个新的欺诈证明，以及一个数据可用性证明系统。

一、引言和动机

随着密码货币和智能合约平台被广泛采用，我们在实践过程中已经看到了区块链的可扩展性限制问题。由于比特币交易的平均费用一度高达20美元 [19.28]，很多流行的比特币支付服务停止接受了比特币支付方式[26]，而以太坊流行的CryptoKitties(加密猫)[6]智能合约一度造成以太坊网络未确认交易积压增长了6倍[40]。由于区块链链上空间是受到限制的，例如比特币的区块大小限制 [2]或以太坊的区块gas限制[41]，用户们就需要为交易纳入区块链而支付更高的交易费用。

虽然扩大链上容量限制将产生更高的交易吞吐量，但人们会担心这种方式会降低区块链的去中心化及安全性，因为这会导致增加完全下载和验证区块链所需的资源，从而导致更少的用户能够负担得起独立验证区块链的全节点，这就要求用户转而去运行轻客户端，该客户端假设是有遵循区块链协议规则的共识算法 [23]。

轻客户端在正常情况下的运行是良好的，但当多数人的共识(例如矿工或区块生产者)是不诚实的时候，轻客户端的安全保证就是较弱的。例如，尽管在比特币或以太坊网络中的多数非诚实节点，目前只能审查、反转或重新排序交易，如果所有的客户端都使用的是轻节点，大多数共识将能够相互勾结，产生包含凭空创造货币的交易区块，而轻节点将无法检测到这一点。另一方面，全节点将立即拒绝那些无效区块。

因此，各种集中于链外扩容的技术解决方案尝试在兴起，例如支付通道[31]，其中参与者在链外签署交易，并最终在链上进行余额结算。支付通道也已扩展到了状态通道 [25]。然而，由于开通和结算通道涉及到了链上交易，因此链上扩容对于支付和状态通道的大规模采用而言，仍然是必要的[3].

在这篇论文中，我们通过使轻客户端能够接收和验证来自全节点的无效区块欺诈证明，以降低链上扩容与安全性之间的权衡，这样它们也可以拒绝它们，前提是，假设至少有一个诚实全节点愿意生成在最大网络延迟的情况下传播的欺诈证明。

我们还设计了一个数据可用性证明系统，这是对欺诈证明的必要补充，以便轻客户端能够保证全节点生成欺诈证明所需的区块数据是可用的，鉴于有少量的诚实轻客户端要重建区块中的丢失数据。我们对自己的总体设计进行了实施，同时评估了安全性和效率。

我们的工作还涉及了区块链分片扩容方案 [1.7.20]，而在一个分片系统中，网络中不需要有节点下载并验证所有分片的状态，因此，我们就需要欺诈证明从恶意分片中检测出无效区块。

二、背景

2.1 区块链模型

简单地从字面上讲，区块链的数据结构是由区块串联成链组成的。每一个区块包含两个部分：一个区块头以及一个交易列表。区块头除了存储其它元数据之外，它还会存储之前区块的哈希值(从而实现链的特性)，以及包含区块所有交易的默克尔树(Merkle tree)根。

区块链网络拥有一种共识算法 [3] ，以确定一旦发生分叉时，我们应该支持哪一条链，例如，如果使用的是工作量证明 [26]算法，那么累积工作最多的那条链会得到承认。它们还具有一组协议规则，规定链的哪些交易是有效的，因此包含无效交易的区块永远不会被共识算法所青睐，实际上，这些无效交易区块也应该会被拒绝。

而所谓全节点，会下载区块链中的所有区块头及交易列表信息，并根据一些协议规则验证这些交易是否是有效的。

而轻客户端只需下载区块头信息，并假定交易列表中的交易是符合协议规则的。轻客户端根据共识规则验证区块，而不是根据协议规则，因此其假定共识规则是诚实的。轻客户端可以从全节点中接收Merkle证明，其中一笔特定的交易或状态对象被包含在区块头中。

目前有两种主要类型的区块链交易模型：未花费交易输出 (UTXO)模型以及帐户模型。基于UTXO模型区块链的交易(例如比特币)，包含了对先前交易的引用，其中哪些币是他们希望去‘花费’的。由于单笔交易可能将币向多个地址发送，一笔交易具有很多的‘输出’，因此，新的交易包含了对这些特定输出的引用。每一个输出只能够花费一次。

另一方面，基于帐户模型的区块链(例如以太坊)，则相对更容易使用(虽然有时在应用并行处理技术时会显得更复杂)，因为这种模型下，每笔交易会简单地指定从一个地址到另一个地址，而不会引用先前的交易。在以太坊中，区块头还包含Merkle树根(包含状态)，其包含了验证下一个区块所需要的‘当前’信息;在以太坊当中，这包含了系统中所有帐户和合约的平衡、代码及永久存储。

2.2 默克尔树(Merkle Tree)和稀疏默克尔树(Sparse Merkle Tree)

默克尔树是一种二叉树，其中每个非叶节点(non-leaf node)通过其子节点连接的加密哈希值标记。而默克尔树的根，是对所有叶节点中所有条目的的一个保证。这就允许了给出一些默克尔树根的默克尔证明，这些证明能够表明一个叶节点是默克尔树的一部分。

某些叶节点的默克尔证明，是由叶节点的祖节点及祖节点同胞中间节点组成的，直到树的根，从而形成子树，该子树的Merkle根可以被重新计算，以验证Merkle证明是有效的。一棵拥有n叶节点的梅克尔树，其Merkle证明的大小和验证时间是O(log(n))。

而所谓的稀疏默克尔树 [12. 21] ，是指那些拥有n叶节点的默克尔树，而其中的n是一个非常大的数字(例如，n=2^256)，但几乎所有的节点都具有相同的默认值(例如，0)。如果k个节点的值是非零点，那么在默克尔树的每个中间层，将有一个最大值k的非零值，并且所有其它值都会是该级别的相同默认值：底层为0.L1=H(0. 0)，第一个中间层为L1=H(0. 0)，第二个中间层为L2=H(L1. L1) ，依此类推。

因此，尽管默克尔树中的节点数呈指数增长，但树的根还是可以通过O(k × log(n)) 时间进行计算的。稀疏默克尔树允许对键值图进行保证，其中的值可以在O(log(n)) 时间内进行更新、插入或删除操作。如果构造地简单，则特定键值条目的Merkle证明，就是log(n)的大小，如果中间节点的同胞节点具有默认值是不需要显示的，那么我们可以将其压缩至log(k) 大小。

像瑞波和以太坊这样的系统，目前所使用的是帕特丽夏树(Patricia tree) [35.41]，而不是稀疏默克尔树;我们在本文中使用稀疏默克尔树为例，是因为它们会更简单。

2.3 擦除码与里德-所罗门码(RS 码)

擦除码是在位擦除(而非位错误)假设下工作的纠错码[14.30];特别是，用户知道哪些位是必须被重建的。纠错码会把长度为k的消息转换为长度为n > k的更长的消息，从而可以从n个符号的子集恢复原始消息。

里德-所罗门码[39]具有多种应用，它是被研究最多的纠错码种类之一。一个RS 码通过将长为k的消息作为某些有限域(素数域和二元域是最常用的)元素x0.x1.…,xk−1列表来编码数据，对多项式 P(x) 进行插值处理，其中 P(i)=xi，其中0 ≤ i < k，然后用xk,xk+1.…,xn−1来延伸这个列表，其中xi=P(i)。

这个多项式P可使用诸如拉格朗日插值(Lagrange interpolation)技术，或者诸如快速傅立叶变换法(Fast Fourier transform)这类更优化、更高级的技术，从这个较长列表中的任何k字符中恢复，而知道P之后，我们就可以恢复原始消息。RS 编码可以检测并校正高达(n−k)/2 种错误，或者是错误和擦除的组合。

通过各种方式 [34.37.42]，RS码已被推广到了多维码[13.36]。在一个d维码中，消息被编码成大小为k × k × … × k的正方形或立方体或混合立方体，而一个多维多项式P (x1. x2. …, xd)是在P(i1.i2.…,in)=xi1.i2&hell

ip;,in处进行插入，这个多项式将扩展到更大的n×n×…×n正方形或立方体或超立方体。

三、假设与威胁模型

在我们提出的网络和威胁模型下，我们的欺诈证明(第四章内容)和数据可用性证明(第五章内容)是可以适用的。

3.1 准备工作

我们提出了一些原语，而在论文的其余部分，我们将会使用到这些原语。

1、–hash(x)是一种加密安全哈希函数，它会返回X的摘要(例如SHA-256);

2、– root(L) 会返回项目L列表的Merkle根;

3、– {e → r} 指出了Merkle证明，其中元素e是根为r的Merkle树的成员;

4、– VerifyMerkleProof(e, {e → r}, r, n, i)是当Merkle证明有效时，它会返回“true”值，其它情况则会返回“false”值，其中n表示基础树中元素的总数，而i是树中E的索引。这验证了e是在i索引当中的，及其成员资格;

5、– {k, v → r} 指出了一个Merkle证明，其中键值对k, v是根为r的稀疏Merkle树的一个成员。

3.2 区块链模型

我们假设了一个通用区块链体系结构，其中区块链是由区块头H=(h0.h1.…,hn)组成的哈希链组成的。每一个区块链头hi包含了Ti交易列表的Merkle根txRooti，这样root(Ti) 就等于 txRooti 。假设一个节点从网络中下载了交易 Ni的列表，如果(i) root(Ni)=ri，并且(ii) 给出一些有效性函数 。那么我们认为区块头hi是有效的。

valid(T, S) ∈ {true, false}

其中T是交易列表，而S是区块链的状态，那么valid(Ti,Si−1)必须返回“true”值，其中Si是在Ti中所有交易之后区块链的状态。我们假设valid(T,S)需要O(n) 时间来执行，其中的n是T列表中的交易数。

在第四章第二节中，我们将讲解基于UTXO(例如比特币)以及帐户模型(例如以太坊)的区块链如何以用这个模型来表示。

目标：我们的目的是向客户端证明，对于给定的区块头hi，valid(Ti, Si−i)在少于O(n)时间及少于O(n)空间的情况下会返回“ false”值，这依靠的是尽可能少的安全假设。

3.3网络模型

我们假设了一个由两种类型节点所组成的网络：

1、全节点。这些节点会下载并验证整个区块链。诚实的全节点会存储和重播它们下载到其它全节点的有效区块，并将与有效区块相关联的区块头广播给轻客户端。这些节点当中，有一些可能会参与共识(通过生产区块)。

2、轻客户端。这些节点的计算能力和网络带宽太低，无法下载和验证整个区块链。它们从全节点那里接收区块头信息，并根据要求，Merkle证明是证明某些交易或状态是区块头的一部分。

我们假设了一个网络拓扑，如图1所示;全节点之间会互相通信，而轻节点客户端则会和全节点进行通信，但轻节点之间并不会互相通信。此外，我们假设了一最大值的的延迟 &网络，这样的情况下，如果一个诚实节点可以连接到网络，并在时间T下载一些数据(例如一个区块)，那么它会保证其它诚实节点将在T‘≤T+&的时间做同样的事。

图片1: 网络模型 ：全节点之间会相互通信，但轻节点只会和全节点通信

3.4 威胁模型

我们在威胁模型中做出了如下假设：

1、区块和共识。区块头可能会由敌对参与者创建，因此可能是无效的，并且不存在我们可依赖的诚实多数共识参与节点;

2、全节点。全节点可能是不诚实的，例如，它们可能不会中继信息(例如欺诈证明)，或者它们可能会中继无效区块。然而，我们假设至少有一个诚实全节点连接到网络(即，它是在线状态的，它愿意生成和传播欺诈证明，并且不受日食攻击(eclipse attack)[18])

3、轻客户端。我们假设每个轻客户端会连接至少一个诚实的全节点。对于数据可用性证明，我们假设最小数量的诚实轻客户端允许区块的重构。具体的数目取决于系统的参数，我们将在第五章第六节中进行具体分析。

四、欺诈证明

图片2:网络级欺诈证明系统的结构概述

4.1 区块结构

为了支持高效的欺诈证明，有必要设计一个支持欺诈证明的区块链数据结构。该模型的扩展描述详见第三章第二节部分，在区块高度i的区块头hi包含了以下元素：