Author: Lucas Luhur Last updated: 2026-07-18
Open questions:
Two deferred latency-model generalisations:
- heterogeneous link latencies: the homogeneous $d(k+1)$ link term generalised to a per-link sum $\sum_j d_j$
- other $d_i^S$ distributions: the quenched $d_i^S \sim U(\cdot)$ is the “for now” choice, non-uniform families a later one-line swap.
This week built the whole second anonymity axis → message attribution: for a specific observed broadcast, which candidate in the sender set actually sent it? With it completed, the anonymity side of the trilemma is now complete. Together with the single-path mix model, each with its own family of measures.
The trilemma’s primary anonymity property is sender anonymity / unlinkability: can a global passive adversary (GPA), watching every link, name the sender of one specific broadcast? The stake attack cannot answer this — it counts participation over an epoch, it does not attribute a single message. Message attribution is the attack that does, and it is a timing attack: what it can learn is set entirely by how the message’s observed broadcast time compares to the deterministic latency of each candidate sender.
The task: infer which candidate $i \in \mathcal S_t$ is the true sender $\mathcal L$.
Every candidate’s message would have accrued a known deterministic latency $\mu(i, r) = d_i^S + D_M + d_r^R$ (the sender→first-mix link, the shared mix-chain total, the exit→receiver link — all public, the GPA knows the topology and observes $r$) plus an unobserved random delay $Z$ (the mixing + sender holds). So for candidate $i$ the residual
$$ z_i \;=\; y - \mu(i, r) $$
is what the random delay would have had to be if $i$ were the sender. Scoring that residual under the delay density $f_Z$ gives the likelihood; a uniform prior over $\mathcal S_t$ turns it into a posterior:
$$ \Pr(\mathcal L = i \mid y, r, \mathcal S_t) \;=\; \frac{\pi_i\, f_Z(z_i)}{\sum_{j \in \mathcal S_t} \pi_j\, f_Z(z_j)}, \qquad \pi_i = \tfrac{1}{|\mathcal S_t|}\ \text{(cancels)}, $$
and the Maximum A Posteriori (MAP) estimator $\hat{\mathcal L} = \arg\max_i \Pr(\mathcal L = i \mid y, r, S_t)$ is the guess.
# Inputs: observe (S_t, r, y) per broadcast; mu(i, r) is PUBLIC knowledge
obs = observe_broadcasts(trace) # the sender sets S_t, receiver r, broadcast time y
r_row = np.repeat(obs.receiver, counts) # r and y broadcast onto every candidate row of S_t
y_row = np.repeat(obs.y, counts)
n_stages = k + (1 if receiver_delays else 0) # m = k mixer holds (or k+1 if R also delays)
# Step 1 -- residual latencies z_i = y - mu(i, r), mu(i, r) = d_i^S + D_M + d_r^R
mu = latency_profile.mu(obs.candidate, r_row)
z = y_row - mu
# Steps 2 & 3 -- one call: eliminate impossible candidates (z_i < 0) AND score the likelihood
# L_i = f_Z(z_i). random_delay_pdf returns 0 for z < 0, so the non-negativity prune is automatic.
like = random_delay_pdf(z, n_stages, sender_scale, mix_scale)
# Step 4 -- posterior = pi_i L_i / sum_j pi_j L_j, uniform prior pi_i = 1/|S_t| (cancels).
# Vectorised: normalise each broadcast's candidate block by its own segment sum.
seg_sum = np.add.reduceat(like, obs.start[:-1])
posterior = like / np.repeat(seg_sum, counts)
# Step 5 -- MAP L_hat = argmax_i posterior. Deferred to the scorer (deanon_top1), so the attack
# returns the FULL posterior over S_t (one per broadcast), not a point estimate.
return PosteriorGuess(obs.broadcast_row, obs.start, obs.candidate, posterior)
# Step 3's likelihood $f_Z$
def random_delay_pdf(z, n_stages, sender_scale, mix_scale, rate_tol=1e-8):
out = np.zeros_like(z)
pos = z >= 0.0 # Step 2: z < 0 -> f_Z = 0 (impossible)
zz = z[pos]
m, lam_m = int(n_stages), 1.0 / mix_scale
if sender_scale <= 0.0: # sender hold off -> Z ~ Gamma(m, lambda_M)
out[pos] = lam_m**m * zz**(m - 1) * np.exp(-lam_m * zz) / factorial(m - 1)
return out
lam_s = 1.0 / sender_scale
if abs(lam_s - lam_m) <= rate_tol * max(lam_s, lam_m): # equal rates -> Z ~ Gamma(m+1, lambda)
out[pos] = lam_m**(m + 1) * zz**m * np.exp(-lam_m * zz) / factorial(m)
return out
a_s = lam_s * lam_m**m / (lam_m - lam_s)**m # general hypoexponential (lambda_S != lambda_M)
poly = sum(((lam_m - lam_s) * zz)**q / factorial(q) for q in range(m))
out[pos] = np.maximum(a_s * (np.exp(-lam_s * zz) - np.exp(-lam_m * zz) * poly), 0.0)
return out