Curve trees could help improve efficiency vs current merkle tree usage

[ctrlc03]

It was brought up that Curve Trees might be more efficient that current merkle trees implementations.

This issue should start with researching current implementations, research the feasibility of implementing a TS version and is so benchmarking it against other IMTs

Material:

• https://www.usenix.org/system/files/usenixsecurity23-campanelli.pdf
• https://www.usenix.org/system/files/sec23_slides_campanelli.pdf

[alexeuler]

Hi @ctrlc03! Can you pls add some details about the goal of this issue? Is it to verify that Curve Trees are indeed better than Merkle for MACI, or some POC implementation needed or smth else?

[ctrlc03]

Hi @ctrlc03! Can you pls add some details about the goal of this issue? Is it to verify that Curve Trees are indeed better than Merkle for MACI, or some POC implementation needed or smth else?

Hi @alexeuler - thanks for your interest in this. I'll admit I did not give this too much thought, I opened this issue to track this idea but did not do any preliminary work.
I would say this issue is quite open ended, so any output would be helpful at this stage (a small PoC, a little blogpost showing them in action and debunking how they work; how they could be used in a smart contract, or in Circom (?), and/or in Typescript, etc.; could they work with MACI?; a comparison of speed/efficiency vs incremental merkle trees) - any of these would be very cool to see at this point.

Would you be interested in helping with this at all? 🙂

[alexeuler]

Hi @ctrlc03! Can you pls add some details about the goal of this issue? Is it to verify that Curve Trees are indeed better than Merkle for MACI, or some POC implementation needed or smth else?

Hi @alexeuler - thanks for your interest in this. I'll admit I did not give this too much thought, I opened this issue to track this idea but did not do any preliminary work. I would say this issue is quite open ended, so any output would be helpful at this stage (a small PoC, a little blogpost showing them in action and debunking how they work; how they could be used in a smart contract, or in Circom (?), and/or in Typescript, etc.; could they work with MACI?; a comparison of speed/efficiency vs incremental merkle trees) - any of these would be very cool to see at this point.

Would you be interested in helping with this at all? 🙂

Yeah, I'd love to explore this

[ctrlc03]

Hi @ctrlc03! Can you pls add some details about the goal of this issue? Is it to verify that Curve Trees are indeed better than Merkle for MACI, or some POC implementation needed or smth else?

Hi @alexeuler - thanks for your interest in this. I'll admit I did not give this too much thought, I opened this issue to track this idea but did not do any preliminary work. I would say this issue is quite open ended, so any output would be helpful at this stage (a small PoC, a little blogpost showing them in action and debunking how they work; how they could be used in a smart contract, or in Circom (?), and/or in Typescript, etc.; could they work with MACI?; a comparison of speed/efficiency vs incremental merkle trees) - any of these would be very cool to see at this point.
Would you be interested in helping with this at all? 🙂

Yeah, I'd love to explore this

Feel free to drop in our discord (link at the bottom of our doc website maci.pse.dev) and say hi (we have a MACI public channel), we can share ideas with other people 🙂

[noshin0061]

Hi @ctrlc03 ! I noticed that the discussion on this issue seems to have stopped in the Discord chat. Would it be possible for me to start tackling this issue now?

I'm currently reading papers related to Curve Tree and researching its comparison with Merkle Tree. Additionally, I've found a GitHub repository(https://github.com/simonkamp/curve-trees?tab=readme-ov-file) where someone has implemented Curve Tree, and I plan to explore the feasibility of implementing it in MACI while performing a simple speed comparison with Merkle Tree.

[ctrlc03]

Hi @ctrlc03 ! I noticed that the discussion on this issue seems to have stopped in the Discord chat. Would it be possible for me to start tackling this issue now?

I'm currently reading papers related to Curve Tree and researching its comparison with Merkle Tree. Additionally, I've found a GitHub repository(https://github.com/simonkamp/curve-trees?tab=readme-ov-file) where someone has implemented Curve Tree, and I plan to explore the feasibility of implementing it in MACI while performing a simple speed comparison with Merkle Tree.

Hey @noshin0061 thanks for your interest to help with this. we will be moving this issue to https://github.com/privacy-scaling-explorations/zk-kit/tree/main/packages as we believe it could be made more general and have an implementation that could be re-used by other projects. I'll be changing the description a little bit, so if that sounds good to you, I'll assign you.