IncrementalBinaryMerkleTree.sol: Update can change uninitialized leaves in the tree

[twister-dev]

Although this is a description for IncrementalBinaryMerkleTree.sol, it probably applies to the Quin Tree contract as well.

Describe the bug

Long story short: It is possible to use the update function to change a zero leaf at an index that hasn't been inserted into the tree yet.

For example, suppose that 4 leaves are inserted into the tree. We can update leaf 7 by proving inclusion of the zero value at leaf 7, because technically the tree is never "empty", but it begins completely filled with zero values.

Updating an uninitialized index can cause the tree root to no longer represent the set of leaves accurately, because the lastSubtrees array will be incorrect at some point when updating the root.

To Reproduce
You can see a demonstration of this bug in a unit test I wrote on my fork of the package:

IncrementalBinaryTreeTest.ts#L188

Expected behavior
The contract should reject updates that reach an index greater than or equal to the number of leaves in the tree. I implemented this in the next commit of the same fork and branch:

contract: IncrementalBinaryTree.sol#L124
test: IncrementalBinaryTreeTest.ts#L188

Additional context
I believe I patched the bug in the IncrementalBinaryMerkleTree.sol contract, as shared above, and if it is a satisfiable solution then I can submit a pull request with that change.

However, I'm mainly opening this bug report because I haven't studied Quin Merkle Trees and don't know how to patch that contract (if the bug is even there, but I'm assuming it is).

[cedoor]

Hi @twister-dev , thank you very much for the comprehensive description of this bug. I think your solution is right, and if you can also submit a PR, that would be great!

The Quin Merkle tree is exactly like a Binary Merkle tree, but with 5 child nodes per node, so the bug should be the same there. But if you're not sure we can fix it.

[twister-dev]

No problem @cedoor. I submitted a pull request with the Binary Merkle tree fix. I'm looking into the Quin Tree next, honestly I'm still trying to figure out how to recover the index from the path indices, but once I figure that out I can submit a fix for that too. If I can't figure it out then I guess I'll follow up with a comment here so you can handle it.

[twister-dev]

I addressed the bug in the Quin Tree as well. I can open a pull request on that fix after the first one goes through.

bug fix: IncrementalQuinTree.sol#L119-L146

unit test: IncrementalQuinTreeTest.ts#L188-L228