Mini Tornado.cash ZK part

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 root;
    signal input pathElements[levels];
    signal input pathIndices[levels];

    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;
}

MiniTornadoCash.js

// $ npm install circomlibjs snarkjs
// $ node mini-tornado-cash.js
// will output input.json
// then use snarkjs generate proof, verify ...

const fs = require("fs");
const {
  buildPedersenHash,
  buildMimcSponge,
  buildBabyjub,
} = require("circomlibjs");

// input params
const inputParams = {
  nullifier: 0,
  secret: 1,
  // not taking part in circuits
  recipient: 0,
  relayer: 0,
  fee: 0,
  refund: 0,
};

async function main() {
  const babyJub = await buildBabyjub();
  const F = babyJub.F;
  const mimcsponge = await buildMimcSponge();
  const pedersen = await buildPedersenHash();

  function number2buff(n) {
    let b = Buffer.alloc(31);
    b.writeUInt32LE(n);
    return b;
  }

  function pedersenHash(data) {
    const h = pedersen.hash(data);
    const hP = babyJub.unpackPoint(h);
    return hP[0];
  }

  function hashInput(n, s) {
    const commitment = F.toString(
      pedersenHash(Buffer.concat([number2buff(n), number2buff(s)]))
    );

    const nullifierHash = F.toString(pedersenHash(number2buff(n)));

    return [commitment, nullifierHash];
  }

  let root = 0;
  let tmp_hash = [];
  let pathElements = [];
  let pathIndices = [];
  function generateMerklePath(leaves, index) {
    tmp_hash = [];
    let len = leaves.length / 2;
    for (let i = 0; i < len; i++) {
      const left = leaves[i];
      const right = leaves[i + 1];
      if (left === 0 && right === 0) {
        tmp_hash.push(0);
      } else {
        tmp_hash.push(F.toString(mimcsponge.multiHash([left, right])));
      }
      if (index === i) {
        pathElements.push(right);
        pathIndices.push(0);
      } else if (index === i + 1) {
        pathElements.push(left);
        pathIndices.push(1);
      }
    }
    if (len > 1) {
      generateMerklePath(tmp_hash, index === 0 ? 0 : index / 2);
    } else {
      root = tmp_hash[0];
    }
  }

  const [commitment, nullifierHash] = hashInput(
    inputParams.nullifier,
    inputParams.secret
  );
  
  // level is 2
  generateMerklePath([commitment, 0, 0, 0], 0);

  let input = {
    root,
    nullifierHash,
    recipient: inputParams.recipient,
    relayer: inputParams.relayer,
    fee: inputParams.fee,
    refund: inputParams.refund,
    nullifier: inputParams.nullifier,
    secret: inputParams.secret,
    pathElements,
    pathIndices,
  };

  console.log(input);
  fs.writeFileSync("./input.json", JSON.stringify(input));
}

main().catch((error) => {
  console.error(error);
  process.exitCode = 1;
});

withdraw.circom

pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/bitify.circom";
include "../node_modules/circomlib/circuits/pedersen.circom";
include "merkleTree.circom";

// computes Pedersen(nullifier + secret)
template CommitmentHasher() {
    signal input nullifier;
    signal input secret;
    signal output commitment;
    signal output nullifierHash;

    component commitmentHasher = Pedersen(496);
    component nullifierHasher = Pedersen(248);
    component nullifierBits = Num2Bits(248);
    component secretBits = Num2Bits(248);
    nullifierBits.in <== nullifier;
    secretBits.in <== secret;
    for (var i = 0; i < 248; i++) {
        nullifierHasher.in[i] <== nullifierBits.out[i];
        commitmentHasher.in[i] <== nullifierBits.out[i];
        commitmentHasher.in[i + 248] <== secretBits.out[i];
    }

    commitment <== commitmentHasher.out[0];
    nullifierHash <== nullifierHasher.out[0];
}

// Verifies that commitment that corresponds to given secret and nullifier is included in the merkle tree of deposits
template Withdraw(levels) {
    signal input root;
    signal input nullifierHash;
    signal input recipient; // not taking part in any computations
    signal input relayer;  // not taking part in any computations
    signal input fee;      // not taking part in any computations
    signal input refund;   // not taking part in any computations
    signal input nullifier;
    signal input secret;
    signal input pathElements[levels];
    signal input pathIndices[levels];
    signal output out;

    component hasher = CommitmentHasher();
    hasher.nullifier <== nullifier;
    hasher.secret <== secret;
    hasher.nullifierHash === nullifierHash;

    component tree = MerkleTreeChecker(levels);
    tree.leaf <== hasher.commitment;
    tree.root <== root;
    for (var i = 0; i < levels; i++) {
        tree.pathElements[i] <== pathElements[i];
        tree.pathIndices[i] <== pathIndices[i];
    }

   
    // Add hidden signals to make sure that tampering with recipient or fee will invalidate the snark proof
    // Most likely it is not required, but it's better to stay on the safe side and it only takes 2 constraints
    // Squares are used to prevent optimizer from removing those constraints
    signal recipientSquare;
    signal feeSquare;
    signal relayerSquare;
    signal refundSquare;
    recipientSquare <== recipient * recipient;
    feeSquare <== fee * fee;
    relayerSquare <== relayer * relayer;
    refundSquare <== refund * refund;

}

component main = Withdraw(2);