Documentation
¶
Overview ¶
Package kamt is a read-only reader for the ref-fvm KAMT (Keccak-AMT) as used by the FEVM EVM actor for contract storage (lantern#43 Part B, Stage 2).
What a KAMT is ¶
The KAMT is a champ-like trie that, unlike the HAMT, does NOT hash its keys — it indexes a fixed-size byte-array key directly, consuming `bit_width` bits at a time from the (big-endian) key to pick a slot at each level. Solidity lays out contiguous storage slots, so the KAMT uses "extensions" (a shared key-bit prefix stored on a Link pointer) to avoid degenerate depth.
FEVM contract-storage config (builtin-actors evm/src/interpreter/system.rs) ¶
KAMT_CONFIG = { min_data_depth: 0, bit_width: 5, max_array_width: 1 }
StateKamt = Kamt<U256, U256, StateHashAlgorithm>
as_hashed_key(slot U256) = slot.to_big_endian() // 32 bytes BE, no hash
So: the "hashed key" for an eth storage slot is just the 32-byte big-endian slot number. bit_width 5 => 32 slots per node (a 4-byte bitfield). Values buckets hold a single KV (max_array_width 1).
Node CBOR layout (ref-fvm ipld/kamt) ¶
Node = [ bitfield (byte string), [ pointer, ... ] ]
Pointer = { "v": [ KV, ... ] } // Values bucket
| { "l": [ cid, extLen u32, extBytes ] } // Link (+ optional extension)
KV = [ keyBytes, valueBytes ] // both byte strings
This reader fetches every node CID-verified through the accessor's BlockGetter, so a value it returns is backed by the same end-to-end verification as the rest of Lantern's state access.
KAMT subtree walker (lantern#44).
WalkSubtree performs a bounded breadth-first traversal of a KAMT rooted at `root`, fetching every node CID it visits through the supplied BlockGetter. Its purpose is **block availability**: when `bg` is a cache-fronted fetcher (combined.Fetcher), walking the subtree pulls the storage-trie nodes into the local cache so that a later eth_call's KAMT lookup hits the cache rather than Bitswap.
The walker is intentionally narrow: it does NOT decode values, it does NOT verify keys, it does NOT enforce extensions beyond reading past them. All it does is "fetch every reachable IPLD node, up to a bound, and return how many we walked". The eth_call read path (kamt.Get) still does the real cryptographic descent + verification.
Index ¶
Constants ¶
const ( // BitWidth is bits consumed from the key per level (FEVM = 5). BitWidth = 5 // KeyLen is the fixed key length in bytes (U256 => 32). KeyLen = 32 )
FEVM contract-storage KAMT parameters.
Variables ¶
var ErrNotFound = fmt.Errorf("kamt: slot not present")
ErrNotFound is returned when a slot is absent from the KAMT (which, for eth storage, means the slot reads as zero).
Functions ¶
func Get ¶
func Get(ctx context.Context, root cid.Cid, slot [KeyLen]byte, bg hamt.BlockGetter) ([]byte, []cid.Cid, error)
Get looks up a 32-byte big-endian storage slot in the KAMT rooted at `root` and returns the raw value bytes (the stored U256, big-endian, minimal-length as encoded). Returns ErrNotFound if the slot is absent.
The returned proof path is the list of node CIDs fetched, in order, so a caller can re-verify independently if desired.
Types ¶
type WalkOptions ¶
type WalkOptions struct {
// MaxNodes caps the total number of nodes visited. Zero or negative
// means "no cap" — caller is responsible for bounding work via ctx.
MaxNodes int
// FetchRetries is the number of additional attempts made for a node
// whose first fetch fails, before the walker gives up on it (and the
// subtree below it). A transient Bitswap/gateway miss during a walk
// otherwise leaves a permanent hole in cache coverage: the failed
// node's children are never queued, so a later eth_call SLOAD into
// that subtree misses and falls back to the bridge. Retrying closes
// that gap for contracts with large/deep storage tries (e.g.
// FilecoinPay) where the read path is fine but the bulk walk races
// the network. Zero means no retry (legacy best-effort behaviour).
FetchRetries int
// RetryBackoff is the base delay between fetch retries (linear:
// attempt n waits n*RetryBackoff). Zero defaults to 150ms when
// FetchRetries > 0.
RetryBackoff time.Duration
// OnNode, if set, is called once for each successfully fetched and
// CID-verified node in the subtree (root included). The PDP tier uses
// this to PIN the walked contract-state nodes in the persistent block
// cache, so the warm set the node proves/settles against is never
// LRU-evicted. Must be cheap and non-blocking; it runs inline on the
// walk goroutine. Nil disables (light-node behaviour).
OnNode func(cid.Cid)
}
WalkOptions controls a WalkSubtree run.
type WalkStats ¶
type WalkStats struct {
NodesFetched int // total IPLD nodes successfully fetched
BytesFetched int64 // total raw block bytes
Errors int // node-fetch / decode errors encountered (BFS continues past these)
Capped bool // true if MaxNodes was hit before the walk finished
}
WalkStats is the per-walk summary returned by WalkSubtree.
func WalkSubtree ¶
func WalkSubtree(ctx context.Context, root cid.Cid, bg hamt.BlockGetter, opts WalkOptions) (WalkStats, error)
WalkSubtree walks the KAMT rooted at `root` breadth-first through bg, visiting at most opts.MaxNodes nodes. It returns when the BFS frontier is empty, the cap is hit, or ctx is done.
Errors from individual node fetches are counted but do not abort the walk: the goal is best-effort cache-warming, not exhaustiveness. Returns an error only if root itself is undefined or ctx fails before any node is visited.
Source Files