Identifiers minted from crypto/rand make a replay diverge from its recording, and three replay checks are weakened for it

[scttfrdmn]

Substrate mints most of its identifiers from crypto/rand, so a recorded run and its replay produce different identifiers. This is the shared prerequisite of #833 and #817, and no issue covers it.

grep across non-test emulator/ code: 78 generate* functions, in 31 files that import crypto/rand. Nearly all draw from it directly.

What it blocks, concretely

#833 — authorization fidelity. A stream containing a mid-stream CreateAccessKey or AssumeRole mints a different AKIA…/session token on replay. The recorded Authorization header then names a key that is absent from replayed state, resolvePrincipal returns nil, and CheckAccess fails open the instant reqCtx.Principal == nil:

	if reqCtx.Principal == nil {
		return nil
	}

(emulator/authz.go:151-153)

So a replay of a recorded stream would authorize everything — the opposite of the fidelity #833 asks for — and it would do so silently.

#817 — body comparison. Any create whose response carries a generated identifier diverges, so a strict body differ reports a mismatch on essentially every mutating event. Criterion 3 of #817 assumes the opposite.

State-hash validation. As of the v0.115.0 reporting work, IncludeStateHashes is honoured and ValidateState actually runs. A stream containing any create now reports a state_hash_after mismatch, because the state key or record contents embed the freshly minted identifier. That is the correct answer — the divergence is real — but it means state validation is only useful once identifiers are reproducible.

The convention already exists in two places and was never generalised

• CloudFormation derives its stack and change-set UUIDs from account + region + name (docs/services.md:1414-1418), specifically so a redeploy and a replay mint the same value.
• error_protocol.go:10-14 states the principle outright: substrateRequestID = "SUBSTRATE" is a fixed constant because "an error body has to be byte-identical across two replays of one recorded run".
• Config rules do the same (configservice_rules.go:412): "AWS mints an opaque config-rule-xxxxxx; substrate derives it by hash so replaying …".

So the design question is not whether to derive rather than randomise, but what to derive from, given that the same operation may legitimately be called twice in one run with identical inputs (two CreateAccessKey calls for one user must produce two distinct keys).

The design question this issue has to answer first

A pure hash of the request is wrong for exactly that reason. The candidate inputs, and what each costs:

Source	Reproducible?	Distinguishes repeat calls?	Notes
account + region + name	yes	n/a (name is the discriminator)	works for named resources; CFN's approach
hash(request)	yes	no	two identical creates collide
hash(request + event sequence)	yes	yes	needs the plugin to see the sequence number, which it does not today
a seeded PRNG per stream	yes	yes	needs a seeded source threaded to every mint site; ReplayEngine.RandInt64 already exists (replay.go:642) but is reachable by nothing
a monotonic per-namespace counter in state	yes	yes	reproducible because it is state, which replay resets; needs a state write per mint

Note that ReplayEngine already carries a seeded rng and exposes RandFloat64/RandInt64 (replay.go:629-647), and ReplayConfig.RandomSeed is plumbed — but no plugin can reach any of them, because a plugin holds no reference to the replay engine. That is the missing wiring, whichever source is chosen.

Whether the answer is one mechanism for all 78 sites or a per-shape choice (ARNs and names derived from inputs; opaque tokens from a seeded source) is the first decision, and it should be made before either replay issue is scheduled.

Acceptance criteria

• A written decision on the identifier source, recorded where the existing conventions are (docs/services.md, alongside the CloudFormation UUID note) rather than only in code.
• A single seam every mint site goes through, so the answer cannot be given two ways in two plugins — the same "one builder, so they cannot drift" structure SQS state keys disagree: the tagging API and the authorizer address queue:<name>, the plugin writes queue:<account>/<name> #826 established for ARNs.
• Two identical create calls in one run still produce distinct identifiers. This is the criterion a naive hash(request) fails, and it must be a test.
• Recording a stream and replaying it produces byte-identical identifiers, asserted through a real state_hash_after comparison (which the v0.115.0 work makes possible).
• The 78 sites are enumerated in the issue or a checklist so the migration is auditable rather than "mostly done".
• Scoped explicitly: which identifier kinds are in scope (ARNs, resource IDs, opaque tokens, request IDs, ETags, session tokens) and which are deliberately left random, with the reason.

Also worth deciding here: MemoryStateManager.List returns Go map iteration order with no sort (state.go:80-97), across 118 non-test state.List( call sites. That makes two identical ListBuckets requests differ within one run, independent of identifier minting. It is a smaller fix (sort in List, once) and arguably belongs in this issue since it has the same symptom and the same two dependents; it is recorded here so it is not researched a third time.

Filed as the prerequisite for #833 and #817 during the v0.115.0 replay-reporting research.

[scttfrdmn]

Deferred out of v0.116.0 to v0.117.0. Three corrections to this issue's premises, verified against the tree at bd1dca7, plus what v0.116.0 discharged.

The central claim does not hold: this issue's cheap form unblocks nothing

The issue positions itself as the prerequisite of #833. It is not, in the scoping it proposes.

Deriving an identifier from its inputs (option i, S/M) cannot serve #833, because #833 needs CreateAccessKey (iam_plugin.go:1475) and AssumeRole (sts_plugin.go:285, :506) reproducible, and neither has a unique-name input to derive from. Both are in the collision class, where identical inputs must legitimately yield distinct identifiers. Seven such sites are verified:

• two access keys for one user
• RunInstances with MaxCount > 1 (ec2_plugin.go:665-667)
• two snapshots of one volume
• two SendMessages with one body
• two AssumeRoles with one session name
• two multipart uploads on one key
• two identical Athena queries

The in-tree counter-argument is already written down. iamSLRTaskUUID's doc comment (iam_service_linked_roles.go:245-249): "deriving one would make two deletions of the same role collide on a single ID."

So the real dependency chain is the full seam (option ii), which is L, not the M this issue implies.

The inventory is wrong in four places

• 75 generate* functions, not 78.
• 66 are crypto/rand-backed, but "nearly all draw from it directly" is wrong twice: ~40 call rand.Read/rand.Int inline and 26 go through one choke point, randomHex (ec2_types.go:489, 40 call sites). That choke point is the good news in this issue — it is the difference between 66 edits and 40.
• Nine are not crypto/rand at all: three already deterministic (ec2_plugin.go:3703, kinesis_plugin.go:880, secretsmanager_types.go:57), five wall-clock (eventstore.go:929, :934, parser.go:823, replay.go:633, s3_plugin.go:3008), one math/rand (organizations_plugin.go:302).
• Minting not named generate* is missing from the issue entirely: randomHex, stsGenerateSecret/stsGenerateToken (sts_plugin.go:631, :640), iamSLRTaskUUID (iam_service_linked_roles.go:250), S3 version IDs (s3_plugin.go:927, :1200), SESv2 MessageId (sesv2_plugin.go:243), and Omics' clock-seeded PRNG (omics_plugin.go:38).

Two shortcuts are closed, and one of #817's premises falls with them

• Event.Sequence is not reachable at mint time. It is assigned inside RecordEvent (eventstore.go:289, pipeline step 8); minting happens at step 5. A sequence-derived identifier is not available where it would be needed.
• TimeController.Now() advances by wall-clock elapsed (types.go:245-250), so a tc.Now() component is not deterministic. This independently falsifies Replay: deep-compare response bodies during verification #817's stated premise that "bodies carry simulated-clock times, which are reproducible." Recorded there too.

A hard prerequisite that was not filed: #886

resetState resets only the StateManager (replay.go:656-664) and PluginRegistry has no reset hook (types.go:334-365), so the two atomic counters (s3_plugin.go:927/:1200, sesv2_plugin.go:20) survive a reset and a second replay in one process diverges from the first. Filed as #886. It is a prerequisite of this issue's full seam, and v0.116.0's CLI wiring (#855) made it reachable from substrate replay rather than only from a hand-built engine.

What v0.116.0 shipped toward this

Two of this issue's real prerequisites, both required by #817 regardless of which minting option is eventually chosen, and neither dependent on that choice:

• state: MemoryStateManager.List returns keys in Go map order, so 111 call sites answer differently run to run #865 — MemoryStateManager.List returns lexicographic order, with the guarantee stated on the interface. 124 non-test call sites were following Go's map hash seed.
• replay: a success body's RequestId derives from the wall clock and the event never records it, so a recorded run cannot be reproduced #866 — Event records the request ID, so a replayed success body carries the recorded RequestId rather than a fresh wall-clock one. This was the missing half of substrateRequestID (error_protocol.go:10-14), whose comment already stated the rule for the error path.

The structural model when option (ii) is taken

#510 is the closed precedent for this class ("FaultController: the PRNG is shared across rules, so Probability determinism depends on request ordering"), and NewFaultController(cfg, seed) (fault.go:157) with per-rule ruleRNGs (fault.go:188-199) is the shape to copy.

Test blast radius, for the record

~45 shape assertions (HasPrefix on i-, vol-, AKIA, …) and ~5 length assertions. Zero tests assert a minted value, because they structurally cannot today. Preserving prefix and length — as cfnNameSuffix's fixed 12 (cfn_physical_name.go:115) and cfgsvcMintRuleID's fixed 6 already do — breaks essentially nothing. That is the reassuring half of an L-sized change.

[scttfrdmn]

Moved to the v0.118.0 milestone, and the hardest structural piece of it is done.

Discharged this release: #886. The blocker filed out of this issue's own analysis in v0.116.0 was
that PluginRegistry had no reset hook, so a plugin holding mutable state on its own struct survived
resetState — meaning even fully deterministic minting would diverge on a second replay in one process.
v0.117.0 added the ResettablePlugin capability and wired it into both ReplayEngine.resetState and
POST /v1/state/reset, clearing the state manager first and the plugins second. The three plugins that
mint from struct-local state — S3Plugin.versionSeq, SESv2Plugin.msgSeq, OmicsPlugin.rng — are
reset with it. That is one of the two reasons this issue was sized L; the lifecycle hook no longer
has to ship as part of it.

Unchanged, and still the reason it is deferred: the seam itself. 66 crypto/rand-backed minters,
~40 of them inline and 26 through one choke point (randomHex, 40 call sites), plus the minting
that is not named generate* at all and so is absent from this issue's inventory — stsGenerateSecret
/ stsGenerateToken, iamSLRTaskUUID, S3 version IDs, the SESv2 MessageId, and Omics' clock-seeded
PRNG. Two shortcuts remain closed off: Event.Sequence is assigned inside RecordEvent, after the
point a handler mints, so it is not reachable at mint time; and TimeController.Now() advances by
wall-clock elapsed, so a tc.Now() component is not deterministic either.

Also still standing, and the thing this issue must decide first: the collision class. Seven verified
sites must yield distinct identifiers from identical inputs — two access keys for one user,
RunInstances with MaxCount>1, two snapshots of one volume, two SendMessages with one body, two
AssumeRoles with one session name, two multipart uploads on one key, two identical Athena queries.
iamSLRTaskUUID's own doc comment is the in-tree argument: "deriving one would make two deletions of
the same role collide on a single ID." So deriving from inputs (the cheap option) unblocks neither
#833 nor #817, both of which need CreateAccessKey and AssumeRole reproducible. NewFaultController(cfg, seed) with its per-rule RNGs remains the structural model for the full seam.

[scttfrdmn]

Moved to the v0.119.0 milestone. Nothing in v0.118.0 touched the seam, but the release produced one
data point worth carrying, because it is evidence about the payoff rather than the cost.

#819's AWS Config arm turns on a derived minter, and it is the first place the benefit shows up
somewhere other than replay. cfgsvcMintRecorderID derives a configuration recorder's ID by
SHA-256 over (account, Region, name), truncated to a fixed 8 characters — the same shape
cfnNameSuffix and cfgsvcMintRuleID already use. Because of that, a recorder's ARN is identical
across a redeploy, and so is a rule's, which is minted from the rule name the same way.

That is what made #819's clobber/removal assertion writable for Config and unwritable for ten of the
twelve types before it. The reconciliation's two safeguards can only be observed on a second
deployment — a caller's own tag is preserved by comparing it against what the stack previously
propagated, and a withdrawn stack tag is removed only when the stored value still matches — and an
UpdateStack re-creates every resource in the template. A type whose create mints a fresh identity is
therefore never revisited at the record a caller could have tagged, so the assertion has nothing to
assert against. A KMS key is the clean example: its update mints a new key, which is why that
spelling's defect had to be covered through an exported accessor instead.

So the argument for this issue is not only "a recorded run replays identically". It is also that a
derived identifier is what makes an update path testable at all, and there are behaviours — both of
this one's safeguards among them — that are unobservable without one.

It does not shrink the issue, and it does not touch the collision class. A configuration recorder
is one per account and Region and a Config rule's name is unique within one, so both have a
unique-by-construction input to derive from. That is exactly what the seven collision sites do not
have — two access keys for one user, RunInstances with MaxCount>1, two snapshots of one volume, two
SendMessages with one body, two AssumeRoles with one session name, two multipart uploads on one
key, two identical Athena queries — so this is a demonstration of the easy half, not a precedent for
the hard one. Everything in the previous comment stands: 66 crypto/rand minters with 26 behind
randomHex, the minting not named generate* and therefore absent from this issue's inventory,
Event.Sequence unreachable at mint time, and TimeController.Now() advancing by wall-clock elapsed.