alkblobs/docs/architecture/hashing-and-keys.md

status, last_updated, notes

status	last_updated	notes
stable	2026-10-17 (ADR-018 — the git-object derivation family registered: bytes 0x03/0x04, preimage-identity hashing over the loose form; from_git_oid_hex's contract pinned blob-family. The family's code landed against this spec — registry, derivation and hasher arms, key decode/order, the put seam — review-002 C-1 complete)	ADR-018 — the derivation-family section and the extended registry below are its landed WHAT; the code landed against it (`c1-git-object-family-impl`)

Hashing and keys

What this is

The content-address layer: the canonical hash derivation every entry is keyed under, the tolerated legacy algorithm, the typed Key/Digest surface the store API speaks, and the physical byte encoding of keys inside backends. This is the crate's one-way door: key byte layouts are persisted in backend rows and filenames, survive digest-layer evolution, and must precede any wire consumer (AGENTS convention 5; phase-0 OQ-BL-03 residual).

The hash family

Three hash-policy classes (ADR-002 §Decision; resolved from OQ-BL-03 after the "multi-hash" premise dissolved — nothing forces BLAKE3 once iroh-blobs' inheritance is rejected):

1. Canonical — git-blob-sha-256: the git oid derivation H("blob <len>\0" + content) with SHA-256, uncompressed content. Chosen because alkgit forces git's derivation by protocol definition, and every other consumer (workspaces, appfile) sees addresses, not algorithms — so one algorithm domain makes the pool one address space and cross-consumer dedup free by construction (ADR-005).
2. Tolerated legacy — git-blob-sha-1: existing git repositories are overwhelmingly SHA-1; the store accepts them under the same preamble discipline. Git's own collision-hardened SHA-1 threat model is inherited verbatim; the store adds nothing and weakens nothing.
3. Not present — BLAKE3: demoted out of the crate entirely. If a chunk-tree transfer encoding is ever adopted, it is a new decision at a new layer (ADR-006); its verified whole-contents would register as ordinary git-blob-sha-256 entries.

The git-object derivation family (ADR-018)

Registered with review-002 C-1 (alkgit's DQ-1a, POC-O-validated) as the single git-object derivation family — not a kind-x-hash matrix, because git's oid function is uniform across kinds:

• Derivation — preimage-identity. The digest is the plain hash over the stored preimage, and the stored preimage is git's loose-object form itself ("<type> <len>\0" + content — the preamble lives inside the value). A digest lookup cannot carry a kind, so the header must be in the value; the result is byte-identical to git's oid of the object, every kind included, with no store-added processing. Algorithm::derive's len parameter is inert for the family members (git's header carries the length inside the preimage).
• Registry bytes — 0x03 (git-object-sha-1, digest 20; key total 21) and 0x04 (git-object-sha-256, digest 32; key total 33), both assigned pre-publish (the one-way door's cheap window; the sha-256 sibling registered in advance so a future object-format=sha256 passthrough needs no renumbering). Total order follows the bytes — the family sorts after the blob members (0x01 < 0x02 < 0x03 < 0x04), and the sweep's live-set range scans ride unchanged.
• The ADR-002 exception, annotated. The family is preimage-identity hashing: no store-added domain separation — git's own header is the separation, inside the preimage. ADR-002 carries the annotation explicitly (ADR-018; the abstraction generalizes rather than breaks). The invariants that survive verbatim: digest length fixed per algorithm, rejects-never-guesses decode, total order, verification-on-get (read-side re-derives with key.algorithm() over the stored preimage byte-identically — verification computes under git's own oid function).
• The stat semantic. For family entries, stat's length is the stored preimage length (the loose form, header included) — not the content length; the entry's algorithm distinguishes the cases (blob entries' lengths stay content lengths). Documented on store-api.md.
• Family-explicit access. Digest/key construction from oid bytes rides the physical encoding (Key::from_bytes over [tag] + oid bytes) — family explicit, rejects-never-guesses. Digest::from_git_oid_hex stays the blob family only (its length-based 40/64-hex disambiguation is ambiguous across families once non-blob forms share the digest space; its contract is pinned as such). The ops wire surface stays blob-family in 0.1 (ADR-018; a family-explicit wire form is a named-consumer + new-ADR door).
• Public put seam. put_git_object(algorithm, len, stream) — known-length only, family members only; the shape, name, and error mapping are pinned on store-api.md.

Security posture: one algorithm across consumers is safe here — SHA-256 has no practical cross-protocol ambiguity at these input shapes, and the preamble domain-separates the derivation (ADR-002 §Consequences).

Key encoding (the one-way door)

Physical key bytes inside backends (POC #1 finding 5, validated in the interop test where an oid produced by external git addresses the same pool entry the store puts):

• Algorithm identity is part of the key itself — a per-store single-algorithm configuration cannot express git-sha-256 and git-sha-1 coexisting in one flat pool, which the external-oid test proves is required.
• The registry (ADR-002, extended by ADR-018): 0x01 = git-blob-sha-256 (32-byte digest; key total 33), 0x02 = git-blob-sha-1 (20-byte digest; key total 21), 0x03 = git-object-sha-1 (20; total 21), 0x04 = git-object-sha-256 (32; total 33), 0x00 reserved and never assigned. Fixed-length, enum-tagged: 1 algorithm byte + digest bytes per algorithm; the POC's extra "kind" tag byte is dropped — the algorithm byte is the load-bearing part. Algorithm bytes are assigned from the registry in ADR-002 (extended by ADR-018) so external producers can compute them.
• Sort stability: fixed-length enum-tagged keys sort cleanly in a total order — required for the sweep's live-set diffs (list() walks are plain range scans; ADR-005). The registry byte order is the sort order; ADR-018's family bytes sort after the blob members.
• Opaque to backends: the Backend trait speaks opaque byte keys (ADR-003); only the store core constructs and interprets typed keys.

The Key/Digest surface (WHAT the API exposes)

• Digest — an algorithm + digest pair; construction via the canonical derivation from content (known length) or from a pre-computed pair (interop: from_git_oid_hex shape validated in POC #1 finding 4). from_git_oid_hex's contract is the blob family only (ADR-018): lowercase 64-hex → git-blob-sha-256, 40-hex → git-blob-sha-1, and never a git-object family member — length cannot name a family once non-blob forms share the digest space, so it never guesses. Family-explicit construction from oid bytes rides Key::from_bytes over the physical encoding.
• Key — the typed wrapper; as_bytes() / from_bytes() are the only conversions across the backend boundary. Malformed key bytes (truncated, unknown algorithm) are rejects, never guesses — the POC's length-checking test is the standard.
• Verification semantics ride the whole-blob posture (ADR-006): put and get paths hash-check against the canonical derivation; there is no per-range hash relationship under this derivation (preamble includes the length), which is the constraint ADR-006 documents rather than works around.

Design Decisions

ADR	Decision	Summary
002	Canonical hash + key encoding	three-tier hash policy; algorithm-in-key byte layout; the declared wire-format ADR
018	The git-object derivation family	registry 0x03/0x04; preimage-identity hashing over the loose form (the annotated ADR-002 exception); from_git_oid_hex pinned blob-family; the stat semantic (OQ-15 resolved)

Open Questions

None owned by this document. The interop surface alkgit ultimately needs (oid formats, hex/binary conventions at its boundary) is OQ-07 — alkgit's question, not a key-encoding question.

References

• docs/research/phase-0.md OQ-BL-03 (resolution + key-encoding mechanics)
• docs/research/poc-trait-dispatch-findings.md findings 4/5 (byte-exact git CLI validation; tagged-key coexistence)
• gix-odb (/workspace/gitoxide/gix-odb) — the consumer-side baseline for object reads/writes
• ADR-002; ADR-018 (the derivation family and its annotated exception); ADR-003 (opaque byte keys at the backend boundary); ADR-006 (what verification is possible under this derivation)