Access Merkle Proof in LazyIMT

[alrevuelta]

Question rather than feature, but it might lead to a feature if feasible.

I'm using the LazyIMT and was wondering if it would be possible to get a Merkle Proof directly from the contract. The main benefit I see, is that any app would be able to get said proof to prove things, without having to locally fetch the whole tree and construct it locally. I'm using the LazyIMT because it seems to offer the closest I'm looking for, but open for other trees.

With a reduced example, given the following tree with 8 leafs, I would like to get a Merkle Proof for a given leaf, provided by the contract. Example:

• Proof that C belongs to the tree: [D, HASH_AB, HASH_EFGH]
• Proof that A belongs to the tree: [B, HASH_CD, HASH_EFGH]

          ROOT (Hash_ABCDEFGH)
          /                  \
         /                    \
 HASH_ABCD                   HASH_EFGH
  /      \                   /       \
 /        \                 /         \
HASH_AB   HASH_CD      HASH_EF    HASH_GH
 /   \     /   \       /   \      /   \
A     B   C     D     E     F    G     H

The LazyIMT seems to store in elements the whole tree, both leafs at the bottom and intermediate levels. In theory, I could get the Merkle Proof of C, by accessing elements at different levels:

• D: _indexForElement(0, 3)
• HASH_AB: _indexForElement(1, 0)
• HASH_EFGH: _indexForElement(2, 1)

The problem is that when the leaf is a left element, it's not hashed. So when the amount of leaves is odd, then upper hashes don't match, since they are not initialized yet. In other words, in the above example, one would expect element at _indexForElement(3, 0) to be the root, but this holds true only when the amount of leafs is even. Based on this, seems like I can't naively make elements public and use it for my purpose.

Some questions:

• Why not hashing when having only a left element?
• How gas efficient is a LazyIMT when compared to others? As far as I understand elements stores both leaves and intermediate ones, hashed up to the root. This means that in my example (8 leafs) a total of 15 elements are stored (8,4,2,1) and updated. Can an insert trigger up to MAX_DEPTH hashes?

tldr: In order to not fall into the x->y, this is the problem I'm trying to solve. I would like to get the Merkle Proof of a given leaf, ideally with a view function and without worsening the gas consumption. Is this feasible? Which tree would you recommend me to use? Any idea on how to implement this?

Thanks.

[chancehudson]

Yes, this is possible to do. I'll answer your numbered questions first.

1. The "lazy" tree performs the minimum number of hashes necessary to insert elements in a tree. This means if there is only a left element the parent hash is not calculated until a corresponding right element exists, to avoid having an intermediate hash that will change in the future. This tree is designed for roots that are infrequently accessed onchain. The specific case we had was a tree that was progressively built over a period of time with the root only accessed once at the end.
2. The lazy approach is ~25% cheaper over the lifetime of the tree. The approach is much more efficient for mostly empty/small trees and equally efficient for tree that are nearly full (assuming the tree root is infrequently accessed). If the root needs to be accessed often this approach is less efficient. The cost of calculating the root is (in the worst case) the same as the cost of inserting into a normal tree. You can see the original conversation with some rough benchmarks here. There's a decent description of the tree here.

To answer the original question, yes this is possible. As you noticed some hashes don't exist in the tree, but the hash of the elements necessary to build the proof should always exist. To build a merkle proof the contract will need to iterate up the tree and at each level check if the intermediate root exists. If the root does not exist the intermediate root should be calculated and used when building higher level roots. This implementation doesn't include such a function because we didn't need it at the time. Building something like this shouldn't be too hard, it will be similar to the update and root functions. I'll look into it later today and see if i can write something simple.

[alrevuelta]

Thanks for your answer @vimwitch.

The specific case we had was a tree that was progressively built over a period of time with the root only accessed once at the end.

Interesting. Our use case expects constant modifications of the tree, and it can be accessed at any time. We don't expect the tree to stabilize ever.

To build a merkle proof the contract will need to iterate up the tree and at each level check if the intermediate root exists. If the root does not exist the intermediate root should be calculated and used when building higher level roots

I see, makes sense. Now that I think about it, what is the reason for storing intermediate leaves? Isn't it possible to hash all leafs up to the root in a view function every time someone wants to access it? Using my above example, why not store just A, B, C, D, E,F,G, H (bottom leafs) and when someone wants to access the root, hash everything in a view function (7 hashes in this case). A view function for the merkle proof should be similar to implement. In other words, calculate everything "on demand". afaik that's "free" in a view function unless I'm missing something.

Edit: Perhaps related, and may answer my question. Calculating the root "on the fly" of a tree with depth 20 as I suggest may hit the limits on any RPC provider? Eg Infura. So I guess the intermediate leaves fix this problem?

To prevent API abuse, the gas parameter in eth_estimateGas and this eth_call method is capped at 10x (1000%) the current block gas limit.

[alrevuelta]

Working on #162 addressing this feature.

[cedoor]

Working on #162 addressing this feature.

Thanks @alrevuelta 👍🏽 Tracking this on the ZK-Kit board!