`
vvggsky
  • 浏览: 68047 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

BitTorrent中的数据块校验方式改进:Merkle Hashing Tree

阅读更多
大家都知道,目前BT应用的发展具有一个非常显著的趋势,那就是用来交换电影、游戏、ISO等大尺寸的数据文件。然而我们也能够观察到另一个事实,那就是:下载文件所对应的索引文件(.torrent)也越来越大,越来越难以下载;这是因为在索引文件中保存了被下载文件中所有数据块的20字节SHA1校验值,而文件越大,数据块越多,则.torrent文件越长(块数=文件长度/数据块长,Bit Torrent标准协议建议块长一般不超过512KB)。

索引文件长度的膨胀将直接加重索引服务器的下载负担,因为所有BT用户均必须从服务器上下载同一份.torrent文件,而这一下载行为本身是集中式的,因而导致系统的扩展性受到较大限制,尤其是用于交换热门资源时;另一方面,为避免索引文件过大,人们在发布种子、制作索引文件时不得不采用增加其基本数据块长度(比如2MB)的方式来减少数据块总数,这将有可能对端对端数据交换性能造成一系列负面影响:因为块长越小,越能帮助我们及时地发现传输错误,试想在2MB块长的情况下,用户直到下载完整个数据块时才通过校验发现传输有误,然后不得不再次重传整个2MB块,这显然较块长为512KB时更加浪费带宽和时间。归根到底,导致上述麻烦的根本原因在于这么一个事实:“.torrent中包含了所有数据块的SHA1校验信息”。

有什么办法让我们既能获得较小的块长而又能减少索引文件长度?Merkle哈希树校验方式为我们提供了一个很好的思路,它试图从校验信息获取及实际校验过程两个方面来改善上述问题。先说说什么是哈希树,以最简单的二叉方式为例,如下图所示,设某文件共13个数据块,我们可以将其padding到16(2的整数次方)个块(注意,padding的空白块仅用于辅助校验,而无需当作数据进行实际传输),每个块均对应一个SHA1校验值,然后再对它们进行反复的两两哈希,直到得出一个唯一的根哈希值为止(root hash, H0),这一计算过程便构成了一棵二元的Merkle哈希树,树中最底层的叶子节点(H15~H30)对应着数据块的实际哈希值,而那些内部节点(H1~H14)我们则可以将其称为“路径哈希值”,它们构成了实际块哈希值与根哈希值H0之间的“校验路径”,比如,数据块8所对应的实际哈希值为H23,则有:SHA1(((SHA1(SHA1(H23,H24),H12),H6),H1)应该等于H0。当然,我们也可以进一步采用n元哈希树来进行上述校验过程,其过程是类似的。



采用Merkle哈希树校验方式能够极大地减小.torrent文件的尺寸,这是因为,一旦采用这种方式来校验数据块,那么便没有必要在.torrent文件中保存所有数据块的校验值了,其中仅需保存一个20字节的SHA1哈希值即可,即整个下载文件的根哈希值H0。想象一下一个3、4GB的文件,其对应.torrent文件却只有100-200字节的样子?heh

下面,让我们来看看其数据块交换及校验的详细过程:

以下载某大文件F为例,为启动BT交换,每一个client均必须从索引服务器中下载F所相应的.torrent文件,从而得到文件长度、数据块长及根哈希值H0等必要信息;
任一client均可通过轮询Tracking服务器或者是DHT方式来定位其他参与交换F数据的peer,进而与之建立TCP连接进行P2P文件交换,其定位peer的方式基本上没有什么改变。
当client从某一peer下载一个数据块时,它将事先向peer发出相应的校验查询请求,要求对方提供校验当前下载块所需的路径哈希值,这一过程可以很方便地通过扩展标准的Peer Wire Protocol实现。以上图为例,当client下载的是数据块8时,在下载开始之前,它将要求peer提供校验块8所需的全部路径哈希值:H24、H12、H6和H1;
当client下载完某数据块之后,它将对其进行哈希树校验;仍以校验块8为例,client将首先计算出块8的哈希值H23',然后再根据peer所提供的信息依次计算各层路径哈希值,直至求得一个唯一的根校验值H0',如果H0'等于.torrent文件中的H0,则数据块下载无误,校验通过;反之则校验失败。
一旦某数据块校验通过,与其哈希树校验过程相关的所有路径哈希值均可以作为cache缓存下来,而不管其究竟是从peer查询所得的,还是由client自身计算所得的;但值得注意的是,如果该数据块的校验未通过,则其所有相关的路径哈希值均不能被cache,而只能被废弃,因为此时我们无法保证peer所提供的路径哈希值的正确性(不能排除peer故意提供错误路径哈希值和哈希值传输出错的可能)。例如,所有与块8校验相关的路径哈希包括:H24、H12、H6、H1、H11、H5、H2,其中前面4个经查询peer所得,而后面3个则由client自己计算所得。块8验证的结果将决定这7个路径哈希是否可信及是否能被cache。
当一定数量的路径哈希值被缓存之后,后继数据块的校验过程将被极大简化。此时我们可以直接利用校验路径上层次最低的已知路径哈希值来对数据块进行部分校验,而无需每次都校验至根哈希值H0,这主要是因为:某一路径哈希值被cache这一事实本身便能够证明其是可信的;例如,在块8校验完成之后,client无需进行额外的peer查询便可以直接对块9进行校验,因此它已经知道了H24的值,并且通过块8的校验过程验证了H24的正确性;而当client需要对块10进行校验时,它仅需向peer查询H26一个校验值即可,由于我们已经知道了H12值,因此对块10的校验仅需2次SHA1哈希即可:一次是计算块哈希H25,一次是计算SHA1(H25,H26),并比较其等不等于H12。同理,当需要验证块12时,由于已知H6,client仅需查询2个路径哈希(H28和H14)和3次SHA1计算(H27、SHA1(H27,H28)和SHA1(H13,H14))即可。缓存的路径哈希值越多,则后继数据块校验越容易,速度也越快。
为了进一步提高校验效率,可以考虑在.torrent文件上再做做文章:令其保存整个哈希树中最上面的若干层路径哈希值,而不仅仅只是一个根哈希值H0,底层的路径哈希值则仍然依靠询问peer或client自身计算所得,从而实现.torrent文件尺寸与校验效率的有效折衷。
最后再来看看上述算法的时空效率如何。假设某文件的总块数为M,将其padding至N个块(N=2^p),块长为K,不难看出:

为了校验整个文件,共需缓存Sum(2^i):i=0 to p,即2N-1个20字节的SHA1哈希值(包括根哈希值、所有路径哈希值和块哈希值)。以512KB为块长的一个4GB的文件为例,M=8000,则N=8192,p=13,所需存储空间为(2*8192-1)*20=327660 Bytes=319KB,其缓冲区较普通校验方式翻倍,但即便如此,校验所需的数据量仍完全可以接受,即使在最糟糕的情况下:完全不用cache、全部依赖peer查询来获得这些校验值,也无非总共增加了1个基本块不到的流量而已,而且这些流量还是通过P2P方式得到的。
在无校验失败的理想情况下,校验整个文件共需M次块长为K的SHA1计算,和N-1次长度为20字节的SHA1运算。即,以哈希树方式校验块长512KB的4GB文件,共需进行8000次长度为512KB的SHA1计算,同时外加8191次长为2*20字节的路径哈希计算,与普通校验方式相比,后者是哈希树额外引入的开销,但由于每次路径哈希的计算量非常小,其影响几可忽略。
综上所述,通过采用哈希树校验方式,我们可以将诸多校验所需哈希值的获取工作分散在P2P数据交换时捎带进行,而不是从.torrent文件中集中获取,从而有利于缓解索引服务器集中下载瓶颈,优化Peer to Peer数据传输性能;在实现上述目的的同时,哈希树校验机制仍能保证以P2P方式获取的校验信息的可靠性,在小块长的情况下,恶意peer几乎无法通过故意提供错误路径哈希值的方式来实现有效的服务拒绝攻击。采用这种方式,我们所需付出的额外代价主要包括几近1倍的校验缓存空间及其SHA1计算量的增长,但是经过简要分析不难看出其实际影响不甚明显,这对于换取较小的块长、提高大文件P2P交换效率而言是值得的。Merkle哈希树校验方式与分布式哈希表技术势必能够帮助BitTorrent协议进一步克服自身的非结构化缺陷,取得更大的应用发展。
  • 大小: 8 KB
分享到:
评论

相关推荐

    无线电能传输中电动汽车充电的Matlab与Maxwell仿真:线圈结构与补偿拓扑优化

    内容概要:本文详细介绍了无线电能传输技术在电动汽车充电中的应用,特别是在Matlab和Maxwell中的仿真过程。首先讨论了SS补偿拓扑的Matlab仿真,展示了如何设置线圈参数、进行谐振匹配以及通过相量分析判断软开关状态。接着探讨了Maxwell中DD线圈的3D电磁场仿真,强调了自定义网格划分和涡流场计算的重要性。随后,文章深入研究了多线圈阵列仿真,揭示了不同线圈布局对耦合系数的影响,并提出了LCC补偿拓扑的应用。此外,文中还分享了许多实用技巧,如避免常见错误、优化仿真参数以及处理实际测试中的问题。 适合人群:从事无线电能传输研究的技术人员、研究生及以上学历的研究人员。 使用场景及目标:适用于需要深入了解无线电能传输技术及其仿真的研究人员和技术开发者,旨在帮助他们掌握Matlab和Maxwell的具体应用,提高仿真精度和效率。 其他说明:文章不仅提供了详细的代码示例和仿真步骤,还分享了作者的实际经验和教训,使读者能够更好地理解和应对仿真过程中遇到的问题。

    用户增删改查功能的前端页面,添加了vue渲染代码

    用户增删改查功能的前端页面,添加了vue渲染代码。

    计算机课程设计相关资源

    计算机课程设计相关资源

    基于51单片机protues仿真的猜数字游戏(仿真图、源代码、AD原理图、流程图)

    基于51单片机protues仿真的猜数字游戏(仿真图、源代码、AD原理图、流程图) 猜数字游戏 1、通过随机数实现该游戏; 2、按下K1键启动游戏并随机生成一个0~9的数字 3、通过矩阵按键输入你的数字,输入数字小于随机生成的数字则显示小于该数,大于的时候显示大于该数,直到相等为止。 4、仿真图、源代码、AD原理图、流程图;

    基于MATLAB的FOC滑膜观测器与锁相环(MATLAB 2021b)实现及硬件移植注意事项

    内容概要:本文详细介绍了利用MATLAB 2021b搭建的FOC滑膜观测器(SMO)与锁相环(PLL)的仿真模型及其在M4硬件平台上的实现方法。文中首先展示了SMO的核心代码,解释了如何通过滑模面计算和符号函数处理来估算反电动势,并讨论了PLL用于速度提取的具体实现。接着探讨了仿真环境中直接0速闭环启动的效果以及实际硬件实现时所需的开环启动策略。此外,文章还分享了多个调试过程中遇到的问题及解决方案,如相位跳变、高频振荡、电流环参数调整等。 适合人群:从事电机控制研究的技术人员,尤其是对无感FOC感兴趣的工程师。 使用场景及目标:适用于希望深入了解FOC滑膜观测器和锁相环的工作原理并尝试将其应用于实际项目的开发者。目标是掌握SMO+PLL组合的设计思路和技术细节,同时了解硬件移植时需要注意的实际问题。 其他说明:文中提供了大量实用的代码片段和调试经验,对于想要快速入门或优化现有系统的读者非常有帮助。特别强调了仿真与现实之间的差异,提醒读者注意参数选择和滤波器设计等方面的不同之处。

    汽车美容员工手册.doc

    汽车美容员工手册.doc

    基于PSO算法的配电网分布式光伏选址定容优化及其Matlab实现

    内容概要:本文详细介绍了利用粒子群优化(PSO)算法解决配电网中分布式光伏系统的选址与定容问题的方法。首先阐述了问题背景,即在复杂的配电网环境中选择合适的光伏安装位置和确定合理的装机容量,以降低网损、减小电压偏差并提高光伏消纳效率。接着展示了具体的PSO算法实现流程,包括粒子初始化、适应度函数构建、粒子位置更新规则以及越界处理机制等关键技术细节。文中还讨论了目标函数的设计思路,将多个相互制约的目标如网损、电压偏差和光伏消纳通过加权方式整合为单一评价标准。此外,作者分享了一些实践经验,例如采用前推回代法进行快速潮流计算,针对特定应用场景调整权重系数,以及引入随机波动模型模拟光伏出力特性。最终实验结果显示,经过优化后的方案能够显著提升系统的整体性能。 适用人群:从事电力系统规划与设计的专业人士,尤其是那些需要处理分布式能源集成问题的研究人员和技术人员。 使用场景及目标:适用于希望深入了解如何运用智能优化算法解决实际工程难题的人士;旨在帮助读者掌握PSO算法的具体应用方法,从而更好地应对配电网中分布式光伏系统的选址定容挑战。 其他说明:文中提供了完整的Matlab源代码片段,便于读者理解和复现研究结果;同时也提到了一些潜在改进方向,鼓励进一步探索和创新。

    晋升考核制度.pptx

    晋升考核制度.pptx

    计网-主机发送IP数据报的过程思维导图

    计网-主机发送IP数据报的过程思维导图

    三菱FX3U PLC与三台E740变频器基于Modbus RTU通讯的工业自动化控制系统实现

    内容概要:本文详细介绍了三菱FX3U PLC与三台三菱E740变频器通过Modbus RTU协议进行通讯的具体实现方法。主要内容涵盖硬件配置(如PLC、变频器、触摸屏)、通讯参数设置(如波特率、数据位、校验方式)、PLC程序编写(包括初始化、启停控制、频率设定等)、触摸屏编程(如画面设计、变量关联)等方面。文中还分享了一些实际应用中的注意事项和避坑指南,确保通讯系统的稳定性和可靠性。 适用人群:从事工业自动化领域的工程师和技术人员,尤其是熟悉三菱产品和Modbus RTU协议的专业人士。 使用场景及目标:适用于需要实现PLC与多台变频器通讯的工业自动化项目,旨在提高系统的集成度和可控性,减少人工干预,提升生产效率。 其他说明:文中提供的实例和代码片段有助于读者快速理解和掌握相关技术要点,同时强调了实际操作中的常见问题及其解决方案。

    自动驾驶路径跟踪:基于二/三自由度动力学模型的MPC算法及Carsim-Simulink联合仿真

    内容概要:本文深入探讨了利用二/三自由度动力学模型和MPC(模型预测控制)实现自动驾驶车辆的任意路径跟踪技术。首先介绍了二自由度动力学模型的基本概念及其状态方程,随后详细解释了MPC的工作原理,包括目标函数的设计和优化求解过程。接着讨论了Carsim和Simulink联合仿真的具体实施步骤和技术要点,如采样同步、约束条件处理等。文中还分享了许多实用的工程经验和调试技巧,例如预瞄距离的设置、权重矩阵的选择以及如何应对高速工况下的挑战。最终通过仿真结果展示,证明了该方法的有效性和优越性。 适合人群:从事自动驾驶研究与开发的专业人士,尤其是对路径跟踪算法感兴趣的工程师和技术爱好者。 使用场景及目标:适用于需要精确路径跟踪的自动驾驶应用场景,旨在提高车辆行驶的安全性和效率。通过掌握本文介绍的方法和技术,可以帮助开发者更好地理解和实现基于MPC的路径跟踪系统。 其他说明:文章不仅提供了理论知识,还包括了大量的实战经验和代码片段,有助于读者快速上手并应用于实际项目中。同时强调了在不同速度范围选择合适自由度模型的重要性,为后续的研究和发展指明了方向。

    基于博途1200PLC的智能灌溉系统设计与实现 - 自动化农业应用

    内容概要:本文详细介绍了基于西门子S7-1200 PLC的智能灌溉系统的设计与实现。系统主要包括PLC控制器、触摸屏、传感器和执行机构。文中详细讲解了如何使用博途V16软件编写PLC程序,包括梯形图编程和SCL语言的应用,以及如何设计触摸屏监控画面。此外,还涉及了IO表和电气原理图的准备,确保系统的正确安装和维护。文章特别强调了自动灌溉的核心逻辑,如状态机结构和异常处理机制,以及触摸屏设计的小技巧,如动态图标和趋势图的使用。最后,提供了调试过程中的一些注意事项和优化建议。 适合人群:从事农业自动化领域的工程师和技术人员,尤其是熟悉PLC编程和触摸屏设计的专业人士。 使用场景及目标:适用于需要提高灌溉效率和精度的现代农业生产环境。目标是通过智能化控制减少水资源浪费,提升作物产量。同时,也为系统开发者提供了详细的实施指南和调试技巧。 其他说明:文章附带了完整的PLC程序、HMI界面和电气图纸,方便读者进行实际操作和验证。

    MINIQMT学习课程Day5

    国金qmt模拟客户端。 模拟账号密码,私聊。

    员工离职面谈记录表.doc

    员工离职面谈记录表.doc

    新员工关怀方案.doc

    新员工关怀方案

    轴承表面缺陷检测数据集解析:基于Python的图像处理与模型训练

    内容概要:本文详细介绍了轴承表面缺陷检测数据集的结构及其应用方法。数据集包含5824张高清轴承图像及其对应的XML标注文件,涵盖擦伤、凹槽、划痕三种类型的缺陷。作者通过Python代码展示了如何检查数据完整性、解析XML标注文件、进行数据可视化以及数据增强操作。此外,还讨论了使用YOLOv5和EfficientDet等模型进行缺陷检测的具体步骤和技术要点,强调了高分辨率图像处理和模型优化的方法。 适合人群:从事工业质检、机器视觉、深度学习等相关领域的研究人员和工程师。 使用场景及目标:适用于需要处理高分辨率工业图像并进行缺陷检测的研究和工程项目。主要目标是提高缺陷检测的准确性,特别是在复杂的工业环境中。 其他说明:文中提供了大量实用的Python代码片段,涵盖了从数据预处理到模型训练的各个环节。特别提到了针对金属表面反光、多缺陷共存等问题的技术解决方案。

    招聘甘特图.xlsx

    招聘甘特图.xlsx

    招聘仪表盘构建及为数据解读P11.pptx

    招聘仪表盘构建及为数据解读P11.pptx

    基于MATLAB的光纤通信物理层传输算法仿真与调试技巧

    内容概要:本文详细介绍了利用MATLAB进行光纤通信物理层传输算法仿真的方法和技术要点。主要内容涵盖色散补偿、非线性放大器建模、信号重构、时钟恢复、QPSK调制、误码率分析等方面。文中提供了多个具体的MATLAB代码示例,如色散补偿、非线性放大器特性拟合、QPSK调制与解调、眼图生成等,并分享了许多调试经验和常见问题解决方案。此外,作者还强调了仿真过程中需要注意的关键细节,如参数设置、变量监控、噪声注入方式等。 适合人群:从事光纤通信研究的技术人员、研究生以及对通信系统仿真感兴趣的开发者。 使用场景及目标:适用于希望深入了解光纤通信物理层传输机制及其仿真实现的研究人员和工程师。目标是帮助读者掌握MATLAB在通信仿真中的应用,提高仿真效率并减少调试时间。 其他说明:文章不仅提供详细的代码示例,还分享了大量实战经验,有助于读者快速上手并解决实际问题。

    线性代数_李宏毅_视频笔记_学习辅助_1742822508.zip

    线性代数

Global site tag (gtag.js) - Google Analytics