Skip to content
/ mpt Public

Simple Implementation of Modified Merkle Patricia Tries

Notifications You must be signed in to change notification settings

begmaroman/mpt

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

25 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

MPT - Modified Merkle Patricia Tries

Simple implementation of Modified Merkle Patricia Tries on GoLang.

Modified Merkle Patricia Trie

Usage

  1. Create the Trie:

    • With empty root node:
    trie := mpt.NewEmptyTrie()
    • With branch root node:
    nd := node.NewBranchNode()
    trie := mpt.NewTrie(nd)
    • With extension root node:
    nd := node.NewExtensionNode(nil, nil)
    trie := mpt.NewTrie(nd)
  2. Add key/value pair:

key := []byte("key")
val := []byte("val")

// create new trie and try add key/value pair
trie := mpt.NewEmptyTrie()
if ok := trie.Put(key, val); !ok {
	// key/pair not added
}
  1. Get data by key:
key := []byte("key")
val := []byte("val")

// create new trie and try add key/value pair
trie := mpt.NewEmptyTrie()
if ok := trie.Put(key, val); !ok {
	// key/pair not added
}

// some logic...

// try to get data by key
getVal, ok := trie.Get(key)
if !ok {
	// key/pair not added
}
  1. Update data by key:
// initialize data
key := []byte("key")
val := []byte("val")

// create new trie and try add key/value pair
trie := mpt.NewEmptyTrie()
if ok := trie.Put(key, val); !ok {
	// key/pair not added
}

// some logic...

// try to update value by key
newVal := []byte("updated value")
if ok := trie.Update(key, newVal); !ok {
	// data not updated
}
  1. Delete data by key:
// initialize data
key := []byte("key")
val := []byte("val")

// create new trie and try add key/value pair
trie := mpt.NewEmptyTrie()
if ok := trie.Put(key, val); !ok {
	// key/pair not added
}

// some logic...

// try to delete data by key
if ok := trie.Delete(key, newVal); !ok {
	// data not deleted
}
  1. Get hash of the trie:
// initialize data
key := []byte("key")
val := []byte("val")

// create new trie and try add key/value pair
trie := mpt.NewEmptyTrie()
if ok := trie.Put(key, val); !ok {
	// key/pair not added
}

// some logic...

// try to get hash of the trie
h, err := trie.Hash()
if err != nil {
	// error while hash calculation
}

fmt.Println("hash of the trie:", h)

Benchmarks

Name Iterations Time Description
BenchmarkTrie_Get/FromFullTrie100000-4 1000000 3463 ns/op Get data from the tree which have 100000 key/value pairs
BenchmarkTrie_Get/FromEmptyTrie-4 1000000 1262 ns/op Get data from the empty tree
BenchmarkTrie_Put/ToFullTrie100000-4 3000000 513 ns/op Put data to the tree which have 100000 key/value pairs
BenchmarkTrie_Put/ToEmptyTrie-4 3000000 524 ns/op Put data to empty tree
BenchmarkTrie_Update/FullTrie100000-4 1000000 3083 ns/op Update data in the tree which have 100000 key/value pairs
BenchmarkTrie_Update/EmptyTrie-4 2000000 674 ns/op Update data in empty tree

Backlog

  • Implement Database layer - need for store tree

Releases

No releases published

Packages

No packages published

Languages