feat: Add Merkle Proof Verifier

[boray]

trafficstars

Fixes #936

I implemented MerkleProof.sol in Cairo.

This is a draft and needs improvement. It uses only Poseidon for now. That should be abstracted to work with Pedersen and Keccak. Testing coverage is narrow and should be extended.

I am waiting for your comments.

PR Checklist

• [ ] Tests
• [ ] Documentation
• [ ] Added entry to CHANGELOG.md
• [ ] Tried the feature on a public network

[ericnordelo]

Hey @boray thanks for taking the time! This would be a nice addition and we are happy to merge it after is finished and reviewed. We will be happy to review the PR after tests and logic are finished.

[ametel01]

Could we have this merged ASAP? I need it in a repo i'm working on and i'd rather skip implementing it from scratch

[ericnordelo]

Hey @ametel01, this PR is from an external contributor, and we will be happy to review it and merge it as soon as it is ready, It is also part of our roadmap for the next milestone, so we plan on working on that in the next three weeks. Note that Cairo 2.7 introduces some important changes, so we can't really release until we have the full cairo version out.

[ametel01]

@ericnordelo understandable

[augustbleeds]

@ericnordelo also waiting to use a MerkleProof Verifier library for some work we're doing at Chainlink. I see that the the rc's for Cairo 2.7 are out already. Do you have an idea of when this work could be completed?

[ericnordelo]

We will start working on it right after finishing this release. The reason is mainly these changes that conflict and must be included first.

[ericnordelo]

Thanks again @boray for kickstarting the implementation. Since we have the issue as part of the current milestone, and it's been some time since this PR last update, we will take it further. Closing in favor of #1101