package module
v0.0.0-...-f941b05 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Dec 20, 2023 License: BSD-3-Clause Imports: 11 Imported by: 22



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

Build Status




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


go get


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.




This section is empty.


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

ErrBadINode is thrown when we find a corrupt/malformed iNode


This section is empty.


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 {
	// 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.

package main

import (

	merkleTree ""

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 {

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL