search

privacy-scaling-explorations / zk-kit.noir

A monorepo of reusable Noir circuits.
MIT License
7 stars 1 forks source link

feat: implement incremental merkle tree #9

Closed YashBit closed 1 month ago

YashBit commented 2 months ago

Important:

  1. Creating a simple PR for just a feedback loop, code not ready yet. Will update the description, etc when I have made all the commits.
  2. Want to check if I am on the correct path and implementing all the necessary components.

Description

YashBit commented 2 months ago

@cedoor I have created a DynamicCalculator trait which will works the same way but with the depth as a parameter now. This basically controls the loop.

In -> packages/merkle-trees/src/incremental_merkle/tree.nr

Questions:

  1. Please let me know if this is the correct direction of implementation with a simple new modified trait that I have completed.

  2. After which I will focus on the MembershipProver, etc methods. Then write the Poseidon Hash tests.

For the tests, how would you like me to test the dynamic depth function? So I should create a tree (let's say of depth 4), and then calculate the results for depth 1, 2, 3?

cedoor commented 1 month ago

@YashBit

  1. Please let me know if this is the correct direction of implementation with a simple new modified trait that I have completed.

The trait seems to be fine, I added other comments for some files that are actually just a copy of the current Merkle tree. You should be able to re-use that code.

  1. After which I will focus on the MembershipProver, etc methods. Then write the Poseidon Hash tests.

Yes, those functions still need to be implemented I guess.

For the tests, how would you like me to test the dynamic depth function? So I should create a tree (let's say of depth 4), and then calculate the results for depth 1, 2, 3?

Exactly, sounds like a good way to test them. Please, take a look at these tests here: https://github.com/privacy-scaling-explorations/zk-kit.circom/blob/326cef9fdb9a2f845b890cffea0594975768be1f/packages/binary-merkle-root/tests/binary-merkle-root.test.ts#L98. You should have the same tests in Noir here.

Also, be aware that this is not an incremental Merkle tree. It works as a general binary Merkle tree with an addition feature: dynamic depth, i.e. the ability to generate a proof with an arbitrary depth even if there's a maximum depth in the circuit (which must be static by design).

signorecello commented 1 month ago

Converting to draft while not ready to merge

YashBit commented 1 month ago

@signorecello Please can you change this back from the draft? The core logic is complete, adding a few tests now.

YashBit commented 1 month ago

@signorecello

Could you please comment on the algorithm? Most of it should remain the same, it is just the calculate_root_dynamic function in now a new trait called DynamicCalculator which should be able to handle the depth function dynamically.

Thank you again.

sripwoud commented 1 month ago

@YashBit CI is (style check ) is failing. Can you please address this issue? I think you should be familiar with that situation given what you've learnt by working on #8

YashBit commented 1 month ago

@sripwoud I will make those changes.

I am mainly concerned with the logic of the incremental tree. That is the most important, since after that I will be done with unit the tests as well.

cedoor commented 1 month ago

@YashBit can we close this PR in favor of https://github.com/privacy-scaling-explorations/zk-kit.noir/pull/16 ?

YashBit commented 1 month ago

@cedoor Yes, please close this one!