Skip to content
Solidity implementation of partial merkle tree for a light weight side chain execution verification
JavaScript Shell
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
contracts
migrations
scripts
test
.gitignore
.solcover.js
.travis.yml
LICENSE
README.md
package-lock.json
package.json
truffle-config.js
truffle.js

README.md

Solidity Partial Merkle Tree

Credits

This implementation is based on Christian Reitwießner's patricia-trie

latest released version

npm Build Status Coverage Status

in progress

npm Build Status Coverage Status

JavaScript Style Guide

Usage

npm i solidity-partial-tree
npm i solidity-patricia-tree
pragma solidity ^0.4.24;

import {PatriciaTree} from "solidity-patricia-tree/contracts/tree.sol";
import {PartialMerkleTree} from "solidity-partial-tree/contracts/tree.sol";

contract TestPartialMerkleTree {
    using PartialMerkleTree for PartialMerkleTree.Tree;
    using PatriciaTree for PatriciaTree.Tree;

    PatriciaTree.Tree patriciaTree;
    PartialMerkleTree.Tree partialTree;

    /**
     * @dev we can reenact merkle tree transformation by submitting only referred siblings instead of submitting all nodes
     */
    function testOnChainProof() public {
        // update merkle root
        patriciaTree.insert("key1", "val1");
        patriciaTree.insert("key2", "val2");
        patriciaTree.insert("key3", "val3");

        // root hash of patricia tree @ phase A
        bytes32 phaseAOfPatriciaTree = patriciaTree.getRootHash();

        // get siblings to update "key1"
        uint branchMask;
        bytes32[] memory siblings;
        (branchMask, siblings) = patriciaTree.getProof("key1");

        // Init partial tree with the root hash
        partialTree.initialize(phaseAOfPatriciaTree);
        // commit branch (we submit sibling data here)
        partialTree.commitBranch("key1", "val1", branchMask, siblings);

        // Update key1 of patricia tree
        patriciaTree.insert("key1", "val4");

        // Update key1 of partial tree
        partialTree.insert("key1", "val4");

        // get updated root hashes of each tree
        bytes32 phaseBOfPatriciaTree = patriciaTree.getRootHash();
        bytes32 phaseBOfPartialTree = partialTree.getRootHash();

        // We have succeeded to reenact merkle tree transformation without submitting all node data
        require(phaseBOfPatriciaTree == phaseBOfPartialTree);
    }
}

Development

Pre-requisites

npm install -g truffle
npm install -g ganache-cli
npm install

Tests

npm run test

Contributors

License

MIT LICENSE

You can’t perform that action at this time.