Solidity Merkle Mountain Range library
Deployed state
- Mainnet: 0x7a1092e623f1194c4f89fef82f405075ba348e76 view on Etherscan
- Ropsten: 0x3708b7360f31467355cf38013161865eb8bde15f view on Etherscan
What is Merkle Mountain Range?
- Append only data structure
- Easy for inclusion proof
- 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?
-
Run the following command in your repository(if you are working on javascript dev env like truffle)
npm install --save solidity-mmr -
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 1mmr.append('0x0002'); // stored at index 2mmr.append('0x0003'); // stored at index 4mmr.append('0x0004'); // stored at index 5mmr.append('0x0005'); // stored at index 8mmr.append('0x0006'); // stored at index 9mmr.append('0x0007'); // stored at index 11mmr.append('0x0008'); // stored at index 12mmr.append('0x0009'); // stored at index 16mmr.append('0x000a'); // stored at index 17uint256 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 leafAssert.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
- Please check the test cases in the TestMMR.js
Future work
- ZK RollUp for MMR (compare the gas cost)
License
This software is under the MIT License