Documentation
¶
Overview ¶
Package merkledb is a generated GoMock package.
Index ¶
- Constants
- Variables
- type BranchFactor
- type ChangeOrRangeProof
- type ChangeProof
- type ChangeProofer
- type Clearer
- type Config
- type Hasher
- type Key
- func (k Key) Bytes() []byte
- func (k Key) Compare(other Key) int
- func (k Key) Extend(keys ...Key) Key
- func (k Key) Greater(other Key) bool
- func (k Key) HasPrefix(prefix Key) bool
- func (k Key) HasStrictPrefix(prefix Key) bool
- func (k Key) Length() int
- func (k Key) Less(other Key) bool
- func (k Key) Skip(bitsToSkip int) Key
- func (k Key) Take(bitsToTake int) Key
- func (k Key) Token(bitIndex int, tokenSize int) byte
- type KeyChange
- type KeyValue
- type MerkleDB
- type MerkleRootGetter
- type MockMerkleDB
- func (m *MockMerkleDB) Clear() error
- func (m *MockMerkleDB) Close() error
- func (m *MockMerkleDB) CommitChangeProof(ctx context.Context, proof *ChangeProof) error
- func (m *MockMerkleDB) CommitRangeProof(ctx context.Context, start, end maybe.Maybe[[]byte], proof *RangeProof) error
- func (m *MockMerkleDB) Compact(start, limit []byte) error
- func (m *MockMerkleDB) Delete(key []byte) error
- func (m *MockMerkleDB) EXPECT() *MockMerkleDBMockRecorder
- func (m *MockMerkleDB) Get(key []byte) ([]byte, error)
- func (m *MockMerkleDB) GetChangeProof(ctx context.Context, startRootID, endRootID ids.ID, ...) (*ChangeProof, error)
- func (m *MockMerkleDB) GetMerkleRoot(ctx context.Context) (ids.ID, error)
- func (m *MockMerkleDB) GetProof(ctx context.Context, keyBytes []byte) (*Proof, error)
- func (m *MockMerkleDB) GetRangeProof(ctx context.Context, start, end maybe.Maybe[[]byte], maxLength int) (*RangeProof, error)
- func (m *MockMerkleDB) GetRangeProofAtRoot(ctx context.Context, rootID ids.ID, start, end maybe.Maybe[[]byte], ...) (*RangeProof, error)
- func (m *MockMerkleDB) GetValue(ctx context.Context, key []byte) ([]byte, error)
- func (m *MockMerkleDB) GetValues(ctx context.Context, keys [][]byte) ([][]byte, []error)
- func (m *MockMerkleDB) Has(key []byte) (bool, error)
- func (m *MockMerkleDB) HealthCheck(arg0 context.Context) (any, error)
- func (m *MockMerkleDB) NewBatch() database.Batch
- func (m *MockMerkleDB) NewIterator() database.Iterator
- func (m *MockMerkleDB) NewIteratorWithPrefix(prefix []byte) database.Iterator
- func (m *MockMerkleDB) NewIteratorWithStart(start []byte) database.Iterator
- func (m *MockMerkleDB) NewIteratorWithStartAndPrefix(start, prefix []byte) database.Iterator
- func (m *MockMerkleDB) NewView(ctx context.Context, changes ViewChanges) (View, error)
- func (m *MockMerkleDB) PrefetchPath(key []byte) error
- func (m *MockMerkleDB) PrefetchPaths(keys [][]byte) error
- func (m *MockMerkleDB) Put(key, value []byte) error
- func (m *MockMerkleDB) VerifyChangeProof(ctx context.Context, proof *ChangeProof, start, end maybe.Maybe[[]byte], ...) error
- type MockMerkleDBMockRecorder
- func (mr *MockMerkleDBMockRecorder) Clear() *gomock.Call
- func (mr *MockMerkleDBMockRecorder) Close() *gomock.Call
- func (mr *MockMerkleDBMockRecorder) CommitChangeProof(ctx, proof any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) CommitRangeProof(ctx, start, end, proof any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) Compact(start, limit any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) Delete(key any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) Get(key any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetChangeProof(ctx, startRootID, endRootID, start, end, maxLength any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetMerkleRoot(ctx any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetProof(ctx, keyBytes any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetRangeProof(ctx, start, end, maxLength any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetRangeProofAtRoot(ctx, rootID, start, end, maxLength any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetValue(ctx, key any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) GetValues(ctx, keys any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) Has(key any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) HealthCheck(arg0 any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) NewBatch() *gomock.Call
- func (mr *MockMerkleDBMockRecorder) NewIterator() *gomock.Call
- func (mr *MockMerkleDBMockRecorder) NewIteratorWithPrefix(prefix any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) NewIteratorWithStart(start any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) NewIteratorWithStartAndPrefix(start, prefix any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) NewView(ctx, changes any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) PrefetchPath(key any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) PrefetchPaths(keys any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) Put(key, value any) *gomock.Call
- func (mr *MockMerkleDBMockRecorder) VerifyChangeProof(ctx, proof, start, end, expectedEndRootID any) *gomock.Call
- type Prefetcher
- type Proof
- type ProofGetter
- type ProofNode
- type RangeProof
- type RangeProofer
- type TraceLevel
- type Trie
- type View
- type ViewChanges
Constants ¶
const ( BranchFactor2 = BranchFactor(2) BranchFactor4 = BranchFactor(4) BranchFactor16 = BranchFactor(16) BranchFactor256 = BranchFactor(256) BranchFactorLargest = BranchFactor256 )
const HashLength = 32
TODO: Support configurable hash lengths
Variables ¶
var ( ErrInsufficientHistory = errors.New("insufficient history to generate proof") ErrNoEndRoot = fmt.Errorf("%w: end root not found", ErrInsufficientHistory) )
var ( ErrInvalidBranchFactor = errors.New("branch factor must match one of the predefined branch factors") BranchFactorToTokenSize = map[BranchFactor]int{ BranchFactor2: 1, BranchFactor4: 2, BranchFactor16: 4, BranchFactor256: 8, } )
var ( ErrInvalidProof = errors.New("proof obtained an invalid root ID") ErrInvalidMaxLength = errors.New("expected max length to be > 0") ErrNonIncreasingValues = errors.New("keys sent are not in increasing order") ErrStateFromOutsideOfRange = errors.New("state key falls outside of the start->end range") ErrNonIncreasingProofNodes = errors.New("each proof node key must be a strict prefix of the next") ErrExtraProofNodes = errors.New("extra proof nodes in path") ErrDataInMissingRootProof = errors.New("there should be no state or deleted keys in a change proof that had a missing root") ErrEmptyProof = errors.New("proof is empty") ErrNoMerkleProof = errors.New("empty key response must include merkle proof") ErrShouldJustBeRoot = errors.New("end proof should only contain root") ErrNoStartProof = errors.New("no start proof") ErrNoEndProof = errors.New("no end proof") ErrProofNodeNotForKey = errors.New("the provided node has a key that is not a prefix of the specified key") ErrProofValueDoesntMatch = errors.New("the provided value does not match the proof node for the provided key's value") ErrProofNodeHasUnincludedValue = errors.New("the provided proof has a value for a key within the range that is not present in the provided key/values") ErrInvalidMaybe = errors.New("maybe is nothing but has value") ErrNilProofNode = errors.New("proof node is nil") ErrNilValueOrHash = errors.New("proof node's valueOrHash field is nil") ErrNilKey = errors.New("key is nil") ErrInvalidKeyLength = errors.New("key length doesn't match bytes length, check specified branchFactor") ErrNilRangeProof = errors.New("range proof is nil") ErrNilChangeProof = errors.New("change proof is nil") ErrNilMaybeBytes = errors.New("maybe bytes is nil") ErrNilProof = errors.New("proof is nil") ErrNilValue = errors.New("value is nil") ErrUnexpectedEndProof = errors.New("end proof should be empty") )
var ( ErrCommitted = errors.New("view has been committed") ErrInvalid = errors.New("the trie this view was based on has changed, rendering this view invalid") ErrPartialByteLengthWithValue = errors.New( "the underlying db only supports whole number of byte keys, so cannot record changes with partial byte lengths", ) ErrVisitPathToKey = errors.New("failed to visit expected node during insertion") ErrStartAfterEnd = errors.New("start key > end key") ErrNoChanges = errors.New("no changes provided") ErrParentNotDatabase = errors.New("parent trie is not database") ErrNodesAlreadyCalculated = errors.New("cannot modify the trie after the node changes have been calculated") )
Functions ¶
This section is empty.
Types ¶
type BranchFactor ¶ added in v1.10.13
type BranchFactor int
func (BranchFactor) Valid ¶ added in v1.10.13
func (b BranchFactor) Valid() error
Valid checks if BranchFactor [b] is one of the predefined valid options for BranchFactor
type ChangeOrRangeProof ¶ added in v1.10.9
type ChangeOrRangeProof struct { ChangeProof *ChangeProof RangeProof *RangeProof }
ChangeOrRangeProof has exactly one of ChangeProof or RangeProof is non-nil.
type ChangeProof ¶
type ChangeProof struct { // A proof that the smallest key in the requested range does/doesn't // exist in the trie with the requested start root. // Empty if no lower bound on the requested range was given. // Note that this may not be an entire proof -- nodes are omitted if // they are also in [EndProof]. StartProof []ProofNode // If [KeyChanges] is non-empty, this is a proof of the largest key // in [KeyChanges]. // // If [KeyChanges] is empty and an upper range bound was given, // this is a proof of the upper range bound. // // If [KeyChanges] is empty and no upper range bound was given, // this is empty. EndProof []ProofNode // A subset of key-values that were added, removed, or had their values // modified between the requested start root (exclusive) and the requested // end root (inclusive). // Each key is in the requested range (inclusive). // The first key-value is the first key-value at/after the range start. // The key-value pairs are consecutive. That is, if keys k1 and k2 are // in [KeyChanges] then there is no k3 that was modified between the start and // end roots such that k1 < k3 < k2. // This is a subset of the requested key-value range, rather than the entire // range, because otherwise the proof may be too large. // Sorted by increasing key and with no duplicate keys. // // Example: Suppose that between the start root and the end root, the following // key-value pairs were added, removed, or modified: // // [kv1, kv2, kv3, kv4, kv5] // where start <= kv1 < ... < kv5 <= end. // // The following are possible values of [KeyChanges]: // // [] // [kv1] // [kv1, kv2] // [kv1, kv2, kv3] // [kv1, kv2, kv3, kv4] // [kv1, kv2, kv3, kv4, kv5] // // The following values of [KeyChanges] are always invalid, for example: // // [kv2] (Doesn't include kv1, the first key-value at/after the range start) // [kv1, kv3] (Doesn't include kv2, the key-value between kv1 and kv3) // [kv1, kv3, kv2] (Not sorted by increasing key) // [kv1, kv1] (Duplicate key-value pairs) // [kv0, kv1] (For some kv1 < start) // [kv1, kv2, kv3, kv4, kv5, kv6] (For some kv6 > end) KeyChanges []KeyChange }
ChangeProof proves that a set of key-value changes occurred between two trie roots, where each key-value pair's key is between some lower and upper bound (inclusive).
func (*ChangeProof) Empty ¶
func (proof *ChangeProof) Empty() bool
func (*ChangeProof) ToProto ¶ added in v1.10.3
func (proof *ChangeProof) ToProto() *pb.ChangeProof
func (*ChangeProof) UnmarshalProto ¶ added in v1.10.3
func (proof *ChangeProof) UnmarshalProto(pbProof *pb.ChangeProof) error
type ChangeProofer ¶ added in v1.10.3
type ChangeProofer interface { // GetChangeProof returns a proof for a subset of the key/value changes in key range // [start, end] that occurred between [startRootID] and [endRootID]. // Returns at most [maxLength] key/value pairs. // Returns [ErrInsufficientHistory] if this node has insufficient history // to generate the proof. // Returns ErrEmptyProof if [endRootID] is ids.Empty. // Note that [endRootID] == ids.Empty means the trie is empty // (i.e. we don't need a change proof.) // Returns [ErrNoEndRoot], which wraps [ErrInsufficientHistory], if the // history doesn't contain the [endRootID]. GetChangeProof( ctx context.Context, startRootID ids.ID, endRootID ids.ID, start maybe.Maybe[[]byte], end maybe.Maybe[[]byte], maxLength int, ) (*ChangeProof, error) // Returns nil iff all the following hold: // - [start] <= [end]. // - [proof] is non-empty. // - All keys in [proof.KeyValues] and [proof.DeletedKeys] are in [start, end]. // If [start] is nothing, all keys are considered > [start]. // If [end] is nothing, all keys are considered < [end]. // - [proof.KeyValues] and [proof.DeletedKeys] are sorted in order of increasing key. // - [proof.StartProof] and [proof.EndProof] are well-formed. // - When the changes in [proof.KeyChanes] are applied, // the root ID of the database is [expectedEndRootID]. VerifyChangeProof( ctx context.Context, proof *ChangeProof, start maybe.Maybe[[]byte], end maybe.Maybe[[]byte], expectedEndRootID ids.ID, ) error // CommitChangeProof commits the key/value pairs within the [proof] to the db. CommitChangeProof(ctx context.Context, proof *ChangeProof) error }
type Clearer ¶ added in v1.10.16
type Clearer interface { // Deletes all key/value pairs from the database // and clears the change history. Clear() error }
type Config ¶
type Config struct { // BranchFactor determines the number of children each node can have. BranchFactor BranchFactor // Hasher defines the hash function to use when hashing the trie. // // If not specified, [DefaultHasher] will be used. Hasher Hasher // RootGenConcurrency is the number of goroutines to use when // generating a new state root. // // If 0 is specified, [runtime.NumCPU] will be used. RootGenConcurrency uint // The number of changes to the database that we store in memory in order to // serve change proofs. HistoryLength uint // The number of bytes used to cache nodes with values. ValueNodeCacheSize uint // The number of bytes used to cache nodes without values. IntermediateNodeCacheSize uint // The number of bytes used to store nodes without values in memory before forcing them onto disk. IntermediateWriteBufferSize uint // The number of bytes to write to disk when intermediate nodes are evicted // from the write buffer and written to disk. IntermediateWriteBatchSize uint // If [Reg] is nil, metrics are collected locally but not exported through // Prometheus. // This may be useful for testing. Reg prometheus.Registerer TraceLevel TraceLevel Tracer trace.Tracer }
type Hasher ¶ added in v1.11.9
type Hasher interface { // Returns the canonical hash of the non-nil [node]. HashNode(node *node) ids.ID // Returns the canonical hash of [value]. HashValue(value []byte) ids.ID }
var ( SHA256Hasher Hasher = &sha256Hasher{} // If a Hasher isn't specified, this package defaults to using the // [SHA256Hasher]. DefaultHasher = SHA256Hasher )
type Key ¶ added in v1.10.14
type Key struct {
// contains filtered or unexported fields
}
func ToKey ¶ added in v1.10.14
ToKey returns [keyBytes] as a new key Assumes all bits of the keyBytes are part of the Key, call Key.Take if that is not the case Creates a copy of [keyBytes], so keyBytes are safe to edit after the call
func ToToken ¶ added in v1.10.16
ToToken creates a key version of the passed byte with bit length equal to tokenSize
func (Key) Bytes ¶ added in v1.10.14
Bytes returns the raw bytes of the Key Invariant: The returned value must not be modified.
func (Key) Extend ¶ added in v1.10.16
Extend returns a new Key that is the in-order aggregation of Key [k] with [keys]
func (Key) Greater ¶ added in v1.10.14
Greater returns true if current Key is greater than other Key
func (Key) HasPrefix ¶ added in v1.10.14
HasPrefix returns true iff [prefix] is a prefix of [k] or equal to it.
func (Key) HasStrictPrefix ¶ added in v1.10.14
HasStrictPrefix returns true iff [prefix] is a prefix of [k] but is not equal to it.
func (Key) Skip ¶ added in v1.10.14
Skip returns a new Key that contains the last k.length-bitsToSkip bits of [k].
type MerkleDB ¶ added in v1.10.2
type MerkleDB interface { database.Database Clearer Trie MerkleRootGetter ProofGetter ChangeProofer RangeProofer Prefetcher }
type MerkleRootGetter ¶ added in v1.10.3
type MockMerkleDB ¶ added in v1.10.2
type MockMerkleDB struct {
// contains filtered or unexported fields
}
MockMerkleDB is a mock of MerkleDB interface.
func NewMockMerkleDB ¶ added in v1.10.2
func NewMockMerkleDB(ctrl *gomock.Controller) *MockMerkleDB
NewMockMerkleDB creates a new mock instance.
func (*MockMerkleDB) Clear ¶ added in v1.10.16
func (m *MockMerkleDB) Clear() error
Clear mocks base method.
func (*MockMerkleDB) Close ¶ added in v1.10.2
func (m *MockMerkleDB) Close() error
Close mocks base method.
func (*MockMerkleDB) CommitChangeProof ¶ added in v1.10.2
func (m *MockMerkleDB) CommitChangeProof(ctx context.Context, proof *ChangeProof) error
CommitChangeProof mocks base method.
func (*MockMerkleDB) CommitRangeProof ¶ added in v1.10.2
func (m *MockMerkleDB) CommitRangeProof(ctx context.Context, start, end maybe.Maybe[[]byte], proof *RangeProof) error
CommitRangeProof mocks base method.
func (*MockMerkleDB) Compact ¶ added in v1.10.2
func (m *MockMerkleDB) Compact(start, limit []byte) error
Compact mocks base method.
func (*MockMerkleDB) Delete ¶ added in v1.10.2
func (m *MockMerkleDB) Delete(key []byte) error
Delete mocks base method.
func (*MockMerkleDB) EXPECT ¶ added in v1.10.2
func (m *MockMerkleDB) EXPECT() *MockMerkleDBMockRecorder
EXPECT returns an object that allows the caller to indicate expected use.
func (*MockMerkleDB) Get ¶ added in v1.10.2
func (m *MockMerkleDB) Get(key []byte) ([]byte, error)
Get mocks base method.
func (*MockMerkleDB) GetChangeProof ¶ added in v1.10.2
func (m *MockMerkleDB) GetChangeProof(ctx context.Context, startRootID, endRootID ids.ID, start, end maybe.Maybe[[]byte], maxLength int) (*ChangeProof, error)
GetChangeProof mocks base method.
func (*MockMerkleDB) GetMerkleRoot ¶ added in v1.10.2
GetMerkleRoot mocks base method.
func (*MockMerkleDB) GetRangeProof ¶ added in v1.10.2
func (m *MockMerkleDB) GetRangeProof(ctx context.Context, start, end maybe.Maybe[[]byte], maxLength int) (*RangeProof, error)
GetRangeProof mocks base method.
func (*MockMerkleDB) GetRangeProofAtRoot ¶ added in v1.10.2
func (m *MockMerkleDB) GetRangeProofAtRoot(ctx context.Context, rootID ids.ID, start, end maybe.Maybe[[]byte], maxLength int) (*RangeProof, error)
GetRangeProofAtRoot mocks base method.
func (*MockMerkleDB) Has ¶ added in v1.10.2
func (m *MockMerkleDB) Has(key []byte) (bool, error)
Has mocks base method.
func (*MockMerkleDB) HealthCheck ¶ added in v1.10.2
func (m *MockMerkleDB) HealthCheck(arg0 context.Context) (any, error)
HealthCheck mocks base method.
func (*MockMerkleDB) NewBatch ¶ added in v1.10.2
func (m *MockMerkleDB) NewBatch() database.Batch
NewBatch mocks base method.
func (*MockMerkleDB) NewIterator ¶ added in v1.10.2
func (m *MockMerkleDB) NewIterator() database.Iterator
NewIterator mocks base method.
func (*MockMerkleDB) NewIteratorWithPrefix ¶ added in v1.10.2
func (m *MockMerkleDB) NewIteratorWithPrefix(prefix []byte) database.Iterator
NewIteratorWithPrefix mocks base method.
func (*MockMerkleDB) NewIteratorWithStart ¶ added in v1.10.2
func (m *MockMerkleDB) NewIteratorWithStart(start []byte) database.Iterator
NewIteratorWithStart mocks base method.
func (*MockMerkleDB) NewIteratorWithStartAndPrefix ¶ added in v1.10.2
func (m *MockMerkleDB) NewIteratorWithStartAndPrefix(start, prefix []byte) database.Iterator
NewIteratorWithStartAndPrefix mocks base method.
func (*MockMerkleDB) NewView ¶ added in v1.10.2
func (m *MockMerkleDB) NewView(ctx context.Context, changes ViewChanges) (View, error)
NewView mocks base method.
func (*MockMerkleDB) PrefetchPath ¶ added in v1.10.13
func (m *MockMerkleDB) PrefetchPath(key []byte) error
PrefetchPath mocks base method.
func (*MockMerkleDB) PrefetchPaths ¶ added in v1.10.13
func (m *MockMerkleDB) PrefetchPaths(keys [][]byte) error
PrefetchPaths mocks base method.
func (*MockMerkleDB) Put ¶ added in v1.10.2
func (m *MockMerkleDB) Put(key, value []byte) error
Put mocks base method.
func (*MockMerkleDB) VerifyChangeProof ¶ added in v1.10.2
func (m *MockMerkleDB) VerifyChangeProof(ctx context.Context, proof *ChangeProof, start, end maybe.Maybe[[]byte], expectedEndRootID ids.ID) error
VerifyChangeProof mocks base method.
type MockMerkleDBMockRecorder ¶ added in v1.10.2
type MockMerkleDBMockRecorder struct {
// contains filtered or unexported fields
}
MockMerkleDBMockRecorder is the mock recorder for MockMerkleDB.
func (*MockMerkleDBMockRecorder) Clear ¶ added in v1.10.16
func (mr *MockMerkleDBMockRecorder) Clear() *gomock.Call
Clear indicates an expected call of Clear.
func (*MockMerkleDBMockRecorder) Close ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) Close() *gomock.Call
Close indicates an expected call of Close.
func (*MockMerkleDBMockRecorder) CommitChangeProof ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) CommitChangeProof(ctx, proof any) *gomock.Call
CommitChangeProof indicates an expected call of CommitChangeProof.
func (*MockMerkleDBMockRecorder) CommitRangeProof ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) CommitRangeProof(ctx, start, end, proof any) *gomock.Call
CommitRangeProof indicates an expected call of CommitRangeProof.
func (*MockMerkleDBMockRecorder) Compact ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) Compact(start, limit any) *gomock.Call
Compact indicates an expected call of Compact.
func (*MockMerkleDBMockRecorder) Delete ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) Delete(key any) *gomock.Call
Delete indicates an expected call of Delete.
func (*MockMerkleDBMockRecorder) Get ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) Get(key any) *gomock.Call
Get indicates an expected call of Get.
func (*MockMerkleDBMockRecorder) GetChangeProof ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetChangeProof(ctx, startRootID, endRootID, start, end, maxLength any) *gomock.Call
GetChangeProof indicates an expected call of GetChangeProof.
func (*MockMerkleDBMockRecorder) GetMerkleRoot ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetMerkleRoot(ctx any) *gomock.Call
GetMerkleRoot indicates an expected call of GetMerkleRoot.
func (*MockMerkleDBMockRecorder) GetProof ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetProof(ctx, keyBytes any) *gomock.Call
GetProof indicates an expected call of GetProof.
func (*MockMerkleDBMockRecorder) GetRangeProof ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetRangeProof(ctx, start, end, maxLength any) *gomock.Call
GetRangeProof indicates an expected call of GetRangeProof.
func (*MockMerkleDBMockRecorder) GetRangeProofAtRoot ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetRangeProofAtRoot(ctx, rootID, start, end, maxLength any) *gomock.Call
GetRangeProofAtRoot indicates an expected call of GetRangeProofAtRoot.
func (*MockMerkleDBMockRecorder) GetValue ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetValue(ctx, key any) *gomock.Call
GetValue indicates an expected call of GetValue.
func (*MockMerkleDBMockRecorder) GetValues ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) GetValues(ctx, keys any) *gomock.Call
GetValues indicates an expected call of GetValues.
func (*MockMerkleDBMockRecorder) Has ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) Has(key any) *gomock.Call
Has indicates an expected call of Has.
func (*MockMerkleDBMockRecorder) HealthCheck ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) HealthCheck(arg0 any) *gomock.Call
HealthCheck indicates an expected call of HealthCheck.
func (*MockMerkleDBMockRecorder) NewBatch ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) NewBatch() *gomock.Call
NewBatch indicates an expected call of NewBatch.
func (*MockMerkleDBMockRecorder) NewIterator ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) NewIterator() *gomock.Call
NewIterator indicates an expected call of NewIterator.
func (*MockMerkleDBMockRecorder) NewIteratorWithPrefix ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) NewIteratorWithPrefix(prefix any) *gomock.Call
NewIteratorWithPrefix indicates an expected call of NewIteratorWithPrefix.
func (*MockMerkleDBMockRecorder) NewIteratorWithStart ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) NewIteratorWithStart(start any) *gomock.Call
NewIteratorWithStart indicates an expected call of NewIteratorWithStart.
func (*MockMerkleDBMockRecorder) NewIteratorWithStartAndPrefix ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) NewIteratorWithStartAndPrefix(start, prefix any) *gomock.Call
NewIteratorWithStartAndPrefix indicates an expected call of NewIteratorWithStartAndPrefix.
func (*MockMerkleDBMockRecorder) NewView ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) NewView(ctx, changes any) *gomock.Call
NewView indicates an expected call of NewView.
func (*MockMerkleDBMockRecorder) PrefetchPath ¶ added in v1.10.13
func (mr *MockMerkleDBMockRecorder) PrefetchPath(key any) *gomock.Call
PrefetchPath indicates an expected call of PrefetchPath.
func (*MockMerkleDBMockRecorder) PrefetchPaths ¶ added in v1.10.13
func (mr *MockMerkleDBMockRecorder) PrefetchPaths(keys any) *gomock.Call
PrefetchPaths indicates an expected call of PrefetchPaths.
func (*MockMerkleDBMockRecorder) Put ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) Put(key, value any) *gomock.Call
Put indicates an expected call of Put.
func (*MockMerkleDBMockRecorder) VerifyChangeProof ¶ added in v1.10.2
func (mr *MockMerkleDBMockRecorder) VerifyChangeProof(ctx, proof, start, end, expectedEndRootID any) *gomock.Call
VerifyChangeProof indicates an expected call of VerifyChangeProof.
type Prefetcher ¶ added in v1.10.13
type Prefetcher interface { // PrefetchPath attempts to load all trie nodes on the path of [key] // into the cache. PrefetchPath(key []byte) error // PrefetchPaths attempts to load all trie nodes on the paths of [keys] // into the cache. // // Using PrefetchPaths can be more efficient than PrefetchPath because // the underlying view used to compute each path can be reused. PrefetchPaths(keys [][]byte) error }
type Proof ¶
type Proof struct { // Nodes in the proof path from root --> target key // (or node that would be where key is if it doesn't exist). // Always contains at least the root. Path []ProofNode // This is a proof that [key] exists/doesn't exist. Key Key // Nothing if [Key] isn't in the trie. // Otherwise, the value corresponding to [Key]. Value maybe.Maybe[[]byte] }
Proof represents an inclusion/exclusion proof of a key.
func (*Proof) UnmarshalProto ¶ added in v1.10.3
func (*Proof) Verify ¶
func (proof *Proof) Verify( ctx context.Context, expectedRootID ids.ID, tokenSize int, hasher Hasher, ) error
Verify returns nil if the trie given in [proof] has root [expectedRootID]. That is, this is a valid proof that [proof.Key] exists/doesn't exist in the trie with root [expectedRootID].
type ProofGetter ¶ added in v1.10.3
type ProofNode ¶
type ProofNode struct { Key Key // Nothing if this is an intermediate node. // The value in this node if its length < [HashLen]. // The hash of the value in this node otherwise. ValueOrHash maybe.Maybe[[]byte] Children map[byte]ids.ID }
type RangeProof ¶
type RangeProof struct { // A proof that the smallest key in the requested range does/doesn't exist. // Note that this may not be an entire proof -- nodes are omitted if // they are also in [EndProof]. StartProof []ProofNode // If no upper range bound was given and [KeyValues] is empty, this is empty. // // If no upper range bound was given and [KeyValues] is non-empty, this is // a proof for the largest key in [KeyValues]. // // Otherwise this is a proof for the upper range bound. EndProof []ProofNode // This proof proves that the key-value pairs in [KeyValues] are in the trie. // Sorted by increasing key. KeyValues []KeyValue }
RangeProof is a proof that a given set of key-value pairs are in a trie.
func (*RangeProof) ToProto ¶ added in v1.10.3
func (proof *RangeProof) ToProto() *pb.RangeProof
func (*RangeProof) UnmarshalProto ¶ added in v1.10.3
func (proof *RangeProof) UnmarshalProto(pbProof *pb.RangeProof) error
func (*RangeProof) Verify ¶
func (proof *RangeProof) Verify( ctx context.Context, start maybe.Maybe[[]byte], end maybe.Maybe[[]byte], expectedRootID ids.ID, tokenSize int, hasher Hasher, ) error
Verify returns nil iff all the following hold:
- The invariants of RangeProof hold.
- [start] <= [end].
- [proof] proves the key-value pairs in [proof.KeyValues] are in the trie whose root is [expectedRootID].
All keys in [proof.KeyValues] are in the range [start, end].
If [start] is Nothing, all keys are considered > [start]. If [end] is Nothing, all keys are considered < [end].
type RangeProofer ¶ added in v1.10.3
type RangeProofer interface { // GetRangeProofAtRoot returns a proof for the key/value pairs in this trie within the range // [start, end] when the root of the trie was [rootID]. // If [start] is Nothing, there's no lower bound on the range. // If [end] is Nothing, there's no upper bound on the range. // Returns ErrEmptyProof if [rootID] is ids.Empty. // Note that [rootID] == ids.Empty means the trie is empty // (i.e. we don't need a range proof.) GetRangeProofAtRoot( ctx context.Context, rootID ids.ID, start maybe.Maybe[[]byte], end maybe.Maybe[[]byte], maxLength int, ) (*RangeProof, error) // CommitRangeProof commits the key/value pairs within the [proof] to the db. // [start] is the smallest possible key in the range this [proof] covers. // [end] is the largest possible key in the range this [proof] covers. CommitRangeProof(ctx context.Context, start, end maybe.Maybe[[]byte], proof *RangeProof) error }
type TraceLevel ¶ added in v1.10.10
type TraceLevel int
const ( DebugTrace TraceLevel = iota - 1 InfoTrace // Default NoTrace )
type Trie ¶
type Trie interface { MerkleRootGetter ProofGetter database.Iteratee // GetValue gets the value associated with the specified key // database.ErrNotFound if the key is not present GetValue(ctx context.Context, key []byte) ([]byte, error) // GetValues gets the values associated with the specified keys // database.ErrNotFound if the key is not present GetValues(ctx context.Context, keys [][]byte) ([][]byte, []error) // GetRangeProof returns a proof of up to [maxLength] key-value pairs with // keys in range [start, end]. // If [start] is Nothing, there's no lower bound on the range. // If [end] is Nothing, there's no upper bound on the range. // Returns ErrEmptyProof if the trie is empty. GetRangeProof(ctx context.Context, start maybe.Maybe[[]byte], end maybe.Maybe[[]byte], maxLength int) (*RangeProof, error) // NewView returns a new view on top of this Trie where the passed changes // have been applied. NewView( ctx context.Context, changes ViewChanges, ) (View, error) // contains filtered or unexported methods }