Skip to content

0017: Two-phase revocation fold

  • Status: superseded by 0046
  • Date: 2026-09-23
  • Superseded: 2026-11-14, when the change policy-linear-chain replaced the multi-pass fold with a linear policy chain replayed in slot order. There are no passes or arbiters any more, and no quorum: root admins are peers in version 1.
  • Amended by: 0043 (the causal-past rule also covers role reductions, for policy records, and the two passes become three so that a rejected revocation or reduction never invalidates an ordinary record; proposed)

Context

The causal-past rule for revocation (ADR 0006) states that "an event by key K is valid only if it is in the causal past of every valid revocation of K". When two admins revoke each other's keys concurrently, this rule becomes self-referential: the validity of each revocation depends on the validity of the other. A fixpoint implementation, iterating until the valid set stabilizes, could oscillate with a period of 4, accepting records that should have been rejected.

Decision

Validity is decided in two fixed passes over the fold's total order (topological sort, then HLC and device ID as tiebreaker):

  • Phase 1 evaluates every record in fold order against the valid records visible in phase 1 up to that point, deciding revocations by induction. A revocation of key K is valid if there is no earlier-in-order valid revocation of K already decided; concurrent revocations are arbitrated by fold order, with the first in order winning. Grants, role assignments and quorum-completing approvals are evaluated in the same pass, so a revocation's authority is judged at its causal position. Revocations decided to be valid in phase 1 become the "arbiters".

  • Phase 2 evaluates every record in fold order again, against the valid records of phase 2 in its causal past, enforcing the full causal-past rule: a record by key K is valid only if it is an ancestor of every arbiter revoking K.

Consequences

  • The algorithm is deterministic for every delivery order and terminates in exactly two passes.
  • No record whose author has a valid concurrent revocation is ever accepted.
  • Which of two mutually-revoking admins survives is determined by fold order (HLC, then device ID): a public and deterministic rule, but not "fair" in the sense of symmetry.
  • Admin device revocation by a peer requires the demotion quorum as a condition of authority (this is a restatement of the spec in ADR 0006 as applied to the two-phase algorithm).

Alternatives considered

  • Iterate to a fixpoint. Rejected: a fixpoint may not exist (odd cycles in revocation graphs), or the iteration may oscillate before reaching a fixpoint, accepting unsound results. The algorithm is unsound.

  • Reject every record in a revocation cycle. Rejected: this prevents any valid record by any author in a concurrent revocation graph from taking effect. A malicious or mistaken admin can lock the vault indefinitely by starting a mutual revocation cycle.

  • Frontier-based approval summing. Rejected: frontier-based schemes (picking the "most approved" subset) lose the well-founded induction property and offer no safety guarantee. Liveness of conflicting operations is a client-side concern and is documented as such (ADR 0006).