search

privacy-scaling-explorations / zk-kit.noir

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

feat: incremental tree rebased #16

Closed YashBit closed 1 month ago

YashBit commented 1 month ago

Pull Request: Implement IncrementalMerkleTree and DynamicCalculator

Description

This PR implements the IncrementalMerkleTree struct and the DynamicCalculator trait for Field elements. The implementation includes several key functions:

  1. key_to_path: Transforms a key into a big-endian array of bits.
  2. min: A utility function to return the minimum of two u32 values.
  3. calculate_root_dynamic: Calculates the root of the Merkle tree dynamically based on the provided leaf and siblings.
  4. calculate_two_roots: Calculates two roots for a given leaf entry - one including the leaf and one excluding it.

These implementations provide efficient methods for working with Merkle trees, particularly for proving membership of leaf entries while simultaneously modifying the tree.

Other information

This implementation is part of the zk-kit.noir project and enhances the functionality of Merkle trees within the system. It allows for more flexible and efficient operations on Merkle trees, which is crucial for many zero-knowledge proof applications.

signorecello commented 1 month ago

Which one of the IMT PRs do you want open?

Sorry I should tell you @YashBit I'm quite curious here as why the original Merkle Tree implementation is unfit for an Incremental Merkle Tree.

YashBit commented 1 month ago

@signorecello This is the correct one! Please delete the other one :)

YashBit commented 1 month ago

@signorecello To answer your question from here:

https://github.com/privacy-scaling-explorations/zk-kit.noir/pull/9#pullrequestreview-2275813961

Hey @YashBit I don't understand the goal here. When you use this library in a circuit, you won't be able to pass anything other than an array into its main circuit.

I am just following the merkle-tree example, which I think was written by you, in this. Merkle_trees is of type = lib, and the ECDH was of type bin (it needed to compile from main.pr using nargo compile) which allowed for the creation of a circuit.json which was loaded into the integrated typescript file.

The incremental-tree has been only implemented in the tests pederson.nr and Poseidon.nr etc. It was never loaded into a circuit in the implementations of merkle-tree and sparse-merkle-tree.