本申请涉及计算机领域中的消息传输技术领域，具体涉及一种优化改进的merkle树存储方法和系统。
背景技术：
机会网络是一种利用节点移动带来的相遇机会实现短距离无线传输的自组织网络。该网络不需要源节点与目标节点建立完全连接。基于机会网络特点及应用场景，人们通过使用移动无线设备相互联系,形成了机会社会网络(opportunitysocialnetwork)。机会社会网络中一个典型的例子是人们在日常生活中通过自身携带的智能手机四处游走，并且在彼此的传输范围内通过蓝牙或wifi相互通信。
在以太坊中，将merkle树和字典树结合构成mpt(merklepatriciatree)树来存储多种信息，保证较高的查找效率并且能够快速计算根哈希值。但是它对树的深度是有限制的，不然攻击者可以通过操纵树的深度，执行dos攻击，使更新变得极其缓慢。以太坊在最初的mpt树设计过程中，考虑到以太坊需要在公链中运行，因此设计了1616的存储空间进行账户信息存储，秉持对账户不可见性采用对账户地址(公钥)利用rlp编码成长度相等的字节数组，编码后账户在树中位置是随机的。一方面树的深度较深在计算根哈希的时候，需要进行多层哈希，而哈希过程也是时间开销最大的。另一方面，大量分支节点的空间浪费，对系统来说也是一笔开销。
传统的无线网络根据当前网络拓扑信息建立路由表,并根据其变化进行路由信息的维护,同时消息的传输依赖于稳定的端到端连接,而机会社会网络在网络拓扑结构不稳定时仍可保持消息的高效传输。其中节点的协作性机制对于机会社会网络来说至关重要。由于源节点与目标节点之间通信受到距离的限制,消息不能直接从源节点发送给目标节点,此时需要中间节点的协作来完成。而节点的自私对网络的危害较大,怎样应对网络中节点的自私行为,并且增强网络节点之间的协作成了亟待解决的难点。
技术实现要素：
本申请的目的在于提出了一种优化改进的merkle树存储方法和系统，解决了增强网络节点之间的协作的问题。拟结合mpt树的数据结构以及交易模型改进账户存储和更新方式，一次对交易中的关联账户同时修改，及通过索引找到账户的公共前缀对应的节点，并以该节点作为根节点的子树对关联账户进行修改，从而减少索引和哈希次数，提高存储效率。
第一方面，本申请实施例提供了一种优化改进的merkle树存储方法，该方法包括：
s1：基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点；
s2：建立的merkle哈希树，并计算所有节点与当前节点的相遇距离；
s3:响应于对构建的merkle哈希树的节点进行行为检测,选择节点相遇距离小的节点作为候选节点；以及
s4:遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
在该方法中，首先根据节点的相遇距离建立路径哈希表,由建立的merkle哈希树判断节点是否存在自私节点,如果存在自私节点,检测自私节点所在的路径,将该自私节点删除并根据相遇距离大小选择转发节点,如果当前节点为非自私节点,则遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
在一些具体实施例中，在s2步骤中的merkle哈希树的建立为将一组节点映射到一组固定大小的字符串。其中每个叶子节点携带一个给定的值,内部节点包括根节点的值通过两个孩子节点哈希所得到,根据节点所携带的数据包及相遇距离构建merkle哈希树。
在一些具体实施例中，在s3步骤中的节点相遇距离的计算为分别计算节点到邻居点和目标点角度。先计算节点移动速度与节点之间距离所成的角度,并预测节点下一时刻的移动位置并计算距离。
在一些具体实施例中，节点到目标点角度的计算公式如下：
其中，携带节点c和及目标节点d的移动速度分别为
在一些具体实施例中，邻居点到目标点角度的计算公式如下：
其中，邻居点n和及目标节点d的移动速度分别为
在一些具体实施例中，节点的移动速度具体公式如下：
其中，设置节点c的前一时刻位置用坐标(c0x，c0y)表示，当前位置为用坐标(cx，cy)表示,δt表示时间δt内节点前一时刻位置与当前位置的距离比值。
在一些具体实施例中，邻居点的移动速度具体公式如下：
其中，设置邻居点n的前一时刻位置用坐标(n0x，n0y)表示，当前位置为用坐标(nx，ny)表示,δt表示时间δt内节点前一时刻位置与当前位置的距离比值。
在一些具体实施例中，merkle哈希树的字符串具体计算公式如下：
yh 1[i]＝f(yh[2i]×yh[2i] 1)
其中，h＝0,....,h,表示树中节点的高度(叶子节点所在高度为0,根节点所在的高度为h),i＝0,…,2h-h-1表示节点从左至右的位置计数,f:(0,1)*→(0,1)n为哈希函数。
第二方面，本申请实施例提供了一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现如上述实施例的方法。
第三方面，本申请实施例提供了优化改进的merkle树存储的系统，该系统包括：
哈希列表单元：配置用于基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点；
相遇距离单元：配置用于建立的merkle哈希树，并计算所有节点与当前节点的相遇距离；
行为检测单元：配置用于响应于对构建的merkle哈希树的节点进行行为检测,选择节点相遇距离小的节点作为候选节点；
最佳路径单元：配置用于遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
本申请提供的一种优化改进的merkle树存储方法和系统。其中，首先根据节点的移动特性建立节点相遇位置预测模型；其次构建merkle哈希树并对自私节点进行检测和删除,更新整个merkle哈希树；最后结合所提出的模型及相遇距离大小选择合适的转发节点,保证了消息的协作转发。本申请提出的方法能够精确地检测网络中的自私节点,并能够保证消息的高效传输。此外在消息投递率及传输时延方面优于典型的传统epidemic、directdelivery算法。包括利用安全多方计算协议实现互不信任的多方之间保护隐私的协同计算、优化改进的基于哈希算法的merkle树存储方法，提高区块链隐私保护能力和效率。针对目前隐私保护机制效率不高、安全性不足等缺陷，利用安全多方计算协议实现互不信任的多方之间保护隐私的协同计算模式，对基于哈希的merkle树存储方法进行优化改进提高存储和处理效率，基于系列密码技术形成安全高效的隐私保护机制。
附图说明
通过阅读参照以下附图所作的对非限制性实施例所作的详细描述，本申请的其它特征、目的和优点将会变得更明显：
图1是根据本申请实施例中的优化改进的merkle树存储方法的流程图；
图2是根据本申请实施例中的优化改进的merkle树存储的节点协作转发流程图；
图3是根据本申请实施例中的一种优化改进的merkle树存储的系统的示意性结构框图；
图4适于用来实现本申请实施例的电子设备的计算机系统的结构示意图。
具体实施方式
下面结合附图和实施例对本申请作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释相关发明，而非对该发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与有关发明相关的部分。
需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本申请。
图1示出了根据本申请实施例中的优化改进的merkle树存储的流程图。如图1所示，该方法包括汇总哈希列表，相遇距离、行为检测和最佳路径的步骤。
在步骤s1中：基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点。
在该步骤中，根据merkle哈希树检测网络中存在的自私节点并将其删除,其次根据节点相遇位置去计算相遇节点的距离大小,综合考虑两个因素选择合适的转发路径进行消息的传输,保证了消息的安全性及高效性。
在一些具体实施例中，当节点s与节点d不存在端到端的传输路径前提下,一个源节点s想要发送消息给目标节点d,在这种情况下,消息需要借助与网络中其他节点相遇的机会进行转发。因此,s节点将会从一组邻居节点(例如n1和n4)中选择一个中间节点,使得该消息通过多跳通信最终传输给节点d。假设s选择节点n1,n1又将消息转发给n2,因为没有其他邻居节点可转发。然而节点n2由于存储、能量等资源限制而表现出自私性,丢弃该消息而不是转发给节点d,由于资源限制导致节点表现出的自私行为很难在机会社会网络中被检测到,使得消息传递成功率降低,传输时间延长。
merkle树是区块链中广泛使用的一种数据结构，例如以太坊中，为了方便数据校验，大多数数据都以merkle树的形式存储。merkle树是哈希大量聚集数据的一种方式，merkle树可以是二叉树也可以是多叉树，叶子节点value存放的是数据，非叶子节点的value是该节点下的所有节点组合的哈希值。图中h1,2的值需要根据叶子节点h1、h2的value值进行哈希计算。merkle树这种数据结构为区块链提供了一种校验机制，称为merkle证明(merkleproof)，即当验证了某一个节点哈希的正确性，则该节点下的所有分支都是正确的。merkle证明可以通过验证少量数据验证大量聚集数据的正确性，区块链正是利用这项技术实现对一个区块中交易的快速校验过程。
在步骤s2中：建立的merkle哈希树，并计算所有节点与当前节点的相遇距离。
在该步骤中，机会社会网络节点的移动性常常导致节点的位置信息发生变化。为了预测节点的相遇位置,我们根据节点的距离预测和计算模型,首先计算节点移动速度与节点之间距离所成的角度,并预测节点下一时刻的移动位置并计算距离；最后利用merkle哈希树去检测其存在自私节点,通过节点协作转发机制,选择最佳转发节点完成消息的转发。
在一些具体实施例中，在s2步骤中的merkle哈希树的建立为将一组节点映射到一组固定大小的字符串。
在一些具体实施例中，merkle哈希树的字符串具体计算公式如下：
yh 1[i]＝f(yh[2i]×yh[2i] 1)
其中，h＝0,....,h,表示树中节点的高度(叶子节点所在高度为0,根节点所在的高度为h),i＝0,…,2h-h-1表示节点从左至右的位置计数,f:(0,1)*→(0,1)n为哈希函数。
在步骤s3中：响应于对构建的merkle哈希树的节点进行行为检测,选择节点相遇距离小的节点作为候选节点。
在该步骤中，根据节点的距离预测和计算模型,首先计算节点移动速度与节点之间距离所成的角度,并预测节点下一时刻的移动位置并计算距离。
在一些具体的实施例中，在s3步骤中的节点相遇距离的计算为分别计算节点到邻居点和目标点角度。
在一些具体的实施例中，节点到目标点角度的计算公式如下：
其中，携带节点c和及目标节点d的移动速度分别为
在一些具体的实施例中，邻居点到目标点角度的计算公式如下：
其中，邻居点n和及目标节点d的移动速度分别为
在优选的实施例中，节点的移动速度具体公式如下：
其中，设置节点c的前一时刻位置用坐标(c0x，c0y)表示，当前位置为用坐标(cx，cy)表示,δt表示时间δt内节点前一时刻位置与当前位置的距离比值。
在优选的实施例中，邻居点的移动速度具体公式如下：
其中，设置邻居点n的前一时刻位置用坐标(n0x，n0y)表示，当前位置为用坐标(nx，ny)表示,δt表示时间δt内节点前一时刻位置与当前位置的距离比值。
在步骤s4中：遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
在该步骤中，基于节点相遇位置预测模型构建merkle哈希树,并对自私节点进行检测。通过节点位置预测模型和计算节点之间的距离选择合适的转发节点,保证节点之间的协作转发。
在一些具体实施例中，假设源节点与目标节点为合法节点,中继节点表现为自私性。merkle哈希树通过散列消息数量创建树的第一层,散列在第一层节点的值成为叶哈希,每两个叶子哈希配对并散列创建新的哈希值,直到最后创建一个散列。
在一些具体实施例中，如果目标节点接收到数据包,则通过接收到的数据包进行散列计算新的merkle根哈希值,然后构建新的merkle哈希树,利用计算出的新merkle根哈希值与原始发送的merkle根哈希值进行比较,如果相等,则表示目标节点接收到正确的数据包数量；反之,则认为在转发的过程中存在自私节点丢失了数据包或者受到攻击等。源节点将merkle根和数据包一起发送到每个数据包的头部,目标节点接收到数据包。
继续参考图2，其示出了根据本申请实施例中的优化改进的merkle树存储方法的协作转发流程图。具体流程包括以下步骤：
步骤201：所有节点存入队列q。
步骤202：判断列表q中的节点是否为空，若“是”，则从候选节点中选择最优转发节点，然后输出最优路径；若“否”，则执行步骤203
步骤203：取出中的首节点i作为当前节点。
步骤204：建立merkle哈希树，并计算节点相遇距离。
步骤205：判断当前节点为是否自私节点，若“是”，则删除当前节点，执行步骤202；若“否”，则执行步骤206。
步骤206：选择节点相遇距离小的节点作为候选节点，重复执行步骤202，直至列表为空，输出最优路径。
在一些具体的实施例中，根据节点的相遇距离建立路径哈希表,由建立的merkle哈希树判断节点是否存在自私节点,如果存在自私节点,检测自私节点所在的路径,将该自私节点删除并根据相遇距离大小选择转发节点,如果当前节点为非自私节点,则遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
在一些具体的实施例中，由于算法主要针对机会社会网络中的自私节点,构建merkle哈希树,其次对构建的merkle哈希树的节点进行行为检测,最后根据节点的自私行为,选择合适的转发路径。其时间复杂度为o(n2)。
在一些具体的实施例中，机会社会网络不依赖于固定的网络基础设施,每个节点充当路由器角色,所有的节点要想正常通信,需要依赖于节点的分布式协作来完成。而非相邻的节点间通信依靠中间节点建立路由链路并转发数据,节点间的协作效果会直接影响到网络性能。
此外，本申请还提出了一种优化改进的merkle树存储方法的系统。其中如图3所示，哈希算的merkle树节点转发系统300包括哈希列表单元301、相遇距离单元302、行为检测单元303和最佳路径单元304。首先通过哈希列表单元301建立相遇距离的哈希列表，相遇距离单元302通过计算所有节点与当前节点的相遇距离，最后经过最佳路径单元304筛选出当前节点与目标节点的相遇距离最小的路径为最佳路径。
下面参考图4，其示出了适于用来实现本申请实施例的电子设备的计算机系统400的结构示意图。图4示出的电子设备仅仅是一个示例，不应对本申请实施例的功能和使用范围带来任何限制。
如图4所示，计算机系统400包括中央处理单元(cpu)401，其可以根据存储在只读存储器(rom)402中的程序或者从存储部分408加载到随机访问存储器(ram)403中的程序而执行各种适当的动作和处理。在ram403中，还存储有系统400操作所需的各种程序和数据。cpu401、rom402以及ram403通过总线404彼此相连。输入/输出(i/o)接口405也连接至总线404。
以下部件连接至i/o接口405：包括键盘、鼠标等的输入部分403；包括诸如、液晶显示器(lcd)等以及扬声器等的输出部分404；包括硬盘等的存储部分408；以及包括诸如lan卡、调制解调器等的网络接口卡的通信部分409。通信部分409经由诸如因特网的网络执行通信处理。驱动器410也可以根据需要连接至i/o接口405。可拆卸介质411，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器410上，以便于从其上读出的计算机程序根据需要被安装入存储部分408。
特别地，根据本公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本公开的实施例包括一种计算机程序产品，其包括承载在计算机可读介质上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实施例中，该计算机程序可以通过通信部分409从网络上被下载和安装，和/或从可拆卸介质411被安装。在该计算机程序被中央处理单元(cpu)401执行时，执行本申请的方法中限定的上述功能。
需要说明的是，本申请的计算机可读介质可以是计算机可读信号介质或者计算机可读介质或者是上述两者的任意组合。计算机可读介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、光纤、便携式紧凑磁盘只读存储器(cd-rom)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本申请中，计算机可读介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在本申请中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、rf等等，或者上述的任意合适的组合。
可以以一种或多种程序设计语言或其组合来编写用于执行本申请的操作的计算机程序代码，程序设计语言包括面向对象的程序设计语言—诸如java、smalltalk、c ，还包括常规的过程式程序设计语言—诸如“c”语言或类似的程序设计语言。程序代码可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(lan)或广域网(wan)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。
附图中的流程图和框图，图示了按照本申请各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，该模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
描述于本申请实施例中所涉及到的模块可以通过软件的方式实现，也可以通过硬件的方式来实现。所描述的模块也可以设置在处理器中，例如，可以描述为：一种处理器包括哈希列表单元、相遇距离单元、相遇距离单元和最佳路径单元。其中，这些模块的名称在某种情况下并不构成对该模块本身的限定，例如，哈希列表单元还可以被描述为“基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点”。
作为另一方面，本申请还提供了一种计算机可读介质，该计算机可读介质可以是上述实施例中描述的电子设备中所包含的；也可以是单独存在，而未装配入该电子设备中。上述计算机可读介质承载有一个或者多个程序，当上述一个或者多个程序被该电子设备执行时，使得该电子设备：基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点；建立的merkle哈希树，并计算所有节点与当前节点的相遇距离；响应于对构建的merkle哈希树的节点进行行为检测,选择节点相遇距离小的节点作为候选节点；以及遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
以上描述仅为本申请的较佳实施例以及对所运用技术原理的说明。本领域技术人员应当理解，本申请中所涉及的发明范围，并不限于上述技术特征的特定组合而成的技术方案，同时也应涵盖在不脱离上述发明构思的情况下，由上述技术特征或其等同特征进行任意组合而形成的其它技术方案。例如上述特征与本申请中公开的(但不限于)具有类似功能的技术特征进行互相替换而形成的技术方案。
1.一种优化改进的merkle树存储方法，其特征在于，所述方法包括：
s1：基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点；
s2：建立的merkle哈希树，并计算所有节点与所述当前节点的相遇距离；
s3:响应于对构建的所述merkle哈希树的节点进行行为检测,选择所述节点相遇距离小的节点作为候选节点；以及
s4:遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
2.根据权利要求1所述的一种优化改进的merkle树存储方法，其特征在于，在所述s2步骤中的所述merkle哈希树的建立为将一组节点映射到一组固定大小的字符串。
3.根据权利要求1所述的一种优化改进的merkle树存储方法，其特征在于，在所述s3步骤中的所述节点相遇距离的计算为分别计算所述节点到邻居点和目标点角度。
4.根据权利要求3所述的一种优化改进的merkle树存储方法，其特征在于，所述节点到目标点角度的计算公式如下：
其中，携带节点c和及目标节点d的移动速度分别为
5.根据权利要求3所述的一种优化改进的merkle树存储方法，其特征在于，所述邻居点到目标点角度的计算公式如下：
其中，邻居点n和及目标节点d的移动速度分别为
6.根据权利要求4所述的一种优化改进的merkle树存储方法，其特征在于，所述节点的移动速度具体公式如下：
其中，设置节点c的前一时刻位置用坐标(c0x，c0y)表示，当前位置为用坐标(cx，cy)表示,δt表示时间δt内节点前一时刻位置与当前位置的距离比值。
7.根据权利要求5所述的一种优化改进的merkle树存储方法，其特征在于，所述邻居点的移动速度具体公式如下：
其中，设置邻居点n的前一时刻位置用坐标(n0x，n0y)表示，当前位置为用坐标(nx，ny)表示,δt表示时间δt内节点前一时刻位置与当前位置的距离比值。
8.根据权利要求2所述的一种优化改进的merkle树存储方法，其特征在于，所述merkle哈希树的所述字符串具体计算公式如下：
yh 1[i]＝f(yh[2i]×yh[2i] 1)
其中，h＝0,….,h,表示树中节点的高度(叶子节点所在高度为0,根节点所在的高度为h),i＝0,…,2h-h-1表示节点从左至右的位置计数,f:(0,1)*→(0,1)n为哈希函数。
9.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-8中任一所述的方法。
10.一种优化改进的merkle树存储的系统，其特征在于，所述系统包括：
哈希列表单元：配置用于基于节点的相遇距离建立路径哈希列表，取出首节点作为当前节点；
相遇距离单元：配置用于建立的merkle哈希树，并计算所有节点与所述当前节点的相遇距离；
行为检测单元：配置用于响应于对构建的所述merkle哈希树的节点进行行为检测,选择所述节点相遇距离小的节点作为候选节点；
最佳路径单元：配置用于遍历当前节点的邻居节点,直至将消息转发给目标节点,最后输出最佳路径。
技术总结