starter pack: merkle-patricia-trie proof verifier

readme.md

Building on the Stateless MPT-based token script for Scout.

instructions

1. use smtp-proof-generator.js to generate a test vector for a basic merkle-patricia-trie proof verifier.
2. paste the test vector into verify-branch.js

TODO

• verify-branch.js only verifies a single proof (i.e. a single merkle branch)
• a more complex verifier would verify a multi-proof (see the turbo-geth docs for an example of a multi-proof)
• verify-branch.js is self-contained, so we can see everything we'd need to port (with the exception of keccak256) for a new implementation, e.g. in AssemblyScript

smtp-proof-generator.js

// code here is from https://github.com/ewasm/scout/pull/11
// added a console.log to print a single proof, for use as a test vector

const assert = require('assert')
const { promisify } = require('util')
const BN = require('bn.js')
const Trie = require('merkle-patricia-tree')
const Account = require('ethereumjs-account').default
const StateManager = require('ethereumjs-vm/dist/state/stateManager').default
const PStateManager = require('ethereumjs-vm/dist/state/promisified').default
const { keccak256, ecsign, stripZeros } = require('ethereumjs-util')
const { encode } = require('rlp')
const Wallet = require('ethereumjs-wallet')
const yaml = require('js-yaml')
const fs = require('fs')

const prove = promisify(Trie.prove)
const verifyProof = promisify(Trie.verifyProof)

async function main () {
  const testSuite = {
    'beacon_state': {
      'execution_scripts': [
        'target/wasm32-unknown-unknown/release/smpt.wasm'
      ],
    },
    'shard_pre_state': {
      'exec_env_states': [
      ]
    },
    'shard_blocks': [
    ],
    'shard_post_state': {
      'exec_env_states': [
      ]
    }
  }

  const rawState = new StateManager()
  const state = new PStateManager(rawState)

  // Generate random accounts
  let accounts = await generateAccounts(state, 5000)

  let root = await state.getStateRoot()
  testSuite.shard_pre_state.exec_env_states.push(root.toString('hex'))

  // Generate txes
  let [txes, proofNodes, simulationData] = await generateTxes(state, accounts, 70)

  // Serialize witnesses and tx data
  const blockData = encode([txes, proofNodes])
  console.log(`block data length: ${blockData.length}`)
  testSuite.shard_blocks.push({
    'env': 0,
    'data': blockData.toString('hex')
  })

  // Apply txes on top of trie to compute post state root
  for (tx of simulationData) {
    await transfer(state, tx)
  }

  root = await state.getStateRoot()
  testSuite.shard_post_state.exec_env_states.push(root.toString('hex'))

  //const serializedTestSuite = yaml.safeDump(testSuite)
  //fs.writeFileSync('smpt.yaml', serializedTestSuite)
}

function proofBuffersToHex(proof) {
  return proof.map(elem => elem.toString('hex'))
}

async function generateTxes (state, accounts, count=50) {
  let txes = []
  let simulationData = []
  let proofNodes = {}
  const root = await state.getStateRoot()
  let totalNodes = 0
  for (let i = 0; i < count; i++) {
    const from = accounts[i].address
    const to = accounts[i + 1].address
    const value = new BN('00000000000000000000000000000000000000000000000000000000000000ff', 16)
    const nonce = new BN('0000000000000000000000000000000000000000000000000000000000000000', 16)
    simulationData.push({ from, to, value, nonce })

    const fromAccount = await state.getAccount(from)
    const fromWitness = await prove(state._wrapped._trie, keccak256(from))
    // just print the first proof
    if (i === 0) {
      const proofData = {
        fromWitness: proofBuffersToHex(fromWitness),
        root: root.toString('hex'),
        fromAddress: from.toString('hex'),
        fromAccountLeaf: fromAccount.serialize().toString('hex')
      };
      // use this proof (i.e. a single merkle branch) as a test vector
      console.log('proofData:', JSON.stringify(proofData))
    }

    let val = await verifyProof(root, keccak256(from), fromWitness)
    assert(val.equals(fromAccount.serialize()), "valid from witness")
    for (item of fromWitness) {
      totalNodes++
      proofNodes[keccak256(item).toString('hex')] = item
    }

    const toAccount = await state.getAccount(to)
    const toWitness = await prove(state._wrapped._trie, keccak256(to))
    val = await verifyProof(root, keccak256(to), toWitness)
    assert(val.equals(toAccount.serialize()), "valid to witness")
    for (item of toWitness) {
      totalNodes++
      proofNodes[keccak256(item).toString('hex')] = item
    }

    const txRlp = encode([to, stripZeros(value.toBuffer('be', 32)), stripZeros(nonce.toBuffer('be', 32))])
    const txHash = keccak256(txRlp)
    const txSig = ecsign(txHash, accounts[i].privateKey)

    txes.push([to, stripZeros(value.toBuffer('be', 32)), stripZeros(nonce.toBuffer('be', 32)), [stripZeros(txSig.r), stripZeros(txSig.s), txSig.v]])
  }
  console.log(`Deduplicated ${totalNodes} total proof nodes down to ${Object.values(proofNodes).length} nodes`)
  return [txes, Object.values(proofNodes), simulationData]
}

async function transfer (state, tx) {
  let { from, to, value, nonce } = tx
  assert(value.gten(0))

  const fromAcc = await state.getAccount(from)
  const toAcc = await state.getAccount(to)

  assert(new BN(fromAcc.balance).gte(value))
  assert(new BN(fromAcc.nonce).eq(nonce))

  const newFromBalance = new BN(fromAcc.balance).sub(value)
  fromAcc.balance = newFromBalance.toBuffer()
  fromAcc.nonce = nonce.addn(1).toBuffer()
  const newToBalance = new BN(toAcc.balance).add(value)
  toAcc.balance = newToBalance.toBuffer()

  await state.putAccount(from, fromAcc)
  await state.putAccount(to, toAcc)
}

async function generateAccounts (state, count=500) {
  let accounts = []
  for (let i = 0; i < count; i++) {
    let wallet = Wallet.generate()
    let address = wallet.getAddress()
    let privateKey = wallet.getPrivateKey()
    let account = new Account()
    account.balance = new BN('ffffff', 16).toBuffer()
    accounts.push({
      address,
      privateKey,
      account
    })
    await state.putAccount(address, account)
  }
  return accounts
}

main().then(() => {}).catch((e) => console.log(e))

verify-branch.js

/**
 * this is a self-contained file with everything needed to verify a merkle-patricia-trie proof
 * functions were copy/pasted from the require() dependencies
 * the only imported dependency is keccak256
 * code is mostly from the verifyProof function in https://github.com/ethereumjs/merkle-patricia-tree/blob/v3.0.0/src/proof.js#L31-L39
 */

const assert = require('assert')
//const rlp = require('rlp');
//const ethUtil = require('ethereumjs-util');
//const Trie = require('merkle-patricia-tree')

// imported deps:
// ethUtil.toBuffer
// ethUtil.sha3
// ethUtil.rlp.decode
const { keccak256 } = require('ethereumjs-util')

const proofData = {
  "fromWitness":["f90211a042d5f0401d27bdae05452ce52bcee42a2c659c112d15b5f30b126b9ec24c68c0a045454ccb94e62efdbcd08423b7eef4cac43614025010c4312a745f67401588a5a02afb19069a247c89761e8eef700649c95743f1651e837c26aab6880228bedbf3a0305dd55390d2baea9157b4b1841bf1356b1187310bacc5eb848c34ce1391875aa0b53a79d67ee772cfdc8df03402e1400e7ff4df4e97423a6296c2b71a7649af1ca0dfaffef77c95e519bd9f2ef464c69545b5085106d767ed1dfcb2fef12d3f94f5a0a898ad01e272c350dd4a7954bd3eda10837ee79de6d7a99245a3b5d638ad51aea0d5476878fd37d082f47084404592dc5fe1f88911e25709862f078712806f0c00a0345ae4503837685c7656a1d7753ba02bafec78f7dd99e18b7f34af9a2ae0d5f5a00b330c853039769f2f6c193ede0d597e84c16694c30bf45ae542c744ee08705aa0f5c48d706862325d76408f20df39f41e7c4dbd37dfbf1862fb5fed95324d7cb4a068eea910788058bc79939fe8077713bc8a18546d1f7ea5883bed970a82cbc3cfa066b9fd9323d3e0192ca69393413812bb2ebe025ebb120d31984f9e9a7a26dbd8a09852cd62db324e6bb2c94d04a5e0b24174af7dfaecebff58801be80f4d1e5400a0414befb1392d59c80ec0437feeab156080c237257ef2b352706f1946dec6c1baa060a5007191b8029e1b03785b2208e86e454eff23748c326a82767de3e16bc05e80","f90211a0f39fe5a7162c45b22c02cb94230a20e2c560a4ac47139f16d5d854aa59824dbca02d1eab2837fe85989bb4c81909b72cca54cb9d1f468e7ec4e3eb456fd495a743a0a5bdd40ad518900a7e5d6eabca6a64e92eef2652dc29923588cf97da71c74ebda067443e65a990f381fac8edf910a808cc2dc2103fd1fa5e7034a707c8700ae82ca035d8a519ef64ebcd0612da781942c35a44f4a7bd3799d44795fa852d05896430a03dd798002fbde0bacdca72a40f9830dfebd407814d9a0c9b4a0020aa1a70b0a4a0ce022440e14c927be3aae6292544706bb8634be61706225d4c3538a26319e9cda0ff32461e225e1ba6ba743917423ea5533c325a301eb84d150d5616d3da46a723a0a98b509e64063e9103f9bc6b88f7bd7c16fff6f87cab04b3cdbd979eb2d2bc2ba0c2cf127b1b4fc25b6ee52426f283ce469094bcfc5628d1b6dfc16ec42d5b16fda0b0bfb7da5d53eeab7a0cfc5a3c7967d5d57f36d52b89ac7741f0c930f2c035f4a0c64b3feb9c5c536aa7bd0604972eaa941fa7e3291059cbea7e3147fcda56c01ba058441cdf89d8d096fd260bcc01a184f77ee5de3ce751e3d7b552f21b996a45d8a01e2e3820cf9c8d9b0b0189c982e8d71f9e29257e48c184c218c3192c5fc2ba04a0a179362070964bd10e6ad521210237263ff1350046a6485e2bbcc9ae24b77a7fa022e8825104733446e36377c3bfc29b391ca456c4eb74a8d28c0a6dfd12e9e5b480","f90131808080a0bfd028e4ddbd46a359735f552d34c0564703e437a35a9ac250e3fde4d1a53e8aa07bc9a92b34fd3cb44243cad532d806c5b56c4037bd7ad4a0f1022da71a95278080a0e777030539c5a325e56bf340093d9122e60bce40217d5ac798e4babc1a655a25a0ebf8f6d6e437ee47289a1fd7623310071ddd8f0ab6f0da3be455bdec071e566e80a0ed7c3468f9983ea04abb3300c38388275566a05872420e468beeadfe4fcf5d3ba01d79398dc95870d72a573ad00e71c6d3ff71e8baa14c4f16093cd908fb037736a0199d7eb18bed36b5ee521a0f0832a5b4a1d4aec8c78bbb49d85dfd36f63a924f80a004c839f5d54f77790d78efe546ee72186e01344775ad02e3f5c9cb2c681cbf80a0e0316b195732276c8de71499c16de5503ba4ba5b5d11438387e25061865e58188080","f87180808080a0bd47c4f9db488edbfab24643591aabab4ec3d104abf6235a361d41bdd3ca7f7080808080808080a0dbfac81e828c6c6cd0142def55de51773458e89c250a71870d09af2d2f5088b180a06eaca5c29825ba75ba49115c2b88635f20b2a4a3e61fa722310f4a640b4815e78080","f86b9f200cd89ae762119fed6ecd8dc969077bb2d6a3471c639a10e710a9374a121db849f8478083ffffffa056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470"],
  "root":"65b7b9ccb7a4d828986e488e081bc11bfa5ef6141fb06b0af2e9a0bda273a753",
  "fromAddress":"6cdf39d8d75538a0cad721f24276ec48562e5c90",
  "fromAccountLeaf":"f8478083ffffffa056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470"
};




function TrieNode(type, key, value) {
  if (Array.isArray(type)) {
    // parse raw node
    this.parseNode(type);
  } else {
    this.type = type;

    if (type === 'branch') {
      var values = key;
      this.raw = Array.apply(null, Array(17));

      if (values) {
        values.forEach(function (keyVal) {
          this.set.apply(this, keyVal);
        });
      }
    } else {
      this.raw = Array(2);
      this.setValue(value);
      this.setKey(key);
    }
  }
}


TrieNode.isRawNode = isRawNode;
TrieNode.addHexPrefix = addHexPrefix;
TrieNode.removeHexPrefix = removeHexPrefix;
TrieNode.isTerminator = isTerminator;
TrieNode.stringToNibbles = stringToNibbles;
TrieNode.nibblesToBuffer = nibblesToBuffer;
TrieNode.getNodeType = getNodeType;
Object.defineProperty(TrieNode.prototype, 'value', {
  get: function get() {
    return this.getValue();
  },
  set: function set(v) {
    this.setValue(v);
  }
});
Object.defineProperty(TrieNode.prototype, 'key', {
  get: function get() {
    return this.getKey();
  },
  set: function set(k) {
    this.setKey(k);
  }
}); // parses a raw node

TrieNode.prototype.parseNode = function (rawNode) {
  this.raw = rawNode;
  this.type = getNodeType(rawNode);
}; // sets the value of the node


TrieNode.prototype.setValue = function (key, value) {
  if (this.type !== 'branch') {
    this.raw[1] = key;
  } else {
    if (arguments.length === 1) {
      value = key;
      key = 16;
    }

    this.raw[key] = value;
  }
};

TrieNode.prototype.getValue = function (key) {
  if (this.type === 'branch') {
    if (arguments.length === 0) {
      key = 16;
    }

    var val = this.raw[key];

    if (val !== null && val !== undefined && val.length !== 0) {
      return val;
    }
  } else {
    return this.raw[1];
  }
};

TrieNode.prototype.setKey = function (key) {
  if (this.type !== 'branch') {
    if (Buffer.isBuffer(key)) {
      key = stringToNibbles(key);
    } else {
      key = key.slice(0); // copy the key
    }

    key = addHexPrefix(key, this.type === 'leaf');
    this.raw[0] = nibblesToBuffer(key);
  }
}; // returns the key as a nibble


TrieNode.prototype.getKey = function () {
  if (this.type !== 'branch') {
    var key = this.raw[0];
    key = removeHexPrefix(stringToNibbles(key));
    return key;
  }
};

TrieNode.prototype.serialize = function () {
  return rlpEncode(this.raw);
};

TrieNode.prototype.hash = function () {
  return keccak256(this.serialize());
};

TrieNode.prototype.toString = function () {
  var out = this.type;
  out += ': [';
  this.raw.forEach(function (el) {
    if (Buffer.isBuffer(el)) {
      out += el.toString('hex') + ', ';
    } else if (el) {
      out += 'object, ';
    } else {
      out += 'empty, ';
    }
  });
  out = out.slice(0, -2);
  out += ']';
  return out;
};

TrieNode.prototype.getChildren = function () {
  var children = [];

  switch (this.type) {
    case 'leaf':
      // no children
      break;

    case 'extention':
      // one child
      children.push([this.key, this.getValue()]);
      break;

    case 'branch':
      for (var index = 0, end = 16; index < end; index++) {
        var value = this.getValue(index);

        if (value) {
          children.push([[index], value]);
        }
      }

      break;
  }

  return children;
};


/**
 * @method addHexPrefix
 * @param {Array} dataArr
 * @returns {Buffer} - returns buffer of encoded data
 **/
function addHexPrefix(key, terminator) {
  // odd
  if (key.length % 2) {
    key.unshift(1);
  } else {
    // even
    key.unshift(0);
    key.unshift(0);
  }

  if (terminator) {
    key[0] += 2;
  }

  return key;
}

function removeHexPrefix(val) {
  if (val[0] % 2) {
    val = val.slice(1);
  } else {
    val = val.slice(2);
  }

  return val;
}


/**
 * Determines if a key has Arnold Schwarzenegger in it.
 * @method isTerminator
 * @private
 * @param {Array} key - an hexprefixed array of nibbles
 */
function isTerminator(key) {
  return key[0] > 1;
}


/**
 * Converts a string OR a buffer to a nibble array.
 * @method stringToNibbles
 * @private
 * @param {Buffer| String} key
 */
function stringToNibbles(key) {
  var bkey = Buffer.from(key);
  var nibbles = [];

  for (var i = 0; i < bkey.length; i++) {
    var q = i * 2;
    nibbles[q] = bkey[i] >> 4;
    ++q;
    nibbles[q] = bkey[i] % 16;
  }

  return nibbles;
}


/**
 * Converts a nibble array into a buffer.
 * @method nibblesToBuffer
 * @private
 * @param arr
 */
function nibblesToBuffer(arr) {
  var buf = Buffer.alloc(arr.length / 2);

  for (var i = 0; i < buf.length; i++) {
    var q = i * 2;
    buf[i] = (arr[q] << 4) + arr[++q];
  }

  return buf;
}


/**
 * Determines the node type.
 * @private
 * @returns {String} - the node type
 *   - leaf - if the node is a leaf
 *   - branch - if the node is a branch
 *   - extention - if the node is an extention
 *   - unknown - if something else got borked
 */
function getNodeType(node) {
  if (node.length === 17) {
    return 'branch';
  } else if (node.length === 2) {
    var key = stringToNibbles(node[0]);

    if (isTerminator(key)) {
      return 'leaf';
    }

    return 'extention';
  }
}

function isRawNode(node) {
  return Array.isArray(node) && !Buffer.isBuffer(node);
}




/**
 * Returns the number of in order matching nibbles of two give nibble arrays
 * @method matchingNibbleLength
 * @private
 * @param {Array} nib1
 * @param {Array} nib2
 */
function matchingNibbleLength(nib1, nib2) {
  var i = 0;

  while (nib1[i] === nib2[i] && nib1.length > i) {
    i++;
  }

  return i;
}


/**
 * Is the string a hex string.
 *
 * @method check if string is hex string of specific length
 * @param {String} value
 * @param {Number} length
 * @returns {Boolean} output the string is a hex string
 */
function isHexString(value, length) {
  if (typeof(value) !== 'string' || !value.match(/^0x[0-9A-Fa-f]*$/)) {
    return false;
  }

  if (length && value.length !== 2 + 2 * length) { return false; }

  return true;
}


/**
 * Returns a `Boolean` on whether or not the a `String` starts with '0x'
 * @param {String} str the string input value
 * @return {Boolean} a boolean if it is or is not hex prefixed
 * @throws if the str input is not a string
 */
function isHexPrefixed(str) {
  if (typeof str !== 'string') {
    throw new Error("[is-hex-prefixed] value must be type 'string', is currently type " + (typeof str) + ", while checking isHexPrefixed.");
  }

  return str.slice(0, 2) === '0x';
}


/**
 * Removes '0x' from a given `String` if present
 * @param {String} str the string value
 * @return {String|Optional} a string by pass if necessary
 */
function stripHexPrefix(str) {
  if (typeof str !== 'string') {
    return str;
  }

  return isHexPrefixed(str) ? str.slice(2) : str;
}



/**
 * Converts a `Number` into a hex `String`
 * @param {Number} i
 * @return {String}
 */
function intToHex(i) {
  var hex = i.toString(16); // eslint-disable-line

  return `0x${hex}`;
}

/**
 * Converts an `Number` to a `Buffer`
 * @param {Number} i
 * @return {Buffer}
 */
function intToBuffer(i) {
  const hex = intToHex(i);

  return Buffer.from(padToEven(hex.slice(2)), 'hex');
}


/**
 * Pads a `String` to have an even length
 * @param {String} value
 * @return {String} output
 */
function padToEven(value) {
  var a = value; // eslint-disable-line

  if (typeof a !== 'string') {
    throw new Error(`[ethjs-util] while padding to even, value must be string, is currently ${typeof a}, while padToEven.`);
  }

  if (a.length % 2) {
    a = `0${a}`;
  }

  return a;
}

/**
 * Attempts to turn a value into a `Buffer`. As input it supports `Buffer`, `String`, `Number`, null/undefined, `BN` and other objects with a `toArray()` method.
 * @param v the value
 */
function toBuffer(v) {
    if (!Buffer.isBuffer(v)) {
        if (Array.isArray(v)) {
            v = Buffer.from(v);
        }
        else if (typeof v === 'string') {
            if (isHexString(v)) {
                v = Buffer.from(padToEven(stripHexPrefix(v)), 'hex');
            }
            else {
                v = Buffer.from(v);
            }
        }
        else if (typeof v === 'number') {
            v = intToBuffer(v);
        }
        else if (v === null || v === undefined) {
            v = Buffer.allocUnsafe(0);
        }
        // not importing BN
        /*
        else if (BN.isBN(v)) {
            v = v.toArrayLike(Buffer);
        }
        */
        else if (v.toArray) {
            // converts a BN to a Buffer
            v = Buffer.from(v.toArray());
        }
        else {
            throw new Error('invalid type');
        }
    }
    return v;
};



/**
 * Parse integers. Check if there is no leading zeros
 * @param v The value to parse
 * @param base The base to parse the integer into
 */
function safeParseInt(v, base) {
    if (v.slice(0, 2) === '00') {
        throw new Error('invalid RLP: extra zeros');
    }
    return parseInt(v, base);
}


function encodeLength(len, offset) {
    if (len < 56) {
        return Buffer.from([len + offset]);
    }
    else {
        var hexLength = intToHex(len);
        var lLength = hexLength.length / 2;
        var firstByte = intToHex(offset + 55 + lLength);
        return Buffer.from(firstByte + hexLength, 'hex');
    }
}

/**
 * RLP Encoding based on: https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-RLP
 * This function takes in a data, convert it to buffer if not, and a length for recursion
 * @param input - will be converted to buffer
 * @returns returns buffer of encoded data
 **/
function rlpEncode(input) {
    if (Array.isArray(input)) {
        var output = [];
        for (var i = 0; i < input.length; i++) {
            output.push(rlpEncode(input[i]));
        }
        var buf = Buffer.concat(output);
        return Buffer.concat([encodeLength(buf.length, 192), buf]);
    }
    else {
        var inputBuf = toBuffer(input);
        return inputBuf.length === 1 && inputBuf[0] < 128
            ? inputBuf
            : Buffer.concat([encodeLength(inputBuf.length, 128), inputBuf]);
    }
}

function rlpDecode(input, stream) {
    if (stream === void 0) { stream = false; }
    if (!input || input.length === 0) {
        return Buffer.from([]);
    }
    var inputBuffer = toBuffer(input);
    var decoded = _decode(inputBuffer);
    if (stream) {
        return decoded;
    }
    if (decoded.remainder.length !== 0) {
        throw new Error('invalid remainder');
    }
    return decoded.data;
}

/** Decode an input with RLP */
function _decode(input) {
    var length, llength, data, innerRemainder, d;
    var decoded = [];
    var firstByte = input[0];
    if (firstByte <= 0x7f) {
        // a single byte whose value is in the [0x00, 0x7f] range, that byte is its own RLP encoding.
        return {
            data: input.slice(0, 1),
            remainder: input.slice(1),
        };
    }
    else if (firstByte <= 0xb7) {
        // string is 0-55 bytes long. A single byte with value 0x80 plus the length of the string followed by the string
        // The range of the first byte is [0x80, 0xb7]
        length = firstByte - 0x7f;
        // set 0x80 null to 0
        if (firstByte === 0x80) {
            data = Buffer.from([]);
        }
        else {
            data = input.slice(1, length);
        }
        if (length === 2 && data[0] < 0x80) {
            throw new Error('invalid rlp encoding: byte must be less 0x80');
        }
        return {
            data: data,
            remainder: input.slice(length),
        };
    }
    else if (firstByte <= 0xbf) {
        llength = firstByte - 0xb6;
        length = safeParseInt(input.slice(1, llength).toString('hex'), 16);
        data = input.slice(llength, length + llength);
        if (data.length < length) {
            throw new Error('invalid RLP');
        }
        return {
            data: data,
            remainder: input.slice(length + llength),
        };
    }
    else if (firstByte <= 0xf7) {
        // a list between  0-55 bytes long
        length = firstByte - 0xbf;
        innerRemainder = input.slice(1, length);
        while (innerRemainder.length) {
            d = _decode(innerRemainder);
            decoded.push(d.data);
            innerRemainder = d.remainder;
        }
        return {
            data: decoded,
            remainder: input.slice(length),
        };
    }
    else {
        // a list  over 55 bytes long
        llength = firstByte - 0xf6;
        length = safeParseInt(input.slice(1, llength).toString('hex'), 16);
        var totalLength = llength + length;
        if (totalLength > input.length) {
            throw new Error('invalid rlp: total length is larger than the data');
        }
        innerRemainder = input.slice(llength, totalLength);
        if (innerRemainder.length === 0) {
            throw new Error('invalid rlp, List has a invalid length');
        }
        while (innerRemainder.length) {
            d = _decode(innerRemainder);
            decoded.push(d.data);
            innerRemainder = d.remainder;
        }
        return {
            data: decoded,
            remainder: input.slice(totalLength),
        };
    }
}







/**
 * Verifies a merkle proof for a given key
 * @method verifyProof
 * @param {Buffer} rootHash
 * @param {String} key
 * @param {Array.<TrieNode>} proof
 * @param {Function} cb A callback `Function` (arguments {Error} `err`, {String} `val`)
 */

function verifyProof (rootHash, key, proof, cb) {
  key = stringToNibbles(key);
  var wantHash = toBuffer(rootHash);

  console.log('verifyProof proof array length:', proof.length)
  console.log('verifyProof rootHash:', rootHash.toString('hex'))

  for (var i = 0; i < proof.length; i++) {
    var p = toBuffer(proof[i]);
    var hash = keccak256(proof[i]);

    console.log('verify proof doing elem i: ' + i + '  (size: ' + proof[i].length + ')')
    console.log('wantHash:', wantHash.toString('hex'))
    console.log('hash of elem i:', hash.toString('hex'))

    if (Buffer.compare(hash, wantHash)) {
      throw new Error('Bad proof node ' + i + ': hash mismatch');
    }

    //console.log('calling new TrieNode...')
    var node = new TrieNode(rlpDecode(p));
    console.log('proof elem i='+i+' is node type:', node.type)
    var cld;

    if (node.type === 'branch') {
      if (key.length === 0) {
        if (i !== proof.length - 1) {
          throw new Error('Additional nodes at end of proof (branch)');
        }

        return node.value;
      }

      cld = node.raw[key[0]];
      key = key.slice(1);

      if (cld.length === 2) {
        var embeddedNode = new TrieNode(cld);

        if (i !== proof.length - 1) {
          throw new Error('Additional nodes at end of proof (embeddedNode)');
        }

        if (matchingNibbleLength(embeddedNode.key, key) !== embeddedNode.key.length) {
          throw new Error('Key length does not match with the proof one (embeddedNode)');
        }

        key = key.slice(embeddedNode.key.length);

        if (key.length !== 0) {
          throw new Error('Key does not match with the proof one (embeddedNode)');
        }

        return embeddedNode.value;
      } else {
        wantHash = cld;
      }
    } else if (node.type === 'extention' || node.type === 'leaf') {
      if (matchingNibbleLength(node.key, key) !== node.key.length) {
        throw new Error('Key does not match with the proof one (extention|leaf)');
      }

      cld = node.value;
      key = key.slice(node.key.length);

      if (key.length === 0 || cld.length === 17 && key.length === 1) {
        // The value is in an embedded branch. Extract it.
        if (cld.length === 17) {
          cld = cld[key[0]][1];
          key = key.slice(1);
        }

        if (i !== proof.length - 1) {
          throw new Error('Additional nodes at end of proof (extention|leaf)');
        }

        return cld;
      } else {
        wantHash = cld;
      }
    } else {
      throw new Error('Invalid node type');
    }
  }

  throw new Error('Unexpected end of proof');
};






let root = Buffer.from(proofData.root, 'hex')
let fromWitness = proofData.fromWitness.map(elem => Buffer.from(elem, 'hex'))
let fromAddress = Buffer.from(proofData.fromAddress, 'hex')
let fromAccountLeaf = Buffer.from(proofData.fromAccountLeaf, 'hex')

console.log('verifying proof...')
let val = verifyProof(root, keccak256(fromAddress), fromWitness)

console.log('verifyProof returned val:', val.toString('hex'))
console.log('fromAccountLeaf:', proofData.fromAccountLeaf)

assert(val.equals(fromAccountLeaf), "valid from witness")