Status: Accepted Resolves: the default hasher, left open by ADR-296 Related: ADR-283 (the edges trust travels along), ADR-005 D3 and D8 (the ledger and its determinism), ADR-017 (the second consumer, decided separately per D8), ADR-316 (the function within a class), ADR-037 D7-D8 (the same question for a reference count)
The threat is hash flooding: an adversary who chooses keys can drive an open-addressed table into quadratic behaviour.
The axis is provenance — where the keys came from — and not how the program is built. A single-threaded server hashing attacker-supplied header names is exactly as vulnerable as a parallel one, and a compute job over an operator-chosen file has no adversary in either. Provenance is a property of the input, known where the input enters the program, and it is the user’s call at that point rather than a global default the language picks for them.
Rust’s standard map hashes everything with a DoS-resistant function because Rust has no whole-program provenance information; with nothing to distinguish the two cases, assuming the worst everywhere is the only safe global default, and every compute workload pays for it. Nikaia already ties every view to the buffer it points into (ADR-283) and already solves whole-program contracts, so it can be exact instead of pessimistic — and pay for hardening only where an adversary exists.
Trusted ⊑ Untrusted. Every buffer entering the program carries one state,
derived values inherit it, and a container’s state is the join of what goes
into it — so a map that receives one untrusted key is untrusted. Which maps
count as one container is D9’s.
This rides machinery that exists. The trust bit travels the same edges ADR-283 already records, lands in the same ledger, and is solved by the same monotone fixpoint, so ADR-005 D8’s determinism, ban list and CI cover it unchanged. A two-element lattice adds no solver and no new pass.
Barriers widen to Untrusted — a dyn boundary, an FFI value, a Rust
dependency’s return. This is the opposite direction from
ADR-283 D5’s representation barrier, deliberately: there the
conservative answer is the wider representation, here it is the safer one. An
analysis that fails open is a vulnerability generator.
Users do not classify std. The library states, per source, who supplied the
bytes:
| Source | Default | Why |
|---|---|---|
http request line, headers, query, body; net sockets; IPC; WASM host imports |
Untrusted | a remote peer chose these bytes |
cli::args, env, compile-time data |
Trusted | the operator chose these bytes |
standard input, fs reads and maps |
Untrusted (Changed by ADR-365 D1) | a path or a pipe does not say who wrote the bytes |
db result rows |
Untrusted | second-order: a row may hold what a user stored earlier |
The database row is why “trusted = local” would be too crude: stored data is attacker-chosen data with a delay. Any source whose content can be influenced by someone other than the operator is untrusted, whatever transport it arrives on.
// A benchmark reading a file it wrote itself (ADR-365 D2).
let data = fs::map(path; trusted: true)
// A benchmark harness reading a fixture it wrote itself.
let body = socket.read_all(; trusted: true)The default is a default, not a verdict, and the decision belongs where the data enters. Both forms use the existing named-parameter convention and both are recorded in the ledger with their source location — which makes the security review of a Nikaia program a grep over one generated file, diffable across commits, rather than an audit of every call site.
The same marker is available on a function parameter, so a library can state what it assumes rather than inheriting the join of its callers.
@untrusted
grammar HttpHeaders { … }A grammar is the specification of an input format, and its author often knows
the threat model better than the person applying it. Effective trust is
join(grammar floor, buffer trust), so a grammar marked @untrusted cannot be
used in trusting mode by accident, whatever buffer it is pointed at.
There is deliberately no @trusted floor: a format cannot make its input safe.
| Effective trust | Hash |
|---|---|
Trusted |
fast non-cryptographic hash, fixed seed |
Untrusted |
keyed hash, per-process random seed |
Everything else about the map is identical: same table, same absence of per-entry allocation, same API, and the same full-content equality (ADR-283 D11, ADR-296 D14). Trust never weakens a correctness property; it selects the class of hash function.
Within a class, the function follows the keys’ shape, and a program may name its own hasher where it makes the map. Changed by ADR-316 D1 and D4.
How the program is built enters only as an implementation detail of how, never as the thing that decides whether. When and for which maps together the choice is made is D9’s.
The random seed must be real. On a target with no entropy source the build fails rather than falling back to a fixed seed: a keyed hash with a predictable key is the vulnerability wearing the mitigation’s clothes.
Randomised seeding means an untrusted map iterates differently from run to run. Stated in the spec rather than discovered; a program that needs an order asks for one. The compiler’s own ledger paths are already forbidden from iterating hash order at all (ADR-005 D8), so the rule the language enforces on itself is the rule it teaches.
--trust (on build, run, test and lower, ADR-260 D3)
prints the provenance of every buffer and the hasher
chosen for every map. Where a hardened map sits in a hot loop, a lint names the
source that made it untrusted — so “why is this slower than I expected” is one
command, and the fix is in the message.
Provenance is a taint lattice and hashing is its consumer. It is built as a mechanism rather than a hasher special case so that a further consumer — SQL parameterisation, log injection — can be decided on its own. A path is not one: where a name reaches the filesystem it names its root at the call (ADR-108), and no provenance travels a path.
One caution belongs on the record now, and is settled by
ADR-017: escaping at a template hole must stay
unconditional, defence in depth. A provenance analysis that silently skips
escaping on “trusted” data turns one wrong trusted: true into an XSS hole.
Provenance may add evidence and lints there; it may not switch escaping off.
Added October 11, 2026 (#581).
// stock.nika
pub struct Tally { pub counts: collections::HashMap[String, i64] }
pub fn count_in(mut t: Tally, word: ref String) {
t.counts[word.clone()] = 1
}
// main.nika, the same package
let mut t = Tally { counts: collections::HashMap() }
count_in(t, line) // `line` from a file: fast; from a socket: keyedD5’s choice is a choice of type in the code the compiler writes: the fast map and the keyed map are two types there, and every place that names a map has to name the same one as the value it receives. So the choice is made for classes and at one time:
let, a map
inside another type (Vec[HashMap[K, V]], HashMap[K, V]?). Positions a map
value passes between - initialised from, assigned, passed, returned, stored,
compared with ==, the arms of one if or match - are one class, and
a class is one type.pub has its class’s type, the same at every use.pub type is a
hidden type parameter of that type, one per position, in the order the
declaration writes them. A map position in the signature of a pub function
or method is one of that item’s, one per group of positions its body makes
one map (a map assigned to another, compared with ==, returned from a
parameter): a body that joins none gives each position a parameter of its
own. Each use fills them, in the package and outside it, as a use of a
generic fills its type: from the class the value it hands in or takes out
belongs to. A map the item’s own body makes at such a position is made with
the hasher the parameter holds.pub function’s entry gets
maps, one line for each group of positions: the positions it joins
(t.counts is a map field of a parameter, <result> the result) and what
its body adds to them: from(p, ...) keys as trusted as the arguments
named, from() none (nothing that is not the caller’s choice), keyed
keys it does not trust, or a barrier. A caller joins the line into its own
classes. A position no line covers is keyed. The key is read as a
permission, as sync is: a wrong from(..) would let a caller choose the
fast hash for keys an adversary picked, so only the compiler writes it, and
only where the body is read to its end: a map handed to a call, kept in a
local, matched or captured makes every line of the function keyed, and
then the positions of one written type are one group.dyn has one
compiled body), a described Rust crate’s signature (its type is the one the
crate wrote, and std’s map is keyed), and a binding for another language
(ADR-284 D26). A class holding one of them is keyed.
A pub function or method that hands a map it was given to a barrier, or
to a private function that has a map of its own in its signature, has that
position fixed keyed: a hidden parameter cannot be shown to be std’s hasher
or the class of a private declaration. A method that hands a map of self
on does so for its type: the impl’s parameters are the type’s, so the type
declares none and its maps are the keyed map, and a program that builds it
is no more trusted than that. The type a grammar rule returns, and the
accumulator of its fold, are written with the hasher the package fills
every other mention with.nikaia_std::hash::Fast and
nikaia_std::hash::Keyed. A pub type’s map parameters default to Keyed,
so Rust code that names Tally gets the map that is safe for any key, and
names Tally<Fast> where it vouches for its keys, as any Rust code that
picks a hasher does.NK1246.--trust reports classes (D7): for each, the positions in it, the type
it got, and the key or barrier that made it keyed.Why this shape.
Rejected:
Shared should follow is not decided here.HashMap[K, V, H]): rejected in
ADR-316 §4.BTreeMap and BTreeSet keep their keys sorted, so the key type needs Rust’s
Ord. The checker answers for it as it does for == (Part III NK1188),
walked structurally: the language’s own types from a list, a float and a
HashMap/HashSet as no, a declared struct or enum as no unless the
program writes impl Ord for it (ADR-341; it derives equality and
copy, not an order), and a type whose parts are Rust from the
ledger’s orders column, whose absence is no. The refusal is NK1247, at
every position a program writes a type, and it names a HashMap, or a key by a
text or a number.
A library type that is Ord says so in its ledger (winnow_grammar::Symbol
does: its order is the order of interning, not the text’s, so a map keyed by it
must not be iterated into output). nikaia describe writes the column where the
crate derives Ord.
Rejected: deriving Ord for a declared type whose parts are ordered. It
would answer the question for programs, but field order would then be a
promise, and no program has asked for it. Rejected: leaving the error to
rustc: an error about generated code reaching the user is a compiler defect
(Part III C.1).
Changed by ADR-341 D6: a declared type with an impl Ord is a key.
HashMap and HashSet find a key by its hash, so the key type needs Rust’s
Hash and an equality that is an equivalence. The checker answers for it by
the same structural walk as == (Part III NK1188): the language’s own types
from a list (a number but no float, String, bool, char, Bytes, and a
tuple, list or option of such); a float, a map and a set as no; a declared
struct or enum as yes where every part hashes; a type whose parts are Rust
from the ledger’s hashes column, whose absence is no. For a declared type
that hashes, the hash is derived from its fields, every field in the order
written, as equality is (ADR-204), so two equal values always hash alike. A
declared type with a hand-written impl Eq (ADR-341 D5) does not hash unless
it also has an impl Hash (D12): its equality is no longer the fields’, and a
hash from the fields would disagree with it. The refusal is NK1260, at every position a program writes a type;
it names the part that does not hash, and for an impl Eq the hand-written
equality and the impl Hash that would answer it.
A text view hashes its text, not where it points. The hash function is the
one D1-D4 choose for the map’s keys; a derived hash feeds the fields to it and
does not depend on which one it is. nikaia describe writes hashes where the
crate derives Hash.
Rejected: refusing every declared type as a key. A record of a few fields
is the ordinary key of a map in every language that has one, and the
language derives what the type’s fields already say. Rejected: a hash
derived from the fields beside a hand-written equality: two values the
impl Eq calls equal may differ in a field, hash apart, and the map would not
find a key it holds. Rejected: leaving the error to rustc
(Part III C.1). Unlike an order (D10), a hash makes no promise about the
fields’ order: it is never shown and never compared.
impl Hash gives a declared type its hash by hand.trait Hash { fn hash(ref self, mut into: Hasher) sync }Hash is a trait of the language, in scope everywhere, as Eq and Ord are
(ADR-341 D1). Hasher is the language’s too: its one method, add, takes a
value that hashes by D11 and feeds it to the map’s hash function, whichever
D1-D5 chose. Hash lowers to Rust’s Hash (into.add(x) is
x.hash(state)), so a type with an impl Hash is a hash key to Rust code
as well.
struct Name { text: String }
impl Eq for Name {
fn eq(ref self, other: ref Self) -> bool sync {
return self.text.to_lowercase() == other.text.to_lowercase()
}
}
impl Hash for Name {
fn hash(ref self, mut into: Hasher) sync {
into.add(self.text.to_lowercase())
}
}A type with an impl Hash hashes, whether its equality is derived or
hand-written; the impl replaces the hash D11 would have derived. It is
written for a type the program declares and that is Eq (by the walk or by an
impl Eq); any other is NK1249, the rule of ADR-341 D5. A body that can
pause is NK1129. A value handed to add that does not hash is NK1260.
The law is the program’s: two values eq calls equal feed add the same
values. The compiler does not check it, as it does not check Eq’s laws
(ADR-341 D5). Beside a derived equality the law holds by itself, since the
body reads only the value’s fields.
Why. A hand-written equality says that values whose fields differ are the
same; only the program knows which part of a value that sameness reads, so
only the program can write a hash that agrees with it. Refusing such a type as
a key would make it the one kind of value a map cannot hold. add and not a
number the body computes: the hash function stays the map’s (D5), and a
program that writes a hash cannot weaken a hardened map.
Rejected: a body that returns a number (Java’s hashCode, Python’s
__hash__): it would choose the hash function and bypass D5. Rejected:
deriving Hash from the fields where an impl Eq exists (D11).
Not decided here: Hash as a bound ([T: Hash]), which stays ADR-341 §6’s.
A program that maps a file named on the command line gets a fast hash: the benchmark does not pay for a threat it does not have, and nobody wrote a line about hashing. Deployed to crunch uploads from strangers, the change is one named argument, and the ledger records it.
A server hashing query parameters and header names off a socket is Untrusted
by default, hardened without anyone remembering to ask, and the DSL for the wire
format can pin it so no later use can lower it.
Two shapes of program get different code from the same source text, and the difference is derived from where the bytes came from — not from a build switch, and not from a global default that is wrong for one of them.
trusted: true is a silent vulnerability. Mitigated by barriers
failing safe (D1), std owning the classification so common cases need no
judgement (D2), every override landing in one auditable file (D3), and a DSL
author being able to pin the floor beyond a user’s reach (D4).std source
without classifying it defaults to Untrusted, which is safe but may
surprise. The table is part of the module’s spec, not an implementation note.