README
¶
go-merkle-tree
Go language to build and check keybase's sitewide merkle tree.
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 ¶
- Variables
- type BadChildPointerError
- type ChildIndex
- type Config
- type Hash
- type HashMismatchError
- type Hasher
- type KeyValuePair
- type Level
- type MemEngine
- func (m *MemEngine) CommitRoot(_ context.Context, prev Hash, curr Hash, txinfo TxInfo) error
- func (m *MemEngine) Hash(_ context.Context, d []byte) Hash
- func (m *MemEngine) LookupNode(_ context.Context, h Hash) (b []byte, err error)
- func (m *MemEngine) LookupRoot(_ context.Context) (Hash, error)
- func (m *MemEngine) StoreNode(_ context.Context, key Hash, b []byte) error
- type Node
- type NodeNotFoundError
- type NodeType
- type Prefix
- type SHA512Hasher
- type SortedMap
- type StorageEngine
- type Tree
- type TxInfo
- type ValueConstructor
Examples ¶
Constants ¶
This section is empty.
Variables ¶
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 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)
type Hash ¶
type Hash []byte
Hash is a byte-array, used to represent a full collision-resistant hash.
func (Hash) Len ¶
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 ¶
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 ¶
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 ¶
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 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 ¶
CommitRoot "commits" the root ot the blessed memory slot
func (*MemEngine) LookupNode ¶
LookupNode looks up a MerkleTree node by hash
func (*MemEngine) LookupRoot ¶
LookupRoot fetches the root of the in-memory tree back out
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 SHA512Hasher ¶
type SHA512Hasher struct{}
SHA512Hasher is a simple SHA512 hash function application
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 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 ¶
Tree is the MerkleTree class; it needs an engine and a configuration to run
func (*Tree) Build ¶
Build a tree from scratch, taking a batch input. Provide the batch import (it should be sorted), and also an optional TxInfo.
Example ¶
package main
import (
"golang.org/x/net/context"
merkleTree "github.com/keybase/go-merkle-tree"
)
func main() {
// 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 {
panic(err.Error())
}
}
Output:
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.
Source Files