ledger

package
v0.13.1-patch.3 Latest Latest
Warning

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

Go to latest
Published: Jan 26, 2021 License: AGPL-3.0 Imports: 6 Imported by: 31

README

Flow Ledger Package

Ledger is a stateful fork-aware key/value storage. Any update (value change for a key) to the ledger generates a new ledger state. Updates can be applied to any recent state. These changes don't have to be sequential and ledger supports a tree of states. Ledger provides value lookup by key at a particular state (historic lookups) and can prove the existence/non-existence of a key-value pair at the given state. Ledger assumes the initial state includes all keys with an empty bytes slice as value.

This package provides two ledger implementations:

  • Complete Ledger implements a fast, memory-efficient and reliable ledger. It holds a limited number of recently used states in memory (for speed) and uses write-ahead logs and checkpointing to provide reliability. Under the hood complete ledger uses a collection of MTries(forest). MTrie is a customized in-memory binary Patricia Merkle trie storing payloads at specific storage paths. The payload includes both key-value pair and storage paths are determined by the PathFinder. Forest utilizes unchanged sub-trie sharing between tries to save memory.

  • Partial Ledger implements the ledger functionality for a limited subset of keys. Partial ledgers are designed to be constructed and verified by a collection of proofs from a complete ledger. The partial ledger uses a partial binary Merkle trie which holds intermediate hash value for the pruned branched and prevents updates to keys that were not part of proofs.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type ErrLedgerConstruction

type ErrLedgerConstruction struct {
	Err error
}

ErrLedgerConstruction is returned upon a failure in ledger creation steps

func NewErrLedgerConstruction

func NewErrLedgerConstruction(err error) *ErrLedgerConstruction

NewErrLedgerConstruction constructs a new ledger construction error

func (ErrLedgerConstruction) Error

func (e ErrLedgerConstruction) Error() string

func (ErrLedgerConstruction) Is

func (e ErrLedgerConstruction) Is(other error) bool

Is returns true if the type of errors are the same

type ErrMissingKeys

type ErrMissingKeys struct {
	Keys []Key
}

ErrMissingKeys is returned when some keys are not found in the ledger this is mostly used when dealing with partial ledger

func (ErrMissingKeys) Error

func (e ErrMissingKeys) Error() string

func (ErrMissingKeys) Is

func (e ErrMissingKeys) Is(other error) bool

Is returns true if the type of errors are the same

type Key

type Key struct {
	KeyParts []KeyPart
}

Key represents a hierarchical ledger key

func NewKey

func NewKey(kp []KeyPart) Key

NewKey construct a new key

func (*Key) CanonicalForm added in v0.12.0

func (k *Key) CanonicalForm() []byte

CanonicalForm returns a byte slice describing the key Warning, Changing this has an impact on how leaf hashes are computed don't use this to reconstruct the key later

func (*Key) DeepCopy

func (k *Key) DeepCopy() Key

DeepCopy returns a deep copy of the key

func (*Key) Equals

func (k *Key) Equals(other *Key) bool

Equals compares this key to another key

func (*Key) Size

func (k *Key) Size() int

Size returns the byte size needed to encode the key

func (*Key) String

func (k *Key) String() string

type KeyPart

type KeyPart struct {
	Type  uint16
	Value []byte
}

KeyPart is a typed part of a key

func NewKeyPart

func NewKeyPart(typ uint16, val []byte) KeyPart

NewKeyPart construct a new key part

func (*KeyPart) DeepCopy

func (kp *KeyPart) DeepCopy() *KeyPart

DeepCopy returns a deep copy of the key part

func (*KeyPart) Equals

func (kp *KeyPart) Equals(other *KeyPart) bool

Equals compares this key part to another key part

func (*KeyPart) MarshalJSON added in v0.11.0

func (kp *KeyPart) MarshalJSON() ([]byte, error)

type Ledger

type Ledger interface {
	// ledger implements methods needed to be ReadyDone aware
	module.ReadyDoneAware

	// InitialState returns the initial state of the ledger
	InitialState() State

	// Get returns values for the given slice of keys at specific state
	Get(query *Query) (values []Value, err error)

	// Update updates a list of keys with new values at specific state (update) and returns a new state
	Set(update *Update) (newState State, err error)

	// Prove returns proofs for the given keys at specific state
	Prove(query *Query) (proof Proof, err error)
}

Ledger is a stateful fork-aware key/value storage. Any update (value change for a key) to the ledger generates a new ledger state. Updates can be applied to any recent states. These changes don't have to be sequential and ledger supports a tree of states. Ledger provides value lookup by key at a particular state (historic lookups) and can prove the existence/non-existence of a key-value pair at the given state. Ledger assumes the initial state includes all keys with an empty bytes slice as value.

type Migration added in v0.12.0

type Migration func(payloads []Payload) ([]Payload, error)

Migration defines how to convert the given slice of input payloads into an slice of output payloads

type Path

type Path []byte

Path captures storage path of a payload; where we store a payload in the ledger

func (*Path) DeepCopy

func (p *Path) DeepCopy() Path

DeepCopy returns a deep copy of the payload

func (Path) Equals

func (p Path) Equals(o Path) bool

Equals compares this path to another path

func (*Path) Size

func (p *Path) Size() int

Size returns the size of the path

func (Path) String

func (p Path) String() string

type Payload

type Payload struct {
	Key   Key
	Value Value
}

Payload is the smallest immutable storable unit in ledger

func EmptyPayload

func EmptyPayload() *Payload

EmptyPayload returns an empty payload

func NewPayload

func NewPayload(key Key, value Value) *Payload

NewPayload returns a new payload

func (*Payload) DeepCopy

func (p *Payload) DeepCopy() *Payload

DeepCopy returns a deep copy of the payload

func (*Payload) Equals

func (p *Payload) Equals(other *Payload) bool

Equals compares this payload to another payload

func (*Payload) IsEmpty

func (p *Payload) IsEmpty() bool

IsEmpty returns true if key or value is not empty

func (*Payload) Size

func (p *Payload) Size() int

Size returns the size of the payload

func (*Payload) String

func (p *Payload) String() string

TODO fix me

type Proof

type Proof []byte

Proof is a byte slice capturing encoded version of a batch proof

func (Proof) Equals

func (pr Proof) Equals(o Proof) bool

Equals compares a proof to another ledger proof

func (Proof) String

func (pr Proof) String() string

type Query

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

Query holds all data needed for a ledger read or ledger proof

func NewEmptyQuery

func NewEmptyQuery(sc State) (*Query, error)

NewEmptyQuery returns an empty ledger query

func NewQuery

func NewQuery(sc State, keys []Key) (*Query, error)

NewQuery constructs a new ledger query

func (*Query) Keys

func (q *Query) Keys() []Key

Keys returns keys of the query

func (*Query) SetState

func (q *Query) SetState(s State)

SetState sets the state part of the query

func (*Query) Size

func (q *Query) Size() int

Size returns number of keys in the query

func (*Query) State

func (q *Query) State() State

State returns the state part of the query

type Reporter added in v0.12.0

type Reporter interface {
	Report(payloads []Payload) error
}

Reporter accepts slice ledger payloads and reports the state of the ledger

type RootHash

type RootHash []byte

RootHash captures the root hash of a trie

func (RootHash) Equals

func (rh RootHash) Equals(o RootHash) bool

Equals compares the root hash to another one

func (RootHash) String

func (rh RootHash) String() string

type State

type State []byte

State captures an state of the ledger

func (State) Base64 added in v0.12.0

func (sc State) Base64() string

Base64 return the base64 encoding of the state

func (State) Equals

func (sc State) Equals(o State) bool

Equals compares the state to another state

func (State) String

func (sc State) String() string

String returns the hex encoding of the state

type TrieBatchProof

type TrieBatchProof struct {
	Proofs []*TrieProof
}

TrieBatchProof is a struct that holds the proofs for several keys

so there is no need for two calls (read, proofs)

func NewTrieBatchProof

func NewTrieBatchProof() *TrieBatchProof

NewTrieBatchProof creates a new instance of BatchProof

func NewTrieBatchProofWithEmptyProofs

func NewTrieBatchProofWithEmptyProofs(numberOfProofs int) *TrieBatchProof

NewTrieBatchProofWithEmptyProofs creates an instance of Batchproof filled with n newly created proofs (empty)

func (*TrieBatchProof) AppendProof

func (bp *TrieBatchProof) AppendProof(p *TrieProof)

AppendProof adds a proof to the batch proof

func (*TrieBatchProof) Equals

func (bp *TrieBatchProof) Equals(o *TrieBatchProof) bool

Equals compares this batch proof to another batch proof

func (*TrieBatchProof) MergeInto

func (bp *TrieBatchProof) MergeInto(dest *TrieBatchProof)

MergeInto adds all of its proofs into the dest batch proof

func (*TrieBatchProof) Paths

func (bp *TrieBatchProof) Paths() []Path

Paths returns the slice of paths for this batch proof

func (*TrieBatchProof) Payloads

func (bp *TrieBatchProof) Payloads() []*Payload

Payloads returns the slice of paths for this batch proof

func (*TrieBatchProof) Size

func (bp *TrieBatchProof) Size() int

Size returns the number of proofs

func (*TrieBatchProof) String

func (bp *TrieBatchProof) String() string

type TrieProof

type TrieProof struct {
	Path      Path     // path
	Payload   *Payload // payload
	Interims  [][]byte // the non-default intermediate nodes in the proof
	Inclusion bool     // flag indicating if this is an inclusion or exclusion
	Flags     []byte   // The flags of the proofs (is set if an intermediate node has a non-default)
	Steps     uint8    // number of steps for the proof (path len) // TODO: should this be a type allowing for larger values?
}

TrieProof includes all the information needed to walk through a trie branch from an specific leaf node (key) up to the root of the trie.

func NewTrieProof

func NewTrieProof() *TrieProof

NewTrieProof creates a new instance of Trie Proof

func (*TrieProof) Equals

func (p *TrieProof) Equals(o *TrieProof) bool

Equals compares this proof to another payload

func (*TrieProof) String

func (p *TrieProof) String() string

type TrieRead

type TrieRead struct {
	RootHash RootHash
	Paths    []Path
}

TrieRead captures a trie read query

type TrieUpdate

type TrieUpdate struct {
	RootHash RootHash
	Paths    []Path
	Payloads []*Payload
}

TrieUpdate holds all data for a trie update

func (*TrieUpdate) Equals

func (u *TrieUpdate) Equals(other *TrieUpdate) bool

Equals compares this trie update to another trie update

func (*TrieUpdate) IsEmpty

func (u *TrieUpdate) IsEmpty() bool

IsEmpty returns true if key or value is not empty

func (*TrieUpdate) Size

func (u *TrieUpdate) Size() int

Size returns number of paths in the trie update

func (*TrieUpdate) String

func (u *TrieUpdate) String() string

type Update

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

Update holds all data needed for a ledger update

func NewEmptyUpdate

func NewEmptyUpdate(sc State) (*Update, error)

NewEmptyUpdate returns an empty ledger update

func NewUpdate

func NewUpdate(sc State, keys []Key, values []Value) (*Update, error)

NewUpdate returns an ledger update

func (*Update) Keys

func (u *Update) Keys() []Key

Keys returns keys of the update

func (*Update) SetState

func (u *Update) SetState(sc State)

SetState sets the state part of the update

func (*Update) Size

func (u *Update) Size() int

Size returns number of keys in the ledger update

func (*Update) State

func (u *Update) State() State

State returns the state part of this update

func (*Update) Values

func (u *Update) Values() []Value

Values returns value of the update

type Value

type Value []byte

Value holds the value part of a ledger key value pair

func (Value) DeepCopy

func (v Value) DeepCopy() Value

DeepCopy returns a deep copy of the value

func (Value) Equals

func (v Value) Equals(other Value) bool

Equals compares a ledger Value to another one

func (Value) MarshalJSON added in v0.11.0

func (v Value) MarshalJSON() ([]byte, error)

func (Value) Size

func (v Value) Size() int

Size returns the value size

func (Value) String

func (v Value) String() string

Directories

Path Synopsis
encoding
Package encoding provides byte serialization and deserialization of trie and ledger structs.
Package encoding provides byte serialization and deserialization of trie and ledger structs.
pathfinder
Package pathfinder computes the trie storage path for any given key/value pair
Package pathfinder computes the trie storage path for any given key/value pair
wal

Jump to

Keyboard shortcuts

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