Blockchain World State Merkle Patricia Tree

Blockchain World State Merkle Patricia Tree

Glossary

Term Definition Blockchain A sequence of data blocks linked together in chronological order, each containing a set of transaction information. Distributed Ledger System (DLS) A system for sharing and synchronizing data between multiple participants. Consensus Network A group of computer networks that reach an agreement through a consensus mechanism. World State The global state of a blockchain network at a specific point in time, including information about all accounts and smart contracts. Merkle Patricia Tree (MPT) A cryptographically hashed data structure used to efficiently store and verify large amounts of data, such as the blockchain world state. Subtree A part of a tree consisting of a node and all its descendant nodes. Root Node The topmost node of a tree. Branch Node A node with multiple child nodes. Extension Node A node that provides path compression between two branch nodes. Leaf Node A node without child nodes, usually storing actual data. Transition Node The most recent ancestor node shared between two account nodes. Depth-First Traversal is a tree or graph traversal algorithm that explores the branches of the tree as deeply as possible. Full Client A node that stores a complete copy of the blockchain and participates in the consensus process. Light Client A node that only stores a partial copy of the blockchain and relies on full nodes to verify information. Short Answer Question

What role does MPT play in the blockchain? MPT is used to organize and store the global state of the blockchain, including information about all accounts and smart contracts. It allows efficient verification of data integrity and retrieval of the state of a specific account.

What is the difference between a full node and a light node? A full node stores a complete copy of the blockchain and participates in the consensus process, while a light node only stores a portion of the blockchain and relies on full nodes to verify information.

Why create a subtree of the world state MPT for light nodes? Because light nodes have limited resources, they do not need to store the entire world state MPT. Creating a subtree reduces the storage and computational burden of light nodes while still allowing them to access the partial state relevant to them.

What is a transition node and what role does it play in subtree updates? A transition node is the nearest ancestor node shared by two account nodes in the MPT. During the subtree update process, transition nodes can be used to avoid repeatedly traversing the path from the root node to each node on the shared path, thereby improving efficiency.

What role does the Update Tree play in the subtree update? The Update Tree contains all the updated nodes in the world state MPT since the last update. By sending only the Update Tree, the amount of data that needs to be transmitted to the light node can be significantly reduced.

When comparing nodes in the subtree and the world state MPT, how to handle different types of nodes? If the two nodes are of the same type and have equal values, no update is required; if the values ​​are different or the types are different, the node in the world state MPT needs to be added to the Update Tree.

How to handle newly added nodes in the world state MPT? New nodes are added to the Update Tree and marked as "not originally present in the subtree" so that the light node can insert it into the local subtree.

During the subtree update process, how to handle intermediate nodes? If there are intermediate nodes in the search path, they are added to the Update Tree and marked as "not originally present in the subtree" so that the light node can insert it into the local subtree.

How does a light node use the update tree to update its local subtree? The light node traverses the update tree and performs a replacement or insertion operation based on the node's tag to update its local subtree.

What is the advantage of this scheme over sending the complete subtree directly? This scheme can significantly reduce the amount of data that needs to be transmitted to the light node, thereby saving bandwidth and computing resources.