2023年7月27日发(作者：)

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号

CN 112699123 A(43)申请公布日

2021.04.23(21)申请号 2.5(22)申请日 2020.12.30(71)申请人 武汉大学地址 430072 湖北省武汉市武昌区珞珈山武汉大学(72)发明人 何琨　陈晶　杜瑞颖　张晨　徐丽华　郑明辉　(74)专利代理机构 武汉科皓知识产权代理事务所(特殊普通合伙) 42222代理人 肖明洲(51).G06F

16/22(2019.01)G06F

21/64(2013.01)

权利要求书3页 说明书6页 附图2页(54)发明名称一种数据存储系统中数据存在性和完整性校验方法及系统(57)摘要本发明公开了一种数据存储系统中数据存在性和完整性校验方法及系统，包括快速归纳和校验块数据的存在性和完整性的默克尔树结构，基于此验证结构，可以实现无块验证。此验证结构的使用方法主要包括创建、证明和验证三个部分，创建方法基于哈希运算，得到一个称为无块默克尔树的验证结构及其元数据；证明方法基于挑战信息、验证结构和文件，生成证据；验证方法基于挑战信息、证据和元数据，生成证据是否有效的决策。本发明适用于大规模数据存储系统下的数据完整性校验，以及以太坊区块数据的存储和交易验证，无块默克尔树的验证结构极大的减小了验证过程中的计算和存储开销，且为指定数据块的检验提供了一种轻量级的无块验证方法。CN

112699123

ACN 112699123 A权　利　要　求　书1/3页1.一种数据存储系统中数据存在性和完整性校验方法，其特征在于，包括以下步骤：步骤1：从数据存储系统中获取原始数据块；步骤2：创建验证结构；步骤2.1：选择一组随机数生成器，并计算原始数据块的同态压缩值；步骤2.2：将原始数据块的同态压缩值计算得到的散列值作为叶节点，向上生成二叉hash树，每个节点的数据结构包括该结点的索引值、该节点可以达到的叶节点数和其散列值；步骤2.3：输出由二叉hash树与随机数生成器组成的验证结构和由节点与随机数生成器组成的元数据；步骤3：输入挑战信息，根据步骤2.3中生成的验证结构及输入的挑战信息，进行被挑战数据块存在性和完整性校验；步骤3.1：根据挑战信息中的块索引和验证结构中的生成元，计算挑战块的同态压缩值；步骤3.2：根据挑战信息中的块系数、块索引和验证结构中的生成元，计算挑战块的线性响应值；步骤3.3：计算从根节点到被挑战叶节点的路径及该路径上的兄弟节点，将计算结果整合成证据输出；步骤3.4：将证据解析，获得挑战块的线性响应值，同态压缩值、从根节点到被挑战叶结点的路径及该路径上的兄弟结点；步骤3.5：根据线性响应值和同态压缩值进行无块同态验证，若验证失败，则输出证据无效的决策，终止验证，否则继续进行下一步；步骤3.6：对于每个挑战块的同态压缩值，计算其散列值；步骤3.7：根据步骤3.4中得到的路径上的兄弟结点和步骤2.3中生成的元数据，重建树，得到根；如果重建得到的树根与验证结构中的树根不相等，则输出证据无效的决策，终止验证，否则继续进行下一步；步骤3.3：验证成功，被挑战数据块是存在且完整的。2.根据权利要求1所述的数据存储系统中数据存在性和完整性校验方法，其特征在于：步骤2中，设G为阶为素数p的乘法循环群，H：{0,1}*→{0,1}*为哈希函数；假设文件由D数据块组成，存储和处理文件时，数据块是基本单元；将每个数据块di划分为s段其中，表示模p的整数集合；时，输出一个经过验证的结构和一些元数据，具体步步骤2中，当输入D个数据块骤如下：(1)选择S随机生成器g1，…，gs∈G；(2)对于每个数据块di，计算其中，表示gj的di，ui表示数据j次幂；块的同态压缩值；(3)建立一个完整的二叉树τ和d叶节点，其中每个节点存储一个vl＝(l,ll,sl)其中l是树中节点的唯一索引，ll是第l个节点可以到达的叶节点数，sl是散列值；根节点的索引值为2CN 112699123 A权　利　要　求　书2/3页1，索引从上到下、从左到右均为递增；(4)对于树中索引为li的第i个叶节点，设置ll＝1并计算其中，与H(ui)都表示ui的散列值；(5)对于树中指数为l的每个非叶节点，分别计算li:＝l2l+l2l+1和sl：＝H(v2l||v2l+1)，其中，v2l＝(2l,l2l,s2l)和v2l+1＝(2l+1,l2l+1,s2l+1)分别为vl的左孩子和右孩子；(6)返回认证结构和元数据3.根据权利要求2所述的数据存储系统中数据存在性和完整性校验方法，其特征在于：步骤3中，输入挑战示被挑战块的索引，合；具体过程如下：(1)计算并得到其中，dib，j表示被挑战的数据块的第j段，数据块二叉树τ和生成一个证据；其中ib表是一个系数，B是被挑战的块的数量，表示除0外模p的整数集uib表示被挑战的数据块dib的同态压缩值；(2)计算并得到其中，μj表示证明值；其中，lib表示索引为ib的被挑战数据块在树中(3)计算从根结点到被挑战叶结点的路径及该路径上结点的兄弟结点θ；(4)返回证据的索引。4.根据权利要求3所述的数据存储系统中数据存在性和完整性校验方法，其特征在于：步骤3中，输入挑战效；具体过程如下：(1)将解析为(2)如果(3)对每个uib，计算(4)根据θ和重建根，其中，如果重建根与v1不相等，则返回0；θ和不成立，则返回0；证据二叉树树τ的根结点v1，检查证据是否有(5)返回1时说明证据有效。5.一种数据存储系统中数据存在性和完整性校验系统，其特征在于：包括以下模块；模块一，用于从数据存储系统中获取原始数据块；模块二，用于创建验证结构；具体实现包括以下子步骤：步骤2.1：选择一组随机数生成器，并计算原始数据块的同态压缩值；步骤2.2：将原始数据块的同态压缩值计算得到的散列值作为叶节点，向上生成二叉hash树，每个节点的数据结构包括该结点的索引值、该节点可以达到的叶节点数和其散列值；步骤2.3：输出由二叉hash树与随机数生成器组成的验证结构和由节点与随机数生成器组成的元数据；3CN 112699123 A权　利　要　求　书3/3页模块三，用于输入挑战信息，根据步骤2.3中生成的验证结构及输入的挑战信息，进行被挑战数据块存在性和完整性校验；具体实现包括以下子步骤：步骤3.1：根据挑战信息中的块索引和验证结构中的生成元，计算挑战块的同态压缩值；步骤3.2：根据挑战信息中的块系数、块索引和验证结构中的生成元，计算挑战块的线性响应值；步骤3.3：计算从根节点到被挑战叶节点的路径及该路径上的兄弟节点，将计算结果整合成证据输出；步骤3.4：将证据解析，获得挑战块的线性响应值，同态压缩值、从根节点到被挑战叶结点的路径及该路径上的兄弟结点；步骤3.5：根据线性响应值和同态压缩值进行无块同态验证，若验证失败，则输出证据无效的决策，终止验证，否则继续进行下一步；步骤3.6：对于每个挑战块的同态压缩值，计算其散列值；步骤3.7：根据步骤3.4中得到的路径上的兄弟结点和步骤2.3中生成的元数据，重建树，得到根；如果重建得到的树根与验证结构中的树根不相等，则输出证据无效的决策，终止验证，否则继续进行下一步；步骤3.8：验证成功，被挑战数据块是存在且完整的。4CN 112699123 A说　明　书1/6页一种数据存储系统中数据存在性和完整性校验方法及系统技术领域[0001]本发明涉及密码学及数据安全领域，提出了一种数据存在性和完整性校验的校验方法，具体涉及一种基于无块验证的默克尔树结构(Blockless Merkle Tree)的大规模数据存储系统中数据存在性和完整性校验方法及系统。背景技术[0002]默克尔树的概念由瑞夫·默克于1979年提出，在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签，最终得到根哈希。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。默克尔树广泛应用于分布式系统和分布式存储中，包括快默克尔树的结构特征使其可以快速归纳和速比较大量数据、快速定位修改和零知识证明，验证数据的存在性和完整性。[0003]近年来，随着区块链技术的发展，P2P网络和去中心化技术受到人们的广泛关注。比特币区块链系统中，每一个区块包含了前一个区块的加密散列、相应时间戳记以及交易数据，通过默克尔二叉树，将区块链中的数据分组进行哈希运算，不断递归运算产生新的哈希节点，最终只剩下一个默克尔根存入区块头中，每个哈希节点重视包含两个相邻的数据块或其哈希值，这样的设计使得区块内容具有难以篡改的特性且极大地提高了区块链的运行效率和可扩展性。此外，默克尔树的“简化支付验证协议”(APV)使得在比特币项目中，客户端在不需要运行完整的区块链网络节点的情况下，也能够对交易数据进行检验。这使得以太坊区块的轻客户端协议成为了可能，它允许客户端轻松地进行并核实交易数据。[0004]在分布式存储系统中，为了保持数据的一致性，系统间的数据需要同步，如果对机器上的所有数据都进行比对的话，数据传输量就会很大，从而造成“网络拥挤”。为了解决这个问题，可以在每台机器上构造一棵默克尔树，这样，唉两台机器上进行数据比对时，从默克尔树的根结点开始进行比对，如果根结点一样，则表示两个副本目前是一致的，不再需要任何处理；如果不一样，则沿着hash值不同的节点路径查询，可以快速定位到数据不一致的叶节点，只需把不一致的数据同步即可，从而大大节省了对比时间和数据的传输量。[0005]此外，云存储的出现为用户数据的存储和访问带来了便捷，虽然云计算基础设施较个人和企业存储设备能力更强、可靠性更高，但来自云平台内部和外部的威胁依然严峻，云端数据的完整性保护一直是研究的热点。数据审计是保护云端数据完整性的一种有效方法，不仅能发现云服务器的软硬件故障导致的数据丢失，而且能够及时检测云端存在的各种破坏数据完整性的恶意行为，基于默克尔树的挑战应答模型为云端数据提供了一种可行的审计方案，这种方式允许验证者(即数据所有者或特殊第三方)在不下载整个文件的情况下检查远程数据完整性，从而降低通信成本。发明内容[0006]基于传统默克尔树的验证方法中，无论数据块是否被破坏或被篡改，验证器都需5CN 112699123 A说　明　书2/6页要根据指定块所在的叶节点到根结点的完整路径及该路径上的兄弟节点进行一次默克尔树的创建操作，当数据块数量巨大时，计算的存储开销是很大的。[0007]为了解决上述技术问题，本发明提供了一种数据存储系统中数据存在性和完整性校验方法及系统。[0008]本发明的方法所采用的技术方案是：一种数据存储系统中数据存在性和完整性校验方法，其特征在于，包括以下步骤：[0009]步骤1：从数据存储系统中获取原始数据块；[0010]步骤2：创建验证结构；[0011]步骤2.1：选择一组随机数生成器，并计算原始数据块的同态压缩值；[0012]步骤2.2：将原始数据块的同态压缩值计算得到的散列值作为叶节点，向上生成二叉hash树，每个节点的数据结构包括该结点的索引值、该节点可以达到的叶节点数和其散列值；[0013]步骤2.3：输出由二叉hash树与随机数生成器组成的验证结构和由节点与随机数生成器组成的元数据；[0014]步骤3：输入挑战信息，根据步骤2.3中生成的验证结构及输入的挑战信息，进行被挑战数据块存在性和完整性校验；[0015]步骤3.1：计算挑战块的同态压根据挑战信息中的块索引和验证结构中的生成元，缩值；[0016]步骤3.2：根据挑战信息中的块系数、块索引和验证结构中的生成元，计算挑战块的线性响应值；[0017]步骤3.3：将计算结计算从根节点到被挑战叶节点的路径及该路径上的兄弟节点，果整合成证据输出；[0018]步骤3.4：将证据解析，获得挑战块的线性响应值，同态压缩值、从根节点到被挑战叶结点的路径及该路径上的兄弟结点；[0019]步骤3.5：根据线性响应值和同态压缩值进行无块同态验证，若验证失败，则输出证据无效的决策，终止验证，否则继续进行下一步；[0020]步骤3.6：计算其散列值；对于每个挑战块的同态压缩值，[0021]步骤3.7：根据步骤3.4中得到的路径上的兄弟结点和步骤2.3中生成的元数据，重建树，得到根；如果重建得到的树根与验证结构中的树根不相等，则输出证据无效的决策，终止验证，否则继续进行下一步；[0022]步骤3.3：验证成功，被挑战数据块是存在且完整的。[0023]本发明的系统所采用的技术方案是：一种数据存储系统中数据存在性和完整性校验系统，其特征在于：包括以下模块；[0024]模块一，用于从数据存储系统中获取原始数据块；[0025]模块二，用于创建验证结构；[0026]具体实现包括以下子步骤：[0027]步骤2.1：选择一组随机数生成器，并计算原始数据块的同态压缩值；[0028]步骤2.2：将原始数据块的同态压缩值计算得到的散列值作为叶节点，向上生成二叉hash树，每个节点的数据结构包括该结点的索引值、该节点可以达到的叶节点数和其散6CN 112699123 A说　明　书3/6页列值；步骤2.3：输出由二叉hash树与随机数生成器组成的验证结构和由节点与随机数生成器组成的元数据；[0030]模块三，用于输入挑战信息，根据步骤2.3中生成的验证结构及输入的挑战信息，进行被挑战数据块存在性和完整性校验；[0031]具体实现包括以下子步骤：[0032]步骤3.1：根据挑战信息中的块索引和验证结构中的生成元，计算挑战块的同态压缩值；[0033]步骤3.2：根据挑战信息中的块系数、块索引和验证结构中的生成元，计算挑战块的线性响应值；[0034]步骤3.3：计算从根节点到被挑战叶节点的路径及该路径上的兄弟节点，将计算结果整合成证据输出；[0035]步骤3.4：将证据解析，获得挑战块的线性响应值，同态压缩值、从根节点到被挑战叶结点的路径及该路径上的兄弟结点；[0036]步骤3.5：根据线性响应值和同态压缩值进行无块同态验证，若验证失败，则输出证据无效的决策，终止验证，否则继续进行下一步；[0037]步骤3.6：计算其散列值；对于每个挑战块的同态压缩值，[0038]步骤3.7：根据步骤3.4中得到的路径上的兄弟结点和步骤2.3中生成的元数据，重建树，得到根；如果重建得到的树根与验证结构中的树根不相等，则输出证据无效的决策，终止验证，否则继续进行下一步；[0039]步骤3.8：验证成功，被挑战数据块是存在且完整的。[0040]本发明提供了一种无块默克尔树验证结构及并给出了其使用方法。该结构与传统默克尔树相比，考虑了数据块数量巨大时的验证过程中的计算和存储开销问题，通过对传统默克尔树的结构进行优化，通过构造同态压缩和线性响应，使其可以实现无块验证，即验证过程中不需要原始数据块参与，极大地减小了验证过程中的计算和存储开销。[0041]本发明与传统默克尔树存在两个主要差异，首先，将额外的验证信息(即结点索引和块索引)嵌入到哈希值中，弥补了传统默克尔树的漏洞；其次，在叶节点下方加了一层存储数据块的散列值的节点，此修改可以实现无块验证。[0042]本发明在传统默克尔树的基础上进行改进，为了减轻验证器的计算和存储开销，在树的创建中，本发明的叶节点是基于数据块的同态压缩值直接生成的，实现一种轻量级的完整性校验方法。附图说明[0043]图1为本发明实施例的方法流程图。[0044][0029]图2为本发明实施例中D＝4且S＝3时生成的树，图中，且v4：＝(4,1,H(u1))。[0045]图3为本发明实施例中基于无块默克尔树的挑战应答模型。7CN 112699123 A说　明　书4/6页具体实施方式[0046]下面结合附图对本发明进行详细说明，但应当说明的是，这些实施方法并非对本发明的限制，本领域普通技术人员根据这些实施方法所作的功能、方法或者结构上的等效变换或替代，均属于本发明的保护范围之内。本说明树的各个实施例示出了无块默克尔树验证结构的具体实施方法，该实施方法主要包括无块默克尔树的创建方法、证明方法和验证方法。此方法与传统默克尔树相比，以前的方法中的默克尔树是基于标签而非文件生成的，而本发明的无块默克尔树生成算法是直接基于文件块生成的，因此其中的证明算法和验证算法与传统的算法有很大的不同。[0047]请见图1，本实施例提供的一种数据存储系统中数据存在性和完整性校验方法，设G为阶为素数p的乘法循环群，H：{0,1}*→{0,1}*为哈希函数。本实施例假设文件由D数据块组成，存储和处理文件时，数据块是基本单元(例如4KB和16KB)。但是，数据块太大，无法在中处理。因此，本实施例将每个数据块di划分为s段其中，表示模p的整数集合；[0048]本实施例的方法主要包括创建、证明和验证三个部分，创建方法基于哈希运算，得到一个称为无块默克尔树的验证结构及其元数据；证明方法基于挑战信息、验证结构和文件，生成证据；验证方法基于挑战信息、证据和元数据，生成证据是否有效的决策。[0049]1、树创建算法[0050]请见图2，当输入D个数据块时，该算法输出一个经过验证的结构和一些元数据，具体步骤如下：[0051](1)选择S随机生成器g1，…，gs∈G；[0052](2)对于每个数据块di，计算其中，表示gj的di，ui表示j次幂；数据块的同态压缩值；[0053](3)建立一个完整的二叉树τ和d叶节点，其中每个节点存储一个vl＝(l,ll,sl)其中l是树中节点的唯一索引，ll是第l个节点可以到达的叶节点数，sl是散列值；根节点的索引值为1，索引从上到下、从左到右均为递增；[0054](4)对于树中索引为li的第i个叶节点，设置ll＝1并计算其中，与H(ui)都表示ui的散列值；[0055](5)对于树中指数为l的每个非叶节点，分别计算li:＝l2l+l2l+1和sl：＝H(v2l||v2l+1)，其中，v2l＝(2l,l2l,s2l)和v2l+1＝(2l+1,l2l+1,s2l+1)分别为vl的左孩子和右孩子；[0056][0057](6)返回认证结构和元数据特别要说明的是，我们使用ui来计算存储在叶结点中的散列值，而不是di，这是本发明不需要标签和验证器的原因。[0058]2、树证明算法[0059]输入挑战(其中ib表示被挑战块的索引，树τ和是一个系数，B是被挑此算法生成一个战的块的数量,表示除0外模p的整数集合；数据块证据。具体的处理过程如下：8CN 112699123 A[0060]说　明　书并得到5/6页(1)计算其中，dib，j表示被挑战的数据块的第j段，uib表示被挑战的数据块dib的同态压缩值；[0061][0062][0063](2)计算并得到其中，μj表示证明值；其中，lib表示索引为ib的被挑战数据块在(3)计算从根结点到被挑战叶结点的路径及该路径上结点的兄弟结点θ；(4)返回证据树中的索引。[0064]在实践中，证明算法的第一步是不必要的，因为uib可以提前计算，还可以让树生成算法输出[0065][0066]并将存储为验证结构。证据树τ的根结点v1，此算法检查证据是否有3、验证算法输入挑战效。具体过程如下：[0067][0068][0069][0070](1)将解析为(2)如果(3)对每个uib，计算(4)根据θ和θ和不成立，则返回0；重建根，其中，这个重建过程与树构建算法相似。如果重建根与v1不相等，则返回0；[0071](5)返回1时说明证据有效。也就是说，每个对应于第ib个叶节点，并且不被篡改(1≤b≤B)。[0072]本实施例还提供了一种数据存储系统中数据存在性和完整性校验系统，包括以下模块；[0073]模块一，用于从数据存储系统中获取原始数据块；[0074]模块二，用于创建验证结构；[0075]具体实现包括以下子步骤：[0076]步骤2.1：选择一组随机数生成器，并计算原始数据块的同态压缩值；[0077]步骤2.2：将原始数据块的同态压缩值计算得到的散列值作为叶节点，向上生成二叉hash树，每个节点的数据结构包括该结点的索引值、该节点可以达到的叶节点数和其散列值；[0078]步骤2.3：输出由二叉hash树与随机数生成器组成的验证结构和由节点与随机数生成器组成的元数据；[0079]模块三，请见图3，用于输入挑战信息，根据步骤2.3中生成的验证结构及输入的挑战信息，进行被挑战数据块存在性和完整性校验；[0080]具体实现包括以下子步骤：[0081]步骤3.1：根据挑战信息中的块索引和验证结构中的生成元，计算挑战块的同态压缩值；9CN 112699123 A[0082]说　明　书6/6页步骤3.2：根据挑战信息中的块系数、块索引和验证结构中的生成元，计算挑战块的线性响应值；[0083]步骤3.3：计算从根节点到被挑战叶节点的路径及该路径上的兄弟节点，将计算结果整合成证据输出；[0084]步骤3.4：将证据解析，获得挑战块的线性响应值，同态压缩值、从根节点到被挑战叶结点的路径及该路径上的兄弟结点；[0085]步骤3.5：根据线性响应值和同态压缩值进行无块同态验证，若验证失败，则输出证据无效的决策，终止验证，否则继续进行下一步；[0086]步骤3.6：对于每个挑战块的同态压缩值，计算其散列值；[0087]步骤3.7：根据步骤3.4中得到的路径上的兄弟结点和步骤2.3中生成的元数据，重建树，得到根；如果重建得到的树根与验证结构中的树根不相等，则输出证据无效的决策，终止验证，否则继续进行下一步；[0088]步骤3.8：验证成功，被挑战数据块是存在且完整的。[0089]本实施例所列出的一系列的详细说明仅仅是针对本发明的可行性实施方式的具体说明，它们并非用以限制本发明的保护范围，凡为脱离本发明技艺精神所作的等效实施方式或变更均应包含在本发明的保护范围之内。[0090]对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括在本发明内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。[0091]以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。10CN 112699123 A说　明　书　附　图1/2页图1图211CN 112699123 A说　明　书　附　图2/2页图312