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
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.
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.
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).
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).
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.
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.
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.
Documentation
¶
Index ¶
- Constants
- Variables
- func ComputeCompactValue(path hash.Hash, value []byte, nodeHeight int) hash.Hash
- func GetDefaultHashForHeight(height int) hash.Hash
- type ErrLedgerConstruction
- type ErrMissingKeys
- type Key
- type KeyPart
- type Ledger
- type Migration
- type Path
- type Payload
- type Proof
- type Query
- type QuerySingleValue
- type Reporter
- type RootHash
- type State
- type TrieBatchProof
- func (bp *TrieBatchProof) AppendProof(p *TrieProof)
- func (bp *TrieBatchProof) Equals(o *TrieBatchProof) bool
- func (bp *TrieBatchProof) MergeInto(dest *TrieBatchProof)
- func (bp *TrieBatchProof) Paths() []Path
- func (bp *TrieBatchProof) Payloads() []*Payload
- func (bp *TrieBatchProof) Size() int
- func (bp *TrieBatchProof) String() string
- type TrieProof
- type TrieRead
- type TrieReadSingleValue
- type TrieUpdate
- type Update
- type Value
Constants ¶
const NodeMaxHeight = PathLen * 8
The node maximum height or the tree height. It corresponds to the path size in bits.
const PathLen = 32
PathLen is the size of paths in bytes.
Variables ¶
var DummyPath = Path(hash.DummyHash)
DummyPath is an arbitrary path value, used in function error returns.
var DummyState = State(hash.DummyHash)
DummyState is an arbitrary value used in function failure cases, although it can represent a valid state.
Functions ¶
func ComputeCompactValue ¶ added in v0.17.0
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 GetDefaultHashForHeight ¶ added in v0.17.0
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 (*Key) CanonicalForm ¶ added in v0.12.0
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
type KeyPart ¶
KeyPart is a typed part of a key
func NewKeyPart ¶
NewKeyPart construct a new key part
func (KeyPart) MarshalJSON ¶ added in v0.11.0
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
// 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 ¶ added in v0.12.0
Migration defines how to convert the given slice of input payloads into an slice of output payloads
type Path ¶
Path captures storage path of a payload; where we store a payload in the ledger
func ToPath ¶ added in v0.17.0
ToPath converts a byte slice into a path. It returns an error if the slice has an invalid length.
func (Path) MarshalJSON ¶ added in v0.25.0
type Payload ¶
Payload is the smallest immutable storable unit in ledger
func (*Payload) Equals ¶
Equals compares this payload to another payload A nil payload is equivalent to an empty payload.
func (*Payload) ValueEquals ¶ added in v0.26.2
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
type Query ¶
type Query struct {
// contains filtered or unexported fields
}
Query holds all data needed for a ledger read or ledger proof
func NewEmptyQuery ¶
NewEmptyQuery returns an empty ledger query
type QuerySingleValue ¶ added in v0.26.2
type QuerySingleValue struct {
// contains filtered or unexported fields
}
QuerySingleValue contains ledger query for a single value
func NewQuerySingleValue ¶ added in v0.26.2
func NewQuerySingleValue(sc State, key Key) (*QuerySingleValue, error)
NewQuerySingleValue constructs a new ledger query for a single value
func (*QuerySingleValue) Key ¶ added in v0.26.2
func (q *QuerySingleValue) Key() Key
Key returns key of the query
func (*QuerySingleValue) State ¶ added in v0.26.2
func (q *QuerySingleValue) State() State
State returns the state part of the query
type Reporter ¶ added in v0.12.0
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 ¶
RootHash captures the root hash of a trie
func ToRootHash ¶ added in v0.17.0
ToRootHash converts a byte slice into a root hash. It returns an error if the slice has an invalid length.
func (RootHash) MarshalJSON ¶ added in v0.25.0
type State ¶
State captures an state of the ledger
func ToState ¶ added in v0.17.0
ToState converts a byte slice into a State. It returns an error if the slice has an invalid length.
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 []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 NewTrieProof ¶
func NewTrieProof() *TrieProof
NewTrieProof creates a new instance of Trie Proof
type TrieReadSingleValue ¶ added in v0.26.2
TrieReadSinglePayload contains trie read query for a single payload
type TrieUpdate ¶
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 ¶
NewEmptyUpdate returns an empty ledger update
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
common
|
|
|
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 |