zk crash course2

Merkle Tree

circuit

pragma circom 2.0.0;

  

include "../node_modules/circomlib/circuits/poseidon.circom";

include "../node_modules/circomlib/circuits/mux1.circom";

  

template CheckRoot(n) { // compute the root of a MerkleTree of n Levels

signal input leaves[2**n];

signal output root;

  

signal intermediate[2**n-1]; // leaves의 hash값을 저장할 level이 1 높은 배열

  

for (var i =0 ; i< 2**n; i++){

intermediate[i] = leaves[i];

}

  

for(var level = 0; level < n; level++){

var levelSize = 2**(n-level-1);

var halfSize = levelSize \ 2;

  

for(var i = 0; i < levelSize; i++){

intermediate[i] = Poseidon([intermediate[2*i], intermediate[2*i+1]]);

}

  

}

root <== intermediate[0];

}

  

template MerkleTreeInclusionProof(n) {

signal input leaf;

signal input pathIndices[n];

signal input siblings[n]; // path index are 0's and 1's indicating whether the current element is on the left or right

signal output root; // note that this is an OUTPUT signal

  

//[assignment] insert your code here to compute the root from a leaf and elements along the path

component poseidons[n];

component mux[n];

  

signal hashes[n+1];

hashes[0] <== leaf;

  

for (var i = 0; i < n; i++){

  

pathIndices[i] * (1 - pathIndices[i]) === 0;

  

poseidons[i] = Poseidon(2);

mux[i] = MultiMux1(2);

  

mux[i].c[0][0] <== hashes[i];

mux[i].c[0][1] <== siblings[i];

  

mux[i].c[1][0] <== siblings[i];

mux[i].c[1][1] <== hashes[i];

  

mux[i].s <== pathIndices[i];

  

poseidons[i].inputs[0] <== mux[i].out[0];

poseidons[i].inputs[1] <== mux[i].out[1];

  

hashes[i+1] <== poseidons[i].out;

}

  

root <== hashes[n];

}

contract

//SPDX-License-Identifier: Unlicense

pragma solidity ^0.8.0;

  

import { PoseidonT3 } from "./Poseidon.sol"; //an existing library to perform Poseidon hash on solidity

import "./verifier.sol"; //inherits with the MerkleTreeInclusionProof verifier contract

  

contract MerkleTree is Verifier {

uint256[] public hashes; // the Merkle tree in flattened array form

uint256 public index = 0; // the current index of the first unfilled leaf

uint256 public root; // the current Merkle root

  

uint256 public constant TREE_DEPTH = 3;

uint256 public constant LEAF_COUNT = 2**TREE_DEPTH;

  

constructor() {

// [assignment] initialize a Merkle tree of 8 with blank leaves

for (uint256 i =0 ;i < 2 * LEAF_COUNT - 1; i++){

hashes.push(0);

}

  

// Calculate initial root

for (uint256 i = LEAF_COUNT - 1; i > 0; i--) {

uint256 leftChild = hashes[2 * i-1];

uint256 rightChild = hashes[2 * i ];

hashes[i - 1] = PoseidonT3.poseidon([leftChild, rightChild]);

}

root = hashes[0];

}

  

function insertLeaf(uint256 hashedLeaf) public {

// [assignment] insert a hashed leaf into the Merkle tree

require(index < LEAF_COUNT, "Tree is full");

  

uint256 leafIndex = index + LEAF_COUNT - 1;

hashes[leafIndex] = hashedLeaf;

  

uint256 currentIndex = leafIndex;

for (uint256 i = 0; i < TREE_DEPTH; i++) {

currentIndex = (currentIndex - 1) / 2;

uint256 leftChild = hashes[2 * currentIndex + 1];

uint256 rightChild = hashes[2 * currentIndex + 2];

hashes[currentIndex] = PoseidonT3.poseidon([leftChild, rightChild]);

}

  

root = hashes[0];

index++;

}

  

function verify(

uint[2] calldata a,

uint[2][2] calldata b,

uint[2] calldata c,

uint[1] calldata input

) public view returns (bool) {

  

// [assignment] verify an inclusion proof and check that the proof root matches current root

return super.verifyProof(a, b, c, input);

}

}