A Merkle Tree implementation written in Go.

Merkle Tree in Golang

Build Report Docs Version

An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with.

At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case.

Documentation

See the docs here.

Install

go get github.com/cbergoon/merkletree

Example Usage

Below is an example that makes use of the entire API - its quite small.

package main

import (
  "crypto/sha256"
  "log"

  "github.com/cbergoon/merkletree"
)

//TestContent implements the Content interface provided by merkletree and represents the content stored in the tree.
type TestContent struct {
  x string
}

//CalculateHash hashes the values of a TestContent
func (t TestContent) CalculateHash() ([]byte, error) {
  h := sha256.New()
  if _, err := h.Write([]byte(t.x)); err != nil {
    return nil, err
  }

  return h.Sum(nil), nil
}

//Equals tests for equality of two Contents
func (t TestContent) Equals(other merkletree.Content) (bool, error) {
  return t.x == other.(TestContent).x, nil
}

func main() {
  //Build list of Content to build tree
  var list []merkletree.Content
  list = append(list, TestContent{x: "Hello"})
  list = append(list, TestContent{x: "Hi"})
  list = append(list, TestContent{x: "Hey"})
  list = append(list, TestContent{x: "Hola"})

  //Create a new Merkle Tree from the list of Content
  t, err := merkletree.NewTree(list)
  if err != nil {
    log.Fatal(err)
  }

  //Get the Merkle Root of the tree
  mr := t.MerkleRoot()
  log.Println(mr)

  //Verify the entire tree (hashes for each node) is valid
  vt, err := t.VerifyTree()
  if err != nil {
    log.Fatal(err)
  }
  log.Println("Verify Tree: ", vt)

  //Verify a specific content in in the tree
  vc, err := t.VerifyContent(list[0])
  if err != nil {
    log.Fatal(err)
  }

  log.Println("Verify Content: ", vc)

  //String representation
  log.Println(t)
}

Sample

merkletree

License

This project is licensed under the MIT License.

Comments
  • OutOfRange error on node length 13

    OutOfRange error on node length 13

    Hi,

    Just got a runtime error (Index out of range) on the node length 13

    I tried to use this on a node list of 208 separate content elements, it got stuck at trying to calculate a list of 13 nodes. I then tried adding a list of 13 nodes to the test case (copy-paste in the original tests) and got the same error.

    ~/workspace/go/src/github.com/cbergoon/merkletree [master] $ go test merkle_tree_test.go merkle_tree.go
    --- FAIL: TestNewTree (0.00s)
    panic: runtime error: index out of range [recovered]
    	panic: runtime error: index out of range
    
    goroutine 5 [running]:
    testing.tRunner.func1(0xc42009a0f0)
    	/usr/local/go/src/testing/testing.go:711 +0x2d2
    panic(0x1119540, 0x11e5950)
    	/usr/local/go/src/runtime/panic.go:491 +0x283
    command-line-arguments.buildIntermediate(0xc420058740, 0x7, 0x8, 0x0)
    	~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:104 +0x50f
    command-line-arguments.buildIntermediate(0xc42009c100, 0xe, 0x10, 0x20)
    	~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:118 +0x4e6
    command-line-arguments.buildWithContent(0x11e9e20, 0xd, 0xd, 0xc4200864b0, 0xc42000a0c0, 0x4, 0x4, 0x0, 0x0)
    	~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:94 +0x2ff
    command-line-arguments.NewTree(0x11e9e20, 0xd, 0xd, 0x11d5d20, 0x20, 0x20)
    	~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:63 +0x4c
    command-line-arguments.TestNewTree(0xc42009a0f0)
    	~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree_test.go:112 +0x86
    testing.tRunner(0xc42009a0f0, 0x1146248)
    	/usr/local/go/src/testing/testing.go:746 +0xd0
    created by testing.(*T).Run
    	/usr/local/go/src/testing/testing.go:789 +0x2de
    FAIL	command-line-arguments	0.010s
    

    Would be a good idea to check for this case.

  • code typo

    code typo

    There is a typo in line 127 of merkle_tree.go. https://github.com/cbergoon/merkletree/blob/master/merkle_tree.go#L127

    code

    if bytes.Equal(currentParent.Left.Hash, current.Hash) {
    

    should be

    if bytes.Equal(currentParent.Right.Hash, current.Hash) {
    

    (sorry I cannot make a pull request)

  • Allow a configurable hash function

    Allow a configurable hash function

    I was wondering if you would be open to supporting a configurable hash function.

    In other words pass the hash function as an argument along with the content list when building the tree. Something like:

    merkle.NewTree(list, sha256.New)

  • Useless parameter in VerifyContent

    Useless parameter in VerifyContent

    Hello,

    expectedMerkleRoot parameter is unused in the code.

    https://github.com/cbergoon/merkletree/blob/0e68ec9a138d919b3052ba7cfea5f0a63630cdfe/merkle_tree.go#L179

  • support merklebtree

    support merklebtree

    #8

    Why not use google/btree

    The structure of node in google/btree doesn't have parent pointer

    https://github.com/google/btree/blob/be84af90a1f71c9eeac820a4cdacb863122396d6/btree.go#L244-L248

    type node struct { 
     	items    items 
     	children children 
     	cow      *copyOnWriteContext 
     } 
    

    google/btree use copyOnWriteContext whick will make it difficlut.

    emirpasic/gods/btree

    So I use emirpasic/gods/btree and modify the

    // Node is a single element within the tree
    type Node struct {
    	Parent   *Node
    	Entries  []*Entry // Contained keys in node
    	Children []*Node  // Children nodes
    }
    
    // Entry represents the key-value pair contained within nodes
    type Entry struct {
    	Key   interface{}
    	Value interface{}
    }
    

    to

    // Node is a single element within the tree
    type Node struct {
    	Parent   *Node
    	Contents []*Content // Contained keys in node
    	Children []*Node    // Children nodes
    }
    
    type Content interface {
    	// Less tests whether the current item is less than the given argument.
    
    	// If a.Comparator(b) return
    	// negative , if a < b
    	// zero     , if a == b
    	// positive , if a > b
    	Comparator(than Content) int
    }
    

    testcase

    === RUN   TestBTreeGet1
    --- PASS: TestBTreeGet1 (0.00s)
    === RUN   TestBTreeGet2
    --- PASS: TestBTreeGet2 (0.00s)
    === RUN   TestBTreePut1
    --- PASS: TestBTreePut1 (0.00s)
    === RUN   TestBTreePut2
    --- PASS: TestBTreePut2 (0.00s)
    === RUN   TestBTreePut3
    --- PASS: TestBTreePut3 (0.00s)
    === RUN   TestBTreePut4
    --- PASS: TestBTreePut4 (0.00s)
    === RUN   TestBTreeRemove1
    --- PASS: TestBTreeRemove1 (0.00s)
    === RUN   TestBTreeRemove2
    --- PASS: TestBTreeRemove2 (0.00s)
    === RUN   TestBTreeRemove3
    --- PASS: TestBTreeRemove3 (0.00s)
    === RUN   TestBTreeRemove4
    --- PASS: TestBTreeRemove4 (0.00s)
    === RUN   TestBTreeRemove5
    --- PASS: TestBTreeRemove5 (0.00s)
    === RUN   TestBTreeRemove6
    --- PASS: TestBTreeRemove6 (0.00s)
    === RUN   TestBTreeRemove7
    --- PASS: TestBTreeRemove7 (0.00s)
    === RUN   TestBTreeRemove8
    --- PASS: TestBTreeRemove8 (0.00s)
    === RUN   TestBTreeRemove9
    --- PASS: TestBTreeRemove9 (0.05s)
    === RUN   TestBTreeHeight
    --- PASS: TestBTreeHeight (0.00s)
    === RUN   TestBTreeLeftAndRight
    --- PASS: TestBTreeLeftAndRight (0.00s)
    === RUN   TestBTreeIteratorValuesAndKeys
    --- PASS: TestBTreeIteratorValuesAndKeys (0.00s)
    === RUN   TestBTreeIteratorNextOnEmpty
    --- PASS: TestBTreeIteratorNextOnEmpty (0.00s)
    === RUN   TestBTreeIteratorPrevOnEmpty
    --- PASS: TestBTreeIteratorPrevOnEmpty (0.00s)
    === RUN   TestBTreeIterator1Next
    --- PASS: TestBTreeIterator1Next (0.00s)
    === RUN   TestBTreeIterator1Prev
    --- PASS: TestBTreeIterator1Prev (0.00s)
    === RUN   TestBTreeIterator2Next
    --- PASS: TestBTreeIterator2Next (0.00s)
    === RUN   TestBTreeIterator2Prev
    --- PASS: TestBTreeIterator2Prev (0.00s)
    === RUN   TestBTreeIterator3Next
    --- PASS: TestBTreeIterator3Next (0.00s)
    === RUN   TestBTreeIterator3Prev
    --- PASS: TestBTreeIterator3Prev (0.00s)
    === RUN   TestBTreeIterator4Next
    --- PASS: TestBTreeIterator4Next (0.00s)
    === RUN   TestBTreeIterator4Prev
    --- PASS: TestBTreeIterator4Prev (0.00s)
    === RUN   TestBTreeIteratorBegin
    --- PASS: TestBTreeIteratorBegin (0.00s)
    === RUN   TestBTreeIteratorEnd
    --- PASS: TestBTreeIteratorEnd (0.00s)
    === RUN   TestBTreeIteratorFirst
    --- PASS: TestBTreeIteratorFirst (0.00s)
    === RUN   TestBTreeIteratorLast
    --- PASS: TestBTreeIteratorLast (0.00s)
    === RUN   TestBTree_search
    --- PASS: TestBTree_search (0.00s)
    PASS
    coverage: 94.2% of statements in ../../merkletree/...
    
  • Unhandled err

    Unhandled err

    https://github.com/cbergoon/merkletree/blob/0e68ec9a138d919b3052ba7cfea5f0a63630cdfe/merkle_tree.go#L47

    The hash writer is an io.Writer. The write method of the io.Writer returns the number of bytes written and an error: Write(p []byte) (n int, err error). These errors are not being handled in your code when you do h.Write(...)

    I would suggest changing all instances of h.Write(...) to:

    if _, err := h.Write(...); err != nil {
      return .., err
    }
    
  • Fork Merkle Tree Library / change to SHA3 - 256

    Fork Merkle Tree Library / change to SHA3 - 256

    Description

    1. Update docs to redirect to our fork
    2. Changed sha256.New() to sha3.New256()
    3. Changed the expected values in the merkle_tree_test.go files to support the new crypt format SHA3-256

    How to test

    • Type the following command line
    $~ go test ./...
    

    Expected result

    ok      github.com/cbergoon/merkletree
    

    Checklist

    • [x] Code compiles and pass all tests
    • [x] No linter warnings (golangci-lint)
    • [x] Created new Updated tests that fail without these changes
    • [x] Updated README.md and/or the documentation
    • [ ] Updated AUTHORS file (bash -c scripts/update-authors.sh)
  • Fix Odd Node Len on Intermediate Layer

    Fix Odd Node Len on Intermediate Layer

    Fixes an issue when there is an odd number of nodes on an intermediate layer. Also includes a small change to create a deep copy of duplicated nodes if the number of original elements is odd.

    Fixes #1

  • What if the leaves has the same content?

    What if the leaves has the same content?

    Hi, I have seen this two method: https://github.com/cbergoon/merkletree/blob/master/merkle_tree.go#L115 https://github.com/cbergoon/merkletree/blob/master/merkle_tree.go#L265 What if we have same contents in two different leaves? Will it result in the wrong result?

  • Is this a self-balancing Merkle Tree?

    Is this a self-balancing Merkle Tree?

    Sorry I'm kind of mixed up what is the current standard Bitcoin Merkle Tree implementation, and what are like "research efforts" or evolving projects? . From here https://codetrips.com/2020/08/02/modern-c-implementing-a-merkle-tree/ It's stated

    Rather obviously, this results in a highly unbalanced tree: however, as the purpose of a MerkleTree is to hold data and ensure its validity against tampering or computation errors (and not, for example, search efficiency) this is a very convenient trade-off: re-balancing the tree after each (or even several) addition would require recomputing almost all of the nodes’ hashes (apart from the leaf nodes, which remain unchanged); given that this would likely require many cryptographic operations (which are notoriously CPU intensive) it would be a rather poor trade-off.

    -and this project from 2018 is entitled "self-balancing"? https://github.com/sputnik1458/merkle-tree

    -How do you implement "add leaf" in here?

    2-second Q: All these implementations r for full nodes right?Did things got mixed in my mind, or there r no deletes in a full node Merkle Tree? In other words, do u have a "delete leaf" in ur implementation?If so how it works?

  • Why does the node contain content?

    Why does the node contain content?

    Hi, wonderful library!

    I have one doubt about the implementation. Why do the leaf nodes contain data? https://github.com/cbergoon/merkletree/blob/master/merkle_tree.go#L40

    I was of the understanding that Merkle Tree only contains hash of data in its leafs - to separate the data from proofs. Are there multiple variations of the concept?

    Good job with the lib again @cbergoon!

  • Added optional sorting before each sibling hashing

    Added optional sorting before each sibling hashing

    I was using this library and wanted to make it work with a popular Ethereum framework called OpenZeppelin

    Unfortunately their Merkle Proof verification expects for each hashed sibling pair to have been ordered before (here). Not a very good idea since merkiling A and B becomes the same as B and A. But since it is a very popular library for Ethereum thought this pull request might be acceptable.

    (maybe more test would be good from my part)

    I preferred to create a new method instead of deleting an already known one, but it is only one more argument.

Exp-tree: go library for parsing expression tree

Vinshop expression tree Exp-tree is go library for parsing expression tree Installation go get -u github.com/vinshop/exp-tree Quick start Format Expre

May 11, 2022
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Nov 3, 2022
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Apr 25, 2022
An R-tree implementation for Go
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Dec 29, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

Dec 29, 2022
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Dec 31, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

Mar 7, 2022
A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees

radixs A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees. This implemen

Feb 14, 2022
An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

Jul 1, 2022
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

Mar 23, 2022
Mmpxmas-go - ModMyPi Programmable Christmas Tree examples written in Go with go-rpio

ModMyPi Programmable Christmas Tree examples in Go This small program contains examples similar to the examples provided by ModMyPi for interacting wi

Jan 4, 2022
A tree like tool help you to explore data structures in your redis server
 A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

Mar 17, 2022
an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Jan 3, 2023
Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Dec 25, 2022
Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Oct 6, 2021
Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

May 17, 2022
Golang channel example with equivalent binary tree
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

Oct 9, 2021
Segment tree for bytes in Go

bsegtree Segment tree for bytes in Go Based on Thomas Oberndörfer's int range segment tree with fixing/optimization/modification for bytes ranges. For

Jun 16, 2022
A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

Nov 1, 2021