Ethereum Merkle Patricia Trie (Extension node)

Question

I do not have time to look through the source code right now. My questions is: In Ethereum, when is the decision to replace part of a given path with an Extension-node made?

I suppose the sole idea of extension nodes is to limit the number of situations where leaf nodes would share the same sequence of nibbles.

Would you describe the algorithm in short? I have two ideas in mind

1) create the trie in an unpacked manner then try to replace some of the paths using a compression algorithm which would replace some of the paths with 'extensions'. This would effectively introduce a second pass to the overall procedure and increase memory usage.

2)I've gone with a different approach and I construct the trie using largest blocks and divide when required. In this approach, I guess, when adding a new node to the trie, I would need to runforth down each branch of the sub-trie just to check if it is worth it to put an extension node just below the current branch and remember the (1-branch-N-Leafs set) which needs to be added to it. Is this the case with Ethereum? Looking forward to your reply and in the meantime, I'll implement this scenario. I am not sure if this approach would produce the optimal result when compared to the offline-second-pass-with-compression method.

So the question holds - when does the Ethereum's Trie construction algorithm decides to combine two or more paths into one extension.

Answer 1

Whenever a new item is added to the trie the algorithm can decide whether to insert a branch, a leaf or an extension. Let's say you need to insert 3 key-value pairs:

"0x01": 1
"0x01234": 2
"0x01235": 3

After "0x01" is inserted the trie will look like this (hash0 is root):

<hash0> leaf ["0x01", 1]

After "0x01234" is inserted (hash1 is root):

<hash1> extension ["0x01", <hash2>]
<hash2> branch [NULL,NULL,<hash3>,..<13 NULLs>.., 1]
<hash3> leaf ["0x34", 2]

After "0x01235" is inserted (hash4 is root):

<hash4> extension ["0x01", <hash5>]
<hash5> branch [NULL,NULL,<hash6>,..<13 NULLs>.., 1]
<hash6> extension ["0x3", <hash7>]
<hash7> branch [NULL,NULL,NULL,NULL,<hash8>,<hash9>..<10 NULLs>.., NULL]
<hash8> leaf ["", 2]
<hash9> leaf ["", 3]

Generally, while inserting a key-value pair:

• if you stopped at a NULL node, you add a new leaf node with the remaining path and replace NULL with the hash of the new leaf.
• if you stopped at a leaf node, you need to convert it to an extension node and add a new branch and 1 or 2 leafs.
• if you stopped at an extension node, you convert it to another extension with shorter path and create a new branch and 1 or 2 leafs. If the new path turns out to be empty you convert it to a branch instead.

When deleting a key-value pair:

• if there is a branch that has a single non NULL nibble and NULL value, this branch can be replaced with a leaf or an extension.
• if there is an extension that points to another extension or a leaf, it can be collapsed into a single extension/leaf.
• if there is branch with all NULL nibbles and non NULL value, it can be converted into a leaf.

I most likely missed a few cases but I hope the general idea is clear. When adding/deleting key-value pairs the algorithm can make the decision locally at the current node, there is no need to create an unpacked version of the trie first and then pack it.

Answer 2

Not sure if every implementation has their own way of doing it, but the way it's done in the geth client implementation resembles your approach in 2). Basically, an extension node is created any time a given path in the trie would contain one or more successive branch nodes with only a single child node. The extension node replaces these branch node(s) (conceptually, not in practice). This can be easily detected before creating the branch nodes by looking at the key of the to-be-inserted leaf node. To clarify:

Suppose you have a trie consisting of 4 nodes, A, B, C and D:

        A
        |
        B      
       / \
      2   6
     /     \
    C       D

Letters are nodes, numbers are indices of branch nodes

A is an extension node, B is a branch node and C,D are value nodes.

I will show keys in decimal format to make reading easier. It is also important to distinguish between two different keys. One is the accumulated key of a value node which is the entire key that defines the path to it. In an Ethereum transaction for example, it would be the transaction index. Keys are chopped up into nibbles. And then there's the (let's call it) node key, which is the key contained inside a value node or extension node. This key will be a subsection of the corresponding accumulated key. Also, since the keys are chopped up into nibbles, each branch node can have 16 (2^4) children.

Say that C's accumulated key is [1,5,4,2,7,9] and D's accumulated key is [1,5,4,6,7,14].

That would mean that A's node key is [1,5,4], C's node key is [7,9] and D's node key is [7,14].

Let's add a value node E with accumulated key [1,5,12,11,7,7].

I won't outline the full recursive algorithm with all possibilities (Find it here), but in our case the following happens, starting at the root node:

1. The first two nibbles of A's node key and E's accumulated key are the same, so create an extension node F with node key [1,5].
2. Create a branch node G with child nodes at indices 4 (next nibble of A's key) and 12 (next nibble of E's key).
3. Since the initial extension node A doesn't have any remaining nibbles, reference B directly in G.
4. Since we know that we had to create a new branch for node E, we know that no other nodes will follow afterwards so just reference the value node itself at index 12 of G.

The new trie is:

        F
        |
        G      
       / \
      4   12
     /     \
    B       E
   / \
  2   6
 /     \
C       D

F is an extension node, B,G are branch nodes, C,D,E are value nodes. Their node keys are:

F:[1,5] C:[7,9] D:[7,14] E:[11,7,7]

I know this doesn't cover all cases but I hope this helps, for further info about the Ethereum trie see:

Source1, Source2, Source3