papers/zoo-identity-chain/sections/05-credential-revocation.tex

\section{Credential Revocation}


\subsection{Accumulator-Based Revocation}

\IChain{} uses cryptographic accumulators \cite{camenisch2009accumulator} for efficient revocation. An accumulator $\text{acc}$ is a short commitment to a set $S$ of non-revoked credential identifiers.

\begin{definition}[Revocation Accumulator]
Let $\mathbb{G}$ be a bilinear group of prime order $q$. The accumulator for non-revoked set $S = \{c_1, \ldots, c_m\}$ is:
\[
\text{acc}_S = g^{\prod_{i=1}^{m}(s + c_i)}
\]
where $s$ is the trapdoor known to the committee and $g$ is a generator.
\end{definition}

\begin{theorem}[Revocation Check Complexity]
Given a non-membership witness $w_c$ for credential $c$, verifying that $c$ has been revoked (i.e., $c \notin S$) requires $O(1)$ bilinear pairing operations.
\end{theorem}

\begin{proof}
The non-membership witness is $(d, w)$ where $d \cdot (s + c) + r = \prod_{c_i \in S}(s + c_i)$ for some $r$. Verification checks $e(\text{acc}, g) = e(w, g^{s+c}) \cdot e(g^r, g)$ using two pairings and one multiplication.
\end{proof}

\subsection{Revocation by Credential Type}

Revocation authority depends on credential type:

\begin{table}[h]
\centering
\begin{tabular}{lll}
\toprule
\textbf{Credential Type} & \textbf{Revocation Authority} & \textbf{Mechanism} \\
\midrule
Validator-issued & Validator committee ($t$-of-$n$) & Accumulator update \\
Trusted issuer & Issuing entity & Signed revocation tx \\
Self-issued & Subject (self) & Document deactivation \\
DAO-governed & DAO vote (66\% supermajority) & Governance proposal \\
\bottomrule
\end{tabular}
\caption{Revocation authorities by credential type}
\label{tab:revocation}
\end{table}

\subsection{Revocation Propagation}

When a credential is revoked, the accumulator is updated atomically in the next block. Light clients that cache accumulator values receive update proofs via the \IdentityVM{} event log. Witness updates for remaining non-revoked credentials require $O(\log n)$ computation per holder, amortized across epochs.