README

go-merkle-tree

Go language to build and check keybase's sitewide merkle tree.

Travis CI

GoDoc

Expand ▾ Collapse ▴

Documentation

Overview

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

    Install:

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

    Design:

    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.

    Implementation:

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

    Usage:

    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.
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

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

      ErrBadINode is thrown when we find a corrupt/malformed iNode

      Functions

      This section is empty.

      Types

      type BadChildPointerError

      type BadChildPointerError struct {
      	V interface{}
      }

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

        func (BadChildPointerError) Error

        func (b BadChildPointerError) Error() string

        type ChildIndex

        type ChildIndex uint32

          ChildIndex specifies one of an iNode's child nodes.

          type Config

          type Config struct {
          	// contains filtered or unexported fields
          }

            Config defines the shape of the MerkleTree.

            func NewConfig

            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

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

              func (Config) PrefixAtLevel

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

              type Hash

              type Hash []byte

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

                func (Hash) Eq

                func (h Hash) Eq(h2 Hash) bool

                  Eq determines if the two hashes are equal.

                  func (Hash) Len

                  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

                    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

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

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

                        type HashMismatchError

                        type HashMismatchError struct {
                        	H Hash
                        }

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

                          func (HashMismatchError) Error

                          func (h HashMismatchError) Error() string

                          type Hasher

                          type Hasher interface {
                          	Hash([]byte) Hash
                          }

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

                            type KeyValuePair

                            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

                              type Level uint

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

                                type MemEngine

                                type MemEngine struct {
                                	// contains filtered or unexported fields
                                }

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

                                  func NewMemEngine

                                  func NewMemEngine() *MemEngine

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

                                    func (*MemEngine) CommitRoot

                                    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

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

                                        Hash runs SHA512

                                        func (*MemEngine) LookupNode

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

                                          LookupNode looks up a MerkleTree node by hash

                                          func (*MemEngine) LookupRoot

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

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

                                            func (*MemEngine) StoreNode

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

                                              StoreNode stores the given node under the given key.

                                              type Node

                                              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

                                                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

                                                  func (n NodeNotFoundError) Error() string

                                                  type NodeType

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

                                                  type Prefix

                                                  type Prefix []byte

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

                                                    func (Prefix) Eq

                                                    func (p Prefix) Eq(p2 Prefix) bool

                                                      Eq returns true if the two prefixes are equal

                                                      func (Prefix) ToHash

                                                      func (p Prefix) ToHash() Hash

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

                                                        type SHA512Hasher

                                                        type SHA512Hasher struct{}

                                                          SHA512Hasher is a simple SHA512 hash function application

                                                          func (SHA512Hasher) Hash

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

                                                            Hash the data

                                                            type SortedMap

                                                            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

                                                              func NewSortedMap() *SortedMap

                                                                NewSortedMap makes an empty sorted map.

                                                                func NewSortedMapFromList

                                                                func NewSortedMapFromList(l []KeyValuePair) *SortedMap

                                                                  NewSortedMapFromList makes a sorted map from an unsorted list of KeyValuePairs

                                                                  func NewSortedMapFromSortedList

                                                                  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

                                                                    func (s *SortedMap) Len() ChildIndex

                                                                      Len returns the number of items in the Map.

                                                                      type StorageEngine

                                                                      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

                                                                        type Tree struct {
                                                                        	sync.RWMutex
                                                                        	// contains filtered or unexported fields
                                                                        }

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

                                                                          func NewTree

                                                                          func NewTree(e StorageEngine, c Config) *Tree

                                                                            NewTree makes a new tree

                                                                            func (*Tree) Build

                                                                            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.

                                                                              Example
                                                                              Output:
                                                                              
                                                                              

                                                                              func (*Tree) Find

                                                                              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

                                                                                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

                                                                                  type TxInfo []byte

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

                                                                                    type ValueConstructor

                                                                                    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.