Updating blockchain world state Merkle Patricia Trie subtree

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 current node of the sub-tree is the root node.

12. The non-transitory computer-readable storage medium of claim 8 , 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.

13. The non-transitory computer-readable storage medium of claim 8 , wherein the update tree is created in response to a request received by the consensus client from the non-consensus client.

14. The non-transitory computer-readable storage medium of claim 8 , 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.

15. A 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 processing comprising:

create, 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;

execute, 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:

determine 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,

determine 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,

determine that the type of the current node of the sub-tree and 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

determine 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

transmit, 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.

16. The system of claim 15 , wherein the processing further comprises: 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.

17. The system of claim 15 , 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.

18. The system of claim 15 , wherein the traversal is ended in response to determining that the current node of the sub-tree is the root node.

19. The system of claim 15 , 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.

20. The system of claim 15 , wherein the update tree is created in response to a request received by the consensus client from the non-consensus client.