Documentation
¶
Overview ¶
Package hamt is Lantern's proof-recording HAMT walker.
The Filecoin state tree maps `Address -> Actor` via a HAMT (hash-array-mapped trie) of bit-width 5, using sha256 as the hash function. Actor sub-state (e.g. the Init actor's address-resolution table) uses HAMTs too. See https://github.com/ipld/specs/blob/master/data-structures/hashmap.md for the IPLD HashMap spec; Filecoin's variant fixes `bucketSize = 3`.
We delegate the actual node decoding and walking to github.com/filecoin-project/go-hamt-ipld/v3 (pure Go, no CGo). Our value-add is two things:
- A BlockGetter abstraction the caller controls (cache + Bitswap + HTTP).
- A path-recording wrapper that captures every node CID fetched during a Lookup. That CID list is the inclusion (or exclusion) proof and is what Lantern's "verified by us" guarantee is built on: a third party can re-run VerifyProof against the same root and prove the value was present in the canonical state at the time of lookup.
Strictly local: this package never talks to the network. Network adapters live in net/bitswap and net/hsync; they implement BlockGetter.
Index ¶
- Constants
- Variables
- func CborStoreFromMem(m *MemBlockStore) *cbornode.BasicIpldStore
- func FilHash(k []byte) []byte
- func Lookup(ctx context.Context, root cid.Cid, key []byte, bg BlockGetter, ...) ([]byte, []cid.Cid, error)
- func LookupCBOR(ctx context.Context, root cid.Cid, key []byte, bg BlockGetter, ...) ([]cid.Cid, error)
- func VerifyBlockCID(c cid.Cid, raw []byte) error
- func VerifyProof(ctx context.Context, root cid.Cid, key []byte, value []byte, proof []cid.Cid, ...) error
- type BlockGetter
- type LookupOptions
- type MemBlockStore
- func (m *MemBlockStore) CIDs() []cid.Cid
- func (m *MemBlockStore) Get(_ context.Context, c cid.Cid) ([]byte, error)
- func (m *MemBlockStore) GetBlock(ctx context.Context, c cid.Cid) (block.Block, error)
- func (m *MemBlockStore) Has(c cid.Cid) bool
- func (m *MemBlockStore) Len() int
- func (m *MemBlockStore) Put(c cid.Cid, raw []byte) cid.Cid
- func (m *MemBlockStore) PutBlock(_ context.Context, b block.Block) error
- func (m *MemBlockStore) PutVerify(c cid.Cid, raw []byte) error
Constants ¶
const ( FilBitWidth = 5 FilBucketSize = 3 )
Defaults for the canonical Filecoin state-tree HAMT.
Variables ¶
var ErrNotFound = fmt.Errorf("key not found in HAMT")
ErrNotFound is returned by Lookup when the key is not in the HAMT.
Functions ¶
func CborStoreFromMem ¶
func CborStoreFromMem(m *MemBlockStore) *cbornode.BasicIpldStore
CborStoreFromMem returns a cbornode.IpldStore backed by an in-memory MemBlockStore. Tests use it.
func FilHash ¶
FilHash implements the go-hamt-ipld HashFunc using sha256, matching what Filecoin's state tree uses. Returns the full 32-byte digest.
func Lookup ¶
func Lookup(ctx context.Context, root cid.Cid, key []byte, bg BlockGetter, opts *LookupOptions) ([]byte, []cid.Cid, error)
Lookup walks the HAMT rooted at `root`, fetching nodes via `bg` (which must serve canonical IPLD-DAG-CBOR encoded HAMT nodes for every CID it returns). It returns the raw value bytes for the leaf, the *path of node CIDs traversed* (the inclusion proof), and an error.
If the key isn't present, Lookup returns ErrNotFound and the proof path captured up to the negative-result node (the absence proof).
func LookupCBOR ¶
func LookupCBOR(ctx context.Context, root cid.Cid, key []byte, bg BlockGetter, out cbg.CBORUnmarshaler, opts *LookupOptions) ([]cid.Cid, error)
LookupCBOR is a convenience wrapper around Lookup that unmarshals the leaf bytes into out via cbor-gen's UnmarshalCBOR interface.
func VerifyBlockCID ¶
VerifyBlockCID recomputes the CID hash over raw and returns nil iff it matches c. Exported because both state/hamt and state/amt callers want it.
func VerifyProof ¶
func VerifyProof(ctx context.Context, root cid.Cid, key []byte, value []byte, proof []cid.Cid, blockGet BlockGetter, opts *LookupOptions) error
VerifyProof independently re-verifies an inclusion-proof: given a root CID, a key, an expected value, and a proof path (list of node CIDs in fetch order), it loads each node from blockGet, walks the HAMT, and confirms the key resolves to value. Returns nil on success.
Crucially, blockGet here is typically a *fresh* MemBlockStore seeded only with the proof-path bytes — that's how a third party can audit a claim "Lantern claimed addr X had balance Y at state root R" using nothing but the proof bytes Lantern published.
Types ¶
type BlockGetter ¶
BlockGetter is the minimal interface Lantern's state layer needs from a block source. It is satisfied by:
- state/cache (local Badger blockstore)
- net/bitswap (Bitswap client)
- net/hsync (HTTP gateway client)
- net/combined (the cache+bitswap+http fallback chain)
- testdata fixtures (MemBlockStore in this package)
Get returns the raw IPLD block bytes for the given CID, or an error. The caller is responsible for verifying the CID against the returned bytes; for safety, all Lantern-internal BlockGetter wrappers re-hash on the way out.
type LookupOptions ¶
type LookupOptions struct {
// BitWidth selects the HAMT bit-width. Default FilBitWidth (5).
BitWidth int
// HashAlgo selects the hashing function. Default FilHash (sha256).
HashAlgo func([]byte) []byte
}
Options on a single Lookup call.
type MemBlockStore ¶
type MemBlockStore struct {
// contains filtered or unexported fields
}
MemBlockStore is an in-memory BlockGetter used for tests and fixture replay. It also implements the go-ipld-cbor IpldBlockstore interface so it can be plugged into go-hamt-ipld and go-amt-ipld directly.
func NewMemBlockStore ¶
func NewMemBlockStore() *MemBlockStore
NewMemBlockStore returns an empty MemBlockStore.
func (*MemBlockStore) CIDs ¶
func (m *MemBlockStore) CIDs() []cid.Cid
CIDs returns the list of stored CIDs (unordered).
func (*MemBlockStore) Has ¶
func (m *MemBlockStore) Has(c cid.Cid) bool
Has reports whether a block is present.
func (*MemBlockStore) Len ¶
func (m *MemBlockStore) Len() int
Len returns the number of stored blocks.
func (*MemBlockStore) Put ¶
Put stores raw bytes under their CID. Returns the CID for chaining. It does not re-validate that c.Hash matches the bytes; callers wanting to import untrusted data should use PutVerify.
Source Files