README
¶
Merkle Tree in Golang
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
License
This project is licensed under the MIT License.
Documentation
¶
Overview ¶
Package merkletree implements a Merkle Tree capable of storing arbitrary content.
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.
Creating a new merkletree requires that the type that the tree will be constructed from implements the Content interface.
type Content interface {
CalculateHash() []byte
Equals(other Content) bool
}
A slice of the Content items should be created and then passed to the NewTree method.
t, err := merkle.NewTree(list)
t represents the Merkle Tree and can be verified and manipulated with the API methods described below.
Index ¶
- func GetHashStrategies() map[string]hash.Hash
- func NumNodes(node *Node) int
- type Bucket
- type BucketPool
- type ByteContent
- type Content
- type MerkleTree
- func (m *MerkleTree) ExtendTree(cs []Content) error
- func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)
- func (m *MerkleTree) Isempty() bool
- func (m *MerkleTree) RebuildTree() error
- func (m *MerkleTree) RebuildTreeWith(cs []Content) error
- func (m *MerkleTree) String() string
- func (m *MerkleTree) VerifyContent(content Content) (bool, error)
- func (m *MerkleTree) VerifyTree() (bool, error)
- type Node
- type StorageBucket
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GetHashStrategies ¶
GetHashStrategies returns a map which maps the hash strategy name as a string to the corresponding hashing function.
Types ¶
type Bucket ¶
type Bucket struct {
Content *bytes.Buffer
// properties of the bucket
Topic string
// values possibly assigned to the bucket
ID string
// Timestamp is the time, the filled bucket is put into the pool
Timestamp time.Time
// contains filtered or unexported fields
}
Bucket implements Content interface from merkletree package. @Content is a byte slice of fixed size per @Type @ID is a unique identification string @Type designates the category of data (for instance interest rate or trade) @Timestamp is the (Unix-?)time, the container is hashed
func (Bucket) CalculateHash ¶
CalculateHash calculates the hash of a bucket. Is needed for a bucket in order to implement Content from merkle_tree.
func (Bucket) Equals ¶
Equals is true if buckets are identical. Is needed for a bucket in order to implement Content from merkle_tree.
func (*Bucket) WriteContent ¶
WriteContent appends a byte slice to a bucket if there is enough space. Does not write and returns false if there isn't. Contents are separated by leading 64bit unsigned integers.
type BucketPool ¶
type BucketPool struct {
Topic string
// contains filtered or unexported fields
}
BucketPool implements a leaky pool of Buckets in the form of a bounded channel.
func NewBucketPool ¶
func NewBucketPool(maxNum uint64, size uint64, topic string) (bp *BucketPool)
NewBucketPool creates a new BucketPool bounded to the length @maxNum. It is initialized with empty Buckets of capacity @size.
func (*BucketPool) Get ¶
func (bp *BucketPool) Get() (b Bucket, err error)
Get gets a Bucket from the BucketPool, or creates a new one if none are available in the pool.
func (*BucketPool) Len ¶
func (bp *BucketPool) Len() int
Len returns the numbers of elements in the bucket pool
func (*BucketPool) Put ¶
func (bp *BucketPool) Put(b Bucket) bool
Put returns the given Bucket to the BucketPool.
type ByteContent ¶
type ByteContent struct {
Content []byte
}
ByteContent enables one to use (root) hashes as merkletree Content
func (ByteContent) CalculateHash ¶
func (bc ByteContent) CalculateHash() ([]byte, error)
CalculateHash for ByteContent in order to implement Content.
func (ByteContent) Equals ¶
func (bc ByteContent) Equals(other Content) (bool, error)
Equals returns true if two ByteContents are identical, false otherwise
func (ByteContent) MarshalJSON ¶
func (bc ByteContent) MarshalJSON() ([]byte, error)
Custom marshaler for ByteContent type
type Content ¶
Content represents the data that is stored and verified by the tree. A type that implements this interface can be used as an item in the tree.
type MerkleTree ¶
MerkleTree is the container for the tree. It holds a pointer to the root of the tree, a list of pointers to the leaf nodes, and the merkle root.
func ForestToTree ¶
func ForestToTree(trees []MerkleTree) (*MerkleTree, error)
ForestToTree returns a merkle tree made from the root hashes of the trees from @trees
func MakeTree ¶
func MakeTree(bp *BucketPool) (*MerkleTree, error)
MakeTree returns a Merkle tree built from the Buckets in the pool @bp
func NewTree ¶
func NewTree(cs []Content) (*MerkleTree, error)
NewTree creates a new Merkle Tree using the content cs.
func NewTreeWithHashStrategy ¶
func NewTreeWithHashStrategy(cs []Content, hashStrategy string) (*MerkleTree, error)
NewTreeWithHashStrategy creates a new Merkle Tree using the content cs using the provided hash strategy. Note that the hash type used in the type that implements the Content interface must match the hash type provided to the tree.
func (*MerkleTree) ExtendTree ¶
func (m *MerkleTree) ExtendTree(cs []Content) error
ExtendTree extends the merkle tree @m by the content @cs
func (*MerkleTree) GetMerklePath ¶
func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)
GetMerklePath gets Merkle path and indexes (left leaf or right leaf)
func (*MerkleTree) Isempty ¶
func (m *MerkleTree) Isempty() bool
Isempty returns true if merkle tree at @m is empty, false otherwise
func (*MerkleTree) RebuildTree ¶
func (m *MerkleTree) RebuildTree() error
RebuildTree is a helper function that will rebuild the tree reusing only the content that it holds in the leaves.
func (*MerkleTree) RebuildTreeWith ¶
func (m *MerkleTree) RebuildTreeWith(cs []Content) error
RebuildTreeWith replaces the content of the tree and does a complete rebuild; while the root of the tree will be replaced the MerkleTree completely survives this operation. Returns an error if the list of content cs contains no entries.
func (*MerkleTree) String ¶
func (m *MerkleTree) String() string
String returns a string representation of the tree. Only leaf nodes are included in the output.
func (*MerkleTree) VerifyContent ¶
func (m *MerkleTree) VerifyContent(content Content) (bool, error)
VerifyContent indicates whether a given content is in the tree and the hashes are valid for that content. Returns true if the expected Merkle Root is equivalent to the Merkle root calculated on the critical path for a given content. Returns true if valid and false otherwise.
func (*MerkleTree) VerifyTree ¶
func (m *MerkleTree) VerifyTree() (bool, error)
VerifyTree verify tree validates the hashes at each level of the tree and returns true if the resulting hash at the root of the tree matches the resulting root hash; returns false otherwise.
type Node ¶
type Node struct {
Left *Node
Right *Node
Hash []byte
C Content
Dup bool
// contains filtered or unexported fields
}
Node represents a node, root, or leaf in the tree. It stores pointers to its immediate relationships, a hash, the content stored if it is a leaf, and other metadata.
func (*Node) UnmarshalJSON ¶
UnmarshalJSON is a custom unmarshaler for nodes
type StorageBucket ¶
type StorageBucket struct {
Content []byte
// TO DO: make Size dependent on Topic?
Topic string
Size uint64
ID string
Timestamp time.Time
}
StorageBucket is similar to a bucket. In contrast to bucket it is only used for storage in influx and read, not for write.
func DataInStorageTree ¶
func DataInStorageTree(data []byte, tree MerkleTree) (bool, StorageBucket, error)
DataInStorageTree returns true if @data is in a bucket of @tree along with the bucket.
func (StorageBucket) CalculateHash ¶
func (sb StorageBucket) CalculateHash() ([]byte, error)
CalculateHash calculates the hash of a StorageBucket. Is needed for a StorageBucket in order to implement Content from merkle_tree.
func (StorageBucket) Equals ¶
func (sb StorageBucket) Equals(other Content) (bool, error)
Equals is true if StorageBuckets are identical. Is needed for a StorageBucket in order to implement Content from merkle_tree.
func (StorageBucket) MarshalJSON ¶
func (sb StorageBucket) MarshalJSON() ([]byte, error)
Custom marshaler for StorageBucket type
func (*StorageBucket) ReadContent ¶
func (sb *StorageBucket) ReadContent() (data [][]byte, err error)
ReadContent returns the content of a storage bucket. Each byte slice correponds to a marshaled data point such as an interest rate or a trade.
Source Files