tree

package
v0.2.2 Latest Latest
Warning

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

 Go to latest Published: Apr 26, 2022 License: MIT Imports: 8 Imported by: 87

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var NavigationError = errors.New("navigation error")
View Source 
var ZeroHashes []Root

Functions

func BitIndex 

func BitIndex(v uint64) (out uint8)

bitmagic: binary search through a uint64 to find the index (least bit being 0) of the first set bit. Zero is a special case, it has a 0 bit index. Example: 

(in out): (0 0), (1 0), (2 1), (3 1), (4 2), (5 2), (6 2), (7 2), (8 3), (9 3)

func BitLength 

func BitLength(v uint64) (out uint8)

bitmagic: binary search through a uint64 to find the bit-length Zero is a special case, it has a 0 bit length. Example: 

(in out): (0 0), (1 1), (2 2), (3 2), (4 3), (5 3), (6 3), (7 3), (8 4), (9 4)

func CoverDepth 

func CoverDepth(v uint64) (out uint8)

bitmagic: binary search through a uint64, to find the BitIndex of next power of 2 (if not already a power of 2) Zero is a special case, it has a 0 depth. Example: 

(in out): (0 0), (1 0), (2 1), (3 2), (4 2), (5 3), (6 3), (7 3), (8 3), (9 4)

func InitZeroHashes 

func InitZeroHashes(h HashFn, zeroHashesLevels uint)

initialize the zero-hashes pre-computed data with the given hash-function.

func ReadRoots added in v0.1.0 

func ReadRoots(dr *codec.DecodingReader, roots *[]Root, length uint64) error

func ReadRootsLimited added in v0.1.0 

func ReadRootsLimited(dr *codec.DecodingReader, roots *[]Root, limit uint64) error

func WriteRoots added in v0.1.0 

func WriteRoots(ew *codec.EncodingWriter, roots []Root) error

WriteRoots serialization, efficient version of List/Vector serialization

Types

type ChunksHTR added in v0.1.0 

type ChunksHTR func(i uint64) Root

type Gindex 

type Gindex interface {
	// Subtree returns the same gindex, but with the anchor moved one bit to the right, to represent the subtree position.
	Subtree() Gindex
	// Anchor of the gindex: same depth, but with position zeroed out.
	Anchor() Gindex
	// Left child gindex
	Left() Gindex
	// Right child gindex
	Right() Gindex
	// Parent gindex
	Parent() Gindex
	// If the gindex points into the left subtree (2nd bit is 0)
	IsLeft() bool
	// If the gindex is the root (= 1)
	IsRoot() bool
	// If gindex is 2 or 3
	IsClose() bool
	// Get the depth of the gindex
	Depth() uint32
	// Iterate over the bits of the gindex
	// The depth is excl. the "root" bit
	BitIter() (iter GindexBitIter, depth uint32)
	// Encode the gindex as little-endian byte array. An invalid gindex (<= 0) must return nil.
	LittleEndian() []byte
	// Encode the gindex as big-endian byte array. An invalid gindex (<= 0) must return nil.
	BigEndian() []byte
	// LeftAlignedBigEndian returns the bits shifted such that the anchor bit is the left-most
	LeftAlignedBigEndian() (data []byte, bitLen uint32)
}

type Gindex64 

type Gindex64 uint64
const LeftGindex Gindex64 = 2
const RightGindex Gindex64 = 3
const RootGindex Gindex64 = 1

func ToGindex64 

func ToGindex64(index uint64, depth uint8) (Gindex64, error)

func (Gindex64) Anchor 

func (v Gindex64) Anchor() Gindex

func (Gindex64) BigEndian added in v0.1.7 

func (v Gindex64) BigEndian() []byte

func (Gindex64) BitIter 

func (v Gindex64) BitIter() (iter GindexBitIter, depth uint32)

func (Gindex64) Depth 

func (v Gindex64) Depth() uint32

func (Gindex64) IsClose 

func (v Gindex64) IsClose() bool

func (Gindex64) IsLeft 

func (v Gindex64) IsLeft() bool

func (Gindex64) IsRoot 

func (v Gindex64) IsRoot() bool

func (Gindex64) Left 

func (v Gindex64) Left() Gindex

func (Gindex64) LeftAlignedBigEndian added in v0.1.9 

func (v Gindex64) LeftAlignedBigEndian() (data []byte, bitLen uint32)

func (Gindex64) LittleEndian added in v0.1.6 

func (v Gindex64) LittleEndian() []byte

func (Gindex64) Parent 

func (v Gindex64) Parent() Gindex

func (Gindex64) Right 

func (v Gindex64) Right() Gindex

func (Gindex64) Subtree 

func (v Gindex64) Subtree() Gindex

type Gindex64BitIter 

type Gindex64BitIter struct {
	Marker uint64
	Gindex uint64
}

func (*Gindex64BitIter) Next 

func (iter *Gindex64BitIter) Next() (right bool, ok bool)

type GindexBitIter 

type GindexBitIter interface {
	// Next: move forward through gindex.
	// It returns bools for each bit after the "root" bit.
	// If "ok" is false, the bit cannot be read, none are remaining.
	// Subsequent calls are invalid.
	// For these extra calls, "ok" will be false, and "right" is undefined.
	Next() (right bool, ok bool)
}

type HTR added in v0.1.0 

type HTR interface {
	HashTreeRoot(h HashFn) Root
}

type HashFn 

type HashFn func(a Root, b Root) Root
var Hash HashFn = sha256Combi

func (HashFn) BitListHTR added in v0.1.0 

func (h HashFn) BitListHTR(bits []byte, bitlimit uint64) Root

func (HashFn) BitVectorHTR added in v0.1.0 

func (h HashFn) BitVectorHTR(bits []byte) Root

func (HashFn) ByteListHTR added in v0.1.2 

func (h HashFn) ByteListHTR(values []byte, limit uint64) Root

func (HashFn) ByteVectorHTR added in v0.1.2 

func (h HashFn) ByteVectorHTR(values []byte) Root

func (HashFn) ChunksHTR added in v0.1.0 

func (h HashFn) ChunksHTR(chunks ChunksHTR, length uint64, limit uint64) Root

ChunksHTR is like SeriesHTR, except that the items are chunked by the input, and chunks are merely merkleized to get the hash-tree-root. No length mixin is performed (required for a list/basic-list/bitlist hash-tree-root).

func (HashFn) ComplexListHTR added in v0.1.0 

func (h HashFn) ComplexListHTR(series SeriesHTR, length uint64, limit uint64) Root

func (HashFn) ComplexVectorHTR added in v0.1.0 

func (h HashFn) ComplexVectorHTR(series SeriesHTR, length uint64) Root

func (HashFn) HashTreeRoot added in v0.1.0 

func (h HashFn) HashTreeRoot(fields ...HTR) Root

HashTreeRoot is a small utility function to implement HTR for custom compound types easily. E.g. for a struct `x` with 3 fields, call hFn.HashTreeRoot(x.A, x.B, x.C)

func (HashFn) Mixin added in v0.1.0 

func (h HashFn) Mixin(v Root, length uint64) Root

func (HashFn) Uint64ListHTR added in v0.1.0 

func (h HashFn) Uint64ListHTR(v func(i uint64) uint64, length uint64, limit uint64) Root

func (HashFn) Uint64VectorHTR added in v0.1.0 

func (h HashFn) Uint64VectorHTR(v func(i uint64) uint64, length uint64) Root

func (HashFn) Uint8ListHTR added in v0.1.4 

func (h HashFn) Uint8ListHTR(v func(i uint64) uint8, length uint64, limit uint64) Root

func (HashFn) Uint8VectorHTR added in v0.1.4 

func (h HashFn) Uint8VectorHTR(v func(i uint64) uint8, length uint64) Root

func (HashFn) Union added in v0.1.7 

func (h HashFn) Union(selector uint8, value HTR) Root
type Link func(v Node) (Node, error)

A link is called to rebind a value, and retrieve the new root node.

func DeeperSetter added in v0.1.6 

func DeeperSetter(link Link, node Node, target Gindex, expand bool) (Link, error)

target.IsRoot() and target.IsClose() must both be false. The link and node args are the first step into the path, i.e. at depth 1, not the anchor node.

func (Link) Wrap 

func (outer Link) Wrap(inner Link) Link

type NewHashFn 

type NewHashFn func() HashFn
var GetHashFn NewHashFn = sha256CombiRepeat

Get a hash-function that re-uses the hashing working-variables. Defaults to SHA-256.

type Node 

type Node interface {
	Left() (Node, error)
	Right() (Node, error)
	IsLeaf() bool
	RebindLeft(v Node) (Node, error)
	RebindRight(v Node) (Node, error)
	Getter(target Gindex) (Node, error)
	Setter(target Gindex, expand bool) (Link, error)
	SummarizeInto(target Gindex, h HashFn) (SummaryLink, error)
	MerkleRoot(h HashFn) Root
}

Node of a binary merkle tree

func Identity 

func Identity(v Node) (Node, error)

func SubtreeFillToContents 

func SubtreeFillToContents(nodes []Node, depth uint8) (Node, error)

func SubtreeFillToDepth 

func SubtreeFillToDepth(bottom Node, depth uint8) Node

func SubtreeFillToLength 

func SubtreeFillToLength(bottom Node, depth uint8, length uint64) (Node, error)

func ZeroNode 

func ZeroNode(depth uint32) Node

type PairNode 

type PairNode struct {
	Value      Root
	LeftChild  Node
	RightChild Node
}

An immutable (L, R) pair with a link to the holding node. If L or R changes, the link is used to bind a new (L, *R) or (*L, R) pair in the holding value.

func NewPairNode 

func NewPairNode(a Node, b Node) *PairNode

func (*PairNode) Getter 

func (c *PairNode) Getter(target Gindex) (Node, error)

func (*PairNode) IsLeaf 

func (c *PairNode) IsLeaf() bool

func (*PairNode) Left 

func (c *PairNode) Left() (Node, error)

func (*PairNode) MerkleRoot 

func (c *PairNode) MerkleRoot(h HashFn) Root

func (*PairNode) RebindLeft 

func (c *PairNode) RebindLeft(v Node) (Node, error)

func (*PairNode) RebindRight 

func (c *PairNode) RebindRight(v Node) (Node, error)

func (*PairNode) Right 

func (c *PairNode) Right() (Node, error)

func (*PairNode) Setter 

func (c *PairNode) Setter(target Gindex, expand bool) (Link, error)

func (*PairNode) SummarizeInto 

func (c *PairNode) SummarizeInto(target Gindex, h HashFn) (SummaryLink, error)

type Root 

type Root [32]byte

func Merkleize added in v0.1.0 

func Merkleize(hasher HashFn, count uint64, limit uint64, leaf func(i uint64) Root) (out Root)

Merkleize with log(N) space allocation

func (Root) ByteLength added in v0.1.0 

func (Root) ByteLength() uint64

func (*Root) Deserialize added in v0.1.0 

func (r *Root) Deserialize(dr *codec.DecodingReader) error

func (Root) FixedLength added in v0.1.0 

func (Root) FixedLength() uint64

func (*Root) Getter 

func (r *Root) Getter(target Gindex) (Node, error)

func (Root) HashTreeRoot added in v0.1.0 

func (r Root) HashTreeRoot(_ HashFn) Root

func (*Root) IsLeaf 

func (r *Root) IsLeaf() bool

func (*Root) Left 

func (r *Root) Left() (Node, error)

func (Root) MarshalText added in v0.0.2 

func (r Root) MarshalText() ([]byte, error)

func (*Root) MerkleRoot 

func (r *Root) MerkleRoot(h HashFn) Root

func (*Root) RebindLeft 

func (r *Root) RebindLeft(v Node) (Node, error)

func (*Root) RebindRight 

func (r *Root) RebindRight(v Node) (Node, error)

func (*Root) Right 

func (r *Root) Right() (Node, error)

func (Root) Serialize added in v0.1.0 

func (r Root) Serialize(w *codec.EncodingWriter) error

func (*Root) Setter 

func (r *Root) Setter(target Gindex, expand bool) (Link, error)

func (Root) String added in v0.0.2 

func (r Root) String() string

func (*Root) SummarizeInto 

func (r *Root) SummarizeInto(target Gindex, h HashFn) (SummaryLink, error)

func (*Root) UnmarshalText added in v0.0.2 

func (r *Root) UnmarshalText(text []byte) error

func (Root) ValueByteLength added in v0.1.0 

func (Root) ValueByteLength() (uint64, error)

type SeriesHTR added in v0.1.0 

type SeriesHTR func(i uint64) HTR
type SummaryLink func() (Node, error)

func SummaryInto added in v0.1.6 

func SummaryInto(n Node, target Gindex, h HashFn) (SummaryLink, error)

SummaryInto creates a SummaryLink that collapses the subtree at the target Gindex into just the root

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.