# Merkle-Patricia-tree

A Merkle Patricia Tree* is the combination of a:

* Patricia Trie: An efficient Radix Trie, a data structure in which "keys" represent the path one has to take to reach a node
* Merkle Tree: A hash tree in which each node's hash is computed from its child nodes hashes.

This is an implementation of the modified merkle patricia tree as specified in the Ethereum [Yellow Paper](https://drive.google.com/file/d/1CJWmxV9kq5iwaTiPxCrBYPq0ED_bwMu4/view?usp=drivesdk):
> The modified Merkle Patricia tree (trie) provides a persistent data structure to map between arbitrary-length binary data (byte arrays). It is defined in terms of a mutable data structure to map between 256-bit binary fragments and arbitrary-length binary data. The core of the trie, and its sole requirement in terms of the protocol specification is to provide a single 32-byte value that identifies a given set of key-value pairs.

#### Install

npm install merkle-patricia-tree

#### Usage

There are 3 variants of the tree implemented in this library, namely: `BaseTrie`, `CheckpointTrie`and`SecureTrie`.`CheckpointTrie` adds checkpointing functionality to the `BaseTrie` with the methods `checkpoint`,`commit` and `revert`.`SecureTrie` extends `CheckpointTrie` and is the most suitable variant for Ethereum applications. It stores values under the `keccsk256` hash of their keys.

###### Initialization and Basic Usage

import level from 'level'
import { BaseTrie as Trie } from 'merkle-patricia-tree'

const db = level('./testdb')
const trie = new Trie(db)

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  const value = await trie.get(Buffer.from('test'))
  console.log(value.toString()) // 'one'
}

test()

###### Merkle Proofs

const trie = new Trie()

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  const proof = await Trie.createProof(trie, Buffer.from('test'))
  const value = await Trie.verifyProof(trie.root, Buffer.from('test'), proof)
  console.log(value.toString()) // 'one'
}

test()

###### Read stream on Geth DB

import level from 'level'
import { SecureTrie as Trie } from 'merkle-patricia-tree'

const db = level('YOUR_PATH_TO_THE_GETH_CHAIN_DB')
// Set stateRoot to block #222
const stateRoot = '0xd7f8974fb5ac78d9ac099b9ad5018bedc2ce0a72dad1827a1709da30580f0544'
// Initialize trie
const trie = new Trie(db, stateRoot)

trie
  .createReadStream()
  .on('data', console.log)
  .on('end', () => {
    console.log('End.')
  })

###### Read Account State including Storage from Geth DB

import level from 'level'
import rlp from 'rlp'
import { BN, bufferToHex } from 'ethereumjs-util'
import Account from 'ethereumjs-account'
import { SecureTrie as Trie } from 'merkle-patricia-tree'

const stateRoot = 'STATE_ROOT_OF_A_BLOCK'

const db = level('YOUR_PATH_TO_THE_GETH_CHAINDATA_FOLDER')
const trie = new Trie(db, stateRoot)

const address = 'AN_ETHEREUM_ACCOUNT_ADDRESS'

async function test() {
  const data = await trie.get(address)
  const acc = new Account(data)

  console.log('-------State-------')
  console.log(`nonce: ${new BN(acc.nonce)}`)
  console.log(`balance in wei: ${new BN(acc.balance)}`)
  console.log(`storageRoot: ${bufferToHex(acc.stateRoot)}`)
  console.log(`codeHash: ${bufferToHex(acc.codeHash)}`)

  let storageTrie = trie.copy()
  storageTrie.root = acc.stateRoot

  console.log('------Storage------')
  const stream = storageTrie.createReadStream()
  stream
    .on('data', (data) => {
      console.log(`key: ${bufferToHex(data.key)}`)
      console.log(`Value: ${bufferToHex(rlp.decode(data.value))}`)
    })
    .on('end', () => {
      console.log('Finished reading storage.')
    })
}

test()

for more resources you can check [rockwaterweb blog](https://rockwaterweb.com/ethereum-merkle-patricia-trees-javascript-tutorial/)