Lean Incremental Merkle Tree inclusion proof

[simon-something]

Describe the package you'd like
A circuit to calculate the root of a lean incremental Merkle tree based on a leaf, its index and its siblings, effectively proving membership of the leaf.

Additional context
There are currently implementations of lean incremental Merkle tree in typescript and solidity in the respective zk-kit repo, but no Circom equivalent. This would provide a way to verify a leaf inclusion, by computing the root based on the leaf, its path/index, and its siblings.

This cannot be done with the current binary Merkle tree taken from Semaphore, as partial subtrees are treated differently (orphan nodes hashed with placeholders vs propagated without hashing).

Side-note: this is a low-hanging fruit as it's already implemented in a @defi-wonderland project (unaudited for now) - I'm just gauging interest in this contribution before writing a readme/proper docs/etc

[cedoor]

Hi @simon-something, thanks for this issue. Could you point to the implementation of @defi-wonderland?

[simon-something]

Hi @cedoor ! Thanks for the answer, unfortunately, the repo is private for now (temporarily tho), here is the implementation in a gist: https://gist.github.com/simon-something/b705500d534f25289e9f5db1ffb275d6 (tested with circomkit/zk-kit LIMT, happy to open a PR with all this if you think it can be of any use!)

[ronanyeah]

That's a great circuit @simon-something - I have implemented it here: https://github.com/ronanyeah/sui-zk-airdrop

[simon-something]

Hey @ronanyeah Great! Good job on the Rust one:)

Watchout that this implementation has not been audited, nor been used in prod (yet)/use at your own risk;)