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 ¶
- type ErrLedgerConstruction
- type ErrMissingKeys
- type Key
- type KeyPart
- type Ledger
- type Migration
- type Path
- type Payload
- type Proof
- type Query
- 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 TrieUpdate
- type Update
- type Value
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 (*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
// 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
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
type Payload ¶
Payload is the smallest immutable storable unit in ledger
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 Reporter ¶ added in v0.12.0
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
type State ¶
type State []byte
State captures an state of the ledger
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 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 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 |
|---|---|
|
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 |