Hash inlining about rust-merkle-trie

[sgkim126]

What I thought was optimizing the implementation without changing the spec, but it seems that your proposal should change the spec.
For instance, embedding leaf node on a branch without changing the address of the branch node. It will reduce the number of db operations, but the users cannot know whether it's optimized or not.

However, it's okay to change the spec if you keep two things.

1. Make a unique root for any state regardless of the insertion order.
2. Make the library provide the old implementation.
   The first condition is important because all nodes should share the same root.
   The next condition is important because it should support the states already included in the chain.

[sgkim126]

The hash of rlp encoding of the node becomes the address of the node.
What I meant was optimizing without changing how to calculate the address of the node.
Since it's an optimization, I want the same result whether it's applied or not.

[majecty]

I agree with you. We don't need to make code complex to gain small performance improvement.
@sgkim126 What do you think about?

[somniumism]

@gnup @sgkim126 @majecty As you said, if the node's data can be stored in the branch node, our Merkle trie will perform better than it currently does. However, we need to consider the remaining nibbles of the node.

Suppose that the node's data is less than 256 bits.
If the remaining nibble is only one(nibble length of leaf = nibble length of branch + 1), then no problem occurs when storing it. However, if not, the data can be stored in the branch node, but there is no place to store the remaining nibbles.

Therefore, I propose a condition under which the node's data can be stored in the branch node:
The size of remaining nibble + The size of the node's data < 256 bit(the size of hash).
With this condition, the summation of the remaining nibble and node's data is stored in the branch node.

Because we know the nibbles of the node, we can get the value(the data of the node) by subtracting the remaining nibble from the summation. Also, no flags are required to distinguish the hash from the value, because the stored data(the summation) is less than 256 bits.

The node and the hash are stored in the DB, but by reducing the function's recursion, the DB operation can be reduced.

What do you think of this method? If there is a better way, could you advise me?

[majecty]

It seems reasonable. I have one question. How can we distinguish the nibble and the data?

[somniumism]

@majecty I'm sorry I didn't explain well. Let the "data" is a data is stored in the branch node, and the "value" is a data of the node. As mentioned, the summation of remaining nibble and value is stored in the branch node. The summation is the "data".

If the path of the node is "ABCDE", then we can find the value of the node using it("ABCDE"). Suppose the nibbles of branch node is "AB". Thus, we know that "ED" is remaining nibbles of the node(because "C" is a location for array). Because the summation("data") is a sum of the "value" and remaining nibble "ED", we can get the "value" by subtracting the remaining nibble "ED" from the data(summation).

[somniumism]

For example, suppose the remaining nibble is "0x3a34" and the value of the node is "0x163", then a summation of these is "0x3b97". Thus, data "0x3b97" will be stored in the branch node.

Let the data is stored in the element, in which the nibble of the branch node is "0x153" and location of element is "6".

The node = [Nibble: 0x15363a34][Value: 0x163] (Remaining nibble: 0x3a34)

The data = Remaining nibble + Value = 0x3a34 + 0x163 = 0x3b97

Branch Node = [Nibble: 0x153][1st: ][2nd: ]...[6th: 0x3b97][ ] ... [ ][ ][ ][ ]

In vice versa, suppose that we want to get the value "0x11" of the node, and the node's nibble is "0x15363a34". We will search from the root to the branch node probably. If we find the branch node that has the nibble "0x153", we will get the data "0x3b97" in the 6th element. Because the remaining nibble is "0x3a34", we can get the value "0x163" by subtracting "remaining nibbles 0x3a34" from "the data 0x3b97".

[somniumism]

Thank you for your good advice. I think I'm thinking it much more complicated than it you said. But I still don't know what to do. I'll give it some thought. : )

[somniumism]

@sgkim126 Actually, I don't understand the meaning of 'changing the spec'. The main point of my proposal is to store both the remaining nibble and the value when it is stored in the branch node.

At first, I thought about the method to store the value in the branch node only when the remaining nibble is only one. However, the method works only when the height of the merkle tree is 64 because the meaning of 'the remaining nibble is only one' is 'it is the last nibble(64th) of the path'. I thought this method was not optimized, and I made up the proposal.

I want to know the exact meaning of 'changing the spec', and I wonder what the difference is between to store the value of the leaf node and the summation introduced to my proposal; I think the address of the branch node will be changed in any way.

Thank you sincerely, and I'm so sorry I didn't quite understand your point. :'(
In addition, I want to know @majecty your opinion too. : )

[majecty]

Aha, I didn't think the fact that a hash of the branch node will be changed.

1. Since we can use a new spec for Foundry, I agree on changing the spec. We can support two versions of Merkle-Patricia trie in this library.

2. We cannot use the plus method to merge the nibbles and data.
   In seungmin reply, he wrote The data = Remaining nibble + Value = 0x3a34 + 0x163 = 0x3b97. In this case we can get 0x163 value when we search for 0x3a34. Also, we can get 0x162 value when we search for 0x3a35. However the returned value when we searched for 0x3a35 should be None.

[somniumism]

@sgkim126 @majecty I'd like to finish this issue.

DB operations such as insert operation can be reduced by storing the value to the branch node. Since the branch node has up to 16 branches and each branch is a 256-bit hash, the data that can be stored in there is less than 256 bits. However, we need to consider the remaining nibbles of the node. If the remaining nibble is only one(nibble length of leaf = nibble length of branch + 1), then no problem occurs when storing it. If not, the data can be stored in the branch node, but there is no place to store the remaining nibbles.

As you know, I proposed the method to store both the remaining nibble and the value when it is stored in the branch node. It is the main point of my proposal. I want to add a condition and store the summation of the remaining nibble and the value of the leaf node to the branch node. Examples are shown above. The condition is the following:
The size of the remaining nibble + The size of the node's data < 256 bit(the size of hash)

As @sgkim126 said, he gave me good advice for changing the specs. In summary, there were two choices to optimize the Merkle tree. The first is to optimize without changing the spec. However, this is not possible because the address of the branch node must be changed if the value is stored in there.

The second, as @majecty said, is to make and use a new spec for Foundry. Thus, I tried to implement my proposal for making a new Merkle trie based on the new spec. The Insert operation should be reduced based on my proposal, but its implementation is very complex. First, it needs many calculation processes because the summation is stored in the branch node. Second, there are too many cases of inserting nodes. This implementation is complex because the value is stored in the branch node rather than a leaf node.

To sum up, I think it is right to close this issue. More specifically, it takes too much time, and it is not as efficient as the time we invested. It may seem like I'm giving up, but I want you to know I've tried enough. I don't know a better way to resolve this issue.

Please tell me your opinion. If you have a better idea, please advise me.

[sgkim126]

I still think it can be done with a little complex code, but I also think the improvement point of this would be overlapped with the caching's. Let's close this issue for now. I'll re-open when I find that it would help even with a cache.

[somniumism]

I proposed the method to store both the remaining nibble and the value when it is stored in the branch node. And I tried to implement my proposal for making a new Merkle trie based on the new spec. The Insert operation should be reduced based on my proposal, but its implementation is very complex. We think that we don't need to make code complex to gain small performance improvement, and this improvement would be overlapped with the cache. Therefore, we will re-open when I find a new way that would help even with a cache.