ledger

package
v0.29.6 Latest Latest
Warning

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

 Go to latest Published: Jan 19, 2023 License: AGPL-3.0 Imports: 13 Imported by: 0

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.

Definitions

In this section we provide an overview of some of the concepts. Hence it is highly recommended to checkout this doc for the formal and technical definitions in more details.

binary Merkle tree

binary Merkle tree image

In this context a binary Merkle tree is defined as perfect binary tree with a specific height including three type of nodes:

  • leaf nodes: holds a payload (data), a path (where the node is located), and a hash value (hash of path and payload content)

  • interim nodes: holds a hash value which is defined as hash of hash value of left and right children.

node types image

A path is a unique address of a node storing a payload. Paths are derived from the content of payloads (see common/pathfinder). A path is explicitly a hash of 256 bits.

paths image

Operations

Get: Fetching a payload from the binary Merkle tree is by traversing the tree based on path bits. (0: left branch, 1: right branch)

Update: Updates to the tree starts with traversing the tree to the leaf node, updating payload, hash value of that node and hash value of all the ancestor nodes (nodes on higher level connected to this node).

update image

Prove: A binary Merkle tree can provide an inclusion proof for any given payload. A Merkle proof in this context includes all the information needed to walk through a tree branch from an specific leaf node (key) up to the root of the tree (yellow node hash values are needed for inclusion proof for the green node).

proof image

Memory-trie (Mtrie)

An Mtrie in this context is defined as a compact version of binary Merkle tree, providing the exact same functionality but doesn't explicitly store empty nodes. Formally, a node is empty:

  • the node is an empty leaf node: it doesn't hold any data and only stores a path. Its hash value is defined as a default hash based on the height of tree.
  • an interim node is defined to be empty, if its two children are empty.

binary partial trie image

forest

Formally, a forest is any acyclic graph. Any set of disjoint trees forms a forest. In the context of Flow, we take an existing state, represented by a Merkle tree. Updating the payload of some of the leafs creates a new Merkle tree, which we add to the forest. In other words, the forest holds a set of state snapshots

compact forest

A compact forest constructs a new trie after each update (copy on change) and reuses unchanged sub-tries from the parent.

compact forest image

path finder

Path finder deterministically computes a path for a given payload. Path finder is responsible for making sure the trie grows in balance.

partial binary Merkle trie

A partial Merkle trie is similar to a Merkle trie but only keeping a subset of nodes and having intermediate nodes without the full sub-trie. It can be constructed from batch of inclusion and non-inclusion proofs. It provides functionality to verify outcome of updates to a trie without the need to have the full trie.

partial trie image

Documentation

Index

Constants

View Source 
const (
	// CAUTION: if payload key encoding is changed, convertEncodedPayloadKey()
	// must be modified to convert encoded payload key from one version to
	// another version.
	PayloadVersion        = uint16(1)
	TrieUpdateVersion     = uint16(0) // Use payload version 0 encoding
	TrieProofVersion      = uint16(0) // Use payload version 0 encoding
	TrieBatchProofVersion = uint16(0) // Use payload version 0 encoding
)

Versions capture the maximum version of encoding this code supports. I.e. this code encodes data with the latest version and only decodes data with version smaller or equal to these versions. Bumping a version number prevents older versions of code from handling the newer version of data. New code handling new data version should be updated to also support backward compatibility if needed.

View Source 
const (
	// TypeUnknown - unknown type
	TypeUnknown = iota
	// TypeState - type for State
	TypeState
	// TypeKeyPart - type for KeyParts (a subset of key)
	TypeKeyPart
	// TypeKey - type for Keys (unique identifier to reference a location in ledger)
	TypeKey
	// TypeValue - type for Ledger Values
	TypeValue
	// TypePath - type for Paths (trie storage location of a key value pair)
	TypePath
	// TypePayload - type for Payloads (stored at trie nodes including key value pair )
	TypePayload
	// TypeProof type for Proofs
	// (all data needed to verify a key value pair at specific state)
	TypeProof
	// TypeBatchProof - type for BatchProofs
	TypeBatchProof
	// TypeQuery - type for ledger query
	TypeQuery
	// TypeUpdate - type for ledger update
	TypeUpdate
	// TypeTrieUpdate - type for trie update
	TypeTrieUpdate
)
View Source 
const NodeMaxHeight = PathLen * 8

The node maximum height or the tree height. It corresponds to the path size in bits.

View Source 
const PathLen = 32

PathLen is the size of paths in bytes.

Variables

View Source 
var DummyPath = Path(hash.DummyHash)

DummyPath is an arbitrary path value, used in function error returns.

View Source 
var DummyState = State(hash.DummyHash)

DummyState is an arbitrary value used in function failure cases, although it can represent a valid state.

Functions

func CheckType 

func CheckType(rawInput []byte, expectedType uint8) (rest []byte, err error)

CheckType extracts encoding byte from a raw encoded message checks it against expected type and returns the rest of rawInput (excluding type byte)

func CheckVersion 

func CheckVersion(rawInput []byte, maxVersion uint16) (rest []byte, version uint16, err error)

CheckVersion extracts encoding bytes from a raw encoded message checks it against the supported versions and returns the rest of rawInput (excluding encDecVersion bytes)

func ComputeCompactValue 

func ComputeCompactValue(path hash.Hash, value []byte, nodeHeight int) hash.Hash

ComputeCompactValue computes the value for the node considering the sub tree to only include this value and default values. It writes the hash result to the result input. UNCHECKED: payload!= nil

func EncodeAndAppendPayloadWithoutPrefix 

func EncodeAndAppendPayloadWithoutPrefix(buffer []byte, p *Payload, version uint16) []byte

EncodeAndAppendPayloadWithoutPrefix encodes a ledger payload without prefix (version and type) and appends to buffer. If payload is nil, unmodified buffer is returned.

func EncodeKey 

func EncodeKey(k *Key) []byte

EncodeKey encodes a key into a byte slice

func EncodeKeyPart 

func EncodeKeyPart(kp *KeyPart) []byte

EncodeKeyPart encodes a key part into a byte slice

func EncodePayload 

func EncodePayload(p *Payload) []byte

EncodePayload encodes a ledger payload

func EncodeTrieBatchProof 

func EncodeTrieBatchProof(bp *TrieBatchProof) []byte

EncodeTrieBatchProof encodes a batch proof into a byte slice

func EncodeTrieProof 

func EncodeTrieProof(p *TrieProof) []byte

EncodeTrieProof encodes the content of a proof into a byte slice

func EncodeTrieUpdate 

func EncodeTrieUpdate(t *TrieUpdate) []byte

EncodeTrieUpdate encodes a trie update struct

func EncodeValue 

func EncodeValue(v Value) []byte

EncodeValue encodes a value into a byte slice

func EncodedPayloadLengthWithoutPrefix 

func EncodedPayloadLengthWithoutPrefix(p *Payload, version uint16) int

func GetDefaultHashForHeight 

func GetDefaultHashForHeight(height int) hash.Hash

GetDefaultHashForHeight returns the default hashes of the SMT at a specified height.

For each tree level N, there is a default hash equal to the chained hashing of the default value N times.

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 DecodeKey 

func DecodeKey(encodedKey []byte) (*Key, error)

DecodeKey constructs a key from an encoded key part

func NewKey 

func NewKey(kp []KeyPart) Key

NewKey construct a new key

func (*Key) CanonicalForm 

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 A nil key is equivalent to an empty 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 DecodeKeyPart 

func DecodeKeyPart(encodedKeyPart []byte) (*KeyPart, error)

DecodeKeyPart constructs a key part from an encoded key part

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 

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

func (*KeyPart) UnmarshalJSON 

func (kp *KeyPart) UnmarshalJSON(b []byte) error

UnmarshalJSON unmarshals a JSON value of KeyPart.

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

	// HasState returns true if the given state exists inside the ledger
	HasState(state State) bool

	// GetSingleValue returns value for a given key at specific state
	GetSingleValue(query *QuerySingleValue) (value Value, err error)

	// 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, trieUpdate *TrieUpdate, 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 

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 hash.Hash

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

func ToPath 

func ToPath(pathBytes []byte) (Path, error)

ToPath converts a byte slice into a path. It returns an error if the slice has an invalid length.

func (Path) Equals 

func (p Path) Equals(o Path) bool

Equals compares this path to another path

func (Path) MarshalJSON 

func (p Path) MarshalJSON() ([]byte, error)

func (Path) String 

func (p Path) String() string

type Payload 

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

Payload is the smallest immutable storable unit in ledger

func DecodePayload 

func DecodePayload(encodedPayload []byte) (*Payload, error)

DecodePayload construct a payload from an encoded byte slice

func DecodePayloadWithoutPrefix 

func DecodePayloadWithoutPrefix(encodedPayload []byte, zeroCopy bool, version uint16) (*Payload, error)

DecodePayloadWithoutPrefix constructs a payload from encoded byte slice without prefix (version and type). If zeroCopy is true, returned payload references data in encodedPayload. Otherwise, it is copied.

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 A nil payload is equivalent to an empty payload.

func (*Payload) IsEmpty 

func (p *Payload) IsEmpty() bool

IsEmpty returns true if payload is nil or value is empty

func (*Payload) Key 

func (p *Payload) Key() (Key, error)

Key returns payload key. Error indicates that ledger.Key can't be created from payload key, so migration and reporting (known callers) should abort. CAUTION: do not modify returned key because it shares underlying data with payload key.

func (Payload) MarshalCBOR 

func (p Payload) MarshalCBOR() ([]byte, error)

MarshalCBOR returns CBOR encoding of p.

func (Payload) MarshalJSON 

func (p Payload) MarshalJSON() ([]byte, error)

MarshalJSON returns JSON encoding of p.

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

func (*Payload) UnmarshalCBOR 

func (p *Payload) UnmarshalCBOR(b []byte) error

UnmarshalCBOR unmarshals a CBOR value of payload.

func (*Payload) UnmarshalJSON 

func (p *Payload) UnmarshalJSON(b []byte) error

UnmarshalJSON unmarshals a JSON value of payload.

func (*Payload) Value 

func (p *Payload) Value() Value

Value returns payload value. CAUTION: do not modify returned value because it shares underlying data with payload value.

func (*Payload) ValueEquals 

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

ValueEquals compares this payload value to another payload value. A nil payload is equivalent to an empty payload. NOTE: prefer using this function over payload.Value.Equals() when comparing payload values. payload.ValueEquals() handles nil payload, while payload.Value.Equals() panics on nil payload.

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 QuerySingleValue 

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

QuerySingleValue contains ledger query for a single value

func NewQuerySingleValue 

func NewQuerySingleValue(sc State, key Key) (*QuerySingleValue, error)

NewQuerySingleValue constructs a new ledger query for a single value

func (*QuerySingleValue) Key 

func (q *QuerySingleValue) Key() Key

Key returns key of the query

func (*QuerySingleValue) State 

func (q *QuerySingleValue) State() State

State returns the state part of the query

type Reporter 

type Reporter interface {
	// Name returns the name of the reporter. Only used for logging.
	Name() string
	// Report accepts slice ledger payloads and reports the state of the ledger
	Report(payloads []Payload, statecommitment State) error
}

Reporter reports on data from the state

type RootHash 

type RootHash hash.Hash

RootHash captures the root hash of a trie

func ToRootHash 

func ToRootHash(rootHashBytes []byte) (RootHash, error)

ToRootHash converts a byte slice into a root hash. It returns an error if the slice has an invalid length.

func (RootHash) Equals 

func (rh RootHash) Equals(o RootHash) bool

Equals compares the root hash to another one

func (RootHash) MarshalJSON 

func (rh RootHash) MarshalJSON() ([]byte, error)

func (RootHash) String 

func (rh RootHash) String() string

type State 

type State hash.Hash

State captures an state of the ledger

func ToState 

func ToState(stateBytes []byte) (State, error)

ToState converts a byte slice into a State. It returns an error if the slice has an invalid length.

func (State) Base64 

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 DecodeTrieBatchProof 

func DecodeTrieBatchProof(encodedBatchProof []byte) (*TrieBatchProof, error)

DecodeTrieBatchProof constructs a batch proof from an encoded byte slice

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  []hash.Hash // the non-default intermediate nodes in the proof
	Inclusion bool        // flag indicating if this is an inclusion or exclusion proof
	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 DecodeTrieProof 

func DecodeTrieProof(encodedProof []byte) (*TrieProof, error)

DecodeTrieProof construct a proof from an encoded byte slice

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 TrieReadSingleValue 

type TrieReadSingleValue struct {
	RootHash RootHash
	Path     Path
}

TrieReadSinglePayload contains trie read query for a single payload

type TrieUpdate 

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

TrieUpdate holds all data for a trie update

func DecodeTrieUpdate 

func DecodeTrieUpdate(encodedTrieUpdate []byte) (*TrieUpdate, error)

DecodeTrieUpdate construct a trie update from an encoded byte slice

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 Type 

type Type uint8

Type capture the type of encoded entity (e.g. State, Key, Value, Path)

func (Type) String 

func (e Type) 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 DecodeValue 

func DecodeValue(encodedValue []byte) (Value, error)

DecodeValue constructs a ledger value using an encoded byte slice

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 A nil value is equivalent to an empty value.

func (Value) MarshalJSON 

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

func (*Value) UnmarshalJSON 

func (v *Value) UnmarshalJSON(b []byte) error

UnmarshalJSON unmarshals a JSON value of Value.

Source Files

View all Source files

Directories

Path Synopsis
common
bitutils
hash
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
proof
testutils
utils
mtrie
mtrie/flattener
mtrie/node
mtrie/trie
wal
wal/fixtures
ptrie

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.