I think the following will give gas savings in the decreasing order of savings:

• self.depth is read several times in a function and in for loops, which can be avoided by caching it in memory first. It avoids expensive SLOADs. An example here:
  

  zk-kit/packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol

  Lines 162 to 168 in db0af5c

  	proofPathIndices.length == self.depth && proofSiblings.length == self.depth,
  	"IncrementalBinaryTree: length of path is not correct"
  	);
  	uint256 hash = leaf;
  	for (uint8 i = 0; i < self.depth; i++) {

• depth can be made uint256 instead of uint8. This can give gas savings as while reading self.depth, it won't need to unpack to uint8 since storage reads the entire slot.
  

  zk-kit/packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol

  Line 9 in db0af5c

  uint8 depth; // Depth of the tree (levels - 1).

• i++ in the for loops can be instead incremented through:

  unchecked {
    ++i;
  }

I tried verifying that these steps actually give savings, but didn't find a way to generate gas report since it uses jest, which I'm not familiar with.

Describe the bug
The doc strings should be accurate, according to the code. There are places where this is not the case, and the doc strings are misleading:

https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/src/utils.ts#L57

Expected behavior
Correct docstrings, we should ensure that the docstrings are aligned with the code.

Describe the package you'd like

Implement a TypeScript package which can perform encryption and decryption following this paper.

Additional context

Original implementation

Is your feature request related to a problem? Please describe.
@zk-kit/smt contains a great SMT implementation in Javascript. It would be neat to have a corresponding Noir circuit at hand to be able to verify (non-)membership proofs and it could enable further applications being able to manipulate SMTs from within a circuit (just like you can in the JS implementation)

Describe the solution you'd like
A Noir library with functions for verify, add, update and delete for BN-based SMTs (based on @zk-kit/smt implementation).

Describe alternatives you've considered

Additional context
I worked on respective circuits and discussed with @cedoor that this repo might be a good place for them to live here: #73 (comment)

Description
During initialization of the IncrementalBinaryTree.sol, the user can enter any value for the uint256 zero field. This becomes an issue if the user uses a value greater than the SNARK_SCALAR_FIELD. A zero leaf can be inside an array of proofSiblings when proving existence of a leaf which may cause an issue when the IncrementalBinaryTree.verify function is called during the IncrementalBinaryTree.remove function. The verify function requires that all proofSiblings are less than the SNARK_SCALAR_FIELD:
require(proofSiblings[i] < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: sibling node must be < SNARK_SCALAR_FIELD" );
https://github.com/appliedzkp/zk-kit/blob/main/packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol#L127

So, if the 'zero' leaf is greater than the SNARK_SCALAR_FIELD, this verify function will unintentionally fail.

Possible Fix
Add a require(zero < SNARK_SCALAR_FIELD, "...") statement in the IncrementalBinaryTree.init() function.
https://github.com/appliedzkp/zk-kit/blob/main/packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol#L29

With engine-strict=true inside .npmrc.

Tasks:

• Make package compatible with browsers
• Add reference to circuit
• Add benchmarks to README file
• Add links to Snark artifacts to README file
• Explain what scope and preimage are
• Hash scope and message with keccak256
• Document code
• Handle additional possible errors
• Add tests

Is your feature request related to a problem? Please describe.
It would be nice to get the new root of a tree as a return value from the insert function. This would avoid subsequent operations needing to load it from storage.

Describe the solution you'd like
Return the root from insert.

Describe alternatives you've considered
Accessing the root from storage after an insert isn't too bad because the storage is warm, but it's still much cheaper to have it on the stack.

Additional context

Is your feature request related to a problem? Please describe.
As a smart contract developer who uses the library contract from zk-kit, I hope I can choose to import this library as an internal function to my main contract or as a publicly deployed library. It may be used in different ways based on the requirements (like I want to save the deployment gas cost or run time gas cost...)

Describe the solution you'd like
I propose to modular the library contract by changing it to consist of public and internal libraries. The core logic is implemented in the internal function of the internal library and the public library contract just calls to the internal library.

For example, the IncrementalBinaryTree.sol library can be moved to an internal function library such as IncrementalBinaryTreeInternal.sol, and all the original implementation remains the same, just changing its naming and function visibility from public to internal
Then use the public IncrementalBinaryTree.sol to inherit IncrementalBinaryTreeInternal.sol, which means that the actual implementation is in IncrementalBinaryTreeInternal.sol and IncrementalBinaryTree.sol is only a public function to call the implementation in IncrementalBinaryTreeInternal.sol

In practice, it is roughly as follows

There are some benefits to doing this

1. For developers to be more flexible, they can choose to use external libraries or internal libraries
2. For developers who want to use internal libraries to save run time gas costs, they can directly inherit IncrementalBinaryTreeInternal.sol to their main contract
3. Those who want to save deployment costs can directly use the deployed public shared IncrementalBinaryTree library which is provided the PSE website or github

In addition to the above, this approach maybe can be applied to many contracts in zk-kit generally, like IncrementalQuinTree.sol, LazyMerkleTree.sol... etc. 😉

Is your feature request related to a problem? Please describe.
In some circuit implementations we don't need the pathIndices and instead use the leaf index. We can calculate the pathIndices from the leaf index, but not the reverse.

Describe the solution you'd like
Add leafIndex to the proof object.

Describe alternatives you've considered

Additional context

Question rather than feature, but it might lead to a feature if feasible.

I'm using the LazyIMT and was wondering if it would be possible to get a Merkle Proof directly from the contract. The main benefit I see, is that any app would be able to get said proof to prove things, without having to locally fetch the whole tree and construct it locally. I'm using the LazyIMT because it seems to offer the closest I'm looking for, but open for other trees.

With a reduced example, given the following tree with 8 leafs, I would like to get a Merkle Proof for a given leaf, provided by the contract. Example:

• Proof that C belongs to the tree: [D, HASH_AB, HASH_EFGH]
• Proof that A belongs to the tree: [B, HASH_CD, HASH_EFGH]

          ROOT (Hash_ABCDEFGH)
          /                  \
         /                    \
 HASH_ABCD                   HASH_EFGH
  /      \                   /       \
 /        \                 /         \
HASH_AB   HASH_CD      HASH_EF    HASH_GH
 /   \     /   \       /   \      /   \
A     B   C     D     E     F    G     H

The LazyIMT seems to store in elements the whole tree, both leafs at the bottom and intermediate levels. In theory, I could get the Merkle Proof of C, by accessing elements at different levels:

• D: _indexForElement(0, 3)
• HASH_AB: _indexForElement(1, 0)
• HASH_EFGH: _indexForElement(2, 1)

The problem is that when the leaf is a left element, it's not hashed. So when the amount of leaves is odd, then upper hashes don't match, since they are not initialized yet. In other words, in the above example, one would expect element at _indexForElement(3, 0) to be the root, but this holds true only when the amount of leafs is even. Based on this, seems like I can't naively make elements public and use it for my purpose.

Some questions:

• Why not hashing when having only a left element?
• How gas efficient is a LazyIMT when compared to others? As far as I understand elements stores both leaves and intermediate ones, hashed up to the root. This means that in my example (8 leafs) a total of 15 elements are stored (8,4,2,1) and updated. Can an insert trigger up to MAX_DEPTH hashes?

tldr: In order to not fall into the x->y, this is the problem I'm trying to solve. I would like to get the Merkle Proof of a given leaf, ideally with a view function and without worsening the gas consumption. Is this feasible? Which tree would you recommend me to use? Any idea on how to implement this?

Thanks.

Tasks:

• Support more types
• Refactoring
• Add documentation
• Add licence
• Add more tests

Describe the bug

When updating the Merkle Tree, the index of the updated member is calculated to validate that the updated member is within the subtree of added members. Since proofPathIndices is a uint8, however, it is possible to update a member past numberOfLeaves (or rather the last index at which a user has been added). To do so, a user can replace all 1s with 2s to cause the index calculation to report that index 0 was updated. This occurs both in zk-kit’s update function.

Additional context

This bug was found by Veridise during their audit of Semaphore. If you acknowledge and fix this bug, can you please mention Veridise in the commit.

Is your feature request related to a problem? Please describe.
In the unirep project we need to create many trees over time. To do this we have to copy the zeroes mapping to each new IncrementalTreeData structure on initialization. This involves depth SLOAD and SSTORE operations.

Describe the solution you'd like
Store an optional defaultZeroes for the IncrementalBinaryTree library. Add a flag to the IncrementalTreeData defaultZeroes that will cause the implementation to use the zeroes included in the library.

Describe alternatives you've considered
Rolling a modified version of the incremental merkle tree ourselves.

Additional context

The poseidon-proof circuit can have a parameter that specify the number of inputs the Poseidon hash function can have. The nullified parameters could be changed so that the second parameter is not the preimage (or the preimages in case of many inputs), but the digest, since the digest is a public output.

Describe the package you'd like
Add the circom circuit for HashTower.

Tasks:

• Create @zk-kit/circuits package
• Create merkle-root.circom
• Create poseidon-proof.circom
• Support multiple zk languages (currently Noir and Circom)
• Document packages
• Add tests
  • Set env
  • MT tests
  • Poseidon-proof tests
• Add more info to readme file

Describe the improvement you're thinking about

The nullifier does not actually need to be calculated in the circuit, as the values used as pre-image are public and anyone can therefore calculate them outside the circuit. Removing the nullifier and the Poseidon hash component to calculate it would reduce the number of constraints.

Additional context

For more information, see the following conversation: #127 (comment).

Tasks:

• Add types of Merkle trees to the imt package
• Add circuits to the circuits package README file list
• Add usage section to the poseidon-cipher package

What is your suggestion? Please describe.

The remove function used to remove leaves from Merkle trees is just a an update where the new leaf is zero value. The function body can be completely replaced by a line of code where the update function is called.

function remove(
  IncrementalTreeData storage self,
  uint256 leaf,
  uint256[] calldata proofSiblings,
  uint8[] calldata proofPathIndices
) public {
  update(self, leaf, 0, proofSiblings, proofPathIndices);
}

Additional context

Currently we have the typescript implementation, but no circom counterpart.

Issue

The insertMany function uses the real position of the leaves in an array, this should be updated to use the real position + 1.

Context

The leaves indices in the LeanIMT contracts are not the same as the ones returned with the function indexOf. The indices start at position 1 instead of 0 to facilitate checks for leaf existence and retrieval of leaf position. Then the first leaf is in position 0, but the saved index is 1 and when the indexOf function is used with this leaf, it will return 0.

current status

Description

The idea is to create a function called updateMany. This function can be useful to update many members at once. It should be more efficient to update N members using updateMany once than using the update function N times.

It would be nice to have an implementation for TypeScript and Solidity. Something to remember is that the TypeScript implementation will be different from the Solidity implementation, as the data saved and optimizations in both environments are different.

More context:

The idea is similar to the insertMany function.

insertMany TypeScript implementation: https://github.com/privacy-scaling-explorations/zk-kit/blob/main/packages/imt/src/lean-imt/lean-imt.ts#L162

insertMany Solidity implementation: https://github.com/privacy-scaling-explorations/zk-kit/blob/main/packages/imt.sol/contracts/internal/InternalLeanIMT.sol#L91

Although this is a description for IncrementalBinaryMerkleTree.sol, it probably applies to the Quin Tree contract as well.

Describe the bug

Long story short: It is possible to use the update function to change a zero leaf at an index that hasn't been inserted into the tree yet.

For example, suppose that 4 leaves are inserted into the tree. We can update leaf 7 by proving inclusion of the zero value at leaf 7, because technically the tree is never "empty", but it begins completely filled with zero values.

Updating an uninitialized index can cause the tree root to no longer represent the set of leaves accurately, because the lastSubtrees array will be incorrect at some point when updating the root.

To Reproduce
You can see a demonstration of this bug in a unit test I wrote on my fork of the package:

IncrementalBinaryTreeTest.ts#L188

Expected behavior
The contract should reject updates that reach an index greater than or equal to the number of leaves in the tree. I implemented this in the next commit of the same fork and branch:

contract: IncrementalBinaryTree.sol#L124
test: IncrementalBinaryTreeTest.ts#L188

Additional context
I believe I patched the bug in the IncrementalBinaryMerkleTree.sol contract, as shared above, and if it is a satisfiable solution then I can submit a pull request with that change.

However, I'm mainly opening this bug report because I haven't studied Quin Merkle Trees and don't know how to patch that contract (if the bug is even there, but I'm assuming it is).

I would like to contribute a data structure to the project: HashTower.

The purpose of it is similar to Incremental Binary Tree.

The amortized cost for adding an item into it is O(1).

REF: https://github.com/LCamel/HashTower/tree/85bff67f73c1893d6cbcf1b093f69d4e7e2dfbdb

[Is your feature request related to a problem? Please describe.

MACI contains a number of custom Circom circuits which could be re used by other zk developers.

Describe the solution you'd like

This issue proposes to extract useful templates and integrate them with zk-kit, to allow more developers to easily access well documented and tested Circom code.

List of templates:

• ECDH - #130
• Poseidon - privacy-scaling-explorations/maci#1169
• SHA256 - privacy-scaling-explorations/maci#1187
• Unpack Element - #163
• Comparators - #164
• Float - #165
• EdDSA Signatures verification (MACI rewrite)
• Merkle Trees (binary/quinary) (MACI rewrite)

Ongoing target branch

Describe the bug
We were using old @zk-kit/protocols package, and it was having a useful generic functions for "generateMerkleTree" and "generateMerkleProof" from IncrementalMerkleTree class. Since it's a deprecated package now we switched to use @zk-kit/incremental-merkle-tree package, which doesn't have those useful utility functions.

// @zk-kit/protocol/src/utils.ts

import { IncrementalMerkleTree, MerkleProof } from "@zk-kit/incremental-merkle-tree"
import { poseidon } from "circomlibjs"
import { StrBigInt } from "./types"

/**
 * Creates a Merkle tree.
 * @param depth The depth of the tree.
 * @param zeroValue The zero value of the tree.
 * @param leaves The list of the leaves of the tree.
 * @returns The Merkle tree.
 */
export function generateMerkleTree(depth: number, zeroValue: StrBigInt, leaves: StrBigInt[]): IncrementalMerkleTree {
  const tree = new IncrementalMerkleTree(poseidon, depth, zeroValue, 2)

  for (const leaf of leaves) {
    tree.insert(BigInt(leaf))
  }

  return tree
}

/**
 * Creates a Merkle proof.
 * @param depth The depth of the tree.
 * @param zeroValue The zero value of the tree.
 * @param leaves The list of the leaves of the tree.
 * @param leaf The leaf for which Merkle proof should be created.
 * @returns The Merkle proof.
 */
export function generateMerkleProof(
  depth: number,
  zeroValue: StrBigInt,
  leaves: StrBigInt[],
  leaf: StrBigInt
): MerkleProof {
  if (leaf === zeroValue) throw new Error("Can't generate a proof for a zero leaf")

  const tree = generateMerkleTree(depth, zeroValue, leaves)

  const leafIndex = tree.leaves.indexOf(BigInt(leaf))

  if (leafIndex === -1) {
    throw new Error("The leaf does not exist")
  }

  const merkleProof = tree.createProof(leafIndex)

  merkleProof.siblings = merkleProof.siblings.map((s) => s[0])

  return merkleProof
}

Not sure if that would be a bug or it's intended for some reasons. The solution that we got now is to rewrite this code in our project.

Possible Solution
Could these utility functions be added in @zk-kit/incremental-merkle-tree as a way to easily create an IncrementalMerkleTree and easily generate a proof without needing to rewrite this code again and installing circomlibjs directly in our project?

Description:

actions/cache@v3 can be removed from the workflows.

Describe the bug
The yarn build command execution returns the following message:

➤ YN0000: (!) Plugin typescript: @rollup/plugin-typescript TS2307: Cannot find module 'toml' or its corresponding type declarations.
➤ YN0000: src/index.ts: (4:18)
➤ YN0000: 
➤ YN0000: 4 import toml from "toml"
➤ YN0000:                    ~~~~~~

Is your feature request related to a problem? Please describe.

The current HashTower implementation emits events of internal nodes.
It is prepared for downloading only O(log N) events to build a proof.
However, it seems that partially downloading events might be unsafe:
https://discord.com/channels/943612659163602974/955585525081837628/1092647984887504907
So we go back to emit only the leaf events.

Describe the solution you'd like

Internal nodes will no longer emit events.
Full level length related code can be removed.
We can pack level lengths in to a single uint256.
By removing the count -> length logic, the code might be easier to read.
The gas will also be reduced.

Describe alternatives you've considered

Additional context

https://discord.com/channels/943612659163602974/1065263015622090802/1093713774088835182

We need to add more tests to cover and test different and special cases, as only basic functional tests have been added.

Poseidon-Proof

• poseidon-proof package (see #124)
• poseidon-proof circuit

Binary-Merkle-Root

• binary-merkle-root package
• binary-merkle-root circuit

Describe the package you'd like
Add the Javascript package @zk-kit/hashtower .

Additional context
Developers can use this package to build proofs for @zk-kit/hashtower.sol .

Describe the bug
The update functions in IncrementalBinaryTree.sol and IncrementalQuinTree.sol do not check that the newLeaf parameter is less than the SNARK field order (SFO) before inserting newLeaf into the tree.

Expected behavior
A fundamental invariant of these data structures is that every member of the tree should be less than the SFO. Not checking whether the newLeaf is less than the field size violates that invariant.

Screenshots
Below is the current implementation in IncrementalBinaryTree.sol. Note that the only check is that leaf is a member of the tree. There is no check on newLeaf

    /// @dev Updates a leaf in the tree.
    /// @param self: Tree data.
    /// @param leaf: Leaf to be updated.
    /// @param newLeaf: New leaf.
    /// @param proofSiblings: Array of the sibling nodes of the proof of membership.
    /// @param proofPathIndices: Path of the proof of membership.
    function update(
        IncrementalTreeData storage self,
        uint256 leaf,
        uint256 newLeaf,
        uint256[] calldata proofSiblings,
        uint8[] calldata proofPathIndices
    ) public {
        require(
            verify(self, leaf, proofSiblings, proofPathIndices),
            "IncrementalBinaryTree: leaf is not part of the tree"
        );

        uint256 depth = self.depth;
        uint256 hash = newLeaf;

        uint256 updateIndex;
        for (uint8 i = 0; i < depth; ) {
            updateIndex |= uint256(proofPathIndices[i] & 1) << uint256(i);
            if (proofPathIndices[i] == 0) {
                if (proofSiblings[i] == self.lastSubtrees[i][1]) {
                    self.lastSubtrees[i][0] = hash;
                }

                hash = PoseidonT3.poseidon([hash, proofSiblings[i]]);
            } else {
                if (proofSiblings[i] == self.lastSubtrees[i][0]) {
                    self.lastSubtrees[i][1] = hash;
                }

                hash = PoseidonT3.poseidon([proofSiblings[i], hash]);
            }

            unchecked {
                ++i;
            }
        }
        require(updateIndex < self.numberOfLeaves, "IncrementalBinaryTree: leaf index out of range");

        self.root = hash;
    }

Additional context
This bug was found by Veridise during their audit of Semaphore. If you acknowledge and fix this bug, can you please mention Veridise in the commit.

Proposed solution: semaphore-protocol/semaphore#480 (comment) by @vplasencia