Skip to content

Instantly share code, notes, and snippets.

@cdetrio
Created July 11, 2019 14:53
Show Gist options
  • Save cdetrio/1f477bdb4c5d41740c45f62aaa09dd5b to your computer and use it in GitHub Desktop.
Save cdetrio/1f477bdb4c5d41740c45f62aaa09dd5b to your computer and use it in GitHub Desktop.
starter pack: merkle-patricia-trie proof verifier

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
// 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))
/**
* 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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment