CN101930442A - Node updating method of Hash tree - Google Patents
Node updating method of Hash tree Download PDFInfo
- Publication number
- CN101930442A CN101930442A CN2009101498278A CN200910149827A CN101930442A CN 101930442 A CN101930442 A CN 101930442A CN 2009101498278 A CN2009101498278 A CN 2009101498278A CN 200910149827 A CN200910149827 A CN 200910149827A CN 101930442 A CN101930442 A CN 101930442A
- Authority
- CN
- China
- Prior art keywords
- node
- hash tree
- hash
- father node
- updating method
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 17
- 230000008569 process Effects 0.000 claims abstract description 5
- 230000006870 function Effects 0.000 description 13
- 230000008859 change Effects 0.000 description 3
- 230000008676 import Effects 0.000 description 2
- 230000015654 memory Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a node updating method of a Hash tree. The invention relates to an information safety technology, in particular to a method for generating check results based on the Hash tree for data. The invention aims at providing the node updating method of the Hash tree, thereby leading the data size which needs to be read by a system to be small when updating nodes. The key points of the adopted technology are as follows: the process of using the child nodes to update the father node is completed by adopting an incremental hash function; and the calculation according to the incremental hash function for obtaining the current value of the father node does not need to contrapose all the child nodes under the father node and only needs to contrapose the changed part of the child nodes under the father node.
Description
Technical field
The present invention relates to information security technology, specifically is a kind of method of data generation based on the check results of Hash tree that be.
Background technology
The safeguard protection of data relates to all many-sides; Wherein, the important point is the integrality (integrity) of checking data, promptly prevents the error (promptly makeing mistakes) or the unauthorized modification of data.In the completeness check technology of data, Hash tree (Hash Tree, or Merkle Tree; Consult: " R.C.Merkle.Protocols for public key cryptography.In IEEE Symposium on Security and Privacy; 1980 ", " M.Blum; W.Evans; P.Gemmell; S.Kannan and M.Naor.Checking the correctness of memories.IEEE Symposium on Foundations of Computer Science; 1991 " and " B.Gassend; G.E.Suh, D.Clarke, M.van Dijk, and S.Devadas.Caches and merkle trees for efficient memory authentication.Ninth International Symposium on High Performance Computer Architecture, 2003 ") be a kind of safe data integrity verifying technology.
Hash tree is organized with tree structure; Wherein, comprise the Hash tree node of some subordinate's nodes, be called father node, and its subordinate's node, be called this subordinate's of father node institute child node; The number of a subordinate's of father node institute child node is usually greater than 1; A subordinate's of father node institute child node is called the brotgher of node again each other.When child node changes and when upgrading corresponding father node, adopts hash function (Hash Function, or hash function; For example Chang Yong MD5 or SHA-1 function), connect all brotgher of node of the child node that changes, will connect the result and import hash function, upgrade the father node of correspondence with resulting Hash result.
Like this, the renewal of node just requires system at first to obtain the brotgher of node that is associated in the Hash tree; When brotgher of node number more just need read the data of larger amt, thus the performance that influence is upgraded.Therefore, be necessary to provide more effective node updating method.
Summary of the invention
The object of the present invention is to provide a kind of method of Hash tree node updates, when making more new node, the required data volume that reads of system is little.
The present invention is achieved by the following technical solutions:
Upgrade the process of father node by child node, adopt the increment hash function and finish.
In for the realization the technical solution adopted in the present invention, the increment hash function is: for drawing the calculating that currency carried out of father node, need be at this child node under the parent node whole, and only need be at the changing unit of this child node under the parent node.
The beneficial effect that the present invention had is: upgrade the required data volume of father node and be not directly proportional with the number of child node, and only be directly proportional with the child node of change; Thereby under the more situation of father node subordinate child node number, upgrading does not need to read extra more data, thereby realizes high more new capability.
Embodiment
Below the present invention is elaborated.Present embodiment is being to implement under the prerequisite with the technical solution of the present invention, has provided detailed embodiment and concrete operating process; But protection scope of the present invention is not limited to following embodiment.
For describing this embodiment, suppose that the Hash tree root node is R1; 4 nodes of R1 subordinate are respectively F1, F2, F3 and F4; 4 nodes of F1 node subordinate are respectively C1, C2, C3 and C4.With regard to " F1 " and " C1, C2, C3 and C4 ", " F1 " is father node, and " C1, C2, C3 and C4 " is the child node of " F1 ", and " C1, C2, C3 and C4 " is the brotgher of node each other.
When C1 changed, Hash tree need calculate the currency of new F1 according to the currency of C1.Usually, can adopt hash function commonly used,, calculate the new value of F1 according to following formula as the MD5 algorithm:
F1
NEW＝MD5(C1
NEW‖C2‖C3‖C4)
That is, connect (with " ‖ " expression) currency C1 after C1 changes
NEW, C2, C3 and C4, and will connect the result and import the MD5 function, and the result who obtains is as the currency F1 of F1
NEWFor this reason, just need read C2, C3 and C4, although they do not change.
According to method proposed by the invention, adopt the increment hash function to calculate the currency of F1.For this reason, the computation process of being implemented is:
Node
OLD＝(C1
OLD‖C2‖C3‖C4)
Node
NEW＝(C1
NEW‖C2‖C3‖C4)
F1
NEW＝I_Hash(F1
OLD，(Node
OLD.XOR.Node
NEW))
Wherein, " Node
OLD" be the initial value that 4 child nodes connect, " Node
NEW" be the currency that 4 child nodes connect, " XOR " is xor operation; Thereby, " (Node
OLD.XOR.Node
NEW) " be the changing unit of node in fact, in other words, be exactly of the change of the currency of C1 with respect to initial value, and irrelevant with unchanged C2, C3 and C4." I_Hash " is the increment hash function, " F1
OLD" be the initial value of F1, and " F1
NEW" then be new F1 result.As seen, system does not need to read C2～C4, just can finish the renewal to F1.
In addition, the increment function function " I_Hash " here can adopt multiple algorithm to constitute, as " M.Bellare; O.Goldteich and S.Goldwasser.Incremental cryptography:the case of hashing and signing.Crypto 94; 1994. ", " David McGrew.Efficient authentication of large; dynamic data sets using Galois/Counter Mode (GCM) .IEEE International Security in Storage Workshop, 2005 ".But the increment function of being constructed need satisfy the ability that can upgrade whole data set Hash result according to the data variation part.
The present invention is not limited to above-mentioned specifically described realization form, but is applicable to the more system of new capability of the obtainable raising Hash tree of all foundations content of the present invention.This comprises on the equipment such as being configured in disk, storer, comprises forms such as using hardware, software; Or the like.
The present invention is applicable to all foundations content of the present invention and the method for constructing, and does not need the ability of other invention character and obtainable version.Therefore, the present invention is applicable to principle as described herein and feature the widest corresponding to scope.
Claims (2)
1. the node updating method of a Hash tree is characterized in that:
Upgrade the process of father node by child node, adopt the increment hash function and finish.
2. the node updating method of Hash tree according to claim 1 is characterized in that:
Described increment hash function is: for drawing the calculating that currency carried out of father node, need be at this child node under the parent node whole, and only need be at the changing unit of this child node under the parent node.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2009101498278A CN101930442A (en) | 2009-06-24 | 2009-06-24 | Node updating method of Hash tree |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2009101498278A CN101930442A (en) | 2009-06-24 | 2009-06-24 | Node updating method of Hash tree |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN101930442A true CN101930442A (en) | 2010-12-29 |
Family
ID=43369623
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2009101498278A Pending CN101930442A (en) | 2009-06-24 | 2009-06-24 | Node updating method of Hash tree |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101930442A (en) |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103812912A (en) * | 2012-11-14 | 2014-05-21 | 北京慧点科技股份有限公司 | Method and device for maintaining organization structure information |
| CN104915381A (en) * | 2015-05-18 | 2015-09-16 | 北京联信永通信息技术有限公司 | Perceiving and rapid synchronizing method for data changing |
| CN106657174A (en) * | 2015-10-28 | 2017-05-10 | 阿里巴巴集团控股有限公司 | Data synchronizing and updating methods and data synchronizing and updating devices |
| CN110399534A (en) * | 2019-07-31 | 2019-11-01 | 京信通信系统（中国）有限公司 | Method, device, device and storage medium for generating terminal performance report |
| US10587454B2 (en) | 2018-01-30 | 2020-03-10 | Hewlett Packard Enterprise Development Lp | Object counts persistence for object stores |
| JP2020515197A (en) * | 2016-12-26 | 2020-05-21 | アリババ・グループ・ホールディング・リミテッドＡｌｉｂａｂａ Ｇｒｏｕｐ Ｈｏｌｄｉｎｇ Ｌｉｍｉｔｅｄ | Block data verification method and device |
| CN111373388A (en) * | 2017-12-28 | 2020-07-03 | 卓普网盘股份有限公司 | Efficiently propagating differentiated values |
| CN112559518A (en) * | 2020-12-10 | 2021-03-26 | 杭州趣链科技有限公司 | Merck tree updating method, terminal device and storage medium |
-
2009
- 2009-06-24 CN CN2009101498278A patent/CN101930442A/en active Pending
Cited By (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103812912A (en) * | 2012-11-14 | 2014-05-21 | 北京慧点科技股份有限公司 | Method and device for maintaining organization structure information |
| CN103812912B (en) * | 2012-11-14 | 2018-01-19 | 北京慧点科技股份有限公司 | A kind of method and device of maintenance organization structural information |
| CN104915381A (en) * | 2015-05-18 | 2015-09-16 | 北京联信永通信息技术有限公司 | Perceiving and rapid synchronizing method for data changing |
| CN106657174A (en) * | 2015-10-28 | 2017-05-10 | 阿里巴巴集团控股有限公司 | Data synchronizing and updating methods and data synchronizing and updating devices |
| CN106657174B (en) * | 2015-10-28 | 2020-11-03 | 阿里巴巴集团控股有限公司 | Data synchronization method, data updating method and data updating device |
| JP2020515197A (en) * | 2016-12-26 | 2020-05-21 | アリババ・グループ・ホールディング・リミテッドＡｌｉｂａｂａ Ｇｒｏｕｐ Ｈｏｌｄｉｎｇ Ｌｉｍｉｔｅｄ | Block data verification method and device |
| US11836151B2 (en) | 2017-12-28 | 2023-12-05 | Dropbox, Inc. | Synchronizing symbolic links |
| CN111373388A (en) * | 2017-12-28 | 2020-07-03 | 卓普网盘股份有限公司 | Efficiently propagating differentiated values |
| US12169505B2 (en) | 2017-12-28 | 2024-12-17 | Dropbox, Inc. | Updating a local tree for a client synchronization service |
| US12135733B2 (en) | 2017-12-28 | 2024-11-05 | Dropbox, Inc. | File journal interface for synchronizing content |
| US12061623B2 (en) | 2017-12-28 | 2024-08-13 | Dropbox, Inc. | Selective synchronization of content items in a content management system |
| CN111373388B (en) * | 2017-12-28 | 2024-03-15 | 卓普网盘股份有限公司 | Methods and devices for effectively communicating differentiated values |
| US11657067B2 (en) | 2017-12-28 | 2023-05-23 | Dropbox Inc. | Updating a remote tree for a client synchronization service |
| US11669544B2 (en) | 2017-12-28 | 2023-06-06 | Dropbox, Inc. | Allocation and reassignment of unique identifiers for synchronization of content items |
| US11704336B2 (en) | 2017-12-28 | 2023-07-18 | Dropbox, Inc. | Efficient filename storage and retrieval |
| US10587454B2 (en) | 2018-01-30 | 2020-03-10 | Hewlett Packard Enterprise Development Lp | Object counts persistence for object stores |
| US10862736B2 (en) | 2018-01-30 | 2020-12-08 | Hewlett Packard Enterprise Development Lp | Object counts persistence for object stores |
| CN110399534B (en) * | 2019-07-31 | 2022-03-25 | 京信网络系统股份有限公司 | Method, device, device and storage medium for generating terminal performance report |
| CN110399534A (en) * | 2019-07-31 | 2019-11-01 | 京信通信系统（中国）有限公司 | Method, device, device and storage medium for generating terminal performance report |
| CN112559518A (en) * | 2020-12-10 | 2021-03-26 | 杭州趣链科技有限公司 | Merck tree updating method, terminal device and storage medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101930442A (en) | Node updating method of Hash tree | |
| CN108322306B (en) | A privacy protection-oriented cloud platform trusted log audit method based on a trusted third party | |
| CN110912706B (en) | An Identity-Based Dynamic Data Integrity Audit Method | |
| Zheng et al. | Fair and dynamic proofs of retrievability | |
| CN103268460B (en) | A kind of cloud integrity of data stored verification method | |
| CN103888262B (en) | Secret key changing and signature updating method for cloud data audit | |
| Chen et al. | Data dynamics for remote data possession checking in cloud storage | |
| CN115017170B (en) | A traceable blockchain transaction trusted erasure method and device | |
| CN105162583A (en) | Scatter method and system for single asymmetrical secret key pair, single-stage asymmetrical secret key pair and multistage asymmetrical secret key pair | |
| CN112565264A (en) | Block chain-based cloud storage data integrity detection method and system | |
| CN114026586A (en) | Zero-knowledge contingent payment protocol for granting access to crypto assets | |
| Chen et al. | Secure cloud storage hits distributed string equality checking: More efficient, conceptually simpler, and provably secure | |
| Wang et al. | Privacy-preserving time-based auditing for secure cloud storage | |
| Shi et al. | Threshold EdDSA signature for blockchain-based decentralized finance applications | |
| CN110225012B (en) | An Ownership Check and Update Method for Outsourced Data Based on Consortium Chain | |
| Yang et al. | Multi-client verifiable encrypted keyword search scheme with authorization over outsourced encrypted data | |
| CN114969836A (en) | SM2 digital signature method and system for resisting side channel attack | |
| CN120850266A (en) | Blockchain-based distributed trusted data space construction method and system | |
| Wu et al. | Slicer: Verifiable, secure and fair search over encrypted numerical data using blockchain | |
| CN118969232B (en) | Medical equipment disinfection traceability management system | |
| CN116155619B (en) | Data processing method, data requester, data owner and data processing device | |
| Khatri et al. | Improving dynamic data integrity verification in cloud computing | |
| CN113259094B (en) | Universal hierarchical signature encryption system and construction method | |
| JP6931331B2 (en) | Blockchain management system, blockchain management method and blockchain management program | |
| CN118381642A (en) | Data integrity verification method, device, electronic device and storage medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C02 | Deemed withdrawal of patent application after publication (patent law 2001) | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20101229 |