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.