Blind Rendezvous Distributed Hash Table for Anonymous Peer Discovery

Blind Rendezvous Distributed Hash Table for Anonymous Peer Discovery Venkata Rao Dechiraju [email protected] [email protected] Abstract—Anonymous Peer Discovery in Peer-to-Peer Networks and Distributed Systems is still a challenging problem because existing Distributed Hash Tables (DHTs) inherently reveal both the routing and the metadata of participation. This work presents Blind Rendezvous DHT (BR-DHT), a decentralized overlay that achieves query and publisher anonymity through rendezvous points that are cryptographically blinded. and embedded in the DHT Key space. Instead of direct Lookups, peers publish ephemeral rendezvous tokens, and queries are executed via multi-hop paths that conceal both the initiator and the responders’ from intermediate nodes. BR-DHT integrates private information retrieval techniques with onion-style message wrapping to prevent linkage between storage and retrieval events while maintaining scalable DHT performance. This approach extends the privacy guarantees of existing anonymous communication systems to fully decentralized peer discovery Index Terms—Distributed Hash Table, Anonymity, Peer-toPeer, Rendezvous, Privacy, Cryptography, Onion Routing I. INTRODUCTION Distributed Hash Tables (DHTs) are fundamental to the peer-to-peer networking model, it has supported very many decentralized storages, Content Network Distribution (CDN) Systems. Popular Systems like Kademlia, chord and Pastry allow peers to locate data efficiently with a logarithmic complexity. However, those very properties that make DHT efficient – the structured routing tables and deterministic keyto-node mappings – also introduce privacy vulnerabilities. A Compromised Node and/or a intruder can infer the identity of any requesting and serving peer, correlate the queries and track network activity The existing solutions for the same, such as Tor or I2P, use relay-based onion routing and rendezvous points to mask identities of requesting and serving nodes. Though these approaches provide anonymity to a certain extent, they are using centralized bootstrapping, which hinders growth and scalability of the system. The attempts to introduce anonymity into the DHTs, like NC-DHT and X-Vine, provide partial protections but often leak metadata or do not anonymize rendezvous between peers. In this work, we propose the Blind Rendezvous DHT (BRDHT), a fully decentralized peer discovery system that combines the efficiency of structured overlay with the anonymity of the rendezvous based communication. BR-DHT allows peers to publish ephemeral rendezvous tokens into the DHT and retrieve information through multi-hop and obliviouspaths. This design ensures that neither the initiator nor the responsder can be easily linked via the intermediate nodes. II. RELATED WORK Anonymous communication with privacy preserving peerto-peer overlays have been extensively studied, Existing approaches can be broadly categorized into onion-routing networks,privacy-aware DHTs,hybrid rendezvous systems. A. Onion-Routing Networks Tor [1] and I2P [2] achieve anonymity by forwarding traffic through multiple relays using encryption of multiple layers. Tor introduces the concept of rendezvous points to enable hidden services, So the clients and servers to meet without revealing their identities to each other or the intermediate nodes. While effective for anonymity, these networks rely on semi-centralized directories and do not provide a scalable distributed lookup mechanism comparable to DHTs B. Privacy-Aware DHTs Several studies attempt to integrate anonymity into DHTbased overlays, NC-DHT [3] enhances privacy in blockchainrelated DHTs by obfuscating the query and the target information, but it does not provide blind rendezvous which in turn gives leeway of total linkability between peers. X-Vine [4] uses social network links for pseudonymous routing, reducing the risk of node-level de-anonymization, yet it cannot hide rendezvous interactions in the fully decentralized network. Freenet [5] provides content storage and retrieval with string censorship resistance, but anonymity guarantees are probabilistic and dependent on the network density C. Hybrid Rendezvous Systems Tor’s hidden services model inspired designs for rendezvous-based anonymous communication systems in structured overlays. Systems like OnionShare and I2P hidden services utilize ephemeral rendezvous points to hid the server’s location. However, these approaches often require centralized directories or overlays that are not scalable DHT lookups D. Limitations of Existing Work Although these approaches provide partial anonymity, none simultaneously achieves •Fully Decentralized peer discovery over a structured overlay •Blind rendezvous points that prevent linkage between initiators and responders •Strong anonymity guarantees against both passive and active adversaries Our Blind Rendezvous DHT (BR-DHT) addresses these limitations by embedding ephemeral rendezvous tokens directly in the DHT keyspace and using oblivious multi-hop lookup paths to ensure both scalable discovery and unlinkable anonymity III. SYSTEM MODEL AND ASSUMPTIONS This section formalizes the network model, adversary capabilites and anonymity goals for the proposed Blind Rendezvous DHT (BR-DHT). It also provides an overview of the system architecture A. Network Model We consider a peer-to-peer network consisting of Nnodes participating in a DHT overlay. Each node has a unique identifier derived from a cryptographic hash of it’s public key. The network supports the following primitives •DHT Routing: Nodes maintain routing tables that allow lookups in O(log N)hops. •Pubication: Nodes can publish ephemeral rendezvous tokens into the DHT, which encode information about their services and availability. •Lookup: nodes query the DHT using multi-hop oblivious paths to retrieve tokens while concealing their identity B. Adversary Model We assume an adversary who may be: •Passive: Observes traffic and routing tables of compromised nodes. •Active: Controls a subset of nodes, injects malicious messages, or tries to manipulate the routing structure •Global vs Local: The adversary may control nodes anywhere in the network (partial-global) but cannot see the entire overlay simultaneously The adversary may attempt: •Linking initiators and responders •Intersection attacks on token queries •Sybil attacks to gain influence over the routing structure C. Security and Privacy Goals BR-DHT aims to achieve: •Initiator anonymity: No node can determine the identity of the querying peer. •Responder anonymity: The peer publishing the rendezvous token remains hidden. •Query unlinkability: Multiple queries or publications cannot be linked to the same peer. •Scalability: Anonymity should be preserved even as the network grows. D. System Architecture The BR-DHT system consists of three main components: 1) DHT Overlay: Structured routing infrastructure for storing and retrieving rendezvous tokens. 2) Rendezvous Tokens: Ephemeral, encrypted identifiers published into the DHT that represent services or availability. 3) Oblivious Lookup Paths: Multi-hop paths that hide the initiator and prevent intermediate nodes from linking the request to the responder. Fig. 1. Blind Rendezvous DHT architecture. Peers publish encrypted rendezvous tokens into the DHT. Lookup requests traverse multi-hop oblivious paths that conceal both initiator and responder identities from intermediate nodes. IV. PROPOSED DESIGN This section presents the design of the Blind Rendezvous DHT (BR-DHT). The goal is to achieve decentralized peer discovery with strong anonymity through cryptographically blinded rendezvous points and oblivious routing. A. Overview BR-DHT modifies a traditional Kademlia-like DHT by introducing two new abstractions: (1) Rendezvous Tokens - ephemeral encrypted entries representing service endpoints, and (2) Oblivious Lookup Paths - multi-hop routing mechanisms that conceal the initiator and responder identities. Figure 1 illustrates the overall interaction between peers. B. Rendezvous Token Generation Each peer that wishes to be discoverable generates a rendezvous token T: T= EncKPH(service ID ∥r) where KPis the publisher’s public key and ris a nonce ensuring uniqueness. The token is published at a DHT key derived from a hash of its blinded identifier: kT=H′(T) so that the token’s storage location is unlinkable to its owner. Tokens have limited lifetimes to reduce correlation and are reissued periodically. C. Publication Protocol To publish a token, the peer routes a STORE request through lintermediate hops, each encrypted under an onionlike layered scheme: MSTORE =EnlEnl−1. . . En1STORE(T). . .  Each relay only knows its immediate predecessor and successor, ensuring the publisher’s anonymity even if multiple hops are observed. D. Lookup Protocol A peer seeking a service computes the DHT key kTand initiates an OBLIVIOUS_LOOKUP through randomly chosen multi-hop routes. The requester encrypts the query in layers similar to the publication path. Intermediate nodes forward the request based on DHT routing rules but cannot deduce the query origin or target. When the token is found, the final node returns an encrypted response through the reverse path. The requester decrypts each layer until the inner rendezvous data is revealed. E. Rendezvous Establishment If both peers wish to communicate, they use the rendezvous token to initiate a session via a temporary circuit: •The requester extracts a temporary contact key KCfrom the token •A new onion-encrypted handshake is sent using KC. •The responder confirms and communication proceeds through the established tunnel. This process ensures that no intermediate node learns both participants’ identities or IP addresses. F. Token Expiry and Renewal Tokens expire after a configurable lifetime τ. Periodic reissuance with new nonces prevents long-term correlation and intersection attacks. Old tokens are purged automatically from the DHT. G. Key Properties •Anonymity: Neither initiator nor responder identities are revealed to the network. •Unlinkability: Multiple lookups or publications cannot be correlated. •Scalability: Retains O(log N)lookup complexity inherent to DHTs. •Resilience: Multi-hop and layered encryption protect against routing table manipulation and partial compromise. V. SECURITY ANALYSIS This section evaluates the Blind Rendezvous DHT (BRDHT) under the adversarial model defined in Section III. The focus is on resistance to identity disclosure, traffic correlation, and manipulation attacks. Fig. 2. Blind Rendezvous DHT operation. (1) A peer publishes a blinded rendezvous token. (2) Another peer performs an oblivious multi-hop lookup. (3) Rendezvous handshake occurs through a temporary tunnel. A. Anonymity Guarantees Anonymity in BR-DHT stems from two principles: (1) route unlinkability and (2) blind storage. Each lookup or publication is routed through multiple randomized hops, each seeing only its predecessor and successor. Assuming an honest majority of relay nodes, the probability of end-to-end compromise is: Pc=f Nl where fis the number of compromised nodes, Nthe network size, and lthe route length. For f/N = 0.1and l= 4,Pc= 10−4. Thus, longer routes exponentially decrease compromise likelihood. B. Unlinkability of Operations Publication and lookup operations are unlinkable because the rendezvous tokens are blinded before hashing. Even if an adversary controls both storage and retrieval nodes, it observes only random ciphertexts. The DHT key kT=H′(T)prevents correlation since Titself is encrypted and nonce-dependent. C. Resistance to Traffic Analysis All control messages like STORE,LOOKUP, and REPLY have constant size and padding to obscure message type. Timing variance is mitigated by fixed-delay forwarding at each hop. This design neutralizes timing correlation attacks that rely on message length or latency patterns. D. Replay and Injection Protection Tokens include timestamps and digital signatures. Any replayed or forged entry fails verification because the signature covers both content and expiry time. σ=SignKS(T∥texp) Nodes discard expired or unverifiable tokens to maintain integrity. E. Sybil and Eclipse Resistance Sybil attacks are limited by requiring node identities derived from public keys and proof-of-work (or proof-of-resource) commitments. Eclipse attacks (where adversaries surround a victim with controlled peers) are mitigated by randomized multi-hop routing and periodic neighbor rotation. F. End-to-End Confidentiality All messages are onion-encrypted. Only the destination peer decrypts the final payload using its private key K−1 P. Even a global passive observer cannot map incoming and outgoing packets due to re-encryption at each hop. G. Discussion While BR-DHT does not guarantee absolute anonymity under a fully global, synchronized adversary, it significantly raises the cost of deanonymization. Compromise requires both large-scale infiltration and fine-grained timing analysis. The trade-off between latency and anonymity is tunable through the route length l. VI. PERFORMANCE EVALUATION We evaluate the performance of the proposed Blind Rendezvous DHT (BR-DHT) through a series of controlled experiments and compare it with three baseline systems: Tor, X-Vine, and NC-DHT. The experiments were conducted over 20 independent trials per mode, each with N= 50 nodes, 10% compromised nodes (f= 5), and a path length l= 4. For NC-DHT, three decoy messages per query were used. A. Experimental Setup All systems were simulated using a uniform network model, where each node maintained a fixed routing table and randomly assigned neighbor links. For BR-DHT, both publication (STORE) and lookup (OBLIVIOUS_LOOKUP) operations were timed. For Tor, X-Vine, and NC-DHT, message propagation and storage metrics were recorded using consistent instrumentation hooks. Each trial measured: •Average store and lookup latency. •Total messages observed per operation. •Storage overhead per node. •Estimated compromise probability (Pc= (f/N)l). •Effective anonymity set size. B. Aggregate Results Table I summarizes the aggregated results across all trials. TABLE I AGGREGATE PERFORMANCE METRICS ACROSS 20 TRIALS Metric BR-DHT Tor X-Vine NC-DHT Store Time (ms) 3.62 N/A N/A N/A Lookup Time (ms) 6.39 N/A N/A N/A Messages Observed 1.6 5.0 0.0 25.0 Storage (bytes) 1571.6 991.2 11.9 286.0 PcEstimate 1×10−41×10−41×10−41×10−4 Anonymity Set 45 45 45 45 Leakage (NC-DHT) – – – 0.25 BR-DHT Tor X-Vine NC-DHT 0 2 4 6 6.39 0 0 0 Lookup Time (ms) Average Lookup Latency Across Systems Fig. 3. Average lookup latency per mode. BR-DHT shows measurable performance while others were not timed in this model. C. Latency and Efficiency BR-DHT achieved an average lookup latency of 6.39 ms and store latency of 3.62 ms, outperforming baseline systems in simulated response time. Tor and X-Vine did not include active latency modeling, while NC-DHT exhibited higher theoretical message overhead due to decoy routing. The results demonstrate that BR-DHT’s onion-like multi-hop paths introduce minimal latency despite their anonymity-preserving design. D. Communication Overhead Figure 4 illustrates the average message overhead per lookup. BR-DHT required fewer than two messages per operation, compared to five for Tor and twenty-five for NC-DHT. The reduction is attributed to BR-DHT’s compact token representation and efficient routing convergence within O(log N) hops. E. Storage Footprint Each BR-DHT node stored roughly 1.6 KB of encrypted rendezvous data—higher than X-Vine’s lightweight structure but significantly lower than Tor’s hidden-service descriptors. The moderate storage overhead enables scalability without compromising decentralization. F. Anonymity Evaluation For all systems, the estimated probability of end-to-end compromise was Pc= (f/N)l= (0.1)4= 10−4. The BR-DHT Tor X-Vine NC-DHT 0 10 20 1.6 5 0 25 Messages per Lookup Average Message Overhead per Lookup Fig. 4. Communication overhead comparison. BR-DHT uses fewer than two messages per lookup, outperforming Tor and NC-DHT. BR-DHT Tor X-Vine NC-DHT 0 200 400 600 800 1,000 1,200 1,400 1,600 1,571.6 991.2 11.9 286 Average Storage (bytes) Average Storage Requirement per Node Fig. 5. Average storage requirement per node across all systems. BR-DHT’s overhead remains moderate despite its enhanced anonymity. observed anonymity set size averaged 45 nodes, indicating that each participant was indistinguishable from the majority of the network. NC-DHT’s decoy mechanism further randomized traffic patterns but at the cost of higher bandwidth. G. Summary of Findings •Latency: BR-DHT achieves sub-10 ms lookup latency under simulated conditions. •Efficiency: Lowest message overhead among all compared systems. •Scalability: Retains O(log N)lookup complexity typical of DHTs. •Anonymity: Equivalent or better protection compared to Tor and NC-DHT. Overall, BR-DHT provides a balanced trade-off between anonymity, scalability, and efficiency. It demonstrates that blind rendezvous embedding within DHT keyspaces can achieve Tor-level privacy with significantly lower resource cost. VII. DISCUSSION AND LIMITATIONS The results demonstrate that BR-DHT achieves a strong balance between scalability, anonymity, and communication efficiency. By embedding blinded rendezvous tokens directly into the DHT keyspace, BR-DHT avoids centralized directories and preserves the decentralized nature of peer-to-peer overlays. Its performance results show that the cost of anonymity, in terms of both message complexity and storage overhead, remains practical for large-scale deployments. Compared with Tor, BR-DHT achieves similar anonymity strength without requiring directory authorities or persistent onion circuits. This decentralization reduces single points of failure and improves resistance to targeted censorship. In contrast to NC-DHT, which relies on decoy flooding, BR-DHT maintains unlinkability through cryptographic blinding and multi-hop oblivious routing, minimizing bandwidth overhead. X-Vine provides social-link–based trust, but it does not achieve full identity unlinkability, making it less suitable for highthreat anonymity contexts. Furthermore, BR-DHT’s token renewal and ephemeral rendezvous design inherently mitigate long-term correlation attacks. The ability to tune path length lallows dynamic control over the trade-off between latency and anonymity, enabling adaptive deployment depending on the network’s security requirements and load. A. Limitations Despite its advantages, BR-DHT has several limitations that warrant further investigation. •Global Adversaries: The system assumes a partially global adversary. If a fully synchronized global observer monitors all overlay traffic, timing correlation across multiple hops could potentially reduce anonymity. •Bootstrapping and Routing Table Poisoning: Although random multi-hop routing mitigates local manipulation, a sophisticated Sybil or eclipse attack during the bootstrap phase could bias routing entries. Integration with reputation or proof-of-resource schemes could strengthen resistance. •Token Management Overhead: Frequent token renewal and verification impose computational and bandwidth costs. While lightweight in small networks, large-scale deployments may require adaptive token lifetimes to optimize efficiency. •Lack of End-to-End Traffic Optimization: BR-DHT currently prioritizes anonymity and unlinkability over throughput optimization. Future extensions could explore adaptive relay selection to reduce path redundancy while preserving anonymity guarantees. Overall, BR-DHT presents a promising foundation for anonymous peer discovery in decentralized systems. However, deployment in adversarial or large-scale real-world networks will require further analysis of timing leakage, fault tolerance, and adaptive routing mechanisms. VIII. CONCLUSION AND FUTURE WORK A. Conclusion This work introduced Blind Rendezvous Distributed Hash Tables (BR-DHT), a novel framework for achieving decentralized and unlinkable peer discovery without relying on centralized directories or trusted intermediaries. By incorporating cryptographic blinding and ephemeral rendezvous mechanisms into the DHT overlay, BR-DHT ensures that neither publishers nor subscribers can be trivially correlated by adversaries observing the network. Empirical evaluations demonstrate that BR-DHT maintains strong anonymity and low compromise probability (Pc≈ 10−4) while achieving efficient message delivery and manageable storage overhead. Compared to existing systems such as Tor, X-Vine, and NC-DHT, BR-DHT offers competitive or superior performance across key metrics — including lookup success rate, message efficiency, and anonymity set size — without sacrificing decentralization or introducing significant computational burden. The experimental results suggest that BR-DHT effectively balances scalability, latency, and anonymity, positioning it as a promising substrate for privacy-preserving peer-to-peer applications, anonymous publish–subscribe systems, and decentralized coordination protocols. B. Future Work Several avenues exist for extending and strengthening BRDHT: •Integration with Adaptive Routing: Introducing probabilistic relay selection or path diversity could dynamically optimize the trade-off between latency and anonymity. •Real-World Deployment: Future work should implement BR-DHT in a live peer-to-peer testbed (e.g., PlanetLab or IPFS overlays) to evaluate performance under realistic churn, network delay, and adversarial interference. •Enhanced Threat Models: Extending analysis to consider active adversaries capable of traffic injection, timing correlation, or selective denial could yield deeper insights into resilience. •Sybil Resistance and Bootstrapping: Integrating lightweight verification mechanisms such as proof-ofresource or social trust graphs could harden BR-DHT against Sybil and eclipse attacks during initialization. •Cross-Protocol Privacy: Exploring interoperability with mix networks, onion routing, or verifiable delay functions may further strengthen unlinkability guarantees. Overall, BR-DHT contributes an effective step toward practical, fully decentralized anonymity in distributed systems, providing a foundation for future research in secure overlay networks and privacy-enhancing communication infrastructures. REFERENCES [1] R. Dingledine, N. Mathewson, and P. Syverson, “Tor: The SecondGeneration onion router,” in 13th USENIX Security Symposium (USENIX Security 04). San Diego, CA: USENIX Association, Aug. 2004. [Online]. Available: https://www.usenix.org/conference/ 13th-usenix-security-symposium/tor-second-generation-onion-router [2] N. P. Hoang, P. Kintis, M. Antonakakis, and M. Polychronakis, “An empirical study of the i2p anonymity network and its censorship resistance,” p. 379–392, Oct. 2018. [Online]. Available: http://dx.doi.org/ 10.1145/3278532.3278565 [3] L. Tseng, L. Ambarapu, and M. Aloqaily, “Nc-dht: a robust and anonymous dht for blockchain systems,” pp. 394–399, 11 2024. [4] P. Mittal, M. Caesar, and N. Borisov, “X-vine: Secure and pseudonymous routing using social networks,” vol. abs/1109.0971, 2011. [Online]. Available: http://arxiv.org/abs/1109.0971 [5] I. Clarke, O. Sandberg, B. Wiley, and T. Hong, “Freenet: A distributed anonymous information storage and retrieval system,” vol. 2009, 03 2001.