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

status, last_updated, notes

status	last_updated	notes
reviewed	2026-10-18 (ADR-020 — the length-routed surface is deleted with the defaults it embodied: `Digest::from_git_oid_hex` and `Digest::derive`'s silent canonical form; family-explicit construction is `Key::from_bytes` or the explicit `Algorithm::derive` derivation, the wire ingress decodes tag-prefixed key hex. The family's registry/derivation/decode record (ADR-018) stands unchanged. Verified landed — wave 14, 2026-10-19 (the shrunk construction surface verified by the fuzz corpus-replay key_encoding invariants and the derived-key tests))	ADR-018 — the derivation-family section and the extended registry below stand as its landed WHAT. ADR-020 — the Key/Digest surface's address-forming constructors are family-explicit only (below), and the wire form is tag-prefixed key hex

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 — the length-routed constructor, whose blob-family-only contract ADR-018 pinned — is deleted (ADR-020 §Decision 5): a length-implied address-forming surface is the defect class the invariant forbids, and the wire ingress it formerly served decodes tag-prefixed key hex directly. The wire form is tag-prefixed key hex (ADR-020); the wire couples only to the frozen registry bytes.
• The put seam. One derivation-explicit write surface: put_as(algorithm, len: Option<u64>, stream) — the crate never picks a derivation for its caller; the shape and error mapping are pinned on store-api.md (ADR-020 §Decision 5; put and put_git_object are deleted with the default they embodied).

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 is family-explicit only (ADR-020 §Decision 5): derivation from content goes through the explicit Algorithm::derive form (the silent canonical constructor's Digest::derive fold is deleted), and pre-computed pairs come in as typed keys (Key::from_bytes over the physical encoding — the interop surface validated in POC #1 finding 4, in its tag-prefixed form). The length-routed Digest::from_git_oid_hex constructor is deleted with the defaults it embodied.
• 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 entry key's own derivation (verification-on-get is derivation-parameterized — key.algorithm(), ADR-018 §Decision 1); 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 key-encoding wire-format ADR
018	The git-object derivation family	registry 0x03/0x04; preimage-identity hashing over the loose form (the annotated ADR-002 exception); the stat semantic (OQ-15 resolved)
020	Family-explicit address formation	the length-routed constructors die (from_git_oid_hex, Digest::derive's silent form); family-explicit construction is Key::from_bytes / explicit Algorithm::derive; the wire form is tag-prefixed key hex

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)