# US 2021/0243013 A1 · Updating a state merkle tree > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0243013 A1 - Document ID: US20210243013A1 - Status: Published application - Kind: A1 - Application number: 17/239,346 - Filed: 2021-04-23 - Published: 2021-08-05 - Earliest claimed: 2019-08-30 - Assignees: Advanced New Technologies Co., Ltd. - Applicants: Advanced New Technologies Co., Ltd. - Inventors: Zhonghao Lu - Web page: https://patentgrep.com/patent/US20210243013A1 ## CPC - G06F 16/901: Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951) - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - G06F 16/9027: {Trees} - H04L 9/0637: {Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]} - H04L 9/0891: {Revocation or update of secret information, e.g. encryption key update or rekeying} - H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD} - H04L 9/50: {using hash chains, e.g. blockchains or hash trees} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Implementations of the present specification provide a method for updating a state Merkle tree, where the state Merkle tree is used to store a state of an account in a blockchain network. The method includes: accessing data related to a state Merkle tree that stores a state of an account in a blockchain network; determining to-be-updated nodes that need to be updated in the state Merkle tree due to a state change of the account; extracting one first subtree and M second subtrees from the state Merkle tree based on the to-be-updated nodes; allocating the M second subtrees to N worker threads, wherein two or more of the N worker threads process in parallel the M second subtrees to obtain each updated second subtree; and updating at least the first subtree based on hash values of root nodes of the updated second subtrees, to obtain an updated state Merkle tree. ## Claims ### Claim 1 A computer-implemented method for updating a blockchain network, the method comprising: accessing data related to a state Merkle tree, wherein the state Merkle tree stores a state of an account in a blockchain network; determining to-be-updated nodes that need to be updated in the state Merkle tree due to a state change of the account; extracting a first subtree and M second subtrees from the state Merkle tree based on the to-be-updated nodes, wherein the first subtree comprises a root node of the state Merkle tree, wherein there is no intersection between any two of the M second subtrees, wherein a root node of each second subtree is a to-be-updated node and is a child node of a bottom-layer node in the first subtree, and wherein M is an integer greater than 1; allocating the M second subtrees to N worker threads, wherein two or more of the N worker threads process in parallel the M second subtrees to obtain M updated root hashes corresponding to the M second subtrees, wherein N is an integer greater than 1; and updating at least the first subtree from one or more leaf nodes of the first subtree to the root node of the state Merkle tree based on the M updated root hashes obtained from the N worker threads, to obtain an updated state Merkle tree. ### Claim 2 (depends on 1) The computer-implemented method according to claim 1, further comprising, before determining the to-be-updated nodes that need to be updated in the state Merkle tree due to the state change of the account: executing each transaction in a transaction set to determine the state change of the account involved in the transaction. ### Claim 3 (depends on 2) The computer-implemented method according to claim 2, wherein the transaction set comprises transactions selected from a local transaction pool, and wherein the method further comprises: packaging the transaction set into a first block after the updated state Merkle tree is obtained, and recording a hash value of the root node of the updated state Merkle tree into the first block. ### Claim 4 (depends on 2) The computer-implemented method according to claim 2, wherein the transaction set comprises transactions and is comprised in a to-be-verified block, and wherein the method further comprises: comparing a hash value of a root node of the updated state Merkle tree with a value of a state root recorded in the to-be-verified block after the updated state Merkle tree is obtained, to verify the to-be-verified block. ### Claim 5 (depends on 1) The method according to claim 1, wherein determining the to-be-updated nodes that need to be updated in the state Merkle tree due to the state change of the account comprises: in the state Merkle tree, tracing back to the root node of the state Merkle tree starting from the one or more leaf nodes that correspond to accounts whose state changes, and determining each node on a trace path as the to-be-updated nodes. ### Claim 6 (depends on 1) The method according to claim 1, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: extracting nodes starting from the root node of the state Merkle tree to a predetermined layer in the state Merkle tree as the first subtree. ### Claim 7 (depends on 1) The method according to claim 1, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: traversing the state Merkle tree layer by layer starting from the root node of the state Merkle tree based on a breadth-first search, and if a number of to-be-updated nodes at a current layer is greater than or equal to a first predetermined threshold, extracting nodes starting from the root node of the state Merkle tree to the current layer as the first subtree. ### Claim 8 (depends on 6) The method according to claim 6, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: obtaining one or more nodes of the to-be-updated nodes in bottom-layer nodes of the first subtree as a first node set; obtaining one or more nodes of the to-be-updated nodes in child nodes of each node in the first node set as a second node set; and separately using each node in the second node set as a starting node to obtain subtrees starting from each starting node to a leaf node as the M second subtrees. ### Claim 9 (depends on 1) The method according to claim 1, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: traversing the state Merkle tree layer by layer starting from the root node of the state Merkle tree based on a breadth-first search, if a number of to-be-updated nodes at a current layer is greater than or equal to a second predetermined threshold, extracting nodes starting from the root node of the state Merkle tree to a layer above the current layer as the first subtree, and using each to-be-updated node at the current layer as a starting node to obtain subtrees starting from each starting node to a leaf node as the M second subtrees. ### Claim 10 (depends on 1) The method according to claim 1, wherein allocating the M second subtrees to the N worker threads comprises: separately numbering the M second subtrees and the N worker threads, so each second subtree has a corresponding first number, and each worker thread has a corresponding second number; and for a second subtree of the M second subtrees, determining a modulo result of the corresponding first number modulo the corresponding second number, and allocating the second subtree to a worker thread whose second number is the modulo result, wherein the corresponding first number corresponds to the second subtree. ### Claim 11 A computer-implemented system, comprising: one or more computers; and one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations for updating a blockchain network, wherein the operations comprise: accessing data related to a state Merkle tree, wherein the state Merkle tree stores a state of an account in a blockchain network; determining to-be-updated nodes that need to be updated in the state Merkle tree due to a state change of the account; extracting a first subtree and M second subtrees from the state Merkle tree based on the to-be-updated nodes, wherein the first subtree comprises a root node of the state Merkle tree, wherein there is no intersection between any two of the M second subtrees, wherein a root node of each second subtree is a to-be-updated node and is a child node of a bottom-layer node in the first subtree, and wherein M is an integer greater than 1; allocating the M second subtrees to N worker threads, wherein two or more of the N worker threads process in parallel the M second subtrees to obtain M updated root hashes corresponding to the M second subtrees, wherein N is an integer greater than 1; and updating at least the first subtree from one or more leaf nodes of the first subtree to the root node of the state Merkle tree based on the M updated root hashes obtained from the N worker threads, to obtain an updated state Merkle tree. ### Claim 12 (depends on 11) The computer-implemented system of claim 11, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: traversing the state Merkle tree layer by layer starting from the root node of the state Merkle tree based on a breadth-first search, and if a number of to-be-updated nodes at a current layer is greater than or equal to a first predetermined threshold, extracting nodes starting from the root node of the state Merkle tree to the current layer as the first subtree. ### Claim 13 (depends on 11) The computer-implemented system of claim 11, wherein allocating the M second subtrees to the N worker threads comprises: separately numbering the M second subtrees and the N worker threads, so each second subtree has a corresponding first number, and each worker thread has a corresponding second number; and for a second subtree of the M second subtrees, determining a modulo result of the corresponding first number modulo the corresponding second number, and allocating the second subtree to a worker thread whose second number is the modulo result, wherein the corresponding first number corresponds to the second subtree. ### Claim 14 A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations for updating a blockchain network, wherein the operations comprise: accessing data related to a state Merkle tree, wherein the state Merkle tree stores a state of an account in a blockchain network; determining to-be-updated nodes that need to be updated in the state Merkle tree due to a state change of the account; extracting a first subtree and M second subtrees from the state Merkle tree based on the to-be-updated nodes, wherein the first subtree comprises a root node of the state Merkle tree, wherein there is no intersection between any two of the M second subtrees, wherein a root node of each second subtree is a to-be-updated node and is a child node of a bottom-layer node in the first subtree, and wherein M is an integer greater than 1; allocating the M second subtrees to N worker threads, wherein two or more of the N worker threads process in parallel the M second subtrees to obtain M updated root hashes corresponding to the M second subtrees, wherein N is an integer greater than 1; and updating at least the first subtree from one or more leaf nodes of the first subtree to the root node of the state Merkle tree based on the M updated root hashes obtained from the N worker threads, to obtain an updated state Merkle tree. ### Claim 15 (depends on 14) The non-transitory, computer-readable medium of claim 14, further comprising, before determining the to-be-updated nodes that need to be updated in the state Merkle tree due to the state change of the account: executing each transaction in a transaction set to determine the state change of the account involved in the transaction. ### Claim 16 (depends on 15) The non-transitory, computer-readable medium of claim 15, wherein the transaction set comprises transactions selected from a local transaction pool, and wherein the operations further comprise: packaging the transaction set into a first block after the updated state Merkle tree is obtained, and recording a hash value of the root node of the updated state Merkle tree into the first block. ### Claim 17 (depends on 15) The non-transitory, computer-readable medium of claim 15, wherein the transaction set comprises transactions and is comprised in a to-be-verified block, and wherein the operations further comprise: comparing a hash value of a root node of the updated state Merkle tree with a value of a state root recorded in the to-be-verified block after the updated state Merkle tree is obtained, to verify the to-be-verified block. ### Claim 18 (depends on 14) The non-transitory, computer-readable medium of claim 14, wherein determining the to-be-updated nodes that need to be updated in the state Merkle tree due to the state change of the account comprises: in the state Merkle tree, tracing back to the root node of the state Merkle tree starting from the one or more leaf nodes that correspond to accounts whose state changes, and determining each node on a trace path as the to-be-updated nodes. ### Claim 19 (depends on 14) The non-transitory, computer-readable medium of claim 14, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: traversing the state Merkle tree layer by layer starting from the root node of the state Merkle tree based on a breadth-first search, and if a number of to-be-updated nodes at a current layer is greater than or equal to a first predetermined threshold, extracting nodes starting from the root node of the state Merkle tree to the current layer as the first subtree. ### Claim 20 (depends on 14) The non-transitory, computer-readable medium of claim 14, wherein extracting the first subtree and the M second subtrees from the state Merkle tree based on the to-be-updated nodes comprises: traversing the state Merkle tree layer by layer starting from the root node of the state Merkle tree based on a breadth-first search, if a number of to-be-updated nodes at a current layer is greater than or equal to a second predetermined threshold, extracting nodes starting from the root node of the state Merkle tree to a layer above the current layer as the first subtree, and using each to-be-updated node at the current layer as a starting node to obtain subtrees starting from each starting node to a leaf node as the M second subtrees.