R2E: A Decentralized Scheme for Rewarding Tor Relays With Cryptocurrencies

Tor's original design does not have an incentive mechanism but relies on volunteers to maintain their relay nodes for free, eventually leading to the current situation of centralization and lack of relay nodes. Current incentive schemes designed for Tor generally rely on centralized roles, thus presenting a risk of destroying Tor's anonymity. This paper proposes R2E, a decentralized scheme that treats Tor relay services as cryptocurrency mining and rewards the relays with generated tokens while addressing the challenge of how to design decentralized protocols that quantify workload while ensuring fairness and anonymity. We construct the Proof-of-Relay protocol in R2E that enforces random circuit selection, limits the number of nonce attempts, and exploits one-time keys and zero-knowledge proofs to protect participants' identities. We implemented a prototype of R2E based on Ethereum and conducted the trial operation and several confirmation experiments involving 2²⁰ clients, 2¹⁰ to 2¹⁶ nodes, and 256 circuits for each client to demonstrate its applicability. Analysis and experimental results show that R2E can effectively ensure the anonymity of participants' identities and fairness of incentive allocation while showing good performance in overhead and scalability, making it easy to be quickly applied in practical deployments.