What multi-signature invariants must survive when revoking a shared agent credential?

**Date of Record:** 2026 October 27 **Scope:** Applies when a shared agent credential (API key, service account, or signing key) used by multiple agents must be revoked, but the revocation requires multi-signature authorization to prevent a single compromised agent from unilaterally locking out the others. Does not apply to per-agent credentials or credentials with single-owner revocation.

Core Distinction

The separation between **revocation decision** (the intent to revoke exists) and **revocation quorum** (enough authorized parties have co-signed the revocation to make it legitimate). Relying on decision alone creates the **Unilateral Revocation Attack**: a single compromised agent signs a revocation, the credential is invalidated, and all other legitimate agents using the same credential are locked out, causing an availability outage.

What Was Observed

In shared-credential agent architectures, failing to enforce multi-signature revocation produces three primary failure modes:

  1. **Rogue Revocation:** One compromised agent revokes the shared credential, causing outage.
  2. **Revocation Race:** Two agents simultaneously attempt revocations for different reasons, and the first one wins, invalidating the second agent's intended remediation.
  3. **Replay Revocation:** An attacker captures a previously valid revocation signature and replays it to trigger revocation at an unintended time.

Recorded Elements

  1. **`revocation_request_nonce`:** A unique, monotonically increasing nonce for each revocation attempt, preventing replay.
  2. **`revocation_quorum_signatures`:** The set of signatures from authorized parties, each binding the specific revocation request (nonce + credential ID) to prevent signature reuse.
  3. **`authorized_revocation_signers`:** The registry of principals authorized to participate in revocation, preventing unauthorized signers from counting toward quorum.
  4. **`revocation_effective_epoch`:** The exact epoch after which revocation takes effect, allowing recovery operations to complete before the credential is invalidated.

Condition of Validity

* **Applies when:** The credential is shared across multiple agents, revocation is destructive (locks out other agents), and quorum signatures are feasible. * **Does not apply when:** The credential is per-agent (single owner can revoke), or the shared credential has no availability requirement (revocation is always acceptable).

Decision Boundary

  1. **Is the revocation request from a single signer or a quorum?** If single, the revocation is unauthorized. Reject. If quorum, proceed.
  2. **Does each signature bind the specific revocation nonce?** If no, the signatures may be replayed from a previous request. Reject.
  3. **Are all signers in the `authorized_revocation_signers` set?** If no, unauthorized signers may be attempting to force revocation. Reject.
  4. **Conversely, when can a single-signer revocation proceed?** Only when the credential is explicitly marked as `SINGLE_SIGNER_REVOKABLE` (e.g., emergency compromise case), or the credential is already known to be fully compromised with no legitimate use remaining.

Operational Effect

  1. **Unilateral Revocation Prevention:** Requires quorum, preventing any single agent from locking out others.
  2. **Replay Prevention:** Nonce binding prevents old revocation signatures from being reused.
  3. **Emergency Flexibility:** Allows single-signer revocation for emergencies with explicit override markers.
from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class RevocationVerdict(Enum):
    SINGLE_SIGNER_EMERGENCY = auto()
    QUORUM_ACHIEVED = auto()
    QUORUM_INSUFFICIENT = auto()
    UNAUTHORIZED_SIGNER = auto()
    NONCE_REPLAY = auto()

@dataclass(frozen=True)
class RevocationRequest:
    credential_id: str
    nonce: int
    signatures: tuple[tuple[str, str], ...]  # (signer_id, signature)
    is_emergency: bool

@dataclass(frozen=True)
class RevocationContext:
    authorized_signers: frozenset[str]
    required_quorum: int
    last_seen_nonce: int

@dataclass(frozen=True)
class RevocationManifest:
    verdict: RevocationVerdict
    directive: str
    manifest_digest: str

class MultiSigRevocationGuard:
    @staticmethod
    def _hash(data: str) -> str:
        return hashlib.sha256(data.encode("utf-8")).hexdigest()

    @classmethod
    def evaluate_revocation(
        cls, req: RevocationRequest, ctx: RevocationContext
    ) -> RevocationManifest:
        
        # Gate 1: Nonce replay
        if req.nonce <= ctx.last_seen_nonce:
            return RevocationManifest(
                verdict=RevocationVerdict.NONCE_REPLAY,
                directive=f"HALT: Nonce {req.nonce} <= last {ctx.last_seen_nonce}. Replay blocked.",
                manifest_digest=cls._hash(f"REPLAY:{req.nonce}")
            )

        # Gate 2: Emergency single-signer
        if req.is_emergency and len(req.signatures) == 1:
            signer_id, _ = req.signatures[0]
            if signer_id not in ctx.authorized_signers:
                return RevocationManifest(
                    verdict=RevocationVerdict.UNAUTHORIZED_SIGNER,
                    directive=f"HALT: Emergency signer {signer_id} not authorized.",
                    manifest_digest=cls._hash(f"UNAUTH_EMERGENCY:{signer_id}")
                )
            digest = cls._hash(json.dumps({
                "credential": req.credential_id,
                "nonce": str(req.nonce),
                "mode": "EMERGENCY"
            }, sort_keys=True))
            return RevocationManifest(
                verdict=RevocationVerdict.SINGLE_SIGNER_EMERGENCY,
                directive=f"PROCEED: Emergency single-signer revocation by {signer_id}.",
                manifest_digest=digest
            )

        # Gate 3: Unauthorized signers
        for signer_id, _ in req.signatures:
            if signer_id not in ctx.authorized_signers:
                return RevocationManifest(
                    verdict=RevocationVerdict.UNAUTHORIZED_SIGNER,
                    directive=f"HALT: Signer {signer_id} not authorized.",
                    manifest_digest=cls._hash(f"UNAUTH:{signer_id}")
                )

        # Gate 4: Quorum
        if len(req.signatures) < ctx.required_quorum:
            return RevocationManifest(
                verdict=RevocationVerdict.QUORUM_INSUFFICIENT,
                directive=f"WAIT: {len(req.signatures)}/{ctx.required_quorum} signatures.",
                manifest_digest=cls._hash(f"QUORUM:{len(req.signatures)}")
            )

        # Gate 5: Quorum achieved
        digest = cls._hash(json.dumps({
            "credential": req.credential_id,
            "nonce": str(req.nonce),
            "signers": tuple(sorted(s[0] for s in req.signatures)),
            "quorum": str(ctx.required_quorum)
        }, sort_keys=True))
        
        return RevocationManifest(
            verdict=RevocationVerdict.QUORUM_ACHIEVED,
            directive=f"PROCEED: Quorum achieved with {len(req.signatures)} signatures.",
            manifest_digest=digest
        )