feat: create a MerkleProofLib Cairo Module

[Eikix]

Feature Request

As part of the Cairo Module track, we want to create new Cairo Modules that unlock usecases on Kakarot Sepolia and iteratively build a vibrant ecosystem of ZK-optimized modules to augment our EVM.

Describe the Feature Request

Needs further scoping cc @enitrat

Create a MerkleProofLib Cairo Module, inspired by Solady's optimized https://github.com/Vectorized/solady/blob/main/src/utils/MerkleProofLib.sol or https://github.com/huff-language/huffmate/blob/main/src/utils/MerkleProofLib.huff to enable developers to verify Merkle inclusion proofs in Kakarot

Describe Preferred Solution

• Check if a Cairo library already exists for Merkle inclusion
• Scope further the issue by identifying sub-libraries to implement first

[augustin-v]

Hello! first-timer here, I'd love to work on this

[onlydustapp]

Hey @augustin-v!
Thanks for showing interest.
We've created an application for you to contribute to Kakarot zkEVM.
Go check it out on OnlyDust!

[enitrat]

@Eikix what's the concrete use case as of now? If not, this is going to be stale for a while until there is demand for it.

[Eikix]

Concrete use case would be to build a toy app that checks the inclusion of an element in a Merkle tree
It'd probably use https://github.com/keep-starknet-strange/alexandria/tree/main/packages/merkle_tree