privacy-scaling-explorations / zk-kit Goto Github PK
View Code? Open in Web Editor NEWA monorepo of reusable libraries for zero-knowledge technologies.
Home Page: https://zkkit.pse.dev/
License: MIT License
A monorepo of reusable libraries for zero-knowledge technologies.
Home Page: https://zkkit.pse.dev/
License: MIT License
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
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.
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);
}
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.
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:
Ongoing target branch
Tasks:
imt
packagecircuits
package README file listusage
section to the poseidon-cipher
packageDescribe 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).
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
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: ~~~~~~
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).
The insertMany
function uses the real position of the leaves in an array, this should be updated to use the real position + 1.
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.
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
circuitBinary-Merkle-Root
binary-merkle-root
packagebinary-merkle-root
circuitDescribe the package you'd like
Implement a TypeScript package which can perform encryption and decryption following this paper.
Additional context
Proposed solution: semaphore-protocol/semaphore#480 (comment) by @vplasencia
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).
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)
Describe the package you'd like
Add the circom circuit for HashTower.
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
IncrementalBinaryTreeInternal.sol
to their main contractIncrementalBinaryTree
library which is provided the PSE website or githubIn addition to the above, this approach maybe can be applied to many contracts in zk-kit
generally, like IncrementalQuinTree.sol
, LazyMerkleTree.sol
... etc. 😉
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
Add the Javascript package @zk-kit/hashtower
.
Additional context
Developers can use this package to build proofs for @zk-kit/hashtower.sol
.
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
Description:
actions/cache@v3
can be removed from the workflows.
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 SLOAD
s. An example here:
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.
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.
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
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
Additional context
Currently we have the typescript implementation, but no circom counterpart.
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
Tasks:
@zk-kit/circuits
packagemerkle-root.circom
poseidon-proof.circom
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:
C
belongs to the tree: [D
, HASH_AB
, HASH_EFGH
]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:
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:
With engine-strict=true
inside .npmrc
.
Tasks:
keccak256
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
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?
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.