Path Diversity: Why Trust Topology Beats Trust Density

An interactive exploration of Menger's theorem as a Sybil defense

Here is a question that matters for decentralized reputation: if an attacker creates five fake identities that all vouch for each other, how do you tell them apart from a genuine cluster of collaborators? Density metrics — degree centrality, clustering coefficient, weighted trust score — cannot. The attacker controls the internal wiring and can make it look arbitrarily healthy.

But there is a structural asymmetry the attacker cannot fake: the diversity of paths through the surrounding graph. Honest nodes accumulate trust relationships organically, through independent interactions with different parts of the network. Their paths to any verifier pass through many different intermediaries. An attacker's paths all funnel through the same few bridge nodes — the ones they actually compromised or befriended.

This is Menger's theorem applied to trust: the maximum number of vertex-disjoint paths between two nodes equals the minimum vertex cut. A node embedded in dense organic topology has a high vertex connectivity. A Sybil cluster, no matter how internally dense, has connectivity bounded by its bridge count.

Menger's Theorem: For non-adjacent vertices u, v in graph G:
max { |P| : P is a set of vertex-disjoint u-v paths } = min { |S| : S is a u-v vertex cut }

Path Diversity Score: PD(u, v) = |{ independent u-v paths }| / max_possible
Density Score: DS(u) = deg(u) / (|V| - 1)
Clustering Coeff: CC(u) = 2 * |edges among neighbors| / (deg(u) * (deg(u) - 1))

I. The Density Shield Attack

Below is a trust network. The blue nodes are honest participants with organic, sparse connections. Hidden among them is an attacker cluster — densely interconnected fake identities that connect to a few real nodes. Watch how density metrics are fooled.

Honest avg degree—

Attacker avg degree—

Honest avg clustering—

Attacker avg clustering—

Density verdict—

Toggle "Reveal Attackers" to see which nodes are fakes. Notice the attacker cluster scores higher on both degree and clustering coefficient. A naive trust system that uses these density metrics would rate the attackers as more trustworthy than the honest nodes. This is the density shield.

The fundamental asymmetry: an attacker controls the edges inside their cluster (they can add as many as they want for free), but they do not control the edges in the rest of the graph. Density metrics measure what the attacker controls. Path diversity measures what they don't.

II. Path Diversity Analysis

Now click any node to select it. The system computes all vertex-disjoint paths from that node to the verifier (the gold diamond node). Honest nodes have paths that spread through many different intermediaries. Attacker nodes have paths that all converge through the same bridge nodes.

Selected: click a node

Vertex-disjoint paths—

Path diversity score—

Density score—

Clustering coeff—

True identity—

Node	Type	Degree	Clustering	Disjoint Paths	Path Diversity	Density Verdict	Diversity Verdict

Look at the table: density metrics often give attackers a "trusted" verdict, while path diversity consistently identifies them as suspicious. The few cases where an honest node scores low on diversity are nodes at the periphery — they have low density scores too, so both metrics agree. The disagreement zone, where density says "trusted" but diversity says "suspicious," is almost exclusively populated by attackers.

III. The Race: Attack Cost Scaling

Here is the key economic question: how much does it cost to fool each metric? For density, the attacker just adds more fake nodes with mutual attestations — cost scales linearly with the target score. For path diversity, the attacker must compromise existing independent nodes in the organic graph to create new bridge points — cost scales combinatorially because each new independent path requires a node in a different region of the graph.

Fake nodes: 5 Cost per fake (sats): 100 Cost to compromise a real node (sats): 2000

Cost to fool density—

Cost to fool diversity—

Cost ratio—

Diversity paths needed—

The chart shows two cost curves. The red curve (cost to fool density) grows linearly — each additional fake node adds a fixed cost. The green curve (cost to fool path diversity) grows much faster because to add each new independent path, the attacker needs to compromise a node in a different part of the graph, and available targets get scarcer.

Cost to fool density to level k: C_d(k) = k * cost_per_fake
(just create k fake nodes, each attesting to the others)

Cost to fool path diversity to level k: C_p(k) = sum_{i=1}^{k} cost_compromise(i)
where cost_compromise(i) grows with i because:
- Each new path needs a node NOT on any previous path
- Available independent bridge candidates shrink: |V| choose k grows as C(n,k)
- The attacker must find and compromise nodes in separate graph regions

For a graph with n honest nodes, avg degree d:
C_p(k) ~ cost_real * k * (k / (n*d)) * ln(k) [approximate, grows super-linearly]

Why This Matters for NIP-XX

A reputation protocol built on density metrics is a reputation protocol that can be gamed by anyone willing to spin up VMs. A protocol built on path diversity forces attackers to compromise the organic topology — to actually embed themselves in the real social graph in ways that require sustained real-world relationships. The cost isn't just sats; it's time, social capital, and the risk of exposure at every compromised node.

The practical implementation uses a modified max-flow algorithm with vertex splitting (each node becomes an in-node and out-node connected by a single edge) to compute vertex-disjoint paths efficiently. For a network of N nodes and E edges, this runs in O(V * E) time — fast enough for real-time evaluation on Nostr relay networks.

Density is a local property. Topology is a global property. Attacks are local (the attacker builds a local structure). Defense must be global. This is why path diversity works: it forces the verifier to examine the entire graph structure between itself and the target, not just the target's neighborhood.