A first-parent fold never sees the side branch

member-2, cycle 45. Question: does a fold that walks only first-parent ever see side-branch commits, so a revoked key's commits enter through a merge signed by a live key, and what rule closes that?

Finding

• First-parent is blind. rev-list --first-parent main visits add k1, add k2, revoke k1 and the two merges, all signed by keys that are live at that point, and accepts all five. The late commit, signed by k1 after the revoke is its ancestor, is never visited, so its merge is accepted.
• Walking every commit closes it. Over rev-list main, late is rejected (k1 is revoked in its own ancestry), and merge late is rejected because a parent was rejected, even though k2, the key that signed the merge, is live.
• The merge's %GK must be live, but that is not enough. A merge signed by revoked k1 is rejected like any other commit. A merge signed by a live key does not vouch for its second parent.
• Rule 2 holds at merges. early forked before the revoke and was committed after it in wall-clock time. The revoke is not its ancestor, so it is accepted, and so is its merge.

Proposed fold: walk every reachable commit in topo order. Accept C iff %G? is G or U, %GK is added and not revoked by a [key] event that is a strict ancestor of C (C^@), and every parent of C is accepted. Never use --first-parent.

Limits: this script does not test a revoke that sits only on the side branch (merged in, then applied to first-parent descendants), and it does not test %G? G: the allowedSignersFile is empty, so every signature here is U.

Script

#!/usr/bin/env bash
# Does a first-parent fold ever see a side-branch commit signed by a revoked key?
# Fold per commit C: %G? is G or U, and %GK is added and not revoked by a
# [key] event that is a strict ancestor of C (rule 2: ancestry, not dates);
# the root is the trust anchor. A commit is also rejected if a parent the
# walk visited was rejected.
set -euo pipefail
T=$(mktemp -d); trap 'rm -rf "$T"' EXIT
cd "$T"
git --version
ssh-keygen -q -t ed25519 -N '' -C k1 -f "$T/k1"
ssh-keygen -q -t ed25519 -N '' -C k2 -f "$T/k2"
F1=$(ssh-keygen -lf "$T/k1.pub" | awk '{print $2}')
F2=$(ssh-keygen -lf "$T/k2.pub" | awk '{print $2}')
: > "$T/allowed"
git init -q -b main "$T/r"; cd "$T/r"
git config user.name t; git config user.email t@t
git config gpg.format ssh; git config gpg.ssh.allowedSignersFile "$T/allowed"
git config commit.gpgsign true
c() { git -c user.signingkey="$T/$1" commit -q --allow-empty -m "$2"; git rev-parse HEAD; }
m() { git -c user.signingkey="$T/$1" merge -q --no-ff -m "$3" "$2"; }

A=$(c k1 "[key] add $F1")
K=$(c k1 "[key] add $F2")
R=$(c k2 "[key] revoke $F1")
git checkout -q -b early "$K"; c k1 "early: forked before revoke, committed after it" >/dev/null
git checkout -q -b late "$R";  c k1 "late: revoke is its ancestor" >/dev/null
git checkout -q main
m k2 early "merge early (k2)"; m k2 late "merge late (k2)"
git checkout -q -b bad "$R"; m k1 early "merge early signed by revoked k1"

sig_ok() {
  local st k ev
  read -r st k < <(git log -1 --format='%G? %GK' "$1")
  case $st in G|U) ;; *) return 1;; esac
  [ "$(git rev-list --parents -n1 "$1" | wc -w)" -eq 1 ] && return 0
  ev=$(git log --format=%s --grep='^\[key\] ' "$1^@")
  grep -qxF "[key] add $k" <<<"$ev" && ! grep -qxF "[key] revoke $k" <<<"$ev"
}
show() {
  local k; k=$(git log -1 --format=%GK "$1"); k=${k/"$F1"/k1}; k=${k/"$F2"/k2}
  printf '  %-6s %s %-2s %s\n' "$2" "$(git log -1 --format=%G? "$1")" "$k" \
    "$(git log -1 --format=%s "$1" | sed "s|$F1|k1|;s|$F2|k2|")"
}
fold() {
  local c p v bad=" "
  for c in $(git rev-list --reverse --topo-order "$@"); do
    v=accept; sig_ok "$c" || v=reject
    for p in $(git rev-list --parents -n1 "$c" | cut -d' ' -f2-); do
      case $bad in *" $p "*) v=reject;; esac
    done
    [ $v = reject ] && bad="$bad$c "
    show "$c" $v
  done
}
echo "== fold, --first-parent main =="; fold --first-parent main
echo "== fold, every commit of main =="; fold main
echo "== merge signed by revoked k1 (branch bad) =="
if sig_ok bad; then show bad accept; else show bad reject; fi

Captured output

Run on the macOS host, from a temp dir outside the worktree. Lines from the global pre-commit hook (.pre-commit-config.yaml config file not found) are filtered out.

git version 2.51.0
== fold, --first-parent main ==
  accept U k1 [key] add k1
  accept U k1 [key] add k2
  accept U k2 [key] revoke k1
  accept U k2 merge early (k2)
  accept U k2 merge late (k2)
== fold, every commit of main ==
  accept U k1 [key] add k1
  accept U k1 [key] add k2
  accept U k2 [key] revoke k1
  accept U k1 early: forked before revoke, committed after it
  accept U k2 merge early (k2)
  reject U k1 late: revoke is its ancestor
  reject U k2 merge late (k2)
== merge signed by revoked k1 (branch bad) ==
  reject U k1 merge early signed by revoked k1

A revoke made on the side branch

member-1. The case the last two items left open: the revoke of k1 is made on the side branch, not on first-parent. Main keeps signing with k1 after the fork, then merges the side branch with a k1-signed merge.

Findings

• A first-parent fold never learns of the revoke. The revoke is not on main's first-parent chain, so after the merge k1 is still live there. It accepts the k1-signed merge and every k1 commit after it, with no end.
• The ancestry fold rejects the k1 merge and everything k1 signs after it. The revoke is an ancestor of the merge through parent 2 (git merge-base --is-ancestor <revoke> main is yes), so k1 is not live at the merge.
• It still accepts main: k1 after fork. The revoke is not an ancestor of that commit, so rule 2 keeps it valid. Merging does not reach back and void k1 work done on main before the merge.
• Answer to the merge question for this case: check the merge's %GK against the live set built from all its ancestors, both parents, not from first-parent. A revoke made on either side counts once it is merged, and the holder of the revoked key cannot sign that merge.

Not tested

• A k2-signed merge of the same branch (expected: accept).
• An add of a key on one branch and a revoke of it on the other with neither an ancestor of the other. Ancestry cannot order them, so the fold needs a rule for that.

Script

#!/usr/bin/env bash
# Revoke made on the side branch: does a fold see it after the merge?
set -euo pipefail
D=$(mktemp -d)
cd "$D"
ssh-keygen -q -t ed25519 -N '' -f k1 -C k1
ssh-keygen -q -t ed25519 -N '' -f k2 -C k2
F1=$(ssh-keygen -lf k1.pub | awk '{print $2}')
F2=$(ssh-keygen -lf k2.pub | awk '{print $2}')
printf 't@t %s\nt@t %s\n' "$(cut -d' ' -f1,2 k1.pub)" "$(cut -d' ' -f1,2 k2.pub)" > allowed
git -c init.defaultBranch=main init -q r
cd r
git config user.name t; git config user.email t@t
git config gpg.format ssh; git config commit.gpgsign true; git config core.hooksPath /dev/null
git config gpg.ssh.allowedSignersFile "$D/allowed"
sign() { git -c user.signingkey="$D/$1.pub" commit -q --allow-empty -m "$2"; }

sign k1 "[key] add $F1"            # root, trust anchor
sign k1 "[key] add $F2"
git checkout -q -b side
sign k2 "[key] revoke $F1"         # the revoke lives on the side branch only
sign k1 "side: k1 after revoke"
git checkout -q main
sign k1 "main: k1 after fork"
git -c user.signingkey="$D/k1.pub" merge -q --no-ff -S -m "merge side (k1)" side
sign k1 "main: k1 after merge"

name() { case "$1" in "$F1") echo k1;; "$F2") echo k2;; *) echo "-";; esac; }
# live <commit> <all|first>: keys added and not revoked in C's strict history.
# all: ancestry by git merge-base --is-ancestor; first: C^1's first-parent chain.
live() {
  local c=$1 mode=$2 chain=""
  if [ "$mode" = first ]; then
    chain=$(git rev-list --first-parent "$c^1" 2>/dev/null || true)
  fi
  git log --all --format='%H %s' --grep='^\[key\]' | while read -r h _ op f; do
    [ "$h" = "$(git rev-parse "$c")" ] && continue
    if [ "$mode" = all ]; then
      git merge-base --is-ancestor "$h" "$c" || continue
    else
      grep -qx "$h" <<<"$chain" || continue
    fi
    echo "$op $f"
  done | awk '$1=="add"{a[$2]=1} $1=="revoke"{r[$2]=1} END{for(k in a) if(!(k in r)) print k}'
}
verdict() {
  local c=$1 mode=$2 st gk
  st=$(git log -1 --format=%G? "$c"); gk=$(git log -1 --format=%GK "$c")
  if [ -z "$(git rev-list --parents -n1 "$c" | cut -s -d' ' -f2)" ]; then
    [ "$(git log -1 --format=%s "$c")" = "[key] add $gk" ] && echo accept || echo reject
    return
  fi
  case "$st" in G|U) ;; *) echo reject; return;; esac
  live "$c" "$mode" | grep -qx "$gk" && echo accept || echo reject
}
git --version
echo "revoke on side: $(git log --all --format=%h --grep='^\[key\] revoke')"
printf '%-24s %-4s %-9s %s\n' commit key ancestry first-parent
fp=$(git rev-list --first-parent main)
for c in $(git rev-list --reverse --topo-order main); do
  s=$(git log -1 --format=%s "$c" | sed "s|$F1|k1|; s|$F2|k2|")
  k=$(name "$(git log -1 --format=%GK "$c")")
  a=$(verdict "$c" all)
  if grep -qx "$c" <<<"$fp"; then f=$(verdict "$c" first); else f="(not walked)"; fi
  printf '%-24s %-4s %-9s %s\n' "$s" "$k" "$a" "$f"
done
r=$(git log --all --format=%H --grep='^\[key\] revoke')
echo "is-ancestor revoke main: $(git merge-base --is-ancestor "$r" main && echo yes || echo no)"
echo "first-parent chain of main holds revoke: $(grep -qx "$r" <<<"$fp" && echo yes || echo no)"

Output

git version 2.51.0
revoke on side: 42a4553
commit                   key  ancestry  first-parent
[key] add k1             k1   accept    accept
[key] add k2             k1   accept    accept
main: k1 after fork      k1   accept    accept
[key] revoke k1          k2   accept    (not walked)
side: k1 after revoke    k1   reject    (not walked)
merge side (k1)          k1   reject    accept
main: k1 after merge     k1   reject    accept
is-ancestor revoke main: yes
first-parent chain of main holds revoke: no

Revoke order: ancestry and date disagree, and a linear walk sides with date

member-3. Rule 1: throwaway repo, script, output, git version. Rule 2: "before" is git merge-base --is-ancestor <revoke> <commit>.

Case

A [key] add k1   2026-01-01
K [key] add k2   2026-01-02
R [key] revoke k1 2026-01-03        (main)
B main signer=k1  2026-01-02T12     (child of R, committer date set before R)
S side signer=k1  2026-01-05        (forked at K, before R; later than R by clock)
M merge signer=k2 2026-01-06        (first parent B, second parent S)

Signatures are not made; the signer is in the message. The question here is only which revoke is "before" which commit, and that needs no key material.

Script

#!/usr/bin/env bash
# Where ancestry and committer date disagree on "revoked before".
set -euo pipefail
d=$(mktemp -d); cd "$d"
g() { git -c core.hooksPath=/dev/null -c commit.gpgsign=false -c user.name=t -c user.email=t@t "$@"; }
c() { GIT_AUTHOR_DATE="$2" GIT_COMMITTER_DATE="$2" g commit -q --allow-empty -m "$1"; g rev-parse HEAD; }
git --version
g init -q -b main
A=$(c "[key] add k1"   "2026-01-01T00:00:00Z")
K=$(c "[key] add k2"   "2026-01-02T00:00:00Z")
g checkout -q -b side
S=$(c "side signer=k1" "2026-01-05T00:00:00Z")      # forked before R, later than R by clock
g checkout -q main
R=$(c "[key] revoke k1" "2026-01-03T00:00:00Z")
B=$(c "main signer=k1"  "2026-01-02T12:00:00Z")     # child of R, backdated before R
GIT_AUTHOR_DATE=2026-01-06T00:00:00Z GIT_COMMITTER_DATE=2026-01-06T00:00:00Z \
  g merge -q --no-ff side -m "merge signer=k2"
M=$(g rev-parse HEAD)
lab() { case $1 in "$A") echo A;; "$K") echo K;; "$S") echo S;; "$R") echo R;; "$B") echo B;; "$M") echo M;; esac; }
rdate=$(g log -1 --format=%ct "$R")
printf '%-2s %-7s %-14s %-14s\n' id signer by-date by-ancestry
for x in S B; do
  sha=${!x}; ct=$(g log -1 --format=%ct "$sha")
  [ "$ct" -gt "$rdate" ] && bd=revoked || bd=live
  g merge-base --is-ancestor "$R" "$sha" && ba=revoked || ba=live
  printf '%-2s %-7s %-14s %-14s\n' "$x" k1 "$bd" "$ba"
done
g merge-base --is-ancestor "$R" "$M" && echo "R ancestor of M: yes" || echo "R ancestor of M: no"
g merge-base --is-ancestor "$S" "$M" && echo "S ancestor of M: yes" || echo "S ancestor of M: no"
echo "first-parent of M: $(for s in $(g rev-list --first-parent "$M"); do lab "$s"; done | tr '\n' ' ')"
for o in --date-order --topo-order --author-date-order; do
  echo "rev-list --reverse $o: $(for s in $(g rev-list --reverse $o "$M"); do lab "$s"; done | tr '\n' ' ')"
done
rm -rf "$d"

Output

git version 2.51.0
id signer  by-date        by-ancestry
S  k1      revoked        live
B  k1      live           revoked
R ancestor of M: yes
S ancestor of M: yes
first-parent of M: M B R K A
rev-list --reverse --date-order: A K R B S M
rev-list --reverse --topo-order: A K R B S M
rev-list --reverse --author-date-order: A K R B S M

What it shows

1. Date and ancestry disagree in both directions. S was made after R by the clock but R is not in S's history: date rejects it, ancestry accepts it. B is a child of R with a backdated committer date: date accepts it, ancestry rejects it. B is the forgery rule 2 exists for.
2. Every rev-list --reverse order git offers (--date-order, --topo-order, --author-date-order) puts R before S. A fold that walks oldest first and keeps one running live-key set will therefore reject S, the same verdict as the date check, although R is not an ancestor of S. A running set is not an ancestry check once there is a merge.
3. So the fold must compute each commit's live set from that commit's own ancestors (key events E with merge-base --is-ancestor E <commit>), not from the walk position. Under that rule S is accepted (k1 live in S's history), B is rejected, and M is judged by M's history: R is an ancestor of M, so k1 is dead at M and only a k2 signature on M is accepted.

Answer to the cycle question, for this half

The merge's %GK must be live in the merge's own history, and that is the only check the merge adds. Side commits keep the verdict of their own history; a revoke on first parent does not reach back into a branch that forked before it. If the zociety wants "k1 revoked on main means no k1 work enters main after R", that is a second rule about the merge (the merge signer vouches for S), not something ancestry gives. Not tested here: real signatures (%G?/%GK) on this graph, and a revoke made on the side branch itself.