Note that, by definition of $\nice_t^{(s)}$ in (<ref>), the pair $(\commset_{\tau^{(s)}}^{(s)}, \anonphase_{\tau^{(s)}}^{(s)})$ characterizes the round of Dandelion in the anonymity phase in which it has active set $\activeset_{\tau^{(s)}}^{(s)}$ and is conditioned to hit a curious node or enter a spreading phase. Then, since Dandelion is Markovian, the pair $(\commset_{\tau^{(s)}}^{(s)}, \anonphase_{\tau^{(s)}}^{(s)})$ only depends on $\left(\activeset_{\tau^{(s)}}^{(s)}, \anonphase_{\tau^{(s)} - 1}^{(s)}\right) = \left(\activeset_{\tau^{(s)}}^{(s)}, 1\right)$. Hence, by the Data Processing Inequality (Theorem 14 of [42]), we have
\[\divinfty{\round_{\tau^{(v)}}^{(v)}}{\round_{\tau^{(u)}}^{(u)}} \le \divinfty{\left(\activeset_{\tau^{(v)}}^{(v)}, 1\right)}{\left(\activeset_{\tau^{(u)}}^{(u)}, 1\right)} = \divinfty{\activeset_{\tau^{(v)}}^{(v)}}{\activeset_{\tau^{(u)}}^{(u)}}.\]
Combining this with (<ref>), we get

\begin{align}
\label{eq:data-processing-two-dandelion}
\divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}} \le \divinfty{\activeset_{\tau^{(v)}}^{(v)}}{\activeset_{\tau^{(u)}}^{(u)}}.
\end{align}

Finally, recall that we showed in (i) that $\activeset_{\tau^{(s)}}^{(s)} = \{W^{(s)}\}$, where $W^{(s)}$ is an absorbing state of the Markov chain (<ref>). Hence, from (<ref>), we have

\begin{align}
\label{eq:data-processing-three-dandelion}
\divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}} \le \divinfty{W^{(v)}}{W^{(u)}}.
\end{align}

Note also that since no curious node is contacted before time $\tau^{(s)}$, $\seqadv{s}$ can be obtained from $\{\round_t^{(s)}\}_{t \ge \tau^{(s)}} = \{(\activeset_t^{(s)}, \commset_t^{(s)}, \anonphase_t^{(s)})\}_{t \ge \tau^{(s)}}$ via a deterministic mapping by definition of $\seqadv{s}$ above in sec:dandelion-privacy. Then, applying the  Data Processing Inequality (Theorem 14 of [42]) again, for any $v,u \in \honest$ we have

\begin{equation}
\label{eq:data-process-seqadv-xt-dandelion}
\divinfty{\seqadv{v}}{\seqadv{u}} \le \divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}}.
\end{equation}

Combining the above with (<ref>), we get

\begin{equation}
\label{eq:data-process-seqadv-w-dandelion}
\divinfty{\seqadv{v}}{\seqadv{u}} \leq \divinfty{W^{(v)}}{W^{(u)}},
\end{equation}

which concludes the proof.

§.§ Upper bounding max divergence

Consider a $(d,\lambda)$-expander graph $G = (V,E)$ of size $n$, and a set of curious nodes $F \subseteq V$, with $|F| = f$. Then, the following assertions hold true

* $\max\{1 - \alpha_F, 1 - (1 + \lambda)\frac{f}{n}\} \le \lambda_1(\vec Q) \le 1 - (1 - \lambda)\frac{f}{n}$.

* $\max\{\left|\lambda_2(\vec Q)\right|, \left|\lambda_{n-f}(\vec Q)\right|\} \le \lambda$.

We first show the left-hand side inequality of assertion (a). Then, we show the right-hand side of assertion (a). Finally, we show assertion (b).

*(i) Left-hand side inequality of (a). We start by showing the left inequality of (a).
Consider matrices $\vec Q + \vec R$ and $\vec Q$. Note that, by definition of $\vec Q$ and $\vec R$, each row of $\vec Q + \vec R$ sums up to 1. Since $\vec Q$ and $\vec R$ have non-negative entries, this implies that $1$ is the largest eigenvalue of $\vec Q + \vec R$. Additionally, since $\degset{F}{v} \le \alpha_F d$, we know $\norm{\vec R}_{op} \le \alpha_F$. Then, by eigenvalue stability inequality (lemma:eigenvalue-stability) we have

\[
\left|\lambda_1(\vec Q + \vec R) - \lambda_1(\vec Q)\right| \le \norm{\vec R}_{op} \le \alpha_F.
\]

Since $\lambda_1(\vec Q + \vec R) = 1$, we have

\begin{equation}
\label{eq:lambda1-alphaF}
\left|1 - \lambda_1(\vec Q)\right| \le \alpha_F.
\end{equation}

\begin{align}
\lambda_1(\vec Q) &= \sup_{\vec x \in \mathbb R^{n-f}\setminus \{0\}} \frac{\norm{\vec Qx}_2}{\norm{x}_2} \notag \\
&\ge \frac{\norm{\vec Q \vec 1_{n-f}}_2}{\norm{\vec 1_{n-f}}_2} \notag \\
&\ge \frac{\norm{\vec Q \vec 1_{n-f}}_1}{\sqrt{n-f}\norm{\vec 1_{n-f}}_2} \notag \\
&= \frac{\norm{\vec Q \vec 1_{n-f}}_1}{n-f}.\label{eq:lambda1-through-1norm}
\end{align}

Note that

\[
\norm{\vec Q \vec 1_{n-f}}_1 = \sum_{u \in \honest} \frac{\degset{\honest}{u}}{d} = (n - f) - \frac{|\partial F|}{d}.
\]

Additionally, by expander mixing lemma ([59], Lemma 4.15) we have

\[
|\partial F| \le \frac{d}{n} f(n-f) (1+\lambda).
\]

\begin{equation}
\label{eq:1norm-mixing-lemma}
\norm{\vec Q \vec 1_{n-f}}_1 = (n - f) - \frac{|\partial F|}{d} \ge (n-f) - (n-f) \frac{f}{n}(1 + \lambda) = (n-f)\left(1 - \frac{f}{n}(1 + \lambda)\right).
\end{equation}

By combining eq:1norm-mixing-lemma and eq:lambda1-through-1norm, we get

\begin{align*}
\lambda_1(\vec Q) &\ge \frac{\norm{\vec Q \vec 1_{n-f}}_1}{n-f} \\
&\ge \frac{(n-f)\left(1 - \frac{f}{n}(1 + \lambda)\right)}{n-f} \\
&= 1 - \frac{f}{n}(1 + \lambda),
\end{align*}

which together with eq:lambda1-alphaF establishes the left inequality of (a).

*(ii) Right-hand side inequality of (a). Now, we show the right inequality of (a). To upper bound $\lambda_1(\vec Q)$, we use a more involved approach. Recall that the powers of $\vec Q$ characterize probability of a random walk going from one node to another while staying within $\honest$. Then, $\frac{1}{n-f}\vec 1^{T}_{n-f} \vec Q^t \vec 1_{n-f}$ is the probability of a random walk staying within $\honest$ after $t$ steps when the initial position is chosen uniformly at random. By Theorem 4.17 of [59], such probability can be upper bounded as follows

\[
\frac{1}{n-f}\vec 1^{T}_{n-f} \vec Q^t \vec 1_{n-f} \le \left(1 - \frac{f}{n} + \lambda\left(\frac{f}{n}\right)\right)^t = \left(1 - (1 - \lambda)\frac{f}{n}\right)^t.
\]

\[
\vec 1_{n-f} \vec Q^t \vec 1_{n-f} \le (n-f)\left(1 - (1 - \lambda)\frac{f}{n}\right)^t.
\]

Note that since entries of $\vec Q^t$ are non-negative, the maximum row sum of $\vec Q^t$ upper bounds $\lambda_1(\vec Q^t)$. As $\vec 1_{n-f} \vec Q^t \vec 1_{n-f}$ is the sum of all entries of $\vec Q^t$, it also upper bounds $\lambda_1(\vec Q^t)$. Then

\[
\lambda_1(\vec Q)^t = \lambda_1(\vec Q^t) \le (n-f)\left(1 - (1 - \lambda)\frac{f}{n}\right)^t,
\]

which implies that for arbitrary $t \ge 0$

\[
\left(\frac{\lambda_1(\vec Q)}{1 - (1 - \lambda)\frac{f}{n}}\right)^t \le n-f.
\]

Since the above holds true for arbitrary large $t$, we must have $\frac{\lambda_1(\vec Q)}{1 - (1 - \lambda)\frac{f}{n}} \le 1$, which establishes the right inequality of (a).

*(iii) Assertion (b). Now, we establish part (b). Since $\vec Q$ is a principal submatrix of normalized adjacency matrix $\Hat{\vec A}$ of $G$, by Cauchy interlacing law (lemma:cauchy-interlace) we know $\max\{\left|\lambda_2(\vec Q)\right|, \left|\lambda_{n-f}(\vec Q)\right|\} \le \lambda$. Thus part (b) holds true.

To bound the coordinates of the first eigenvector of $\vec Q$, we introduce two perturbations of $\vec Q$, namely $\overline{\vec Q}$ and $\underline{\vec Q}$. They have spectral properties similar to $\vec Q$, and have an explicit first eigenvector. Moreover, all entries of $\overline{\vec Q}$ and $\underline{\vec Q}$ provide a lower and an upper bound respectively of the corresponding entries of $\vec Q$. Later, we will use them to derive bounds for the first eigenvector of $\vec Q$.

Let $G, F, \vec Q, \vec R$ and $\alpha_F$ be as in lemma:spectral-Q. We define $\overline{\vec Q} =(\vec I_{n-f} - \vec R)^{-1/2}\vec Q(\vec I_{n-f} - \vec R)^{-1/2}$ and $\underline{\vec Q} = (1 - \alpha_F)\overline{\vec Q}$. Then, the following assertions hold

* $\lambda_1\left(\overline{\vec Q}\right) = 1$ with $\ell_2$-normalized eigenvector $\overline{\vec \eigen}_1$, where $\overline{\eigen}_{1w}^2 = \frac{\degset{\honest}{w}}{\sum_{u\in \honest} \degset{\honest}{u}}$ for all $w \in \honest$.

* $\lambda_1\left(\underline{\vec Q}\right) = 1 - \alpha_F$ with $\ell_2$-normalized eigenvector $\underline{\vec \eigen}_1 = \overline{\vec \eigen}_1$.

* $\max\left\{\left|\lambda_2\left(\overline{\vec Q}\right)\right|, \left|\lambda_{n-f}\left(\overline{\vec Q}\right)\right|\right\} \le \frac{\lambda}{1-\alpha_F}$.

* $\max\left\{\left|\lambda_2\left(\underline{\vec Q}\right)\right|, \left|\lambda_{n-f}\left(\underline{\vec Q}\right)\right|\right\} \le \lambda$.

* $\vec O_{(n-f) \times (n-f)} \preceq \underline{\vec Q} \preceq \vec Q \preceq \overline{\vec Q}$.

We prove different assertions separately.

*(i) Assertions (a), (b).
Recall that by definition of $\vec Q$ and $\vec R$, each row of the matrix $\vec Q + \vec R$ sums up to $1$. Then

\[
(\vec Q + \vec R)\vec 1_{n-f} = \vec 1_{n-f} \Rightarrow \vec Q\vec 1_{n-f} = (\vec I_{n-f} - \vec R)\vec 1_{n-f}.
\]

\[
(\vec I_{n-f} - \vec R)^{-1/2}\vec Q (\vec I_{n-f} - \vec R)^{-1/2} (\vec I_{n-f} - \vec R)^{1/2}\vec 1_{n-f} = (\vec I_{n-f} - \vec R)^{1/2}\vec 1_{n-f}.
\]

which implies

\[
\overline{\vec Q} (\vec I_{n-f} - \vec R)^{1/2}\vec 1_{n-f} = (\vec I_{n-f} - \vec R)^{1/2}\vec 1_{n-f}.
\]

In other words, $1$ is an eigenvalue of $\overline{\vec Q}$ with eigenvector $(\vec I_{n-f} - \vec R)^{1/2}\vec 1_{n-f}$. Note that the $w^\text{th}$ coordinate of this vector is $\sqrt{\frac{\degset{\honest}{w}}{d}}$ by definition of $\vec R$. Denote $\overline{\vec \eigen}_1$ to be $\ell_2$-normalized version of this vector. Then, we have $\overline{\eigen}_{1w} = \sqrt{\frac{\degset{\honest}{w}}{\sum_{u \in \honest}\degset{\honest}{u}}}$. This establishes (a). Part (b) follows since $\underline{\vec Q} = (1 - \alpha_F)\overline{\vec Q}$.

*(ii) Assertions (c), (d).
To show (c) and (d), we use Theorem H.1.c. of [45]. Note that entries of $\vec Q$ and $(\vec I_{n-f} - \vec R)^{-1/2}$ are non-negative, which implies $\overline{\vec Q}$ is a matrix with non-negative entries. Then, by part (a) of lemma:perron, $\lambda_1\left(\overline{\vec Q}\right)$ is the largest eigenvalue in absolute value, i.e. $\lambda_1\left(\overline{\vec Q}\right)$ is the first singular value of $\overline{\vec Q}$. In this case, $\max\left\{\left|\lambda_2\left(\overline{\vec Q}\right)\right|, \left|\lambda_{n-f}\left(\overline{\vec Q}\right)\right|\right\}$ is the second  singular value of $\overline{\vec Q}$. Also, since $\vec R \preceq \alpha_F \vec I_{n-f}$, we have $\vec I_{n-f} - \vec R \succeq (1 - \alpha_F)\vec I_{n-f}$. Hence, $(\vec I_{n-f} - \vec R)^{-1/2}$ is diagonal with every element upper bounded by $(1 - \alpha_F)^{-1/2}$. Theorem H.1.c. of [45] with $k = 1$ and $i_1 = 2$ implies

\begin{align*}
\max\left\{\left|\lambda_2\left(\overline{\vec Q}\right)\right|, \left|\lambda_{n-f}\left(\overline{\vec Q}\right)\right|\right\} &= \sigma_2\left(\overline{\vec Q}\right) \\
&\le \sigma_1\left((\vec I_{n-f} - \vec R)^{-1/2}\right) \sigma_2(\vec Q) \sigma_1\left((\vec I_{n-f} - \vec R)^{-1/2}\right)\\
&\le (1 - \alpha_F)^{-1/2} \lambda (1 - \alpha_F)^{-1/2} \\
&\le \frac{\lambda}{1 - \alpha_F}.
\end{align*}

This establishes (c). Part (d) follows since $\underline{\vec Q} = (1 - \alpha_F)\overline{\vec Q}$.

*(iii) Assertion (e). First, we show the leftmost inequality. We express $\underline{\vec Q}$ as follows

\begin{equation}
\label{eq:underline-q-rewritten}
\underline{\vec Q} = \left(\frac{\vec I_{n-f} - \vec R}{1 - \alpha_F}\right)^{-1/2}\vec Q\left(\frac{\vec I_{n-f} - \vec R}{1 - \alpha_F}\right)^{-1/2}.
\end{equation}

Since $\alpha_F < 1 - \lambda \le 1$, we have $\vec R \preceq \alpha_F \vec I_{n-f} \prec I_{n-f}$. Hence, entries of $\left(\frac{\vec I_{n-f} - \vec R}{1 - \alpha_F}\right)^{-1/2}$ are positive. Additionally, $\vec Q$ has non-negative entries, hence

\[
\underline{\vec Q} \succeq \vec O_{(n-f) \times (n-f)}.
\]

Now we show the middle inequality. Since $\vec I_{n-f} - \vec R \succeq (1 - \alpha_F)\vec I_{n-f}$, every diagonal entry of $\left(\frac{\vec I_{n-f} - \vec R}{1 - \alpha_F}\right)$ is lower bounded by $1$. Therefore, $\left(\frac{\vec I_{n-f} - \vec R}{1 - \alpha_F}\right)^{-1/2} \preceq \vec I_{n-f}$. Then, by lemma:partial-order-mult and eq:underline-q-rewritten, we get $\underline{\vec Q} \preceq \vec Q$.

Finally, we show the rightmost inequality. Similarly to eq:underline-q-rewritten, we can express $\overline{\vec Q}$ as

\[
\overline{\vec Q} = \left(\vec I_{n-f} - \vec R\right)^{-1/2} \vec Q \left(\vec I_{n-f} - \vec R\right)^{-1/2}.
\]

Since $\vec I_{n-f} - \vec R \preceq \vec I_{n-f}$, we have $\overline{\vec Q} \succeq \vec I_{n-f}^{-1/2} \vec Q \vec I_{n-f}^{-1/2} = \vec Q$.

We now provide upper and lower bounds on the entries of the first eigenvector of $\vec Q$. They will be used to upper and lower bound the infinite series in eq:Q-series.

Consider a $(d,\lambda)$-expander graph $G = (V,E)$ of size $n$, and a set of curious nodes $F \subset V$ with $|F| = f$ and adversarial density $\alpha_F < 1-\lambda$. Let $\vec Q$ and $\vec R$ be as in (<ref>). Then, there exists an $\ell_2$-normalized eigenvector of $\vec Q$ with non-negative coordinates, denoted $\vec \eigen_1$. Moreover, for any $v\in \honest$, the following holds true

\[
(1 - \alpha_F)^{T + 1} \frac{1}{2(n-f)} \le \eigen_{1v}^2 \le (1 - \alpha_F)^{-T - 1} \frac{2}{n-f},
\]

where $T = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil$.

Note that lemma:Q-delocalization can be seen as a statement on delocalization (as in, e.g., [53]) of the first eigenvector of an arbitrary subgraph of $G$ in the worst-case, or of a random subgraph of $G$ in the average-case adversary setting. In that sense, lemma:Q-delocalization is of independent interest for research on delocalization.

Note that since $\vec Q \succeq \vec O_{(n-f) \times (n-f)}$, by part (b) of lemma:perron there exists the first eigenvector of $\vec Q$ with non-negative coordinates. Let $\vec\eigen_1$ be $\ell_2$ normalized version of such eigenvector. We establish upper and lower bounds for coordinates of $\vec \eigen_1$ using matrices $\overline{\vec Q}$ and $\underline{\vec Q}$ from lemma:spectral-Q-hat. From lemma:spectral-Q-hat, we know that

\[
\vec O_{(n-f) \times (n-f)} \preceq \underline{\vec Q} \preceq \vec Q \preceq \overline{\vec Q}.
\]

Then, using lemma:partial-order-power, for any $t \ge 0$ we get

\begin{equation}
\label{eq:chain-ineq-Q}
\underline{\vec Q}^t \preceq \vec Q^t \preceq \overline{\vec Q}^t.
\end{equation}

Using lemma:matrix-powers-first-eigenvector for $\vec Q^t$ we get

\begin{equation}
\label{eq:sandwich-Q}
\lambda_1(\vec Q)^t \vec\eigen_1\vec\eigen_1^\top - \lambda^t\vec J_{n-f} \preceq \vec Q^t \preceq \lambda_1(\vec Q)^t \vec\eigen_1\vec\eigen_1^\top + \lambda^t\vec J_{n-f}.
\end{equation}

We will first show a lower bound on the coordinates of $\vec\eigen_1$, and then an upper bound.

*(i) Lower bound on coordinates of $\vec\eigen_1$.
Using lemma:matrix-powers-first-eigenvector for $\underline{\vec Q}^t$ with part (d) of lemma:spectral-Q-hat, we get

\begin{equation}
\label{eq:sandwich-Q-underline}
\lambda_1\left(\underline{\vec Q}\right)^t \underline{\vec\eigen}_1\underline{\vec\eigen}_1^\top - \lambda^t\vec J_{n-f} \preceq \underline{\vec Q}^t.
\end{equation}

Combining the left inequality of eq:chain-ineq-Q with eq:sandwich-Q and eq:sandwich-Q-underline, we have

\[
\lambda_1\left(\underline{\vec Q}\right)^t \underline{\vec\eigen}_1\underline{\vec\eigen}_1^\top - \lambda^t\vec J_{n-f} \preceq \underline{\vec Q}^t  \preceq \vec Q^t \preceq \lambda_1(\vec Q)^t \vec\eigen_1\vec\eigen_1^\top + \lambda^t\vec J_{n-f}.
\]

By part (a) of lemma:spectral-Q, we know $\lambda_1(\vec Q) \le 1$ and by part (b) of lemma:spectral-Q-hat, we know $\lambda_1\left(\underline{\vec Q}\right) = 1 -\alpha_F$. The above implies

\[
(1 - \alpha_F)^t \underline{\vec\eigen}_1\underline{\vec\eigen}_1^\top - \lambda^t\vec J_{n-f} \preceq \vec\eigen_1\vec\eigen_1^\top + \lambda^t\vec J_{n-f},
\]

\[
(1 - \alpha_F)^t \underline{\vec\eigen}_1\underline{\vec\eigen}_1^\top - 2\lambda^t\vec J_{n-f} \preceq \vec\eigen_1\vec\eigen_1^\top.
\]

Then, for every $v \in V\setminus F$, we have

\begin{equation}
\label{eq:lower-eigen1}
(1 - \alpha_F)^t \underline{\eigen}_{1v}^2 - 2\lambda^t \le \eigen_{1v}^2.
\end{equation}

Using part (b) of lemma:spectral-Q-hat, we have

\begin{align}
\underline{\eigen}_{1v}^2 &= \frac{\degset{\honest}{v}}{\sum_{u\in \honest} \degset{\honest}{u}}. \notag\\
\intertext{Note that $d(1-\alpha_F) \le \degset{\honest}{u} \le d$ for every $u\in\honest$ by definition of $\alpha_F$, which implies}
\underline{\eigen}_{1v}^2 &\ge \frac{d(1-\alpha_F)}{(n-f)d} \notag \\
&\ge \frac{1 - \alpha_F}{n-f}. \label{eq:eigen-underline}
\end{align}

Combining eq:lower-eigen1 and eq:eigen-underline, we have

\[
\frac{(1 - \alpha_F)^{t+1}}{n-f} - 2\lambda^t \le \eigen_{1v}^2.
\]

After rearranging, the above becomes

\[
(1 - \alpha_F)^t\left(\frac{1 - \alpha_F}{n-f} - 2\left(\frac{\lambda}{1  - \alpha_F}\right)^t\right) \le \eigen_{1v}^2.
\]

Recall that $T = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil$. Then, $\left(\frac{\lambda}{1  - \alpha_F}\right)^T = \frac{1 - \alpha_F}{4(n-f)}$. Then, by plugging $t = T$ in the above we get

\[
(1 - \alpha_F)^T \frac{1 - \alpha_F}{2(n-f)} \le \eigen_{1v}^2.
\]

This gives the desired lower bound.

*(ii) Upper bound on coordinates of $\vec\eigen_1$. We now show an upper bound on the coordinates of $\vec\eigen_1$. The proof is similar to the proof of the lower bound. Using lemma:matrix-powers-first-eigenvector for $\overline{\vec Q}$ with part (c) of lemma:spectral-Q-hat, we get

\begin{equation}
\label{eq:sandwich-Q-overline}
\overline{\vec Q}^t \preceq \lambda_1\left(\overline{\vec Q}\right)^t \underline{\vec\eigen}_1\underline{\vec\eigen}_1^\top + \left(\frac{\lambda}{1 - \alpha_F}\right)^t\vec J_{n-f}.
\end{equation}

Combining the right inequality of eq:chain-ineq-Q with eq:sandwich-Q and eq:sandwich-Q-overline, we get

\[
\lambda_1(\vec Q)^t \vec\eigen_1\vec\eigen_1^\top - \lambda^t\vec J_{n-f} \preceq \vec Q^t \preceq \overline{\vec Q}^t \preceq  \lambda_1\left(\overline{\vec Q}\right)^t \overline{\vec\eigen}_1\overline{\vec\eigen}_1^\top + \left(\frac{\lambda}{1 - \alpha_F}\right)^t\vec J_{n-f}.
\]

By part (a) of lemma:spectral-Q, we know $\lambda_1(\vec Q) \ge 1 - \alpha_F$ and by part (a) of lemma:spectral-Q-hat, we know $\lambda_1\left(\overline{\vec Q}\right) = 1$. Therefore, the above implies

\[
(1 - \alpha_F)^t \vec\eigen_1\vec\eigen_1^\top - \lambda^t\vec J_{n-f} \preceq\overline{\vec\eigen}_1\overline{\vec\eigen}_1^\top + \left(\frac{\lambda}{1 - \alpha_F}\right)^t\vec J_{n-f}.
\]

\begin{align*}
(1 - \alpha_F)^t \vec\eigen_1\vec\eigen_1^\top &\preceq \overline{\vec\eigen}_1\overline{\vec\eigen}_1^\top + \left(\frac{\lambda}{1 - \alpha_F}\right)^t\vec J_{n-f} + \lambda^t\vec J_{n-f}\\
&\preceq \overline{\vec\eigen}_1\overline{\vec\eigen}_1^\top + 2\left(\frac{\lambda}{1 - \alpha_F}\right)^t\vec J_{n-f}.
\end{align*}

Then, for every $v \in V\setminus F$, we have

\[
(1 - \alpha_F)^t \eigen_{1v}^2 \le \overline{\eigen}_{1v}^2 + 2\left(\frac{\lambda}{1 - \alpha_F}\right)^t,
\]

\begin{equation}
\label{eq:upper-eigen1}
\eigen_{1v}^2 \le (1 - \alpha_F)^{-t} \left( \overline{\eigen}_{1v}^2 + 2\left(\frac{\lambda}{1 - \alpha_F}\right)^t\right).
\end{equation}

From part (a) of lemma:spectral-Q-hat, we have

\begin{align}
\overline{\eigen}_{1v}^2 &= \frac{\degset{\honest}{v}}{\sum_{u\in \honest} \degset{\honest}{u}}. \notag\\
\intertext{Note that $d(1-\alpha_F)\degset{\honest}{u} \le d$ for every $u\in\honest$ by definition of $\alpha_F$, which implies}
\overline{\eigen}_{1v}^2 &\le \frac{d}{(n-f)d(1-\alpha_F)} \notag \\
&\le \frac{1}{(n-f)(1-\alpha_F)}. \label{eq:eigen-overline}
\end{align}

Combining eq:upper-eigen1 and eq:eigen-overline, we get

\[
\eigen_{1v}^2 \le (1 - \alpha_F)^{-t} \left( \frac{1}{(n-f)(1-\alpha_F)} + 2\left(\frac{\lambda}{1 - \alpha_F}\right)^t\right).
\]

Recall that $T = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil$. Then, $\left(\frac{\lambda}{1  - \alpha_F}\right)^T = \frac{1 - \alpha_F}{4(n-f)}$. Then, by plugging in $t = T$ in the above we get

\begin{align*}
\eigen_{1v}^2 &\le (1 - \alpha_F)^{-T} \left( \frac{1}{(n-f)(1-\alpha_F)} + \frac{1 - \alpha_F}{2(n-f)}\right)\\
&\le (1 - \alpha_F)^{-T}  \frac{2}{(n-f)(1-\alpha_F)}.
\end{align*}

This gives the desired upper bound.

We now provide an upper and a lower bound for the matrix $(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}$ from lemma:reduction-rw.

Consider a $(d,\lambda)$-expander graph $G = (V,E)$ of size $n$ and a set $F \subseteq V$ of size $f$ and adversarial density $\alpha_F$. Let $\vec Q$ and $\vec R$ be as in (<ref>). Consider an arbitrary $\rho \in [0,1]$. Then, the following asserions hold true

* $(\vec I_{n-f} - (1-\rho)\vec Q)^{-1} \preceq  \vec I_{n-f} + (1-\lambda)^{-1}\left(\frac{2n (1 - \alpha_F)^{-\Tilde{T}}}{(\rho(n-f) + f)(n-f)}  + \lambda\right) \vec J_{n-f}$.

* $(\vec I_{n-f} - (1-\rho)\vec Q)^{-1} \succeq \vec I_{n-f} + \frac{n(1-\alpha_F)^{\Tilde{T}}(1-\rho)^{\Tilde{T}}}{8(\rho(n-f) + f)(n-f)} \vec J_{n-f}$.

where $\Tilde{T} = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil \left(\log_{\frac{\lambda}{1 - \alpha_F}}(1 - \alpha_F) + 2\right) + 2$.

First, we establish the upper bound (a), and then the lower bound (b).

*(i) Assertion (a). First, we show an upper bound. Let $\vec\eigen_1$ be the $\ell_2$-normalized first eigenvector of $\vec Q$ as given in lemma:Q-delocalization. Then, by lemma:matrix-powers-first-eigenvector we have for any $t \ge 0$

\begin{align}
\vec Q^t &\preceq \lambda_1(\vec Q)^t \vec \eigen_{1} \vec \eigen_{1}^\top + \max\{\left|\lambda_2(\vec Q)\right|, \left|\lambda_{n - f}(\vec Q)\right|\}^t \vec J_{n-f}. \notag \\
\intertext{By part (b) of \lemmaref{lemma:spectral-Q} , $\max\{\left|\lambda_2(\vec Q)\right|, \left|\lambda_{n - f}(\vec Q)\right|\} \le \lambda$, hence,}
\vec Q^t &\preceq \lambda_1(\vec Q)^t \vec \eigen_{1} \vec \eigen_{1}^\top + \lambda^t\vec J_{n-f}. \label{eq:qt-upper}
\end{align}

Then, by eq:Q-series, we get

\begin{align}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}
&=\sum_{t = 0}^{\infty} (1-\rho)^t\vec Q^t \notag\\
&\preceq \vec I_{n-f} + \sum_{t = 1}^{\infty} (1-\rho)^t \vec Q^t. \notag
\intertext{From \equationref{eq:qt-upper}, we have}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}  &\preceq \vec I_{n-f} + \sum_{t = 1}^{\infty} (1- \rho)^t\left(\lambda_1(\vec Q)^t \vec \eigen_1 \vec \eigen_1^\top + \lambda^t \vec J_{n-f}\right) \notag\\
&\preceq \vec I_{n-f} + \vec \eigen_1 \vec \eigen_1^\top  \sum_{t = 1}^{\infty} (1- \rho)^t \lambda_1(\vec Q)^t + \vec J_{n-f} \sum_{t = 1}^{\infty} (1-\rho)^t \lambda^t. \notag
\intertext{By reducing the infinite geometric series, we get}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1} &\preceq \vec I_{n-f} + \frac{(1-\rho)\lambda_1(\vec Q)}{1 - (1-\rho)\lambda_1(\vec Q)} \vec \eigen_1 \vec \eigen_1^\top + \frac{\lambda(1-\rho)}{1 - \lambda(1-\rho)} \vec J_{n-f}. \notag
\intertext{Since $\lambda_1(\vec Q) \le 1$ and $1 - \rho \le 1$, we have}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1} &\preceq \vec I_{n-f} + \frac{1}{1 - (1-\rho)\lambda_1(\vec Q)} \vec \eigen_1 \vec \eigen_1^\top + \frac{\lambda}{1 - \lambda} \vec J_{n-f}. \notag
\intertext{We know $\lambda_1(\vec Q) \le 1 - (1 - \lambda)\frac{f}{n}$ by part (a) of \lemmaref{lemma:spectral-Q}, hence}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1} &\preceq \vec I_{n-f} + \left(\frac{1}{1 - (1-\rho)(1 - (1-\lambda)f/n)} \vec \eigen_1 \vec \eigen_1^\top + \frac{\lambda}{1 - \lambda}\right) \vec J_{n-f} \notag\\
&= \vec I_{n-f} + \left(\frac{1}{\rho(1 - (1-\lambda)f/n) + (1-\lambda)f/n} \vec \eigen_1 \vec \eigen_1^\top + \frac{\lambda}{1 - \lambda}\right) \vec J_{n-f}\notag\\
&\preceq \vec I_{n-f} + \left(\frac{1}{(1-\lambda)(\rho(1 - f/n) + f/n)} \vec \eigen_1 \vec \eigen_1^\top + \frac{\lambda}{1 - \lambda}\right) \vec J_{n-f}\notag\\
&\preceq \vec I_{n-f} + \frac{1}{1-\lambda}\left(\frac{n}{\rho(n - f) + f} \vec \eigen_1 \vec \eigen_1^\top + \lambda\right) \vec J_{n-f}. \label{eq:series-qt-upper}
\end{align}

Set $T_1 = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil$. Recall that, from lemma:Q-delocalization we have

\[
\vec \eigen_1 \vec \eigen_1^\top \preceq  \frac{2 (1 - \alpha_F)^{-T_1 - 1}}{(n-f)}  \vec J_{n-f}.
\]

Substituting the above into eq:series-qt-upper, we get

\begin{align*}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}
&\preceq \vec I_{n-f} + (1-\lambda)^{-1}\left(\frac{2n (1 - \alpha_F)^{-T_1 - 1}}{(\rho(n-f) + f)(n-f)}  + \lambda\right) \vec J_{n-f}.
\intertext{Since $T_1 + 1 \le \Tilde{T} = T_1\left(\log_{\frac{\lambda}{1 - \alpha_F}}(1 - \alpha_F) + 2\right) + 2$, we finally get}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}
&\preceq \vec I_{n-f} + (1-\lambda)^{-1}\left(\frac{2n (1 - \alpha_F)^{-\Tilde{T}}}{(\rho(n-f) + f)(n-f)}  + \lambda\right) \vec J_{n-f},
\end{align*}

which concludes the proof of assertion (a).

*(ii) Assertion (b). Now, we derive a lower bound in a similar way. Note that by lemma:matrix-powers-first-eigenvector we have for any $t \ge 0$

\begin{align}
\vec Q^t &\succeq \lambda_1(\vec Q)^t \vec \eigen_{1} \vec \eigen_{1}^\top - \max\{\left|\lambda_2(\vec Q)\right|, \left|\lambda_{n - f}(\vec Q)\right|\}^t \vec J_{n-f}. \notag \\
\intertext{By part (b) of \lemmaref{lemma:spectral-Q}, $\max\{\left|\lambda_2(\vec Q)\right|, \left|\lambda_{n - f}(\vec Q)\right|\} \le \lambda$, hence,}
\vec Q^t &\succeq \lambda_1(\vec Q)^t \vec \eigen_{1} \vec \eigen_{1}^\top - \lambda^t\vec J_{n-f}. \label{eq:qt-lower}
\end{align}

Note that all entries of $\vec Q$ are non-negative, hence entries of $\vec Q^t$ will be non-negative for any $t \ge 1$. By eq:Q-series, we get for any $T_2 \ge 1$

\begin{align}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&=\sum_{t = 0}^{\infty} \vec (1-\rho)^t \vec Q^t \notag\\
&=\vec Q^0 + \sum_{t = 1}^{T_2 - 1} (1 - \rho)^t\vec Q^t + \sum_{t=T_2}^\infty \vec Q^t \vec (1-\rho)^t \vec Q^t \notag\\
&\succeq \vec I_{n-f} + \sum_{t = T_2}^{\infty} (1-\rho)^t \vec Q^t. \notag
\intertext{From \equationref{eq:qt-lower}, we have}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} + \sum_{t = T_2}^{\infty} (1-\rho)^t\left(\lambda_1(\vec Q)^t \vec \eigen_1 \vec \eigen_1^\top - \lambda^t \vec J_{n-f}\right). \label{eq:series-qt-lower}
\end{align}

Recall that, by lemma:Q-delocalization we have

\[
\vec \eigen_1 \vec \eigen_1^\top \succeq  \frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)}  \vec J_{n-f}.
\]

Substituting this into eq:series-qt-lower, we get

\begin{align}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1} &\succeq \vec I_{n-f} + \sum_{t = T_2}^{\infty} (1-\rho)^t\left(\lambda_1(\vec Q)^t \vec \eigen_1 \vec \eigen_1^\top - \lambda^t \vec J_{n-f}\right) \notag\\
&\succeq \vec I_{n-f} + \sum_{t = T_2}^{\infty} (1-\rho)^t\left(\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \lambda^t\right) \vec J_{n-f}. \label{eq:series-qt-lower-eigen}
\end{align}

Set $T_2 = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}} \left( \frac{(1-\alpha_F)^{T_1 + 1}}{4(n-f)} \right)\right\rceil$. Then, for any $t \ge T_2$ we have

\begin{align}
\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \lambda^t
&= \lambda_1(\vec Q)^t \left(\frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \left(\frac{\lambda}{\lambda_1(\vec Q)}\right)^t\right). \notag \\
\intertext{By part (a) \lemmaref{lemma:spectral-Q}, $\lambda_1(\vec Q) \ge 1 - \alpha_F$, hence}
\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \lambda^t
&\ge \lambda_1(\vec Q)^t \left(\frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \left(\frac{\lambda}{1-\alpha_F}\right)^t\right). \notag
\intertext{Since $t \ge T_2$ and $1 - \alpha_F > \lambda$, we get}
\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \lambda^t
&\ge \lambda_1(\vec Q)^t \left(\frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \left(\frac{\lambda}{1-\alpha_F}\right)^{T_2}\right). \notag
\intertext{With $T_2$ defined as above, we get}
\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \lambda^t
&\ge \lambda_1(\vec Q)^t \left(\frac{(1 - \alpha_F)^{T_1 + 1}}{2(n-f)} - \frac{(1-\alpha_F)^{T_1 + 1}}{4(n-f)}\right) \notag \\
&=\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{4(n-f)}. \label{eq:series-qt-subexpession}
\end{align}

Substituting eq:series-qt-subexpession into eq:series-qt-lower-eigen, we get

\begin{align}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} + \sum_{t = T_2}^{\infty} (1-\rho)^t\lambda_1(\vec Q)^t \frac{(1 - \alpha_F)^{T_1 + 1}}{4(n-f)} \vec J_{n-f}.\notag
\intertext{By reducing the infinite geometric series, we get}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} + \frac{(1-\rho)^{T_2}\lambda_1(\vec Q)^{T_2}}{1 - (1-\rho)\lambda_1(\vec Q)} \cdot \frac{(1 - \alpha_F)^{T_1 + 1}}{4(n-f)} \vec J_{n-f}.\notag
\intertext{From part (a) of \lemmaref{lemma:spectral-Q}, we have $\lambda_1(\vec Q) \ge 1 - \alpha_F$, hence}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} + \frac{1}{1 - (1-\rho)\lambda_1(\vec Q)} \cdot \frac{(1 - \alpha_F)^{T_2 + T_1 + 1} (1-\rho)^{T_2}}{4(n-f)} \vec J_{n-f}. \notag
\intertext{From part (a) of \lemmaref{lemma:spectral-Q}, we also have $\lambda_1(\vec Q) \ge 1 - (1 + \lambda)f/n$, hence}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} + \frac{1}{1 - (1-\rho)(1 - (1 + \lambda)f/n)} \cdot \frac{(1 - \alpha_F)^{T_2 + T_1 + 1} (1-\rho)^{T_2}}{4(n-f)} \vec J_{n-f}\notag\\
&= \vec I_{n-f} + \frac{1}{(1-\rho)(1 + \lambda)f/n + \rho} \cdot \frac{(1 - \alpha_F)^{T_2 + T_1 + 1} (1-\rho)^{T_2}}{4(n-f)} \vec J_{n-f}. \notag
\intertext{As $\lambda + 1 \ge 1$, we have}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} + \frac{1}{(1 + \lambda)((1-\rho)f/n + \rho)} \cdot \frac{(1 - \alpha_F)^{T_2 + T_1 + 1} (1-\rho)^{T_2}}{4(n-f)} \vec J_{n-f}. \notag
\intertext{As $\lambda + 1 \le 2$, we have}
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1}
&\succeq \vec I_{n-f} +  \frac{n(1-\alpha_F)^{T_2 + T_1 + 1}(1-\rho)^{T_1}}{8(\rho(n-f) + f)(n-f)} \vec J_{n-f}. \label{eq:series-qt-almost}
\end{align}

Also, note that, by definition of $T_1$ and $T_2$, we have

\begin{align*}
T_2 + T_1 + 1 &= \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}} \left( \frac{(1-\alpha_F)^{T_1 + 1}}{4(n-f)} \right)\right\rceil + T_1 + 1\\
&\le \log_{\frac{\lambda}{1 - \alpha_F}} \left( \frac{(1-\alpha_F)^{T_1 + 1}}{4(n-f)} \right) + T_1 + 2 \\
&= T_1\log_{\frac{\lambda}{1 - \alpha_F}}\left(1 - \alpha_F\right) + \log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right) + T_1 + 2\\
&= T_1\log_{\frac{\lambda}{1 - \alpha_F}}\left(1 - \alpha_F\right) + 2T_1 + 2\\
&= \Tilde{T}.
\end{align*}

Combining this and $\Tilde{T} \ge T_1$ with eq:series-qt-almost, we finally get

\[
(\vec I_{n-f} - (1-\rho) \vec Q)^{-1} \succeq \vec I_{n-f} +  \frac{n(1-\alpha_F)^{\Tilde{T}}(1-\rho)^{\Tilde{T}}}{8(\rho(n-f) + f)(n-f)} \vec J_{n-f},
\]

which concludes the proof of assertion (b).

By putting everything together, we obtain the desired bound on the maximal divergence.

Consider an undirected connected $(d,\lambda)$-expander graph $G=(V,E)$ of size $n$, a set of curious nodes $F \subset V$ with $|F| = f$ and adversarial density $\alpha_F < 1-\lambda$. Consider a $(1+\rho)$-cobra walk (or $\rho$-Dandelion) with $\rho < 1$. Then, for every $v,u \in \honest$, the following holds true

\[
\divinfty{\seqadv{v}}{\seqadv{u}} \le \ln(\rho(n-f) + f) - 2\Tilde{T}\ln(1 - \alpha_F) - \Tilde{T}\ln(1 - \rho) - \ln(1-\lambda) + \ln(24) ,
\]

where $\Tilde{T}  = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil \left(\log_{\frac{\lambda}{1 - \alpha_F}}(1 - \alpha_F) + 2\right) + 2$.

From part (a) of lemma:Q-powers-upper-bound, for any $v,w \in \honest$, we have

\begin{align}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}_{vw}
&\le 1 + (1-\lambda)^{-1}\left(\frac{2n (1 - \alpha_F)^{-\Tilde{T}}}{(\rho(n-f) + f)(n-f)}  + \lambda\right)\notag\\
&= (1-\lambda)^{-1}\left(\frac{2n (1 - \alpha_F)^{-\Tilde{T}}}{(\rho(n-f) + f)(n-f)}  + 1\right).\label{eq:upper-vw}
\end{align}

Also, from part (b) of lemma:Q-powers-upper-bound, for any $u,w \in \honest$, we have

\begin{align}
(\vec I_{n-f} - (1-\rho)\vec Q)^{-1}_{uw} \ge \frac{n(1-\alpha_F)^{\Tilde{T}}(1-\rho)^{\Tilde{T}}}{8(\rho(n-f) + f)(n-f)}. \label{eq:lower-uw}
\end{align}

Then, by lemma:sufficient-varepsilon-0 and lemma:dandelion-reduction we have for both $\rho$-Dandelion and $(1 + \rho)$-cobra walk.

\begin{align*}
\divinfty{\seqadv{v}}{\seqadv{u}}
&\le \max_{w \in \honest}\ln\frac{(\vec I_{n-f} - (1 - \rho)\vec Q)^{-1}_{vw}}{(\vec I_{n-f} - (1 - \rho)\vec Q)^{-1}_{uw}}.
\intertext{By substituting \equationref{eq:upper-vw} and \equationref{eq:lower-uw}, we get}
\divinfty{\seqadv{v}}{\seqadv{u}}&\le \ln\left(\frac{(1-\lambda)^{-1}\left(\frac{2n (1 - \alpha_F)^{-\Tilde{T}}}{(\rho(n-f) + f)(n-f)}  + 1\right)}{\frac{n(1-\alpha_F)^{\Tilde{T}}(1-\rho)^{\Tilde{T}}}{8(\rho(n-f) + f)(n-f)}}\right).
\intertext{By rearranging the terms, we get}
\divinfty{\seqadv{v}}{\seqadv{u}} &\le \ln\left(16(1 - \rho)^{-\Tilde{T}} + \frac{8(\rho(n-f) + f)(n-f)}{n(1-\alpha_F)^{\Tilde{T}}(1-\rho)^{\Tilde{T}}}\right) - \ln(1 - \lambda) .
\intertext{Since $n-f\le n$, we have}
\divinfty{\seqadv{v}}{\seqadv{u}}
&\le \ln\left(16(1 - \rho)^{-\Tilde{T}} + \frac{8(\rho(n-f) + f)}{(1-\alpha_F)^{\Tilde{T}}(1-\rho)^{\Tilde{T}}}\right) - \ln(1 - \lambda) \\
&=\ln\left(16(1 - \rho)^{-\Tilde{T}} + 8(\rho(n-f) + f))(1-\alpha_F)^{-\Tilde{T}}(1-\rho)^{-\Tilde{T}}\right) - \ln(1 - \lambda).
\intertext{Since $\rho(n-f) + f \ge 1$ and $(1-\alpha_F)^{-\Tilde{T}} \ge 1$, have }
\divinfty{\seqadv{v}}{\seqadv{u}}&\le \ln\left(24(\rho(n-f) + f))(1-\alpha_F)^{-\Tilde{T}}(1-\rho)^{-\Tilde{T}}\right) - \ln(1 - \lambda) \\
&\le \ln(\rho(n-f) + f) - \Tilde{T}\ln(1-\alpha_F) - \Tilde{T}\ln(1-\rho) - \ln(1 - \lambda) + \ln(24),
\end{align*}

which concludes the proof.

§.§ Proof of thm:main

First, put $\alpha = f/d$ and consider the worst-case adversary. The adversarial density $\alpha_F$ is upper bounded by $\alpha = f/d$ since the neighbourhood of every node has size $d$ and contains at most $f$ curious nodes. Then $\mathcal P$ is $\varepsilon$-DP with $\alpha = f/d$ against the worst-case adversary by lemma:bound-d-infty-joint.

Now, put $\alpha$ as in lemma:adversarial-density and consider the average-case adversary. For the average-case adversary, by lemma:adversarial-density, $\alpha_F$ is upper bounded by $\alpha$ with high probability. Therefore $\mathcal P$ is $\varepsilon$-DP with $\alpha$ as in lemma:adversarial-density against the average-case adversary by lemma:bound-d-infty-joint and eq:average-guarantee-probability.

§ DISSEMINATION TIME VS. PRIVACY TRADE-OFF: PROOFS OF SECTION <REF>

In this part of the appendix, we present detailed proofs of theorems from Section <ref>.

§.§ Privacy guarantees on near-Ramanujan graphs (Proof of corollary:privacy-nr)

The proof of corollary:privacy-nr relies on the two following observations. First, we upper bound the value of $\alpha$ in lemma:adversarial-density for dense near-Ramanujan graphs.

Let $\mathcal G$ be a family of $d$-regular near-Ramanujan graphs with $n$ nodes and $d \in n^{\Omega_n(1)}$. Suppose $f/n \in 1 - \Omega_n(1)$. Let $G \in \mathcal G$ and let $\alpha$ be as in lemma:adversarial-density. Then

\[
\alpha \in 1 - \Omega_n(1).
\]

Set $\beta = f/n$ and $\gamma = \ln(n)/(ed)$, as in lemma:adversarial-density. Note that since $d \in n^{\Omega_n(1)}$, we have $\gamma \in o_n(1)$. Select $n$ large enough so that $\gamma < 1/(8e)$. We consider two cases: when $\beta < 1/(8e)$ and when $\beta \ge 1/(8e)$. In the first case, by the first part of lemma:adversarial-density, we have

\begin{equation}
\label{eq:alpha-ub-nr-1}
\alpha \le 4e\frac{\max\{\gamma, \beta\}}{1 + \max \{\ln(\gamma) - \ln(\beta), 0\}} \le 4e\max\{\gamma, \beta\} < 1/2,
\end{equation}

hence, $\alpha \in 1 - \Omega_n(1)$ in this case. Now, consider the case when $\beta \ge 1/(8e)$. Set $c = 1/(8e)$ and $\delta = \frac{n/f - 1}{2} \in O_n(1)$. Then, $\beta \ge c$. Note that since $d \in n^{\Omega_n(1)}$, we have $d \in \omega_n(\log(n))$. Select $n$ large enough so that $d > 64e^2\ln(n)/\delta^2$, i.e., $d > \frac{\ln(n)}{c^2\delta^2}$. Then, by second part of lemma:adversarial-density, we have

\begin{equation}
\label{eq:alpha-ub-nr-2}
\alpha \le (1 + \delta)\beta =  \left(\frac{n/f - 1}{2} + 1\right) \cdot \frac{f}{n} = \frac{f/n + 1}{2} \in 1 - \Omega_n(1),
\end{equation}

where the last transition follows from the fact that $f/n \in 1 -\Omega_n(1)$. Combining eq:alpha-ub-nr-1 and eq:alpha-ub-nr-2 concludes the proof.

Now, we bound from above the value of $\Tilde{T}$ from thm:main.

Let $\mathcal G$ be a family of $d$-regular near-Ramanujan graphs with $n$ nodes and $d \in n^{\Omega_n(1)}$. Suppose $f/d \in 1 - \Omega_n(1)$ (resp. $f/n \in 1 - \Omega_n(1)$). Let $G \in \mathcal G$ and let $\Tilde{T}$ be as in thm:main. Then, both against a worst-case and an average-case adversary, we have

\[
\Tilde{T} \in O_n(1).
\]

By definition of near-Ramanujan graphs, we have $\lambda \in O_n\left(d^{-1/2}\right)$. Since $d \in n^{\Omega_n(1)}$, this yields

\begin{equation}
\lambda \in n^{-\Omega_n(1)}.
\label{eq:lambda-nr}\end{equation}

Also, recall that

\[
\Tilde{T} = \left\lceil\log_{\frac{\lambda}{1 - \alpha}}\left(\frac{1 - \alpha}{4(n-f)}\right)\right\rceil \left(\log_{\frac{\lambda}{1 - \alpha}}(1 - \alpha) + 2\right) + 2.
\]

Note that against a worst-case adversary we have $\alpha = f/d \in 1 - \Omega_n(1)$. We also know that $\alpha \in 1 - \Omega_n(1)$ against an average-case adversary, as per lemma:alpha-nr. Then, regardless of the type of the adversary, we have

\begin{equation}
\label{eq:alpha-bounded-away-nr}
\alpha \in 1 -\Omega_n(1).
\end{equation}

From eq:lambda-nr and (<ref>), we get $\frac{\lambda}{1 - \alpha} \in n^{-\Omega_n(1)}$ and $\frac{1 - \alpha}{4(n-f)} \in n^{-O_n(1)}$. Hence, the following holds true

\begin{equation}
\label{eq:tilde-t-expression-ub}
\log_{\frac{\lambda}{1 - \alpha}}\left(\frac{1 - \alpha}{4(n-f)}\right) = \frac{\ln\left(\frac{1 - \alpha}{4(n-f)}\right)}{\ln\left(\frac{\lambda}{1 - \alpha}\right)} \in O_n(1).
\end{equation}

Additionally, since $\alpha \in 1 - \Omega_n(1)$ as per eq:alpha-bounded-away-nr, using eq:lambda-nr we get $\log_{\frac{\lambda}{1 - \alpha}}(1 - \alpha) \in O_n(1)$. Combining this with eq:tilde-t-expression-ub, we get

\[
\Tilde{T} = \left\lceil\log_{\frac{\lambda}{1 - \alpha}}\left(\frac{1 - \alpha}{4(n-f)}\right)\right\rceil \left(\log_{\frac{\lambda}{1 - \alpha}}(1 - \alpha) + 2\right) + 2\in O_n(1),
\]

which concludes the proof.

Recall, that by thm:main
, $\mathcal P$ satisfies $\varepsilon$-DP with

\[
\varepsilon = \ln(\rho(n-f) + f) - 2\Tilde{T}\ln(1 - \alpha) - \Tilde{T}\ln(1 - \rho) - \ln(1-\lambda) + \ln(24),
\]

and $\Tilde{T}  = \left\lceil\log_{\frac{\lambda}{1 - \alpha}}\left(\frac{1 - \alpha}{4(n-f)}\right)\right\rceil \left(\log_{\frac{\lambda}{1 - \alpha}}(1 - \alpha) + 2\right) + 2.$ Note that for both the worst and the average-case adversary, we have $\alpha \in 1 - \Omega_n(1)$ (lemma:alpha-nr) and $\Tilde{T} \in O_n(1)$ (lemma:t-tilde-nr). Then

\begin{equation}
\label{eq:t-tilde-alpha}
- 2\Tilde{T}\ln(1 - \alpha) \in O_n(1).
\end{equation}

Since we are given $1 - \rho \in \Omega_n(1)$, we also have

\begin{equation}
\label{eq:t-tilde-rho}
- \Tilde{T}\ln(1 - \rho) \in O_n(1).
\end{equation}

Finally, for dense near-Ramanujan graphs we have $\lambda \in O_n(d^{-1/2}) \subseteq n^{-\Omega_n(1)}$, hence,

\[
- \ln(1-\lambda) \in O_n(1).
\]

Combining this with eq:t-tilde-alpha and eq:t-tilde-rho, for both adversaries we have

\begin{align*}
\varepsilon &= \ln(\rho(n-f) + f) - 2\Tilde{T}\ln(1 - \alpha) - \Tilde{T}\ln(1 - \rho) - \ln(1-\lambda) + \ln(24) \\
&\in \ln(\rho(n-f) + f) + O_n(1),
\end{align*}

which concludes the proof.

§.§ Trade-off for cobra walks

§.§.§ Proof of the tightness of corollary:privacy-nr

In this section, we show the following result.

Let $\mathcal P$ be a $(1 + \rho)$-cobra walk with $\rho \in [0,1]$ and let $\mathcal G$ be a family of $d$-regular near-Ramanujan graphs with $n$ nodes, $f$ of which are curious and $d \in n^{\Omega_n(1)}$. Suppose $f \in n^{\Omega_n(1)}$ and $f/n \in 1-\Omega_n(1)$, and $\mathcal P$ satisfies $\varepsilon$-DP against either an average-case or a worst-case adversary on $G \in \mathcal G$. Then,

\[\varepsilon \in \ln{(\rho (n-f) + f)}+\Omega_n(1).\]

This effectively means that corollary:privacy-nr is tight for cobra walks. Note that the statement of thm:cobra-privacy-lower with $\rho = 0$ follows from thm:universal-impossibility. Without loss of generality, we assume $\rho > 0$ in the remaining.

First, we prove two helpful auxiliary lemmas.

Let $G = (V,E)$ be an undirected connected graph of size $n \ge 3$. Let $F \sim \uniformsubset{f}{V}$ be a random subset of $V$ of size $f \ge 3$. Then, with probability at least $2/(n-1)$, $F$ contains two nodes connected by an edge.

Let $w_1, \ldots, w_f$ be nodes of $F$, i.e., $w_1, \ldots, w_f$ are sampled uniformly at random without replacement. Fix an arbitrary node $v \in V$. Since the graph is of size at least $3$ and is connected, $v$ has at least one neighbour. Let $u \in N(v)$ be a fixed neighbour of $v$.
Note that

\begin{align*}
\Pr[u \in F \mid w_1 = v] &= \Pr[w_2=u \vee w_3 =u \vee...\vee w_f = u  \mid w_1 = v]\\
\intertext{Since events $w_i = u$ are disjoint, we get}
\Pr[u \in F \mid w_1 = v] & = \sum_{i = 2}^f \Pr[w_i = u\mid w_1 = v] = (f-1)\frac{1}{n-1} \ge \frac{2}{n-1}.
\end{align*}

Then, regardless of the value of $w_1$, it has a neighbour in set $F$ with probability $\ge 2/(n-1)$. Then, $F$ contains two nodes connected by an edge with probability $\ge 2/(n-1)$.

Let $G = (V,E)$ be an undirected connected graph of size $n \ge 3$. Let $F\subseteq V$ be of size $2\le f \le n-1$, such that there are two nodes in $F$ connected by an edge. Then, there exist $v \in \honest$ and $w_1, w_2 \in F$ such that $\{v,w_1\}, \{w_1, w_2\} \in E$.

Let $w_1', w_2'$ be two nodes in $F$ connected by an edge. Consider a subgraph $G'$ of $G$ induced on vertices of $F$, and consider a connected component of this graph containing $w_1'$ and $w_2'$. Let $F' \subseteq F$ be vertices of this component. Since $G$ is connected and $2\le|F|\le n -1$, there is an edge in $G$ between a vertex from $F'$ and a vertex from $V\setminus F'$. Let $v \in V\setminus F'$ and $w_1 \in F'$ be these vertices. Note that $v \not \in F$, because otherwise $v$ would belong to a connected component $F'$ of graph $G'$ (i.e., $v \in F'$). Then, we must have $v \in \honest$. Finally, notice that subgraph of $G$ induced on $F'$ is connected, hence, $w_1$ has a neighbour $w_2 \in F'$. Hence, we selected $v,w_1,w_2$ such that $v \in \honest$ and $w_1, w_2 \in F$ such that $\{v,w_1\}, \{w_1, w_2\} \in E$, which concludes the proof.

Now, we give a definition of passage probability, which will help us to bound $D_\infty$ from below.

Consider an execution of a $(1 + \rho)$-cobra walk with $\rho \in (0,1]$ on an undirected connected graph $G = (V,E)$. Let $F\subseteq V$ be a subset of curious nodes. For $v,u \in\honest$, define the passage probability $\passage{u}{v}$ from $u$ to $v$ as the probability of a protocol started from $u$ to reach node $v$ while not interacting with any curious nodes

\[
\passage{u}{v} = \Pr\left[\exists t \ge \starttime: \activeset_t = \{v\} \land (\activeset_i \cap F = \emptyset, \forall i \le t) \mid \activeset_{\starttime} = \{u\}\right].
\]

We now bound $\divinfty{\seqadv{v}}{\seqadv{u}}$ from below using passage probabilities between $u$ and $v$. Recall that we say cobra walk branches if an active node communicates gossip to two of its neighbours. Accordingly, we use the term “branch” (as a noun) to refer to a sequence of nodes $v_1,v_2,\ldots$ of a cobra walk such that for some $t\ge \starttime$, $v_1$ communicated the gossip to $v_2$ at round $t$, $v_2$ communicated the gossip to $v_3$ at round $t+1$, etc. Note that active nodes of a branch of a cobra walk follow the same law as a simple random walk.

Let $\mathcal P$ be a $(1 + \rho)$-cobra walk where $\rho \in (0,1]$, and consider an undirected connected graph $G = (V,E)$ of size $n \ge 3$. Let $F\subseteq V$ be a set of curious nodes of size $f \ge 1$ such that there exist two curious nodes connected by an edge. Then, there exist $v \in \honest$ such that for any $u \in \honest$ we have

\[
\divinfty{\seqadv{v}}{\seqadv{u}} \ge \ln\left(\passage{u}{v}^{-1}\right).
\]

Note that, by lemma:two-curious-with-neighbour we can select $v \in \honest$ and $w_1, w_2 \in F$ such that $\{v, w_1\}, \{w_1, w_1\} \in E$. Let $\Pi_{u\Rightarrow v}$ be the event such that

\[
\Pi_{u\Rightarrow v} = \left\{\exists t \ge \starttime: \activeset_t = \{v\} \land (\activeset_i \cap F = \emptyset, \forall i \le t) \mid \activeset_{\starttime} = \{u\}\right\}.
\]

Then, by def:passage

\begin{equation}
\label{eq:huv}
\Pr[\Pi_{u\Rightarrow v}] = \passage{u}{v}.
\end{equation}

Recall that $w_1$ and $w_2$ are connected. Then, set $\fakecomm_0 = \{(v\to w_1), (v\to w_1)\}$, $\fakecomm_i = \{(w_1\to w_2), (w_1\to w_2)\}$ for odd $i \ge 1$, and $\fakecomm_i = \{(w_2\to w_1), (w_2\to w_1)\}$ for even $i \ge 1$. Then, define $\sigma_{v,t}$ to be a set of adversarial observations which begins with a prefix $\left(\fakecomm_0, \fakecomm_1, \ldots, \fakecomm_t\right)$. In other words, in $\sigma_{v,t}$, the first contact with the curious nodes is $v$ contacting $w_1$ twice in the same round ($\fakecomm_0$), and then, during the following $t$ steps, $w_1$ and $w_2$ communicate to each other twice per round in an alternating manner ($\fakecomm_i$). Moreover, no other communication involving curious nodes happens in these $t$ rounds. Then, by the law of total probability, we can write

\[
\Pr[\seqadv{u} \in \sigma_{v,t}] = \Pr[\seqadv{u} \in \sigma_{v,t} \mid \Pi_{u\Rightarrow v}] \Pr[\Pi_{u\Rightarrow v}] + \Pr[\seqadv{u} \in \sigma_{v,t} \land \neg \Pi_{u\Rightarrow v}].
\]

Note that $\seqadv{v}$ and $\seqadv{u} \mid \Pi_{u\Rightarrow v}$ are equal in law, since cobra walk conditioned on $\Pi_{u\Rightarrow v}$ passes through an active set $\{v\}$ and cobra walk is Markovian. Then, the above becomes

\begin{equation}
\label{eq:seqadv-u-expansion}
\Pr[\seqadv{u} \in \sigma_{v,t}] = \Pr[\seqadv{v} \in \sigma_{v,t}] \Pr[\Pi_{u\Rightarrow v}] + \Pr[\seqadv{u} \in \sigma_{v,t} \land \neg\Pi_{u \Rightarrow v}].
\end{equation}

Now we will bound $\Pr[\seqadv{u} \in \sigma_{v,t} \land \neg\Pi_{u \Rightarrow v}]$.
First, for $t \ge 0$, let us denote by $\event^{(a)}_t$ the event that a cobra walk started from source $a$ did not communicate to curious nodes for the first $t$ rounds. Consider one of the branches of a cobra walk that started at $a$. It behaves like a simple random walk. Note that, from Theorem 4.17 of [59], we know that the probability of a random walk not hitting a given non-empty set in $t$ rounds approaches $0$ as $t \to \infty$. In particular, we have

\begin{equation}
\label{eq:prob-not-hitting}
\lim_{t\to \infty}\Pr[\event^{(a)}_t] = 0.
\end{equation}

Now, note that, if $\seqadv{u} \in \sigma_{v,t}$, but $\Pi_{u \Rightarrow v}$ does not hold, there are at least two active nodes in $\honest$ when $v$ communicates to $w_1$. We know that $v$ is one of them, let $a \in \honest$ be another active node. By construction of $\sigma_{v,t}$, if $\seqadv{u} \in \sigma_{v,t}$, then for at least $t$ rounds after $v$ communicated with $w_1$, there is no communication between nodes of $\honest$ and $F$.

Since $a$ is active at the beginning of these $t$ rounds, the probability of non-curious nodes not communicating to curious nodes for $t$ rounds can be upper bounded by $\Pr[\event_t^{(a)}]$ by definition of $\event_t^{(a)}$. Then, as $(\rho/d^2)^t$ is the probability of $w_1$ and $w_2$ communicating with each other for $t$ rounds (twice in each round), we have

\[
\Pr[\seqadv{u} \in \sigma_{v,t} \land \neg \Pi_{u \Rightarrow v}] \le \left(\frac{\rho}{d^2}\right)^t\Pr[\event^{(a)}_t].
\]

On the other hand, we have $\Pr[\seqadv{v} \in \sigma_{v,t}] \ge (\rho/d^2)^{t+1}$, since, with probability $\rho/d^2$, the node $v$ communicates to $w_1$ in the first round of the protocol, $w_1$ and $w_2$ exchange messages for $t$ rounds (twice in each round) with probability $(\rho/d^2)^t$. Then, by eq:prob-not-hitting

\begin{equation}
\label{eq:limsup-seqadv-u-residue}
\limsup_{t\to \infty} \frac{ \Pr[\seqadv{u} \in \sigma_{v,t} \land \neg \Pi_{u \Rightarrow v}] }{\Pr[\seqadv{v} \in \sigma_{v,t}]} \le \limsup_{t\to \infty} \Pr[\event_t^{(a)}] \frac{d^2}{\rho} = 0.
\end{equation}

Also, by eq:seqadv-u-expansion

\begin{align*}
\limsup_{t\to \infty} \frac{\Pr[\seqadv{u} \in \sigma_{v,t}]}{\Pr[\seqadv{v} \in \sigma_{v,t}]}
&= \limsup_{t\to \infty} \frac{ \Pr[\seqadv{v} \in \sigma_{v,t}] \Pr[\Pi_{u\Rightarrow v}] + \Pr[\seqadv{u} \in \sigma_{v,t} \land \neg\Pi_{u \Rightarrow v}]}{\Pr[\seqadv{v} \in \sigma_{v,t}]} \\
&= \Pr[\Pi_{u\Rightarrow v}] + \limsup_{t\to \infty} \frac{ \Pr[\seqadv{u} \in \sigma_{v,t} \land \neg\Pi_{u \Rightarrow v}] }{\Pr[\seqadv{v} \in \sigma_{v,t}]}.
\intertext{Finally, by \equationref{eq:limsup-seqadv-u-residue}, we have}
\limsup_{t\to \infty} \frac{\Pr[\seqadv{u} \in \sigma_{v,t}]}{\Pr[\seqadv{v} \in \sigma_{v,t}]}
&\le \Pr[\Pi_{u\Rightarrow v}] + 0 = \passage{u}{v}.
\end{align*}

Note that $\left(\limsup_{t \to \infty} x_t\right)^{-1} = \liminf_{t \to \infty} 1/x_t$ for any non-negative sequence $\{x_t\}$ since $x \mapsto 1/x$ is decreasing. Then, by definition of max divergence,

\[
\divinfty{\seqadv{v}}{\seqadv{u}} \ge \ln\left(\liminf_{t\to\infty} \frac{\Pr[\seqadv{v} \in \sigma_{v,t}]}{\Pr[\seqadv{u} \in \sigma_{v,t}]}\right) \ge \ln\left(\passage{u}{v}^{-1}\right),
\]

which concludes the proof.

The rest of the proof boils down to upper bounding $\passage{u}{v}$. To do so, we introduce a new process, called $(b,\rho)$-anaconda walk where $\rho \in [0,1]$ and $b \in \mathbb N$. Essentially, an anaconda walk resembles a cobra walk with two restrictions: (i) only one node (which we call “the head”) is allowed to branch, and (ii) the total number of times the head branches is limited to $b$. Note that we only introduce anaconda walk to help us derive the upper bound for passage probabilities of cobra walk.

*Anaconda walk Now, we give a detailed description of $(b,\rho)$-anaconda. An example of an execution of anaconda walk can be found in fig:anaconda. Let $G = (V,E)$ be an undirected connected graph, and let $s \in \honest$ be the source node. Then, a $(b,\rho)$-anaconda walk started from $s$ can be described as follows. At time $t$, a $(b,\rho)$-anaconda walk is characterized by a triplet $(\anaconda_t, h_t, c_t)$, where $\anaconda_t\subseteq V$ is the set of active nodes, $h_t \in Y_t$ is an active node which we refer to as the head, $c_t \in \mathbb Z$ is a counter storing the number the times head branched up to time $t$. Initially, we have $\anaconda_{\starttime} = \{s\}$, $h_{\starttime} = s$ and $c_{\starttime} = 0$ where $\starttime$ is the start time of the protocol. Consider a round $t \ge \starttime$. If $c_t < b$, the current head node $h_t$, with probability $1-\rho$, samples a random neighbor $v_1$ and communicates gossip to $v_1$, or, with probability $\rho$, samples two neighbors $v_1$ and $v_2$ with replacement and successively communicates gossip to each of them (in this case, we will say the head branches). If $c_t = b$, the head $h_t$ simply samples one random neighbor $v_1$ and communicates the gossip to $v_1$. In both cases, $v_1$ becomes a new head node ($h_{t+1}$). If the head branches in round $t$, the value of $c_t$ is updated to $c_{t+1} = c_t + 1$; otherwise, we simply have $c_{t+1} = c_t$. Every node $u \in \anaconda_t \setminus \{h_t\}$ communicates the gossip to one random neighbour. As usual, $\anaconda_{t+1}$ includes all the nodes which received the gossip in round $t$, i.e., nodes which send a message in round $t$ but do not receive any will deactivate.

[draw,use Hobby shortcut,closed=true, fill=yellow, fill opacity=0.15]
(1.4, 0).. (1.5,-0.3).. (1.6, 0) .. (1.5, 0.3);
[circle] (curious) at (1.6, 0.4) $Y_5$;

[draw,use Hobby shortcut,closed=true, fill=yellow, fill opacity=0.15]
(0.9, -0.1).. (1,0.35).. (1.1, -0.1) .. (1, -0.55);
[circle] (curious) at (1.05, 0.45) $Y_4$;

[draw,use Hobby shortcut,closed=true, fill=yellow, fill opacity=0.15]
(0.4, 0.1).. (0.5,0.5).. (0.6, 0.1) .. (0.5, -0.4);
[circle] (curious) at (0.55, 0.6) $Y_3$;

[draw,use Hobby shortcut,closed=true, fill=yellow, fill opacity=0.15]
(-0.1, 0).. (0,0.3).. (0.1, 0) .. (0, -0.3);
[circle] (curious) at (0.05, 0.45) $Y_2$;

[draw, use Hobby shortcut, closed=true, fill=yellow, fill opacity=0.15]
(-0.65, 0).. (-0.5,0.2).. (-0.35, 0) .. (-0.5, -0.2);
[circle] (curious) at (-0.5, 0.3) $Y_1$;

[every node/.style=circle, draw, inner sep=0pt,text width=1.5mm,fill=curious, scale=2.0]
[label=left:$s$] (B) at (-0.5,0) ;
(C) at (0,0.2) ;
(D) at (0.5,0.4) ;
(E) at (1,0.25) ;
(F) at (1.5,0.2) ;

[every node/.style=circle, draw, inner sep=0pt,text width=1.5mm,fill=cobra, scale=2.0]
(H) at (0,-0.2) ;
(I) at (0.5,-0.3) ;
(J) at (1,-0.1) ;
(K) at (1,-0.45) ;
(L) at (1.5,-0.2) ;

[every node/.style=circle, draw, inner sep=0pt,text width=1.5mm,fill=node, scale=2.0]

(1) at (0.7,0.05) ;
(2) at (-0.05,-0.45) ;
(4) at (1.3, 0.1) ;
(10) at (0.25,-0.1) ;
(6) at (0.7,-0.6) ;
(9) at (-0.2,0.4) ;

every edge/.style=draw=curious, thick]
[->] (B) edge (C);
[->] (C) edge (D);
[->] (D) edge (E);
[->] (E) edge (F);

every edge/.style=draw=cobra, thick]

[->] (B) edge (H);
[->] (H) edge (I);
[->] (D) edge (J);
[->] (I) edge (K);
[->] (J) edge (L);
[->] (K) edge (L);

Illustration of an anaconda walk. $s$ is the source of dissemination, $Y_i$ corresponds to nodes active at round $i$. Red nodes correspond to the main branch: each red node in $Y_i$ is a head $h_i$ respectively. As the head branches, the branching counter is updated at each step: $c_1=0; c_2 = c_3= 1; c_4=c_5=2$. Blue nodes are those that did not receive the gossip yet.

We call a “branch” of an anaconda walk a sequence of nodes $u_1,u_2,\ldots$ such that $u_1$ was a head in some round $t$, then it communicated gossip to $u_2$ in round $t$,  $u_2$ communicated gossip to $u_3$ in round $t+1$, etc.

Consider an arbitrary graph $G = (V,E)$. Let $s \in V$ be the source node and $b \in \mathbb N$. Consider a $(1+\rho)$-cobra walk with active set $\{\activeset_t\}_{t\ge \starttime}$. Then, there exists $\left\{(\anaconda_t, h_t, c_t)\right\}_{t\ge \starttime}$ such that $\anaconda_t \subseteq \activeset_t$ for every $t\ge \starttime$ and $\left\{(\anaconda_t, h_t, c_t)\right\}_{t\ge \starttime}$ has the same law as the triplet of a $(b,\rho)$-anaconda walk.

We will construct such a sequence $\{(\anaconda_t,h_t,c_t)\}_{t\ge \starttime}$ iteratively. First, define $\anaconda_\starttime = \{s\}$, $h_\starttime = \{s\}$ and $c_\starttime = 0$. Then $\anaconda_\starttime \subseteq \activeset_\starttime$. Suppose, for some $t \ge \starttime$, we have $\anaconda_t \subseteq \activeset_t$.

Consider the head node $h_t \in \anaconda_t \subseteq \activeset_t$. First, consider the case when $c_t = b$, or $h_t$ did not branch in round $t$ of a cobra walk. Let $u \in N(h_t)$ be one of the nodes to which $h_t$ communicated the gossip in round $t$ of the cobra walk. Then set $h_{t+1} = u$ and add $u$ to $\anaconda_{t+1}$. Additionally, set $c_{t+1} = c_t$. Second, consider the case when $c_t < b$ and $h_t$ branches in round $t$ of a cobra walk. Let $u_1, u_2 \in N(h_t)$ be the two neighbours of $h_t$ to which it communicated the gossip in round $t$ of the cobra. Then set $h_{t+1}$ to be either $u_1$ or $u_2$ chosen at random, and add both $u_1$ and $u_2$ to $\anaconda_{t+1}$. Also, set $c_{t+1} = c_t + 1$.

Now, consider a node $v \in \anaconda_t\setminus\{h_t\}$. Let $u \in N(v)$ be one of the nodes to which $v$ communicated the gossip in round $t$ of cobra walk. Add $u$ to $\anaconda_{t+1}$ for every $v \in \anaconda_t\setminus\{h_t\}$.

Then, $\anaconda_{t+1} \subseteq \activeset_{t+1}$ by construction. Also, notice that, while $c_t < b$, the head $h_t$ branches with probability $\rho$ at each step. After the value of $c_t$ reaches $b$, the head does not branch. Additionally, nodes in $\anaconda_t\setminus \{h_t\}$ never branch. Hence, $\left\{(\anaconda_t, h_t, c_t)\right\}_{t\ge \starttime}$ has the same law as the triplet of a $(b,\rho)$-anaconda walk.

Similarly to the study of a cobra walk, we define passage probabilities for an anaconda walk.

Consider an execution of a $(b,\rho)$-anaconda walk where $\rho \in [0,1]$ on a graph $G = (V,E)$. Let $F\subseteq V$ be the subset of curious nodes of size $f$. For $v,u \in\honest$, we denote by passage probability $\passagehat{u}{v}$ of an anaconda walk the probability that an anaconda walk started from $u$ reached an active set $\{v\}$ while not interacting with any curious nodes. More formally,

\[
\passagehat{u}{v} = \Pr[\exists t \ge \starttime: \anaconda_t = \{v\} \land (\anaconda_i \cap F = \emptyset, \forall i \le t) \mid \anaconda_\starttime = \{u\}].
\]

Now, we can use passage probabilities of an anaconda walk to upper bound the passage probabilities of a cobra walk.

Let $\rho \in [0,1]$ and $b\in \mathbb N$. Consider a $(1 + \rho)$-cobra walk and a $(b,\rho)$-anaconda walk on an undirected connected graph $G= (V,E)$. Then, for any set of curious nodes $F \subset V$ and  $v,u \in \honest$, we have

\[
\passage{u}{v} \le \passagehat{u}{v}.
\]

Consider $(1+\rho)$-cobra walk $\{\activeset_t\}_{t\ge \starttime}$ started at $u$. Let $\left\{(\anaconda_t, h_t, c_t)\right\}_{t\ge \starttime}$ be as in lemma:anaconda-coupling. By definition of passage probabilities (def:passage), we have

\begin{align*}
\passage{u}{v} &= \Pr[\exists t \ge \starttime: \activeset_t = \{v\} \land (\activeset_i \cap F = \emptyset, \forall i \le t) \mid \activeset_{\starttime} = \{u\}].
\intertext{By \lemmaref{lemma:anaconda-coupling}, we have $\anaconda_i \subseteq \activeset_i$ for every $i$. Then, $\activeset_i \cap F = \emptyset$ implies $\anaconda_i \cap F = \emptyset$ and $\activeset_t = \{v\}$ implies $\anaconda_t = \{v\}$, hence}
\passage{u}{v} &\le \Pr[\exists t \ge \starttime: \anaconda_t = \{v\} \land (\anaconda_i \cap F = \emptyset, \forall i \le t) \mid \anaconda_{\starttime} = \{u\}] \\
&= \passagehat{u}{v},
\end{align*}

which concludes the proof.

Then, to obtain an upper bound on $\passage{u}{v}$, it is enough to upper bound $\passagehat{u}{v}$. To do that, we introduce the notion of passage bandwidth. We define bandwidth $\bandwidth$ of the passage from $u$ to $v$ to be the number of times head branched during that passage. Accordingly, $\passagehat[\bandwidth < x]{u}{v}$ and $\passagehat[\bandwidth = x]{u}{v}$ are probabilities of a passage with bandwidth less than $x$ and exactly $x$ respectively.

We first upper bound passage probability with small bandwidth.

Consider an execution of a $(b,\rho)$-anaconda walk where $\rho \in (0,1]$ on $d$-regular graph $G = (V,E)$ of size $n$. Let $F\subseteq V$ be the set of curious nodes of size $f \ge 1$. Let $\vec \eigen_1 \in \mathbb R^{n-f}$ be a vector as in lemma:Q-delocalization. Then, for every $v \in \honest$, there exists $u_\star \in \honest$ such that

\[
\passagehat[\bandwidth < b]{u_\star}{v} \le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1}\cdot \frac{b+1}{(f/n + \rho(1 - f/n))(1-\lambda) }.
\]

Let $u\in \honest$ be arbitrary and consider a $(b,\rho)$-anaconda walk $\{(\anaconda_t, h_t,c_t)\}_{t\ge \starttime}$ that started at $u$. Consider the head $h_t$. It follows the distribution of a random walk on $G$. Let $\vec e_i\in \mathbb R^{n-f}$ be the $i^\text{th}$ coordinate unit vector (i.e., a vector where $i^\text{th}$ coordinate is equal to one, and the rest are $0$), and let $\vec Q$ be as in eq:block-form-absorbing-markov. Then, the probability that $h_t$ reaches $v$ in exactly $\tau$ steps without hitting any curious nodes is given by
$(\vec Q)^\tau_{uv} = \vec e_u^\top \vec Q^\tau \vec e_v$
by definition of $\vec Q$. Also, since $h_t$ branches at each step with probability $\rho$, the probability that $h_t$ branches exactly $k < b$ times in $\tau$ steps is given by ${\tau\choose k} \rho^k (1 -\rho)^{\tau-k}$. Then

\begin{equation}
\label{eq:passage-k-u-v}
\passagehat[\bandwidth = k]{u}{v} \le \sum_{\tau = 0}^\infty \vec e_u ^\top\vec Q^\tau \vec e_v \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k}.
\end{equation}

By lemma:Q-delocalization, all coordinates of $\vec \eigen_1$ are non-negative. Define the distribution $\Phi$ over the nodes in $\honest$ so that $\Phi(w) = \frac{\eigen_{1w}}{\norm{\vec\eigen_1}_1}$. Consider sampling $u$ according to $\Phi$. Then, by eq:passage-k-u-v, we have

\begin{align}
\E_{u\sim \Phi}\left[\passagehat[\bandwidth = k]{u}{v}\right] &\le \E_{u\sim \Phi}\left[\sum_{\tau = 0}^\infty \vec e_u^\top \vec Q^\tau \vec e_v \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k}\right] \notag\\
&= \sum_{\tau = 0}^\infty \sum_{u\in\honest} \Phi(u) \vec e_u^\top \vec Q^\tau \vec e_v \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k} \notag\\
&= \sum_{\tau = 0}^\infty \sum_{u\in\honest} \frac{\eigen_{1u}}{\norm{\vec\eigen_1}_1} \vec e_u^\top \vec Q^\tau \vec e_v \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k} \notag \\
&= \sum_{\tau = 0}^\infty \frac{\vec \eigen_{1}^\top}{\norm{\vec\eigen_1}_1} \vec Q^\tau \vec e_v \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k}. \notag
\intertext{By choice of $\vec \eigen_1$ from \lemmaref{lemma:Q-delocalization}, it is a first eigenvector of $\vec Q$, hence}
\E_{u\sim \Phi}\left[\passagehat[\bandwidth = k]{u}{v}\right]&\le\sum_{\tau = 0}^\infty  \lambda_1(\vec Q)^{\tau} \frac{\vec \eigen_{1}^\top}{\norm{\vec\eigen_1}_1} \vec e_v \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k} \notag\\
&= \sum_{\tau = 0}^\infty \lambda_1(\vec Q)^{\tau} \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1}  \cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k}.    \label{eq:expect-passage-k-u-v}
\end{align}

\begin{align*}
\E_{u\sim \Phi}\left[\passagehat[\bandwidth < b]{u}{v}\right]
&= \sum_{k = 0}^{b-1}\E_{u\sim \Phi}\left[\passagehat[\bandwidth < b]{u}{v}\right].
\intertext{By \equationref{eq:expect-passage-k-u-v}, we have}
\E_{u\sim \Phi}\left[\passagehat[\bandwidth < b]{u}{v}\right]
&\le \sum_{k = 0}^{b-1} \sum_{\tau = 0}^\infty \lambda_1(\vec Q)^{\tau} \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1}\cdot {\tau\choose k} \rho^k (1 -\rho)^{\tau-k}\\
&= \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \sum_{k = 0}^{b-1} \sum_{\tau = 0}^\infty \lambda_1(\vec Q)^{\tau} {\tau\choose k} \rho^k (1 -\rho)^{\tau-k}.
\intertext{Using the identity $\sum_{n = k}^\infty {n \choose k} x^{n-k} = (1-x)^{-k-1}$ for $|x| < 1$, we have}
\E_{u\sim \Phi}\left[\passagehat[\bandwidth < b]{u}{v}\right]
&\le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \sum_{k = 0}^{b-1} \frac{\rho^k}{(1 - \lambda_1(\vec Q)(1 -\rho))^{k+1}}.
\intertext{Note that since $\lambda_1(\vec Q)\le 1$ by \lemmaref{lemma:spectral-Q}, we have $\frac{\rho}{1 - \lambda_1(\vec Q)(1 -\rho)} \le \frac{\rho}{1 - (1-\rho)} = 1$, hence}
\E_{u\sim \Phi}\left[\passagehat[\bandwidth < b]{u}{v}\right]
&\le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1}\cdot \frac{1}{1 - \lambda_1(\vec Q)(1-\rho)} \sum_{k = 0}^{b-1} 1\\
&= \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{b}{1 - \lambda_1(\vec Q)(1-\rho)}.
\end{align*}

Then, there exists $u_\star \in \honest$ such that

\[
\left[\passagehat[\bandwidth < b]{u_\star}{v}\right] \le \E_{u\sim \Phi}\left[\passagehat[\bandwidth < b]{u}{v}\right] \le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{b}{1 - \lambda_1(\vec Q)(1-\rho)},
\]

which concludes the proof.

Let $\mathcal G$ be an infinite family of $d$-regular near-Ramanujan graphs of size $n$ with $d \in n^{\Omega_n(1)}$. Let $G = (V,E) \in \mathcal G$ be a graph of large enough size. Let $F\subseteq V$ be a set of $f$ curious nodes such that $f/n, \alpha_F \in 1 - \Omega_n(1)$. Let $\vec Q$ be as in eq:block-form-absorbing-markov. Then

\[
\sum_{t = 1}^\infty \max_{v,u \in\honest} \left(\vec Q^t\right)_{vu} \in O_n\left(\frac{1}{d} + \frac{1}{f}\right).
\]

Since $\mathcal G$ is near-Ramanujan with $d \in n^{\Omega_n(1)}$, we have

\begin{equation}
\label{eq:lambda-nr-2}
\lambda \in O_n(d^{-1/2}) \subseteq n^{-\Omega_n(1)}.
\end{equation}

Then, there exists $L \in O_n(1)$ such that $\lambda^L < 1/n$ for all large enough $n$.

Note that since $\vec Q$ is a principal submatrix of
a normalized adjacency matrix $\Hat{\vec A}$ of $G$, every entry of $\vec Q$ is upper bounded by $1/d$. Also, since $\vec Q \succeq \vec O_{(n-f)\times(n-f)}$ and each row of $\vec Q$ has sum less or equal to $1$, we have for every $t \ge 1$

\begin{equation}
\label{eq:qt-vu-ub}
(\vec Q^t)_{vu} \le \frac{1}{d}.
\end{equation}

Let $T = \left\lceil\log_{\frac{\lambda}{1 - \alpha_F}}\left(\frac{1 - \alpha_F}{4(n-f)}\right)\right\rceil$ be as in lemma:Q-delocalization. Recall that $\alpha_F \in 1 - \Omega_n(1)$ as given in the lemma statement. Combining this with eq:lambda-nr-2, we have $\frac{\lambda}{1 - \alpha_F} \in n^{-\Omega_n(1)}$. Since also $\frac{1 - \alpha_F}{4(n-f)} \in n^{-O_n(1)}$, we have

\begin{equation}
\label{eq:t-is-o1}
T \in O_n(1).
\end{equation}

By lemma:matrix-powers-first-eigenvector, for every $t \ge 1$ we have

\begin{align*}
(\vec Q^t)_{vu} &\le \lambda_1(\vec Q)^t \eigen_{1v} \eigen_{1u} + \lambda^t.
\intertext{By \lemmaref{lemma:Q-delocalization}, we get }
(\vec Q^t)_{vu} &\le \lambda_1(\vec Q)^t \frac{2(1 - \alpha_F)^{-T-1}}{n-f} + \lambda^t.
\end{align*}

Combining this with eq:qt-vu-ub, we get

\begin{align}
\sum_{t = 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu}
&= \sum_{t = 1}^L \max_{v,u} \left(\vec Q^t\right)_{vu} + \sum_{t = L + 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu}\notag\\
&\le \frac{L}{d} + \sum_{t = L + 1}^\infty \left(\lambda_1(\vec Q)^t \frac{2(1 - \alpha_F)^{-T-1}}{n-f} + \lambda^t\right)\notag\\
&= \frac{L}{d} + \frac{2(1 - \alpha_F)^{-T-1}}{n-f}\sum_{t = L + 1}^\infty \lambda_1(\vec Q)^t + \lambda^L \sum_{t = 1}^\infty\lambda^t. \notag
\intertext{By definition of $L$, we have}
\sum_{t = 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu} &\le \frac{L}{d} + \frac{2(1 - \alpha_F)^{-T-1}}{n-f}\sum_{t = L + 1}^\infty \lambda_1(\vec Q)^t + \frac{1}{n} \sum_{t = 1}^\infty\lambda^t. \notag
\intertext{From part (a) of \lemmaref{lemma:spectral-Q}, we get}
\sum_{t = 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu} &\le \frac{L}{d} + \frac{2(1 - \alpha_F)^{-T-1}}{n-f}\sum_{t = L + 1}^\infty \left(1 - \frac{f}{n}(1-\lambda)\right)^t + \frac{1}{n} \sum_{t = 1}^\infty\lambda^t. \notag
\intertext{Since $1 - \frac{f}{n}(1-\lambda) > 0$ and $\lambda > 0$, we get}
\sum_{t = 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu} &\le \frac{L}{d} + \frac{2(1 - \alpha_F)^{-T-1}}{n-f}\sum_{t = 0}^\infty \left(1 - \frac{f}{n}(1-\lambda)\right)^t + \frac{1}{n} \sum_{t = 0}^\infty\lambda^t. \notag
\intertext{By reducing the infinite geometric series, we get}
\sum_{t = 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu} &\le \frac{L}{d} + \frac{2(1 - \alpha_F)^{-T-1}}{n-f}\cdot \frac{n}{f(1-\lambda)} + \frac{1}{n(1-\lambda)}.\label{eq:sum-maxvu-ub}
\end{align}

Since $f/n \in 1 - \Omega_n(1)$ as given by the lemma statement, we have $n/(n-f) \in O_n(1)$. Also, since $\alpha_F \in 1 - \Omega_n(1)$ as given in the lemma statement and using eq:t-is-o1, we have $(1 - \alpha_F)^{-T-1} \in O_n(1)$. Additionally, since $\lambda \in 1 - \Omega_n(1)$ as given by the lemma statement, then $(1-\lambda)^{-1}\in O_n(1)$. Finally, since $L \in O_n(1)$, by eq:sum-maxvu-ub, we have

\[
\sum_{t = 1}^\infty \max_{v,u} \left(\vec Q^t\right)_{vu}\in O_n\left(\frac{1}{d} + \frac{1}{f}\right),
\]

which concludes the proof.

We now upper bound passage probability with large bandwidth.

Let $\mathcal G$ be an infinite family of $d$-regular near-Ramanujan graphs with $d \in n^{\Omega_n(1)}$. Let $G = (V,E) \in \mathcal G$ be a graph of large enough size. Let $F\subseteq V$ be a set of $f$ curious nodes such that $f/n, \alpha_F \in 1 - \Omega_n(1)$. Consider an execution of $(b,\rho)$-anaconda walk on $G$ with $b \in O_n(1)$. Then, for any $v,u$ the following holds true

\[
\passagehat[\bandwidth = b]{u}{v} \in O_n\left(\left(\frac{1}{d} + \frac{1}{f}\right)^b\right).
\]

Note that by definition of a bandwidth, in a passage with $\bandwidth = b$, the anaconda head branches $b$ times. Let $t_1 < t_2<\ldots < t_b$ be the times at which the head branches. For every $i \in [b]$ and $t \ge t_i$, let $y_{t}^{(i)}$ be the active node that belongs to the branch number $i$ at time $t$. For convenience, also denote $y_t^{(0)} = h_t$ to be a position of anaconda head at time $t$, and denote $t_0 = \starttime$ to be the start time of the anaconda walk. We will say that branch $i$ coalesces with branch $j$ at time $t'$ if $y_{{t'}}^{(i)} = y_{{t'}}^{(j)}$. In that case, we also have $y_{t}^{(i)} = y_{t}^{(j)}$ for all $t \ge t'$.

We will upper bound the passage probability $\passagehat[\bandwidth = b]{u}{v}$ by the probability that, starting at node $u$, all branches coalesce with each other before hitting the curious set. All branches coalesce before time $t > t_b$ if we have $y^{(0)}_t = y^{(1)}_t = \ldots = y^{(b)}_t$. If branch $i$ coalesces with branch $j < i$, we will say that $i$ merges into $j$. Then, all branches coalesce before the time $t > t_b$ if and only if for every $i \in [b]$, the branch $i$ merges into the branch $j$ for some $j < i$ before time $t$. Let $\mathcal A_{ij}$ be the event that the branch $i$ merges into the branch $j < i$ before any of the branches $0,1,\ldots,i$ hits the curious set, and let $\mathcal A_i =
\bigvee_{j = 0}^{i-1} \mathcal A_{ij}$ (i.e. $\mathcal A_i$ corresponds to branch $i$ merging into one of the branches $\{0,1,\ldots, i-1\}$). Then, all branches coalesce before hitting the curious set if and only if the event $\bigwedge_{i = 1}^b \mathcal A_i$ holds true.

Now, we will show that the probability of event $\mathcal A_i$ can be upper bounded regardless of the positions of the nodes corresponding to branches $0,1,\ldots,i-1$.
For $i \ge 0$, let $\Sigma_i$ be a sigma algebra generated by sequences $\{y_t^{(i)}\}_{t\ge t_i}$, $\{y_t^{(i-1)}\}_{t\ge t_{i-1}}$, $\ldots$, $\{y_t^{(0)}\}_{t\ge t_{0}}$. Then, $\mathcal A_{1}, \mathcal A_{2},\ldots, \mathcal A_{i} \in \Sigma_i$ by definition of $\mathcal A_j$. Consider $\Pr[\mathcal A_{ij} \mid \Sigma_{i-1}]$. Let $\vec Q$ be as in eq:block-form-absorbing-markov. Note that, conditioned on $\{y_t^{(j)}\}_{t\ge t_j}$, the probability of branch $i$ merging into $j$ at time $t > t_i$ is upper bounded by $(\vec Q^{t-t_i})_{y_{t_i}^{(i)}y_{t}^{(j)}}$. Then

\begin{align}
\Pr[\mathcal A_{ij} \mid \Sigma_{i-1}] &\le \sum_{t = t_i + 1}^\infty (\vec Q^{t-t_i})_{y_{t_i}^{(i)}y_{t}^{(j)}}\notag \\
&\le \sum_{t = t_i + 1}^\infty \max_{v,u\in V\setminus F} (\vec Q^{t-t_i})_{vu}.\notag
\intertext{By shifting the summation index, we get}
\Pr[\mathcal A_{ij} \mid \Sigma_{i-1}] &\le \sum_{t = 1}^\infty \max_{v,u\in V\setminus F} (\vec Q^{t})_{vu}. \notag
\intertext{From \lemmaref{lemma:q-powers-nr}, we have}
\Pr[\mathcal A_{ij} \mid \Sigma_{i-1}] &\in O_n\left(\frac{1}{d} + \frac{1}{f}\right).\label{eq:aij-given-sigma-ub}
\end{align}

Then, by union bound, we have

\begin{align}
\Pr[\mathcal A_{i} \mid \Sigma_{i-1}]
&= \Pr\left[\bigvee_{j = 0}^{i-1} \mathcal A_{ij} \mid \Sigma_{i-1}\right] \notag\\
&\le \sum_{j = 0}^{i-1} \Pr\left[\mathcal A_{ij} \mid \Sigma_{i-1}\right].\notag
\intertext{Using \equationref{eq:aij-given-sigma-ub} and since $i < b \in O_n(1)$, we get}
\Pr[\mathcal A_{i} \mid \Sigma_{i-1}] &\in O_n\left(\frac{1}{d} + \frac{1}{f}\right).\label{eq:ai-given-sigma-ub}
\end{align}

Then, we have

\begin{align}
\Pr\left[\bigwedge_{i=1}^b \mathcal A_i\mid\Sigma_0\right]&= \Pr\left[\bigwedge_{i=1}^b \mathcal A_i\mid \Sigma_0\right ]\notag\\
&= \prod_{i=1}^b \Pr\left[\mathcal A_i \mid \mathcal A_{i-1},\ldots,\mathcal A_1, \Sigma_0\right]\notag.
\intertext{Since $\mathcal A_{i-1},\ldots, \mathcal A_1 \in \Sigma_{i-1}$ for $i \ge 1$, we get}
\Pr\left[\bigwedge_{i=1}^b \mathcal \mathcal A_i\mid\Sigma_0\right]&= \prod_{i=1}^b \Pr[A_i \mid \Sigma_{i-1}].\notag
\intertext{Since $b \in O_n(1)$, using \equationref{eq:ai-given-sigma-ub}, we get}
\Pr\left[\bigwedge_{i=1}^b \mathcal A_i\mid\Sigma_0\right]&\in O_n\left(\frac{1}{d} + \frac{1}{f}\right). \label{eq:union-ai-ub}
\end{align}

Recall that $\passagehat[\bandwidth = b]{u}{v}$ can be upper bounded by probability of $\bigwedge_{i=1}^b \mathcal A_i$, i.e., the event that all $b$ branches coalesce before hitting the curious set.

\[
\passagehat[\bandwidth = b]{u}{v}\le \Pr\left[\bigwedge_{i=1}^b \mathcal A_i\right] = \E\left[\Pr\left[\bigwedge_{i=1}^b \mathcal A_i \mid \Sigma_0\right]\right] \in O_n\left(\frac{1}{d} + \frac{1}{f}\right),
\]

which concludes the proof.

First, for $G \in \mathcal G$, we describe such sets of curious nodes $F_\star$, such that proving a lower bound on $D_\infty$ for $F_\star$ is sufficient for a lower bound on $\varepsilon$ for both worst-case and average-case adversaries. Then, we show a lower bound on max divergence for two carefully chosen source nodes in $V\setminus F_\star$. Finally, we show that this yields a desired lower bound on $\varepsilon$ for both the worst-case and the average-case adversaries.

*(i) Selecting a set of curious nodes $F_\star$.

First, let $n$ be large enough such that we have $f \ge 3$ (since $f \in n^{\Omega_n(1)}$, such $n$ exists). Let $G = (V,E)$ be an arbitrary element of $\mathcal G$ of size $n$. Consider $F \sim\uniformsubset{f}{V}$, a set of $f$ curious nodes sampled at random. Let $\alpha$ be as in lemma:adversarial-density. Since $\mathcal G$ is a near-Ramanujan family, by lemma:alpha-nr we have $\alpha \in 1 - \Omega_n(1)$.

By lemma:adversarial-density, we have $\alpha_F \le \alpha$ with probability $1 - \frac{1}{n}$. Also, since $f\ge 3$, by lemma:two-curious-prob, with probability at least $2/(n-1)$, there is an edge between two nodes of $F$. Hence, we have both (1) $\alpha_F \le \alpha$ and (2) there is an edge between two nodes of $F$ with $\frac{2}{n-1} - \frac{1}{n} > \frac{1}{n}$. Let $F_\star$ be any set of curious nodes for which both (1) and (2) hold.

*(ii) Lower bounding max divergence. Define $T$ and $\vec\eigen_1$ as in lemma:Q-delocalization for set $F_\star$. By lemma:Q-delocalization, we have for every $v \in V\setminus F_\star$,

\[
\frac{(1-\alpha_{F_\star})^{(T+1)/2}}{\sqrt{2(n-f)}}\le \eigen_{1v} \le \frac{\sqrt{2}(1-\alpha_{F_\star})^{-(T+1)/2}}{\sqrt{(n-f)}}.
\]

Then, for every $v \in V\setminus F_\star$, we have

\[
\norm{\vec\eigen_1}_1 = \sum_{v \in V\setminus F_\star} \left|\eigen_{1v}\right| \ge \frac{(1-\alpha_{F_\star})^{(T+1)/2}\sqrt{n-f}}{\sqrt{2}}.
\]

This implies that for every $v \in V\setminus F_\star$

\begin{align}
\frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} &\le \frac{\frac{\sqrt{2}(1-\alpha_{F_\star})^{-(T+1)/2}}{\sqrt{(n-f)}}}{\frac{(1-\alpha_{F_\star})^{(T+1)/2}\sqrt{n-f}}{\sqrt{2}}}\notag\\
&= \frac{2(1-\alpha_{F_\star})^{(T+1)}}{n-f}.\notag
\intertext{By \equationref{eq:t-is-o1}, we have $T \in O_n(1)$, and also $\alpha_{F_\star} \le \alpha \in 1 - \Omega_n(1)$, therefore, }
\frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} &\in O_n\left(\frac{1}{n-f}\right).\notag
\intertext{Since $f/n\in 1-\Omega_n(1)$, we have $n-f \in \Theta_n(n)$, hence}
\frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} &\in O_n\left(\frac{1}{n}\right).
\label{eq:eigen-over-1-norm}
\end{align}

Recall that $f,d \in n^{\Omega_n(1)}$ as given by the lemma statement. Let $b \in O_n(1)$ be such that $(1/d + 1/f)^b\in O_n(1/n^2)$, and consider a $(b,\rho)$-anaconda walk.

By our choice of $F_\star$ in (ii), $F_\star$ contains at least two nodes connected by an edge. Let $v_\star$ be as given by lemma:privacy-lb-necessary-passage. Then, by lemma:passage-low-bandwidth, there exist  $u_\star \in V\setminus F_\star$ such that

\begin{align}
\passagehat[\bandwidth < b]{u_\star}{v_\star} &\le \frac{\eigen_{1v_\star}}{\norm{\vec\eigen_1}_1}\cdot \frac{b+1}{(f/n + \rho(1 - f/n))(1-\lambda)}.
\intertext{By \equationref{eq:eigen-over-1-norm}, we get}
\passagehat[\bandwidth < b]{u_\star}{v_\star}&\in O_n\left(\frac{1}{n}\cdot \frac{b+1}{(f/n + \rho(1 - f/n))(1-\lambda) } \right).
\intertext{Hence,}
\passagehat[\bandwidth < b]{u_\star}{v_\star} &\in O_n\left(\frac{b+1}{(f + \rho(n - f))(1-\lambda) } \right).
\intertext{Recall that we have $b \in O_n(1)$ and $\mathcal G$ is near-Ramanujan. Hence,}
\passagehat[\bandwidth < b]{u_\star}{v_\star} &\in O_n\left(\frac{1}{f + \rho(n - f)} \right).
\label{eq:thm-proof-low-bandwidth}
\end{align}

From lemma:passage-large-bandwidth, we have

\begin{align}
\passagehat[\bandwidth = b]{u_\star}{v_\star}
&\in O_n\left(\left(\frac{1}{d} + \frac{1}{f}\right)^b\right).\notag
\intertext{Recall that $b$ is chosen such that $\left(1/d + 1/f\right)^b \in O_n(1/n^2)$, hence,}
\passagehat[\bandwidth = b]{u_\star}{v_\star} &\in O_n\left(\frac{1}{n^2}\right).
\label{eq:thm-proof-large-bandwidth}
\end{align}

Then, by lemma:anaconda-reduction, we have

\begin{align}
\passage{u_\star}{v_\star}
&\le \passagehat{u_\star}{v_\star}\notag \\
&\le \passagehat[\bandwidth = b]{u_\star}{v_\star} + \passagehat[\bandwidth < b]{u_\star}{v_\star}. \notag
\intertext{Using \equationref{eq:thm-proof-low-bandwidth} and \equationref{eq:thm-proof-large-bandwidth}, we get}
\passage{u_\star}{v_\star}  &\in O_n\left(\frac{1}{f + \rho(n - f)} + \frac{1}{n^2}\right).\notag
\intertext{Since $f + \rho(n-f) \le n < n^2$, we have}
\passage{u_\star}{v_\star} &\in O_n\left(\frac{1}{f + \rho(n - f)}\right).\notag
\end{align}

Recall that $v_\star$ is chosen as in lemma:privacy-lb-necessary-passage. Hence, we have

\begin{equation*}
\divinfty{\seqadv{v_\star}}{\seqadv{u_\star}} \ge \ln\left(\passage{u_\star}{v_\star}^{-1}\right) \in \ln\left(f + \rho(n - f)\right) + \Omega_n(1),
\end{equation*}

which yields

\begin{equation}
\label{eq:divinfty-in-omega}
\max_{v,u\in V\setminus F_\star}\divinfty{\seqadv{v}}{\seqadv{u}} \in \ln\left(f + \rho(n - f)\right) + \Omega_n(1),
\end{equation}

*(iii) Conclusion. Recall that the above holds true for any set of curious nodes $F_\star$ for which both of the following conditions hold: (1) $\alpha_F \le \alpha$, and (2) there is an edge between two nodes of $F_\star$. As we explained in (i), this happens with probability $> 1/n$ as we select $F_\star$ randomly from the distribution $\uniformsubset{f}{V}$. Hence, as $F_\star$ is sampled uniformly at random, the lower bound in (<ref>) holds with probability $>1/n$. Hence, as per equation (<ref>) we have for average-case adversary

\begin{equation}
\label{eq:epsilon-in-omega}
\varepsilon \in \ln\left(f + \rho(n - f)\right) + \Omega_n(1).
\end{equation}

Since in the worst-case we require $\varepsilon$-DP for every set of curious nodes, (<ref>) applies to the worst-case adversary as well, which concludes the proof.

§.§.§ Dissemination time of cobra walks (proof of thm:cobra-speed)

First, we establish the following lemma, which we use to show that the expected dissemination time of $(1+\rho)$-cobra walk is a non-increasing  function of $\rho$.

Consider an undirected connected graph $G = (V,E)$ of size $n$ and let $s \in V$ be an arbitrary source node. Let $\{\activeset_{t}\}_{t \ge \starttime}$ be an active set of $(1+\rho)$-cobra walk started at $s$. Then, for every $\rho' < \rho$, there exists $\{\activeset_{t}'\}_{t \ge \starttime}$ such that $\activeset_{t}' \subseteq \activeset_t$ for every $t \ge \starttime$, and $\{\activeset_{t}'\}_{t \ge \starttime}$ has the same law as the active set of a $(1+\rho')$-cobra walk.

We construct the sequence $\{\activeset_{t}'\}_{t \ge \starttime}$ iteratively. First, define $\activeset_{\starttime}' = \activeset_\starttime = \{s\}$. Suppose for some $t \ge \starttime$, we have $\activeset_t' \subseteq \activeset_t$ and consider an arbitrary node $x \in \activeset_t'$. First, suppose $x$ does not branch in round $t$ of $(1+\rho)$-cobra walk. Then, we simply add the node $y$, to which $x$ communicated the gossip, to $\activeset_{t+1}'$. On the other hand, suppose $x$ branches in round $t$ of $(1+\rho)$-cobra walk, and let $y_1, y_2 \in N(x)$ be the two nodes to which $x$ communicated the gossip. Then, with probability $\frac{\rho'}{\rho}$ we include both $y_1,y_2$ in $\activeset_{t+1}'$ and, with probability $1 - \frac{\rho'}{\rho}$, we include only $y_1$ in $\activeset_{t+1}'$. We construct set $\activeset_{t+1}'$ by doing the described procedure for every $x \in \activeset_t'$.

Note that, by construction, every node of $\activeset_t'$ has two neighbours in $\activeset_{t+1}'$ to which it communicated the gossip with probability $\rho \cdot \frac{\rho'}{\rho} = \rho'$. Accordingly, it has only one neighbour in $\activeset_{t+1}'$ to which it communicated the gossip with probability $1 - \rho'$. This implies that $\{\activeset_{t}'\}_{t \ge \starttime}$ has the same law as the active set of a $(1 + \rho')$-cobra walk which concludes the proof.

Consider an undirected connected $(d,\lambda)$-expander graph $G$ of size $n$ with $d \ge 3$ and $\lambda \in 1 - \Omega_n(1)$. Let $\mathcal P$ be a $(1+\rho)$-cobra walk with $\rho \in \omega_n\left(\sqrt{\log(n)/n}\right)$. Then, regardless of the identity of the source, the expected dissemination time of $\mathcal P$ is a non-increasing function of $\rho$. Furthermore, the dissemination time is at least $\Omega_n\left(\log(n)/\rho\right)$ rounds in expectation and at most $O_n\left(\log(n)/\rho^3\right)$ rounds in expectation and with high probability.

First, we show that the dissemination time is a non-increasing function of $\rho$. Next, we show how the upper bound on the dissemination time follows from [12]. Finally, we show the lower bound on dissemination time. For the remainder of the proof, we fix an arbitrary source $s \in V$. Additionally, we denote by $T_{\mathcal P}$ the dissemination time of $(1+\rho)$-cobra walk started from $s$.

*(i) Dissemination time is a non-decreasing function of $\rho$. Let $\mathcal P$ and $\mathcal P'$ be a $(1 + \rho)$-cobra walk and a $(1 + \rho')$-cobra walk respectively started from $s$, where $0 \le \rho' < \rho \le 1$. Let $\activeset_t$ be an active set of $\mathcal P$ at time $t$. By lemma:cobra-coupling, there exist $\{\activeset_{t}'\}_{t \ge \starttime}$ such that $\activeset_{t}' \subseteq \activeset_{t}$ for every $t \ge \starttime$ and $\{\activeset_{t}'\}_{t \ge \starttime}$ follows $\mathcal P'$ in law. Note that the expected dissemination time can be expressed in the following way

\begin{align*}
\E[T_{\mathcal P'}] &= \E\left[ \min\left\{t' \ge \starttime\colon \bigcup_{t \in [\starttime, t']} \activeset_{t}' = V \right\}\right].
\intertext{Since $\activeset_{t}' \subseteq \activeset_t$ for every $t$, $\bigcup_{t \in [\starttime, t']} \activeset_{t}' = V$ also implies $\bigcup_{t \in [\starttime, t']} \activeset_{t} = V$. Hence, }
\E[T_{\mathcal P'}] &\ge \E\left[ \min\left\{t' \ge \starttime\colon \bigcup_{t \in [\starttime, t']} \activeset_{t} = V \right\}\right]\\
&= \E[T_{\mathcal P}].
\end{align*}

Since the above holds true for every $\rho' < \rho$, this concludes the proof of this part.

*(ii) Upper bound. The work of [12] only considers cases of $\rho \in \Omega_n(1)$. We now show how the analysis in [12] can be expended to other regimes of $\rho$. Their proof is based on analyzing a BIPS proces, which is dual to cobra walk. Let $A_t$ be an active set of $(1+\rho)$-BIPS process at time $t$, as defined in [12]. Then, Corollary 1 of [12] states that for any $A \subseteq V$, we have

\begin{equation}
\label{eq:bips-growth}
\E\left[|A_{t+1}| \mid A_t = A\right] \ge \left(1 + \rho(1 - \lambda^2)\left(1 - \frac{|A|}{n}\right)\right).
\end{equation}

Note that since $\lambda < 1$, we have $\rho(1-\lambda^2) > 0$. Let $\lambda' < 1$ be such that $1 - (\lambda')^2 = \rho(1 - \lambda^2)$. Then, the above can be rewritten as

\[
\E\left[|A_{t+1}| \mid A_t = A\right] \ge \left(1 + (1 - (\lambda')^2)\left(1 - \frac{|A|}{n}\right)\right),
\]

which is an analog of Lemma 1 [12] with $\lambda$ replaced by $\lambda'$. The rest of the analysis of [12] holds true with $\lambda$ replaced by $\lambda'$. Note that

\[
\lambda' = \sqrt{1 - \rho(1-\lambda^2)} \le \frac{1 + 1 - \rho(1-\lambda^2)}{2} = 1 - \frac{\rho(1 - \lambda^2)}{2}.
\]

Then, since $\rho \in \omega_n\left(\sqrt{\frac{\log(n)}{n}}\right)$ and $\lambda \in 1 - \Omega_n(1)$ (as the underlying graph $G$ is near-Ramanujan), we have

\[
1 - \lambda' \ge  \frac{\rho(1 - \lambda^2)}{2}\in \omega_n\left(\sqrt{\frac{\log(n)}{n}}\right).
\]

Then, Theorem 1 [12] applied for $\lambda'$ yields that the dissemination time $T_{\mathcal P}$ of $(1 + \rho)$-cobra walk is upper bounded in expectation and with high probability by

\[
O_n\left(\frac{\log(n)}{(1 - \lambda')^3}\right) \subseteq O_n\left(\frac{\log(n)}{\rho^3(1 - \lambda^2)^3}\right) \subseteq O_n\left(\frac{\log(n)}{\rho^3}\right),
\]

which concludes the proof of the upper bound.

*(iii) Lower bound.
Denote $N_t = |\activeset_t|$ to be the number of active nodes of a $(1+\rho)$-cobra walk in round $t\ge \starttime$. Accordingly, $N_{\starttime} = 1$. Also, define $B_t$ to be the number of active nodes that branch in round $t$. Note that $N_{t+1} \le (N_t - B_t) + 2B_t$, since every node in round $t$ that did not branch corresponds to at most one active node at time $t$, and every node that branched corresponds to at most two. Hence, for every $t\ge\starttime$

\[
N_{t + 1} \le N_t + B_t,
\]

which implies

\begin{equation}
\label{eq:nt-plus-1-ub-conditional}
\E[N_{t+1}\mid N_t] \le N_t + \E[B_t \mid N_t].
\end{equation}

Note that, by definition of a cobra walk, every node in round $t$ branches with probability $\rho$. Then, we have $B_t \mid N_t \sim \Bin{N_t}{\rho}$. Then, from eq:nt-plus-1-ub-conditional, we have

\[
\E[N_{t+1}\mid N_t] \le N_t + N_t\rho = (1 + \rho)N_t.
\]

Hence, for every $t \ge \starttime$, we have

\[
\E[N_{t+1}] \le (1 + \rho)\E[N_t],
\]

which, since $N_t = 1$ and using a simple inductive argument, implies that for every $t \ge \starttime$ we have

\begin{equation}
\label{eq:nt-expected}
\E[N_t] \le (1+\rho)^{t-1}.
\end{equation}

Now, we define $\tau$ as the first round such that $N_{\tau} \ge n^{1/4}$. Also, we set $\tilde{t} = \left\lfloor \log_{1 + \rho}\left(\frac{n^{1/4}}{2}\right) \right\rfloor + 1$. Then, by definition of $\tau$, we have

\begin{align}
\Pr[\tau \le \tilde{t}]
&\leq \Pr[N_{\tilde{t}} \ge n^{1/4}].\notag
\intertext{By Markov inequality, we get}
\Pr[\tau \le \tilde{t}]  &\le \frac{\E[N_{\tilde{t}}]}{n^{1/4}}.\notag
\intertext{By \equationref{eq:nt-expected}, we have}
\Pr[\tau \le \tilde{t}]  &\le \frac{(1+\rho)^{\tilde{t}-1}}{n^{1/4}}.\notag
\intertext{Recall that $\tilde{t} - 1 = \left\lfloor \log_{1 + \rho}\left(\frac{n^{1/4}}{2}\right) \right\rfloor\le \log_{1 + \rho}\left(\frac{n^{1/4}}{2}\right)$, hence}
\Pr[\tau \le \tilde{t}] &\le \frac{1}{2}. \label{eq:tau-ub}
\end{align}

Note that while the size of the active set $\activeset_t$ does not exceed $n^{1/4}$, cobra walk needs at least $n/n^{1/4} = n^{3/4}$ rounds to disseminate information to all nodes. Thus, the dissemination time of the cobra walk can be bounded from below by $\min\{n^{3/4}, \tau \}$. Then,

\begin{align}
\E\left[T_{\mathcal P}\right]
&\ge \E[\min\{n^{3/4}, \tau\}]. \notag
\intertext{Note that by \equationref{eq:tau-ub}, we have $\tau \ge \tilde{t}$ with probability $\ge 1/2$, hence,}
\E\left[T_{\mathcal P}\right]
&\ge \min\left\{n^{3/4}, \frac{1}{2}\tilde{t}\right\}. \label{eq:expected-tp-lb}
\end{align}

Finally, note that

\begin{align*}
\tilde{t} &= \left\lfloor \log_{1 + \rho}\left(\frac{n^{1/4}}{2}\right) \right\rfloor \\
&\in \Omega_n\left(\log_{1 + \rho}(n)\right).
\intertext{Using $\log_{1 + \rho}(n) = \frac{\log(n)}{\log(1 + \rho)} \ge \frac{\log(n)}{\rho}$, we get}
\tilde{t} &\in \Omega_n\left(\frac{\log(n)}{\rho}\right).
\end{align*}

Combined with eq:expected-tp-lb, this implies

\begin{align*}
\E\left[T_{\mathcal P}\right] &\in \Omega_n\left( \min\left\{n^{3/4}, \frac{\log(n)}{\rho}\right\}\right).
\intertext{Since $\rho \in \omega_n\left(\sqrt{\frac{\log(n)}{n}}\right)$, we have $\frac{\log(n)}{\rho} \in o_n\left(n^{1/2}\right) \subseteq  o_n\left(n^{3/4}\right)$, hence}
\E\left[T_{\mathcal P}\right] &\in \Omega_n\left( \frac{\log(n)}{\rho}\right),
\end{align*}

which concludes the proof of the lower bound.

§.§ Trade-off for Dandelion

§.§.§ Proof of the tightness of corollary:privacy-nr

To show that corollary:privacy-nr is also tight for Dandelion, we prove the following.
Let $\mathcal P$ be a $\rho$-Dandelion with $\rho \in [0,1)$ and let $\mathcal G$ be a family of $d$-regular near-Ramanujan graphs with $n$ nodes, $f$ of which are curious, and $d \in n^{\Omega_n(1)}$. Suppose $f/n\in1 - \Omega_n(1)$ and $\mathcal P$ satisfies $\varepsilon$-DP against either an average-case or a worst-case adversary on $G \in \mathcal G$. Then
\[\varepsilon \in \ln{(\rho (n-f) + f)}+\Omega_n(1).\]

The proof is similar to the proof of thm:cobra-privacy-lower. Note that the statement of thm:dandelion-privacy-lower with $\rho = 0$ follows from thm:universal-impossibility. Without loss of generality, we assume $\rho \in (0,1)$ in the remaining. Let $\anonphase_t$ be the value of $\anonphase$ at round $t$.

Consider an execution of a $\rho$-Dandelion where $\rho \in (0,1]$ on an undirected connected graph $G = (V,E)$. Let $F\subseteq V$ be a subset of curious nodes of size $f$. For $v,u \in\honest$, define the passage probability $\passagedandelion{v}{u}$ from $v$ to $u$ as the probability of a protocol started from $v$ to reach node $u$ while not interacting with any curious nodes, and while still in the anonymity phase. More formally,

\[
\passagedandelion{v}{u} = \Pr\left[\exists t \ge \starttime: \activeset_t = \{u\} \land \anonphase_t = 1 \land (\activeset_i \cap F = \emptyset, \forall i \le t) \mid \activeset_{\starttime} = \{v\}\right].
\]

Let $\mathcal P$ be a $\rho$-Dandelion where $\rho \in (0,1)$, and consider an undirected connected graph $G = (V,E)$ of size $n$. Let $F\subseteq V$ be a set of curious nodes of size $1\le f < n-2$. Then, for any $v \in N(F)$ and $u \in \honest$ we have

\[
\divinfty{\seqadv{v}}{\seqadv{u}} \ge \ln\left(\passagedandelion{u}{v}^{-1}\right).
\]

Since $v \in N(F)$, there exists a $w \in F$, such that $v$ and $w$ are neighbors. Recall that, for Dandelion, $S_\textsc{adv} = \{\left(\fadv(\commset_t), \anonphase_t\right)\}_{t \ge \tadv}$. Define $\sigma_v$ to be the set of adversarial observations which begin with $\fadv\left(\commset_{\tadv}\right) = \{(v \to w)\}$ and $\anonphase_{\tadv} = 1$ (i.e., the protocol is still in the anonymity phase).

Let us define $\Pi_{u \Rightarrow v}$ as

\[
\Pi_{u \Rightarrow v} = \left\{\exists t \ge \starttime: \activeset_t = \{u\} \land \anonphase_t = 1 \land (\activeset_i \cap F = \emptyset, \forall i \le t) \mid \activeset_{\starttime} = \{v\}\right\}
\]

By def:explosive-passage, we have

\begin{equation}
\label{eq:passage-uv}
\passagedandelion{u}{v} = \Pr[\Pi_{u \Rightarrow v}].
\end{equation}

Now, consider the probability of $\seqadv{v} \in \sigma_v$. By law of total probability, we have

\[
\Pr[\seqadv{u} \in \sigma_v] = \Pr[\seqadv{u} \in \sigma_v \mid \Pi_{u \Rightarrow v}] \Pr[\Pi_{u \Rightarrow v}] + \Pr[\seqadv{u} \in \sigma_v \mid \neg \Pi_{u \Rightarrow v}] \Pr[\neg \Pi_{u \Rightarrow v}].
\]

Note that it is impossible for curious nodes to observe communication $(v\to w)$ in the anonymity phase if node $v$ was never active during the anonymity phase. Then $\Pr[\seqadv{u} \in \sigma_v \mid \neg \Pi_{u \Rightarrow v}] = 0$. Also, note that $\seqadv{v}$ and $\seqadv{u} \mid \Pi_{u \Rightarrow v}$ are equal in law, since an execution conditioned on $\Pi_{u \Rightarrow v}$ passes through an active set $\{v\}$ in the anonymity phase which is equivalent to executing the protocol with $v$ as the source node. Hence, the above becomes

\[
\Pr[\seqadv{u} \in \sigma_v] = \Pr[\seqadv{u} \in \sigma_v \mid \Pi_{u \Rightarrow v}] \Pr[\Pi_{u \Rightarrow v}] =\Pr[\seqadv{v} \in \sigma_v] \Pr[\Pi_{u \Rightarrow v}].
\]

From eq:passage-uv, we get

\[
\Pr[\seqadv{u} \in \sigma_v] = \Pr[\seqadv{v} \in \sigma_v] \passagedandelion{u}{v}.
\]

It remains to notice that $\Pr[\seqadv{v} \in \sigma_v] \not = 0$, since there is a positive probability of node $v$ contacting $w$ in the first round of the protocol while still in the anonymity phase (since $\rho > 0$). Hence,

\[
\divinfty{\seqadv{v}}{\seqadv{u}} \ge \ln\left(\frac{\Pr[\seqadv{v} \in \sigma_v]}{\Pr[\seqadv{u} \in \sigma_v]}\right) = \ln\left(\passagedandelion{u}{v}^{-1}\right),
\]

which concludes the proof.

Now, the proof boils down to upper bounding $\passagedandelion{u}{v}$ appropriately.

Consider an execution of a $\rho$-Dandelion where $\rho \in (0,1)$ on $d$-regular graph $G = (V,E)$ of size $n$. Let $F\subseteq V$ be the set of curious nodes of size $f \ge 1$. Let $\vec \eigen_1 \in \mathbb R^{n-f}$ be a vector as in lemma:Q-delocalization. Then, for every $v \in \honest$, there exists $u_\star \in \honest$ such that

\[
\passagedandelion{u_\star}{v} \le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1}\cdot \frac{1}{(f/n + \rho(1 - f/n))(1-\lambda) }.
\]

Let $a_t$ be the active node in round $t$ of the anonymity phase of the execution of the protocol. It follows the distribution of a random walk on $G$. Let $\vec e_i \in \mathbb R^{n-f}$ be an $i^\text{th}$ coordinate unit vector ($i^\text{th}$ coordinate is $1$, and the rest is $0$). Let $\vec Q$ be as in eq:block-form-absorbing-markov.
Then, the probability that $a_t$ reaches $v$ starting from some node $u\in\honest$ in exactly $\tau$ steps without contacting curious nodes is given by
$(\vec Q)^\tau_{uv} = \vec e_u^\top \vec Q^\tau \vec e_v$
by definition of $\vec Q$. Also, the execution must stay in the anonymity phase for $\tau$ steps, which happens with probability $(1 -\rho)^{\tau}$. Then

\begin{equation}
\label{eq:passage-k-u-v-dandelion}
\passagedandelion{u}{v} = \sum_{\tau = 0}^\infty \vec e_u^\top\vec Q^\tau \vec e_v (1 -\rho)^{\tau}.
\end{equation}

By lemma:Q-delocalization, all coordinates of $\vec \eigen_1$ are non-negative. Define the distribution $\Phi$ over the nodes in $\honest$ so that $\Phi(w) = \frac{\eigen_{1w}}{\norm{\vec\eigen_1}_1}$. Consider sampling $u$ according to $\Phi$. Then, by eq:passage-k-u-v-dandelion, we have

\begin{align}
\E_{u\sim \Phi}\left[\passagedandelion{u}{v}\right] &= \E_{u\sim \Phi}\left[\sum_{\tau = 0}^\infty (1-\rho)^{\tau}\vec e_u^\top \vec Q^\tau \vec e_v \right] \notag\\
&= \sum_{\tau = 0}^\infty \sum_{u\in\honest} \Phi(u)  (1-\rho)^{\tau}\vec e_u^\top \vec Q^\tau \vec e_v  \notag\\
&= \sum_{\tau = 0}^\infty \sum_{u\in\honest} \frac{\eigen_{1u}}{\norm{\vec\eigen_1}_1} (1-\rho)^{\tau}\vec e_u^\top \vec Q^\tau \vec e_v  \notag \\
&= \sum_{\tau = 0}^\infty \frac{\vec \eigen_{1}^\top}{\norm{\vec\eigen_1}_1} (1-\rho)^{\tau} \vec Q^\tau \vec e_v. \notag
\intertext{By choice of $\vec \eigen_1$ from \lemmaref{lemma:Q-delocalization}, it is a first eigenvector of a symmetric matrix $\vec Q$, hence}
\E_{u\sim \Phi}\left[\passagedandelion{u}{v}\right]&=\sum_{\tau = 0}^\infty  \lambda_1(\vec Q)^{\tau} (1-\rho)^{\tau}\frac{\vec \eigen_{1}^\top}{\norm{\vec\eigen_1}_1} \vec e_v \notag\\
&= \sum_{\tau = 0}^\infty \lambda_1(\vec Q)^{\tau} \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} (1-\rho)^{\tau} \notag \\
&= \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{1}{1 - \lambda_1(\vec Q) (1-\rho)}. \notag\\
\intertext{From \lemmaref{lemma:spectral-Q}(a), we have $\lambda_1(\vec Q) \le 1 - (1 - \lambda)\frac{f}{n}$, which gives}
\E_{u\sim \Phi}\left[\passagedandelion{u}{v}\right] &\le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{1}{1 - (1 - (1 - \lambda)\frac{f}{n}) (1-\rho)} \notag\\
&\le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{1}{(1 - \lambda)\frac{f}{n} + \rho(1 - (1-\lambda)\frac{f}{n})} \notag\\
&\le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{1}{(1 - \lambda)\left(\frac{f}{n} + \rho(1 - \frac{f}{n})\right)}
\label{eq:expect-passage-explosive}
\end{align}

The upper bounds above hold in expectation as $u \sim \Phi$, hence there exists $u_\star \in \honest$ such that

\[
\passagedandelion{u_\star}{v} \le \frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} \cdot \frac{1}{(1 - \lambda)\left(\frac{f}{n} + \rho(1 - \frac{f}{n})\right)},
\]

which concludes the proof.

For $G \in \mathcal G$, we show a lower bound on max divergence for two carefully chosen source nodes. Let $G = (V,E)$ be an arbitrary element of $\mathcal G$. Let $F \sim\uniformsubset{f}{V}$ be a set of $f$ curious nodes sampled at random. Let $\alpha$ be as in lemma:adversarial-density. Since $\mathcal G$ is a near-Ramanujan family, by lemma:alpha-nr we have $\alpha \in 1 - \Omega_n(1)$. Also, by lemma:adversarial-density, we have $\alpha_F \le \alpha$ with high probability. Let $F_\star \subset V$ be an arbitrary set of size $f$ for which $\alpha_{F_\star} \le \alpha$ holds true. Since $\mathcal G$ is near-Ramanujan with $d \in n^{\Omega_n(1)}$, we have

\begin{equation}
\label{eq:lambda-nr-explosive}
\lambda \in O_n(d^{-1/2}) \subseteq n^{-\Omega_n(1)}.
\end{equation}

Let $T = \left\lceil\log_{\frac{\lambda}{1 - \alpha_{F_\star}}}\left(\frac{1 - \alpha_{F_\star}}{4(n-f)}\right)\right\rceil$ be as in lemma:Q-delocalization for set $F_\star$. Recall that $\alpha_{F_\star} \le \alpha \in 1 - \Omega_n(1)$. Combining this with eq:lambda-nr-explosive, we have $\frac{\lambda}{1 - \alpha_F} \in n^{-\Omega_n(1)}$. Since also $\frac{1 - \alpha_F}{4(n-f)} \in n^{-O_n(1)}$, we have

\begin{equation}
\label{eq:t-is-o1-explosive}
T \in O_n(1).
\end{equation}

By lemma:Q-delocalization, we have for every $v \in V\setminus F_\star$,

\[
\frac{(1-\alpha_{F_\star})^{(T+1)/2}}{\sqrt{2(n-f)}}\le \eigen_{1v} \le \frac{\sqrt{2}(1-\alpha_{F_\star})^{-(T+1)/2}}{\sqrt{(n-f)}}.
\]

Then, for every $v \in V\setminus F_\star$, we have

\[
\norm{\vec\eigen_1}_1 = \sum_{v \in V\setminus F_\star} \left|\eigen_{1v}\right| \ge (n-f) \frac{(1-\alpha_{F_\star})^{(T+1)/2}}{\sqrt{2(n-f)}} = \frac{(1-\alpha_{F_\star})^{(T+1)/2}\sqrt{n-f}}{\sqrt{2}}.
\]

This implies that for every $v \in V\setminus F_\star$

\begin{align}
\frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} &\le \frac{\frac{\sqrt{2}(1-\alpha_{F_\star})^{-(T+1)/2}}{\sqrt{(n-f)}}}{\frac{(1-\alpha_{F_\star})^{(T+1)/2}\sqrt{n-f}}{\sqrt{2}}} = \frac{2(1-\alpha_{F_\star})^{-(T+1)}}{n-f}.\notag
\intertext{By \equationref{eq:t-is-o1-explosive}, we have $T \in O_n(1)$, and also $\alpha_{F_\star} \le \alpha \in 1 - \Omega_n(1)$, therefore, }
\frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} &\in O_n\left(\frac{1}{n-f}\right).\notag
\intertext{Since $f/n\in 1-\Omega_n(1)$, we have $n-f \in \Theta_n(n)$, hence}
\frac{\eigen_{1v}}{\norm{\vec\eigen_1}_1} &\in O_n\left(\frac{1}{n}\right).
\label{eq:eigen-over-1-norm-explosive}
\end{align}

Since $G$ is connected and $F_\star \not = V$, $N(F_\star)\setminus F_\star$ has at least one node. Let $v_\star \in N(F_\star)\setminus F_\star$ be an arbitrary non-curious node in a neighborhood of $F$. Then, by lemma:passage-explosive-ub, there exists $u_\star \in V\setminus F_\star$ such that

\begin{align*}
\passagedandelion{u_\star}{v_\star} &\le \frac{\eigen_{1v_\star}}{\norm{\vec\eigen_1}_1}\cdot \frac{1}{(f/n + \rho(1 - f/n))(1-\lambda)}.
\intertext{By \equationref{eq:eigen-over-1-norm-explosive}, we get}
\passagedandelion{u_\star}{v_\star}&\in O_n\left(\frac{1}{n}\cdot \frac{1}{(f/n + \rho(1 - f/n))(1-\lambda) } \right).
\intertext{Hence,}
\passagedandelion{u_\star}{v_\star} &\in O_n\left(\frac{1}{(f + \rho(n - f))(1-\lambda) } \right).
\intertext{Recall that $\mathcal G$ is near-Ramanujan. Hence,}
\passagedandelion{u_\star}{v_\star} &\in O_n\left(\frac{1}{f + \rho(n - f)} \right).
\end{align*}

Then, by lemma:necessary-explosive-passage, we have

\begin{align*}
\divinfty{\seqadv{v_\star}}{\seqadv{u_\star}} \ge \ln\left(\passage{u_\star}{v_\star}^{-1}\right) \in \ln\left(f + \rho(n - f)\right) + \Omega_n(1),
\end{align*}

which yields

\begin{align}
\label{eq:divinfty-lower-dandelion}
\max_{v,u\in V\setminus F_\star}\divinfty{\seqadv{v}}{\seqadv{u}} \in \ln\left(f + \rho(n - f)\right) + \Omega_n(1).
\end{align}

Note that the above holds for arbitrary set of curious nodes $F_\star$ for which $\alpha_{F_\star} \le \alpha$ holds. By lemma:adversarial-density, $\alpha_{F_\star} \le \alpha$ holds true with high probability as $F_\star$ is selected uniformly at random. Hence, (<ref>) implies that for both worst-case and average-case adversaries we have

\[
\varepsilon \in \ln\left(f + \rho(n - f)\right) + \Omega_n(1).
\]

§.§.§ Dissemination time of Dandelion (proof of thm:dandelion-speed)

Consider an undirected connected graph $G$ of size $n$ and diameter $D$. Let $\mathcal P$ be a $\rho$-Dandelion protocol with $\rho \le 1$ and $\rho \in \Omega_n(1/n)$. Then, regardless of the source node, the dissemination time of $\mathcal P$ is in order of $\Theta_n\left(1/\rho + D\right)$ rounds in expectation.

Let $\tau$ be the number of rounds it takes for the protocol to transition into a spreading phase. Then $\tau \sim \Geom(\rho)$, and hence $\E[\tau] = 1/\rho$.

*(i) Upper bound. Note that broadcast spreads the gossip to all nodes in at most $D$ rounds. Since the protocol spends $1/\rho$ rounds in expectation in the anonymity phase, the upper bound of $1/\rho + D$ follows.

*(ii) Lower bound. First, note that for any $v \in V$ there exists $u \in V$ at distance at least $D/2$ away from $v$. Indeed, if every vertex is at distance $< D/2$ away from $v$, then for any two $w_1$, $w_2$ we have $d(w_1, w_2) \le d(w_1, v) + d(v, w_2) < D$ by triangle inequality, i.e., the diameter of the graph is $<D$, which is a contradiction. With this in mind, consider the two following cases.

*(ii.1) Case $1/\rho < D/4$. Let $s$ be the source, and let $u$ be the node at distance at least $D/2$ away from $s$. Note that, regardless of the phase of the execution, the protocol requires at least $D/2$ rounds to propagate the gossip from $s$ to $u$.
Then, the expected dissemination time can be lower bounded by

\[
D/2 \in \Omega_n(D) \subseteq \Omega_n(D + 1/\rho),
\]

where the last transition follows from the fact that $1/\rho < D/4$.

*(ii.2) Case $1/\rho \ge D/4$. Note that, if have $\rho > 1/2$, the lower bound is trivial, since it amounts to asserting that dissemination time is in $\Omega_n(1)$. In the remaining, assume $\rho \le 1/2$. Recall that also $\rho \in \Omega_n(1/n)$. Define $t = \min\{1/\rho, n/2\}$. Since $\rho \in \Omega_n(1/n)$, we have $t = \Theta_n(1/\rho)$. Since also $\rho \le 1/2$, we have $\Pr[\tau \ge t] = (1-\rho)^{t} \in (1-\rho)^{\Theta_n(1/\rho)} \subseteq \Omega_n(1)$. Finally, note that if $\tau \le t \le n/2$, then after $t$ round of the protocol, there are nodes which have not received the gossip yet. Hence, the expected dissemination time is lower bounded by

\[
\Pr[\tau \ge t] t \in \Omega_n(t) \subseteq \Omega_n(1/\rho) \subseteq \Omega_n(1/\rho + D),
\]

where the last transition follows from the fact that $1/\rho \ge D/4$. This concludes the proof of the lower bound.

§ EXTENSION TO MUTING PUSH

§.§ Protocol description

Muting push is a protocol introduced in [5], which constitutes a parameterized version of standard push protocol [51]. This is a gossip protocol where at every round $t \geq \starttime$, each node active node $u \in \activeset_t$ pushes the gossip $g$ to a neighbour $v \in N(u)$ chosen uniformly at random (i.e., $(u \to v)$ is added to $\commset_t$). Additionally, $u$ samples a token from a Bernoulli distribution with parameter $\rho$. If the token equals one, $u$ stays active for the next round (i.e., $(u \to u)$ is added to $\commset_t$). If the token equals zero, $u$ deactivates (“mutes”). Note that, in our setting, $\rho$ corresponds to the probability of a node not muting and staying active for a subsequent round.
Note that, when $\rho = 0$, this protocol degenerates into a classic random walk on the graph. On the other hand, $\rho = 1$ matches the standard push gossip [51].

§.§ Privacy guarantees

Now, we extend our positive results in thm:main and corollary:privacy-nr to muting push [5]. We will prove the following results.

Consider an undirected connected $(d,\lambda)$-expander graph $G=(V,E)$ of size $n$, let $f$ be the number of curious nodes, and let $\mathcal P$ be a $\rho$-muting push with $\rho < 1$. Set $\alpha = f/d$ (resp. set $\alpha$ as in lemma:adversarial-density). If $\lambda < 1 - \alpha$, then $\mathcal P$ satisfies $\varepsilon$-DP against a worst-case adversary (resp. an average-case adversary) with

\[
\varepsilon = \ln(\rho(n-f) + f) - 2\Tilde{T}\ln(1 - \alpha) - \Tilde{T}\ln(1 - \rho) - \ln(1-\lambda) + \ln(24),
\]

and $\Tilde{T}  = \left\lceil\log_{\frac{\lambda}{1 - \alpha}}\left(\frac{1 - \alpha}{4(n-f)}\right)\right\rceil \left(\log_{\frac{\lambda}{1 - \alpha}}(1 - \alpha) + 2\right) + 2.$

Let $\mathcal P$ be a $\rho$-muting push and let $\mathcal G$ be a family of $d$-regular near-Ramanujan graphs with $n$ nodes and $d \in n^{\Omega_n(1)}$. Suppose $f/d \in 1 - \Omega_n(1)$ (resp. $f/n \in 1 - \Omega_n(1)$). Then, for any $G \in \mathcal G$ of large enough size $n$ and any $\rho \in 1 - \Omega_n(1)$, $\mathcal P$ satisfies $\varepsilon$-DP against a worst-case adversary (resp. an average-case adversary) for some

\[
\varepsilon \in \ln\left(\rho(n-f) + f\right) + O_n(1).
\]

To establish the results above, it is sufficient to show that a reduction in lemma:sufficient-varepsilon-0 applies to $\rho$-muting push. The rest of the proof of thm:main-muting and cor:muting will be exactly the same as for thm:main and corollary:privacy-nr. Formally, we have the following.
Conside $\rho$-muting push on a $d$-regular graph $G = (V,E)$. Let $F \subset V$ be a set of curious nodes such that the subgraph of $G$ induced by $\honest$ is connected. Let $\vec Q = \Hat{\vec A}[\honest]$ and, for $s \in \honest$, let $W^{(s)}$ be the absorbing state of the Markov chain as in eq:block-form-absorbing-markov. Then, for any  $v, u \in \honest$, the following holds true

\[ \divinfty{\seqadv{v}}{\seqadv{u}} \le \divinfty{W^{(v)}}{W^{(u)}} = \max_{w\in \honest} \ln\frac{(\vec I_{n-f} - (1 - \rho)\vec Q)^{-1}_{vw}}{(\vec I_{n-f} - (1 - \rho)\vec Q)^{-1}_{uw}}.\]

Let $s\in \honest$ be arbitrary. Note that the right-hand side equality follows from the proof of (<ref>). To prove the left-hand side inequality, we will first introduce a notion of “safe” rounds, in a similar way as for the proof of lemma:sufficient-varepsilon-0. We call a round of the execution safe if the set of active nodes then has size $1$, and the only active node contacts a non-curious node during the current round and then deactivates (“mutes”). We also introduce an indicator variable $\nice_t^{(s)}$ corresponding to a round $t$ being safe. Formally,

\begin{equation}
\label{eq:nice-muting}
\nice_t^{(s)} = \ind_{\left\{\exists v,u \in \honest \colon \activeset_t^{(s)} = \{u\}\land \commset_t^{(s)} = \{(u \to v)\}\right\}}.
\end{equation}

Note that since $\commset_t^{(s)}$ does not contain $(u \to u)$ in the event under the indicator in (<ref>), $u$ will deactivate after round $t$ (i.e., $u \not \in \activeset_{t+1}^{(s)}$) according to the formalism we defined in sec:preliminaries.

*(i) Relating safe rounds to an absorbing Markov chain in (<ref>).

If $\activeset_t^{(s)} = \{u\}$ for some $u \in \honest$, then $u$ will deactivate after round $t$ probability $1-\rho$. Additionally, since we consider $d$-regular graphs, $u$ will contact a fixed node $v \in N(u)$ with probability $1/d$. Hence, for any $u, v \in \honest$ such that $v \in N(u)$ we have

\begin{align*}
\Pr\left[\activeset_{t+1}^{(s)} = \{v\} \land \nice_t^{(s)} = 1 \mid \activeset_t^{(s)} = \{u\} \right] &= \frac{1 - \rho}{d} = (1-\rho) \vec Q_{vu}
\end{align*}

Note that for any $t$ and any $u, v \in \honest$ such that $v \notin N(u)$, we have

\begin{align*}
\Pr[\activeset_{t+1}^{(s)} = \{v\} \land \nice_t^{(s)} = 1 \mid \activeset_t^{(s)} = \{u\}]= 0 = (1 - \rho)\vec Q_{vu}.
\end{align*}

Then, for any $v,u \in \honest$, we get

\begin{align}
\label{eq:transient-flag-up-muting}
\Pr[\activeset_{t+1}^{(s)} = \{v\} \land \nice_t^{(s)} = 1 \mid \activeset_t^{(s)} = \{u\}] = (1 - \rho)\vec Q_{vu},
\end{align}

which is equal to the transition probability between two transient states $v$ and $u$ of (<ref>). Also, for any $u$, we have

\begin{align}
\Pr[\nice_t^{(s)} = 0 \mid \activeset_t^{(s)} = \{u\}] &= 1 - (1-\rho)\frac{\deg_{\honest}(u)}{d} \notag\\
&= \rho + \frac{\deg_F(u)}{d} (1-\rho) \notag\\
&= \rho(\vec I_{n-f})_{uu} + (1 - \rho)\vec R_{uu} \label{eq:absorbing-flag-down-muting},
\end{align}

which is equal to the probability of being absorbed at $\sink(u)$ from state $u$ in (<ref>). Let $\tau^{(s)}$ be the first unsafe round, i.e.,

\begin{equation}
\label{eq:tau-s-muting}
\tau^{(s)} = \min\{t \colon \nice_t^{(s)} = 0\}.
\end{equation}

Then, $\tau^{(s)}$ is the first round in which the active node either does not mute (i.e., $(u\to u)\in \commset_t$ for $u \in \activeset_t^{(s)}$) or contacts a curious node. Then, from (<ref>) and (<ref>), at time $\tau^{(s)}$, we have $\activeset_{\tau^{(s)}}^{(s)} = \{W^{(s)}\}$, where $W^{(s)}$ is an absorbing state of chain defined in (<ref>).

*(ii) Applying the Data Processing inequality.
Let $\round_t^{(s)} = (\activeset_t^{(s)}, \commset_t^{(s)})$ for every $t$, i.e., $\round_t^{(s)}$ describes a round $t$ of the execution. Consider a sequence $\{\round_t^{(s)}\}_{t \ge \starttime}$. Note that $\{\round_t^{(s)}\}_{t \ge \starttime}$ is Markovian by definition of muting push in appendix:muting-def.

Then $\tau^{(s)}$ is a stopping time for a Markov chain $\{\round_t^{(s)}\}_{t\ge \starttime}$ by definition of $\tau^{(s)}$ in (<ref>) (for definition of a stopping time, see Section 6.2 of [41]).

Then, by Strong Markov Property (Proposition A.19 of [41]), the law of $\{\round_t^{(s)}\}_{t \ge \tau^{(s)}}$ only depends on $\round_{\tau^{(s)}}^{(s)}$. Hence, by the Data Processing Inequality (Theorem 14 of [42]), we have

\begin{align}
\label{eq:data-processing-one-muting}
\divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}} \le \divinfty{\round_{\tau^{(v)}}^{(v)}}{\round_{\tau^{(u)}}^{(u)}}.
\end{align}

By definition of $\tau^{(s)}$ in (<ref>), for all $t \le \tau^{(s)}$, we have $|\activeset_t^{(s)}| = 1$. Also, note that the random variable $\commset_{\tau^{(s)}}^{(s)}$ characterizes a round of muting push in which it has active set $\activeset_{\tau^{(s)}}^{(s)}$ and is conditioned on the only active node either not muting for next round (i.e., $(u\to u)\in \commset_t$ for $u \in \activeset_t^{(s)}$) or contacting a curious node. Then, since muting push is Markovian, communications $\commset_{\tau^{(s)}}^{(s)}$ that happen in round $\tau^{(s)}$ only depend on $\activeset_{\tau^{(s)}}^{(s)}$. Hence, by the Data Processing Inequality (Theorem 14 of [42]), we have $\divinfty{\round_{\tau^{(v)}}^{(v)}}{\round_{\tau^{(u)}}^{(u)}} \le \divinfty{\activeset_{\tau^{(v)}}^{(v)}}{\activeset_{\tau^{(u)}}^{(u)}}$. Then

\begin{align}
\label{eq:data-processing-two-muting}
\divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}} \le \divinfty{\activeset_{\tau^{(v)}}^{(v)}}{\activeset_{\tau^{(u)}}^{(u)}}.
\end{align}

Finally, recall that we showed in (i) that $\activeset_{\tau^{(s)}}^{(s)} = \{W^{(s)}\}$, where $W^{(s)}$ is an absorbing state of the Markov chain (<ref>). Hence,

\begin{align}
\label{eq:data-processing-three-muting}
\divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}} \le \divinfty{W^{(v)}}{W^{(u)}}.
\end{align}

Note also that since no curious node is contacted before time $\tau^{(s)}$, $\seqadv{s}$ can be obtained from $\{\round_t^{(s)}\}_{t \ge \tau^{(s)}} = \{(\commset_{t}^{(s)}, \activeset_{t}^{(s)})\}_{t \ge \tau^{(s)}}$ via a deterministic mapping from definition of $\seqadv{s}$ in sec:source-anonymity-with-DP. Then, applying the  Data Processing Inequality (Theorem 14 of [42]) again, for any $v,u \in \honest$ we have

\begin{equation}
\label{eq:data-process-seqadv-xt-muting}
\divinfty{\seqadv{v}}{\seqadv{u}} \le \divinfty{\{\round_t^{(v)}\}_{t \ge \tau^{(v)}}}{\{\round_t^{(u)}\}_{t \ge \tau^{(u)}}}.
\end{equation}

By combining the above with (<ref>), we get

\begin{equation}
\label{eq:data-process-seqadv-w-muting}
\divinfty{\seqadv{v}}{\seqadv{u}} \leq \divinfty{W^{(v)}}{W^{(u)}},
\end{equation}

which concludes the proof.

§ SEMANTIC FOR SOURCE ANONYMITY: PROOFS OF SUBSECTION:DPSEMANTICS

§.§ Proof of (<ref>)

First, note that by definition of $\varepsilon$-DP, we have for any $v \in \honest$.

\begin{equation*}
\frac{\Pr\left[\seqadv{\smap} \in \sigmaevent\right]}{\Pr\left[\seqadv{v} \in \sigmaevent\right]} \le \exp\left(\divinfty{\seqadv{\smap}}{\seqadv{v}}\right) \le \exp(\varepsilon).
\end{equation*}

Then, we have

\begin{equation}
\label{eq:smap-ratio-bound}
\frac{\Pr\left[\seqadv{\smap} \in \sigmaevent\right]}{\max_{v\in\honest}\Pr\left[\seqadv{v} \in \sigmaevent\right]} \le \exp(\varepsilon).
\end{equation}

By Bayes law, we get

\begin{align*}
\Pr_{s \sim \prior}\left[\smap = s \mid \seqadv{s} \in \sigmaevent \right] &= \frac{\Pr\left[\seqadv{\smap} \in \sigmaevent\right] p(\smap)}{\sum_{v \in \honest} \Pr\left[\seqadv{v} \in \sigmaevent\right] p(v)}. \\
&\le \frac{\Pr\left[\seqadv{\smap} \in \sigmaevent\right] p(\smap)}{\max_{v\in \honest} \Pr\left[\seqadv{v} \in \sigmaevent\right] \sum_{v \in \honest} p(v)}. \\
\intertext{Using (\ref{eq:smap-ratio-bound}), we get}
\Pr_{s \sim \prior}\left[\smap = s \mid \seqadv{s} \in \sigmaevent \right] &\le \frac{\exp(\varepsilon) p(\smap)}{\sum_{v \in \honest} p(v)} \\
&\le \exp(\varepsilon) p(\smap),
\end{align*}

which concludes the proof.

§.§ Proof of (<ref>)

Plugging $p = \uniform{\honest}$ into (<ref>), we have

\[
\Pr_{s \sim \uniform{\honest}} \left[\smle = s \mid \seqadv{s} \in \sigmaevent \right] \le \exp(\varepsilon) p(\smle) = \frac{\exp(\varepsilon)}{n - f},
\]

as desired.