Merkle树遍历机制的改进及应用研究

无线Mesh网络的网络结构导致了无线Mesh网络具有更多的安全隐患.其中数据完整性校验是保障无线Mesh网络通信安全的一个重要方面,而Merkle可信树适用于批量数据验证.研究无线Mesh网络的安全特点,并研究Merkle可信树数字签名技术.研究表明,在Merkle可信树应用中,遍历可信树计算认证路径节点值需要消耗大量的时间.Merkle可信树的遍历算法的效率是影响Merkle可信树数字签名的关键.在研究的基础上,提出了一种改进的Merkle可信树遍历算法,并将改进后的Merkle可信树应用于无线Mesh网络的数据完整性校验机制.     

区块链中Merkle树性能研究

区块链技术具有去中心化、安全可靠和不可篡改等特性,已经得到广大的重视.Merkle树是区块中核心组成部分,占据区块存储空间的96%以上,主要用来解决在区块链交易中的简化支付验证问题,因此选择合适的Merkle树结构会极大影响区块链系统性能.但是,目前缺乏公共的平台对不同区块链系统下的Merkle树性能进行分析和实验验证.本文提出了一整套相关性能评价与分析指标,从存储、验证和构建时间等方面,综合评价比特币、以太坊和超级账本三种主流区块链的Merkle树的性能.本文提出的指标及评价方法不仅为Merkle树的进一步研究提供了定量的数据支持,也为区块链从业者选择Merkle树结构提供了理论依据.     

WSN中基于簇的Sybil攻击防御机制

提出一种基于簇的平面Merkle哈希树的Sybil攻击防御机制。将网络分成簇,单个簇内的节点维护一棵Merkle哈希树,利用Merkle哈希树生成密钥。理论分析与模拟实验证明,该机制具有较高的安全连通性和较低的能耗,有较长的网络生命周期和较短的认证时延。     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况，提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树，由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路，运用欧拉回路技术计算前缀和，前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

一种快速的基于并行的碰撞检测算法

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树形成对一任务树的遍历,采用并行算法中的流水线技术,利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。     

一种混合云环境下基于Merkle哈希树的数据安全去重方案

重复数据删除技术是云存储系统中一种高效的数据压缩和存储优化技术,能够通过检测和消除冗余数据来减少存储空间、降低传输带宽消耗。针对现有的云存储系统中数据安全去重方案所采用的收敛加密算法容易遭受暴力攻击和密文计算时间开销过大等问题,提出了一种混合云环境下基于Merkle哈希树的数据安全去重方案MTHDedup。该方案通过引入权限等级函数和去重系数来计算去重标签,高效地实现了支持访问控制的数据安全去重系统;同时通过执行额外的加密算法,在文件级和数据块级的数据去重过程中构造Merkle哈希树来生成加密密钥,保证了生成的密文变得不可预测。安全性分析表明,该方案能够有效地抵制内部和外部攻击者发起的暴力攻击,从而提高数据的安全性。仿真实验结果表明,MTHDedup方案能有效地降低密文生成的计算开销,减少密钥的存储空间,而且随着权限集数目的增加,性能优势将更加明显。     

基于Merkle散列树的无线传感器网络实体认证协议

针对无线传感器网络节点能量、计算和存储有限的特点,以及公开密钥算法和数字签名实施认证耗能多的不足,提出一种适用于无线传感器网络的基于分簇的Merkle散列树实体认证协议(CMAS).该协议利用Merkle散列树的思想,可获得有效的安全认证策略;结合网络分簇技术,使得协议更实用;并且只使用对称密钥算法,避免了采用公开密钥算法实施数字签名计算量大的问题,有效地降低了认证的时延、增大网络生存期和提高了安全性.仿真实验证明该协议的有效性.     

使用堆栈生成二叉链表树的非递归算法实现

讨论了利用堆栈来生成二叉链表树的非递归算法.通过仔细分析二叉链表树的递归生成过程,从中找到了二叉树非递归实现的算法,最后应用前序遍历和中序遍历可以惟一确定一棵二叉树的方法来检验生成的二叉树的正确性.分析该算法的实现,有助于我们对它的理解与掌握.     

自然语言向SQL代码的转化方法

为解决智能学习系统查询语言的转化问题,提出一种自然语言向SQL代码转化的方法。利用所建立的字典扫描单词和理解语义,采用改进后的单词提取技术扫描自然语言串,以生成语义依赖树,并将其语义关系划分为若干独立的集合块,通过对该集合块遍历生成与自然语言等价的SQL代码。实验结果表明,该转化方法简单有效。     

第三讲 二叉树的遍历及最优二叉树

本讲继续学习“树”中“二叉树”的遍历,并向大家介绍最优二叉树即哈夫曼树的生成。     

无线传感器网络中基于Merkle树的广播认证策略

在无线传感器网络中广播是一种基本的数据传输方式,因此广播认证在整个网络的安全体制中占有非常重要的地位.在利用Merkle树进行广播认证策略的基础上,提出了一种分级式的Merkle树广播认证策略,着重对其广播初始化参数的分配方法进行研究,该策略支持在网络中存在大规模广播发送节点的情况,有效的抑制了由此引起的参数认证时,节点计算量与内存消耗过度以及通信负载上升的问题.为了解决广播发送节点长生存周期与所需密钥链长度之间的矛盾,将二级μTESLA协议引入分级式的Merkle树广播认证策略,并提出了一个选择低级密钥链长度的条件式.     

Optimal trade-off for Merkle tree traversal

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo [Fractal Merkle tree representation and traversal, in: RSA Cryptographers Track, RSA Security Conference, 2003] and M. Szydlo [Merkle tree traversal in log space and time, in: Proc. Eurocrypt, in: LNCS, vol. 3027, 2004, pp. 541–554; Merkle tree traversal in log space and time, Preprint version 2003, available at http://www.szydlo.com]. In particular, we show that our algorithm requires 2logn/log⁽³⁾n$2logn/{log}^{\left(3\right)}n$ hash function computations and storage for less than (logn/log⁽³⁾n+1)loglogn+2logn$(logn/{log}^{\left(3\right)}n+1)loglogn+2logn$ hash values, where n$n$ is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than O(logn/logt)$O(logn/logt)$ time and less than O(tlogn/logt)$O(tlogn/logt)$ space for any choice of parameter t≥2$t\ge 2$.     

基于VC＋＋的二叉树遍历算法演示软件的设计与实现

利用VC＋＋开发平台,以《数据结构》课程的重要章节二叉树遍历算法为例,论述二叉树遍历算法演示软件的设计和关键技术并实现整个系统。系统使得学生加深算法的理解,取得良好的教学效果。     

一种基于MB 树的网络共享数据查询和检验方法*

网络数据共享机制将数据置于远程网络服务商处并通过外部访问接口进行共享,用户无需保存数据副本,网络服务商负责数据的安全保障,因此无副本情况下数据用户对网络服务商处存储数据的查询和安全效验至关重要。分析目前对远程存储数据查询和检验常用的Merkle散列树方法,就其对大规模数据进行检验时存在验证过程冗余、验证辅助数据量大等不足,提出一种基于MB 树的网络共享数据查询和检验方法,帮助数据用户确认位于网络服务商处数据的正确性和完整性。利用MB 树非叶结点包含多出度、叶结点直接映射数据等特性对数据文件进行抽象组织,避免Merkle散列树的结点数和深度随数据文件块的增多而呈现线性增长的问题,同时缩短检验过程中的查询认证路径,减少检验所需的辅助认证信息,有效地控制了时间和空间消耗。通过实验分析可知,相较于常用的方法（如Merkle散列树）,处理大规模数据时MB 树更易于构建,也能够更加快速地查询和检验数据文件。     

数字证书的选择性泄漏研究

目前X．509v3是广泛使用的数字证书标准，但是依然存在着安全缺陷。基于该标准的现实意义，简单介绍了相关背景知识和存在的缺陷。也分析了已经存在的解决方案，并针对其需要较多存储空间的不足，用Merkle树方法加以改进。同时也分析了Merkle树方案的不足。利用数字证书字段出现的概率，用Huffman树方法做了改进。最后对3种方案做了简单的比较。     

二叉树的遍历探究与应用

通过对同一棵二叉树的前序遍历、中序遍历、后序遍历及层次遍历得到四个不同序列的分析,概括出二叉树的前序遍历、中序遍历、后序遍历及层次遍历序列间的关系,确定对应的二叉树。