An introduction of zk-merkle-tree, a JavaScript library for anonymous voting on Ethereum using…
An introduction of zk-merkle-tree, a JavaScript library for anonymous voting on Ethereum using zkSNARK
Anonymity in voting is one of the basic requirements, but on a public network like a blockchain, it’s not trivial to implement it. Fortunately, the technology of zero-knowledge proofs (ZKP) makes it possible, but unfortunately, ZKP is a very complex technology. This is why I built zk-merkle-tree, a JavaScript library that hides almost every complexity of zkSNARK.
There are other libraries like semaphore, that solve this problem. The advantage of zk-merkle-tree is that it is very simple. I also have an example project, where you can see, how you can use it in your own project.
In this article, I will show you step by step how I built this library based on the source code of the coin mixer application, Tornado Cash, so this article will be not only a library introduction but a tutorial on how you can build a general zkSNARK based application.
I have previous articles about zero-knowledge proofs and zkSNARK. It is strongly recommended to read them before this article because this article is based on them.
The first thing that I want to talk about is hashing. In the Ethereum world, we are using variations of the SHA algorithm (SHA-256, Keccak-256, etc.) for hashing. Unfortunately, the calculation of ZKP by using these algorithms is expensive, so we have to use ZK-friendly hashing. There are some ZK-friendly algorithms, like MiMC and Pedersen that are used by Tornado Cash (and also zk-merkle-tree), or Poseidon which is used by semaphore. These hashes can be calculated cheaply in ZK circuits, but are a little bit more expensive on the blockchain than the SHA variations.
Tornado Cash and zk-merkle-tree are using MiMC hashes for building the Merkle tree. Circonlibjs contains an implementation of it and a smart contract generator that you can use to deploy it to the blockchain.
const MiMCSponge = new ethers.ContractFactory(
mimcSpongecontract.abi,
mimcSpongecontract.createCode(SEED, 220),
signers[0]
)
mimcsponge = await MiMCSponge.deploy()The code above is from zktree_test.ts and uses ethers to deploy the MiMC hash contract to the blockchain.
The hasher on the JS side can be generated by the following:
mimc = await buildMimcSponge();You can test your contract by this code:
const res = await mimcsponge["MiMCSponge"](1, 2, 3);
const res2 = mimc.hash(1, 2, 3);
assert.equal(res.xL.toString(), mimc.F.toString(res2.xL));
assert.equal(res.xR.toString(), mimc.F.toString(res2.xR));The first line calculates the hash by using the smart contract, and the second line also calculates it by the JS function. The only interesting part is the number-to-string conversion by F.toString. In zk-SNARK, every calculation is done in a finite field, so we have to use mimc.F.toString for the conversion.
Now we can calculate ZK-friendly MiMC hashes, so everything is ready to build the Merkle tree. The Solidity implementation of the Merkle tree is fully imported from TornadoCash:
// based on https://github.com/tornadocash/tornado-core/blob/master/contracts/MerkleTreeWithHistory.sol
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;
import "hardhat/console.sol";
interface IHasher {
function MiMCSponge(
uint256 in_xL,
uint256 in_xR,
uint256 k
) external pure returns (uint256 xL, uint256 xR);
}
contract MerkleTreeWithHistory {
uint256 public constant FIELD_SIZE =
21888242871839275222246405745257275088548364400416034343698204186575808495617;
uint256 public constant ZERO_VALUE =
21663839004416932945382355908790599225266501822907911457504978515578255421292; // = keccak256("tornado") % FIELD_SIZE
IHasher public immutable hasher;
uint32 public levels;
// the following variables are made public for easier testing and debugging and
// are not supposed to be accessed in regular code
// filledSubtrees and roots could be bytes32[size], but using mappings makes it cheaper because
// it removes index range check on every interaction
mapping(uint256 => bytes32) public filledSubtrees;
mapping(uint256 => bytes32) public roots;
uint32 public constant ROOT_HISTORY_SIZE = 30;
uint32 public currentRootIndex = 0;
uint32 public nextIndex = 0;
constructor(uint32 _levels, IHasher _hasher) {
require(_levels > 0, "_levels should be greater than zero");
require(_levels < 32, "_levels should be less than 32");
levels = _levels;
hasher = _hasher;
for (uint32 i = 0; i < _levels; i++) {
filledSubtrees[i] = zeros(i);
}
roots[0] = zeros(_levels - 1);
}
/**
@dev Hash 2 tree leaves, returns MiMC(_left, _right)
*/
function hashLeftRight(
uint256 _left,
uint256 _right
) public view returns (bytes32) {
require(
_left < FIELD_SIZE,
"_left should be inside the field"
);
require(
_right < FIELD_SIZE,
"_right should be inside the field"
);
uint256 R = _left;
uint256 C = 0;
(R, C) = hasher.MiMCSponge(R, C, 0);
R = addmod(R, _right, FIELD_SIZE);
(R, C) = hasher.MiMCSponge(R, C, 0);
return bytes32(R);
}
function _insert(bytes32 _leaf) internal returns (uint32 index) {
uint32 _nextIndex = nextIndex;
require(
_nextIndex != uint32(2) ** levels,
"Merkle tree is full. No more leaves can be added"
);
uint32 currentIndex = _nextIndex;
bytes32 currentLevelHash = _leaf;
bytes32 left;
bytes32 right;
for (uint32 i = 0; i < levels; i++) {
if (currentIndex % 2 == 0) {
left = currentLevelHash;
right = zeros(i);
filledSubtrees[i] = currentLevelHash;
} else {
left = filledSubtrees[i];
right = currentLevelHash;
}
currentLevelHash = hashLeftRight(uint256(left), uint256(right));
currentIndex /= 2;
}
uint32 newRootIndex = (currentRootIndex + 1) % ROOT_HISTORY_SIZE;
currentRootIndex = newRootIndex;
roots[newRootIndex] = currentLevelHash;
nextIndex = _nextIndex + 1;
return _nextIndex;
}
/**
@dev Whether the root is present in the root history
*/
function isKnownRoot(bytes32 _root) public view returns (bool) {
if (_root == 0) {
return false;
}
uint32 _currentRootIndex = currentRootIndex;
uint32 i = _currentRootIndex;
do {
if (_root == roots[i]) {
return true;
}
if (i == 0) {
i = ROOT_HISTORY_SIZE;
}
i--;
} while (i != _currentRootIndex);
return false;
}
/**
@dev Returns the last root
*/
function getLastRoot() public view returns (bytes32) {
return roots[currentRootIndex];
}
/// @dev provides Zero (Empty) elements for a MiMC MerkleTree. Up to 32 levels
function zeros(uint256 i) public pure returns (bytes32) {
if (i == 0)
return
bytes32(
0x2fe54c60d3acabf3343a35b6eba15db4821b340f76e741e2249685ed4899af6c
);
else if (i == 1)
return
bytes32(
0x256a6135777eee2fd26f54b8b7037a25439d5235caee224154186d2b8a52e31d
);
else if (i == 2)
return
bytes32(
0x1151949895e82ab19924de92c40a3d6f7bcb60d92b00504b8199613683f0c200
);
else if (i == 3)
return
bytes32(
0x20121ee811489ff8d61f09fb89e313f14959a0f28bb428a20dba6b0b068b3bdb
);
else if (i == 4)
return
bytes32(
0x0a89ca6ffa14cc462cfedb842c30ed221a50a3d6bf022a6a57dc82ab24c157c9
);
else if (i == 5)
return
bytes32(
0x24ca05c2b5cd42e890d6be94c68d0689f4f21c9cec9c0f13fe41d566dfb54959
);
else if (i == 6)
return
bytes32(
0x1ccb97c932565a92c60156bdba2d08f3bf1377464e025cee765679e604a7315c
);
else if (i == 7)
return
bytes32(
0x19156fbd7d1a8bf5cba8909367de1b624534ebab4f0f79e003bccdd1b182bdb4
);
else if (i == 8)
return
bytes32(
0x261af8c1f0912e465744641409f622d466c3920ac6e5ff37e36604cb11dfff80
);
else if (i == 9)
return
bytes32(
0x0058459724ff6ca5a1652fcbc3e82b93895cf08e975b19beab3f54c217d1c007
);
else if (i == 10)
return
bytes32(
0x1f04ef20dee48d39984d8eabe768a70eafa6310ad20849d4573c3c40c2ad1e30
);
else if (i == 11)
return
bytes32(
0x1bea3dec5dab51567ce7e200a30f7ba6d4276aeaa53e2686f962a46c66d511e5
);
else if (i == 12)
return
bytes32(
0x0ee0f941e2da4b9e31c3ca97a40d8fa9ce68d97c084177071b3cb46cd3372f0f
);
else if (i == 13)
return
bytes32(
0x1ca9503e8935884501bbaf20be14eb4c46b89772c97b96e3b2ebf3a36a948bbd
);
else if (i == 14)
return
bytes32(
0x133a80e30697cd55d8f7d4b0965b7be24057ba5dc3da898ee2187232446cb108
);
else if (i == 15)
return
bytes32(
0x13e6d8fc88839ed76e182c2a779af5b2c0da9dd18c90427a644f7e148a6253b6
);
else if (i == 16)
return
bytes32(
0x1eb16b057a477f4bc8f572ea6bee39561098f78f15bfb3699dcbb7bd8db61854
);
else if (i == 17)
return
bytes32(
0x0da2cb16a1ceaabf1c16b838f7a9e3f2a3a3088d9e0a6debaa748114620696ea
);
else if (i == 18)
return
bytes32(
0x24a3b3d822420b14b5d8cb6c28a574f01e98ea9e940551d2ebd75cee12649f9d
);
else if (i == 19)
return
bytes32(
0x198622acbd783d1b0d9064105b1fc8e4d8889de95c4c519b3f635809fe6afc05
);
else if (i == 20)
return
bytes32(
0x29d7ed391256ccc3ea596c86e933b89ff339d25ea8ddced975ae2fe30b5296d4
);
else if (i == 21)
return
bytes32(
0x19be59f2f0413ce78c0c3703a3a5451b1d7f39629fa33abd11548a76065b2967
);
else if (i == 22)
return
bytes32(
0x1ff3f61797e538b70e619310d33f2a063e7eb59104e112e95738da1254dc3453
);
else if (i == 23)
return
bytes32(
0x10c16ae9959cf8358980d9dd9616e48228737310a10e2b6b731c1a548f036c48
);
else if (i == 24)
return
bytes32(
0x0ba433a63174a90ac20992e75e3095496812b652685b5e1a2eae0b1bf4e8fcd1
);
else if (i == 25)
return
bytes32(
0x019ddb9df2bc98d987d0dfeca9d2b643deafab8f7036562e627c3667266a044c
);
else if (i == 26)
return
bytes32(
0x2d3c88b23175c5a5565db928414c66d1912b11acf974b2e644caaac04739ce99
);
else if (i == 27)
return
bytes32(
0x2eab55f6ae4e66e32c5189eed5c470840863445760f5ed7e7b69b2a62600f354
);
else if (i == 28)
return
bytes32(
0x002df37a2642621802383cf952bf4dd1f32e05433beeb1fd41031fb7eace979d
);
else if (i == 29)
return
bytes32(
0x104aeb41435db66c3e62feccc1d6f5d98d0a0ed75d1374db457cf462e3a1f427
);
else if (i == 30)
return
bytes32(
0x1f3c6fd858e9a7d4b0d1f38e256a09d81d5a5e3c963987e2d4b814cfab7c6ebb
);
else if (i == 31)
return
bytes32(
0x2c7a07d20dff79d01fecedc1134284a8d08436606c93693b67e333f671bf69cc
);
else revert("Index out of bounds");
}
}The contract has 2 initial parameters. The level of the tree, and the address of the MiMC hasher contract.
The hashLeftRight private method calculates the MiMC hash of the pair of elements.
The _insert method inserts an element and calculates the new Merkle root. The tree stores the history of the last 30 roots because Ethereum transactions are not real-time. It is possible that you send your Merkle proof to the blockchain, but before your transaction, somebody inserts a new element that changes the Merkle root. Because of the history, your Merkle proof will be still valid, because the root that you used for your proof is in the history. This root checking is done by the isKnownRoot method.
Now we have a ZK-friendly Merkle tree where we can store the commitments. Let’s see, how we can calculate a Merkle proof for our commitment:
// calculates Merkle root from elements and a path to the given element
export function calculateMerkleRootAndPath(mimc: any, levels: number, elements: any[], element?: any) {
const capacity = 2 ** levels
if (elements.length > capacity) throw new Error('Tree is full')
const zeros = generateZeros(mimc, levels);
let layers = []
layers[0] = elements.slice()
for (let level = 1; level <= levels; level++) {
layers[level] = []
for (let i = 0; i < Math.ceil(layers[level - 1].length / 2); i++) {
layers[level][i] = calculateHash(
mimc,
layers[level - 1][i * 2],
i * 2 + 1 < layers[level - 1].length ? layers[level - 1][i * 2 + 1] : zeros[level - 1],
)
}
}
const root = layers[levels].length > 0 ? layers[levels][0] : zeros[levels - 1]
let pathElements = []
let pathIndices = []
if (element) {
const bne = BigNumber.from(element)
let index = layers[0].findIndex(e => BigNumber.from(e).eq(bne))
for (let level = 0; level < levels; level++) {
pathIndices[level] = index % 2
pathElements[level] = (index ^ 1) < layers[level].length ? layers[level][index ^ 1] : zeros[level]
index >>= 1
}
}
return {
root: root.toString(),
pathElements: pathElements.map((v) => v.toString()),
pathIndices: pathIndices.map((v) => v.toString())
}
}This method is from zktree.ts, and calculates the Merkle proof for the given element. For the Merkle root calculation, we need the previously added elements and build the Merkle tree. We can read this information from the blockchain because every insert operation emits a Commit event. The code below collects these events and calculates the Merkle proof from them:
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)
}Now we have a Merkle tree on the blockchain, we can insert elements into it and we can generate Merkle proofs on the client side, so let’s see the ZK part:
// based on https://github.com/tornadocash/tornado-core/blob/master/circuits/merkleTree.circom
pragma circom 2.0.0;
include "../node_modules/circomlib/circuits/mimcsponge.circom";
// Computes MiMC([left, right])
template HashLeftRight() {
signal input left;
signal input right;
signal output hash;
component hasher = MiMCSponge(2, 220, 1);
hasher.ins[0] <== left;
hasher.ins[1] <== right;
hasher.k <== 0;
hash <== hasher.outs[0];
}
// if s == 0 returns [in[0], in[1]]
// if s == 1 returns [in[1], in[0]]
template DualMux() {
signal input in[2];
signal input s;
signal output out[2];
s * (1 - s) === 0;
out[0] <== (in[1] - in[0])*s + in[0];
out[1] <== (in[0] - in[1])*s + in[1];
}
// Verifies that merkle proof is correct for given merkle root and a leaf
// pathIndices input is an array of 0/1 selectors telling whether given pathElement is on the left or right side of merkle path
template MerkleTreeChecker(levels) {
signal input leaf;
signal input pathElements[levels];
signal input pathIndices[levels];
signal output root;
component selectors[levels];
component hashers[levels];
for (var i = 0; i < levels; i++) {
selectors[i] = DualMux();
selectors[i].in[0] <== i == 0 ? leaf : hashers[i - 1].hash;
selectors[i].in[1] <== pathElements[i];
selectors[i].s <== pathIndices[i];
hashers[i] = HashLeftRight();
hashers[i].left <== selectors[i].out[0];
hashers[i].right <== selectors[i].out[1];
}
root <== hashers[levels - 1].hash;
}The Merkle proof validator circuit is also copied from the source of Tornado Cash, like the Merkle tree contract itself. The circuit iterates on the path elements and calculates the Merkle root. When the voter votes, she doesn’t have to send the Merkle proof to the smart contract, only the Merkle root, and the ZK proof that she can successfully calculate the root by using this circuit and the Merkle proof that is known only by her (this is the private part of ZKP).
The last step is the commitment/nullifier generation method. To ensure that one voter votes only once, she has to send a nullifier to the blockchain, which is registered by the smart contract, and can be used only once. The nullifier has to be unique and assigned to the commitment. So, one commitment has only one nullifier, but because of ZKP, nobody knows (only the voter) which nullifier is assigned to which commitment. The nullifier is generated by MiMC in zk-merkle-tree:
export async function generateCommitment() {
const mimc = await buildMimcSponge();
const nullifier = BigNumber.from(crypto.randomBytes(31)).toString()
const secret = BigNumber.from(crypto.randomBytes(31)).toString()
const commitment = mimc.F.toString(mimc.multiHash([nullifier, secret]))
const nullifierHash = mimc.F.toString(mimc.multiHash([nullifier]))
return {
nullifier: nullifier,
secret: secret,
commitment: commitment,
nullifierHash: nullifierHash
}
}As you can see, the commitment is a hash of the nullifier and a secret. The public part is the hash of the nullifier and the commitment hash, the secret is private. It’s easy to see, that without the secret, nobody can link the commitment to the nullifier.
Let’s see the whole validator circuit:
pragma circom 2.0.0;
include "CommitmentHasher.circom";
include "MerkleTreeChecker.circom";
template Verifier(levels) {
signal input nullifier;
signal input secret;
signal input pathElements[levels];
signal input pathIndices[levels];
signal output nullifierHash;
signal output root;
component commitmentHasher = CommitmentHasher();
component merkleTreeChecker = MerkleTreeChecker(levels);
commitmentHasher.nullifier <== nullifier;
commitmentHasher.secret <== secret;
merkleTreeChecker.leaf <== commitmentHasher.commitment;
for (var i = 0; i < levels; i++) {
merkleTreeChecker.pathElements[i] <== pathElements[i];
merkleTreeChecker.pathIndices[i] <== pathIndices[i];
}
nullifierHash <== commitmentHasher.nullifierHash;
root <== merkleTreeChecker.root;
}
component main = Verifier(20);The circuit is relatively simple. The CommitmentHasher validates the commitment and the nullifier hashes by using the nullifier and the secret as private parameters. If the commitment is valid, it validates the given Merkle proof in the next step.
Now we have everything that we need, so let’s put things together:
export async function calculateMerkleRootAndZKProof(address: any, provider: any, levels: number, commitment: any, zkey: any) {
const mimc = await buildMimcSponge();
const rootAndPath = await calculateMerkleRootAndPathFromEvents(mimc, address, provider, levels, commitment.commitment);
const { proof, publicSignals } = await snarkjs.groth16.fullProve(
{
nullifier: commitment.nullifier, secret: commitment.secret,
pathElements: rootAndPath.pathElements, pathIndices: rootAndPath.pathIndices
},
getVerifierWASM(),
zkey);
const cd = convertCallData(await snarkjs.groth16.exportSolidityCallData(proof, publicSignals));
return {
nullifierHash: publicSignals[0],
root: publicSignals[1],
proof_a: cd.a,
proof_b: cd.b,
proof_c: cd.c
}
}After the voter generated the commitment, she sends it to the smart contract that stores it in the Merkle tree. In the voting phase, she uses the calculateMerkleRootAndZKProof method that calculates the Merkle proof from the Commit events that are emitted by the smart contract. This method calculates the zero-knowledge proof and converts it into the correct form for the validator smart contract.
The Validator smart contract is generated from the Validator circuit by snarkjs. It can be done by the following command:
npx snarkjs zkey export solidityverifier build/Verifier.zkey contracts/Verifier.solFor more info, please check the prepare.sh script, and my previous article about the topic.
The full ZKTree contract looks like this:
// based on https://github.com/tornadocash/tornado-core/blob/master/contracts/Tornado.sol
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;
import "./MerkleTreeWithHistory.sol";
interface IVerifier {
function verifyProof(
uint[2] memory a,
uint[2][2] memory b,
uint[2] memory c,
uint[2] memory input
) external pure returns (bool r);
}
contract ZKTree is MerkleTreeWithHistory {
mapping(bytes32 => bool) public nullifiers;
mapping(bytes32 => bool) public commitments;
IVerifier public immutable verifier;
event Commit(
bytes32 indexed commitment,
uint32 leafIndex,
uint256 timestamp
);
constructor(
uint32 _levels,
IHasher _hasher,
IVerifier _verifier
) MerkleTreeWithHistory(_levels, _hasher) {
verifier = _verifier;
}
function _commit(bytes32 _commitment) internal {
require(!commitments[_commitment], "The commitment has been submitted");
commitments[_commitment] = true;
uint32 insertedIndex = _insert(_commitment);
emit Commit(_commitment, insertedIndex, block.timestamp);
}
function _nullify(
bytes32 _nullifier,
bytes32 _root,
uint[2] memory _proof_a,
uint[2][2] memory _proof_b,
uint[2] memory _proof_c
) internal {
require(!nullifiers[_nullifier], "The nullifier has been submitted");
require(isKnownRoot(_root), "Cannot find your merkle root");
require(
verifier.verifyProof(
_proof_a,
_proof_b,
_proof_c,
[uint256(_nullifier), uint256(_root)]
),
"Invalid proof"
);
nullifiers[_nullifier] = true;
}
}The contract is inherited from the MerkleTree contract, and it has 3 initial parameters. The level and the hasher for the Merkle tree, and the address of the Verifier contract that is generated by snarkjs from the Verifier circuit.
The _commit method inserts the commitment into the Merkle tree and emits the Commit event for the Merkle root calculation.
The _nullify method checks that the nullifier is not used (one voter can vote only once), checks the root by the isKnownRoot method, and verifies the zero-knowledge proof.
The _commit and _nullify methods are abstract, so you cannot use the ZKTree contract directly, you have to inherit your own contract from it. This top-level contract will be responsible for the voter validation, and registration of votes.
You can find a minimal implementation in the zktree-vote project (I have a full article about it).
In summary, the implementation and the voting process are the following:
- You have to implement the ZKTree contract and deploy it. Your contract will responsible for voter and vote registration.
- The voter generates a commitment by the generateCommitment method and sends the commitment to the smart contract in the registration phase.
- In the voting phase, the voter generates the zero-knowledge proof by the calculateMerkleRootAndZKProof method and sends it with the nullifier to the smart contract, which verifies it and registers the vote.
That’s all. I hope this article will help you to understand how zero-knowledge proofs can be used with JavaScript and Solidity (not only for voting).
For more info, please check the zk-merkle-tree repository, and the zktree-vote repository which is an example implementation of the library.