merkledb

Jul 4, 2024

Changes in this version

+ const BranchFactorLargest

type Config

+ Hasher Hasher

+ type Hasher interface

+ HashNode func(node *node) ids.ID

+ HashValue func(value []byte) ids.ID

+ var DefaultHasher = SHA256Hasher

+ var SHA256Hasher Hasher = &sha256Hasher{}

Feb 29, 2024

Changes in this version

+ var ErrEmptyProof = errors.New("proof is empty")

+ var ErrNoChanges = errors.New("no changes provided")

+ var ErrNoEndRoot = fmt.Errorf("%w: end root not found", ErrInsufficientHistory)

type Config

+ IntermediateWriteBatchSize uint

+ IntermediateWriteBufferSize uint

type Key

+ func (k Key) Compare(other Key) int

type Trie

+ GetRangeProof func(ctx context.Context, start maybe.Maybe[[]byte], end maybe.Maybe[[]byte], ...) (*RangeProof, error)

+ GetValue func(ctx context.Context, key []byte) ([]byte, error)

+ GetValues func(ctx context.Context, keys [][]byte) ([][]byte, []error)

+ type View interface

+ CommitToDB func(ctx context.Context) error

Dec 8, 2023

Changes in this version

+ var BranchFactorToTokenSize = map[BranchFactor]int

+ var ErrInvalidBranchFactor = errors.New("branch factor must match one of the predefined branch factors")

+ var ErrVisitPathToKey = errors.New("failed to visit expected node during insertion")

+ type Clearer interface

+ Clear func() error

type Key

+ func ToToken(val byte, tokenSize int) Key

+ func (k Key) Extend(keys ...Key) Key

+ func (k Key) Length() int

type MockMerkleDB

+ func (m *MockMerkleDB) Clear() error

type MockMerkleDBMockRecorder

+ func (mr *MockMerkleDBMockRecorder) Clear() *gomock.Call

Dec 7, 2023

Changes in this version

+ var ErrInvalidKeyLength = errors.New("key length doesn't match bytes length, check specified branchFactor")

+ var ErrNilKey = errors.New("key is nil")

+ type Key struct

+ func ToKey(keyBytes []byte, branchFactor BranchFactor) Key

+ func (k Key) Append(token byte) Key

+ func (k Key) AppendExtend(token byte, extensionKey Key) Key

+ func (k Key) Bytes() []byte

+ func (k Key) Greater(other Key) bool

+ func (k Key) HasPrefix(prefix Key) bool

+ func (k Key) HasStrictPrefix(prefix Key) bool

+ func (k Key) Less(other Key) bool

+ func (k Key) Skip(tokensToSkip int) Key

+ func (k Key) Take(tokensToTake int) Key

+ func (k Key) Token(index int) byte

+ func (k Key) TokensLength() int

type ProofNode

+ Key Key

Dec 7, 2023

Changes in this version

+ var ErrInconsistentBranchFactor = errors.New("all keys in proof nodes should have the same branch factor")

+ var ErrInvalidPathLength = errors.New("path length doesn't match bytes length, check specified branchFactor")

+ var ErrNilPath = errors.New("path is nil")

+ var ErrPartialByteLengthWithValue = errors.New(...)

+ type BranchFactor int

+ const BranchFactor16

+ const BranchFactor2

+ const BranchFactor256

+ const BranchFactor4

+ func (f BranchFactor) Valid() error

type Config

+ BranchFactor BranchFactor

type MockMerkleDB

+ func (m *MockMerkleDB) PrefetchPath(arg0 []byte) error

+ func (m *MockMerkleDB) PrefetchPaths(arg0 [][]byte) error

type MockMerkleDBMockRecorder

+ func (mr *MockMerkleDBMockRecorder) PrefetchPath(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) PrefetchPaths(arg0 interface{}) *gomock.Call

+ type Path struct

+ func NewPath(p []byte, branchFactor BranchFactor) Path

+ func (p Path) Append(token byte) Path

+ func (p Path) AppendExtend(token byte, extensionPath Path) Path

+ func (p Path) Bytes() []byte

+ func (p Path) Greater(other Path) bool

+ func (p Path) HasPrefix(prefix Path) bool

+ func (p Path) HasStrictPrefix(prefix Path) bool

+ func (p Path) Less(other Path) bool

+ func (p Path) Skip(tokensToSkip int) Path

+ func (p Path) Take(tokensToTake int) Path

+ func (p Path) Token(index int) byte

+ func (p Path) TokensLength() int

+ type Prefetcher interface

+ PrefetchPath func(key []byte) error

+ PrefetchPaths func(keys [][]byte) error

Dec 6, 2023

Changes in this version

type Config

+ IntermediateNodeCacheSize uint

+ RootGenConcurrency uint

+ TraceLevel TraceLevel

+ ValueNodeCacheSize uint

+ type TraceLevel int

+ const DebugTrace

+ const InfoTrace

+ const NoTrace

+ type ViewChanges struct

+ BatchOps []database.BatchOp

+ ConsumeBytes bool

+ MapOps map[string]maybe.Maybe[[]byte]

Dec 1, 2023

Changes in this version

+ var ErrInsufficientHistory = errors.New("insufficient history to generate proof")

+ var ErrNodesAlreadyCalculated = errors.New("cannot modify the trie after the node changes have been calculated")

+ var ErrParentNotDatabase = errors.New("parent trie is not database")

+ type ChangeOrRangeProof struct

+ ChangeProof *ChangeProof

+ RangeProof *RangeProof

Aug 28, 2023

Changes in this version

+ var ErrUnexpectedEndProof = errors.New("end proof should be empty")

Aug 25, 2023

Changes in this version

+ const DefaultEvictionBatchSize

Aug 25, 2023

Changes in this version

+ var ErrInvalidChildIndex = fmt.Errorf("child index must be less than %d", NodeBranchFactor)

+ var ErrInvalidMaybe = errors.New("maybe is nothing but has value")

+ var ErrNilChangeProof = errors.New("change proof is nil")

+ var ErrNilMaybeBytes = errors.New("maybe bytes is nil")

+ var ErrNilProof = errors.New("proof is nil")

+ var ErrNilProofNode = errors.New("proof node is nil")

+ var ErrNilRangeProof = errors.New("range proof is nil")

+ var ErrNilSerializedPath = errors.New("serialized path is nil")

+ var ErrNilValue = errors.New("value is nil")

+ var ErrNilValueOrHash = errors.New("proof node's valueOrHash field is nil")

type ChangeProof

+ func (proof *ChangeProof) ToProto() *pb.ChangeProof

+ func (proof *ChangeProof) UnmarshalProto(pbProof *pb.ChangeProof) error

+ type ChangeProofer interface

+ CommitChangeProof func(ctx context.Context, proof *ChangeProof) error

+ GetChangeProof func(ctx context.Context, startRootID ids.ID, endRootID ids.ID, start []byte, ...) (*ChangeProof, error)

+ VerifyChangeProof func(ctx context.Context, proof *ChangeProof, start []byte, end []byte, ...) error

type Config

+ EvictionBatchSize int

+ type MerkleRootGetter interface

+ GetMerkleRoot func(ctx context.Context) (ids.ID, error)

type Proof

+ func (proof *Proof) ToProto() *pb.Proof

+ func (proof *Proof) UnmarshalProto(pbProof *pb.Proof) error

+ type ProofGetter interface

+ GetProof func(ctx context.Context, bytesPath []byte) (*Proof, error)

type ProofNode

+ func (node *ProofNode) ToProto() *pb.ProofNode

+ func (node *ProofNode) UnmarshalProto(pbNode *pb.ProofNode) error

type RangeProof

+ func (proof *RangeProof) ToProto() *pb.RangeProof

+ func (proof *RangeProof) UnmarshalProto(pbProof *pb.RangeProof) error

+ type RangeProofer interface

+ CommitRangeProof func(ctx context.Context, start []byte, proof *RangeProof) error

+ GetRangeProofAtRoot func(ctx context.Context, rootID ids.ID, start, end []byte, maxLength int) (*RangeProof, error)

Aug 25, 2023

Changes in this version

+ type MerkleDB interface

+ CommitChangeProof func(ctx context.Context, proof *ChangeProof) error

+ CommitRangeProof func(ctx context.Context, start []byte, proof *RangeProof) error

+ GetChangeProof func(ctx context.Context, startRootID ids.ID, endRootID ids.ID, start []byte, ...) (*ChangeProof, error)

+ GetRangeProofAtRoot func(ctx context.Context, rootID ids.ID, start, end []byte, maxLength int) (*RangeProof, error)

+ VerifyChangeProof func(ctx context.Context, proof *ChangeProof, start []byte, end []byte, ...) error

+ type MockMerkleDB struct

+ func NewMockMerkleDB(ctrl *gomock.Controller) *MockMerkleDB

+ func (m *MockMerkleDB) Close() error

+ func (m *MockMerkleDB) CommitChangeProof(arg0 context.Context, arg1 *ChangeProof) error

+ func (m *MockMerkleDB) CommitRangeProof(arg0 context.Context, arg1 []byte, arg2 *RangeProof) error

+ func (m *MockMerkleDB) Compact(arg0, arg1 []byte) error

+ func (m *MockMerkleDB) Delete(arg0 []byte) error

+ func (m *MockMerkleDB) EXPECT() *MockMerkleDBMockRecorder

+ func (m *MockMerkleDB) Get(arg0 []byte) ([]byte, error)

+ func (m *MockMerkleDB) GetChangeProof(arg0 context.Context, arg1, arg2 ids.ID, arg3, arg4 []byte, arg5 int) (*ChangeProof, error)

+ func (m *MockMerkleDB) GetMerkleRoot(arg0 context.Context) (ids.ID, error)

+ func (m *MockMerkleDB) GetProof(arg0 context.Context, arg1 []byte) (*Proof, error)

+ func (m *MockMerkleDB) GetRangeProof(arg0 context.Context, arg1, arg2 []byte, arg3 int) (*RangeProof, error)

+ func (m *MockMerkleDB) GetRangeProofAtRoot(arg0 context.Context, arg1 ids.ID, arg2, arg3 []byte, arg4 int) (*RangeProof, error)

+ func (m *MockMerkleDB) GetValue(arg0 context.Context, arg1 []byte) ([]byte, error)

+ func (m *MockMerkleDB) GetValues(arg0 context.Context, arg1 [][]byte) ([][]byte, []error)

+ func (m *MockMerkleDB) Has(arg0 []byte) (bool, error)

+ func (m *MockMerkleDB) HealthCheck(arg0 context.Context) (interface{}, error)

+ func (m *MockMerkleDB) Insert(arg0 context.Context, arg1, arg2 []byte) error

+ func (m *MockMerkleDB) NewBatch() database.Batch

+ func (m *MockMerkleDB) NewIterator() database.Iterator

+ func (m *MockMerkleDB) NewIteratorWithPrefix(arg0 []byte) database.Iterator

+ func (m *MockMerkleDB) NewIteratorWithStart(arg0 []byte) database.Iterator

+ func (m *MockMerkleDB) NewIteratorWithStartAndPrefix(arg0, arg1 []byte) database.Iterator

+ func (m *MockMerkleDB) NewPreallocatedView(arg0 int) (TrieView, error)

+ func (m *MockMerkleDB) NewView() (TrieView, error)

+ func (m *MockMerkleDB) Put(arg0, arg1 []byte) error

+ func (m *MockMerkleDB) Remove(arg0 context.Context, arg1 []byte) error

+ func (m *MockMerkleDB) VerifyChangeProof(arg0 context.Context, arg1 *ChangeProof, arg2, arg3 []byte, arg4 ids.ID) error

+ type MockMerkleDBMockRecorder struct

+ func (mr *MockMerkleDBMockRecorder) Close() *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) CommitChangeProof(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) CommitRangeProof(arg0, arg1, arg2 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Compact(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Delete(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Get(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetChangeProof(arg0, arg1, arg2, arg3, arg4, arg5 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetMerkleRoot(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetProof(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetRangeProof(arg0, arg1, arg2, arg3 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetRangeProofAtRoot(arg0, arg1, arg2, arg3, arg4 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetValue(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) GetValues(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Has(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) HealthCheck(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Insert(arg0, arg1, arg2 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewBatch() *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewIterator() *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewIteratorWithPrefix(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewIteratorWithStart(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewIteratorWithStartAndPrefix(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewPreallocatedView(arg0 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) NewView() *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Put(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) Remove(arg0, arg1 interface{}) *gomock.Call

+ func (mr *MockMerkleDBMockRecorder) VerifyChangeProof(arg0, arg1, arg2, arg3, arg4 interface{}) *gomock.Call

Aug 25, 2023

Changes in this version

type ChangeProof

+ KeyChanges []KeyChange

+ type KeyChange struct

+ Key []byte

+ Value Maybe[[]byte]

Mar 29, 2023

Changes in this version

+ var ErrInvalidMaxSize = errors.New("expected max size to be > 0 KB")

+ var ErrNoValidRoot = errors.New("a valid root was not provided to the trieView constructor")

type Database

+ func (*Database) CommitToDB(context.Context) error

+ func (*Database) CommitToParent(context.Context) error

type Maybe

+ func Clone(m Maybe[[]byte]) Maybe[[]byte]

type TrieView

+ CommitToParent func(ctx context.Context) error

Mar 28, 2023

Changes in this version

+ var ErrGetPathToFailure = errors.New("GetPathTo failed to return the closest node")

+ var ErrInvalid = errors.New("the trie this view was based on has changed, rending this view invalid")

+ var ErrViewIsNotAChild = errors.New("passed in view is required to be a child of the current view")

type TrieView

+ CommitToDB func(ctx context.Context) error

Mar 28, 2023

Changes in this version

+ const HashLength

+ var ErrProofNodeHasUnincludedValue = errors.New(...)

+ var ErrProofValueDoesntMatch = errors.New(...)

type Proof

+ Value Maybe[[]byte]

type ProofNode

+ ValueOrHash Maybe[[]byte]

Feb 15, 2023

Changes in this version

+ const EmptyPath

+ const NodeBranchFactor

+ const RootPath

+ var Codec = newCodec()

+ var ErrChangedBaseRoot = errors.New("the trie this view was based on has changed its root")

+ var ErrCommitted = errors.New("view has been committed")

+ var ErrDataInMissingRootProof = errors.New(...)

+ var ErrEditLocked = errors.New(...)

+ var ErrExtraProofNodes = errors.New("extra proof nodes in path")

+ var ErrGetClosestNodeFailure = errors.New("GetClosestNode failed to return the closest node")

+ var ErrInvalidMaxLength = errors.New("expected max length to be > 0")

+ var ErrInvalidProof = errors.New("proof obtained an invalid root ID")

+ var ErrNoEndProof = errors.New("no end proof")

+ var ErrNoMerkleProof = errors.New("empty key response must include merkle proof")

+ var ErrNoProof = errors.New("proof has no nodes")

+ var ErrNoStartProof = errors.New("no start proof")

+ var ErrNonIncreasingProofNodes = errors.New("each proof node key must be a strict prefix of the next")

+ var ErrNonIncreasingValues = errors.New("keys sent are not in increasing order")

+ var ErrOddLengthWithValue = errors.New(...)

+ var ErrProofNodeNotForKey = errors.New("the provided node has a key that is not a prefix of the specified key")

+ var ErrRootIDNotPresent = errors.New("root id is not present in history")

+ var ErrShouldJustBeRoot = errors.New("end proof should only contain root")

+ var ErrStartAfterEnd = errors.New("start key > end key")

+ var ErrStartRootNotFound = errors.New("start root is not before end root in history")

+ var ErrStateFromOutsideOfRange = errors.New("state key falls outside of the start->end range")

+ var Version = newCodec()

+ type ChangeProof struct

+ DeletedKeys [][]byte

+ EndProof []ProofNode

+ HadRootsInHistory bool

+ KeyValues []KeyValue

+ StartProof []ProofNode

+ func (proof *ChangeProof) Empty() bool

+ func (proof *ChangeProof) Verify(ctx context.Context, db *Database, start []byte, end []byte, ...) error

+ type Config struct

+ HistoryLength int

+ NodeCacheSize int

+ Reg prometheus.Registerer

+ Tracer trace.Tracer

+ ValueCacheSize int

+ type Database struct

+ func New(ctx context.Context, db database.Database, config Config) (*Database, error)

+ func (db *Database) Close() error

+ func (db *Database) CommitChangeProof(ctx context.Context, proof *ChangeProof) error

+ func (db *Database) CommitRangeProof(ctx context.Context, start []byte, proof *RangeProof) error

+ func (db *Database) Compact(start []byte, limit []byte) error

+ func (db *Database) Delete(key []byte) error

+ func (db *Database) Get(key []byte) ([]byte, error)

+ func (db *Database) GetChangeProof(ctx context.Context, startRootID ids.ID, endRootID ids.ID, start []byte, ...) (*ChangeProof, error)

+ func (db *Database) GetHistoricalView(ctx context.Context, rootID ids.ID) (ReadOnlyTrie, error)

+ func (db *Database) GetMerkleRoot(_ context.Context) (ids.ID, error)

+ func (db *Database) GetProof(ctx context.Context, key []byte) (*Proof, error)

+ func (db *Database) GetRangeProof(ctx context.Context, start, end []byte, maxLength int) (*RangeProof, error)

+ func (db *Database) GetRangeProofAtRoot(ctx context.Context, rootID ids.ID, start, end []byte, maxLength int) (*RangeProof, error)

+ func (db *Database) GetValue(ctx context.Context, key []byte) ([]byte, error)

+ func (db *Database) GetValues(ctx context.Context, keys [][]byte) ([][]byte, []error)

+ func (db *Database) Has(k []byte) (bool, error)

+ func (db *Database) HealthCheck(ctx context.Context) (interface{}, error)

+ func (db *Database) Insert(ctx context.Context, k, v []byte) error

+ func (db *Database) NewBatch() database.Batch

+ func (db *Database) NewIterator() database.Iterator

+ func (db *Database) NewIteratorWithPrefix(prefix []byte) database.Iterator

+ func (db *Database) NewIteratorWithStart(start []byte) database.Iterator

+ func (db *Database) NewIteratorWithStartAndPrefix(start, prefix []byte) database.Iterator

+ func (db *Database) NewPreallocatedView(ctx context.Context, estimatedSize int) (TrieView, error)

+ func (db *Database) NewView(ctx context.Context) (TrieView, error)

+ func (db *Database) OnEviction(node *node)

+ func (db *Database) Put(k, v []byte) error

+ func (db *Database) Remove(ctx context.Context, key []byte) error

+ type Decoder interface

+ DecodeChangeProof func(bytes []byte, p *ChangeProof) (uint16, error)

+ DecodeProof func(bytes []byte, p *Proof) (uint16, error)

+ DecodeRangeProof func(bytes []byte, p *RangeProof) (uint16, error)

+ type Encoder interface

+ EncodeChangeProof func(version uint16, p *ChangeProof) ([]byte, error)

+ EncodeProof func(version uint16, p *Proof) ([]byte, error)

+ EncodeRangeProof func(version uint16, p *RangeProof) ([]byte, error)

+ type EncoderDecoder interface

+ type KeyValue struct

+ Key []byte

+ Value []byte

+ type Maybe struct

+ func Nothing() Maybe[T]

+ func Some(val T) Maybe[T]

+ func (m Maybe[T]) IsNothing() bool

+ func (m Maybe[T]) Value() T

+ type Proof struct

+ Key []byte

+ Path []ProofNode

+ func (proof *Proof) Verify(ctx context.Context, expectedRootID ids.ID) error

+ type ProofNode struct

+ Children map[byte]ids.ID

+ KeyPath SerializedPath

+ Value Maybe[[]byte]

+ type RangeProof struct

+ EndProof []ProofNode

+ KeyValues []KeyValue

+ StartProof []ProofNode

+ func (proof *RangeProof) Verify(ctx context.Context, start []byte, end []byte, expectedRootID ids.ID) error

+ type ReadOnlyTrie interface

+ GetMerkleRoot func(ctx context.Context) (ids.ID, error)

+ GetProof func(ctx context.Context, bytesPath []byte) (*Proof, error)

+ GetRangeProof func(ctx context.Context, start, end []byte, maxLength int) (*RangeProof, error)

+ GetValue func(ctx context.Context, key []byte) ([]byte, error)

+ GetValues func(ctx context.Context, keys [][]byte) ([][]byte, []error)

+ type SerializedPath struct

+ NibbleLength int

+ Value []byte

+ func (s SerializedPath) AppendNibble(nibble byte) SerializedPath

+ func (s SerializedPath) Equal(other SerializedPath) bool

+ func (s SerializedPath) HasPrefix(prefix SerializedPath) bool

+ func (s SerializedPath) HasStrictPrefix(prefix SerializedPath) bool

+ func (s SerializedPath) NibbleVal(nibbleIndex int) byte

+ type Trie interface

+ Insert func(ctx context.Context, key, value []byte) error

+ NewPreallocatedView func(ctx context.Context, estimatedChanges int) (TrieView, error)

+ NewView func(ctx context.Context) (TrieView, error)

+ Remove func(ctx context.Context, key []byte) error

+ type TrieView interface

+ Commit func(ctx context.Context) error