feat(imt): add rust implementation of imt

[Arch0125]

Description

This PR adds Rust implmentation of IMT, aligned with the current TS version, with the following methods included insert/update/delete/create-proof/verify-proof

Related Issue

Resolves #133

Does this introduce a breaking change?

• [ ] Yes
• [x] No

Other information

Test coverage

• [x] Test New IMT Instance

  • Description: Ensure that a new IMT instance is created successfully.

• [x] Test Leaf Insertion

  • Description: Check if new leaves can be inserted into the tree.

• [x] Test Leaf Deletion

  • Description: Test the deletion functionality of a leaf in the tree.

• [x] Test Leaf Update

  • Description: Ensure that a leaf in the tree can be updated correctly.

• [x] Test Create and Verify Proof

  • Description: Create a Merkle proof for a leaf and verify its correctness.

• [x] Should Not Initialize with Too Many Leaves

  • Description: The tree should not initialize if the number of leaves exceeds arity ^ depth.

• [x] Should Not Insert in Full Tree

  • Description: Test that leaves cannot be inserted into a full tree.

• [x] Should Not Delete Nonexistent Leaf

  • Description: Ensure that attempting to delete a nonexistent leaf results in an error.

[cedoor]

Hey @Arch0125, do you think you'll have time to work on the remaining minor changes?

We're planning to create a ZK-Kit repo for Rust and it would be nice to have this implementation there :)

[Arch0125]

Hey @cedoor, yeah ill get done with the minor changes mostly by EOD, or by earlier tomorrow. It kinda slipped out of my mind, got busy with some stuff at work, apologies for that

[cedoor]

@Arch0125 no worries :) Thanks for your quick response!

[Arch0125]

Updating the code structure in the next commit as mentioned by @0xjei

[cedoor]

@Arch0125 This PR should be ready right? Could you solve the conflicts?

[Arch0125]

Yep solving the conflicts asap

[Arch0125]

@cedoor ive fixed the remaining issues that came up after the merge

[gitpoap-bot[bot]]

Congrats, your important contribution to this open-source project has earned you a GitPOAP!

GitPOAP: 2024 ZK-KIT Contributor:

Head to gitpoap.io & connect your GitHub account to mint!

Learn more about GitPOAPs here.

[cedoor]

@Arch0125 Thank you so much for this PR! As a second step, we need to move this crate to the zk-kit.rust repo. Would you like to do it yourself?

[Arch0125]

@cedoor Yeah sure, ill take it up, can you assign it there ?

[cedoor]

@cedoor Yeah sure, ill take it up, can you assign it there ?

Sure, here: https://github.com/privacy-scaling-explorations/zk-kit.rust/issues/3. Can you add a comment there?