28 Apr 2022
It seems that many people have started using Mastodon recently. But the place feels a bit empty, especially if like me you join a small server. How do I find my friends on Mastodon? Today, there are two ways: they tell me their handle using some other service, or I stumble upon one of their posts promoted by a common friend. This might work eventually, but it is much less straightforward than just searching by name or email address, something that is easy on Facebook. Of course, finding people should not be too easy, because it would provide avenues for spam or harassment. Facebook provides option, such as only making your account visible to “your friends”, or “the friends of your friends”. These options, and search in general, are straightforward to implement on a centralized server. Can we implement them in a decentralized network?
One obvious and wrong solution would be to broadcast search requests to every server in the whole network. That’s obviously wrong because it creates a huge load, and because it broadcasts private information to a lot of servers who don’t need to know about it. Another obvious and wrong solution is to create a distributed database of all registered names, maybe as a distributed hash table. That would create less load than broadcasting all name queries, but that would still broadcast the name information and create big privacy issues.
My preferred solution would be for users to send the queries to all their friends, as in “Hey, Bob, this is Alice, do you know Carol’s handle?” The load is lower than broadcasting queries. The privacy risks are more contained, although not eliminated. The queries will likely be visible to Bob’s server, and that server can build a database of all of Alice’s friends. Big servers would build bigger databases. This might provide incentives for centralization.
Can we design the queries in ways that minimize the privacy risks? We could use end to end encryption, so that the queries are only visible by the actual user, not their server. We could also encode queries, so they carry the one-way hash of the queried name, as in “Hey, Bob, this is Alice, do you know the handle of the user whose name hashes with this nonce to produce 0xdeadbeef?” Bob will have to compute the hashes of all his friends’ names, see whether one matches, and then return it.
Of course, the security worries do not end there. If we have any kind of automated search, it can be abused. Spammers do that on Facebook today: they manage to befriend someone, download the list of that person’s friends, and then try to befriend every person in that list. Encrypting or hashing queries will not prevent that, but something else might. For example, when receiving the query, Bob might relay it to Carol: “Hey, Carol, this is Bob. I got a message from Alice asking for your handle, shall I respond?” Carol can then decide.
We could also make the messages more complex. Facebook, for example, decorates friend requests with lists of common friends, so the user can make an informed decision. This fall in the general category of “introduction services”. This is hard to design, but we must start somewhere. It would make a ton of sense to add the distributed introduction service to a distributed social network, so maybe we should just start there.