historytree

Documentation

Overview

Package historytree implements part of Crosby's and Wallach's history tree data structure, as presented in "Efficient Data Structures for Tamper-Evident Logging", available at http://static.usenix.org/event/sec09/tech/full_papers/crosby.pdf . We provide membership proofs and omit incremental proofs and signing roots. We also support computing the updated roots on the history tree based on a membership proof that fixes the rest of the tree. See the Balloon paper for details.

Index

• type MembershipProof
  • func (p *MembershipProof) Size() (bytes int)
  • func (p *MembershipProof) Update(events [][]byte) (root []byte, version int, err error)
  • func (p *MembershipProof) Verify() (correct bool)
• type Position
• type ProofPosition
• type Tree
  • func NewTree() (t *Tree)
  • func (t *Tree) Add(event []byte) (root []byte, err error)
  • func (t *Tree) Clone() (clone *Tree)
  • func (t *Tree) LatestVersion() int
  • func (t *Tree) MembershipProof(index, version int) (proof MembershipProof, err error)
  • func (t *Tree) Root() (c []byte)
  • func (t *Tree) Size() int

Types

type MembershipProof

type MembershipProof struct {
	Nodes          []ProofPosition
	Index, Version int
	Event, Root    []byte
}

MembershipProof is a proof of membership of an event.

func (*MembershipProof) Size

func (p *MembershipProof) Size() (bytes int)

Size returns the size in bytes of a membership proof.

func (*MembershipProof) Update

func (p *MembershipProof) Update(events [][]byte) (root []byte, version int, err error)

Update calculates the updated history tree, represented by the valid membership proof for the latest event inserted into a history tree, by inserting the provided events. Returns the updated root, or an error.

func (*MembershipProof) Verify

func (p *MembershipProof) Verify() (correct bool)

Verify verifies a membership proof

type Position

type Position struct {
	Index, Layer int
}

Position is a position in the tree.

type ProofPosition

type ProofPosition struct {
	Hash []byte
	Position
}

ProofPosition is a position and its hash in the tree.

type Tree

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

Tree is a history tree.

func NewTree

func NewTree() (t *Tree)

NewTree returns a new history tree.

func (*Tree) Add

func (t *Tree) Add(event []byte) (root []byte, err error)

Add adds an event to the history tree.

func (*Tree) Clone

func (t *Tree) Clone() (clone *Tree)

Clone creates a copy of the history tree.

func (*Tree) LatestVersion

func (t *Tree) LatestVersion() int

LatestVersion returns the latest version of the tree.

func (*Tree) MembershipProof

func (t *Tree) MembershipProof(index, version int) (proof MembershipProof, err error)

MembershipProof generates a membership proof.

func (*Tree) Root

func (t *Tree) Root() (c []byte)

Root returns the current root of the tree.

func (*Tree) Size

func (t *Tree) Size() int

Size returns the number of events in the tree.