Review: the fix for H-L2-04 (a commit that adds a key package this member never saw)

From mnema-talk v3.3.13, rendered on this site.

Branch under review: msch128/fix-h-l2-04, commit caeefac66 on main 3.0.9. Read-only review in a temporary checkout; the measuring tests I wrote were scratch files and are not part of the branch.

Verdict: MERGE

The honest-relay numbers are not worse. On 400 honest seeds at the default lifetimes the share of member time without keys after holding them goes from 6.29 to 6.17 percent, and the number of start-overs from 2118 to 2129 (+0.5 percent); at production ratios on the honest relay (300 seeds) 2.50 to 2.41 percent and 1547 to 1548. Nothing breaks an invariant in either relay (the full sweep passes; at production ratios the hostile relay goes from three violating seeds to none). The slow seeds the author mentions are real, but the extra time is not spent in the new path (see "Does the fix make ordinary rooms worse"). I found no BLOCKER and no SHOULD-FIX that has to go first. The findings are two small follow-ups and notes.

BLOCKER

None.

SHOULD-FIX

1. The design note says the flag is set "exactly when ... refused for that reason and no other"; it is not exact, and the text should say so

wasRelayed (override in groupBehind.ts:30) sets the flag when it returns false. scanCommitProposals stops at the first proposal that fails, so the flag means "the first violation the scan met is an unseen add". A commit with an unseen add and another violation behind it (for example [add X, remove P] where P is present, or an add of an identity that is not in the room) sets the flag too. This is not a hole in the vet rule: the retry runs the whole validator again, so such a commit is never taken (once the package has arrived the scan goes on, meets the second violation and refuses; the flag is then clear and nothing starts over). What differs is the cost: a receiver that never got X's package starts over after the wait for a commit that was also otherwise illegal, where before it ignored it. Only the committer (by that receiver's view) gets that far (the validator returns before the scan for anyone else, so a member that is not the committer cannot trigger it). A malicious lowest id could already make receivers start over with a commit for a later epoch (isCommitAhead needs no signature check and the same reset limit applies), so this is no new power, but the sentence in doc/security/h-l2-04-unseen-add.md ("exactly ... and no other") and in the code comment of groupBehind.ts should say "the first failing proposal".

2. A mutant survives: the flag is never cleared in validator

Removing this.clearUnseen() from validator (group.ts) leaves both new tests green. It is harmless today (the flag is cleared at each validator run and consumed in refused, and conflictNow runs the validator without ever calling refused, so a flag it leaves is overwritten by the next processCommit), except on a path where processPublicMessage rejects without calling the validator; then a stale flag could start a hold for an unrelated refusal. Either add the test (a conflict trial that sets the flag, then an unrelated rejection that must not hold) or delete the clear and clear the flag where it is consumed.

NOTE

1. Per-property check of the design note

  • A removed member cannot come back: the add rule (illegalAdd, isValidAddIdentity, wasRelayed) is untouched. The retry calls the same validator through receivePublic. Confirmed.
  • A key package or Welcome is used once: the new code creates none and consumes none; held keeps the public message and the state object. A start-over is the existing one. The hold does not hold secrets longer than before (the state was already held; a refused commit consumes nothing). Confirmed.
  • The vet rule is not weaker: nothing in vetProposals, scanCommitProposals or processAddProposal changed; the override only records the answer. A commit can be taken on retry only if the full validator accepts it. Confirmed; see SHOULD-FIX 1 for the second violation behind the unseen add.
  • A hung or malicious lowest id and the reset limit: refused asks resets.waitMs('self') before recoverNow, and while it is above zero it re-arms the timer for wait + 50 ms and runs the vet again then (a bounded loop, no start over meanwhile). The hold is per epoch: a second refusal of the same epoch while a commit is held returns at once (held.state === this.state), so a relay cannot stretch or multiply it by repeating deliveries.
  • Cost of one forced start-over to a relay: one withheld package delivery on a genuine commit with an add (the same kind of price as dropping one commit so that the next is "ahead"), at most one start-over per reset limit (10 s doubling to 60 s). It can reach every receiver at once, as a dropped commit can. The new path does shorten the time: a start-over after 4 s instead of after the next commit or two heartbeats of the lowest id. That is the point of the fix and the relay already had the power (it can end a call altogether).
  • The held commit: one slot (held), replaced by a new hold in a later epoch, released in close, when the state changed at the retry, and after the retry. Repeated refusals in the same epoch are ignored, so a flood adds no timers or memory; each flooded message still costs a signature check, as before.
  • Mixed rooms: only receivers change behaviour. A 3.0.9 receiver stays behind as before, a new one starts over; the committer's behaviour is the same. I found no mix that is worse than 3.0.9.

2. Does the fix make ordinary rooms worse

I measured the availability (member time without keys after holding them, and start-overs, from the trace) and the time to agree, with and without the fix (the fix switched off by returning at the top of refused).

SettingLost-key share, base to fixStart-overs, base to fixViolating seeds, base to fix
Honest, default lifetimes, 400 seeds6.29 to 6.17 percent2118 to 2129none, none
Honest, production ratios, 300 seeds2.50 to 2.41 percent1547 to 1548none, none
Hostile, production ratios, 300 seeds5.36 to 6.30 percent4091 to 4227 (+3.3)149, 175, 176 to none

Honest default: 17 of 400 seeds differ; 6 lose more than 5 s of key time, 6 lose less; no invariant breaks. Honest production: 8 of 300 differ; seed 82 goes from 82 s to 1613 s to agree, seed 58 from 880 s to 42 s. Hostile production: 166 of 300 differ; 16 are more than 60 s slower to agree (seed 29: 1 s to 871 s) and 36 are more than 60 s faster; median time to agree 23 s to 18 s, the 90th percentile 3150 s to 1127 s. The lost-key share rises on the hostile relay (+0.94 points) because the measure counts only time with no keys: a member that stays behind after a refused commit holds stale keys and counts as fine, so the fix is penalised for ending a split with a start-over. The time to agree is the better measure and it improves.

What the extra time in seeds 82 (honest) and 29 (hostile) is spent on: I logged every hold and every start-over of the new path. Honest 82: holds at 16.2, 16.3, 17.9 and 19.5 s (four members) and one start-over (m2 at 21.9 s); the other three took the commit within the wait (the package had come). Hostile 29: holds at 10.2, 14.5, 51.8, 51.8 and 65.5 s and start-overs at 14.2 and 75.0 s. All of this is inside the 75 s chaotic phase; after it neither run has a hold or a start-over of the new path. The run diverges at the first start-over (seed 252 honest and 82 and 29 show it in the trace as one extra keys none), the random schedule of the simulator follows a different path, and the long tail that follows (in honest 82 a late joiner sits in a group of one from 898 s to about 1670 s, waiting out the offer back-offs) is the existing slow tail, which the base also has on other seeds (its 90th percentile on the hostile relay is 3150 s). I did not dissect why that tail is that slow; it is not in the new path.

The 4 s hold in an honest room: it delays only a member whose commit is refused for an unseen add. The honest relay gives each member one ordered stream, so a package comes before the commit that uses it; a member can lack a package only after a lost delivery (a reconnect, a sleep). In the simulator all honest-relay holds are of that kind and happen in the chaotic phase (the 82 and 252 traces). A member that is merely slow to receive an ordered package is not delayed. I did not test a real browser on a real server; this is from the code and the simulator.

The author's sweep time (696 s against 466 s) I could not compare: my full sweep on the branch took 879 s, on a machine that was busy, and I did not run the base sweep. The simulator work per run does grow with each start-over.

3. Hostile seed 149 and the H-L2-04 test

With the fix hostile 149 settles (production-ratio run above has no violation). The two new tests in group.behind.test.ts kill these mutants: retry removed (both tests fail), no start-over after the retry (the first fails), no wait (the second fails), immediate start-over on first refusal (the first fails). One mutant survives (SHOULD-FIX 2).

4. Gates

src/lib/media: 37 files passed, 1 skipped, 396 tests passed, 48 skipped. ESLint on src/lib/media: no findings. vue-tsc --noEmit for tsconfig.app.json and tsconfig.tests.json: clean. group.ts is at 398 lines (limit 400), groupBehind.ts 92, the new test 55. The next change to group.ts needs a split first.

What I ran

  • Full sweep on the branch (SIM_SWEEP=1, --maxWorkers=3): 2 of 2 passed, 879 s.
  • Measurements (scratch test reading the trace): honest 400 seeds default, with and without the fix; honest and hostile 300 seeds at production ratios, with and without; traces and a hold/start-over log of honest 82, hostile 29 and honest 252.
  • Mutants on groupBehind.ts and group.ts (above).
  • ESLint, vue-tsc for both projects, src/lib/media tests.

What I did not check

  • The base full sweep and its time, and a hostile-relay run of all 400 seeds at default lifetimes with availability.
  • The cause of the slow tail in honest 82 and hostile 29 (only that the new path takes no part in it).
  • A real browser, or a relay under real delays.
  • Whether a stale flag can really survive on a path where processPublicMessage rejects without calling the validator (SHOULD-FIX 2 is from the code, not reproduced).

Round 2: commit 95b8e2b6b (on top of caeefac66)

Verdict: MERGE

Both should-fix items are closed. No change to protocol behaviour in this commit.

No behaviour change

The commit touches four files: SECURITY.md, doc/security/h-l2-04-unseen-add.md, group.behind.test.ts and groupBehind.ts. The diff of groupBehind.ts is two comment blocks only (I filtered out comment lines in the diff of every file under src/lib/media other than the test: nothing is left). group.ts is untouched (still 398 of 400 lines).

Should-fix 1 (wording): closed

The SECURITY.md paragraph, the design note and the comments now say "the first violation the scan met is an add of a package never relayed to this receiver", that such a commit is never taken if it breaks another rule (the retry runs the whole validator), and that a receiver may start over for a commit that was also otherwise illegal, which only the committer by its own view can cause and which a commit ahead can already cause. This matches the code: the committer rule is checked before the scan, scanCommitProposals returns at the first failing proposal, and wasRelayed sets the flag.

Should-fix 2 (the clear): closed; the state the test sets by hand is reachable

The new test calls the real wasRelayed on an unseen package to leave the flag set, then delivers a commit that the committer rule refuses, and requires that nothing is held, retried or started over. With this.clearUnseen() removed from validator it fails (1 failed, 2 passed); with it, 3 passed. So the mutant is killed.

Reachable path (read from the code, not run end to end): conflictNow vets a rival commit against the saved state with this.validator(saved.state, from) while a self-update is outstanding. If that commit is the committer's and its first violation is an unseen add, wasRelayed sets the flag and the validator rejects; conflictNow then takes its wins === false branch (return this.step()), which never calls refused(), so nothing consumes the flag. Without the clear in validator, the next commit refused for any other reason would reach refused() with the flag set, be held and start the member over. So the clear is live and the hand-set flag is a state the real code reaches. I could not confirm the author's second path ("or a throw"): processPublicMessage verifies the signature before it calls the validator, so I found no throw between the validator and refused; the conflict path is enough to justify the line. Nobody has run the rival-commit-during-self-update case end to end (the author says so too); the test pins the part that can go wrong (the clear), not the whole path.

What I ran (exit codes read directly, no pipe)

  • src/lib/media: exit 0, 37 files passed, 1 skipped, 397 tests passed, 48 skipped.
  • Sweep shard 0/8 (SIM_SWEEP=1 SIM_SHARD=0/8, both relays), --maxWorkers=3: exit 0, 2 of 2 passed, 108 s.
  • Mutant (no clearUnseen() in validator): the new test fails, exit 1; restored.
  • ESLint on src/lib/media: exit 0. vue-tsc --noEmit for tsconfig.app.json and tsconfig.tests.json: exit 0.

I did not run the full sweep again (the code did not change since the round-1 full sweep, only comments and a test).

Something wrong on this page? Tell us.