merkletree

Documentation

Index

• Constants
• Variables
• func ValidateAddLeaf(mtdt *Metadata, leaf *Node, toRoot []*Node) error
• func ValidateCreate(mtdt *Metadata) error
• func Verify(proof []Hash, root Hash, leaf Leaf) bool
• type Hash
  • func (h Hash) String() string
• type Leaf
• type MerkleTree
  • func InitializeNew(ctx context.Context, db Store, name string, levels uint8, seeds []Seed, ...) (*MerkleTree, error)
  • func LoadExisting(ctx context.Context, db Store, name string, readOnly bool) (*MerkleTree, error)
  • func (t *MerkleTree) AddLeaf(ctx context.Context, leaf Leaf) error
  • func (t *MerkleTree) GetCurrentRootNode(ctx context.Context) (*Node, error)
  • func (t *MerkleTree) GetLastAddedLeafNode(ctx context.Context) (*Node, error)
  • func (t *MerkleTree) GetLeafCount(ctx context.Context) (uint64, error)
  • func (t *MerkleTree) GetLeafNode(ctx context.Context, leaf Leaf) (*Node, error)
  • func (t *MerkleTree) GetLeafNodeByIndex(ctx context.Context, index uint64) (*Node, error)
  • func (t *MerkleTree) GetLeafNodeForRoot(ctx context.Context, root Hash) (*Node, error)
  • func (t *MerkleTree) GetProofForLeafAtIndex(ctx context.Context, forLeaf, untilLeaf uint64) ([]Hash, error)
  • func (t *MerkleTree) GetRootNodeForLeaf(ctx context.Context, leaf uint64) (*Node, error)
  • func (t *MerkleTree) Refresh(ctx context.Context) error
  • func (t *MerkleTree) SimulateAddingLeaves(ctx context.Context, leaves []Leaf) (Hash, error)
• type Metadata
  • func (m *Metadata) Clone() Metadata
  • func (m *Metadata) CopyTo(dst *Metadata)
  • func (m *Metadata) Validate() error
• type Node
  • func (n *Node) Clone() Node
  • func (n *Node) CopyTo(dst *Node)
  • func (n *Node) Validate() error
• type Seed
• type Store

Constants

const (
	// todo: 64 levels causes an overflow issue
	MaxLevels = 63
	MinLevels = 1
)

Variables

var (
	ErrMerkleTreeNotFound = errors.New("merkle tree not found")
	ErrLeafNotFound       = errors.New("merkle tree leaf not found")
	ErrRootNotFound       = errors.New("merkle tree root not found")
	ErrStaleMerkleTree    = errors.New("merkle tree state is stale")
	ErrMerkleTreeFull     = errors.New("merkle tree is full")
	ErrInvalidLevelCount  = errors.New("merkle tree level count is invalid")
	ErrTreeIsntMutable    = errors.New("merkle tree is a read-only instance")
)

var (
	ErrMetadataExists   = errors.New("merkle tree metadata already exists")
	ErrMetadataNotFound = errors.New("merkle tree metadata not found")
	ErrInvalidMetadata  = errors.New("merkle tree metadata is old or invalid")
	ErrNodeExists       = errors.New("merkle tree node already exists")
	ErrNodeNotFound     = errors.New("merkle tree node not found")
)

Functions

func ValidateAddLeaf

func ValidateAddLeaf(mtdt *Metadata, leaf *Node, toRoot []*Node) error

ValidateAddLeaf is used by Store implementations to validate AddLeaf calls

func ValidateCreate

func ValidateCreate(mtdt *Metadata) error

ValidateCreate is used by Store implementations to validate Create calls

func Verify

func Verify(proof []Hash, root Hash, leaf Leaf) bool

Verify verifies that a merkle proof is correct

Types

type Hash

type Hash []byte

func (Hash) String

func (h Hash) String() string

type Leaf

type Leaf []byte

type MerkleTree

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

MerkleTree is a DB-backed merkle tree implementation. It is locally thread safe, but any higher level entity using this implementation should use a distributed lock.

todo: We'll need a heuristic to allow us to delete old versions of nodes whenever proofs are no longer needed.

func InitializeNew

func InitializeNew(ctx context.Context, db Store, name string, levels uint8, seeds []Seed, readOnly bool) (*MerkleTree, error)

InitializeNew initializes a new MerkleTree backed by the provided DB

func LoadExisting

func LoadExisting(ctx context.Context, db Store, name string, readOnly bool) (*MerkleTree, error)

LoadExisting loads an existing MerkleTree from the provided DB

func (*MerkleTree) AddLeaf

func (t *MerkleTree) AddLeaf(ctx context.Context, leaf Leaf) error

AddLeaf adds a leaf node to the merkle tree. If ErrStaleMerkleTree is returned, then this merkle tree instance is outdated and a new one should be loaded.

func (*MerkleTree) GetCurrentRootNode

func (t *MerkleTree) GetCurrentRootNode(ctx context.Context) (*Node, error)

GetCurrentRootNode gets the current root node given the tree's local state

func (*MerkleTree) GetLastAddedLeafNode

func (t *MerkleTree) GetLastAddedLeafNode(ctx context.Context) (*Node, error)

GetLastAddedLeafNode gets the last added leaf node given the tree's local state

func (*MerkleTree) GetLeafCount

func (t *MerkleTree) GetLeafCount(ctx context.Context) (uint64, error)

GetLeafCount gets the number of leaves in the merkle tree given the tree's local state

func (*MerkleTree) GetLeafNode

func (t *MerkleTree) GetLeafNode(ctx context.Context, leaf Leaf) (*Node, error)

GetLeafNode gets a leaf node in the tree by its value

func (*MerkleTree) GetLeafNodeByIndex

func (t *MerkleTree) GetLeafNodeByIndex(ctx context.Context, index uint64) (*Node, error)

func (*MerkleTree) GetLeafNodeForRoot

func (t *MerkleTree) GetLeafNodeForRoot(ctx context.Context, root Hash) (*Node, error)

GetLeafNodeForRoot gets the leaf node added into the tree when the root equated to the provided hash.

func (*MerkleTree) GetProofForLeafAtIndex

func (t *MerkleTree) GetProofForLeafAtIndex(ctx context.Context, forLeaf, untilLeaf uint64) ([]Hash, error)

GetProofForLeafAtIndex gets a merkle proof for a leaf node

func (*MerkleTree) GetRootNodeForLeaf

func (t *MerkleTree) GetRootNodeForLeaf(ctx context.Context, leaf uint64) (*Node, error)

GetRootNodeForLeaf gets the root node at the time of adding the provided leaf

func (*MerkleTree) Refresh

func (t *MerkleTree) Refresh(ctx context.Context) error

Refresh refreshes a MerkleTree to an updated state. This is particularly useful in certain scenarios:

1. The tree is in read-only mode, and won't observe state changes locally.
2. AddLeaf failed with ErrStaleMerkleTree, so it must be outdated.

func (*MerkleTree) SimulateAddingLeaves

func (t *MerkleTree) SimulateAddingLeaves(ctx context.Context, leaves []Leaf) (Hash, error)

SimulateAddingLeaves simulates adding leaves to the merkle tree given its local state and returns the computed root hash. This can be used to validate leaf insertion before committing it to the DB using AddLeaf.

type Metadata

type Metadata struct {
	Id        uint64
	Name      string
	Levels    uint8
	NextIndex uint64
	Seed      Seed
	CreatedAt time.Time
}

func (*Metadata) Clone

func (m *Metadata) Clone() Metadata

func (*Metadata) CopyTo

func (m *Metadata) CopyTo(dst *Metadata)

func (*Metadata) Validate

func (m *Metadata) Validate() error

type Node

type Node struct {
	Id        uint64
	TreeId    uint64
	Level     uint8
	Index     uint64
	Hash      Hash
	LeafValue []byte
	Version   uint64
	CreatedAt time.Time
}

Level 0 = leaf Level (0, Record.Levels) = subtree Level Record.Levels = root

func (*Node) Clone

func (n *Node) Clone() Node

func (*Node) CopyTo

func (n *Node) CopyTo(dst *Node)

func (*Node) Validate

func (n *Node) Validate() error

type Seed

type Seed []byte

type Store

type Store interface {
	// Create creates a new merkle tree metadata
	Create(ctx context.Context, mtdt *Metadata) error

	// GetByName gets merkle tree metadata by name
	GetByName(ctx context.Context, name string) (*Metadata, error)

	// AddLeaf updates a merkle tree by inserting the provided leaf and
	// updated nodes going along the path from leaf to root.
	//
	// todo: Better name for "toRoot"
	AddLeaf(ctx context.Context, mtdt *Metadata, leaf *Node, toRoot []*Node) error

	// GetNode gets an exactly versioned node for a tree at a particular level
	// and index
	GetNode(ctx context.Context, tree uint64, level uint8, index uint64, version uint64) (*Node, error)

	// GetLatestNode gets the latest versioned node, bounded inclusively by
	// untilVersion, for a tree at a particular level and index
	GetLatestNode(ctx context.Context, tree uint64, level uint8, index uint64, untilVersion uint64) (*Node, error)

	// GetLatestNodesForProof gets the latest non-zero nodes that make up the
	// proof for forLeaf at the untilVersion version of the merklee tree
	GetLatestNodesForProof(ctx context.Context, tree uint64, levels uint8, forLeaf, untilVersion uint64) ([]*Node, error)

	// GetLatestNodesForFilledSubtrees gets the latest nodes that make up a
	// merkle tree's filled subtrees array at the untilVersion version of the
	// merklee tree
	GetLatestNodesForFilledSubtrees(ctx context.Context, tree uint64, levels uint8, untilVersion uint64) ([]*Node, error)

	// GetLeafByHash gets a leaf node by its hash value
	GetLeafByHash(ctx context.Context, tree uint64, hash Hash) (*Node, error)

	// GetNodeByHash gets a node by its hash value
	GetNodeByHash(ctx context.Context, tree uint64, hash Hash) (*Node, error)
}

Store is a DB layer to support persistent merkle trees. It should be used in conjuction with the MerkleTree implementation (ie. don't use this interface directly).