Merkle Patricia Tree

nadifsd (40)in #cryptocurrency • 7 years ago

Rong Jialei (Ethernet Square lovers & contributors, Hyperchain core developers)

Chapter 1 Introduction

1.1 Overview

Merkle Patricia Tree (also known as Merkle Patricia Trie) is a through improved, trees and blend Merkel prefix tree The data structure of the two tree structures is the important data structure used in the etherbox to organize the management account data and generate the transaction set hash.

The MPT tree has the following functions:

(1) storing key-value key-value data of any length;
(2) providing a mechanism for quickly calculating the hash of the maintenance data set;
(3) providing a fast state the rolling mechanism;
(4) providing a method called proof Merkel proof, lightweight expanded node, simple payment verification;

because MPT combination of (1) a prefix tree (2) two kinds of tree Merkel Tree structure of the characteristics and advantages, so before the introduction of MPT, we first briefly introduced the characteristics of these two tree structure.

1.2 prefix tree

prefix tree (also known as the dictionary tree), used to save the associated array, the key (key) content is usually a string. The position of the prefix tree node in the tree is determined by the contents of its key, that is, the key value of the prefix tree is encoded in the root node to the path of the node.

As shown in the following figure, there are six leaf nodes in the figure, the key values are (1) to (2) tea (3) ted (4) ten (5) A (6) inn.

Advantages:

Compared to the hash table, the use of prefix tree to query the common prefix key data is very efficient, for example, in the dictionary to find the prefix prefix for the word, for the hash table, the need to traverse the entire table, time efficiency For the prefix (tree), but for the prefix tree, only need to find the prefix in the tree pre-node, and traverse the node as the root node of the subtree.

But for the worst case (prefix is empty string), the time efficiency is O (n), still need to traverse the whole tree, this time the same efficiency and hash table.

Compared to the hash table, the use of prefix tree for data organization does not exist hash conflict problem.

Disadvantages:

(1) direct search efficiency low

Prefix tree search efficiency is O (m), m is the length of the key to find the node, and hash table search efficiency is O (1). And a search will have m times IO overhead, compared to direct search, whether it is the rate, or the pressure on the disk, performance is not ideal.

(2) may cause space to waste

When there is a node, the key value is very long (such as a string of very long string), when the tree does not have the same prefix with its branch, in order to store the node, need to create many Non-leaf nodes to build the root node to the path between the nodes, resulting in a waste of storage space.

1.3 Merkel Tree The

Merkle tree was written by computer scientist Ralph Merkle many years ago and named after his own name. Since the data structure was used in the Bitcoin network to verify the correctness of the data, Here briefly introduce the merkle tree characteristics and principles.

In the Bitcoin network, the merkle tree is used to summarize all transactions in a block and to generate a digital fingerprint of the entire transaction set. In addition, due to the presence of the merkle tree, it is possible to implement a simple payment verification by extending a "light node" in the case of the public chain of the bitcoin. The contents of the light node will be described in detail below.

Features

(1) Merkel tree is a tree, most of the binary tree, you can also multi-tree, whether it is a few trees, it has all the characteristics of the tree structure;
(2) Merkel leaves the node value is
(3) The value of the non-leaf node is based on the information of the child's node and then calculated according to the Hash algorithm.
Principle

In the bit-coin network, the merkle tree is the value of the data item, and the value of the data item is the hash value of the data item. Bottom up to build. In the example below, the four cell data of L1-L4 are firstized and then the hash value is stored to the corresponding leaf node. These nodes are Hash0-0, Hash0-1, Hash1-0, Hash1-1

The hash of the two adjacent nodes into a string, and then calculate the hash of the string, the two nodes are the father of the hash value.

If the number of tree nodes in the layer is singular, then for the last remaining tree node, the situation is preceded by a hash operation, and the hash of its parent node is the hash of its hash value (for singular Leaf nodes, with different methods of handling, can also be used to copy the last leaf node to join the even number of leaf nodes). Loop the above calculation process, and finally calculate the last node of the hash value, the node's hash value as the whole tree hash.

If the two trees of the root hash consistent, then the structure of the two trees, the contents of the node must be the same.

As shown in the above figure, a tree with four leaf nodes, calculated on behalf of the entire tree of the hash need to go through 7 times the calculation, if the use of the four leaf nodes spliced into a string to calculate, just only once Greek can be achieved, then why use this seemingly strange way?

Advantages:

(1) fast re-hash

One of the features Merkel tree when the tree node is changed contents, can be based on previous hash calculation, only the modified node tree recomputed hash, Will be able to get a new root hash used to represent the state of the whole tree.

(2) light node expansion

using Merkel tree, you can expand in the public chain environment, a "light node." The light node is characterized by the need to store only about 80 bytes of block header data for each block, without storing the transaction list, receipt list, and so on. However, through the light node, you can achieve in the untrusted public chain environment to verify whether a transaction is included in the function of the block chain books. This makes it possible to run blocks such as Bitcoin, Ethernet, and other terminals with small storage capacity for personal PCs, smartphones, and so on.

Disadvantages:

large storage space overhead.

Chapter 2 Terminology

In the following, there will be specific technical terms, where the definitions of these terms are first

State of the world:

In the etherbox, the status data for all accounts (including contract accounts, regular accounts) are collectively referred to as world states.

Light node:

refers to only block data stored in the block node node.

Block chain bifurcation:

two blocks that point to the same parent block are generated at the same time. Some miners see one of the blocks and the other miners see another block. This leads to the simultaneous growth of the two block chains.

Block header:

refers to a part of the block structure, used to store the block of the head information, such as the parent block hash, the world state hash, transaction receipt collection hash and so on. The block header stores only some "fixed" length hash fields.

Chapter 3 Structure Design

3.1 Node Classification

As mentioned above, although the prefix tree can serve the purpose of maintaining key-value data, it has a very obvious limitation. Whether it is query operation, or increase or decrease the data, not only inefficient, and the storage space is serious. Therefore, in the ether square, for the MPT tree added several different types of tree nodes, in order to try to compress the overall tree height, reduce the complexity of the operation.

In the MPT tree, the tree nodes can be divided into the following four categories:

(1) empty nodes

(2) branch nodes

(3) leaf nodes

(4) expansion nodes

whose hollow nodes are used to represent empty strings.

The branch node

branch node is used to represent all non-leaf nodes in the MPT tree that have more than one child node. The definition is as follows:

type fullNode struct {

Children [17] node // Actual trie node data to encode / decode (needs custom encoder

flags nodeFlag

}

// nodeFlag contains caching-related metadata about a node.

type nodeFlag struct {

hash hashNode // cached hash of the node (may be nil)

gen uint16 // cache generation counter

dirty bool // if the node has changes that must be written to the database

}

Like the prefix tree, the MPT also encodes the key of the key-value data item in the path of the tree, but the range of each byte of the key is too large ([0-127]), So in the ether square, before the tree operation, the first will be a key encoding conversion (the next section will be detailed), a byte of four high and low content split into two bytes of storage. By encoding transitions, the value range for each bit of key 'is within [0, 15]. Thus, a branch node has at most 16 children. In this way, the etherbox reduces the capacity of each branch node, but increases the height of the tree to a certain extent.

The last element in the child list of the branch node is used to store its own content.

In addition, each branch node will have an attached field nodeFlag, which records some auxiliary data:

(1) node hash: If the field is not empty, then when the node needs to hash calculation, you can skip the calculation process directly using the result (when the node is dirty, this field is blank) calculated last time;

(2) the dirty flag: when a node is modified, the flag is set to 1;

(3) birth mark: When the node is first loaded into memory (or modified), will be given a count value as a birth mark, the logo will be used as a basis for the removal of the node, remove the memory "too old The

leaf node & extension node

leaf node is similar to the definition of the extended node, as follows:

type shortNode struct {

key [] byte

Val node

flags nodeFlag

}

where the key field is:

(. 1) key: for storing node belonging to the key range;
(2) Val: used to store the contents of the node;
wherein key is a key tree MPT achieve high compression tree!

As mentioned earlier, there will be a serious waste of storage space in the prefix tree, as shown below:

There is a long string of nodes on the right side of the figure, most of which are only non-leaf nodes, used to build a path, only to store the leaves on the path of the node.

In this case, the MPT tree is optimized for this: When the MPT tries to insert a node, the insertion process finds that there is currently no path with the same prefix as the node Key. At this point the MPT stores the remaining keys in the Key field of the leaf / extension node and acts as a "Shortcut".

For example, we will call the red line node called node1, the blue line of the node called node2. node1 and node2 share the path prefix t, but node1 at the time of insertion, the tree does not have a common prefix with oast path, so node1 key oast, to achieve the coding path compression.

This approach has the following advantages:

(1) to improve the efficiency of the node to find, to avoid excessive disk access;

(2) to reduce storage space waste, to avoid the storage of useless nodes;

Val field used to store leaf / expansion node Content, for the leaf node, the field is stored in a data item content; and for the expansion node, the field can be the following two kinds of content:

(1) Val field is stored in the child node in the database storage

(2) The Val field stores a reference to its child's node;

since the leaf / extension node shares a set of definitions, how does the Val field store it in the end ? (2) The Val field stores the reference to the child's node; Is the content of a data item, or a string of hash index? In the etherbox, two types of nodes are distinguished by adding special flags to the Key.

Note

why the design of the Val field in the extended node is likely to store a string of hash values as child node indexes?

In the ether square, the hash represents another node in the database index, that is, based on the hash value as an index in the database, you can read from the database to another node's content.

The purpose of this design is:

(1) when the whole tree is persistent to the database, to maintain the relationship between nodes;

(2) read nodes from the database, try to avoid unnecessary IO overhead;

in memory , The association between the parent node and the child node can be implemented by reference, pointer, etc., but when the tree node is persisted to the database, the parent node stores the index value of a child node in the database to keep the association relationship.

Similarly, from the database to read the node, the principle of the minimum IO overhead, only need to read those nodes need to use the data, so if the current node has been included in the need to find information, it is not necessary to its The child node to read out; the other hand, according to the hash of the child node to recursively read the child node, until the required information to read.

3.2Key value encoding

In the ether square, MPT tree key value of a total of three different coding methods to meet the different needs of different scenes, here as a separate section to introduce.

Three encoding mode are:

(. 1) Raw encoding (native character);

(2) Hex coding (scalable coding hex);

(. 3) Hex-encoding the Prefix (hex prefix encoding);

Raw encoding

Raw Encoding is the original key value, do not make any changes. This key way of coding, MPT external interface to provide the default encoding.

For example, a key is "cat", the value of "dog" data item, the Raw code is ['c', 'a', 't'], replaced by ASCII representation is [63, 61, 74]

Hex encoding

In the introduction of the branch node, we introduced, in order to reduce the number of branches of children, the need to convert the key code, the original key of the four high and low split into two bytes for storage. This conversion of the key encoding, that is, Hex coding.

From Raw encoding to Hex encoding conversion rules are:

(1) Raw will be encoded for each character, according to the high 4 low 4 bits split into two bytes;
(2) If the corresponding node corresponding to the Key is stored
(3) If the node corresponding to the key stores the hash index of another node (ie, the node corresponding to the key) is stored in the last bit of the node. The node is the extension node), without any character;
key is "cat", value is "dog" data item, the Hex code is [3, 15, 3, 13, 4, 10, 16]

Hex encoding The MPT tree node key is encoded in memory.

HP coding

In the introduction of leaf / expansion node, we introduced the two node definitions are shared, even if the persistence to the database, the storage is the same way. Then when the node is loaded into memory, it is also necessary to distinguish the type of node by an additional mechanism. So the etherbox proposed an HP coding to distinguish the key of the leaf / extension node stored in the database. Before these two types of nodes are persisted to the database, the key of the node will be converted to the encoding, that is, from Hex encoding to HP encoding.

The coding rules for HP are as follows:

(1) remove the byte if the value of the last byte of the original key is 16 (that is, the node is a leaf node);
(2) add a nibble before the key, where the least significant bit is used Encoding the original key length of the parity information, key length is odd, then the bit is 1; low 2 bits in the encoding of a special termination tag, if the node is a leaf node, the bit is 1;
(3)
(4) the original key of the contents of the compression, that is, the two characters in the high 4 to 4 low combination, stored in a byte (in bytes ) , the length of the odd value, then add a value of 0x0 before the nibble; (Hex extended inverse);
if Hex is encoded as [3, 15, 3, 13, 4, 10, 16], the HP encoded value is [32, 63, 61, 74] The

HP encoding is used for the database In the tree node key to encode.

Conversion relationship

Conversion relation above three coding scheme is:

(. 1) Raw Code: native key coding is encoding MPT provide external interface used when the data item is inserted into the tree, Raw code is converted into Hex coding;

(2) Hex encoding: hexadecimal extension encoding, used to encode the tree node key in memory, when the tree node is persisted to the database, Hex encoding is converted to HP coding;

(3) HP encoding: hexadecimal Prefix encoding, used to encode the tree node key in the database, when the tree node is loaded into memory, the HP code is converted to Hex encoding;

3.3 security MPT

MPT tree described above can be used to store content for any length key-value data item. If the length of the data item key is not limited, when the amount of data maintained in the tree is large, will still cause the depth of the whole tree becomes more and more deep, will cause the following effects:

(1) query a node may need many read IO times and inefficient;

(2) Dos system vulnerable to attack, the attacker specific data stored in the contract through "structure" a tree has a very long path, and then continue to read the instructions call SLOAD the contents of the node tree, causing the system efficiency is extremely decreased;

(3) all of the key is actually a form of storing plaintext;

to solve this problem, in the square of the MPT ether then a package of data items (sha3 (key), value)

Advantage:

The key to the incoming MPT interface is a fixed length (32 bytes) that can be avoided, so that the key is passed to the MPT interface. It appears very long path length occurs tree;

disadvantages:

; (1) once per tree operation is necessary to increase the hash computation

(2) need to store additional SHA3 (key) in the database with the key Correspondence;

CHAPTER 4 BASIC OPERATION

4.1Get

The procedure for a Get operation is:

Converts the Raw encoding that needs to find the Key to Hex encoding, and the resulting content is called the search path.
From the root node, the search is consistent with the search path Path;

2.1 If the current node is a leaf node, the stored content is the content of the data item, and the contents of the search path are consistent with the key of the leaf node, then the node is found; otherwise, the node does not exist in the tree.

2.2 If the current node is an extension node and the stored content is a hash index, the hash is used to load the node from the database, and the search path is used as a parameter to recursively query the newly loaded node.

2.3 If the current node is an extension node, the stored content is a reference to another node, and the key of the current node is the prefix of the search path, the search path is subtracted from the key of the current node, and the remaining search path is used as a parameter. The child node recursively calls the lookup function; if the key of the current node is not the prefix of the search path, it indicates that the node does not exist in the tree.

If the current node is a branch node, if the search path is empty, then return to the branch node storage content; the other side of the search path using the first byte to select the child node node node, the remaining search path as a parameter recursively call to find function.

The figure above is a process of finding the key as a "cat" node.

(1) the key "cat" into hex encoding [3,15,3,13,4,10, T] (at the end of the addition of the terminator is due to the need to find a real data item content);

(2) the current node Is the root node, and is the extension node, the key is 3,15, then recursively its sub-node to find the call, the remaining search path is [3,13,4,10, T];

(3) the current node is

(4) the current node is the leaf node, and the key is the node of the first node of the search path. 3, the fourth child node is recursively searched, and the remaining search path is [13,4,10, T] And the remaining search path, that found the node, return Val as "dog";

4.2Insert

insert operation is based on the search process is completed, an insert process is:

According to the description described in 4.1 steps, first found with the new

If the node is a branch node:

2.1 the remaining search path is not empty, then the new node as a leaf node into the corresponding child list;

2.2 ( 2) the node is the node with the longest path prefix, The remaining search path is empty (exact match), then the new section Content stored in the first point 17 by children of branch node entries (the Value);

If the node is a leaf / node expansion:

3.1 rest of the search path coincides with the current node's key, to put the current node updates Val ;

3.2 The remaining search path is not exactly the same as the key of the current node. Then, the child node of the leaf / extension node is replaced with the branch node. The common prefix of the new node and the current node key is used as the key of the current node, and the new node and the current node The child node is inserted into the child list of the branch node as the two children, and the current node is converted into an extension node (if the new node does not have a common prefix with the current node, the current node is replaced directly with the generated branch node)

If the insertion is successful, the dirty flag of the modified node is set to true, the hash flag is empty (the previous result is no longer available), and the birth token of the node is updated to the present;

The figure is a key for the key "cau", value for the "dog1" node insert the process.

(1) the key "cau" into hex encoding [3,15,3,13,4,11, T];

(2) through the search algorithm to find the left blue circle out of the node node1, and have a new insert

(3) Add a branch node node2, insert the val of node1 with the new node as the child into the child list of node2, replace the val of node1 with the new prefix of the node [3,15,3,13,4] Into the node2;

(4) node1 into a expansion node;

4.3Delete

delete operation and insert operation is similar to the need to complete the search process, a delete process:

According to the description described in 4.1 to find and need to insert the node has the same node longest path prefix, referred to as node;
If the node is a leaf / extension node;

2.1 if the rest of the search path and node of Key exactly the same, it will delete the entire node;

. If the remaining 2.2 Search the path node key does not match, then the node to be deleted does not exist in the tree, the delete fails;

. 2.3 if the node key prefix of the remaining search path, then the node for deletion Val recursive call;

If Node is a branch node:

3.1. Delete the child list phase Node standard logo should under;

3.2 Delete the end, the number of children if Node of only one, it will replace the branch node into a leaf / node expansion;

If the deletion is successful, it will be modified dirty flag node Is true, the hash flag is blank (the previous result is no longer possible), and the birth mark of the node is updated to the present;

The above two pictures will be a key for the "cau", value for the "dog1" node to delete the process.

(1) the key "cau" into hex encoding [3,15,3,13,4,11, T];

(2) through the search algorithm to find the fork node node1, from the root node to node1 path exactly the same search path;

(3) remove the node from the parent node node1, a parent node remaining child node, the parent node to convert it into a leaf node;

(4) the newly generated leaf node and the parent node ( Expansion node) merged, and finally generated a leaf node contains all the information (Figure 2);

4.4Update

update operation is 4.2Insert and 4.3Delete combination. When the user calls the Update function, if the value is not empty, then implicitly to call Insert; if the value is empty, then implicitly call Delete, it will not repeat.

4.5Commit

Commit function provides the ability to persist the MPT data in memory into the database. In the first chapter we mentioned that the MPT has the ability to quickly calculate the ability to maintain the data set hash hash in a fast state, and is also implemented in the function.

After the commit is complete, all the dirty tree nodes will re-hash the calculation and write the new content to the database; the final new root hash will be returned as the latest state of the MPT.

An MPT tree commit is a recursive call. Before we introduce the MPT commit process, we first describe how a single node performs hash computation and storage.

Single node

First of all, the node to determine the dirty position, if the current node is not modified, then directly return to the node's hash value, the call ends (in addition, if the current node has not been modified, and exist in the memory Time and "too long", then the node as the root node of the subtree from the memory out);
The node is a dirty node, the hash of the node is recalculated. First, the current node of the child node hash calculation, the child node hash calculation is the use of recursively to deal with the node to complete. The purpose of this step is to convert the child 's node information into a hash value.

3, the current node hash calculation. The hash calculation uses the sha256 hash algorithm to hash the RLP encoding of the current node;

3.1. For the branch node, the RLP encoding of the node is to encode the contents of its child list, and in the second step, all Of the child nodes have been converted into a hash value;

3.2. For the leaf / extension node, the node's RLP encoding is its Key, Value field encoding. Also in the second step, if Value refers to a reference to another node, it has been converted to a hash value (in the second step, Key has been converted to HP coding);

will the current The node's data is stored in the database, and the format is stored as [node hash, node RLP encoding].
own dirty flag to false, and the resulting hash value calculation buffer;

filed MPT tree during

the submission process after understanding single node, the process is submitted to MPT tree root node as an entry for the root Node to submit the call can be.

The graph shows a process in which an MPT is persisted:

the leaf node in the lower left corner computes a hash of 0xaa, stores it in a database, and replaces it with a hash value in its parent node; the pink extension node calculates Hash is 0xcc, in the parent node with 0xcc to replace; recursion to the root node, calculate the root node hash to 0xee, that is, the entire tree hash to 0xee.

Node through the old basis to judge

determine whether a long time based on the presence of nodes in memory are:

(1) The node has not been modified;
(2) the current MPT counter minus the birth mark node exceeds a fixed upper limit;
( 3) When the MPT calls the Commit function once, the MPT counter is incremented.

Implementation function

(1) Fast calculation of the maintenance data set Hash identity

This feature is reflected in the first step of a single node calculation, that is, before the node hash calculation The status of the node will be judged, only when the contents of the node becomes dirty, will be the hash re-calculation, database persistence and other operations. As a result, in a certain transaction operation, the contents of some nodes of the entire MPT tree have been modified. Then, once the hash is recalculated, only these modified nodes, and from these nodes to the root node path Of the nodes to recalculate, will be able to regain the new tree of the new hash.

(2) rapid state rollback

in the public chain environment, the use of POW algorithm is likely to cause bifurcation caused by the block chain state to roll back. In the ether square, due to the block time is short, this bifurcation probability is very large, block chain state rollback phenomenon is very frequent.

(2) the world state of the block chain (account information) needs to be rolled back, that is, the previous operation to be revoked (2) the block state of the block chain (account information) need to be rolled back, that is, the previous operation to revoke The

The MPT tree provides a mechanism to complete the rollback of the world state at zero delay when bifurcated. The cost of this mechanism is the need to waste storage space to redundantly store the historical state of each node.

The storage of each node in the database is value-driven. When the content of a node changes, the hash changes accordingly, and the MPT will be the hash as a database index, also achieved for each value, in the database has a certain record. And MPT is based on the node hash to associate the parent and child nodes, so whenever the contents of a node changes, and ultimately for the parent node, the change is only a hash index; the contents of the parent node also changed, resulting in A new parent node recursively passes this effect to the root node. Eventually, a change creates a new path from the changed node to the root node, and the old node can still be accessed by the old root node through the old path.

Example:

In the above figure, the contents of a node from 27 to 45, corresponding to create a new path by the blue coil, through the green coil out of the unmodified node information, construct a new tree, and the old path Still keep. So through the old stateRoot, we can still query the node to the value of 27.

Therefore, in the ether square, the bifurcation of the world state rollback, only need to use the old MPT root node as an entry, you can complete the "state rollback."

Chapter 5 Light Node Expansion

5.1 Light Node

In an ether square or bit bank, a participant consensus node usually maintains data for the entire block chain, each containing block header information, all transactions, receipt information, and so on. Due to the non-tampering of the block chain, this will result in a significant increase in the volume of the entire block chain as time increases. The possibility of running on a personal PC or mobile terminal is minimal. In order to solve this problem, a lightweight, lightweight node that stores only the block header information is presented. This node only needs to maintain all the block header information in the chain (the size of a block header is usually tens of bytes, the ordinary mobile terminal equipment is fully able to bear).

In the environment of the public chain, only through the local maintenance of the block header information, the light node can prove whether a transaction exists in the block chain; whether an account exists with the block chain, the balance is how much Function, which is simple payment verification.

5.2 Merkel prove

Merkel prove refers to a light node initiates a full node to request a proof, ask Merkel complete the whole tree node, if there is a specified node; a full node returns to the light Merkel node Prove the path, calculated by the light node, verify the existence.

If the tree node is shown in the following figure, if a node wants to verify 9Dog: 64 whether the tree node exists with the Merkel tree, only need to send the request to the full node, the whole node will return a 1FXq: 18, ec20, 8f74 a path (Merkel path, as shown in Figure 2 yellow box). After getting the path, the light node uses 9Dog: 64 with 1FXq: 18 for the hash, with the ec20 seeking the hash, and finally with the 8f74 seeking the hash, the results obtained with the local maintenance of the root hash are equal.

5.3 Security

(1) If the whole node returns a malicious path? Attempting to forge a legitimate merkle path for a node that does not exist in the block chain, so that the final result is the same as the Merck root hash in the block header.

Since the calculation of the hash is unpredictable, a malicious "whole" node wants to forge a "pseudo-path" for a non-existent node so that the final calculated root hash is the same as the root hash maintained by the light node impossible.

(2) why not directly to the whole node to ask whether the node exists in the block chain?

Because in the public chain environment, can not determine whether the request of the whole node is a malicious node, so directly to one or more nodes request results can not be guaranteed. But the light node to maintain the local maintenance of the block information, is verified by the workload verification, that is, through the consensus must be correct, if the use of the full node to provide the Merkel path, and the node to be verified hash calculation, if the final results Consistent with the root hash in the locally maintained block header, it is possible to prove that the node must exist in the Merkel tree.

5.4 Simple Payment Verification

In a bitcover or ethernet network, a batch of transaction data is processed to construct a Merkel tree, which is logically believed that each leaf node of the Merkel tree stores a transactional message.

The client can initiate a query to a light node to inquire whether the transaction specifying the hash has been included in the block chain; the soft node initiates a Merck certificate to the neighboring node, and whether the transaction has been Included. This process is a simple payment verification process.

Chapter 6 Reference

https://github.com/ethereum/wiki/wiki/Patricia-Tree

http://gavwood.com/paper.pdf

https://www.wikipedia.org/wiki/Trie

https://en.wikipedia.org/wiki/Merkle_tree

https://github.com/ethereum/wiki/wiki/Design-Rationale

https://github.com/ethereum/wiki/wiki/Light-client-protocol

#hyperchain #blackchain #rong-jialei