@dclimate/ipld-index

Content-addressed index structures over IPLD blocks: a HAMT, a sharded-root placeholder, a reference Kubo block store, and — the part that did not exist anywhere before — a frozen conformance suite generated from py-hamt.

Implements docs/ipld-index-proposal.md.

npm install @dclimate/ipld-index

Why this exists

Three repositories (py-hamt, jaxray, dparquet) independently contained the same layer, none named for it. py-hamt ships a HAMT plus a Zarr store plus a CAS plus ChaCha20 encryption; jaxray has no subpath exports, so importing its HAMT drags in zarrita and an HTTP client. This package is that layer on its own, with the coupling removed and the wire format pinned.

Subpath exports

Load-bearing, not cosmetic — a consumer importing /hamt gets the HAMT and nothing else: no HTTP client, no Zarr, no encryption.

| Export | Contents | | --- | --- | | @dclimate/ipld-index | types, errors, version constants | | @dclimate/ipld-index/hamt | node codec, extractBits, Hamt, HamtBuilder, blake3 hasher | | @dclimate/ipld-index/sharded | version discriminants only — deliberately unfrozen | | @dclimate/ipld-index/kubo | KuboCas (BlockStore + RangeSource), MemoryBlockStore | | @dclimate/ipld-index/vectors | golden conformance vectors + runner helpers |

The import rule: /hamt and /sharded must never import /kubo. Dependencies point one way — transport may know about the BlockStore interface; index structures must not know about transport. This is enforced by a lint rule and by test/layering.test.ts, which resolves /hamt's whole module graph and asserts it reaches no transport code and no package beyond the three permitted dependencies (@ipld/dag-cbor, multiformats, @noble/hashes).

Usage

import { Hamt, HamtBuilder } from '@dclimate/ipld-index/hamt'
import { KuboCas } from '@dclimate/ipld-index/kubo'

const store = new KuboCas({ apiUrl: 'http://127.0.0.1:5001' })

// Write: buffers dirty nodes, writes bottom-up on flush().
const builder = HamtBuilder.create(store, { bucketSize: 4 })
await builder.set('USW00094728', valueCid)
const root = await builder.flush()

// Read: a root CID only ever comes from flush().
const hamt = Hamt.load(store, root)
await hamt.get('USW00094728')
for await (const [key, cid] of hamt.entries()) { /* … */ }

Bring your own block store

The package takes a store; it does not own one:

interface BlockStore {
  get(cid: CID): Promise<Uint8Array>
  put(cid: CID, bytes: Uint8Array): Promise<void>
  has(cid: CID): Promise<boolean>
}

dparquet's BlockStore satisfies this structurally today. Read-only consumers may pass a store whose put/has throw — the Hamt read path never calls them.

Wire format — frozen (hamt/0)

A node is a dag-cbor array of exactly 256 elements. No named fields, no bitmap, no header.

Node    := dag-cbor array, length exactly 256
Node[i] := Bucket | Link
Bucket  := CBOR map { utf8-string key -> CID }    // empty map {} = empty slot
Link    := CBOR array of length 1, [ CID ]        // child node

Discrimination on read: array ⇒ link, map ⇒ bucket.

• Hash: BLAKE3, 32-byte output, over utf8(key). No normalization, no salt, no length prefix. (é NFC and é NFD are different keys.)
• Slot index at depth d: hash[d]. extractBits(hash, d, 8) reduces to exactly this; the general form is kept for conformance with py-hamt's extract_bits.
• Bucket overflow: when a bucket is full and the key is absent, drain the bucket plus the new entry into a child one level deeper, cascading as needed.
• Bucket size is write-time tuning only. A reader walks buckets and links structurally and never needs to know it.

Two things this package pins that py-hamt leaves ambiguous

1. Pointers are CIDs (dag-cbor tag 42), always. py-hamt emits raw 34-byte multihashes under InMemoryCAS and real CIDs under KuboCAS — different bytes on the wire for the same logical tree. Only CIDs are permitted here.
2. Values are CIDs, not inline data. py-hamt supports arbitrary IPLDKind values and a values_are_bytes flag that changes stored bytes. Restricting to CIDs matches every real consumer and removes a format variable. decodeNode rejects a non-CID bucket value rather than accepting it.

Determinism

The same key/value set yields the same root CID regardless of insertion order, and delete re-canonicalizes — for a fixed bucket size. Different bucket sizes produce different tree shapes and different roots for identical data. This is a documented property, not a bug, and it is why bucket size belongs in the consumer's version discriminant.

Versioning

None of the three existing implementations has a version field, magic bytes, or a parameter block: a reader that guesses wrong does not error, it misparses. This package does not change the node format to fix that — that would fork compatibility with py-hamt and jaxray, throwing away the one thing that currently works. Instead it exports its parameters as data, for consumers to record in their own root:

{ kind: 'hamt/0', hash: 'blake3', bits: 8, bucketSize: 4, root: CID }

Format changes get a new constant (hamt/1) and a new vector set.

Conformance vectors

Twelve vectors, generated from py-hamt via a CID-emitting CAS, each carrying its full block set so consumers verify offline with no IPFS daemon:

| Vector | What it catches | | --- | --- | | empty | the degenerate all-{} root | | single-key | one bucket, no links | | bucket-full | boundary before split | | bucket-overflow | 5 keys colliding on the depth-0 slot: first split | | deep-cascade | collision at depth 0 and 1: split cascades two levels | | 500-keys-bucket-4 | scale; mirrors py-hamt's own fixture | | 300-keys-bucket-1 | non-default tuning ⇒ different shape, same data | | order-{ascending,shuffled,reverse} | one root CID from three insertion orders | | delete-to-collapse | the _collapse_delete_path re-canonicalization case | | unicode-and-empty-keys | empty string, astral plane, combining marks, embedded NUL |

Note that sequentially-numbered keys scatter across all 256 root slots, so a naive "5 keys" case never fills a bucket and never splits. The split vectors are constructed from the hash, not assumed.

import { vectors, vectorStore, vectorRoot } from '@dclimate/ipld-index/vectors'
import { Hamt } from '@dclimate/ipld-index/hamt'

for (const vector of vectors) {
  const hamt = Hamt.load(vectorStore(vector), vectorRoot(vector))
  // assert against vector.entries …
}

Regenerate (requires py-hamt checked out beside this repo, with its virtualenv):

../py-hamt/.venv/bin/python scripts/generate-vectors.py > src/vectors/vectors.json

/kubo

The merged client: dparquet's verified IPLD operations plus jaxray's resilience layer.

const cas = new KuboCas({
  gatewayUrl: ['http://gw1.example', 'http://gw2.example'],  // multiple ⇒ failover
  concurrency: 32,
  maxRetries: 3,
})

Retries with jittered exponential backoff, Retry-After honoring, a concurrency semaphore, gateway failover with circuit breaking, and pinning are all internal — configured through KuboCasOptions, not exposed as API surface.

Full blocks are verified locally before being returned. Ranges intentionally are not hash-verified: a byte range does not contain enough information to recompute its CID. getRange handles gateways that ignore Range and answer 200 by slicing locally.

offline — read this before pointing it at a daemon

Kubo's block/get and refs treat a missing block as a network lookup and will walk the DHT indefinitely rather than answering "not here". Measured against Kubo 0.39, an absent CID hangs past 120 s by default and returns in ~40 ms with offline=true.

• has() always sends offline=true. A local existence check that consults the DHT is not an existence check.
• get() / getBlock() / refs() honor the offline option, default false — because fetching a block you do not yet hold is the entire point of IPFS. Set offline: true for a purely local store, where missing should fail fast:

const local = new KuboCas({ offline: true })

Note that refs() walks values as well as index nodes. If a HAMT's values are CIDs whose blocks live elsewhere, a recursive offline walk will correctly report it cannot fetch them — walk the node links directly if you only mean to verify the index structure.

onlyIfCached — the same question, asked of a gateway

offline is an RPC query parameter aimed at the daemon API. Range reads go to the gateway, which has no such parameter, so local-only ranges need the HTTP header instead:

const local = new KuboCas({ offline: true, onlyIfCached: true })

They are separate flags rather than one because in a multi-gateway configuration they address different hosts — a caller with a local daemon plus public gateways legitimately wants offline: true with onlyIfCached: false.

A gateway that lacks the block answers 412. That is a miss, not a fault: failover still tries the rest of the rotation, a 412 is never retried, and it does not count against a gateway's health. Only a clean sweep of 412s raises RangeNotCachedError; a mixed 412-and-500 rotation reports the real failure instead. Measured against a networked daemon, an absent block goes from an ~18 s stall to a 0 s answer.

The header is advisory. A gateway that ignores Range generally ignores this too and may answer 200 from the network, which is indistinguishable from a cache hit here — the 200-slice path is preserved for correctness, not as cache-miss protection.

/sharded is deliberately unfrozen

Only the version discriminants ship today. The proposal declines to specify the format until both profiles have a real consumer — dense/0 for the Zarr case, sparse/0 for the bbox-pruned geo projection — so the two can be designed against each other rather than one being guessed from the other.

Browser support

/hamt, /sharded, and /vectors are pure computation over Uint8Array; /kubo speaks fetch, which browsers have. There are no Node built-ins, no Node-only globals, and the only three dependencies are browser-safe.

// Inject fetch to add auth, a proxy, or a test double.
new KuboCas({ gatewayUrl: 'https://gw.example', fetchFn: window.fetch.bind(window) })

Enforced two ways: test/browser.test.ts asserts statically that no source file imports node:* or touches process/Buffer/__dirname, and scripts/browser-check.mjs is a runtime proof that deletes process, Buffer, and global before importing the built package and then verifies all 12 conformance vectors.

npm run check:browser

Note that a KuboCas pointed at 127.0.0.1:5001 from a browser needs CORS configured on the daemon; a public gateway URL for reads needs no such setup.

Development

npm run check          # typecheck + lint + test
npm run build          # emit dist/ with declarations
npm run check:browser  # runtime proof the package runs without Node globals
npm run test:live      # live-daemon tests (auto-skip when no Kubo is running)

Live-daemon tests skip themselves when nothing answers at KUBO_API_URL (default http://127.0.0.1:5001), so the suite stays green without one. They cover what a mocked fetch structurally cannot: real block/put round-trips, real UnixFS chunking, pinning, and — most importantly — that the conformance root CIDs reproduce identically on real storage, proving the wire format does not depend on where blocks land.

no-await-in-loop is off by design: every await-in-loop here is inherently sequential — HAMT tree descent (each level's CID comes from the previous node), retry backoff, and gateway failover. Parallelizing them would be incorrect, not faster.