Merkle Patricial Tree

Merkel Patricia Tree (MPT) specification
 Merkel Patricia Tree, provides an encrypted, self-tamper-proofing data structure for storing key-value pairs. Here in after referred to as MPT. Although within the scope of this specification we restrict the type of a key value to a string (it is still valid for all types, since it is only necessary to provide a simple serialization and de-ordering mechanism that will store the type and string Conversion can be).MPT is  certainty refers to the same content key, will be guaranteed to find the same result, have the same root hash. In terms of efficiency, the time complexity of tree insertion, search and deletion is controlled at O ​​(log (n)). MPT is better understood and coded than red-black trees.

1. Foreword: Radix TreeIn a standard cardinality tree, the data to be stored is as follows:[i0, i1, ... iN, value]The i0 to iN representations are generally alphabetic in binary or hexadecimal format. value represents the final value stored in the tree node. Each i0 to iN slot value is either NULL or a pointer to another node (in the current scenario, the hash of other nodes is stored). So we have implemented a simple key-value storage. For example, if you want to find the value of the key dog ​​in this cardinality tree, First, you need to convert dog to something like ascii code (hexadecimal is 646f67). Then according to the alphabet order to form a layer-by-layer down tree. Along the path formed by the letters, at the bottom leaf node of the tree, find the dog corresponding value. Specifically, first find the root node that stores the key-value pair data, find the 6th node of the next level, and then go one level down to find the node 4, and then look down one level after another until the path is completed root -> 6 -> 4 -> 6 -> f -> 6 -> 7. So you will eventually find the value of the corresponding node.Base tree update and delete operations is relatively simple, you can press the following definition:def update (node, key, value):
    if key == '':
        curnode = db.get (node) if node else [NULL] * 17
        newnode = curnode.copy ()
        newnode [-1] = value
    else:
        curnode = db.get (node) if node else [NULL] * 17
        newnode = curnode.copy ()
        newindex = update (curnode [key [0]], key [1:], value)
        newnode [key [0]] = newindex
    db.put (hash (newnode), newnode)
    return hash (newnode)def delete (node, key):
    if key == '' or node is NULL:
        return NULL
    else:
        curnode = db.get (node)
        newnode = curnode.copy ()
        newindex = delete (curnode [key [0]], key [1:])
        newnode [key [0]] = newindex
        if len (filter (x -> x is not NULL, newnode)) == 0:
            return NULL
        else:
            db.put (hash (newnode), newnode)
            return hash (newnode)1.1 Data Verification Problem - Merkle TreeThe relationship between the radix tree nodes is generally concatenated using 32-bit or 64-bit memory address pointers, such as the C language. However, in order to achieve data tamper proof and validation in Ethereum, we introduced the Merkle Tree and used the hash values ​​of the nodes to establish the node relationship. Thus, if the root hash of a given prefix is ​​known, then anyone can check against this prefix. It is impossible for an attacker to prove that a key-value pair does not exist because the root hash ultimately depends on all underlying hash values, so any modification will result in a change in the root hash.1.2 Efficiency Problems - Patricia TreeAnother major drawback of the cardinality tree is inefficiency. Even if you only want to save a key-value pair, but the key length is several hundred characters in length, then you need a lot of extra space at each level of the character. Each search and delete will have hundreds of steps. Here we introduce the Patricia tree to solve this problem.2 core specifications2.1 key data encoding algorithmBefore introducing the full specification, let's introduce a compression algorithm for key encoding algorithms, hexadecimal sequences with optional end tags. The traditional way to encode hexadecimal strings is to convert them to decimal. For example, 0f1248 means three bytes [15,18,72]. However, this method is a bit small problem, if the hexadecimal character length is odd. In this case, there is no way to know how to convert hexadecimal character pairs to decimal. Additionally, MPT requires an extra feature, a hexadecimal string, that can have a special closing tag (usually T) on the ending node. The end tag appears only at the end, and appears only once. Or, there is not an end tag, but there is a marker bit, marking the current node is a final node, holding the value we want to find. If you do not include the end tag, it means that you need to point to the next node to continue searching.In order to solve these problems mentioned above. We force the first nibble (half a byte, 4 bits, also known as nibble), to encode the two flag bits using the final byte stream. Whether the tag is the parity of the end tag and the current byte stream (not counting the end tag) is stored in the lower two bits of the first nibble, respectively. If the data is even-numbered, we introduce a zero-valued nibble to ensure that it is eventually even-numbered, so that bytes can be used to represent the entire stream of bytes. Coding method can refer to:def compact_encode (hexarray):
    term = 1 if hexarray [-1] == 16 else 0
    if term: hexarray = hexarray [: - 1]
    oddlen = len (hexarray)% 2
    flags = 2 * term + oddlen
    if oddlen:
        hexarray = [flags] + hexarray
    else:
        hexarray = [flags] + [0] + hexarray
    // hexarray now has an even length whose first nibble is the flags.
    o = ''
    for i in range (0, len (hexarray), 2):
        o + = chr (16 * hexarray [i] + hexarray [i + 1])
    return oThe above code can be seen, if you want to represent the T end of the string, term value of 1, or 0. If odd length, take the value of 1, otherwise take the value of 0. Since the term tag is the higher of the two tags, multiply term by one to the left by one. If the byte stream that does not count after the closing tag is odd, it will not be filled. If it is an even digit, make up a nibble with a value of zero.Some examples of actual conversion:> [1, 2, 3, 4, 5]'\ x11 \ x23 \ x45' (Here in python, '\ x11 # E' because of its displaying unicodes.)// Do not include the end, so there is no end tag, because the byte stream is odd, the flag bit value 1, not make-up, so just make up a nibble just fine.> [0, 1, 2, 3, 4, 5]'\ x00 \ x01 \ x23 \ x45'// Do not include an even number of the end tag, and because it is an even number The first nibble is 0, because it is an even number, you need to make a nibble value is zero, so it is 00. Followed by the value of the back.> [0, 15, 1, 12, 11, 8, T]'\ x20 \ x0f \ x1c \ xb8'// Because of the closing tag, the first nibblie is 2, except for the length of the closing tag, which is incremented by an even number to make up for a nibble of 0, so add 20 to the end.> [15, 1, 12, 11, 8, T]'\ x3f \ x1c \ xb8'// Since there is an end tag and is an odd number, the first value is 3, and since it is an odd number that does not require padding, the value is 3 plus the following value.2.2 Merkle Patricia TreeThe MPT has made some improvements to the current data structure when it comes to addressing inefficiencies. The node type of MPT is defined as follows.

    NULL (empty string)
    An array of two elements [k, v] (aka key-value pairs)
    An array of 17 elements. [v0 ... v15, vt]. (Also known as branch node)The idea is to reduce this hierarchical relationship to a key-value pair node [k, v] when there are nodes of one element but a long path. Where the key is the path element of the hierarchical tree, using the hexadecimal string for the above encoding, the value is the hash of the node, just like a standard radix tree. In addition, we have added a concept of optimization, on the internal nodes can not store value, only those who have no children can store value. But for this key-value storage scheme to become more generic, both dog and doge can be stored. We added an end marker 16 to the alphabet, so there would be no situation where one value was incorrectly pointed to another.For a key-value node, an array of two elements [k, v]. v can only be a value or node.

    When v is a value, k must be a compact string of nibbles containing an end marker as described above.
    When v is to point to another node, k must be a nibble without end tags as described above for compactly encoded strings.For a branch node, an array of 17 elements [v0 ... v15, vt]. Each element in v0 through v15 is either a node, either empty, and vt is always a value, or empty. So if we just stored the value in one of v0 through v15, we should use a key-value pair node, where k is an empty nibble list encoding result that contains an ending token.Here's the code to get a node in MPT:def get_helper (node, key):
    if key == []: return node
    if node = '': return ''
    curnode = rlp.decode (node ​​if len (node) <32 br="" db.get="" else="" node="">    if len (curnode) == 2:
        (k2, v2) = curnode
        k2 = compact_decode (k2)
        if k2 == key [: len (k2)]:
            return get (v2, key [len (k2):])
        else:
            return
    elif len (curnode) == 17:
        return get_helper (curnode [key [0]], key [1:])def get (node, key):
    key2 = []
    for i in range (len (key)):
        key2.push (int (ord (key) / 16))
        key2.push (ord (key)% 16)
    key2.push (16)
    return get_helper (node, key2)For example, suppose we have a tree with values ​​like 'dog', 'puppy', 'horse', 'stallion', 'do', 'verb', 'doge', 'coin' . First, we turn them into hexadecimal format:[6, 4, 6, 15, 16]: do => 'verb'// 64 6f[6, 4, 6, 15, 6, 7, 16]: dog =>

'puppy' //64 6f 67 [ 6, 4, 6, 15, 6, 7, 6, 5, 16 ] : doge => 'coin' //64 6f 67 65 [ 6, 8, 6, 15, 7, 2, 7, 3, 6, 5, 16 ] : horse => 'stallion' //68 6f 72 73 65

Create the tree, as shown below:ROOT: ['\ x16', A]A: [',' ',' ',' ', B', '', '', C, '', '', '', '' ']B: ['\ x00 \ x6f', D]D: [',', '', '', '', '', E, '', '', '', '', '' 'verb']E: ['\ x17', F]F: [',' ',' ',' ',' ',' ', G,' ',' ',' ',' ',' ' 'puppy']G: ['\ x35', 'coin']C: ['\ x20 \ x6f \ x72 \ x73 \ x65', 'stallion']The tree's construction logic is the root node, to construct a kv node pointing to the next node. The first key encoding, the current node is not the end of the node, the value of the key for the odd number of characters, so the leading value of 1, and because the odd not make up, the final deposit is 0x16. It points to a full node A The next level, to be encoded is the second nibble of d and h, 4 and 6. So in the fifth position of node A (from zero) and the seventh position, we can see that they are pointed to two nodes B and C respectively. For Node B later do, dog, doge. They are followed by an o character code 6f. So here, node B is encoded as a kv node pointing to D, and data is directed to node D. Which key storage 6f, because it is to point to another node kv node, does not contain the end tag, and is even, you need to fill 0, get 00, the final encoding result is 006f. Follow-up node and so on.When you reference another node in one node, it contains H (rlp.encode (x)). The hash algorithm is H (x) = sha3 (x) if len (x)> = 32 else x, where rlp.encode is the method that uses the RLP encoding function. Note that you need to save the key-value pair (sha3 (x), x) in a persistent look-up table only when updating a prefix that is longer than 32 bytes. When less than 32 bytes, you do not need to dump anything. Because f (x) is always equal to its own value x.