1

If I understood well, extension and leaf nodes should be used when there are shared nibbles, and branch nodes when there are differences.

Which type of node should be used when storing a different nibble and a shared one at the same point?

For instance, what would be the type of node used in the root for these data:

'ac4f' : 'data1', //shared nibbles 'ac'
'ac03' : 'data2', //shared nibbles 'ac'
'5e5f' : 'data3'  //different nibble '5'
2

Your trie would start off with a branch node in this case. I have created this trie, it should be self-explanatory

Merkle Patricia Trie for data1,data2,data3

  • One question related to it... What about if our data was ac4, ac3 and 5e5f? In this case we wouldn't have leaf nodes in the trie right side? Or we would still have them but with empty nibbles? – Ethersworn Canonist Sep 2 '18 at 12:29
  • @EtherswornCanonist exactly. The last nibble is implicitly contained within the leaf node through the reference from the preceding branch node. – sea212 Sep 2 '18 at 13:39
  • I really would appreciate the answer for that. – Ethersworn Canonist Sep 2 '18 at 15:17
  • @EtherswornCanonist I was not precise with my previous comment. You would have two leaf nodes at the right side of the trie like it is pictured in my answere, but there would not be any nibbles contained within those leaf nodes. The last nibbles, in your second example it's 4 and 3, are implicitly contained within the leaf node through the preceding branch node. – sea212 Sep 2 '18 at 19:50
  • A leaf node is a tuple [encodedPath, value]... so if I understood your answer we would have the following nodes for the 4 and 3 nibbles: [20, someValue], [20, someOtherValue]. Those 20 are the Hex-Prefix for leaf nodes with even length path, in these cases path length would be 0... is that correct? – Ethersworn Canonist Sep 3 '18 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.