README
¶
go-kamt-ipld
A Go implementation of the Filecoin KAMT, the "fixed-size Keyed AMT": a sharded IPLD map keyed by fixed-length byte strings, with level skipping. The KAMT is a HAMT derivative that does not hash keys and lets links skip runs of empty levels via extensions, designed for the EVM actor's contract storage (FIP-0054), where consecutive Solidity slots share long key prefixes.
Writes are wire-compatible, bit for bit, with the reference Rust
implementation
fvm_ipld_kamt.
The fixtures/ directory holds cross-implementation vectors generated from
the Rust crate by fixtures/generator; the test suite replays them and
requires identical root CIDs and byte-identical blocks. The reader is
deliberately stricter than Rust's: it rejects a number of non-canonical
block shapes that no conformant writer produces (see the compatibility
contract in doc.go).
See doc.go for the format description, parameters and canonical form
rules, and go-hamt-ipld
for the hashed sibling structure.
Usage
import (
kamt "github.com/filecoin-project/go-kamt-ipld"
cbor "github.com/ipfs/go-ipld-cbor"
)
// the EVM actor's contract storage parameters
n, err := kamt.NewNode(cbor.NewCborStore(bs),
kamt.UseTreeBitWidth(5), kamt.UseMaxArrayWidth(1))
err = n.Set(ctx, key, value) // key is exactly 32 bytes
c, err := n.Write(ctx) // flush and get the root CID
n, err = kamt.LoadNode(ctx, store, c,
kamt.UseTreeBitWidth(5), kamt.UseMaxArrayWidth(1))
The configuration is not recorded in the serialized form; readers and writers must agree on it out of band.
Regenerating fixtures
$ cd fixtures/generator && cargo run --release
License
Dual MIT and Apache 2.
Documentation
¶
Overview ¶
Package kamt implements the Filecoin KAMT, a "fixed-size Keyed AMT": a sharded IPLD map keyed by fixed-length byte strings, with level skipping. It is wire-compatible, bit for bit, with the reference Rust implementation (fvm_ipld_kamt in ref-fvm), which defines the format; cross-implementation fixtures generated from the Rust crate are replayed by this package's tests.
The KAMT is a derivative of the Filecoin HAMT with two structural differences, both introduced to suit the EVM actor's contract storage, currently the format's only production use (see FIP-0054):
Keys are not hashed. A key is a fixed-length byte string used directly as the traversal path, consumed bitWidth bits at a time from the most significant bit of the first byte. Solidity locates storage in contiguous runs of slots; hashing would scatter them, while direct keying co-locates them under shared prefixes.
Links carry extensions. Unhashed keys with long common prefixes would otherwise force long chains of intermediate nodes each holding a single pointer. A link's extension records the skipped portion of the key path so the link points directly at the next branching (or data-bearing) node, in the manner of a Patricia tree.
Structure ¶
A node is a bitfield over 2^bitWidth slots plus a compacted pointers array holding one entry per set bit; a pointer at slot i of the bitfield lives at position popcount(bitfield, up to i) of the array. Each pointer is either a bucket of up to maxArrayWidth key-value pairs, sorted by key, or a link to a child node with its extension.
Lookup (Find) walks the key's bits: at each node, take the next bitWidth bits as a slot index; absent bit means absent key; a bucket is searched directly; a link's extension must match the next ext-length bits of the key exactly (any divergence means the key is absent), after which traversal continues below.
Set inserts into buckets until they overflow, at which point the bucket's entries and the new entry are pushed down into a new child node linked with an extension covering the longest prefix they all still share. A key that diverges partway along an existing extension splits it: a new node is inserted at the divergence with two children, the original target under the tail of the extension and the new entry, with the link above retaining the head.
Delete reverses all of this exactly. A node left with a single pointer is spliced out, merging the extensions above and below it (the reverse of a split); a node whose buckets would fit within one bucket is collapsed into one. The tree for a given set of entries is therefore canonical: the same entries under the same parameters produce the same nodes and the same root CID regardless of the order of operations that produced them. A reader rejects, rather than normalizes, blocks violating the local wire invariants listed under "Serialized form" below; global minimality (that every collapse the entries permit has been performed) is a writer obligation a reader cannot cheaply prove.
When minDataDepth is greater than zero, levels above it hold only links, never buckets; entries that would land there are pushed down into (otherwise empty) child nodes. This keeps frequently read upper nodes small.
Parameters ¶
The serialized form records none of the configuration; every reader and writer must supply identical parameters or the data will be unreadable, or worse, writes will produce divergent CIDs.
- bitWidth (1..8, default 8): bits of key consumed per level; nodes have 2^bitWidth slots.
- maxArrayWidth (default 3): entries a bucket may hold before push-down.
- minDataDepth (default 0): shallowest level allowed to hold buckets.
- keyLength (default 32): the fixed key length in bytes.
The EVM actor's contract storage (persistent and transient) uses bitWidth 5, maxArrayWidth 1, minDataDepth 0 and 32-byte big-endian U256 keys.
Serialized form ¶
Blocks are DAG-CBOR; Filecoin links them with Blake2b-256 CIDs, and links must themselves be DAG-CBOR. As IPLD Schemas:
type Node struct {
bitfield Bytes # minimal big-endian, no leading zero bytes
pointers [Pointer]
} representation tuple
type Pointer union {
| Bucket "v"
| Link "l"
} representation keyed
type Link struct {
node &Node
extLength Int # extension length in bits
extPath Bytes # skipped key bits, packed MSB-first
} representation tuple
type Bucket [KV]
type KV struct {
key Bytes # zeroless: big-endian, leading zero bytes stripped
value Any
} representation tuple
Note the keyed (single-entry map) union, unlike the Filecoin HAMT v3's kinded union. Bucket keys are stored zeroless, matching the serialization of the EVM actor's U256 keys; this package accepts and returns full-length keys and converts at the boundary. The extension path's bit length is recorded separately because it need not be a whole number of bytes; unused trailing bits of the final byte are zero.
Values are embedded as given and treated as opaque: readers check only that a value is a single well-formed CBOR item, and writers using SetRaw are responsible for the DAG-CBOR strictness of the bytes they supply. Set routes through the same single-item validation; cbor-gen generated marshalers produce strict output, but the strictness of a hand-written CBORMarshaler is not verified.
Compatibility contract ¶
For conforming input this package writes blocks byte-identical to the Rust implementation; the fixture suites (Rust-generated vectors and a chain-extracted CAR) hold that equality. The accepted-block sets are not identical: this reader deliberately rejects several non-canonical shapes the Rust reader currently accepts, none of which a conformant writer produces. Enumerated: non-minimal or out-of-range bitfield encodings; non-zeroless bucket keys; extension paths with nonzero trailing bits or a byte length disagreeing with the bit length; non-DAG-CBOR root CIDs (the Rust store layer also admits plain CBOR); uncollapsed single-pointer or bucket-collapsible non-root nodes. Conversely, node blocks followed by trailing bytes are rejected by both (Go checks in Node.UnmarshalCBOR, Rust in its decoder). Validation remains local per block: key membership under the path leading to a bucket is not verified, so a maliciously crafted tree can hold entries visible to ForEach that Find cannot reach; full verification requires traversal-aware checking, which neither implementation performs today.
Load validation enforces the local invariants of canonical form: pointer count equal to the bitfield's popcount and within 2^bitWidth, no bits set beyond the addressable slots, minimal bitfield encoding; no empty nodes except a root with no entries at all; buckets non-empty, within maxArrayWidth, strictly sorted, keys zeroless, and only at or below minDataDepth; extension lengths a multiple of bitWidth and shorter than the key bits remaining at their depth, with zeroed trailing path bits.
Usage considerations ¶
The KAMT provides no key privacy and no defence against adversarial key choice: with no hashing, whoever chooses keys chooses the shape of the tree. Extensions make deliberately deep paths cheap to represent (a shared 250-bit prefix costs one extension, not 50 levels), but the caller remains responsible for key distribution in adversarial settings, as the EVM does by deriving storage slots from Keccak-256 where user input is involved.
Mutations accumulate in memory until Flush or Write; blocks are written bottom-up so links always address flushed children.
Index ¶
- Variables
- type Bitfield
- type KV
- type Node
- func (n *Node) Delete(ctx context.Context, k []byte) (bool, error)
- func (n *Node) Find(ctx context.Context, k []byte, out cbg.CBORUnmarshaler) (bool, error)
- func (n *Node) FindRaw(ctx context.Context, k []byte) (bool, []byte, error)
- func (n *Node) Flush(ctx context.Context) error
- func (n *Node) ForEach(ctx context.Context, f func(k []byte, val *cbg.Deferred) error) error
- func (n *Node) ForEachNode(ctx context.Context, f func(info NodeInfo) error) error
- func (n *Node) MarshalCBOR(w io.Writer) error
- func (n *Node) Set(ctx context.Context, k []byte, v cbg.CBORMarshaler) error
- func (n *Node) SetIfAbsent(ctx context.Context, k []byte, v cbg.CBORMarshaler) (bool, error)
- func (n *Node) SetRaw(ctx context.Context, k []byte, raw []byte) error
- func (n *Node) UnmarshalCBOR(r io.Reader) error
- func (n *Node) Write(ctx context.Context) (cid.Cid, error)
- type NodeInfo
- type Option
- type Pointer
Constants ¶
This section is empty.
Variables ¶
var ErrMaxDepth = errors.New("attempted to traverse KAMT beyond key length")
ErrMaxDepth is returned when a key would require traversal beyond the number of levels the fixed-size key can address. With well-formed keys of the configured length this is unreachable; it indicates a key of the wrong length or a corrupt structure.
Functions ¶
This section is empty.
Types ¶
type Bitfield ¶
Bitfield records which of a node's 2^bitWidth slots are occupied. It is serialized as a minimal (no leading zeros) big-endian byte string, the same wire form the Rust implementation produces from its fixed [u64; 4].
type KV ¶
KV is a key-value pair held in a bucket. In memory Key is always the full configured key length; on the wire it is stored zeroless (big-endian with leading zero bytes stripped), matching the serialization of the EVM actor's U256 keys.
type Node ¶
type Node struct {
Bitfield Bitfield
Pointers []*Pointer
// contains filtered or unexported fields
}
Node is a single block of a KAMT: a bitfield recording which of the 2^bitWidth slots are occupied, and a compacted array with one Pointer per set bit. The root of a KAMT is a plain Node; no wrapper records the configuration, so a reader must know the parameters the structure was built with.
func LoadNode ¶
LoadNode loads a KAMT root from the IPLD store. The options must describe the same configuration the structure was written with; none of it is recorded in the serialized form.
func (*Node) Delete ¶
Delete removes the entry at key `k`, returning whether it was present. Deletion restores the canonical form for the remaining data, which may collapse child nodes and merge extensions back together. If an error is returned the in-memory tree may have been partially modified and should be discarded; a true return alongside an error means the entry was removed before the failure.
func (*Node) Find ¶
Find navigates to where key `k` should exist. If the key is not found, returns false. If found, returns true and, if `out` is non-nil, decodes the value into it.
func (*Node) FindRaw ¶
FindRaw performs the same function as Find but returns a copy of the raw value bytes.
func (*Node) Flush ¶
Flush writes all modified nodes below this one to the IPLD store and updates the links that point to them.
func (*Node) ForEach ¶
ForEach calls f on every key-value pair in the KAMT, in key order. Keys are presented at their full configured length; values as raw bytes. The value is shared with the tree and must be treated as read-only. This performs a full traversal, loading every reachable node.
func (*Node) ForEachNode ¶
ForEachNode calls f on every node in the KAMT, parents before children, children in key order. Structural inspection companion to ForEach: the pointers of each visited node expose buckets, links and extensions. Intended for trees loaded from a store; an unflushed tree has undefined CIDs on dirty links. This performs a full traversal, loading every reachable node.
func (*Node) SetIfAbsent ¶
SetIfAbsent adds the value at key `k` only if the key has no value already, returning whether it was added.
func (*Node) SetRaw ¶
SetRaw adds or overwrites pre-encoded value bytes at key `k`. The bytes must hold exactly one well-formed CBOR item and are copied. Well-formed is all that is checked: DAG-CBOR strictness (canonical integer widths, no indefinite lengths, tag restrictions) is not enforced and remains the caller's responsibility; non-strict value bytes are embedded, and committed to by CIDs, exactly as given. Set, which encodes through cbor-gen, always produces strict values.
type NodeInfo ¶
type NodeInfo struct {
// CID is the link the parent pointer holds for this node; undefined for
// the node ForEachNode was called on.
CID cid.Cid
// Depth is the physical depth: nodes traversed from the root, which is
// depth 0. Extensions do not contribute.
Depth int
// LogicalDepth counts key levels consumed to reach this node, including
// levels skipped by extensions. Equal to Depth in a tree with no
// extensions.
LogicalDepth int
// Node is the visited node. Read-only: it is shared with the tree.
Node *Node
}
NodeInfo describes one node visited by ForEachNode.
type Option ¶
type Option func(*config) error
Option is a configuration parameter for a KAMT instance. The configuration is not stored in the serialized form; every reader and writer of a given structure must supply identical parameters or the data will be unreadable, or worse, produce divergent CIDs on write.
func UseKeyLength ¶
UseKeyLength sets the fixed key length in bytes. Every key supplied to this KAMT must be exactly this long. The EVM actor's contract storage uses 32 (big-endian U256).
func UseMaxArrayWidth ¶
UseMaxArrayWidth sets the number of key-value pairs a bucket may hold before it is pushed down into a new child node, up to 1024 so that every writable tree round-trips through the decoder. The EVM actor's contract storage uses 1.
func UseMinDataDepth ¶
UseMinDataDepth reserves the levels above the given depth for links only; no key-value pairs will be stored in them. The default of 0 allows data in the root node.
func UseTreeBitWidth ¶
UseTreeBitWidth sets the number of bits of the key consumed at each level of the tree, from 1 to 8, giving nodes 2^bitWidth slots. The EVM actor's contract storage uses 5.
type Pointer ¶
Pointer occupies one set bit of a node's bitfield and is either a bucket of key-value pairs or a link to a child node. A link carries an extension recording any part of the key path it skips.
func (*Pointer) Extension ¶
Extension reports the key path a link skips over: its length in bits (a multiple of the tree bitWidth, zero when the link skips nothing) and the packed MSB-first path bytes. Intended for structural inspection of trees; the returned path is a copy. Meaningless for bucket pointers, which return (0, nil).
Source Files