Constructing blockchain world state Merkle Patricia Trie subtree
Implementations of this specification include traversing a world-state MPT in multiple iterations, and, at each iteration, for a current node of the world-state MPT, executing one of: marking the current node as an account node and storing an address of the current node in the address list, determining that the current node is an extension node, and moving to a next iteration of the traversal setting the current node to a node referenced by the extension node, and marking the current node as a transition node, and storing an address of the current node in the address list; creating a sub-tree of the world-state MPT based on the address list, a root node of the sub-tree including a root node of the world-state MPT, and one or more child nodes of the sub-tree corresponding to nodes of the world-state MPT having an address stored in the address list.
1. A computer-implemented method for providing a sub-tree of a hash tree within a blockchain network, the method comprising:
providing, by a consensus client of the blockchain network, the hash tree and an address list for storing addresses of nodes within the blockchain network, the address list being initially empty;
executing, by the consensus client, a traversal of at least a portion of the hash tree in a plurality of iterations to perform operations comprising:
marking a first node of the hash tree as an account node, and storing an address of the first node in the address list,
marking a second node of the hash tree as an extension node, and moving to a next iteration of the traversal setting referenced by the second node, and
marking a third node of the hash tree as a transition node, and storing an address of the third node in the address list;
generating, by the consensus client, the sub-tree of the hash tree based on the address list, a sub-tree root node of the sub-tree comprising a root node of the hash tree, and one or more of the first node, the second node, and the third node; and
transmitting, by the consensus client, the sub-tree of the hash tree to a non-consensus client of the blockchain network, the sub-tree providing a state of accounts associated with the non-consensus client.
2. The method of claim 1 , wherein the third node is marked as the transition node in response to determining that the third node is a branch node, and that all children nodes of the branch node have been traversed.
3. The method of claim 1 , wherein, after marking the first node as the account node, the first node of the next iteration of the traversal comprises a parent node of the account node.
4. The method of claim 1 , wherein, after marking the first node as the account node, the first node of the next iteration of the traversal comprises a child node of the one of the account node and the transition node.
5. The method of claim 1 , wherein generating the sub-tree of the hash tree based on the address list at least partially comprises, for an address marked as the account node in the address list, determining a path within the hash tree, and adding the path to the sub-tree.
6. The method of claim 1 , wherein the traversal comprises a depth-first pre-order traversal.
7. A non-transitory computer-readable storage medium storing one or more instructions executable by a computer system to perform operations for providing a sub-tree of a hash tree within a blockchain network, the operations comprising:
providing, by a consensus client of the blockchain network, the hash tree and an address list for storing addresses of nodes within the blockchain network, the address list being initially empty;
executing, by the consensus client, a traversal of at least a portion of the hash tree in a plurality of iterations to perform operations comprising:
marking a first node of the hash tree as an account node, and storing an address of the first node in the address list,
marking a second node of the hash tree as an extension node, and moving to a next iteration of the traversal setting referenced by the second node, and
marking a third node of the hash tree as a transition node, and storing an address of the third node in the address list;
generating, by the consensus client, the sub-tree of the hash tree based on the address list, a sub-tree root node of the sub-tree comprising a root node of the hash tree, and one or more of the first node, the second node, and the third node; and
transmitting, by the consensus client, the sub-tree of the hash tree to a non-consensus client of the blockchain network, the sub-tree providing a state of accounts associated with the non-consensus client.
8. The non-transitory computer-readable storage medium of claim 7 , wherein the first node is marked as the account node in response to determining that the first node is one of a leaf node, and a branch node that is absent a null value.
9. The non-transitory computer-readable storage medium of claim 7 , wherein the third node is marked as the transition node in response to determining that the third node is a branch node, and that all children nodes of the branch node have been traversed.
10. The non-transitory computer-readable storage medium of claim 7 , wherein, after marking the first node as the account node, the first node of the next iteration of the traversal comprises a parent node of the account node.
11. The non-transitory computer-readable storage medium of claim 7 , wherein, after marking the first node as one of the account node, the first node of the next iteration of the traversal comprises a child node of the one of the account node and the transition node.
12. The non-transitory computer-readable storage medium of claim 7 , wherein generating the sub-tree of the hash tree based on the address list at least partially comprises, for an address marked as the account node in the address list, determining a path within the hash tree, and adding the path to the sub-tree.
13. The non-transitory computer-readable storage medium of claim 7 , wherein the traversal comprises a depth-first pre-order traversal.
14. 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 operations for providing a sub-tree of a hash tree within a blockchain network, the operations comprising:
providing, by a consensus client of the blockchain network, the hash tree and an address list for storing addresses of nodes within the blockchain network, the address list being initially empty,
executing, by the consensus client, a traversal of at least a portion of the hash tree in a plurality of iterations to perform operations comprising:
marking a first node of the hash tree as an account node, and storing an address of the first node in the address list,
marking a second node of the hash tree as an extension node, and moving to a next iteration of the traversal setting referenced by the second node, and
marking a third node of the hash tree as a transition node, and storing an address of the third node in the address list,
generating, by the consensus client, the sub-tree of the hash tree based on the address list, a sub-tree root node of the sub-tree comprising a root node of the hash tree, and one or more of the first node, the second node, and the third node, and
transmitting, by the consensus client, the sub-tree of the hash tree to a non-consensus client of the blockchain network, the sub-tree providing a state of accounts associated with the non-consensus client.
15. The system of claim 14 , wherein the first node is marked as the account node in response to determining that the first node is one of a leaf node, and a branch node that is absent a null value.
16. The system of claim 14 , wherein the third node is marked as a transition node in response to determining that the third node is a branch node, and that all children nodes of the branch node have been traversed.
17. The system of claim 14 , wherein, after marking the first node as the account node, the first node of the next iteration of the traversal comprises a parent node of the account node.
18. The system of claim 14 , wherein, after marking the first node as one of the account node, the first node of the next iteration of the traversal comprises a child node of the one of the account node and the transition node.
19. The system of claim 14 , wherein generating the sub-tree of the hash tree based on the address list at least partially comprises, for an address marked as the account node in the address list, determining a path within the hash tree, and adding the path to the sub-tree.
20. The system of claim 14 , wherein the traversal comprises a depth-first pre-order traversal.