The fuel_merkle::binary::verify almost ignores the num_leaves

[xgreenx]

The test below returns Ok while it should fail.

The test is added here.

[xgreenx]

Maybe we need to add this check as well

[bvrooman]

Maybe we need to add this check as well

I implemented the same check in fuel-merkle and incorporated it in the verify function. However, the tests still failed in this way.

After a while trying to identify any differences in code, I decided I would apply the same test case against the fuel-merkle-sol implementation. It turns out that the fuel-merkle-sol implementation also suffers from this issue, and the test cases fail: FuelLabs/fuel-merkle-sol#31

[bvrooman]

I think this may not be a "solvable" problem.

From the perspective of the verify function, there may actually be no difference in the "shape" of two different proofs. For example, a tree with 3 leaves will generate the same "shape" of proof as a tree with 4 leaves. In both cases, the tree has a height of 2, and therefore 2 items in the proof set. They will only differ by hashes. Unfortunately, there is no way (that I can think of?) to determine from the hashes alone what the shape of the original tree was.

This means that a tree with num_leaves in the range (2^n, 2^(n+1)] can produce proofs with the same number of items in the proof set for the same proof index, and it's not possible to determine from the proof set alone if the number of leaves is accurate. During verification, the number of leaves is used only as a hint to help the algorithm know how to combine items in the proof set when reconstructing the root.

For example, if you had four different trees:

• Tree with 5 leaves,
• Tree with 6 leaves
• Tree with 7 leaves
• Tree with 8 leaves

they all have a height of 3. For proof index 0, they would all produce a proof set with the 3 entries. There's nothing in the proofs themselves that tell us the exact number of leaves in the original tree.

The proof index implies the minimum size of the tree, but we still don't know the maximum.