导读

区块链有一个非常经典的性质——可追溯性，本文提出一种细粒度、安全、高效的数据溯源方式——LineageChain，将数据的来源信息存储在Merkle树中，并通过一种仅附加跳跃列表进行高效查询。

如果你有什么问题，或者有什么想法，欢迎评论与我一起沟通交流。如果你想了解更多有关于区块链相关技术的内容，那就加群：955538712 或者扫描下方二维码加入我们吧！

Fine-grained, secure and efficient data provenance 

on blockchain systems

作者：Pingcheng Ruan, Gang Chen等

DOI：10.14778/3329772.3329775

发表：VLDB (Very Large Data Bases)（A类会议）

时间：2019

获取完整了论文，请在公众号回复：FSEDP或10.14778/3329772.3329775

摘要

背景

比特币等加密货币使区块链变火，区块链系统实现了防篡改的分布式账本，用于记录修改全局状态的交易。系统记录整个状态的发展历史，管理系统也被称为数据溯源或世系，在数据库系统中进行了广泛研究。但只能通过重放所有事务来查询现有区块链的数据历史，适用于大规模离线分析，不适合在线处理。

工作

提出一个用于区块链的细粒度的安全高效溯源系统——LineageChain，LineageChain通过简洁的界面向智能合约公开来源信息，从而启用一类新的区块链应用，其执行逻辑在运行时依赖来源信息。LineageChain在合约执行时捕获来源，并将其高效存储在Merkle树中。

提供一种新颖的跳跃列表索引，用于支持高效前向查询处理。

在Hyperledger和区块链优化存储系统ForkBase实现了LineageChain，广泛评估表明，它对新的区块链应用程序、高效的查询和较小的存储开销都有好处。

1 引言

背景

区块链是块的链，每个块包含多个交易并通过hash指针与其前一个块连接。Bitcoin第一次引入区块链，中本聪在每批加密货币交易中应用它。作为分布式账本，链可以保证全部交易历史的完整性。基于P2P网络和分布式一致性协议——PoW，确保诚实节点有相同的账本。和Hyperledger拓展到其他应用，特别是引入智能合约，在区块链上编码任意的图灵完全计算。智能合约将其状态存储在区块链上，并通过调用合约的交易修改状态。

区块链打破了很多行业，包括金融、供应链和医疗服务，这些行业充分利用两个区块链相对于传统数据管理系统的明显优势：一、允许相互不信任的参与方代替可信的一方一起管理数据。二、区块链为账本中的交易记录提供完整性保护，完整的交易历史是安全的。

管理数据历史在数据库中进行广泛研究，很多系统支持数据溯源。区块链上下文有明确的粗粒度溯源支持，特别的，区块链被视为具有一些状态（具有已知初始值），每个交易使系统变为一个新状态。状态或来源的发展历史可以通过复制所有交易来安全完整地构建。这种重构可以在离线分析期间完成，但是，在合约执行（或运行时）期间，智能合约没有来源信息是安全有效的。换句话说，智能合约不能以防篡改的方式访问历史区块链状态。因此，缺乏对来源的安全、细粒度的运行时访问限制了合约可编码的业务逻辑的表达能力。

图一所示智能合约示例，包含一个从一个用户转移一定量代币到另一个用户的方法，假设用户A希望根据B最近几个月的历史余额向B发送代币。例如A仅在B的每天平均余额多余t的时候才会发送。目前不可能对此操作写一个合约方法。为了解决这个问题，A首先需要通过查询和重放所有链上交易来计算B的历史余额，然后根据结果发布转移交易。除了与区块链的多次交互产生的性能开销之外，这种方法也不安全：它无法实现交易序列化。特别地，假设A基于其对B的历史余额的计算来发布转移交易tx。但是在区块链接收到tx之前，提交另一个交易，使得B的平均余额变为t’<t。因此，当稍后提交tx时，它将基于过时状态，因此无法满足预期的业务逻辑。在具有创世币的区块链中，可串行化违规可被用于对用户造成重大经济损失的事务排序攻击。

工作

设计并实现细粒度、安全高效的区块链溯源系统——LineageChain。目标是使一类新的智能合约能够在运行时访问来源信息。与现有向数据库添加来源目标类似，但有三个挑战：

（1）缺乏以输入-输出依赖的形式捕获来源的数据操作符。更具体地说，对于一般数据管理工作负载(即非加密货币)，当前的区块链只公开通用运算符，例如键值元组的put和get。这些操作符没有输入-输出依赖关系。相反，关系数据库操作符(如map、join、union)被定义为输入和输出之间的关系，它们清楚地捕获了它们的依赖关系。为了克服这种缺乏来源友好操作符的问题，使用区块链运行时记录任何合约调用中使用的所有状态的读写依赖关系，然后将其传递给用户定义的方法，该方法指定要持久化的依赖关系。

（2）区块链假定了一个对抗性的环境，因此，任何捕获的来源必须防篡改。为了解决这个问题，将来源存储在Merkle树数据结构中，该结构也允许进行有效的验证。

（3）确保溯源查询是快速的，因为由于验证器的困境，大量的执行开销是不受欢迎的。为了解决这一挑战，我们设计了一个新的跳跃表索引，并针对来源查询进行了优化。索引的存储开销很小，其性能与区块链中的块数量无关。

贡献

1、引入LineageChain系统，高效捕获区块链的细粒度来源。安全存储来源，并向智能合约公开简单的访问接口。

2我们设计新的查询区块链来源的索引。索引的存储开销很小，其性能与区块链大小无关。它改编自跳跃列表，但我们完全删除了随机性，以适应确定性区块链。

3、为Hyperledger实现基于ForkBase（一个区块链优化存储）的LineageChain。进行评估，评估显示有利于依赖来源的应用，且具有高效查询和较小存储开销。

LineageChain是我们Hyperledger++系统的一个组件，我们改进了Hyperledger的执行和存储层，以提供安全的运行时来源支持。在其他地方，通过有效地应用分片和利用可信硬件来横向扩展系统解决共识瓶颈，大幅提高系统吞吐量。设计了一个支持高效分叉的Forkbase存储引擎，提高了存储效率。目前正在整合智能合约验证，以增强智能合约的正确性。

组织结构

论文的其余部分组织如下。第2节提供了区块链的背景知识。第3节描述了我们用于捕获来源和公开于智能合约的接口的设计。第4节讨论了如何存储源，第5节描述了我们的新索引。第6节介绍了我们的实现。第7节报告了LineageChain的性能。第8节讨论了相关工作，第9节对本文进行了总结。

2 背景和概述

介绍区块链系统的相关背景，以及影响索引结构需求的设计选择。

1 区块链系统

区块链系统由多个互不信任的节点组成。目前的区块链可以大致分为无许可制和许可制。在前者中，任何节点都可以加入或离开网络。在后者中，成员资格受到严格控制，节点必须经过身份验证并被授予加入网络的权限。

共识

除了少数具有高可审计性的受许可区块链外，大多数区块链都采用拜占庭失效模型，在该模型中，故障节点的行为是任意的。在这种不利环境下。他们使用拜占庭容错(BFT)共识协议，以确保诚实的节点同意相同的状态。BFT协议的例子包括在比特币[27]中使用的工作证明(PoW)，以及在Hyperledger中使用的PBFT[11]。另一方面，PoW及其变体允许不一致性，因为链可以有分叉。这些协议通过确定地选择一个分支而不是另一个分支来处理分支。例如,在PoW最长的分支被选中。

数据模型

不同的区块链对其状态采用不同的数据模型。比特币状态是建模为未花费交易输出(UTXOs)的未花费硬币，它由未被用作另一笔交易的输入的交易的输出组成。UTXO模型适合于简单的交易验证，因为节点只需要检查过去没有使用过交易输出。最近的区块链，即和Hyperledger，支持可以通过智能合约任意修改的一般状态。它们采用基于帐户的数据模型，其中每个帐户都有自己的本地状态存储在区块链上。智能合约事务可以将任意数据写入存储。这种灵活的数据模型是以完整性保护和帐户状态验证为代价的。本文主要研究基于账户的数据模型。

块结构

区块链中的块存储交易和全局状态。区块头包含以下字段：

PreviousBlockHash:引用链中的前一个块
Nonce:用于校验块的有效性。在PoW共识中，Nonce是解决PoW难题的方法。
TransactionDigest:用于块中事务列表的完整性保护。
StateDigest:用于块事务执行后的全局状态完整性保护。

TransactionDigest和StateDigest都是Merkle-tree根。它们允许有效的块传输，其中块头和块内容可以不挂钩并分别传输。此外，它们还可以有效地验证交易和状态。

块验证

算法1说明了一个节点如何使用块头来验证它从网络接收到的块是否有效。如果该块有效，则将其追加到链中。当PoW被用于共识时，节点首先检查Nonce是否是PoW难题的正确解。如果使用确定性共识协议，如PBFT，则跳过此步骤。接下来，通过从列表中计算和验证TransactionDigest，检查交易列表是否被篡改。然后，它试探性地重新执行包含的交易。在执行期间，通过一些索引结构访问状态。执行之后，节点检查结果状态是否与StateDigest相匹配。如果有，则认为块是有效的，新的状态被提交到存储中。否则，状态将回滚到执行之前的状态。我们注意到算法1接受一个表示全局状态的对象gState作为输入。如果区块链没有分叉，例如Hyperledger，则该对象是最新状态。然而，当存在分叉时，例如在中，该对象可以引用过去某个点的全局状态。

2 状态组织

区块链最重要的特性是保证数据完整性，这意味着全局状态必须是不可篡改。上述块验证算法对区块链的安全性至关重要。我们注意到，该算法需要访问状态的所有历史快照，以及批量更新状态的能力。这些要求为组织区块链状态设计索引结构提出了新的挑战。特别是，不能使用传统的数据库索引，如B+ tree。我们现在详细阐述区块链索引的要求，并解释如何在和Hyperledger中满足这些要求。LineageChain建立在现有的区块链索引上，以确保获取的来源的安全性。

篡改证明

用户可能希望在不下载和执行所有交易的情况下读取一些状态。因此，索引结构必须能够为任何状态生成完整性证明。此外，索引必须为全局状态提供唯一的摘要，以便节点可以快速检查执行后的状态在整个网络中是否相同。

增量更新

在一个典型的区块链应用程序中，全局状态的规模是很大的，但是一个块只更新一小部分状态。例如，一些状态可能在每个块上更新，而另一些可能更新得少得多。因为索引必须在每个块上更新，所以它必须能够高效地处理增量更新。

快照

必须在每个块上对索引和全局状态进行快照。这对于实现区块链的不变性属性至关重要，该属性允许用户读取任何历史状态。这对区块核查也很重要。如前所述，当接收到创建分叉的新块时，必须使用状态的旧快照作为输入进行验证。即使区块链不允许分叉，当接收到的块在执行后被发现无效时，快照也会启用回滚(算法1中的第4步)。

现有的区块链使用基于Merkle树的索引。特别是，实现了Merkle Patricia Trie (MPT)和Hyperledger实现了Merkle Bucket

3 LineageChain概述

给定一个现有区块链上的智能合约，LineageChain用细粒度、安全和高效的溯源来丰富它，如下所示。首先，合约可以实现一个helper方法来定义在每次合约调用时要捕获的确切的来源信息。默认情况下，记录所有状态的所有读写依赖关系。第二，可以添加在运行时使用源的新方法。就合约开发人员而言，这是对现有的、非溯源的区块链仅有的两个更改。然后捕获的信息存储在一个增强的区块链存储中，以确保来源的有效跟踪和篡改证明。在这个存储之上，我们构建了一个跳跃列表索引来支持快速的起源查询。对区块链存储的这些更改对合约开发人员是不可见的。

3 细粒度溯源

在本节中，我们将描述在执行智能合约期间捕获来源的方法。我们提供了允许合约在运行时查询来源的API。

运行示例

在本节中，我们使用图1所示的代币智能合约作为运行示例。图2描述了合约如何修改全局状态。特别是，该合约部署在区块链的第L个区块。两个地址Addr1和Addr2用100个代币初始化。在两个地址之间传输代币的两个交易Txn1和Txn2分别在块M和块N提交。Addr1的值从块R到块M-1是100，从块M到块N-1是90，在块N是70。全局状态gState本质上是地址和它们值的映射。

1 捕获来源

对于一般的工作负载，区块链只支持一小部分数据操作符，即read和write。这些操作符对来源不友好，从这个意义上说，它们不捕获任何数据关联(输入-输出依赖)。相反，关系数据库或大数据系统有许多源友好操作符，如map、reduce和join，它们的语义有意义地捕捉关联。例如，join的输出显然来自(或依赖于)输入数据。

在LineageChain中，每个合约方法都可以通过helper方法实现友好溯源。更具体地说，在交易执行期间，LineageChain收集被访问状态的标识符和值，即用于read和write操作的标识符和值。结果是读集reads和写集writes。对于Txn1：

reads = {Addr1 : 100, Addr2 : 100}
writes = {Addr1 : 90, Addr2 : 110}

在执行完成后，这些集合连同合约方法的名称一起传递给用户定义的方法prov_helper。prov_helper的签名如下:

它根据输入的读和写集返回一组关联项。图3显示了代币合约的helper方法的实现。它首先从读写集计算发送方和接收方的标识符。具体来说，在write操作中值小于在read操作中值的标识符是发送方，在接收方中值正好相反。然后它返回单个元素的关联集：接收方-发送方关联。在我们的例子中，对于Txn1，这个方法返回{Addr2 : [Addr1]}。

LineageChain确保每次成功执行合约后立即调用prov_helper，如果该方法为空，LineageChain使用读集中的所有标识符作为写集中每个标识符的关联关系。感兴趣的读者可能会注意到，vanilla Hyperledger已经在背书阶段计算了读/写集合。与我们的方法不同，它们在内部用于并发控制，以实现单副本的可序列化性。相反，我们允许合约开发人员获取他们的应用程序级来源。

2 智能合约API

当前智能合约只能安全地访问最新的区块链状态。例如，在Hyperledger中，get(k)操作返回被写入或被批处理的k的最后一个值。另一方面，在中，当智能合约在区块b读取k值时，系统将区块b-1的状态快照视为最新状态。虽然在不同的分支上可能存在一个b’ > b块，但是智能合约总是将从存储层返回的数据作为最新状态处理。

当前API的主要限制是智能合约不能篡改读取状态的以前值。相反，合约必须显式地跟踪历史版本，例如为每个状态维护一个版本列表。这种方法在存储和计算方面都是昂贵的。LineageChain通过三个额外的智能合约API解决了这个限制。

Hist(stateID, [blockNum]):返回元组(val, blkStart, txnID)，其中：
  · val是区块blockNum的stateID的值。如果没有指定blockNum，则使用最新的块。
  · txnID是将stateID设置为val的交易；
  · blkStart是执行txnID的区块号


Backward(stateID, blkNum):返回元组(depStateID, depBlkNum)，其中：
  · depStateID是blkNum块上stateID的依赖状态。
  · depBlkNum是设置depStateID值的块号。
  在我们的示例中，Backward(Addr2, N)返回(Addr1, M)。
  
Forward(stateID, blkNum):与Backward类似，但返回stateID为依赖项的状态。：
  在我们的示例中，Backward(Addr1, L)返回(Addr2, M)。

图4演示了如何使用上述API来表达智能合约逻辑，而这些逻辑目前以安全方式是不可能实现的。(vanilla Hyperledger可选地提供历史查询的historyDB。但从平面存储实现，它不提供防篡改保证，这是我们的主要贡献。)。我们在原始合约中添加了两个额外的方法，它们都使用了新的API。Refund方法是检查一个账户最近一个月的平均余额，然后根据余额进行退款。Blacklist方法将一个地址标记为黑名单，如果该地址的最后5个交易中有一个与黑名单地址有关。

4 安全溯源存储

在本节中，我们将讨论LineageChain如何增强现有的区块链存储层，以便为捕获的起源提供有效的跟踪和篡改证明。我们的关键见解是将原来Merkle树中的扁平叶节点重组为Merkle DAG，然后讨论其性质。最后，我们解释了如何利用区块链执行模型来支持前向来源跟踪。

1 Merkle DAG

设k为区块链状态的唯一标识符，期望跟踪其演化历史。设v为唯一的版本号，用于标识状态在其演变历史中的状态。当版本v的状态更新时，新的版本v’严格大于v，在LineageChain中，我们直接使用区块号作为它的版本v。让 表示版本v时标识符为k的状态的值，如果k和v的意义不重要，我们就去掉下标。对任意的 和  ，  和  表示两个不同状态在不同版本的值。  表示位于块b之前，标识符为k的最新版本的状态值。在我们的示例中，  ，  ， 

定义1：交易由严格递增的tid标识，读取一组输入状态  ，并更新一组输出状态 

属性(1)意味着一个交易的所有输出状态的版本都是相同的，因为它们是由同一个块中的同一个交易更新的。属性(2)暗示任何输入状态的版本都严格低于输出版本。这是有意义的，因为区块链建立了交易的总顺序，并且输入状态只能在以前的交易中更新。属性(3)指出，对于所有具有相同标识符的状态，以后交易的输入永远不能有更早的版本。这确保了任何事务的输入状态在执行期间都必须是最新的。属性(4)意味着每个状态更新都是唯一的。

定义2：状态s的依赖是输出s的交易的输入状态的子集，更具体地说:

我们注意到，由prov_helper方法返回的dep只是读集的一个子集。

定义3：状态  的项 

一个条目唯一地标识一个状态。在LineageChain中，我们将每个条目与其对应的hash关联。

定义4：区块b的最新状态集 

 表示区块b的更新状态，我们可以通过组合  和  递归计算  。

定义5：  是建立在map 

LineageChain存储  作为块头中的状态摘要。

2 讨论

我们新的Merkle DAG可以很容易地集成到现有的区块链索引结构。特别是，现有的Merkle索引(如MPT)直接将状态值存储在叶子上，而LineageChain中的Merkle DAG将最新状态版本的入口hash存储在叶子上。通过增加一个间接级别，我们维护了索引的三个属性(篡改证明、增量更新和快照)，同时通过遍历DAG以提取细粒度溯源信息的能力来增强它。

回想一下，状态条目hash捕获状态的整个发展历史。由于该hash受到篡改证明的Merkle索引的保护，所以状态历史也是如此。换句话说，我们为出处添加了完整性保护，而不会给索引结构增加任何额外的成本。例如，假设客户端想要读取一个状态的特定版本，它首先读取最新块上的状态条目hash。与现有的区块链一样，这种读取操作可以被验证不会被篡改。接下来，客户机从这个hash遍历DAG以读取所需的版本。因为DAG是防篡改的，所以可以保证读取版本的完整性。

3 支持前向追踪

上述DAG模型的一个问题是它不支持向前跟踪，因为hash指针只引用向后依赖项。当状态更新时，这些向后依赖关系将永久建立，因此它们属于状态的不可变派生历史。但是，该状态可以被未来交易读取，因此在更新时不能确定其正向依赖关系。

我们在这里的关键观点是，只有最新状态的向前依赖关系是可变的。一旦状态更新，由于区块链智能合约的执行模型(总是读取最新状态)，前一个状态版本的前向依赖关系将成为永久的。因此，它们可以包含在起源历史中。图6展示了一个例子，在这个例子中，当状态更新为  时，  的正向依赖关系就确定了。这是因为当执行输出  的交易时，它读取  而不是  。

在LineageChain中，对每一个最新版本的状态  ，我们缓冲一个指向依赖项的前向指针列表，这些项包括 ​ ;我们将这个列表称为 ​ ，其更精确的定义如下:

当  的状态更新为 ​ 时，我们将 ​ 存储在 ​ 的条目。

5 高效溯源查询

Merkle DAG结构支持对最新状态版本的有效访问，因为b块上的状态索引包含指向该块上所有最新版本的指针。要读取s的最新版本，只需读取Xb，跟随s条目的索引，然后从该条目中读取状态值。然而，在DAG中查询任意版本的效率很低，因为它必须从DAG头开始，遍历一个长边到请求的版本。当用户只想检查特定版本的状态历史记录(例如，为了审计目的)时，支持快速版本查询是很重要的。这对于依赖溯源的智能合约也很重要，因为这样的查询会直接影响合约的执行时间。

在本节中，我们将描述一种新的索引，它可以促进快速的版本查询。该索引是为受许可的区块链设计的。我们讨论了它的效率以及如何将其扩展到无许可的区块链。

1 确定性仅附加跳跃列表

我们提出在一个状态DAG上建立一个索引来支持快速版本查询。索引有一个跳跃表结构，我们称之为确定性仅附加跳跃表(或DASL)。它是为区块链而设计的，利用了区块链仅是附加的事实，随机性并没有得到很好的支持。更具体地说，与普通跳跃表相比，DASL有两个截然不同的属性。首先，它是仅附加的。附加项的索引键(在本例中是版本)严格递增。其次，它是确定性的，也就是说，索引结构是由附加项的值唯一确定的，这与随机跳跃表不同。为了便于解释，我们假设版本号是正整数。

定义6：令 为标识符k的状态版本号序列，对任意的  ，都有  ，k的DASL索引由N个列表组成：  ，  和  分别是表 设b为基数，是一个系统范围的参数。Li的内容构建如下:

1）

2）给定  是 

图7显示了DASL如何与状态一起存储在名为Node的数据结构中。这个结构(也称为节点)由状态版本和值组成。一个节点属于多个列表(或级别)，因此它维护一个指向某些版本号的指针列表，以及另一个指向其他节点的指针列表。两个列表的大小都是N，列表的第i个条目指向级别Li中该节点的前一个版本(或前一个节点)。对于同一个键，版本号唯一地标识节点，因此我们使用版本号来引用相应的节点。

我们可以把一个列表看作是由某些大小的连续的、不重叠的区间组成的。其中，Li的第j个区间表示范围 

DASL和跳跃列表共享两个属性。首先，如果一个版本号出现在Li中，它也会出现在j < i的Lj中。其次，如果b = 2，假设一个版本最后出现的级别是i，那么这个版本在Li中前面的邻居出现在Lj中，其中j > i。给定这些属性，DASL中的版本查询将以与跳跃列表中相同的方式执行。更具体地说，查询尽可能遍历一个高级列表，从最后一个列表中的最后一个版本开始。只有当当前列表中的上一个版本严格小于请求的版本时，它才会移动到较低的级别。在DASL中，对  版本的查询返回最大的  版本，使  (  存在才能取等)。这个结果表示在  时可见的状态值。

现在我们来描述一个新节点是如何附加到DASL的。挑战是确定应该包含新节点的列表。算法2详细说明了查找新节点的列表和随后是先前版本的步骤。关键思想是从L0中的最后一个节点开始，然后不断增加列表级别，直到当前节点和新节点属于同一时间间隔(第9 - 18行)。图8(b)显示了将带有版本12的节点追加到原始DASL的结果。该算法从节点10开始，向上移动到列表L1和L2。它在L3停止，因为在这个级别节点10和12属于相同的间隔，即[8，16)。因此，新节点被追加到列表L0到L2中。当算法到达最后一个级别并且仍然能够追加时，它创建一个新的级别，其中节点0是第一个条目，并重复这个过程(第21 - 24行)。在图8(b)中，当添加版本 16时，可以使用所有现有的列表。然后，该算法创建L4和节点1，并将节点16添加到它。它也创建了级别L5，但随后丢弃了它，因为节点16不会被追加，因为它属于相同的区间[0，32)与节点1。

2 讨论

集成到Merkle DAG：DASL被集成到Merkle DAG中，如下所示。节点结构(图7)存储在状态条目(定义3)中。节点指针是实现的条目散列。Merkle树结构保持不变。

速度与存储权衡：作为跳跃列表的变体，DASL具有相同的lineage空间复杂性和对数查询时间复杂性。假设有v*数量的版本，DASL的基础是b。所需指针的最大数量是  （最多有  级别，第i级别最多需要  个指针）。假设查询版本是  ，查询距离为  ，该查询的最大跳数限制为 (从末尾开始的查询遍历将经历两个阶段，一个阶段指向较低的层次，另一个阶段返回到较高的层次。在每个阶段中，在进入下一个关卡之前，遍历同一列表最多需要b跳。并且有最多为  级别要遍历。)。因此，b控制空间开销和查询延迟之间的权衡。这个属性的一个好处是，DASL查询更倾向于最近的版本，即d是小的，这对于使用最近版本而不是旧版本的智能合约很有用。另一个好处是，这种最近版本查询的性能不会随着状态历史增长而改变。

扩展到无需许可的区块链：我们注意到，DASL会带来存储开销。版本查询也会带来一些计算成本，尽管使用DASL比不使用它更有效。正如我们在第7节中演示的那样，这些成本可能非常小，不会影响已许可的区块链的性能。然而，他们需要在无需许可的区块链中小心管理，因为任何管理费都直接转化为矿工的货币成本。特别是，矿工的任何额外成本都会触发验证者的困境，损害区块链的激励机制。

恶意用户可能会发出一个引用非常旧版本的交易。阅读早期版本比较昂贵，因为有更多的跳跃。这个开销由网络中的所有节点承担，因为网络中的每个节点都必须执行相同的交易。当前的公共区块链通过对交易中的每个操作明确收费来防止这种拒绝服务攻击。在中，交易所有者为gas中的资源消耗付费。写入更多数据或消耗更多CPU的交易需要支付更多的gas。因此，理性的用户不会在区块链上运行过于复杂的交易。

由于DASL消耗资源，它的成本必须在无需许可的区块链中显式地计算。更具体地说，在部署期间，合约所有者指定哪些声明需要DASL支持。另外，可以从合约的源代码自动推断出对DASL的支持。部署费用应该反映DASL额外的存储成本。如果费用太高，业主可以通过增加b来降低费用。在合约执行过程中，执行引擎必须将DASL查询的成本收取到交易费用中。特别是，需要更多跳转才能找到请求版本的查询会招致更高的交易费用。用户可以根据上面推导的理论上界，根据经验估计跃点(以及成本)。

6 实现

在本节中，我们将介绍基于Hyperledger的LineageChain的实现。我们在Hyperledger v0.6和v1.3版本中都实现了LineageChain。虽然两个区块链遵循不同的设计，但它们共享相同的四个逻辑层:存储层、执行层、共识层和应用层。图9描述了这些层，并突出显示了我们对原始Hyperledger栈所做的更改。特别是，我们用Merkle DAG和DASL索引的实现完全取代了Hyperledger的存储层。这种新的存储是建立在ForkBase之上的，这是一种支持版本跟踪的最先进的区块链存储系统。我们使用原始执行引擎在合约执行期间记录读写集。在应用层，我们添加了一个新的helper方法和三个溯源API。执行引擎改良为在每次合约成功执行后调用helper方法。

1 存储层实现

我们没有从头实现存储层，而是利用了ForkBase对版本跟踪的支持。我们开发了LineageChain中ForkBase的三个特性。第一个是fork语义，应用程序可以使用fork语义为更新指定一个分叉。给定一个分叉，ForkBase提供对最新值的访问。第二个属性是tamper evidence，其中每个更新都会返回一个篡改证明标识符vid，该标识符捕获更新值的整个演变历史。ForkBase中的数据对象由key和vid唯一标识。在LineageChain中，vid被用作DAG中的条目哈希，以及DASL中的指针。第三个属性是丰富的内置数据类型集，包括map、list和set。

算法3详细说明了在提交块时更新状态和计算全局状态摘要的实现。使用新的状态和依赖项列表调用update函数。我们首先通过检索依赖状态的最新vids来准备反向指针列表(第5-8行)。接下来，我们为DASL索引构建指针，然后检索前一个状态的前向指针(第9行)。这些步骤的元数据被序列化，并与ForkBase中更新的值一起存储(第14-16行)。结果是更新的新vid，它被追加到每个依赖状态的前向指针列表(第18-20行)。vid现在是最新版本(第21行)。

全局状态存储在ForkBase中的map对象中。要计算全局状态摘要，只需使用为该块计算的新vid更新map对象。map对象的更新操作(在ForkBase中构建为Merkle树)返回摘要latest_vid，该摘要随后包含在块头中。该摘要为到当前块为止的所有状态的发展历史提供了篡改证明。

2 应用和执行层实现

在Hyperledger中，用户通过实现Chaincode接口来编写智能合约。给定一个链代码，执行引擎在部署和调用期间分别触发Init和Invoke方法。这两种方法都以ChaincodeStubInterface的实例作为输入，该实例提供了智能合约的相关上下文，比如对账本状态的访问。

我们将名为ProvHelper的helper方法添加到Chaincode接口。第三节解释了该方法的签名，以及如何使用它编写用户定义的溯源规则。执行引擎在执行过程中获取PutState和GetStates，记录读集和写集。执行结束时调用ProvHelper，传递给它ChaincodeStubInterface、方法名和记录的读集和写集。三个新的溯源API：Hist，Backward和Forward，被添加到ChaincodeStubInterface，因此所有合约方法都可以访问。

7 效用评估

1 基准和实验设置

我们根据两个基准来评估LineageChain。在第一个基准(称为Hyperledger+)中，我们直接将来源信息存储到Hyperledger的原始存储，即RocksDB，并依靠RocksDB的内部索引来支持种源查询。在第二个基准(称为LineageChain–)中，我们使用ForkBase存储状态版本。这个基准不支持多状态依赖关系，也没有DASL索引。我们用它来评估索引的存储开销和跟踪多状态依赖关系，以及索引的性能优势。

我们做了三组实验。首先，我们评估LineageChain对于Provenance-dependent的区块链应用程序的性能。我们将其与在发出区块链交易之前脱机查询来源的方法进行比较。其次，我们在一台机器上评估LineageChain中溯源查询的性能。对于单状态版本查询，我们使用BLOCKBENCH中提供的YCSB基准，用键值元组填充区块链状态。然后，我们测量两个查询的延迟:一个查询在特定块上检索状态，另一个查询遍历状态历史。对于多状态依赖性跟踪，我们为供应链应用程序实现了一个合约。在这个应用程序中，一个电话由由其他组件或原材料制成的中间组件组装而成。供应链创建一个DAG，表示电话的派生历史。DAG的最大深度为6。我们为这个契约生成合成数据，并检查使用Backtrack检索给定电话依赖项的操作的延迟。

在第三组实验中，我们评估了在分布式设置下，来源对区块链整体性能的影响。为此，我们在多个节点上运行BLOCKBENCH中的Smallbank基准测试。我们测量总吞吐量，并分析成本明细，以了解来源支持的开销。

我们的实验是在一个有16个节点的本地集群上进行的。每个节点配备E5-1650 3.5GHz CPU，32GB内存，2TB硬盘。节点之间通过1Gbps以太网连接。报告的结果是基于Hyperledger v0.6，除非另有说明。

2 实验结果

Provenance-dependent 应用

我们通过修改BLOCKBENCH中的YCSB基准来实现一个简单的依赖溯源的区块链应用程序，这样更新操作就依赖于历史值。使用LineageChain，合约可以直接访问来源信息，而客户端与原始YCSB中保持一致。如果没有LineageChain，客户端将被修改为在发布交易之前读取B最新的块。B表示客户端离最新状态还有多远。

我们使用Hyperledger v1.3上的LineageChain实现进行实验，有16个节点和1个客户端。图10(a)显示了使用不同的b的交易延迟。可以看出，使用LineageChain，延迟几乎保持不变，因为客户端不需要为起源查询获取任何块。相比之下，如果没有LineageChain，延迟会随着b线性增加。这证明了在运行时访问起源信息的性能优势。

溯源查询

我们首先创建500个键值元组，然后不断地发出更新元组，直到分类帐中有多于10000个块。每个块包含500个交易。然后，对不同块号上的键值执行查询。图11(a)说明了从上一个块开始的块距离不断增加的查询延迟。可以看出，当距离较小时，LineageChain-的延迟最小。LineageChain-没有DASL索引，因此对该查询执行最新版本的线性扫描。因此，当请求的版本是最近的版本时，它的速度很快，因为读取的次数很少。然而，它的性能会随着距离的增加而迅速下降。特别是当块距离达到128时，查询速度比LineageChain慢4倍。我们观察到Hyperledger+的查询延迟与块距离无关。这是因为查询直接使用了RocksDB索引。LineageChain的表现优于LineageChain-和Hyperledger+。由于DASL, 当块距较小时，LineageChain中的查询延迟较低。当块距增加时，延迟在LineageChain中仅以对数形式增加，而在LineageChain-中呈线性增加。

我们重复上面的实验，同时将块的距离固定为64，并改变块的总数。图11(b)显示了当块数量增加时版本查询的结果。可以看出LineageChain和Hyperledger+的查询延迟基本相同。换句话说，在这些系统中，版本查询的性能与块号无关，这是由于跟踪状态版本的DAG数据模型。LineageChain的性能优于Hyperledger+，这是因为它的索引减少了需要读取的跳跃数。一个有趣的观察是，Hyperledger+的延迟有明显波动。我们将这种变化归因于RocksDB的log-structure-merge tree索引，在该索引中，当块总数增加时，请求的版本可能位于树的不同级别。

接下来，我们测量给定键的整个版本历史的操作的延迟。图11(c)显示了随着块数量增加的扫描延迟。对于Hyperledger+，我们首先构造键范围，并依赖于RocksDB迭代器进行扫描。LineageChain-和LineageChain都使用了ForkBase迭代器，因此性能相同。随着块数量的增加，版本历史会变长，这就导致了两个系统中延迟的线性增加。然而，LineageChain的表现比Hyperledger+要好一个常数倍。我们将这一差异归因于ForkBase对版本跟踪的优化。

最后，我们评估了具有多状态依赖关系的查询性能。我们用原材料填充区块链状态，并发出创建新手机的交易。我们执行广度优先搜索来检索电话的所有依赖项。在这个实验中，我们只比较了Hyperledger+和LineageChain，因为LineageChain-不支持多状态依赖。图10(b)显示了不同搜索深度下的性能，其中Hyperledger+和LineageChain的延迟都随着深度的增加呈指数增长。然而，LineageChain的表现超过了基准。这是因为LineageChain中的索引直接捕获依赖关系，而Hyperledger+中的每个溯源操作都需要遍历RocksDB索引。当查询的数量随着搜索级别的增加而增加时，它们的性能差距就会累积。

LineageChain开销

我们在单个客户机和不断增加的节点数量下运行Smallbank基准测试。客户端使用16个线程，每秒发出16个交易。我们检查了对区块链的整体性能的来源支持的开销。

图12显示了交易延迟和总吞吐量。我们没有观察到LineageChain和其他基准之间的显著差异。特别是，交易延迟约为1.2s，吞吐量从大约118tps下降到108tps。

我们将块延迟分解为三个部分:共识延迟(块提议阶段)、执行延迟(事务执行时)和提交延迟(状态提交到存储时)。图13显示了节点数为8、12和16时的详细情况。可以看出，执行阶段占了成本的大部分。Hyperledger+和LineageChain在块执行时间上没有显著差异。因此，起源捕获引擎的开销可以忽略不计。

由于ForkBase的计算需要在提交过程中更新内部数据结构，LineageChain-和LineageChain的块提交延迟比Hyperledger+高2倍。然而，块提交阶段只占总块延迟的不到20%。我们进一步注意到，交易延迟是以秒为单位的，而块延迟是以数百毫秒为单位的。因此，由来源支持引起的任何额外开销不会导致区块链在用户感知的性能上有任何明显的差异。

接下来，我们研究LineageChain存储成本的细分。图14显示了不同数量的块的存储细分。块大小固定为每个块500个交易。图14显示了不同块大小的细分，同时将块的数量固定在1000。可以看出，存储大小与块的数量和块大小呈线性增长。我们观察到块内容占存储成本的大部分。相比之下，额外的出处和DASL索引只占总空间消耗的2-4%。在LineageChain, DASL指针被实现为20字节的vid字符串。一个新的状态最多会添加  个新指针，其中N是以前版本的数量，D是依赖状态的数量。与千字节大小的块相比，这些指针的存储消耗并不显著。因此，DASL的存储开销很小。

最后，我们评估了Hyperledger v1.3版本的LineageChain开销。这个版本的Hyperledger使用了一个不同的共识协议和比v0.6更简化的数据模型。我们使用16个节点，通过增加客户的交易率来改变报价负载。图15显示了性能开销。在饱和状态下，与没有溯源支持的原始Hyperledger相比，LineageChain-和LineageChain增加的延迟小于200ms。相比之下，Hyperledger+增加了超过1s。LineageChain-和LineageChain达到了与原始Hyperledger相似的吞吐量，大约是350tps。Hyperledger+峰值约330tps。这些结果表明LineageChain的开销比原始Hyperledger小。

8 相关工作

数据溯源

数据来源在数据库系统中得到了广泛的研究。从关系数据库[13,14,8]、协作数据共享系统[23,33]到大数据平台[30,5,36]，对起源的支持已经被添加到许多系统中。然而，这些系统对起源有不同的要求，因此面临不同的挑战。因此，它们的起源解决方案是临时的，不能很好地推广。在关系数据库中，Peter Buneman等人[9]提出了一种查询来源的方法，在这种方法中，他们为数据库确定了两种类型的溯源：“为什么”和“哪里”溯源。在Hadoop和其他MapReduce系统中，基于从映射器到约简器[21]的数据流，建立了数据派生图。提香[22]仪器触发Spark的原始RDDs捕获数据转换。其他作品利用特定应用领域的溯源，如网络[12]、语言处理[17]和交互式工作流应用[31]。它们专注于提高起源存储和查询效率。

我们的工作与上述工作具有同样的思想。我们在区块链中添加了溯源功能，从而支持新的区块链应用类。我们设计了一个针对区块链优化的新数据模型和索引。我们的系统解决了区块链的去中心化本质所带来的独特挑战。

区块链

区块链系统的大部分研究集中在无许可区块链的安全性上。一个公开的挑战是提高激励兼容性。如果诚实的参与者得到的回报与其对网络的贡献成比例，那么协议就是激励兼容的。例如币就不是激励兼容的[20,32,28]。另一个挑战是提高智能合约的安全性。最近的漏洞导致了巨大的经济损失，促使人们努力寻找漏洞并使用编程语言技术保护智能合约[6,16,25]。区块链作为一个数据管理系统，性能较差。BLOCKBENCH[19]比较了几个区块链和内存中的数据库，并显示了事务吞吐量的数量级差异。

我们的工作旨在通过引入溯源来丰富区块链的功能。它与上面那些旨在提高共识协议的安全性和性能的方法是正交的。与我们最密切相关的工作是ForkBase[37]。事实上，目前的LineageChain实现是建立在ForkBase之上的，以利用它的版本跟踪功能。然而，我们在ForkBase上的创新包括多状态依赖跟踪、高效索引和用于在运行时访问源的丰富API。另一个类似的近期工作是VChain[38]，研究人员在区块链数据库的历史数据上实现了布尔范围查询的完整性。但与我们不同的是，它们针对离线分析查询进行了优化。相反，我们将来源支持扩展到区块链在线交易。

9 结论

本文提出了LineageChain，一种细粒度、安全和高效的区块链溯源系统。系统在运行时有效地捕获来源信息，并将其安全存储。它向智能合约公开了简单的API，从而支持了一类新的依赖于源的区块链应用程序。在LineageChain中，由于有一种新颖的跳跃表索引，来源查询是有效的。我们在Hyperledger的基础上实现了LineageChain，并对其进行了基准测试。结果显示了LineageChain在支持丰富的、依赖源的应用程序方面的好处。它们证明了溯源查询是有效的，并且系统产生的存储开销很小。。

AI与区块链技术

长按二维码关注​