A Transaction-Level Model for Blockchain Privacy

In three numbers

What the model delivers

The problem

Everyone says "untraceable". Nobody means the same thing.

Bitcoin and Ethereum show every sender, recipient and amount. The protections built on top take very different routes. Coinjoin merges many users' coins into one transaction. Tornado Cash uses zero-knowledge proofs to separate deposits from withdrawals. Monero hides the real input among decoys with ring signatures. Zcash hides it in a shielded pool. Each line of research uses its own model and notation, so they are hard to compare.

The paper asks three questions. How do these mechanisms compare? Which structures in a ledger protect privacy, and which break it? What forms does privacy take in a blockchain? To answer them, it extends the Transaction DAG (TDAG) of Cachin et al. into the PDAG, then defines two notions on that one graph:

Adversary model (§3.1): passive, computationally unbounded, idealised cryptography, and focused on the transaction layer. It only observes and records transactions.

Interactive 1 · Figure 2

Anatomy of a PDAG, and what the adversary sees

A PDAG has states ($\bigcirc$, coins), witnesses ($\Box$, one per transaction) and nullifiers ($\Diamond$). Nullifiers are Monero key images, Zcash nullifiers or Tornado withdrawal commitments; they block double-spends. The paper adds masking edges to the TDAG: a masking edge consumes a state, but to everyone except the author it looks like an observing edge. Switch to the adversary's view and every masking edge disappears into the ambiguous ones.

Graph reproduced from figures/pdag_example.tex (Figure 2). Transaction descriptions follow §2.4.

Interactive 2 · Figure 3 · Definitions 5–7

Untraceability: prune to the core, then count

The adversary keeps only the regular transactions and their inputs, which gives a bipartite graph $G^*$ of states and witnesses (§3.2). Every witness consumes at least one state, so the real spends form a maximum matching. Any edge that belongs to no maximum matching cannot be the real spend. Pruning those edges leaves the Dulmage–Mendelsohn core, the union of all maximum matchings (Def. 5). A transaction is $k$-untraceable when $k\ge2$ of its edges survive in the core. A PDAG is only as untraceable as its weakest transaction (Def. 7).

With the paper's graph, the two maximum matchings are $M_1$ and $M_2$ (§3.2). Neither uses $s_1\to w_3$ or $s_2\to w_3$, so the core drops both, and $w_3$ is left with a single edge: traceable. The graph looks 2- and 3-untraceable, but the PDAG gives no untraceability at all.

Computed live by listing every matching of the 3×3 graph. The paper's case reproduces the core stated in §3.2: $\{s_1w_1, s_2w_2, s_3w_3, s_1w_2, s_2w_1\}$.

Interactive 3 · Definition 10 · Lemmas 2–4, 7

The unlinkability score, and the paper's two readings of it

The adversary puts $n$ states into one class $[s]_{\tilde L}$. In this calculator, $l$ of them form a single group that truly belongs together, and the other $n-l$ are unrelated singletons. Definition 10 describes the score in words as "the ratio of the number of unlinked pairs to all possible pairs". Its formula, however, counts only the pairs inside $[s]_{\tilde L}\setminus[s]_L$. The two agree in some places and not in others. The paper's worked values also split between them, so this calculator shows both: (A) is the formula for a member of the group, and (B) is the wording applied to the whole class.

Interactive 4 · Figure 6 · Lemma 1

Coinjoin: beat the multi-input heuristic

The multi-input heuristic (Eq. 1) assumes every input of a transaction has the same owner. Coinjoin breaks that assumption. In Figure 6, three users merge 7 inputs into one transaction, so the adversary's class is all 7 inputs. Each state's score depends only on how many of the 7 its owner holds. Click an input to change its owner.

The paper's split reproduces its stated scores: $\frac{10}{21}$ for the four inputs of the two 2-address users, and $\frac{6}{21}$ for the three inputs of the 3-address user (§4.1.1). Lemma 1 bounds a Coinjoin with at least two owners between $\binom{|S_I|-|U|}{2}/\binom{|S_I|}{2}$ and $\binom{|S_I|-|u|}{2}/\binom{|S_I|}{2}$, where $U$ is the largest owner class and $u$ the smallest.

Interactive 5 · Figures 8 and 9 · Lemmas 6 and 8

Monero vs Zcash: where the decoys come from

Both chains hide the spent input behind masking edges and stop double-spends with nullifiers. They differ in who ends up in the untraceability set. A Monero ring signature names its decoys explicitly: 16 ring members since v0.18.0.0. A Zcash shielded spend names none, so the set is implicitly every earlier state in the pool. Step through each chain's sample run from the paper.

Graphs reproduced from figures/pdag_monero_h2.tex (Figure 8) and figures/pdag_zcash_all_min.tex (Figure 9). Grey areas are the shielded pool, drawn exactly as in the figure source. The sample runs are toy-sized. The protocol-scale guarantees are the ones in the "At protocol scale" card.

Properties

What each system guarantees, in the paper's terms

"Linkable" means the heuristic was right and the score is $0$. The paper states the Tornado Cash, Monero and Zcash scores under the Def. 10 wording, reading (B) above; see source notes.

Results

Ten numbered linking relations, one notation

This is a formal-model paper, so it has no measurements or benchmarks. Its main result is this catalogue: heuristics from Bitcoin, Tornado Cash, Monero and Zcash research, each rewritten as an inferred linking relation $\tilde L$ on the PDAG, with the score each one leaves.

Address reuse has no equation number, because it uses the address relation $A$ directly rather than a new $\tilde L$. Equation numbers are from main.aux of the ePrint build. Expressions are copied as printed in the paper, including Lemma 5's denominator (see source notes). "Maximal extractable privacy" (§3.3): the largest score a relation $\tilde L$ allows, i.e. what a user can gain by deliberately mixing unlinked states into a transaction that the heuristic misreads.

Provenance

Where the paper disagrees with itself

This page shows these issues as the paper states them instead of silently choosing one version. They appear in the ePrint text that the PDF links to.

1. Two readings of the unlinkability score. The words of Def. 10 ("unlinked pairs to all possible pairs") and its formula $\binom{|[s]_{\tilde L}\setminus[s]_L|}{2}/\binom{|[s]_{\tilde L}|}{2}$ disagree. Because $[s]_L\ni s$, the formula gives $0$ for any state that shares a class of two with one unrelated state, and the text says such a state should score $1$. The Coinjoin example, Lemma 1 and Lemma 9 follow the formula. The motivating example in §3.3 and the proofs of Lemmas 2, 3, 4, 7 and 10 follow the wording. Even the wording is used two ways. Lemma 2 scores the unlinked $s_w$ by the pairs of the whole class, including the $s_d$–$s_f$ pair, which does not involve $s_w$. Lemma 4 instead defines $l$ from $s$ itself, $l=|[s]_L\cap[s]_{\tilde L}|$. Interactive 3 puts both readings next to each other.
2. Lemma 5 divides by $\binom{2l}{l}$, while every other score divides by a count of pairs, $\binom{\cdot}{2}$. It also subtracts a single $\binom{l}{2}$, although its proof describes two disjoint classes of size $l$. The two denominators agree only at $l=2$. The expression is reproduced here as printed.
3. Coinjoin example (§4.1.1). The text lists the adversary's class as $\{s_1,\dots,s_6\}$ and numbers scores $u_1\dots u_6$. Figure 6 and the denominator $21=\binom{7}{2}$ both use 7 inputs, $s_0\dots s_6$. Interactive 4 uses the 7 inputs of Figure 6.
4. Tornado Cash (§4.1.2). The text calls the deposit "$T_{w_1}$". Figure 7a and the rest of the paragraph call it $T_{w_0}$.
5. Zcash (§4.3). The text sends $T_{w_4}$ to "shielded $s_{10}$ and transparent $s_8$, $s_{10}$". In Figure 9, $s_{10}$ sits inside the shielded area and $s_8$, $s_9$ sit outside. Interactive 5 follows the figure.
6. Figure 3 text says "$1\le i\le 2$" for three transactions $T^*_{w_1},T^*_{w_2},T^*_{w_3}$.

The FC 2024 camera-ready (lncs/ in the source repo) is a shorter version with different numbering. It keeps the same Def. 10 formula.

Reference

Cite this work

@inproceedings{wicht2024transaction,
  title     = {A Transaction-Level Model for Blockchain Privacy},
  author    = {Wicht, Fran{\c{c}}ois-Xavier and Wang, Zhipeng and
               Le, Duc V. and Cachin, Christian},
  booktitle = {Financial Cryptography and Data Security (FC)},
  year      = {2024},
  note      = {Full version: Cryptology ePrint Archive, Paper 2023/1902}
}

Code and data. This is a formal-model paper. It has no data availability statement and no accompanying implementation or dataset, so none is linked here. Every number on this page comes from the paper's text, figures and lemmas, or is computed live from its definitions.