README
¶
merkle
Package merkle implements a very simple, immutable, in-memory, generic, "hash function-agnostic" merkle tree.
Documentation is provided in godoc, as usual.
Documentation
¶
Overview ¶
Package merkle implements a very simple, immutable, in-memory, generic, "hash function-agnostic" merkle tree.
Index ¶
- type Datum
- type ErrHashUnavailable
- type ErrNoData
- type Tree
- func (t *Tree) AppendAndReconstruct(data ...Datum)
- func (t *Tree) DeleteAndReconstruct(data ...Datum)
- func (t *Tree) Height() int
- func (t *Tree) Leaves() [][]byte
- func (t *Tree) MerkleRoot() []byte
- func (t *Tree) MerkleSize() (merkleSize int)
- func (t *Tree) NumLeaves() (numLeaves int)
- func (t *Tree) Size() int
- func (t *Tree) VerifyDatum(datum Datum) (bool, error)
- func (t *Tree) VerifyDigest(digest []byte) (bool, error)
- func (t *Tree) VerifyOrderedID(orderedID uint) (bool, error)
- func (t *Tree) VerifySerializedDatum(serializedDatum []byte) (bool, error)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Datum ¶
type Datum interface {
// Serialize must return a serialized representation of the Datum.
Serialize() []byte
}
Datum is the interface that any piece of data has to implement so as to be able to be contained in the leaves of the merkle tree.
type ErrHashUnavailable ¶
type ErrHashUnavailable struct{}
ErrHashUnavailable signifies that the requested hash function has not been linked into the binary.
func (ErrHashUnavailable) Error ¶
func (ErrHashUnavailable) Error() string
type ErrNoData ¶
type ErrNoData struct{}
ErrNoData signifies that the piece of data requested is either nil or not present in the merkle tree.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is the exported struct to interact with the merkle tree.
func NewTree ¶
NewTree creates a new merkle tree given one of the available (i.e. linked into the binary) hash functions and a bunch of data.
It returns a non-nil error either if the requested hash function has not been linked into the binary, or if data are not given at all.
func (*Tree) AppendAndReconstruct ¶
AppendAndReconstruct appends the given data as new tree leaves, and reconstructs the merkle tree to take them into account as well.
This obviously modifies the merkle root of the tree.
func (*Tree) DeleteAndReconstruct ¶
DeleteAndReconstruct deletes the given data from the tree leaves, and reconstructs the merkle tree on the new (reduced) number of leaves.
This obviously modifies the merkle root of the tree.
func (*Tree) Height ¶
Height returns the height of the merkle tree, including both its leaves and the merkle nodes.
func (*Tree) Leaves ¶
Leaves returns a slice of all pieces of Data stored in the merkle tree (in their serialized format) in the order that they were inserted by the user.
func (*Tree) MerkleRoot ¶
MerkleRoot returns the hash digest of the root of the merkle tree.
func (*Tree) MerkleSize ¶
MerkleSize returns the number of merkle nodes in the merkle trees, i.e. the total number of nodes in the merkle tree, excluding its leaves.
func (*Tree) Size ¶
Size returns the total number of nodes in the merkle tree, including both its leaves and the merkle nodes.
func (*Tree) VerifyDatum ¶
VerifyDatum verifies that the given Datum is present in the merkle tree, in which case it returns true and a nil error value.
It requires O(log2(L)) search among the leaves and O(log2(L)) hash calculations.
If the given hash digest cannot be verified, VerifyDatum returns false. If the given hash digest cannot be found in one of the merkle tree's leaves, VerifyDatum returns false and a non-nil error value.
func (*Tree) VerifyDigest ¶
VerifyDigest verifies that the given (leaf) hash digest is present in the merkle tree, in which case it returns true and a nil error value.
It requires O(L) search among the leaves and O(log2(L)) hash calculations.
If the given hash digest cannot be verified, VerifyDigest returns false. If the given hash digest cannot be found in one of the merkle tree's leaves, VerifyDigest returns false and a non-nil error value.
func (*Tree) VerifyOrderedID ¶
VerifyOrderedID verifies that the Datum with the given ordered ID (based on the order that the leaves were initially given) is present in the merkle tree, in which case it returns true and a nil error value.
It requires O(L) search among the leaves and O(log2(L)) hash calculations.
If the given hash digest cannot be verified, VerifyOrderedID returns false. If the given hash digest cannot be found in one of the merkle tree's leaves, VerifyOrderedID returns false and a non-nil error value.
func (*Tree) VerifySerializedDatum ¶
VerifySerializedDatum verifies that the given Datum (given in its serialized format) is present in the merkle tree, in which case it returns true and a nil error value.
It requires O(log2(L)) search among the leaves and O(log2(L)) hash calculations.
If the given hash digest cannot be verified, VerifySerializedDatum returns false. If the given hash digest cannot be found in one of the merkle tree's leaves, VerifySerializedDatum returns false and a non-nil error value.
Source Files