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?

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!

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.