# US 2021/0243009 A1 · Correlation-based hash tree verification > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0243009 A1 - Document ID: US20210243009A1 - Status: Published application - Kind: A1 - Application number: 16/779,334 - Filed: 2020-01-31 - Published: 2021-08-05 - Earliest claimed: 2020-01-31 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Ryo Kawahara - Web page: https://patentgrep.com/patent/US20210243009A1 ## CPC - H04L 9/0637: {Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]} - H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD} - G06F 16/9027: {Trees} - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 9/50: {using hash chains, e.g. blockchains or hash trees} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An example operation may include one or more of receiving a request to verify a data store which stores key-value pairs, mapping values of key-value pairs of the data store to nodes of a hash tree structure based on a key-bucket map in which correlated key-value pairs are mapped to a same bucket or adjacent buckets within the hash tree structure, generating a root hash of the hash tree structure based on the values of the key-value pairs mapped to the nodes of the hash tree structure, and storing the generated root hash with a storage. ## Claims ### Claim 1 An apparatus comprising a processor configured to receive a request to verify a data store which stores key-value pairs, map values of key-value pairs of the data store to a nodes of a hash tree structure based on a key-bucket map in which correlated key-value pairs are mapped to a same bucket or adjacent buckets within the hash tree structure, and generate a root hash of the hash tree structure based on the values of the key-value pairs mapped to the nodes of the hash tree structure; and a storage configured to store the generated root hash. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the processor is configured to map a pair of correlated key-value pairs that are updated by a same blockchain transaction to a same bucket in the hash tree structure. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein the data store comprises a state database of a blockchain, and the processor is further configured to generate the key-bucket map based on correlations between key-values of blockchain transactions. ### Claim 4 (depends on 3) The apparatus of claim 3, wherein the processor is further configured to identify the correlations between the key-values of the blockchain transactions based on one or more of document identifiers, document types, user identifiers, and account identifiers. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein the processor is further configured to receive a modified key-bucket map and change a mapped value of a key-value pair from a first node to a second node of the hash tree structure based on the modified key-bucket map. ### Claim 6 (depends on 1) The apparatus of claim 1, wherein two adjacent buckets correspond to two adjacent nodes in the hash tree structure, respectively. ### Claim 7 (depends on 1) The apparatus of claim 1, wherein the processor is configured to modify an initial random and uniform map of key-value pairs to buckets of the hash tree structure based on the key-bucket map. ### Claim 8 (depends on 1) The apparatus of claim 1, wherein the hash tree structure comprises a Merkle tree, and the root hash comprises a root hash of the Merkle tree. ### Claim 9 A method comprising receiving a request to verify a data store which stores key-value pairs; mapping values of key-value pairs of the data store to nodes of a hash tree structure based on a key-bucket map in which correlated key-value pairs are mapped to a same bucket or adjacent buckets within the hash tree structure; generating a root hash of the hash tree structure based on the values of the key-value pairs mapped to the nodes of the hash tree structure; and storing the generated root hash with a storage. ### Claim 10 (depends on 9) The method of claim 9, wherein the mapping comprises mapping a pair of correlated key-value pairs that are updated by a same blockchain transaction to a same bucket in the hash tree structure. ### Claim 11 (depends on 9) The method of claim 9, wherein the data store comprises a state database of a blockchain, and the method further comprises generating the key-bucket map based on correlations between key-values of blockchain transactions. ### Claim 12 (depends on 11) The method of claim 11, further comprising identifying the correlations between the key-values of the blockchain transactions based on one or more of document identifiers, document types, user identifiers, and account identifiers. ### Claim 13 (depends on 9) The method of claim 9, further comprising receiving a modified key-bucket map and changing a mapping of a values of a key-value pair from a first node to a second node of the hash tree structure based on the modified key-bucket map. ### Claim 14 (depends on 9) The method of claim 9, wherein two adjacent buckets correspond to two adjacent nodes in the hash tree structure, respectively. ### Claim 15 (depends on 9) The method of claim 9, wherein the mapping comprises modifying an initial random and uniform mapping of key-value pairs to buckets of the hash tree structure based on the key-bucket map. ### Claim 16 (depends on 9) The method of claim 9, wherein the hash tree structure comprises a Merkle tree, and the root hash comprises a root hash of the Merkle tree. ### Claim 17 A non-transitory computer readable medium comprising instructions, that when read by a processor, cause the processor to perform a method comprising: receiving a request to verify a data store which stores key-value pairs; mapping values of key-value pairs of the data store to nodes of a hash tree structure based on a key-bucket map in which correlated key-value pairs are mapped to a same bucket or adjacent buckets within the hash tree structure; generating a root hash of the hash tree structure based on the values of the key-value pairs mapped to the nodes of the hash tree structure; and storing the generated root hash with a storage. ### Claim 18 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the mapping comprises mapping a pair of correlated key-value pairs that are updated by a same blockchain transaction to a same bucket in the hash tree structure. ### Claim 19 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the data store comprises a state database of a blockchain, and the method further comprises generating the key-bucket map based on correlations between key-values of blockchain transactions. ### Claim 20 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the method further comprises receiving a modified key-bucket map and changing a mapping of a values of a key-value pair from a first node to a second node of the hash tree structure based on the modified key-bucket map.