Last year, we released Arke [MSGJ24], a protocol for privacy-preserving contact discovery. We also shared an experimental prototype of the system which we used to run geo-distributed benchmarks for our paper. Since then, the paper has been peer-reviewed and published in ACM-CCS'24.

The goal is to allow users of an existing social graph (e.g., 𝕏) to find each other and construct a new graph (e.g., Bluesky) without revealing either of the social graphs nor publicly linking the existing and new accounts. I encourage you to read this article by Moxie Marlinspike for more context on why contact discovery is desirable and hard to do privately.

In this short note, I highlight how to apply our protocol to provide a contact discovery service for 𝕏 users joining Bluesky.

Actors

The protocol requires the following actors:

• Setup committee (aka discovery service): a committee of $n$ entities that hold shares of a BLS signing key. We need to assume that $t$ participants are honest. These entities will need to verify zero-knowledge proofs and emit BLS signatures.
• Public bulletin board: a publicly accessible bulletin board, can be untrusted.
• User client: users will need to run a client app. This app will be responsible for generating lightweight ZK proofs, performing a one-time setup (by communicating with the committee), publishing anonymized connection requests on the bulletin board and periodically check it for relevant connection requests.

The number of authorities $n$ and threshold $t$ are parameters we get to choose. The fewer authorities there are, the faster users can get set up; on the flip-side it means we trust each authority a bit more.

Protocol overview

We give a high-level overview of the protocol, specialized for Bluesky’s use-case.

• Committee setup (one-time): run a DKG between the committee entities.
• User setup (one-time per user): each user produces a ZK proof of their 𝕏 handle (e.g. using zkemail). Users show this proof to $t$ honest authorities to obtain a unique discovery key.
• Discovery (peer-to-peer process between users, facilitated by the bulletin board): during the discovery phase, a user (Alice) can combine her discovery key and a friend’s 𝕏 handle (Bob) to derive a unique seed. Similarly, Bob can use his discovery key and Alice’s 𝕏 handle to derive the same unique seed. This seed is used to bootstrap an anonymous communication channel over the bulletin board. Using this channel, users can disclose their Bluesky handle. Importantly, the Bluesky handle is only disclosed to friends we intentionally choose to disclose it to.

What is “a friend”?
We can choose what a friend means in our context. Could be:

• users who follow me on 𝕏,
• users I follow on 𝕏, or
• an intersection or union of the above.

The great thing is that each user can set this to their preferences. The above assumes that the user client will be able to access the list of 𝕏 followers / following, either by logging in or scraping it.

Experimental performance

In our (very unoptimized) experiments, the user client running on an M1 Mac performed ≈2.5 seconds of computation per committee member it interacted with. Discovery is on the order of milliseconds per friend.

References

[MSGJ24] Nicolas Mohnblatt, Alberto Sonnino, Kobi Gurkan, and Philipp Jovanovic. 2024. Arke: Scalable and Byzantine Fault Tolerant Privacy-Preserving Contact Discovery. In Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security (CCS ’24). Published version: http://doi.org/10.1145/3658644.3670289. full version: https://eprint.iacr.org/2023/1218.