背景

产业更看重区块链的两点优势：

区块链是一个去中心化系统，这使得互不信任的人可以共同维护一个共同认可的数据而不需要相信一个第三方（毕竟第三方是否可信也存在问题）。
区块链提供了对所存储的交易信息的数据完备性保护（不可篡改性）。即，保证了完整的交易历史信息的安全性。

数据溯源已被数据库方向广泛研究，现有的区块链系统可以支持粗粒度的溯源。

区块链可以被视作存有多种状态（且已知其初始状态），每一笔交易信息都会将现有状态更新到新的状态。

对于历史状态的演化可以通过对所有交易信息的重放（replay all transactions）来安全地、完整地重新构建出来。

这样的重新构建可以被离线分析完成，但在智能合约执行的过程中，没有任何溯源信息可以被智能合约使用。

换言之，智能合约不能访问区块链中存储的历史数据状态，从而做到数据溯源。

运行时细粒度的数据溯源功能的缺乏，限制了为实现商务逻辑对智能合约的使用。

考虑下面这个智能合约的例子：

Fig1

这个智能合约包含一个方法，可以将一部分代币 (token) 从一个账户转到另一个账户。假设用户 A 想要将一部分代币转给 B，转账条件基于 B 的过去几个月的历史账户余额。例如，只有当 B 的每日平均账户余额超过 t 的时候，A 才会转账给 B。使用现有的智能合约目前不能简单实现这一操作。要解决这一问题，A 需要首先查询然后重放有关 B 的所有历史交易数据，然后基于得到的结果决定是否发起上图所示的 Transfer 这笔交易。除去在与区块链网络多次交互所带来的性能开销的缺点，这一做法实际上并不安全：它不能实现交易的可串行化。假设 A 想要基于 B 的历史余额发起 Transfer 交易 Tx，但在 Tx 被区块链网络认可前，另一个可以使 B 的余额小于 t 的交易被区块链认可，那么这样的后果就是当 Tx 被认可后，它会基于一个过时的状态（stale state）。这样的结果会违反最初设定的商业逻辑。在区块链中，违反可串行化会导致用户严重的财产损失。

假设用户 A 想根据最近几个月历史余额发送 token 给 B：

A 只当 B 的每天平均余额超过 t 才发，但目前不可能对这项操作去写一个合约；
A 首先需要通过查询和重放所有链上交易去计算历史余额，然后基于结果发布交易 Transfer。

问题：

区块链多次交互产生性能开销（performance overhead）
Not safe，它违反交易可序列化（transaction serializability）

假设A基于B的历史余额发布交易转移，但在通过区块链被收到之前，进行了另一笔交易使得B的平均余额变为t’ < t，结果当 t’ 之后才被提交，那么它将基于过时的状态（stale state），因此无法满足预期的业务逻辑。

也就是说，A 对 B 的交易转移是基于余额大于 t 的这一状态的，但是在转移过程中 B 的状态更新了，即余额变成了比 t 小的 t’，因此当这个交易转移到达后就发生了错位。

概念介绍

区块链系统

由多个互相不信任的节点构成。现有的区块链可大致分为公有链和私有链。对于前者，任何节点都可以加入或离开网络；对于后者，加入与否被严格限制。一个节点必须经过认证才会被授予加入网络的权利。

共识 (consensus)。所有的区块链都假设了 Byzantine Failure 模型。在这个模型中，故障的节点可以做出任何行为。在这样的设定下，区块链使用 Byzantine Fault Tolerance (BFT) 共识协议来保证诚实的节点可以达成一致的状态。BFT 协议包括比特币使用的 Proof of Work (PoW)，Hyperledger 使用的 PBFT。传统的 BFT 协议，例如 PBFT，保证了诚实节点达到相同的区块链结构。PoW 及其变种允许不一致性，也就是分叉（forks）。这些协议使用确定性选择一个分支的方法来解决分叉。比如在 PoW 中，最长的分支会被选择。
数据模型 (data model)。不同的区块链对状态有不同的数据模型。比特币使用 Unspent Transaction Outputs (UTXOs) 模型。
UTXO模型可以支持简单的交易验证。节点只需要检查交易的输出没有被之前的交易使用。而以太坊Ethereum和Hyperledger都使用了更加广泛地状态类型，使用智能合约来管理区块链上的状态。他们使用了基于账户的数据模型（account-based data model）。每个账户在区块链上都有其本地的状态。智能合约交易可以在对应的存储写入任何数据。这种灵活的数据模型以保护完整性和验证账户状态为代价。这篇论文只考虑 account-based 模型。
区块结构 (block structure)。区块存储对应的交易和全局状态信息 (global states)。区块头包含：
1. PreviousBlockHash: 对应前一个区块的哈希信息。
2. Nonce: 被用来查看此区块的有效性。在 PoW 共识中，Nonce 是 PoW 的答案。
3. TransactionDigest: 被用来做区块内交易信息的完备性保证。
4. StateDigest: 被用来做在执行过交易后的全局状态的完备性保证。
TransactionDigest 和 StateDigest 均为由 Merkel 树构成的根哈希信息。它们支持高效率的区块传递。区块头和区块体可以分开传输。它们也使得对于交易和全局状态的验证更加高效。

区块验证算法：

算法解释：

首先根据PoW验证Nonce的正确性。如果是确定性的公式算法，这一步可以跳过。接下来查看存储的交易信息没有被篡改，根据验证TransactionDigest来判断。再重新执行包含的交易，之后节点可以检查结果的状态是否和StateDigest匹配。如果都验证通过，新的状态可以被提交到区块链存储。否则状态就会被回滚到之前的状态。

状态的组织

对于区块链来说最重要的特点就是保障数据的完备性，这意味着其存储的全局状态必须保证防篡改。上述的区块验证算法对于区块链的安全至关重要。算法需要访问所存有状态的所有历史快照（history snapshots），同时还要保证可以批量地更新状态。这些需求给设计用于组织区块链状态的索引结构带来了新的挑战。特别地，传统的数据库索引比如B+树不能被直接使用。接下来我们讨论有关设计索引的需求。

防止篡改的证据。用户可能想要读取其中一些状态值而不愿意下载并执行所有的区块链交易。由此，所设计的索引必须可以生成对于任何状态读取的完备性证明。进一步讲，索引必须提供一个唯一的信息摘要 (digest) 来代表整个全局状态。这样，区块链节点就可以快速查看区块链网络上执行后的状态值是否相同。
增量更新。整个全局状态在区块链应用中会变得十分庞大。但一个区块只会改变一部分状态。比如，有些状态可能在每一个区块中都会被更新，其他状态的更新频率可能更低一些。因为索引会在每一个区块被更新，对于增量更新的支持显得尤为重要。
快照（snapshot）。一个索引的快照（snapshot）和对应全局状态都会在每一个新的区块产生时发生变化。若一个接收到的新区块产生了一个分叉（fork），则旧的状态快照（snapshot）必须被用作验证程序的输入。若区块链不允许有分叉，则当接收到的区块在执行交易后被发现为失效交易则可以回滚到之前的状态（算法1的第4步）。

现有的区块链系统使用基于Merkle结构的索引。进一步讲，以太坊 Ethereum 平台使用 Merkle Patricia Trie (MPT) 索引结构，是 Merkle 结构和前缀树的结合体。Hyperledger 使用 Merkle Bucket Tree (MBT)。在 Merkle 树中，父节点的哈希值是根据子节点哈希值算出的。根节点代表了整个数据内容的唯一标识符。验证完备性的证明可以快速地通过 Merkle 树来生成而不需要读取整个数据。所以，Merkle 树符合第一个要求。这一结构同样适合做增量更新（第二个要求），因为只有在更新中被影响的节点才需要发生变化。为了支持高效的快照，在 Merkle 树更新时要递归地在更新路径上生成新的节点。新的根节点可以作为新的快照的索引，且可以被添加到区块头中。

LineageChain 概述

给定一个智能合约，LineageChain 支持更加细粒度的、安全的、高效的数据溯源。智能合约可以实现一个 helper 方法来定义对应在合约被调用时需要记录的数据溯源信息。默认的情况下，所有的状态的读写依赖都会被记录。获取到的信息会被存储到一个区块链存储上来保证高效的数据追踪和防止篡改的数据溯源。系统有在存储结构之上构建一个基于跳表的索引结构以支持更加快速的数据溯源查询。这些对于区块链存储的改变对于合约开发者来说是不可见的。

细粒度溯源

图2显示了全局状态 gState 如何被合约改变：

Fig2

合约部署在区块链的第 L 个块上；
地址 Addr1 和 Addr2 都分别用 100 个 token 初始化；
在两个地址间交换 token 的交易 Txn1 和 Txn2 分别提交给块 M 和块 N；
从块 R 到块 M-1，Addr1 的值是 100；从块 M 到块 N-1，值是 90；从块 N 开始，值是 70；
gState 是地址与值的一个映射 (map)。

Capturing Provenance

Blockchains support only a small set of data operators for general workloads, namely read and write. These operators are not provenance friendly.

缺乏数据运算符以输入输出相关关系的形式语义的捕获源头。

区块链只提供read和write，非常provenance-unfriendly。

关系数据库或大数据系统有许多 provenance-friendly 的操作符，如 map, reduce, join。它们的语义都能有意义地捕获关联。例如，联接 (join) 的输出显然是从输入数据派生出来的(或依赖于输入数据)。

在 LineageChain 中，每个合约方法都可以通过一个 helper 方法使之变得 provenance-friendly。

method prov_helper(name: string,
                   reads: map(string, byte[]),
                   writes: map(string, byte[]))
       returns map(string, string[]);

在事务执行期间，LineageChain 收集被访问状态的标识符和值，即一系列 read 和 write 操作所导致的值的变化。结果将是一个读集合 reads 和一个写集合 writes。

例如在图2中：

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

Txn2: reads = { Addr1 : 90, Addr2 : 110 }, writes = { Addr1: 70, Addr2: 130 }

图1中 Token contract 的 helper 方法实现：

Fig3

可以看到，最终的返回值是一个 dependency set，这个集合只有一个 element，是个依赖关系，即 recipient-sender dependency。例如对 Txn1，这个方法返回 {Addr2:[Addr1]}。

想想数据库学过的那些知识就很好理解了！

LineageChain 确保 prov_helper 在每次成功执行合约后立即被调用。如果该方法为空，则 LineageChain 使用读集合中的所有标识符作为写集合中每个标识符的依赖。

Smart Contract APIs

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

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

Hist(stateID, [blockNum]): 返回元组 (val, blkStart, txnID) ，其中 val 是 stateID 在块 blockNum 的值。如果 blockNum 没有被指明，则 the latest block 会被使用。txID 是把 stateID 设置为 val 的 transaction，blkStart 是 txID 被执行时的块号。
BackWard(stateID, blkNum): 返回一个元组列表 (depStateID, depBlkNum) ，其中 depStateID 是 stateID 在块 blkNum 的 dependency state。depBlkNum 是 depStateID 被设置时的块号。在刚才的例子中，Backward(Addr2, N) 返回 (Addr1, M)。
Forward(stateID, blkNum): 和 Backward API 类似，但是返回当 stateID 是一个依赖关系时的状态。在刚才的例子中，Forward(Addr1, L) 返回 (Addr2, M)。

Fig4

Refund 方法检查帐户最近一个月的平均余额，并相应地进行退款。Blacklist 方法将一个地址标记为黑名单，如果它的最后 5 个交易中有一个是黑名单地址。

安全溯源存储

这一节讨论 LineageChain 如何增强现有的区块链存储层，从而为捕获的起源提供有效的跟踪和篡改证据。

Insights: 将原 Merkle 树中的扁平叶节点 (flat leaf nodes) 重组为 Merkle DAG。我们首先描述 Merkle DAG 结构，然后讨论它的属性。最后，我们解释了如何利用区块链执行模型来支持前向溯源跟踪。

处在叶节点的事务是扁平事务，处于根节点的事务为顶层事务，其他称为子事务。事务的前驱(predecessor)为父事务(parent)，事务的下一层称为子事务(child)。

Merkle DAG 跟 Merkle tree 很相似，但不完全一样，比如：Merkle DAG 不需要进行树的平衡操作，非叶子节点允许包含数据等。

Merkle DAG 有如下的功能：

内容寻址：使用多重哈希来唯一识别一个数据块的内容
防篡改：可以方便地检查哈希值来确认数据是否被篡改
去重：由于内容相同的数据块哈希是相同的，可以很容易去掉重复的数据，节省存储空间

Merkle DAG

设 k 是一个区块链状态的唯一标识符，它的 evolution history 是要被 track 的。

设 v 是一个能够在 k 的 evolution history 中标识状态的 unique version number。

当处于版本 v 的状态被更新时，新的版本 v’ 将严格大于 v。

在 LineageChain 中，直接使用块号作为这个块的版本号 v。

$s_{k,v}$ 表示 k 在 v 时的状态值。

$s_k^b$ 表示 k 在它 latest version 时的、在块 b 之前的状态值。

在例子中：

$k=Addr1, v=M, s_{k,v}=90$

一个有效的 transaction 需要满足的条件：

Def1

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

Fig5

Def2345

参考资料：

Fine-Grained, Secure and Efficient Data Provenance on Blockchain Systems

背景