[Feature]: Add Differential Tests for Functions in _merkle.rs_

[0xNeshi]

What is the feature you would like to see?

Towards #520

See how Solidity's Foundry defines differential testing.

Differential tests would compare the results of our merkle verification implementation against some third-party implementation. This would help pinpoint any latent issues, bugs etc.

One possible candidate for this is rs-merkle, but we can search for other implementations if they're more robust/well-known

Contribution Guidelines

• I agree to follow this project's Contribution Guidelines

[Haxry]

Hi @0xNeshi, I’d love to work on this issue. I’ve previously implemented Merkle Trees in Rust and shared my work in this repository. Please assign this issue to me. Thank you!

[bidzyyys]

Hi @Haxry! Thanks for your interest in contributing to our library! Please let us know if you have any questions.
Before delivering the tests, please provide us overview how you are going to solve this issue.

CC: @0xNeshi

[Haxry]

Differential Testing Implementation Plan for Merkle Verification

Proposed Approach 🔍

1. Generate Test Cases:
   Create diverse test cases to ensure thorough coverage of different scenarios.

2. Run Through Stylus Implementation:
   Execute the generated test cases using our Stylus-based Merkle proof implementation.

3. Run Through rs-merkle:
   Execute the same test cases using the rs-merkle library as a reference implementation.

4. Compare Results:
   Analyze the outputs from both implementations to identify any discrepancies.

5. Evaluate Outcome:

   • If the results match, the test passes.
   • If the results do not match, flag the discrepancy for further investigation.

---

I hope the approach is correct. Please suggest any changes or improvements to my approach.

---

One question I have is: Should I do differential fuzzing or are differential unit tests sufficient?

Thank you!

[0xNeshi]

Hi @Haxry , this seems like the right approach. Once you create the first differential test case, please create a draft PR so we can ensure we have the same understanding of the approach.

Regarding your question, differential fuzz tests would be awesome to include! Note that diff. unit tests have higher priority.