commitground/solidity-partial-tree

Solidity implementation of partial merkle tree for a light weight side chain execution verification

Solidity Partial Merkle Tree

Credits

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

latest released version

in progress

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

• Wanseob Lim<email@wanseob.com>

License

MIT LICENSE