Solidity Patricia Tree

Credits

This is a rewritten version of Christian Reitwießner's patricia-trie to use his patricia tree implementation as a solidity library through npm.

latest released version

in progress

Usage

npm i solidity-patricia-tree

pragma solidity ^0.4.25;

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

contract TestPatriciaTree {
    using PatriciaTree for PatriciaTree.Tree;
    PatriciaTree.Tree tree;

    function test() public {
        // testInsert();
        testProofs();
    }

    function testInsert() internal {
        tree.insert("one", "ONE");
        tree.insert("two", "ONE");
        tree.insert("three", "ONE");
        tree.insert("four", "ONE");
        tree.insert("five", "ONE");
        tree.insert("six", "ONE");
        tree.insert("seven", "ONE");
        // update
        tree.insert("one", "TWO");
    }

    function testProofs() internal {
        tree.insert("one", "ONE");
        uint branchMask;
        bytes32[] memory siblings;
        (branchMask, siblings) = tree.getProof("one");
        PatriciaTree.verifyProof(tree.root, "one", "ONE", branchMask, siblings);
        tree.insert("two", "TWO");
        (branchMask, siblings) = tree.getProof("one");
        PatriciaTree.verifyProof(tree.root, "one", "ONE", branchMask, siblings);
        (branchMask, siblings) = tree.getProof("two");
        PatriciaTree.verifyProof(tree.root, "two", "TWO", branchMask, siblings);
    }
}

Development

Pre-requisites

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

Tests

Test cases include the information about how the functions work, but also includes a demo scenario. Running and reading the test cases will help you understand how it works.

npm run test

Contributors

• Original author: Christian Reitwießner
• Wanseob Lim<[email protected]>

License

MIT LICENSE