• This repository has been archived on 19/Jan/2021
  • Stars
    star
    305
  • Rank 131,617 (Top 3 %)
  • Language
    TypeScript
  • Created almost 10 years ago
  • Updated over 3 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Project is in active development and has been moved to the EthereumJS VM monorepo.

SYNOPSIS

NPM Status Actions Status Coverage Status Discord

This is an implementation of the modified merkle patricia tree as specified in the Ethereum Yellow Paper:

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.

The only backing store supported is LevelDB through the levelup module.

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 keccak256 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()

Additional examples with detailed explanations are available here.

API

Documentation

TESTING

npm test

BENCHMARKS

There are two simple benchmarks in the benchmarks folder:

  • random.ts runs random PUT operations on the tree.
  • checkpointing.ts runs checkpoints and commits between PUT operations.

A third benchmark using mainnet data to simulate real load is also under consideration.

Benchmarks can be run with:

npm run benchmarks

To run a profiler on the random.ts benchmark and generate a flamegraph with 0x you can use:

npm run profiling

0x processes the stacks and generates a profile folder (<pid>.0x) containing flamegraph.html.

REFERENCES

EthereumJS

See our organizational documentation for an introduction to EthereumJS as well as information on current standards and best practices.

If you want to join for work or do improvements on the libraries have a look at our contribution guidelines.

LICENSE

MPL-2.0

More Repositories

1

ethereumjs-monorepo

Monorepo for the Ethereum VM TypeScript Implementation
TypeScript
2,397
star
2

ethereumjs-wallet

Utilities for handling Ethereum keys
TypeScript
966
star
3

ethereumjs-tx

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
779
star
4

keythereum

Create, import and export Ethereum keys
JavaScript
602
star
5

ethereumjs-util

Project is in active development and has been moved to the EthereumJS monorepo.
TypeScript
601
star
6

ethereumjs-lib

[DEPRECATED] A JavaScript library of core Ethereum functions
442
star
7

ethereumjs-abi

[DEPRECATED] Decoder and encoder for the Ethereum ABI
JavaScript
294
star
8

ethereumjs-client

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
192
star
9

ethereumjs-devp2p

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
140
star
10

ethereumjs-blockchain

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
120
star
11

rlp

Project is in active development and has been moved to the EthereumJS monorepo.
TypeScript
120
star
12

ethrpc

Maximal RPC wrapper
JavaScript
109
star
13

ultralight

Ethereum Portal Network TypeScript implementation
HTML
87
star
14

ethereumjs-blockstream

Reliable stream of Ethereum blocks
TypeScript
80
star
15

helpeth

Help (with) Ethereum. Purists' commandline tool for key and transaction management.
JavaScript
75
star
16

browser-builds

[DEPRECATED] Browser builds of ethereumjs libraries.
JavaScript
59
star
17

node-blockchain-server

[DEPRECATED] A simple blockchain server (downloads block and serves them, doesn't do state transitions)
57
star
18

ethashjs

Project is in active development and has been moved to the EthereumJS VM monorepo.
JavaScript
56
star
19

ethereumjs-account

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
44
star
20

geth.js

Start and stop geth from Node.js
JavaScript
44
star
21

ethereumjs-block

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
42
star
22

ethereumjs-units

Ethereum unit conversion.
JavaScript
41
star
23

ethereumjs-connect

[DEPRECATED] Basic Ethereum connection tasks
JavaScript
36
star
24

eth-query

minimal rpc wrapper
JavaScript
28
star
25

node-devp2p

[DEPRECATED] A node.js implementation of the RLPx transport
28
star
26

ethereumjs-common

Project is in active development and has been moved to the EthereumJS VM monorepo.
TypeScript
26
star
27

rustbn.js

Rust to Javascript/Webassembly compilation of ethereum-bn128.rs.
HTML
19
star
28

node-devp2p-dpt

[DEPRECATED] Ethereum Distubted Peer Table Implementation
15
star
29

ethereumjs-ledger

[DEPRECATED] A wrapper library around the Ledger line of devices that attempts to simplify usage and handle various failure modes/problems.
TypeScript
14
star
30

ethereumjs-icap

Utilities for handling ICAP (Ethereum in IBAN) encoding
JavaScript
14
star
31

eth-bin-to-ops

[DEPRECATED] Simple utility for parsing binary evm code into opcodes
JavaScript
13
star
32

ethereum-verified-contracts

[DEPRECATED] Ethereum Verified Contracts
JavaScript
12
star
33

organization

A repo for discussions and other non-code organizing stuff
11
star
34

ethereumjs-testing

This utility library has been moved to the EthereumJS VM monorepo.
JavaScript
11
star
35

ethereumjs.github.io

Website for an intro to the EthereumJS ecosystem
CSS
10
star
36

ethereumjs-stub-rpc-server

Stub Ethereum JSON-RPC Server
JavaScript
9
star
37

node-ethash

Node bindings for the C++ Ethash implementation.
C++
7
star
38

fixed-bn.js

a bn.js wrapper that constrains numbers to a fixed width
TypeScript
7
star
39

ethereumjs-config

[DEPRECATED] Configuration is now added within a config folder of the EthereumJS monorepo
Shell
4
star
40

node-devp2p-eth

[DEPRECATED] Ethereum wire protocol implementation
3
star
41

sharding

Serenity phase 2 shard-chain PoC
WebAssembly
2
star
42

eth-bin-to-method-ids

[DEPRECATED] Extract the four byte method ids from evm byte code
JavaScript
2
star
43

rustbn-wasm

TypeScript
1
star
44

ethereumjs-collation

[DEPRECATED] Implementation of an Ethereum sharding collation
JavaScript
1
star
45

node-devp2p-rlpx

[DEPRECATED] Implements RLPx
1
star