基于Merkle山脉的数据可信溯源方法

刘 炜，张聪，佘维，宋轩，田钊*

（1.郑州大学网络空间安全学院，郑州 450002；2.互联网医疗与健康服务河南省协同创新中心（郑州大学），郑州 450052）

0 引言

随着物联网［1］、大数据等信息技术的发展，数据呈现爆炸性增长［2］。在大数据时代下，数据作为重要资产，背后的价值日益凸显。数据共享可以实现数据价值的交换和利用，为了防止数据恶意篡改和造假等行为，需要对共享数据的真伪、数据的质量进行监管和存证，即对数据的演变过程进行记录，便于日后产生异议时进行数据溯源［3］。溯源是指记录、访问、验证数据在整个流转过程中的演变，从数据的生产源头到最终的流转结果。通过对数据溯源，防止记录在流转过程中被非法篡改，保证数据的安全性、真实性和可靠性［4］。目前，常见的溯源方法有标注法，虽然可以达到数据溯源的目的，但在大数据时代下，需要极大的存储空间，给存储系统带来巨大的存储压力；此外，现有的存储技术多采用中心化数据库，一旦中央服务器遭受恶意攻击，系统会出现单点故障［5-6］，且中心化的存储方式由于监管力度不够，存在利益驱使而造假数据，使数据溯源过程变得困难且可信度不高。在物联网系统中，大多数是轻量级节点，节点的可用资源有限，而数据溯源过程中验证需要消耗大量时间和设备资源，对轻量级节点来说是一个严峻的挑战。

区块链［7］技术源于2008 年，它是一个分类账本，具有不可篡改、分布式存储、去中心化等特性。区块链独特的链式结构，使每一个区块都包含前一区块的哈希，提供了可追溯和可验证性，解决了传统溯源方法中存在的问题。文献［8］中提出了密文策略基于属性加密（Ciphertext-Policy Attribute-Based Encryption，CP-ABE）的溯源方案，基于策略的加密算法使区块内容可以动态更新，保护数据隐私的同时实现溯源信息共享；文献［9］中提出了一种基于联盟链和IPFS（Inter-Planetary File System）的质量数据追溯方案，将加密的质量数据和对应的密钥存储在IPFS 中，实现质量数据的追溯过程；文献［10］中基于区块链提出了一种疾病信息跟踪方法，以2019 冠状病毒病为例，形成疾病信息时间序列区块链，便于追踪传染病传播途径；文献［11］中基于区块链提出了一个食品追溯模型，通过食品质量指数算法生成食品质量数，存储在区块链中，并结合产品标识符实现可靠的食品溯源；文献［12］中针对多层次纺织品供应链，提出了一个基于区块链可追溯框架，智能合约实现特定的交易规则，并验证该区块链系统的可行性；文献［13］中提出了一种双联盟链存储结构，使用区块链记录网络中动态数据的流转过程，通过公钥机制完成数据的安全传输，实现对数据的追溯；文献［14］中以飞机配件为例，借助区块链技术，实现一个追溯系统，通过该系统可以实现配件供应链中各个组织的信息共享和数据追溯；文献［15］中基于区块链技术设计了一个农产品供应链的信息存储和查询追溯系统，结合数据库和区块链实现链上链下双存储，缓解区块链存储压力；文献［16］中提出了一种基于联盟链的农产品溯源方法，采用拜占庭容错算法（Practical Byzantine Fault Tolerance，PBFT）减少共识时间，实现高效的溯源过程。

上述文献将区块链应用于溯源场景，解决了传统溯源系统中数据不透明、追溯结果不可信、数据库中心化程度高、信息孤岛等问题，实现了在农业、工业等领域的数据可信溯源，但提出的区块链溯源方案，没有考虑到数据追溯验证时资源消耗和效率问题。由于物联网系统中的设备多为轻量级节点［17］，这些节点计算能力和存储资源有限，在进行数据追溯时，保存海量的物联网数据较为困难，溯源验证过程效率低下，即使基于区块链技术，只需保存区块头信息，对资源有限的轻量级物联网节点来说，也是一个严峻的考验。随着区块链网络高度的增加，溯源时需要下载的数据量增大，对验证节点的存储空间和资源要求较高，因此不适用于资源有限的物联网场景。

综上所述，本文提出一种基于Merkle 山脉（Merkle Mountain Range，MMR）［18］的数据可信溯源方法MMRBCV（Merkle Mountain Range BlockChain Verification），引入IPFS，提高系统存储容量，缓解区块链存储压力；设计双链结构，源数据与数据流转记录分开存储，提高数据的隐私性和安全性；在区块中引入Merkle 山脉（MMR）减少验证过程中所需下载的数据量和验证时间，解决轻量级物联网节点因资源受限存在的验证问题。

1 相关技术

1.1 区块链

区块链网络中节点相互独立，共同参与数据管理和交易记录，部分节点出现宕机问题不会影响整个网络的运行，可以避免单点故障。

区块由区块头和区块体组成：区块头包含交易、时间戳、难度值、目标散列、Merkle 树根（Merkle Tree Root，MTR）等关键字，通过保存前一区块的哈希，形成一种链式结构，为区块链提供了可追溯性；区块体包含网络中的交易，采用Merkle树（Merkle Tree，MT）的结构存储。区块结构如图1所示。

图1 区块结构Fig.1 Block structure

区块链根据其开放程度和应用场景，可以分为公有链、联盟链和私有链3 种［19］，如表1 所示。公有链去中心化程度最高，网络中的所有节点可以自由地加入或退出，节点身份匿名，数据的公开性和透明性强；联盟链去中心化程度相对较弱，只有经过授权的节点才可以加入网络中，节点身份需要通过审核，多用于商业机构，由Linux 基金会发起的Hyperledger Fabric 就是典型的联盟链［20］；私有链中心化程度最高，开放程度最低，只有私人或者某一特定组织有使用权限，一般多用于企业内部。

表1 区块链类型Tab.1 Blockchain types

1.2 IPFS

IPFS 是一个面向全球、点对点的分布式的文件系统［21］。它基于BitTorrent 协议进行文件分发，上传到IPFS 的文件会返回一个哈希值作为CID（Content-ID）。当文件内容被修改时，对应的哈希值也会发生变化，保证文件与CID 一一对应。对于已经存在的数据文件，再次上传时不会返回新的哈希值。IPFS 存储如图2 所示。

图2 IPFS存储Fig.2 IPFS storage

IPFS 存储文件时步骤如下：

1）把文件拆分成若干个256 KB 大小的数据块，如果文件大小没超过256 KB，则不执行此步骤。

2）对拆分后的文件数据块1，2，…，n，逐个进行哈希运算，得到数据块对应的哈希值hash(1)，hash(2)，…，hash(n)。

3）将所有的hash(1)，hash(2)，…，hash(n)拼凑，构成一个数组，将该数组再次进行哈希运算，得到文件对应的hash(file)，hash(file)=hash(∑hash(i))（i=1，2，…，n），即文件的CID，再次查找只需通过该CID 即可在IPFS 中找到相关文件。

本文使用IPFS 作为数据存储层，缓解区块链存储压力，提高存储容量。

1.3 Merkle山脉

Merkle 山脉是Peter Todd 提出的变种数据结构［22］，是一种特殊的Merkle 树。在构造数据结构时，Merkle 树是一棵完美二叉树，而Merkle 山脉不一定是完美二叉树。当Merkle 树构建完成后，不可再对数据进行增加或者删除，而Merkle 山脉可以动态地进行数据的追加，不需要重新构建该数据结构。Merkle 树和Merkle 山脉都是由叶子节点进行哈希运算，最后生成该数据结构。Merkle 山脉也可以验证一个叶子节点是否存在该结构之中。Merkle 树和Merkle 山脉两种数据结构中已有的叶子节点中数据发生改变都会导致父节点的改变，所以MTR 的值和Merkle 山脉根（Merkle Mountain Range Root，MMRR）的值也会发生变化。如果MTR 或MMRR 中存储的哈希值没有变，则说明叶子节点存储的数据没有改变，因此广泛应用于区块链中进行交易验证。

本文在区块中引入Merkle 山脉结构、轻量级物联网节点进行数据溯源时，只需下载链上的一个最新区块即可完成数据溯源中的验证过程。

2 数据可信溯源方法

本文设计基于Merkle 山脉的数据可信溯源方法，以IPFS作为数据层，提出数据私有链（Data Private BlockChain，DPBC）和记录联盟链（Record Consortium BlockChain，RCBC）双链模型，保护数据隐私性，提高存储安全性。在此模型上设计一种Merkle 山脉区块结构，用于物联网系统中轻量级节点进行数据溯源时的验证。

2.1 双链架构

数据溯源过程既要满足溯源数据真实可靠，数据流转过程公开透明，又要保证数据追溯过程中的隐私性和安全性［23］。本文提出基于联盟链和私有链的双链溯源模型，如图3 所示。同一局域网的物联网设备作为私有链节点，包括全节点和轻节点，DPBC 的作用是实现数据的可靠存储。物联网节点采集的源数据上传到IPFS 中，IPFS 返回文件对应的CID，文件CID 和文件摘要作为私有链中的交易，存储在Merkle 树的叶子节点里，便于后续对数据的查询和追溯。私有链的中心化程度高，只有少数节点可以访问，保证链上数据的隐私性，区块链不可篡改的特性以及IPFS 的唯一对应性，保证链上存储的数据文件不可篡改。

图3 双链结构Fig.3 Double-blockchain structure

数据私有链中的物联网全节点组成联盟成员，构成联盟链。RCBC 主要功能是溯源信息的查询共享，记录数据文件的流转过程。通过智能合约，物联网全节点将数据文件的操作记录同步到联盟链中，通过共识算法达成一致，以Merkle树的结构存储在RCBC 的区块体中，第三方对数据文件的操作产生争议时，可以通过联盟链对数据以及结果进行追溯，获取区块内容，保证数据流转记录的安全可信。

联盟链和私有链中均引入Merkle 山脉结构（区块结构在2.2 节进行详细说明），把当前高度之前的所有区块头作为Merkle 山脉的叶子节点存储：一方面实现区块的锚定，保证该高度前的所有区块存储内容不可篡改；另一方面引入Merkle 山脉结构，便于轻量级物联网节点进行溯源数据时的快速高效验证。

采用双链结构的设计：一方面可以提高区块链网络的性能，数据流转记录和数据分开存储的方式，减轻网络中的通信负担，提高溯源查询效率；另一方面私有链可以保证链上存储数据的隐私安全。IPFS 作为模型的数据层，可以将大量的物联网设备采集的数据存储在IPFS中，缓解区块链的存储压力，实现数据链上链下的高效存储。IPFS 和区块链结合，提高了系统的存储能力和安全性，解决了区块链扩展性不足的问题。

2.2 MMR区块结构

本文对区块结构进行了改进，设计一种新的Merkle 山脉区块结构如图4 所示。区块包含区块头和区块体两部分，区块头中新增字段MMRR，区块体中新增Merkle 山脉结构。区块头包含版本号、时间戳、难度值、目标散列、前一区块哈希、MTR 和MMRR，区块体由Merkle 树和Merkle 山脉组成。Merkle 树中的叶子节点存储区块链网络中的交易信息，DPBC 中Merkle 树的叶子节点存储文件CID 和文件摘要，RCBC 中Merkle 树的叶子节点存储文件流转过程。Merkle 树的叶子节点经过哈希计算，得到MTR，并将该数据锚定在区块头中。Merkle 山脉中的叶子节点存储区块链上的区块头，DPBC 和RCBC 的叶子节点均为该区块前的所有区块头，经过哈希计算得到MMRR。通过Merkle 树证明和Merkle 山脉证明可验证Merkle 树和Merkle 山脉中的数据是否被篡改。

图4 Merkle山脉区块结构Fig.4 Block structure based on Merkle mountain range

随着区块链网络的应用，区块高度线性增长。对于计算及存储能力较小的轻量级物联网节点来说，同步区块链上所有的区块头日志，会消耗大量节点资源和时间。如果在区块中引入Merkle 山脉结构，通过MMRR 可以验证包含该交易的区块是否在网络中的最长合法链上，用来验证区块头的合法性，可以减少区块链网络中验证时造成的资源浪费、缩短验证时间，降低轻量级物联网节点的工作压力。当链上有新的区块生成时，只需将新区块作为Merkle 山脉一个叶子节点，动态追加即可。

2.3 Merkle山脉证明

数据溯源过程中需要对Merkle 山脉叶子节点存储的数据进行验证，确保数据未被篡改、真实可信，即Merkle 山脉证明［22］。把Merkle 山脉证明集合进行哈希计算，记为MMRR'，将MMRR'与区块中存储MMRR 哈希值进行对比：如果相同，则表明数据真实可信未被篡改；如果结果不同，根据哈希计算的不可逆性，表明待验证叶子节点数据被恶意篡改，数据不可信。Merkle 山脉证明过程为：

1）从待验证的目标节点开始，向上层父节点查找，到目标节点所在Merkle 树的MTR 结束，查找所经过节点集合称为Merkle 山脉路径；

2）查找Merkle 山脉中所有子树的MTR；

3）将Merkle 山脉路径中的节点和第2）步中中子树的MTR 构成一个证明集合，即Merkle 山脉证明集合；

4）对Merkle 山脉证明集合进行哈希运算得到MMRR'，与区块头中的MMRR 字段比较是否一致，完成Merkle 山脉证明。

以图5 中叶子节点L8 为例说明Merkle 山脉证明过程，要证明L8，就需要得到图5 中虚线圈住的节点哈希值，其中hash（）表示取哈希值。

图5 Merkle山脉结构Fig.5 Structure of Merkle mountain range

1）计算叶子节点L8 哈希值H'(8)、H'(8)=hash(L8)，获取Merkle 山脉路径中叶子节点L9、L12 哈希值H(9)、H(12)，H(9)=hash(L9)、H(12)=hash(L12)。

2）获取Merkle 山脉中叶子节点L8 所在子树中的一个右子根H(10，11)，即H(10，11)=hash(H(10)&H(11))。

3）将叶子节点L8 的哈希值H'(8)、叶子节点L9 的哈希值H(9)，哈希运算得H'(8，9)=hash(H'(8)&H(9))。

4）将步骤3）计算结果H'(8，9)与步骤2）H(10，11)，再次进行哈希运算，计算得到H'(H'(8，9)，H(10，11))，即H'(H'(8，9)，H(10，11))=hash(H'(8，9)&H(10，11))。

5）获取图5 中，Merkle 山脉结构中最左侧一个完美二叉子树的根，即H(((0，1)&(2，3))&((4，5)&(6，7)))。

6）将数据H(12)、H(((0，1)&(2，3))&((4，5)&(6，7)))、H'(H'(8，9)，H(10，11))哈希得到MMRR'，如式（1）所示：

7）将计算得到的MMRR'与存储在区块中的MMRR进行对比，如果MMRR'=MMRR，证明节点L8 数据未被篡改。

上述证明过程流程如图6 所示。

图6 Merkle山脉证明流程Fig.6 Flow of Merkle mountain range proof

2.4 Merkle山脉区块溯源方法

本文提出一种基于Merkle 山脉的数据溯源方法，溯源方法流程如图7 所示，其中K表示当前网络中最新的区块高度；k表示待验证的区块高度。当需要对高度为k(k＜K)的区块中的数据流转记录（Data Flow Record，DFR）进行验证时，轻量级物联网节点只需要从网络中同步第k个区块以及最新高度K的区块头即可完成验证，具体内容如算法1 所示。当需要验证通过第k(k≤K)个区块中的交易时，首先通过区块高度为k的区块头中的MTR可以验证区块体中的数据是否存在且正确；其次通过第K个区块头中的MMRR 可以验证第k个区块的MTR 是否正确，即验证第k(k＜K)个区块是否在最长合法链上。通过上述两步即可完成验证过程而无需下载整条链的区块头，从而节省存储空间，减少轻量级物联网节点能源消耗。

图7 MMRBCV溯源流程Fig.7 Flow chart of MMRBCV traceability

验证步骤如下：

1）物联网系统中的轻量级节点，从DPBC 网络中全节点的本地账本同步高度为k的区块信息，从k区块中获得该区块中MT 的MTR。

2）节点通过哈希计算得到MTR'，如果MTR'=MTR，则证明该交易包含在区块中且正确。

3）需要进行数据验证的物联网系统轻量级节点，从RCBC 网络中全节点的本地账本，同步当前最新高度K的区块信息，从K区块获得MMRR。

4）轻量级节点通过哈希计算得到，如果MMRR'=MMRR，则证明高度为k（k＜K）的区块在网络中的最长合法链上，完成验证。

上述过程如算法1 所示。

算法1 数据溯源方法。

输入 数据流转记录DFR；

输出 追溯结果true/false。

上述验证过程先验证某笔交易包含在高度为k的区块中，再验证高度为k的区块在最长合法链上，从而完成数据追溯过程。

3 实验与分析

为评估本文提出的数据追溯方法性能，进行仿真实验，使用Python 语言，对SPV（Simplified Payment Verification）和MMRBCV 方法进行对比分析。实验环境为Intel Core i7-4790 CPU 和8 GB 内存，操作系统为64 位Windows 10。

3.1 数据下载量对比分析

数据下载量是指节点进行数据追溯验证时，需要在本地保存的数据大小。数据下载量与节点的资源消耗成正比。区块链高度越高，轻量级物联网节点需要下载的区块头数据量越大，需要的节点资源越多。本实验对比分析相同区块高度下，节点使用SPV 需要下载的数据量和MMRBCV 需要下载的数据量。为讨论区块数量对资源消耗的影响，选择区块高度为1 000、2 000、3 000、10 000、20 000、30 000、60 000、100 000、150 000、200 000 时，SPV 和本文提出的MMRBCV 两种方法进行验证时的数据下载量，实验结果如表2 所示。

表2 SPV和MMRBCV的数据下载量Tab.2 Data downloaded by SPV and MMRBCV

随着区块链高度增加，SPV 和MMRBCV 所需下载的数据量都会增大；但SPV 进行数据验证时，需要下载整条链的区块头信息，本文方法只需要下载最长合法链中的最新区块。从表2 中数据可以看出，在相同的区块高度下，MMRBCV 方法比SPV 下载数据量小，一定程度上可以减少轻节点的资源消耗。

3.2 验证时间对比分析

验证时间是指验证某笔交易所需要的时间。验证时间是溯源过程中一个重要指标，时间越短，溯源效率越高。本文中验证时间测试的是从提交包含某笔交易的MTR 到查找到该哈希值之间的时间。为讨论不同数量级区块对验证时间的影响，实验选择区块高度为1 000、2 000、3 000、10 000、20 000、30 000、60 000、100 000、150 000、200 000 时，对比SPV和MMRBCV 数据验证的时间。

实验结果如图8 所示，当区块链网络中区块数量增多时，SPV 和MMRBCV 方法的验证时间会逐步增加，相比之下，SPV 验证时间长，这是因为该方法需要从最新高度区块开始向下遍历，直到追溯到目标区块。MMRBCV 方法验证时间短，这是由于MMRBCV 只需获取Merkle 山脉的验证路径计算得到MMRR，与最新高度区块头中哈希值进行对比。当区块高度为200 000 时，SPV 的最大时间开销约为36 ms，MMRBCV 的最大时间开销约为10 ms，验证时间较SPV 缩短了约72%，提高数据溯源过程中的验证效率。

图8 SPV和MMRBCV的验证时间Fig.8 Verification time of SPV and MMRBCV

3.3 区块高度对验证时间的影响分析

Merkle 山脉是一种可变的数据结构，结构中的节点数量会影响结构中二叉树的个数和形状，当数据中的节点数据量为2n时，Merkle 山脉可以组成一个完美二叉树的结构，即和Merkle 树的结构相同，Merkle 山脉中的结构包含多个二叉树。为讨论Merkle 山脉结构对数据溯源效率的影响，从树的高度和是否为完美二叉树两个方面验证，当树高度为14、15、16 时，分别讨论Merkle 山脉为完美二叉树和非完美二叉树两种情况，即214-1、214、215-1、215、216-1、216，对应叶子节点个数为16 383、16 384、32 767、32 768、65 535、65 536 时完成一次验证所需的时间，实验结果如表3 所示。

表3 不同区块高度时的验证时间Tab.3 Verification time with different block height

以Merkle 山脉高度是15 为例，测试Merkle 山脉叶子节点个数为30 000 至34 000 时，完成一次验证所需的时间，实验结果如图9 所示。

图9 高度为30 000～34 000时MMRBCV的验证时间Fig.9 MMRBCV’s verification time with height of 30 000 to 34 000

数据验证时间与Merkle 山脉结构有关，当Merkle 山脉可以组成一个完美二叉树时，完成一次验证过程所需的时间，比Merkle 山脉是一个非完美二叉树的验证时间短，即使非完美二叉树结构的Merkle 山脉叶子节点少。因为Merkle 山脉是一个完美二叉树时只需要对整棵树进行验证，而Merkle 山脉是非完美二叉树时，需要对多个数据结构进行查找验证，所以验证时间比Merkle 山脉是一个完美二叉树时的验证时间长。

4 结语

针对物联网系统中数据量大、处理速度快、轻量级节点数量多等特点，以及基于区块链的溯源系统中轻量级物联网节点验证困难、资源浪费等问题，本文提出一种基于Merkle山脉的物联网数据溯源方法MMRBCV。将IPFS 作为系统的数据层存储数据，实现链上链下存储，缓解区块链面向物联网海量数据时的存储压力；双链结构实现数据安全存储；基于Merkle 山脉结构设计适用于物联网系统的区块结构，减少轻量级物联网节点对溯源数据验证时下载的数据量和验证时间，提高验证效率。Merkle 山脉一定程度上可以节省轻量级物联网节点资源，提高验证效率；但引入新的数据结构，区块内容增多，加重了网络中全节点的存储压力，在未来工作中，将考虑存储性能方面的问题。