Updating blockchain world state Merkle Patricia Trie subtree

Patent metadata

Field	Value
Publication number	US-10691676-B1
Application number	US-201916587155-A
Country	US
Kind code	B1
Filing date	Sep 30, 2019
Priority date	Mar 4, 2019
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

Implementations of this specification include traversing a sub-tree of a world-state MPT in multiple iterations, and, at each iteration, for a current node of the sub-tree, executing one of: adding the current node of the world-state MPT to the update tree, adding the current node of the world-state MPT to the update tree, and moving to a next iteration of the traversal setting the current node of the sub-tree to a node referenced by the extension node, adding the current node of the world-state MPT to the update tree, and moving to a next iteration of the traversal setting the current node of the sub-tree to a node pointed to by a slot of the current node of the sub-tree; and transmitting the update tree to a client for updating a locally stored sub-tree using the update tree.

First claim

What is claimed is:

1. A computer-implemented method for updating a sub-tree of a world-state Merkle Patricia Trie (MPT) within a blockchain network, the method comprising:
creating, by a consensus client of the blockchain network, an update tree comprising a root node of the sub-tree of the world-state MPT and new nodes that are added to the update tree;
executing, by the consensus client, a traversal of at least a portion of the sub-tree in a plurality of iterations
at each iteration, for a current node of the sub-tree, determining a type of the current node of the sub-tree and a value of the current node, the type comprising leaf nodes, extension nodes, and branch nodes, at least one of the branch nodes comprising a transition node between two or more leaf nodes, the transition node marking merged paths from the root node of the sub-tree to the transition node that apply to each of the respective two or more leaf nodes;
comparing the value of the current node of the sub-tree to a respective node of the world-state MPT based on the type of the current node of the sub-tree;
in response to comparing the value of the current node of the sub-tree to the respective node of the world-state MPT, executing one of:
determining that the type of the current node of the sub-tree and the respective node of the world-state MPT comprises the leaf nodes, and corresponding values are unequal, and, in response, adding the respective node of the world-state MPT to the update tree,
determining that the type of the current node of the sub-tree and the the respective node of the world-state MPT comprise the extension nodes, and, in response, adding the current node of the world-state MPT to the update tree, and moving to a next iteration of the traversal setting the current node of the sub-tree to a reference node referenced by the extension node,
determining that the type of the current node of the sub-tree and the the respective node of the world-state MPT comprise the branch nodes, and the values are unequal, and, in response, adding the respective node of the world-state MPT to the update tree, and
determining that the type of the current node of the sub-tree and the the respective node of the world-state MPT comprise the branch nodes, and the values are equal, and, in response, moving to a next iteration of the traversal setting the current node of the sub-tree to a node pointed to by a slot of the current node of the sub-tree; and

transmitting, by the consensus client, the update tree of the sub-tree to a non-consensus client of the blockchain network, the non-consensus client updating a locally stored sub-tree using the update tree to provide an updated sub-tree that provides a state of accounts associated with the non-consensus client.

2. The method of claim 1 , further comprising, during at least one iteration, finding a corresponding node in the world-state MPT, and providing a search path, one or more nodes in the search path being marked as intermediate nodes, and marked as being absent from the sub-tree.

3. The method of claim 1 , wherein comparing values of the current node of the sub-tree and a current node of the world-state MPT is performed in response to determining that the current node of the sub-tree and a current node of the world-state MPT are branch nodes, and that a current iteration is a first iteration, in which the current node of the sub-tree is considered.

4. The method of claim 1 , wherein the traversal is ended in response to determining that the current node of the sub-tree is the root node.

5. The method of claim 1 , wherein the locally stored sub-tree is updated by one or more of replacing a node of the sub-tree with a node of the update tree, and inserting a node of the update tree into the sub-tree.

6. The method of claim 1 , wherein the update tree is created in response to a request received by the consensus client from the non-consensus client.

7. The method of claim 1 , wherein the update tree is created in response to determining that a value of a root node of the sub-tree and a value of the root node of the world-state MPT are different.

8. A non-transitory, computer-readable storage medium storing one or more instructions executable by a computer system to perform operations comprising:
creating, by a consensus client of the blockchain network, an update tree comprising a root node of the sub-tree of the world-state MPT and new nodes that are added to the update tree;
executing, by the consensus client, a traversal of at least a portion of the sub-tree in a plurality of iterations
at each iteration, for a current node of the sub-tree, determining a type of the current node of the sub-tree and a value of the current node, the type comprising leaf nodes, extension nodes, and branch nodes, at least one of the branch nodes comprising a transition node between two or more leaf nodes, the transition node marking merged paths from the root node of the sub-tree to the transition node that apply to each of the respective two or more leaf nodes;
comparing the value of the current node of the sub-tree to a respective node of the world-state MPT based on the type of the current node of the sub-tree;
in response to comparing, executing one of:
determining that the type of the current node of the sub-tree and the respective node of the world-state MPT comprises the leaf nodes, and corresponding values are unequal, and, in response, adding the respective node of the world-state MPT to the update tree,
determining that the type of the current node of the sub-tree and the the respective node of the world-state MPT comprise the extension nodes, and, in response, adding the current node of the world-state MPT to the update tree, and moving to a next iteration of the traversal setting the current node of the sub-tree to a reference node referenced by the extension node,
determining that the type of the current node of the sub-tree and the the respective node of the world-state MPT comprise the branch nodes, and the values are unequal, and, in response, adding the respective node of the world-state MPT to the update tree, and
determining that the type of the current node of the sub-tree and the the respective node of the world-state MPT comprise the branch nodes, and the values are equal, and, in response, moving to a next iteration of the traversal setting the current node of the sub-tree to a node pointed to by a slot of the current node of the sub-tree; and

transmitting, by the consensus client, the update tree of the sub-tree to a non-consensus client of the blockchain network, the non-consensus client updating a locally stored sub-tree using the update tree to provide an updated sub-tree that provides a state of accounts associated with the non-consensus client.

9. The non-transitory computer-readable storage medium of claim 8 , configured with further instructions executable by the one or more computer to, during at least one iteration, find a corresponding node in the world-state MPT, and providing a search path, one or more nodes in the search path being marked as intermediate nodes, and marked as being absent from the sub-tree.

10. The non-transitory computer-readable storage medium of claim 8 , wherein comparing values of the current node of the sub-tree and a current node of the world-state MPT is performed in response to determining that the current node of the sub-tree and a current node of the world-state MPT are branch nodes, and that a current iteration is a first iteration, in which the current node of the sub-tree is considered.

11. The non-transitory computer-readable storage medium of claim 8 , wherein the traversal is ended in response to determining that the cur

Assignees

• Alibaba Group Holding Ltd

Inventors

• Zhang Wenbin

Classifications

• G06F16/23

  Updating · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/2372

  Updates performed during offline database operations · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/2379 Primary

  Updates performed during online database operations; commit processing · CPC title