Giter Club home page Giter Club logo

zk-merkle-tree's Introduction

zk-merkle-tree

A JavaScript library for anonymous voting on Ethereum blockchain using zero-knowledge proof.

The library is based on the source code of Tornado Cash. The most essential component of TC is a Merkle tree where users can deposit ethers with a random commitment, that can be withdrawn with a nullifier. The nullifier is assigned to the commitment, but nobody knows which commitment is assigned to which nullifier, because the link between them is the zero-knowledge. This method can be also used for anonymous voting, where the voter sends a commitment in the registration phase, and a nullifier when she votes. This method ensures that one voter can vote only once.

For more info, please read my article on Medium about the library.

Usage

Create your own voting contract that is inherited from zk-merkle-tree/contracts/ZKTree.sol.

Implement the _commit and _nullify methods.

A simple implementation of the ZKTree contract looks like this (from the zktree-vote project):

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

import "zk-merkle-tree/contracts/ZKTree.sol";

contract ZKTreeVote is ZKTree {
    address public owner;
    mapping(address => bool) public validators;
    mapping(uint256 => bool) uniqueHashes;
    uint numOptions;
    mapping(uint => uint) optionCounter;

    constructor(
        uint32 _levels,
        IHasher _hasher,
        IVerifier _verifier,
        uint _numOptions
    ) ZKTree(_levels, _hasher, _verifier) {
        owner = msg.sender;
        numOptions = _numOptions;
        for (uint i = 0; i <= numOptions; i++) optionCounter[i] = 0;
    }

    function registerValidator(address _validator) external {
        require(msg.sender == owner, "Only owner can add validator!");
        validators[_validator] = true;
    }

    function registerCommitment(
        uint256 _uniqueHash,
        uint256 _commitment
    ) external {
        require(validators[msg.sender], "Only validator can commit!");
        require(
            !uniqueHashes[_uniqueHash],
            "This unique hash is already used!"
        );
        _commit(bytes32(_commitment));
        uniqueHashes[_uniqueHash] = true;
    }

    function vote(
        uint _option,
        uint256 _nullifier,
        uint256 _root,
        uint[2] memory _proof_a,
        uint[2][2] memory _proof_b,
        uint[2] memory _proof_c
    ) external {
        require(_option <= numOptions, "Invalid option!");
        _nullify(
            bytes32(_nullifier),
            bytes32(_root),
            _proof_a,
            _proof_b,
            _proof_c
        );
        optionCounter[_option] = optionCounter[_option] + 1;
    }

    function getOptionCounter(uint _option) external view returns (uint) {
        return optionCounter[_option];
    }
}

The constructor has 4 parameters:

  • _levels is the levels of the Merkle tree. It has to be 20 if you use the default Verifier. If you want to use different number of levels, you have to implement your own Verifier circuit.
  • _hasher is the address of the MiMC sponge smart contract. (Check the test folder for the MiMC sponge generator code.)
  • _verifier is the address of the Verifier contract. It is generated from the Verifier (circuits/Verifier.circom) circuit by the prepare script (scripts/preapre.sh).
  • _numOptions is the number of options.

The registerCommitment method implements the _commit method. It has 2 parameters:

  • _uniqueHash is a unique hash of the voter (ex.: the hash of the ID card). It ensures that one voter is registered only once.
  • _commitment is the commitment of the user.

The vote method implements the _nullify method. It has 6 parameters:

  • _option is the option what the voter chooses.
  • _nullifier is the nullifier for the commitment.
  • _root is the Merkle root for the proof.
  • _proof_a, _proof_b and _proof_c are the zero-knowledge proof.

The commitment and the nullifier is generated on the client side by the generateCommitment method. (Please check the VoterRegistration component in the zktree-vote project.)

To generate the zero-knowledge proof, use calculateMerkleRootAndZKProof. (Please check the Vote component in the zktree-vote project.)

For more info, please check the test folder in the repository and the zktree-vote project.

WARNING: This library is not audited, so use it at your own risk.

zk-merkle-tree's People

Contributors

thebojda avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar

zk-merkle-tree's Issues

Deployed this zk-tree-vote project on testnet but encountered error

Hello, thanks for your earlier reply to the issue I raised.

The project worked perfectly on my local computer as expected.

Then, I decided to move it to testnet.

The voter validation aspect worked perfectly, but when to vote, it shows an error: "exceed maximum block range: 5000". I did some search, and I discover the error is due to "event" that is needed to be retrieved for computation. What can be done.

I think this code portion is the issue, there should be a way to mitigate.
export async function calculateMerkleRootAndPathFromEvents(mimc: any, address: any, provider: any, levels: number, element: any) { const abi = [ "event Commit(bytes32 indexed commitment,uint32 leafIndex,uint256 timestamp)" ]; const contract = new Contract(address, abi, provider) const events = await contract.queryFilter(contract.filters.Commit()) let commitments = [] for (let event of events) { commitments.push(BigNumber.from(event.args.commitment)) } return calculateMerkleRootAndPath(mimc, levels, commitments, element) }

Feature Request: Foundry Support

Hey, thanks for putting together such a useful resource! I found this really easy to import and spin up my own ZK-enabled repo using Hardhat.

Do you have any plans to make this more Foundry-friendly? I'd love to help out if so!

FIELD_SIZE need to change. Is this possible?

Hello,

I am trying to use the MerkleTreeWithHistory.sol smart contract, and I am trying to pass address type (converted to bytes32), as _insert function expects, and raise an error, when reaching the hashLeftRight. The error states: "_left should be inside the field", which means that the uint256 representation of an address produce a number greater that the FIELD_SIZE.

Is this possible to change? And if yes, how?

I am trying to use the circom-ecdsa circuit located here. The circuit expects as input a ethereum private key, extracts the public key and calculates the eth address as the BigInt representation, which later this BigInt is going to be passed to a Merkle Tree as leaf.
Meaning that if we pass an address 0x7c5E44C6074Fb29B309f4AbAE9bF790ba338A208, the circuit returns 710017116651888399609443089319006059204116521480.

Now I managed to do the same with solidity, but the MerkleTreeWithHistory.sol return the aforementioned error. The circuit works fine without problems. A solution would be to incread the FIELD_SIZE, but I do not know whether it is feasible or not.

Thanks in advance.

If a hashFn returns an odd length string, the buffer removes the last digit

My hash fn sometimes returns odd length strings and returns them as the hash of two leaves. Then behind the scenes this string probably gets turned to a buffer before it gets sent to the fn again. The problem is that a buffer from a hex string needs to be even in order to remain untouched. If its odd length it will remove the last digit. Is there a solution?

React JS incompatible

I want to use this library with React (and Next.JS). But I got error:
Module not found: Error: Can't resolve 'fs'

Steps to reproduce:

  1. Create fresh React app: yarn create react-app my-app --template typescript
  2. Add zk-merkle-tree dependency yarn add zk-merkle-tree
  3. Import zk-merkle-tree in src/App.tsx: import {generateCommitment} from "zk-merkle-tree"
  4. Call generateCommitment:
useEffect(() => {
    generateCommitment().then()
  }, [])

src/App.tsx full file example
5. Start project yarn start
6. Get errors:

ERROR in ./node_modules/ejs/lib/ejs.js 46:9-22
Module not found: Error: Can't resolve 'fs' in '<...>/node_modules/ejs/lib'
And much more, here is full error message

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.