merkleMapping.sol

pragma experimental ABIEncoderV2;
pragma solidity ^0.4.24;

library merkleMap{

  struct node{
    bytes32 key;
    bytes32 value;
    bytes32 leftChildHash;
    bytes32 rightChildHash;
  }

  function verify(node[] memory merkleChain, bytes32 storageRoot) public pure{

    for(uint i=0; i < merkleChain.length-1; i++){
      require(hash(merkleChain[i]) == merkleChain[i+1].leftChildHash || hash(merkleChain[i]) == merkleChain[i+1].leftChildHash,
      "Invalid Node Linking");

      if(hash(merkleChain[i]) == merkleChain[i+1].leftChildHash){
        require(keyLessThan(merkleChain[i].key, merkleChain[i+1].key), "Incorectly Ordered Tree");
      }
      else{
        require(keyGreaterThan(merkleChain[i].key, merkleChain[i+1].key), "Incorectly Ordered Tree");
      }
    }

    require(hash(merkleChain[merkleChain.length-1]) == storageRoot, "Tree does not match storage root");
  }

  function hash(node holder) internal pure returns(bytes32 ret){
    assembly{
      ret := keccak256(holder, 0x80)
    }
  }
  function keyGreaterThan(bytes32 key1, bytes32 key2) internal pure returns(bool ret){
      uint ptr;
      assembly{
        ptr := mload(0x40)
        mstore(ptr, key1)
        mstore(add(ptr,0x20),key2)
        ret := gt(keccak256(ptr,0x20), keccak256(add(ptr,0x20),32))
      }
  }
  function keyLessThan(bytes32 key1, bytes32 key2) internal pure returns(bool ret){
    uint ptr;
    assembly{
      ptr := mload(0x40)
      mstore(ptr, key1)
      mstore(add(ptr,0x20),key2)
      ret := lt(keccak256(ptr,0x20), keccak256(add(ptr,0x20),32))
    }
  }

  function set(bytes32 key, bytes32 value, node[] merkleChain, bytes32 storageRoot) internal pure returns(bytes32 newStorageRoot){
      verify(merkleChain, storageRoot);

      require(merkleChain[0].key == key ||
        (merkleChain[0].leftChildHash == 0 && keyLessThan(merkleChain[0].key, key)) ||
        (merkleChain[0].rightChildHash == 0 && keyGreaterThan(merkleChain[0].key, key)), "Invalid insertion point");

     if(merkleChain.length == 1){

       node memory newRoot;
       newRoot.key = merkleChain[0].key;
       newRoot.value = value;
       newRoot.leftChildHash = merkleChain[0].leftChildHash;
       newRoot.rightChildHash = merkleChain[0].rightChildHash;

       newStorageRoot = hash(newRoot);
     }

     else{
       for(uint i = merkleChain.length - 1; i > 0; i--){

         if(hash(merkleChain[i-1]) ==  merkleChain[i].leftChildHash){
           require(keyLessThan(key , merkleChain[i].key), "Invalid BST Insertion");
         }
         else{
           require(keyGreaterThan(key , merkleChain[i].key), "Invalid BST Insertion");
         }
       }

       bytes32 newHash = keccak256(abi.encodePacked(keccak256(abi.encodePacked(key)), value, bytes32(0), bytes32(0)));
       bytes32 leftover = hash(merkleChain[0]);

       if(keyLessThan(merkleChain[0].key,key)){
         merkleChain[0].leftChildHash = newHash;
       }
       else if(keyGreaterThan(merkleChain[0].key, key)){
         merkleChain[0].rightChildHash = newHash;
       }
       else{
         merkleChain[0].value = value;
       }

       newStorageRoot = computeNewStateRoot(merkleChain, leftover);
     }
  }
  function computeNewStateRoot(node[] nodeChain, bytes32 leftover) internal pure returns(bytes32){
    for(uint i = 0; i < nodeChain.length-1; i++){

      leftover = hash(nodeChain[i+1]);
      bytes32 newHash = hash(nodeChain[i]);

      if(leftover == nodeChain[i+1].leftChildHash){
        nodeChain[i+1].leftChildHash = newHash;
      }
      else{
        nodeChain[i+1].rightChildHash = newHash;
      }
    }
    return hash(nodeChain[nodeChain.length - 1]);
  }
}