go-merkle-tree: github.com/keybase/go-merkle-tree Index | Examples | Files

package merkleTree

import "github.com/keybase/go-merkle-tree"

Package merkleTree is a generic Merkle Tree implementation, for provably publishing lots of data under one succinct tree root.


go get github.com/keybase/go-merkle-tree


This package outputs a MerkleTree with two types of nodes: interior index nodes, or iNodes, and exterior data nodes, of Leaf nodes. The inodes consist of tables that map prefixes to child pointers. The leafs map a full hash to a "value".

This is best demonstrated with a simple example. Let's say you are storing the key-value pair (`0123456789abcdef`, {"name" : "max"}) in the Merkle tree. Let's say that the shape of the tree is to have 256 children per inode. Then this key-value pair might be stored under the path

at root     node: 01 → aabbccdd
at aabbccdd node: 23 → eeff5588
at eeff5588 node: 34 → 99331122
at 99331122 node: 0123456789abcdef → {"name" : "max" }

Meaning at the root node, we take the first 256-bits of the needed key to get a prefix `01`, and look that up in the node's pointer table to get a child pointer, which is `aabbccdd`. This is a hash of an iNode, which we can fetch from storage, verify it matches the hash, and then recursively apply the same algorithm to find the next step in the path. The leaf node has a sparse table of long-hashes (which are the keys) that map to the values actually stored in the tree.


All nodes are encoded with msgpack before being hashed or written to store. See `types.go` for the exactly layout of the msgpack objects.


To construct a new Tree from scratch, you need to specify three parameters:

- A Config, which specifies the shape of the Tree. That is,
  how many children per interior Node, and how big leaves
  can get before a new level of the tree is introduced. Also,
  the hash function to use for hashing nodes into pointers.

- A StorageEngine, which determines how to load and store tree Nodes
  from storage, and how to load and store the root hash of the Merkle tree.

- An array of KeyValuePairs, the things actually stored in the Merkle tree.



Package Files

bitslice.go config.go doc.go errors.go hash.go inode.go interfaces.go mem.go msgpack.go node.go sorted_map.go tree.go types.go


var ErrBadINode = errors.New("Bad iNode found")

ErrBadINode is thrown when we find a corrupt/malformed iNode

type BadChildPointerError Uses

type BadChildPointerError struct {
    V interface{}

BadChildPointerError is thrown when the types of an interior node are not pointers to children.

func (BadChildPointerError) Error Uses

func (b BadChildPointerError) Error() string

type ChildIndex Uses

type ChildIndex uint32

ChildIndex specifies one of an iNode's child nodes.

type Config Uses

type Config struct {
    // contains filtered or unexported fields

Config defines the shape of the MerkleTree.

func NewConfig Uses

func NewConfig(h Hasher, m ChildIndex, n ChildIndex, v ValueConstructor) Config

NewConfig makes a new config object. Pass it a Hasher (though we suggest sha512.Sum512); a parameter `m` which is the number of children per interior node (we recommend 256), and `n`, the maximum number of entries in a leaf before a new level of the tree is introduced.

func (Config) PrefixAndIndexAtLevel Uses

func (c Config) PrefixAndIndexAtLevel(level Level, h Hash) (Prefix, ChildIndex)

func (Config) PrefixAtLevel Uses

func (c Config) PrefixAtLevel(level Level, h Hash) Prefix

type Hash Uses

type Hash []byte

Hash is a byte-array, used to represent a full collision-resistant hash.

func (Hash) Eq Uses

func (h Hash) Eq(h2 Hash) bool

Eq determines if the two hashes are equal.

func (Hash) Len Uses

func (h Hash) Len() int

Len returns the number of bytes in the hash, but after shifting off leading 0s from the length size of the hash

func (Hash) Less Uses

func (h Hash) Less(h2 Hash) bool

Less determines if the receiver is less than the arg, after shifting off all leading 0 bytes and using big-endian byte ordering.

func (Hash) MarshalJSON Uses

func (h Hash) MarshalJSON() ([]byte, error)

MarshalJSON prints out a hash for debugging purposes. Not recommended for actual JSONing

type HashMismatchError Uses

type HashMismatchError struct {
    H Hash

HashMismatchError is raised when a value fails to match its hash key.

func (HashMismatchError) Error Uses

func (h HashMismatchError) Error() string

type Hasher Uses

type Hasher interface {
    Hash([]byte) Hash

Hasher is an interface for hashing MerkleTree data structures into their cryptographic hashes.

type KeyValuePair Uses

type KeyValuePair struct {
    Key   Hash        `codec:"k"`
    Value interface{} `codec:"v"`
    // contains filtered or unexported fields

KeyValuePair is something inserted into the merkle tree. The key can be something like a UID or a TLF ID. The Value is a generic interface, so you can store anything there, as long as it obeys Msgpack-decoding behavior.

Note that though the key is of type `Hash`, it can be a smaller or different hash from the one used for interior nodes.

type Level Uses

type Level uint

Level specifies what level of the merkle tree we are at.

type MemEngine Uses

type MemEngine struct {
    // contains filtered or unexported fields

MemEngine is an in-memory MerkleTree engine, used now mainly for testing

func NewMemEngine Uses

func NewMemEngine() *MemEngine

NewMemEngine makes an in-memory storage engine, mainly for testing.

func (*MemEngine) CommitRoot Uses

func (m *MemEngine) CommitRoot(_ context.Context, prev Hash, curr Hash, txinfo TxInfo) error

CommitRoot "commits" the root ot the blessed memory slot

func (*MemEngine) Hash Uses

func (m *MemEngine) Hash(_ context.Context, d []byte) Hash

Hash runs SHA512

func (*MemEngine) LookupNode Uses

func (m *MemEngine) LookupNode(_ context.Context, h Hash) (b []byte, err error)

LookupNode looks up a MerkleTree node by hash

func (*MemEngine) LookupRoot Uses

func (m *MemEngine) LookupRoot(_ context.Context) (Hash, error)

LookupRoot fetches the root of the in-memory tree back out

func (*MemEngine) StoreNode Uses

func (m *MemEngine) StoreNode(_ context.Context, key Hash, b []byte) error

StoreNode stores the given node under the given key.

type Node Uses

type Node struct {
    PrevRoot Hash           `codec:"p,omitempty"`
    INodes   []Hash         `codec:"i,omitempty"`
    Leafs    []KeyValuePair `codec:"l,omitempty"`
    Type     NodeType       `codec:"t"`

Node is a node in the merkle tree. Can be either an interior iNode or a leaf that has pointers to user data.

type NodeNotFoundError Uses

type NodeNotFoundError struct {
    H Hash

NodeNotFoundError is raised when an interior node of the tree isn't found, though it was advertised by a parent node.

func (NodeNotFoundError) Error Uses

func (n NodeNotFoundError) Error() string

type NodeType Uses

type NodeType int
const (
    NodeTypeNone  NodeType = 0
    NodeTypeINode NodeType = 1
    NodeTypeLeaf  NodeType = 2

type Prefix Uses

type Prefix []byte

Prefix is the prefix of a Hash, for lookup of interior nodes.

func (Prefix) Eq Uses

func (p Prefix) Eq(p2 Prefix) bool

Eq returns true if the two prefixes are equal

func (Prefix) ToHash Uses

func (p Prefix) ToHash() Hash

ToHash converts a prefix into a hash, with a simple cast.

type SHA512Hasher Uses

type SHA512Hasher struct{}

SHA512Hasher is a simple SHA512 hash function application

func (SHA512Hasher) Hash Uses

func (s SHA512Hasher) Hash(b []byte) Hash

Hash the data

type SortedMap Uses

type SortedMap struct {
    // contains filtered or unexported fields

SortedMap is a list of KeyValuePairs, kept in sorted order so that binary search can work.

func NewSortedMap Uses

func NewSortedMap() *SortedMap

NewSortedMap makes an empty sorted map.

func NewSortedMapFromList Uses

func NewSortedMapFromList(l []KeyValuePair) *SortedMap

NewSortedMapFromList makes a sorted map from an unsorted list of KeyValuePairs

func NewSortedMapFromSortedList Uses

func NewSortedMapFromSortedList(l []KeyValuePair) *SortedMap

NewSortedMapFromSortedList just wraps the given sorted list and doesn't check that it's sorted. So don't pass it an unsorted list.

func (*SortedMap) Len Uses

func (s *SortedMap) Len() ChildIndex

Len returns the number of items in the Map.

type StorageEngine Uses

type StorageEngine interface {
    StoreNode(context.Context, Hash, []byte) error
    CommitRoot(ctx context.Context, prev Hash, curr Hash, txinfo TxInfo) error
    LookupNode(context.Context, Hash) ([]byte, error)
    LookupRoot(context.Context) (Hash, error)

StorageEngine specifies how to store and lookup merkle tree nodes and roots. You can use a DB like Dynamo or SQL to do this.

type Tree Uses

type Tree struct {
    // contains filtered or unexported fields

Tree is the MerkleTree class; it needs an engine and a configuration to run

func NewTree Uses

func NewTree(e StorageEngine, c Config) *Tree

NewTree makes a new tree

func (*Tree) Build Uses

func (t *Tree) Build(
    ctx context.Context, sm *SortedMap, txi TxInfo) (err error)

Build a tree from scratch, taking a batch input. Provide the batch import (it should be sorted), and also an optional TxInfo.


// factory is an "object factory" that makes a whole bunch
// of phony objects. Importantly, it fits the 'ValueConstructor'
// interface, so that it can tell the MerkleTree class how
// to pull type values out of the tree.
factory := merkleTree.NewTestObjFactory()

// Make a whole bunch of phony objects in our Object Factory.
objs := factory.Mproduce(1024)

// Collect and sort the objects into a "sorted map"
sm := merkleTree.NewSortedMapFromList(objs)

// Make a test storage engine
eng := merkleTree.NewMemEngine()

// 256 children per node; once there are 512 entries in a leaf,
// then split the leaf by adding more parents.
config := merkleTree.NewConfig(merkleTree.SHA512Hasher{}, 256, 512, factory)

// Make a new tree object with this engine and these config
// values
tree := merkleTree.NewTree(eng, config)

// Make an empty Tranaction info for now
var txInfo merkleTree.TxInfo

// Build the tree
err := tree.Build(context.TODO(), sm, txInfo)
if err != nil {

func (*Tree) Find Uses

func (t *Tree) Find(ctx context.Context, h Hash) (ret interface{}, root Hash, err error)

Find the hash in the tree. Return the value stored at the leaf under that hash, or nil if not found. Return an error if there was an internal problem.

func (*Tree) Upsert Uses

func (t *Tree) Upsert(ctx context.Context, kvp KeyValuePair, txinfo TxInfo) (err error)

Upsert inserts or updates the leaf with the given KeyValuePair information. It will associate the given transaction info if specified.

type TxInfo Uses

type TxInfo []byte

TxInfo is optional information that can be committed to a database along with a new MerkleTree root.

type ValueConstructor Uses

type ValueConstructor interface {
    // Construct a new template empty value for the leaf, so that the
    // Unmarshalling routine has the correct type template.
    Construct() interface{}

ValueConstructor is an interface for constructing values, so that typed values can be pulled out of the Merkle Tree. We are of course assuming that there is only one type of Value at the leaves, which makes sense.

Package merkleTree imports 11 packages (graph) and is imported by 10 packages. Updated 2020-03-16. Refresh now. Tools for package owners.