This reminds me of both Namecoin, stealth addresses and that Distributed Anonymous Credentials paper from the Zerocoin folks (consider it like an anonymized Namecoin). <a href="https://eprint.iacr.org/2013/622.pdf">https://eprint.iacr.org/2013/622.pdf</a> My take on how to use Namecoin profiles: <a href="http://roamingaroundatrandom.wordpress.com/2014/05/29/universal-p2p-address-book-software-using-namecoin/">http://roamingaroundatrandom.wordpress.com/2014/05/29/universal-p2p-address-book-software-using-namecoin/</a> Being able to tie a real world identity (vouched for by some entity like ID card issuers or CA:s) and credentials to your profile in a way which you can prove selectively in a non-replayable manner (I can prove my name to my friend, he can't prove it to somebody else) would be awesome. You could choose what would be public for all to see, and what only can be seen and verified in-person. (Stealth addresses comes into the mix for the anonymous messaging. It can not only be applied to Bitcoin addresses, but also for mailing.) You could actually use this practically everywhere. Proving you're a paying subscriber of your VPN service (just switch IP and even they don't know which of their customers you are), proving your citizenship as you mentioned, proving your gym membership, etc... And to make sure you can't be tracked across services but that you also can't make multiple profiles, they can challenge you to hash your ID's private key (or a similar challenge that can't be bruteforced on their side to reveal your ID) with their service ID, and prove with ZKP that it was created using your profile. You can only create one such hash per service, and they still don't know who you are. (About the same thing as your pond anti-spam idea.)