Simulation on a synthetic social graph of one million nodes (average degree 4.65, maximum 13) shows that when 1.5% of nodes act as proxies and random routes of length r=5 are used, the median node can reach 3 proxies and more than 90% of nodes can access at least one proxy.

Centralized proxy-discovery services are reliably disabled by censors: both Anonymizer and SafeWeb were blocked in China by targeting their central discovery sites, and Wikipedia identified and blocked all 700+ Tor anonymizing relay servers to prevent anonymous edits. Any single publicly-known host that handles proxy distribution becomes the censor's primary and sufficient target.

§2 detection

Kaleidoscope uses at most one intermediate relay hop so proxies can serve users beyond their immediate trust neighborhood without directly learning user addresses. If a system allowed each proxy to directly advertise to N users, a censor posing as a proxy would learn N user identities; the one-hop relay design caps per-proxy exposure to r=5 relay addresses and keeps end-user identities hidden from proxies.

§3 defense

On a crawled Orkut subgraph of 42,474 users (≈90% Brazilian nodes treated as the censored domain, 15% of external nodes as proxies = 1.5% overall), the median node reaches 7 proxies — higher than the synthetic graph due to greater average degree (5.59 vs. 4.65) and lower clustering. Even when subverted trust links reach half the total proxy count, more than 94% of users can still access at least one proxy unknown to the censor.

§3.2 evaluation

Kaleidoscope bounds censor knowledge by routing proxy advertisements over symmetric random routes of length r=5 on a social trust graph: if the censor controls f subverted trust links, they can learn of at most r×f = 5f users or proxies regardless of how many Sybil identities they generate. Symmetric routing ensures the set a node learns of and the set that learns of a node are identical, closing the asymmetric information-leakage channel.

§3, §3.2 defense