1

Given a decoded BlockBodies message, I want to compute the root hash of the transactions trie, so that I can match it against block headers that my node has downloaded.

After reviewing How Ethereum transaction tree is formed and scanning through the source code for go-ethereum, OpenEthereum (nee Parity) and ethereumjs-block, I feel like I'm close — but I'm still not getting the correct result.

Here are the important bits from my code:

const { Transaction } = require('ethereumjs-tx')
const { rlp, toBuffer } = require('ethereumjs-util')
const Trie = require('merkle-patricia-tree')

// Construct a Patricia trie, using each transaction's index as the key, and the
// raw transaction body as the value.
const tree = new Trie()
tree.batch(transactionsRaw.map((t, i) => ({
  type: 'put',
  key: rlp.encode(toBuffer(i)),
  value: new Transaction(t).serialize()
})))

// According to Infura, the transactions trie root for block 9069000 is...
console.log('Expected tx root: 0xcee16501e007fe5240aa50faa96cce60c7de8ae56f34044d850e378b98e04537')
// And this is what my code generates...
console.log(`Actual   tx root: 0x${tree.root.toString('hex')}`)

Here's what I get when I run the code:

Expected tx root: 0xcee16501e007fe5240aa50faa96cce60c7de8ae56f34044d850e378b98e04537
Actual   tx root: 0x8147ebbcffc667ee12746a2154299728a46435f4078d2f6f8b113e34f2758c6b

I have verified that transactionsRaw contains the correct data by unserialising each transaction and comparing their hashes against Infura.

I feel like I'm just putting the wrong keys/values into the trie, but I can't find any examples, and comparing hashes doesn't exactly provide a whole lot of feedback

What am I doing wrong here?

todofixthis
  • 131
  • 6

1 Answers1

2

After reviewing how ethereumjs-block:Block.genTxTrie() does it, I managed to figure it out:

const trie = new Trie()
await Promise.all(transactionsRaw.map((t, i) =>
  new Promise(resolve => {
    trie.put(
      rlp.encode(i),
      new Transaction(t).serialize(),
      resolve
    )
  })
))

or

const trie = new Trie()

const put = util.promisify(trie.put.bind(trie))
await Promise.all(transactionsRaw.map((t, i) =>
  put(rlp.encode(i), new Transaction(t).serialize())
))

And it works 

Expected tx root: 0xcee16501e007fe5240aa50faa96cce60c7de8ae56f34044d850e378b98e04537
Actual   tx root: 0xcee16501e007fe5240aa50faa96cce60c7de8ae56f34044d850e378b98e04537

The reason why merkle-patricia-tree:BaseTrie.batch() was getting the wrong result is because that method only operates on the underlying LevelDB instance, not the actual patricia trie!

todofixthis
  • 131
  • 6