基于Merkle树的P2P流媒体内容完整性校验

李添杰，刘 述，高 强

（1.北京航空航天大学 电子信息工程学院，北京100191；2.工业和信息化部 电信传输研究所，北京100191）

0 引 言

随着P2P流媒体应用［1，2］的日益普及，安全问题逐渐成为影响其发展的重要因素，各种攻击行为也呈现出愈演愈烈的趋势。常见的攻击方式有覆盖网络攻击、DDoS（distributed denial of service）攻击、忽略攻击和污染攻击［3］。对于普通用户，这些攻击行为严重影响了搜索和下载资源的效率。本文研究的内容完整性校验方法是为了对抗发生在数据下载阶段的假块污染攻击，一些攻击节点通过在P2P流媒体共享网络中伪造大量虚假客户端，接受其它节点的下载请求后上传虚假数据，从而导致下载时间延长并增加带宽浪费，严重的情况下会使用户无法成功下载到目标文件。

国内外对P2P文件共享系统中假块污染攻击的对抗方法已有很多研究，如针对BitTorrent网络中假块污染攻击状况的研究以及所提出的对抗策略［4］。恶意节点篡改或者伪造的编码数据更具有隐蔽性，传统的一些污染攻击对抗方法不适用于流媒体内容的完整性校验［5］。本文在研究已有科研成果的基础上，提出了一种基于Merkle哈希树的内容完整性校验方法，从而有效地对抗假块污染攻击，保证P2P流媒体系统下载过程的安全性。

该校验方法引入Merkle哈希树机制，根据P2P流媒体系统的特性和需求合理地设计了校验过程，减少启动下载所需的信息，实现快速启动。校验所需的信息不再从数据源节点获得，而是在数据下载的过程中同步获取，提高了系统的灵活性。对校验方法进行理论分析和实验测试，其结果表明该校验方法能够准确地识别虚假数据，具有提高系统启动速度、灵活性强、校验效率高的特点。

1 P2P流媒体系统中的假块污染攻击

假块污染攻击发生在P2P流媒体内容共享过程中的数据传输阶段［6］。本小节首先将对P2P流媒体内容共享系统的相关机制和工作原理进行介绍，并在此基础上对假块污染攻击的攻击原理进行分析。

1.1 P2P流媒体内容共享系统

P2P网络流媒体技术将P2P 技术引入到网络流媒体领域，和传统的客户机与服务器结构相比，P2P 是由网络中的计算机节点向其它的计算机节点分享数据，这能够充分地利用普通计算机节点的计算资源、带宽资源和存储资源，每个节点在从其它节点获取流媒体数据的同时，也可以向其它节点传送数据。

为了实现P2P流媒体系统在互联网中的大规模部署和应用，各种各样的技术被使用来改善和提高系统性能，其中一些技术是借鉴已经比较成熟并得到大规模应用的P2P文件共享系统。在P2P文件共享系统中为了提高文件的下载速度，会采用分块机制，例如在eMule／aMule中，每个文件会被首先划分为9.28 MB大小的数据分块 （part），然后进一步细分为180KB大小的数据分块 （block）；同样在BitTorrent中，每个文件会被首先划分为256KB 大小的数据分片 （piece），然后进一步细分为16KB大小的数据分块（block），在P2P文件共享系统中，客户端所下载到的目标文件的一个数据分块 （part／piece）所包含的诸多数据块（block）通常是从多个节点处获取的，当数据分块 （part／piece）下载完成时，客户端通过计算整块的检验值来验证数据的完整性，如果验证失败，客户端会丢弃整个数据分块 （part／piece）并重新下载。在P2P 流媒体服务中，为了提高流媒体数据的复用性，P2P 流媒体数据源通常也会将一个大的流媒体文件分成固定或者符合一定规则变化长度的流媒体数据块［7］。在P2P流媒体内容共享系统中采用分块机制，可以有效地加快流媒体数据的下载。而怎样进行数据块调度是P2P 流媒体技术需要解决的核心问题之一，数据块调度策略即计算机节点如何选择所需的流媒体数据块，并采用何种传输方式获得该数据块［8］。当前最为流行的P2P流媒体应用采用纯拉策略 （mesh pull）来进行数据调度，例如PPLive和PPStream。纯拉策略是指在P2P 网络中，请求同一个流媒体资源的计算机节点互为邻居节点，这其中每一个节点都要周期地向它的邻居节点发送本地拥有的数据块的指示信息，该信息表明了哪些数据块能够共享。收到指示信息的节点通过比对本地媒体数据信息，将自己缺少的数据从拥有该数据的节点处请求过来，与此同时，该节点也将自己拥有的媒体数据发送给它的邻居们。

P2P流媒体系统中所采用的这些技术极大地改善了系统性能，给网络流媒体用户带来了前所未有的性能体验。

1.2 假块污染攻击原理

在基于P2P网络的应用为我们带来巨大的便利和前所未有的性能的同时，也把它的安全威胁带到了计算机网络之中，正是由于P2P网络这种分布式的架构，使得P2P流媒体内容共享系统面临着各种各样的安全威胁。其中，假块污染攻击是对P2P流媒体系统性能影响较大的一种安全威胁。

所谓的假块污染攻击是在流媒体数据交换过程中针对分块机制的一种攻击方式，P2P 网络中的恶意节点 （该节点有可能是被动的），称之为 “污染者”，将篡改、伪造甚至含有恶意内容的流媒体数据块，通过P2P流媒体网络在较短的时间内分发到系统中的所有或者大部分的节点。

假块污染攻击，根据污染的表现形式，可分为3类：

（1）篡改部分数据：该类污染方式，通常可以表现为恶意节点将已有的流媒体数据块提取出来并进行部分的修改。

（2）替换数据：在此类污染方式中，恶意节点将从其它节点处获得的流媒体数据块替换为含有恶意内容的流媒体数据。

（3）伪造数据：该类污染方式，主要表现为恶意节点在获知P2P流媒体数据源对共享内容的分块规则之后，伪造一系列的数据块，并与P2P流媒体网络中的其它邻居节点进行交换。

流媒体的大数据量和较强的实时性，使得被污染的数据有可能在短时间内就传输到网络内的各个节点，在没有安全防范机制的P2P流媒体网络中，无法区分被污染的数据块和安全完整的数据块，用户节点接收这些假块不仅会影响到自己的数据下载和播放，还有可能将这些假块在无意识的情况下发送给其它的邻居节点，从而被动地成为了“污染者”。当P2P流媒体内容共享网络中被污染的数据量大增时，用户可能无法正常使用该系统，那么有可能会停止使用该系统。

作为流媒体内容的传输渠道，P2P 流媒体系统提供的数据的质量 （包括真实性、高质量和传输速率等），是决定P2P流媒体应用优势的最根本的指标。因而在保证一定传输速率的前提下，如何确保流媒体数据的安全是P2P 流媒体应用的一个关键问题［9］。

2 基于Merkle树的P2P流媒体内容完整性校验方法

在像BitTorrent这样的P2P 文件共享系统中，现有的文件完整性校验方法是采取密码学的方法检验文件的完整性。用户从中心索引服务器下载种子文件 （torrent file）来启动下载并利用种子文件中记录的每个文件分块的检验值来进行完整性校验［10］。这种方法需要提前生成一个种子文件，该文件中需要保存目标文件的每个数据分片 （piece）的检验值，当客户端下载完成一个数据分片时会计算该数据分片的检验值并与种子文件中对应的检验值进行比对，两个校验值相符则表示校验成功，否则校验失败，客户端会丢弃整个数据分片并重新下载。显而易见，随着目标文件的增大，数据分片会增多，那么种子文件会越来越大。

对于流媒体这种大数据量的资源来说，会产生大量的数据分块，如果采用类似于BitTorrent这种完整性校验方法，将会使种子文件的大小明显变大，这不仅意味着启动下载所需要的信息量急剧增大，而且会加剧种子服务器的负担，降低系统的灵活性，这种方法也不能扩展用于流媒体直播内容的完整性校验。

针对P2P流媒体内容共享系统中出现的假块污染攻击，本文提出了一种基于Merkle树的P2P流媒体内容完整性校验方法，用以在流媒体数据下载过程中对假块进行检测，进而发现系统中的恶意节点，保证正常的数据下载和良好的播放质量。

2.1 Merkle树的构造

Merkle提出了一种新型的树结构，这种树将二叉树与哈希算法相结合，被称作Merkle树或者Merkle哈希树。Merkle树作为一种特殊的二叉树，其集合中的元素 （哈希值）对应二叉树的叶子结点，而树中上级结点对应其左右孩子结点级联后的哈希值，逐层迭代，得到根结点。

在Merkle树中，每一个叶子结点都对应了一条从叶子结点到根结点的哈希路径 （hash path）。Merkle树是一种高效地用于数据校验的索引结构。与简单的数字签名方法相区别的是，Merkle树并不需要对每个元组都计算一个数字签名，而是基于数据分块来构建一个二叉树，二叉树的规模由数据块的数目决定，二叉树的每一个叶子结点对应一个数据分块 （哈希值），通过将叶子结点与其对应的哈希路径联合计算，然后将结果与根结点的哈希值进行比对，便可以验证数据块的正确性和完整性。

2.2 实现完整性校验的过程

根据Merkle树的定义，构造一个用于P2P流媒体内容完整性校验的哈希树，其中哈希算法使用SHA1。假设该流媒体资源共有7 块数据，即该资源分为7 个子块（Chunk）C0－C6，如图1所示。

图1 Merkle树

根据资源分块数目，需要构建相应规模的Merkle树使得叶子结点数足够容纳所有的子块，叶子结点数一般是2的整数次方。所以Merkle树宽度为8，叶子结点从左至右依次对应7个子块C0－C6，剩余的叶子结点为空并不对应子块，哈希值为全零，仅用于辅助校验而无需当做数据进行实际传输，而每个子块可以由单向哈希算法SHA1计算得到一个20B 的哈希值，根据单向哈希算法自身的特性，如果子块内容发生任何改变都会导致计算结果不同，因此每个子块对应的哈希值都是唯一的，这样每一个叶子结点都对应了一个唯一的哈希值。对于Merkle树中的每个父结点，可以由两个子结点的哈希值级联后求出哈希值作为父结点的哈希值，以此类推，直到求出根结点的哈希值H0，这一计算过程就构成了一颗二元的Merkle哈希树，树中的叶子结点对应实际子块的哈希值以及空哈希值，除此之外，非根结点的所有其它结点对应着路径哈希值H1－H6，是哈希路径的组成元素。

根哈希值也是该流媒体资源的标识 （content ID），用户只需要获得少量的信息 （根哈希值以及一些邻居节点的地址）就可以启动下载。当用户向某个邻居节点发出子块请求信息时，被请求节点除了返回相应的响应数据之外，还需要返回验证该子块所需要的路径哈希值。例如子块C0对应实际哈希值为H7，那么它所对应的路径哈希值为H8、H4、H2，则判断如下等式是否成立

SHA1 （SHA1 （SHA1 （H7＋H8）＋H4）＋H2）＝H0

如果等式成立，则完整性校验成功；如果等式不成立，则校验失败，该子块为假块，对应的邻居节点为“污染者”。

2.3 流媒体数据子块交换和校验流程

在流媒体数据子块的交换过程中利用基于Merkle树的P2P流媒体内容完整性校验方法实现对子块的完整性校验，假设用户节点从一个可信任的源节点处获得了该流媒体资源的根哈希值H0。验证任意一个子块的完整性的详细流程描述如下：

（1）首先该用户节点U0向某个邻居节点U1发送子块Ci下载请求，U1除了返回该子块数据之外，还要一起返回对该子块进行完整性校验所需要的所有路径哈希值Path（i）；

（2）用户节点U0 利用哈希算法SHA1 计算出接收到的子块的哈希值H （i）；

（3）用户节点U0利用哈希值H （i）和路径哈希值Path（i）计算得到待校验值Check（i），判断该值是否等于H0；

（4）若Check （i）等于H0，校验成功，则用户节点U0将哈希值H （i）和路径哈希值Path （i）保存，用于对后续子块的完整性校验，并继续请求下一个子块；

（5）若Check （i）不等于H0，校验失败，说明该子块为假块，该邻居节点为 “污染者”。这时，用户节点U0丢弃该子块以及对应的路径哈希值，重新寻找邻居节点请求下载该子块。

以图1构造的Merkle树为例，当用户节点U0请求下载的是数据子块C4时，用户节点U0在接收到子块数据的同时也会接收到对应的路径哈希值：H12，H6 和H1。当用户节点U0下载完该数据子块之后，将先计算出子块C4的哈希值H11，然后再结合路径哈希值依次计算各层路径哈希值，直至求得一个唯一的待校验值Check （4），将该值与H0进行比较得到校验结果。

一旦某数据子块校验通过，用户节点U0 可以将与其校验过程相关的所有路径哈希值保存下载，当一定数量的路径哈希值被保存之后，后续子块的校验过程将被简化。例如当子块C4完成校验之后，用户节点U0不需要请求子块C5的路径哈希值就可以直接对子块C5进行校验，因为此时该用户节点已经知道了C5对应的哈希值H12，并且通过子块C4的校验过程已经验证了H12 的正确性；同理，当需要对子块C6进行校验时，只需要请求H14这一个路径哈希值就可以了，因为哈希值H6 是已知的。由上述分析可以说明，缓存的路径哈希值越多，则后续子块的校验过程越简单，速度也越快。

2.4 性能分析

本文提出的基于Merkle树的P2P流媒体内容完整性校验方法对下载启动过程进行了优化。当前应用于P2P 文件共享系统中的完整性校验方法要求客户端在文件下载启动之前获得所有文件分块的哈希值，所有的这些校验信息包含在一个扩展名为torrent的文件中 （如BitTorrent中的种子文件），下载同一份文件的所有BitTorrent用户均必须从中心索引服务器上下载同一份种子文件，而这一下载行为本身是集中式的。由于流媒体资源数据量一般较大，资源数据量越大，数据子块数目越多，那么相应的种子文件也就越大。种子文件长度的增加将直接加重中心索引服务器的负担，导致系统的扩展性受到限制。另一方面，人们为了避免种子文件过大，不得不采用增加数据子块大小的方式来减少数据子块总数，这将有可能限制系统中数据子块的并行下载，对系统性能造成一系列负面影响。本文所提出的完整性校验方法精简了种子文件中的信息，只需要少量的信息 （即根哈希值和一些用户节点的地址）就可以启动下载过程，对于流媒体这种大数据量的资源来说，这种方法可以有效地缓解中心索引服务器的集中下载瓶颈，优化了下载启动过程。

对该方法在下载过程中的校验效率分析如下：在实际校验过程中，并不需要将Merkle树中所有结点对应的哈希值发送给客户端。针对一个数据子块进行完整性校验只需要发送相应的路径哈希值，而且可以从对应的路径哈希值中筛选出最优的组合进行发送。假设用户节点U0 向某个邻居节点U1发送下载请求，节点U1在发送数据子块之前会检查节点U0已经确定拥有的子块信息 （注意：该信息是节点U0通过确认消息通知所有的邻居节点），通过这个过程可以知道节点U0 已经拥有了哪些相关的路径哈希值。例如，用户节点U0已经确定拥有了子块C0和C1，那么该节点必定拥有路径哈希值H2和H4，那么可以进一步通过将已知的子结点哈希值级联计算得到路径哈希值H1 和H3。因此，在发送子块C6时，只需要随同发送路径哈希值H5和H14，用户节点U0就可以完成对该子块的完整性校验。因此缓存的路径哈希值越多，那么在后续的数据子块进行完整性校验时需要发送的路径哈希值越少，校验也就越容易，速度也越快，这样可以有效地减少校验过程中的消耗，减少完整性校验的代价。

以图1构造的Merkle树为例，当用户节点对目标子块C0－C6 （C7并不对应具体子块，为空）逐一进行下载时，下载每个子块所需要发送的路径哈希值以及所有需要发送的哈希值的个数见表1。

表1 路径哈希值

由表1数据可得，在下载过程中并不需要将Merkle树中所有结点对应的哈希值发送给客户端，只需要发送目标子块对应的路径哈希值，随着部分子块的下载并完成完整性校验，本地缓存的路径哈希值会越来越多，据此可以对之后需要发送的路径哈希值组合进行优化，最终下载所有的子块C0－C6所需要发送的路径哈希值的总数为7个。

除此之外，该校验过程引入的SHA1计算量是以P2P的方式分散在各个节点上，所带来的时间开销对整个流媒体内容共享系统整体的性能影响可以忽略，因此该方法带来的是较低的网络延迟。

3 结束语

本文提出的基于Merkle树的P2P流媒体内容完整性校验方法可以有效地检测出流媒体数据下载过程中的假块。该方法只需要少量的信息就可以启动下载，提高了启动效率。通过减少校验值在网络传输中的大小，提高了子块校验的效率，降低了网络延迟。该方法只是针对P2P 流媒体内容共享中的点播过程进行完整性校验，针对流媒体直播的完整性校验还有待进行进一步的研究扩展。

［1］YANG Ge，LIAO Jianxin，ZHU Xiaomin，et al.Survey of key technologies of the distribution system for streaming media［J］.Acta Electronica Sinica，2009，37 （1）：137－145 （in Chinese）.［杨戈，廖建新，朱晓民，等.流媒体分发系统关键技术综述 ［J］.电子学报，2009，37 （1）：137－145.］

［2］QIN Fenglin，LIU Ju.Key technologies in P2P media streaming ［J］.Acta Electronica Sinica，2011，39 （4）：919－927（in Chinese）.［秦丰林，刘琚.P2P网络流媒体关键技术 ［J］.电子学报，2011，39 （4）：919－927.］

［3］Haridasan M，Renesse VR.Defense against intrusion in a live streaming multicast system ［C］／／Proceedings of IEEE International Conference on Peer－to－Peer Computing.Cambridge：P2P，2006：185－192.

［4］Dhungel P，Wu D，Ross WK，et al.Measurement and mitigation of BitTorrent leecher attacks［J］.Computer Communications，2009，32 （17）：1852－1861.

［5］ZHAO Xin.Research on key technologies of peer－to－peer streaming media distribution ［D］.Beijing：Beijing University of Posts and Telecommunications，2010 （in Chinese）.［赵鑫.P2P流媒体内容分发的关键技术研究 ［D］.北京：北京邮电大学，2010.］

［6］SHI Jiantao，ZHANG Hongli，FANG Binxing.Study on the countermeasures of BitTorrent fake block attack ［J］.Chinese Journal of Computers，2011，34 （1）：15－24 （in Chinese）.［史建焘，张宏莉，方滨兴.BitTorrent假块污染攻击的对抗方法研究 ［J］.计算机学报，2011，34 （1）：15－24.］

［7］ZHOU Shenbao.Research on P2Pstreaming media security ［D］.Hunan：Central South University，2009 （in Chinese）.［周神保.P2P流媒体安全研究［D］.湖南：中南大学，2009.］

［8］ZHANG Mingjun，PENG Ya，YU Wenjing.Research on P2P streaming media service scheme and its key technologies ［J］.Computer Engineering，2013，39 （1）：125－139 （in Chinese）.［张明军，彭娅，俞文静.P2P 流媒体服务方案及其关键技术研究 ［J］.计算机工程，2013，39 （1）：125－139.］

［9］WU Jie.Research on key technology of P2Pstreaming content delivery and service ［D］.Shanghai：Fudan University，2008（in Chinese）.［吴杰.P2P流媒体内容分发与服务关键技术研究 ［D］.上海：复旦大学，2008.］

［10］YAO Ruhao，LIU Bingshuang，QU Deshuai，et al.Smartblacklisting：An efficient methodology for mitigating fake block attack in P2Pfile－sharing systems［J］.Journal on Communications，2013，34 （8）：88－94（in Chinese）.［姚汝颢，刘丙双，曲德帅，等.Smart－blacklisting：P2P文件共享系统假块污染攻击对抗方法［J］.通信学报，2013，34 （8）：88－94.］