merkle-patricia-tree

What is merkle-patricia-tree?

The merkle-patricia-tree npm package is a JavaScript implementation of the Ethereum modified Merkle Patricia Trie. It is used to store key-value pairs in a way that allows for efficient verification of the inclusion and integrity of data. This is particularly useful in blockchain applications where data integrity and proof of inclusion are critical.

What are merkle-patricia-tree's main functionalities?

Creating a Trie

This feature allows you to create a new instance of a Merkle Patricia Trie. The Trie can then be used to store and manage key-value pairs.

const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();

Inserting Data

This feature allows you to insert key-value pairs into the Trie. The keys and values are stored as Buffers.

const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
  if (err) throw err;
  console.log('Data inserted');
});

Retrieving Data

This feature allows you to retrieve the value associated with a given key from the Trie.

const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
  if (err) throw err;
  trie.get(Buffer.from('key1'), (err, value) => {
    if (err) throw err;
    console.log('Retrieved value:', value.toString());
  });
});

Deleting Data

This feature allows you to delete a key-value pair from the Trie.

const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
  if (err) throw err;
  trie.del(Buffer.from('key1'), (err) => {
    if (err) throw err;
    console.log('Data deleted');
  });
});

Proving Inclusion

This feature allows you to create a proof that a particular key-value pair is included in the Trie.

const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
  if (err) throw err;
  trie.createProof(Buffer.from('key1'), (err, proof) => {
    if (err) throw err;
    console.log('Proof:', proof);
  });
});

Other packages similar to merkle-patricia-tree

merkle-tree

The merkle-tree package provides a simple implementation of a Merkle Tree, which is a binary tree used for data verification. Unlike the merkle-patricia-tree, it does not support the Patricia Trie structure, which is more efficient for certain types of key-value storage and retrieval.

merkle

The merkle package is another implementation of a Merkle Tree. It is designed for general-purpose use and does not include the Patricia Trie optimizations found in merkle-patricia-tree. It is simpler but less efficient for large datasets.

merkle-tools

The merkle-tools package provides utilities for creating and managing Merkle Trees. It includes features for creating proofs and verifying data integrity, similar to merkle-patricia-tree, but it does not implement the Patricia Trie structure.

README

#modified merkle patricia tree

This is an implementation of the modified merkle patricia tree as specified in the Ethereum's 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.
- Ethereum's yellow paper

Installation

• npm install merkle-patricia-tree

Usage

var Trie = require('merkle-patricia-tree'),
levelup = require('levelup'),
db = levelup('./testdb'),
trie = new Trie(db); 

trie.put('test', 'one', function () {
  trie.get('test', function (err, value) {
    if(value) console.log(value.toString())
  });
});

API

new new Trie([db], [root])

new Trie([root])

Creates a new Trie object

• db - A instance of levelup or compatiable API. If no db is null or left undefined then the the trie will be stored in memory vai memdown
• root - A hex String or Buffer for the root of a prevously stored trie.

---

Trie Properties

• root - The root of the trie as a Buffer
• isCheckpoint - A Boolean determining if you are saving to a checkpoint or directly to the db
• EMPTY_TRIE_ROOT - A buffer that is a the Root for an empty trie.

---

Trie Methods

trie.put(key, value, cb)

Stores a give value at the give key

• key - the key as a Buffer or String
• value - the value to be stored
• cb - a callback Function which is given the argumnet err - for an errors that may have occured

---

trie.get(key, cb)

Retrieves a value stored at a key

• key - the key as a Buffer or String
• cb - a callback Function which is given the argumnets err - for an errors that may have occured and vlue - The found value in a Buffer or if no value was found null.

---

trie.delete(key, cb)

Removes a value

• key - the key as a Buffer or String
• cb - a callback Function which is given the argumnet err - for an errors that may have occured

---

trie.checkpoint()

Creates a checkpoint that can later be reverted to or commited. After this is called, no changes to the trie will be permanently saved until commit is called.

---

trie.commit(cb)

Commits a checkpoint to the trie

• cb - a callback Function

---

trie.revert()

revets the trie to the state it was at when checkpoint was first called

---

trie.batch(operations)

Give an hash of operation adds them to the DB

• operations a hash of key/values to add to the trie. example

var ops = {
 'dog': 'dogecoin', 
 'cat': 'meow',
 'bird': ''    //delete bird
}

---

trie.deleteState([stateRoot], cb)

Deletes all the nodes of a given stateroot. If no stateroot is given then it will delete the current state.

• cb - a callback Function

---

trie.createReadStream()

returns a read stream. The data event is given an Object hat has two propeties; the key and the value. Both should be Buffers.

examples

see this blog post

Testing

npm test
Test use mocha