solidity-mmr

    1.0.0 • Public • Published

    Solidity Merkle Mountain Range library

    npm Build Status

    Deployed state

    What is Merkle Mountain Range?

    1. Append only data structure
    2. Easy for inclusion proof
    3. Use significantly small amount of gas to append a new item
      • To append 1000 items, MMR used 95307 gas on average while Merkle patricia tree used 676606 gas
      • Regarding to appending an item, MMR was roughly 7 more times cheaper than MPT

    To get more detail information see this

    How to use?

    1. Run the following command in your repository(if you are working on javascript dev env like truffle)

      npm install --save solidity-mmr
    2. import to your smart contract. See MMRWrapper.sol.

      pragma solidity >=0.4.21 <0.6.0;
       
      import {MMR} from "solidity-mmr/contracts/MMR.sol";
       
      contract TestMMR {
          using MMR for MMR.Tree;
          MMR.Tree mmr;
       
          /**
           * Appending 10 items will construct a Merkle Mountain Range like below
           *              15
           *       7             14
           *    3      6     10       13       18
           *  1  2   4  5   8  9    11  12   16  17
           */
          function testMerkleMountainRange() public {
              mmr.append('0x0001'); // stored at index 1
              mmr.append('0x0002'); // stored at index 2
              mmr.append('0x0003'); // stored at index 4
              mmr.append('0x0004'); // stored at index 5
              mmr.append('0x0005'); // stored at index 8
              mmr.append('0x0006'); // stored at index 9
              mmr.append('0x0007'); // stored at index 11
              mmr.append('0x0008'); // stored at index 12
              mmr.append('0x0009'); // stored at index 16
              mmr.append('0x000a'); // stored at index 17
       
              uint256 index = 17;
              // Get a merkle proof for index 17
              (bytes32 root, uint256 size, bytes32[] memory peakBagging, bytes32[] memory siblings) = mmr.getMerkleProof(index);
              // using MMR library verify the root includes the leaf
              Assert.isTrue(MMR.inclusionProof(root, size, index, '0x000a', peakBagging, siblings), "should return true or reverted");
          }
      }

    APIs

    /**
     * @dev This only stores the hashed value of the leaf.
     * If you need to retrieve the detail data later, use a map to store them.
     */
    function append(Tree storage tree, bytes memory data) public;
     
    /**
     * @dev It returns the root value of the tree
     */
    function getRoot(Tree storage tree) public view returns (bytes32);
     
    /**
     * @dev It returns the size of the tree
     */
    function getSize(Tree storage tree) public view returns (uint256);
     
    /**
     * @dev It returns the hash value of a node for the given position. Note that the index starts from 1
     */
    function getNode(Tree storage tree, uint256 index) public view returns (bytes32);
     
    /**
     * @dev It returns a merkle proof for a leaf. Note that the index starts from 1
     */
    function getMerkleProof(Tree storage tree, uint256 index) public view returns (
        bytes32 root,
        uint256 size,
        bytes32[] memory peakBagging,
        bytes32[] memory siblings
    );
     
    /** Pure functions */
     
    /**
     * @dev It returns true when the given params verifies that the given value exists in the tree or reverts the transaction.
     */
    function inclusionProof(
        bytes32 root,
        uint256 size,
        uint256 index,
        bytes memory value,
        bytes32[] memory peakBagging,
        bytes32[] memory siblings
    ) public pure returns (bool);
     
    /**
     * @dev It returns the hash a parent node with hash(M | Left child | Right child)
     *      M is the index of the node
     */
    function hashParent(uint256 index, bytes32 left, bytes32 right) public pure returns (bytes32);
     
    /**
     * @dev it returns the hash of a leaf node with hash(M | DATA )
     *      M is the index of the node
     */
    function hashLeaf(uint256 index, bytes memory data) public pure returns (bytes32);
     
    /**
     * @dev It returns the height of the highest peak
     */
    function mountainHeight(uint256 size) public pure returns (uint8);
     
    /**
     * @dev It returns the height of the index
     */
    function heightAt(uint256 index) public pure returns (uint8 height);
     
    /**
     * @dev It returns whether the index is the leaf node or not
     */
    function isLeaf(uint256 index) public pure returns (bool);
     
    /**
     * @dev It returns the children when it is a parent node
     */
    function getChildren(uint256 index) public pure returns (uint256 left, uint256 right);
     
    /**
     * @dev It returns all peaks of the smallest merkle mountain range tree which includes
     *      the given index(size)
     */
    function getPeaks(uint256 size) public pure returns (uint256[] memory peaks);

    Contribution

    Future work

    • ZK RollUp for MMR (compare the gas cost)

    License

    This software is under the MIT License

    Install

    npm i solidity-mmr

    DownloadsWeekly Downloads

    4

    Version

    1.0.0

    License

    MIT

    Unpacked Size

    45.1 kB

    Total Files

    14

    Last publish

    Collaborators

    • wanseob