Distributed anonymity services, such as onion routing networks or cryptocurrency tumblers, promise privacy protection without trusted third parties. While the security of these services is often well-researched, security implications of their required bootstrapping processes are usually neglected: Users either jointly conduct the anonymization themselves, or they need to rely on a set of non-colluding privacy peers. However, the typically small number of privacy peers enable single adversaries to mimic distributed services. We thus present AnonBoot, a Sybil-resistant medium to securely bootstrap distributed anonymity services via public blockchains. AnonBoot enforces that peers periodically create a small proof of work to refresh their eligibility for providing secure anonymity services. A pseudo-random, locally replicable bootstrapping process using on-chain entropy then prevents biasing the election of eligible peers. Our evaluation using Bitcoin as AnonBoot’s underlying blockchain shows its feasibility to maintain a trustworthy repository of 1000 peers with only a small storage footprint while supporting arbitrarily large user bases on top of most blockchains.
@inproceedings{2020-asiaccs-matzutt-anonboot, author = {Matzutt, Roman and Pennekamp, Jan and Buchholz, Erik and Wehrle, Klaus}, title = {{Utilizing Public Blockchains for the Sybil-Resistant Bootstrapping of Distributed Anonymity Services}}, year = {2020}, pages = {531-542}, publisher = {ACM}, booktitle = {Proceedings of the 15th ACM ASIA Conference on Computer and Communications Security (ACM ASIACCS'20)}, DOI = {10.1145/3320269.3384729}, ISBN = {978-1-4503-6750-9/20/10}, }