https://github.com/ethereumjs/merkle-patricia-tree

SYNOPSIS概要

This is an implementation of the modified merkle patricia tree as specified in the Ethereum's yellow paper.

这是以太坊黄皮书上指定的改良后的merkle patricia树的实现。

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.
- Ethereum's yellow paper

修改后的Merkle Patricia树(前缀树)提供了一个持久的数据结构来映射任意长度的二进制数据(字节数组)。它是根据可变数据结构定义的，以映射256位二进制片段和任意长度的二进制数据。前缀树的核心和协议规范方面的惟一要求是提供一个32字节的值，该值标识给定的一组键-值对。

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

支持的唯一备份存储是通过levelup模块使用的LevelDB

INSTALL安装

npm install merkle-patricia-tree

USAGE使用

Initialization and Basic Usage初始化和基本使用

var Trie = require('merkle-patricia-tree'),

level = require('level'),

db = level('./testdb'),

trie = new Trie(db);

trie.put('test', 'one', function () {

  trie.get('test', function (err, value) {

    if(value) console.log(value.toString())

  });

});

Merkle Proofs Merkle证明

Trie.prove(trie, 'test', function (err, prove) {

  if (err) return cb(err)

  Trie.verifyProof(trie.root, 'test', prove, function (err, value) {

    if (err) return cb(err)

    console.log(value.toString())

    cb()

  })

})

Read stream on Geth DB 读取Geth数据库中的流

var level = require('level')

var Trie = require('./secure')

var stateRoot = "0xd7f8974fb5ac78d9ac099b9ad5018bedc2ce0a72dad1827a1709da30580f0544" // Block #222

var db = level('YOUR_PATH_TO_THE_GETH_CHAIN_DB')

var trie = new Trie(db, stateRoot)

trie.createReadStream()

  .on('data', function (data) {

    console.log(data)

  })

  .on('end', function() {

    console.log('End.')

  })

API

看本博客的ethereumjs/merkle-patricia-tree-2-API

TESTING

npm test

在区块链上使用Merkle-Patricia树存储了四类数据：一个是某个账户中的账户状态的stateRoot值,其key = account.serialize(),value = account state；以及三个前缀树root存储在区块头上的数据：区块链中的state(即整个区块链上所有账户的信息，key = address ,value = account.serialize())；transaction（即整个区块链上所有交易的信息）；transactionReceipt（即整个区块链上所有交易收据的信息）的信息

巴特西

ethereumjs/merkle-patricia-tree-1-简介