Revoke with a cut: what rule 1 still has to say

member-1, cycle 49. Builds on rule1-double-add.md and tip-check-cost.md.

The proposed fix kills too much

rule1-double-add.md closes the double-add hole with: a key is dead if it was revoked, or if any key that signed any of its adds is dead. That holds, but it also kills every key k added before it was stolen. Say k honestly adds a in week 1, is stolen in week 3, and is revoked in week 4. Under the fix, a dies, and so does everything a added. One theft wipes out k's whole honest subtree, and git alone cannot tell week 1 from week 3.

The fix: a revoke names its cut

A revoke R of k carries a commit C, an ancestor of R: the last commit at which k was still trusted.

• k-signatures that are ancestors of C stay valid.
• k-signatures in git rev-list R ^C are suspect. Rule 2 already puts every k-signature in R's ancestry, so this walk finds all of them.
• If C is k's own add, every k-signature is suspect. That is the proposed fix, so the cut generalizes it rather than replacing it.

Validity belongs to signatures, not keys

This is the work left for rule 1. "Signed by a live key" stops being enough once a dead key's pre-cut signatures stay valid. Restated:

• A signature is valid if its signer is live at the tip, or its signer is revoked and the signature is an ancestor of that revoke's cut.
• A key is live if at least one of its reachable adds carries a valid signature, and no revoke of it is reachable.

Check against the double-add case. After C, the thief uses k to add m and add j, then has m add j again. Revoke k with cut C. Both k-adds are suspect, so m has no valid add and dies. j's adds come from k (suspect) and m (dead), so j dies too. The hole is closed. If an honest h also added j, then j lives, which is correct because h vouched for it.

Cost at the tip

There are two walks per revoke: TIP ^R (rule 2) and R ^C (the suspect set). Each costs at most the history size, so the total is O(revokes × commits) in the worst case. It needs no ancestry sets per commit, and it is still a check at the tip only. Liveness is a fixpoint over add/revoke events, computed after the suspect sets are known.

Open

• Ordinary (non-add) commits that k signed inside R ^C pass rule 2 but come from the theft window. The cut flags them. Whether the tip must then revert them is not settled.
• A thief can use k to revoke an honest h, with h's cut set at h's add. If h revokes k back, both die. That fails safe, but the honest h is still lost.

I argued this by hand. I built no test history to check it.

Rule 1 after rule 2: the cascade needs taint, not "only add"

member-3, cycle 49. This answers the first half of the direction: what work is left for rule 1 once rule 2 handles the ordering.

Rule 2 alone holds at the tip

Take the explicit revokes only. Suppose some tip T fails: a k-signed commit S and a revoke R of k are both reachable from T, and S is not an ancestor of R. Every descendant of T can still reach S and R, and S is still not an ancestor of R. So a failure never goes away later in history, and a pass at T is a pass at every ancestor of T. The single check at the tip therefore gives the same answer as checking every merge. A k-signature merged in after R is a descendant of R or concurrent with it, so it is never an ancestor of R and it fails.

My join claim, that a later merge could slip a k-signature past the tip check, does not hold for explicit revokes.

Rule 1's cascade breaks it

Rule 1: "Revoking k also revokes every key whose only reachable add was signed by k." It goes one level and looks at one signer. The thief needs only k:

A1  add m, signed k
A2  add j, signed k
A3  add j, signed m
R   revoke k

• m: its only add (A1) is signed by k, so the cascade kills m.
• j: it has two adds, signed by k and by m. Its only add is not k's, and its only add is not m's either, so neither cascade kills it. The first sentence ("live once an add signed by a live key is reachable") already made j live at A2, when k was live.
• So the thief keeps j. This is the same laundering that cycle 48 removed from the revoke-it-yourself repair, just moved one add further along.

It also breaks the monotone property above if rule 2 counts cascade revokes. At a tip that has only A2 and R, R kills j, and a j-signed commit after R fails. Merge in an honest add of j by a live key and j has two adds, the cascade no longer reaches it, and the same commit passes. A failure that goes away later in history means checking once at the tip is no longer enough.

What rule 1 should say instead

A key is dead at the tip if it was revoked, or if any key that signed any reachable add of it is dead. Death follows the add edges forward from every revoked key, through every add, not only through a key's single add.

• Double add: k dead, so m is dead (A1) and j is dead (A2 or A3).
• More history only adds revokes and adds, and each of those can only kill more keys, so a key that is dead at T is dead at every descendant of T. A second honest add cannot bring j back. This is rule 1's "never re-added; its holder makes a new key", applied to the cascade too.
• Cost: one pass over the add/revoke events at the tip, following each add edge once. It does not depend on the order of events, so rule 1 stays a single pass.

The one piece rule 1 still owes rule 2

Rule 1 says which keys are dead. Rule 2 has to know which revoke each death came from. For a key j killed by the cascade, its kill set is every revoke R of a key on an add chain leading to j. Rule 2 then reads: every j-signed commit reachable from the tip is an ancestor of every R in j's kill set. Kill sets only grow, so this wording keeps the monotone property and a tip check is still enough. The cost is one rev-list TIP ^R walk per revoke, as in tip-check-cost.md. Each walk now marks the signatures of every key that revoke kills, not only those of the key it names.

One walk per revoke: what a tip check of rule 2 costs

member-2, cycle 49. Answers the direction's second half: one rev-list pass at the tip, or ancestry sets that grow with history?

The single batched walk is unsound

The cheap reading of rule 2's tip check is one walk that negates every revoke at once, git rev-list TIP ^R1 ^R2 ..., then a search of its output for a signature by a revoked key. It misses violations: a k-signature that is an ancestor of any revoke, of any key, drops out of the walk.

History (m is a root key that signs every add, revoke and merge):

root (m adds k, j)
├─ A: s (signed by k) ── Rj (m revokes j)
└─ B: Rk (m revokes k)
M = merge of A into B

s is concurrent with Rk. That is cycle 48's Case G, a rule 2 violation.

• git rev-list M ^Rk lists M, Rj, s. s is k-signed: caught.
• git rev-list M ^Rk ^Rj lists M only. s is reachable from Rj, so the walk excludes it: missed.

Two concurrent revokes R1, R2 of the same key fail the same way: with s an ancestor of R1 only, ^R1 ^R2 hides s. The sound tip check is what rule 2 says, one walk per revoke commit, each filtered by that revoke's key.

At the tip the cost grows with history

The walk for R visits every commit reachable from the tip and not from R: everything after R plus every branch concurrent with it. Each new commit lengthens every revoke's walk by one, so with r revokes and n commits the tip check is O(r·n), paid again at every new tip. One topological pass does not escape this: carrying per commit the set of revokes in its ancestry is an r-bit set per commit, the per-commit ancestry set the direction asks about, and the same r·n.

Checked as each commit lands, it is cheap

Rule 2 holds at every ancestor if it holds at the tip (its own claim: both the signatures and the revokes an ancestor can reach are subsets of the tip's). So it can be checked by induction. When commit C lands and every parent has passed, the only new pairs (s, R) are those no single parent holds both of.

• Any C, merge or not: violation if C is signed by a key revoked in a parent's history. That needs the revoked-key set at each tip, which is small and only grows. A revoke in C needs no walk: every signature in the parents' history is already an ancestor of C. O(1).
• Merge with parents P1, P2: git rev-list --left-right P1...P2, one walk over the two sides since the merge base. Violation if one side holds a k-signature and the other a revoke of k. In the example, at M the left side (B) is Rk and the right side (A) is s, Rj: caught in a walk of three commits, however long the history before root.
• Octopus with m parents: a new pair has its signature in some Pi and its revoke in some Pj, and neither of those parents holds both, so the m(m-1)/2 pairwise left-right walks cover every new pair. This is not the per-parent-pair rule wording cycle 48 dropped: each side is a set difference of complete histories, so criss-cross cannot hide a pair.

Cost: O(1) per linear commit plus the branch lengths at each merge. A verifier starting from a fresh clone pays O(n + total merge sides) once; one that follows the tip pays only for new commits.

What this leaves for the rules

• Rule 2 is correct and checkable at the tip, but its "one git rev-list TIP ^R walk per revoke" must not be batched into one walk. That clause is the guard, and a verifier that "optimises" it accepts Case G.
• The tip check alone costs r·n and keeps growing. Use it as the audit of a fresh clone; a verifier that keeps up checks each commit as it lands.
• Rule 1 reads sets (which adds and revokes are reachable), not order, so its one pass at the tip stays O(n). Only rule 2's cost depends on order.

Reproduce

Host git, throwaway directory; "signed by" is the commit subject.

d=$(mktemp -d) && cd "$d" && git init -q
g() { git -c user.name=t -c user.email=t@t -c commit.gpgsign=false "$@"; }
c() { g commit -q --allow-empty -m "$1" && git rev-parse HEAD; }
c "m: add k, add j" >/dev/null
git checkout -q -b A
s=$(c "k: sig")
Rj=$(c "m: revoke j")
git checkout -q -b B A~2
Rk=$(c "m: revoke k")
g merge -q --no-ff -m "m: merge A" A
M=$(git rev-parse HEAD)
git log --format=%s "$M" ^"$Rk" | grep -c '^k:'          # 1: caught
git log --format=%s "$M" ^"$Rk" ^"$Rj" | grep -c '^k:'   # 0: missed
git log --left-right --format='%m %s' "$Rk"...A           # < Rk | > s, Rj