What invariants must survive when idempotency keys collide across tenants?

**Date of Record:** 2026 October 27 **Scope:** Applies when an agentic session uses idempotency keys for retry-safe operations, and multiple tenants share infrastructure where key namespaces are not strictly isolated. Does not apply to systems with tenant-scoped idempotency databases that cryptographically separate namespaces.

Core Distinction

The separation between **idempotency key uniqueness** (the key identifies the operation) and **idempotency key tenant scoping** (the key is unique within a tenant but may collide across tenants). Relying on global uniqueness creates the **Cross-Tenant Key Collision**: two tenants use the same key (e.g., "user-123-refund"), the deduplication layer returns Tenant A's cached result to Tenant B, and Tenant B's legitimate operation is silently dropped or receives corrupted data.

What Was Observed

In multi-tenant agent architectures, failing to scope idempotency keys produces three primary failure modes:

  1. **Cross-Tenant Data Leak:** Tenant B's request returns Tenant A's cached result, exposing Tenant A's data to Tenant B.
  2. **Silent Operation Drop:** Tenant B's operation is deduplicated against Tenant A's key, so Tenant B's operation never executes, but the agent believes it succeeded.
  3. **Audit Trail Corruption:** The idempotency log shows one operation attributed to multiple tenants, breaking compliance reporting.

Recorded Elements

  1. **`tenant_scoped_key_hash`:** The idempotency key hash that includes both the tenant ID and the operation key, ensuring uniqueness across the tenant namespace.
  2. **`original_operation_context_hash`:** The full context of the operation that created the key (tenant, resource, payload), allowing verification that any deduplication is legitimate.
  3. **`cross_tenant_detection_receipt`:** A cryptographic proof that a key collision was detected, alerting the deduplication layer to reject the second tenant's operation rather than serving the first's result.
  4. **`tenant_isolation_proof`:** The cryptographic proof that the idempotency storage enforces tenant isolation, preventing cross-tenant reads even in the event of a bug.

Condition of Validity

* **Applies when:** The idempotency layer is shared across tenants, key namespaces are not strictly isolated, and cross-tenant collisions are possible. * **Does not apply when:** Each tenant has a physically separate idempotency store with cryptographic isolation, or keys are content-addressed and globally unique by construction.

Decision Boundary

  1. **Is the idempotency key scoped to a specific tenant?** If yes, standard idempotency applies. If no, proceed.
  2. **Does the idempotency layer return a prior result for this key?** If no, the operation is new. If yes, proceed to tenant verification.
  3. **Does the `original_operation_context_hash` match the current tenant?** If yes, the deduplication is legitimate. If no, the collision is cross-tenant. Reject.
  4. **Conversely, when can an agent accept a cross-tenant result?** Only when the tenants have explicitly authorized cross-tenant sharing (e.g., a shared parent tenant), and the authorization is cryptographically recorded.

Operational Effect

  1. **Cross-Tenant Leak Prevention:** Prevents one tenant's cached result from being served to another.
  2. **Silent Drop Prevention:** Detects collisions before silently dropping the second tenant's operation.
  3. **Audit Integrity:** Preserves per-tenant operation attribution even in shared infrastructure.
from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class IdempotencyVerdict(Enum):
    NEW_OPERATION = auto()
    LEGITIMATE_DEDUPLICATION = auto()
    CROSS_TENANT_COLLISION = auto()
    CROSS_TENANT_AUTHORIZED = auto()

@dataclass(frozen=True)
class IdempotencyKey:
    key_hash: str
    tenant_id: str
    operation_context_hash: str

@dataclass(frozen=True)
class StoredKeyState:
    stored_key: IdempotencyKey
    stored_result_hash: str | None

@dataclass(frozen=True)
class IdempotencyPolicy:
    cross_tenant_authorizations: frozenset[str]

@dataclass(frozen=True)
class IdempotencyManifest:
    verdict: IdempotencyVerdict
    directive: str
    manifest_digest: str

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

    @classmethod
    def evaluate_key(
        cls, request: IdempotencyKey, stored: StoredKeyState | None, policy: IdempotencyPolicy
    ) -> IdempotencyManifest:
        
        # Gate 1: New operation
        if stored is None:
            digest = cls._hash(json.dumps({
                "key": request.key_hash,
                "tenant": request.tenant_id,
                "context": request.operation_context_hash
            }, sort_keys=True))
            return IdempotencyManifest(
                verdict=IdempotencyVerdict.NEW_OPERATION,
                directive="PROCEED: New operation, no prior key.",
                manifest_digest=digest
            )

        # Gate 2: Same tenant
        if stored.stored_key.tenant_id == request.tenant_id:
            if stored.stored_key.operation_context_hash == request.operation_context_hash:
                digest = cls._hash(json.dumps({
                    "key": request.key_hash,
                    "tenant": request.tenant_id,
                    "result": stored.stored_result_hash or "NONE"
                }, sort_keys=True))
                return IdempotencyManifest(
                    verdict=IdempotencyVerdict.LEGITIMATE_DEDUPLICATION,
                    directive="PROCEED: Same tenant, same context. Return cached result.",
                    manifest_digest=digest
                )
            return IdempotencyManifest(
                verdict=IdempotencyVerdict.CROSS_TENANT_COLLISION,
                directive=f"HALT: Same tenant but different context. Key reuse rejected.",
                manifest_digest=cls._hash(f"CONTEXT_DIFF:{request.key_hash}")
            )

        # Gate 3: Cross-tenant
        authorization_key = f"{stored.stored_key.tenant_id}->{request.tenant_id}"
        if authorization_key in policy.cross_tenant_authorizations:
            digest = cls._hash(json.dumps({
                "key": request.key_hash,
                "from_tenant": stored.stored_key.tenant_id,
                "to_tenant": request.tenant_id,
                "authorized": authorization_key
            }, sort_keys=True))
            return IdempotencyManifest(
                verdict=IdempotencyVerdict.CROSS_TENANT_AUTHORIZED,
                directive=f"PROCEED: Cross-tenant authorized ({authorization_key}).",
                manifest_digest=digest
            )

        # Gate 4: Unauthorized collision
        return IdempotencyManifest(
            verdict=IdempotencyVerdict.CROSS_TENANT_COLLISION,
            directive=f"HALT: Key collision across tenants {stored.stored_key.tenant_id} and {request.tenant_id}.",
            manifest_digest=cls._hash(f"COLLISION:{request.key_hash}")
        )