What does the prefix '3☐' mean in the leaf nodes?
Add a comment
|
2 Answers
Appendix D of the Yellow Paper, in defining the node types, states (italics mine):
Leaf: A two-item structure whose first item corresponds to the nibbles in the key not already accounted for by the accumulation of keys and branches traversed from the root. The hex-prefix encoding method is used and the second parameter to the function is required to be true.
Appendix C defines Hex Prefix Encoding HP:
...The low nibble of the first byte is zero in the case of an even number of nibbles and the first nibble in the case of an odd number. All remaining nibbles (now an even number) fit properly into the remaining bytes
When applied to the Merkle Tree, if the key length is an odd number of nibbles, the first nibble of the key is stored in the second nibble of the prefix, else the second nibble of the prefix is set to 0. If you look closely at the drawing you'll see tiny little arrows intended to depict this. Either way (even or odd key length) the total number of nibbles is always even, which means the size of the merkle tree will always be a whole number of bytes.
Another way of putting this might be:
Given a key k with some number of nibbles, the prefix byte will be:
prefix byte key byte(s)
[nibble0, nibble1]---> Node type [stored nibbles]
[0, 0] ----------> Extension Node, n (=length(k)) is even [k[0]...k[n-1]]
[1, k[0]] ----------> Extension Node, n (=length(k)) is odd [k[1]...k[n-1]]
[2, 0] ----------> Leaf Node, n (=length(k)) is even [k[0]...k[n-1]]
[3, k[0]] ----------> Leaf Node, n (=length(k)) is odd [k[1]...k[n-1]]
-
Can you please show how the total number of nibbles is even in this example?– spharishCommented Mar 10, 2017 at 13:15
-
When I had worked out, 3☐ <-- 7, 3 is the first nibble , box(7) is the second nibble and 7 is the third nibble. I don't know which nibbles(prefix or key) to take into consideration, when you say the total number of nibbles is even?– spharishCommented Mar 10, 2017 at 13:27
-
1In that case there is no third nibble, as it is stored in the second byte of the prefix. Total no. nibbles is
length(prefix+keys)...– LeeCommented Mar 10, 2017 at 13:33
If the OP reads this.....I think it would be good to make it clear the ☐ refers to the first nibble of the original key. Also, to avoid confusion, I think it would also be a good idea to express both nibbles of the "even' prefixes...In other words, show the prefix 2 as 20 and the prefix 0 as 00 in the diagram to avoid confusion. Just my $0.02.
Finally, I'm not sure the original keys having an odd number of nibbles (e.g. 0xa711355) will ever happen. The use case for Merkle Patricia trees is to store dictionaries (associative lists). Clearly all keys will be expressed in bytes and cannot have an odd number of nibbles. Admittedly, in theory, keys can be any number of bits. But in the real world, you rarely see keys that are not some integer number of bytes. That would be well...odd.
Please correct me if I'm wrong. I'm just tryin' to learn like everyone else. ;)
