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}
\end{description}

The SHEDAG source model generalizes the SHELA online source model studied by Aggarwal, Obremski, Ribeiro, Siniscalchi, and Visconti (EUROCRYPT 2020) and by Chattopadhyay, Gurumukhani, and Ringach (FOCS 2024), Chattopadhyay, Gurumukhani, Ringach, and Servedio (CCC 2026). These prior works consider the special case in which the DAG $G$ is a path, whereas we study correlation models parameterized by arbitrary fixed DAGs and determine the precise graph-dependent corruption thresholds for perfect and negligible-error extraction.

Added explicit construction of SHEDAG extractor with negligible error when honest nodes are uniform.

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general model 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. Blocks output by honest nodes are independent (by default uniformly random, more generally having high min-entropy), while blocks output by corrupted nodes are arbitrary functions of their causal views (all predecessors in $G$).
We tightly characterize the conditions under which randomness extraction from SHEDAG sources is possible.

$\textbf{Zero-error extraction:}$ We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an "unrelated set'' (an antichain under reachability) of size at least $t+1$. Conversely, if every unrelated set has size at most $t$, we show that no function can output a perfectly uniform bit. We also provide a polynomial-time algorithm to find a maximum unrelated set, thus efficiently identifying the largest corruption threshold $t$ allowing perfect extraction.

$\textbf{Negligible-error extraction:}$
We identify a quantity that we call ``resilience'' of a DAG $G$, denoted $\text{res}(G)$, that characterizes the possibility of randomness extraction with \emph{negligible} error (in the block length).
We show that negligible-error extraction is impossible whenever $t>\text{res}(G)$, and, to complement this, for every $t\leq \text{res}(G)$ we prove the existence of the extractor with polynomial output length and negligible error.

Our results generalize prior online source models studied by (Aggarwal, Obremski, Ribeiro, Siniscalchi, Visconti, Eurocrypt 2020) and (Chattopadhyay, Gurumukhani, Ringach, FOCS 2024), which correspond to the special case of a SHEDAG source whose DAG $G$ is a path.

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 $\mathrm{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.

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general model 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. Blocks output by honest nodes are independent (by default uniformly random, more generally having high min-entropy), while blocks output by corrupted nodes are arbitrary functions of their causal views (all predecessors in $G$).
We tightly characterize the conditions under which randomness extraction from SHEDAG sources is possible.

$\textbf{Zero-error extraction:}$ We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an "unrelated set'' (an antichain under reachability) of size at least $t+1$. Conversely, if every unrelated set has size at most $t$, we show that no function can output a perfectly uniform bit. We also provide a polynomial-time algorithm to find a maximum unrelated set, thus efficiently identifying the largest corruption threshold $t$ allowing perfect extraction.

$\textbf{Negligible-error extraction:}$
We identify a quantity that we call "resilience'' of a DAG $G$, denoted $\text{res}(G)$, that characterizes the possibility of randomness extraction with "negligible" error (in the block length).
We show that negligible-error extraction is impossible whenever $t>\text{res}(G)$, and, to complement this, for every $t\leq \text{res}(G)$ we construct explicit extractors with polynomial output length and negligible error.

Our results generalize prior online source models studied by (Aggarwal, Obremski, Ribeiro, Siniscalchi, Visconti, Eurocrypt 2020) and (Chattopadhyay, Gurumukhani, Ringach, FOCS 2024), which correspond to the special case of a SHEDAG source whose DAG $G$ is a path.