merkle-tree-rollup

This library provides "pure" type roll up functions for merkle tree structure. Implementer can choose or implement own hash function to calculate the branch node.

examples test codes

How to use

Install

npm install merkle-tree-rollup

Import and use the roll up tree you want to use

pragma solidity >= 0.6.0;
 
import { Tree } from "merkle-tree-rollup/contracts/library/Types.sol";
import { MiMCTree } from "merkle-tree-rollup/contracts/trees/MiMCTree.sol";
 
contract MiMCExample is MiMCTree {
    Tree public tree;
 
    constructor() public {
        tree = newTree();
    }
 
    function push(
        uint[] memory leaves,
        uint[] memory initialSiblings
    ) public {
        uint newRoot = rollUp(tree.root, tree.index, leaves, initialSiblings);
        tree.root = newRoot;
        tree.index += leaves.length;
    }
}

Implement your custom hash function

This is an example of roll up contract using keccak256 which depth is 7

pragma solidity >= 0.6.0;
 
import { RollUpTree } from "merkle-tree-rollup/contracts/library/RollUpTree.sol";
 
contract KeccaTree is RollUpTree {
    function parentOf(uint left, uint right) public override pure returns (uint) {
        return uint(keccak256(abi.encodePacked(left, right)));
    }
 
    function preHashedZero() public override pure returns (uint[] memory preHashed) {
        preHashed = new uint[](8);
        preHashed[0] = 0x0000000000000000000000000000000000000000000000000000000000000000;
        preHashed[1] = 0xad3228b676f7d3cd4284a5443f17f1962b36e491b30a40b2405849e597ba5fb5;
        preHashed[2] = 0xb4c11951957c6f8f642c4af61cd6b24640fec6dc7fc607ee8206a99e92410d30;
        preHashed[3] = 0x21ddb9a356815c3fac1026b6dec5df3124afbadb485c9ba5a3e3398a04b7ba85;
        preHashed[4] = 0xe58769b32a1beaf1ea27375a44095a0d1fb664ce2dd358e7fcbfb78c26a19344;
        preHashed[5] = 0x0eb01ebfc9ed27500cd4dfc979272d1f0913cc9f66540d7e8005811109e1cf2d;
        preHashed[6] = 0x887c22bd8750d34016ac3c66b5ff102dacdd73f6b014e710b51e8022af9a1968;
        preHashed[7] = 0xffd70157e48063fc33c97a050f7f640233bf646cc98d9524c6b92bcf3ab56f83;
        //...
    }
}

APIs

RollUpTree.sol

You can implement a custom hash function by inheriting RollUpTree contract. RollUpTree has the following interface.

/**
  * @param prevRoot The previous root of the merkle tree
  * @param index The index where new leaves start
  * @param leaves Items to append to the merkle tree
  * @param initialSiblings Sibling data for the merkle proof of the prevRoot
  * @return new root after appending the given leaves
  */
function rollUp(
    uint prevRoot,
    uint index,
    uint[] memory leaves,
    uint[] memory initialSiblings
) public pure returns (uint);
 
/**
 * @param root The roof of a merkle tree
 * @param leaf The leaf to prove the membership
 * @param index Where the leaf is located in
 * @param siblings The sibling data of the given leaf
 * @return proof result in boolean
 */
function merkleProof(
    uint root,
    uint leaf,
    uint index,
    uint[] memory siblings
) public pure returns (bool);
 
/**
 * @dev You should implement how to calculate the branch node. The implementation
 *      can be differ by which hash function you use.
 */
function parentOf(uint left, uint right) public virtual pure returns (uint);
 
/**
 * @dev Merkle tree for roll up consists of empty leaves at first. Therefore you
 *      can reduce the hash cost by using hard-coded pre hashed zero value arrays.
 *      If you want to use a merkle tree which depth is 4, you should return a hard coded
 *      array of uint which length is 5. And the value should be equivalent to the following
 *      [0, hash(0, 0), hash(hash(0,0, hash(0,0)))...]
 */
function preHashedZero() public virtual pure returns (uint[] memory preHashed);

RollUpLib.sol

Or you can implement your own tree contract using the roll up library. RollUpLib provides the following functions.

function rollUp(
    Hasher memory self,
    uint startingRoot,
    uint index,
    uint[] memory leaves,
    uint[] memory initialSiblings
) internal pure returns (uint newRoot);
 
function merkleRoot(
    Hasher memory self,
    uint leaf,
    uint index,
    uint[] memory siblings
) internal pure returns (uint);
 
function merkleProof(
    Hasher memory self,
    uint root,
    uint leaf,
    uint index,
    uint[] memory siblings
) internal pure returns (bool);
 
/**
 * @dev It returns an initialized merkle tree which leaves are all empty.
 */
function newTree(Hasher memory hasher) internal pure returns (Tree memory tree) {
    tree.root = hasher.preHashedZero[hasher.preHashedZero.length - 1];
    tree.index = 0;
}