search

privacy-scaling-explorations / zk-kit

A monorepo of reusable libraries for zero-knowledge technologies.
https://zkkit.pse.dev
MIT License
284 stars 69 forks source link

Curve trees could help improve efficiency vs current merkle tree usage #330

Open ctrlc03 opened 11 months ago

ctrlc03 commented 11 months ago

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:

alexeuler commented 10 months ago

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 commented 10 months ago

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 commented 10 months ago

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 commented 10 months ago

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 commented 3 weeks ago

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 commented 2 weeks ago

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.