Paper 2026/066

Complete Characterization of Randomness Extraction from DAG-Correlated Sources

Abstract

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general framework for multi-block randomness sources with causal correlations. A SHEDAG source is defined over a directed acyclic graph (DAG) $G$, whose nodes output $n$-bit blocks. Honest nodes output mutually independent blocks, which are uniformly random by default and, more generally, may have high min-entropy. Corrupted nodes output arbitrary functions of their causal views (all predecessors in $G$). We tightly characterize the conditions under which zero-error and negligible-error randomness extraction from SHEDAG sources is possible. \begin{description} \item[Zero-error extraction:] We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an \emph{unrelated set} (an antichain under reachability) of size at least $t+1$. In particular, if every unrelated set has size at most $t$, no function can extract a perfectly uniform bit. We also give a polynomial-time algorithm for finding a maximum unrelated set, thereby efficiently determining the largest corruption threshold $t$ for which perfect extraction is possible. \item[Negligible-error extraction:] We introduce a graph parameter, called the \emph{resilience} of a DAG $G$, that characterizes the feasibility of randomness extraction with \emph{negligible} error in the block length. We define two variants of this parameter, $\res_\uni(G)$ and $\res_\ent(G)$, corresponding to uniform and entropic honest nodes, respectively. We show that when honest nodes are uniform, negligible-error extraction is impossible when the number of corrupted nodes $t>\res_\uni(G)$. When honest nodes are entropic, we show that negligible-error extraction is impossible when $t>\res_\ent(G)$. Complementing these impossibility results, we establish the following: \begin{itemize} \item[(i)] There exists an explicit extractor for SHEDAG sources with $t\leq \res_\uni(G)$ corrupted nodes and honest blocks that are uniform over $\bits^n$, achieving output length $\Omega_N(n)$ and error $2^{-\Omega_N(n)}$. Here $N$ is number of vertices of the DAG $G$. \item[(ii)] There exists a non-explicit extractor for SHEDAG sources with $t\leq \res_\ent(G)$ corrupted nodes and honest blocks of min-entropy $k\geq \poly\log n$, achieving output length $k^{\Omega(1)}$ and error $2^{-k^{\Omega(1)}}$. \end{itemize}

Note: In an earlier version, we claimed an efficient construction of extractor for SHEDAG sources with negligible error, whenever the number of corrupted nodes is at most res(G). However, that claim was incorrect. In the current version, we instead establish the existence of a SHEDAG extractor with negligible error under the same upper bound on the number of corrupted blocks. Further, in the latest version we add explicit construction of SHEDAG extractor with negligible error when honest nodes are uniform.