Mechanisms for private "block" relationships between Bluesky accounts

[bnewbold]

In late April (#922), we rolled out "blocks" in Bluesky, as a mechanism for individual accounts to control interactions.

NOTE: we will likely post more context about the decision to roll out public blocks, and will update with a link here if we do

In planning out how blocks would work in a federated system, we knew that there was a tension between making the actions public enough that all the services in the network could act upon them, but also the potential for harassment and call-outs if blocks were entirely public and enumerable. In the end we could not come up with a design for meaningfully "private" blocks while still having the block behaviors enforced consistently, so we went ahead with storing blocks as public records in atproto repositories, very similar to other graph records like "follow".

To re-iterate, the core block behaviors are:

• "symmetric": the block acts in both directions between two accounts, regardless of who blocked who first
• "mutual mute": neither account will see posts or oth content from the other, while logged in. note that that this is only "friction" for public content, and can be bypassed, but this "friction" is still helpful in many situations
• "no interactions": this includes things which would result in notifications (like mentions, new follows, etc), as well as not being able to reply in post threads

The purpose of this discussion is to describe some of the ideas we've had for non-public blocks, and to solicit ideas from the community.

[bnewbold]

Bloom Filters

One technical mechanism to keep blocks public, but make them less trivially "enumerable", would be to store them in Bloom Filters. These are a probabilistic data structure which makes it possible to check if an object is in a set, without having to store or transmit the entire set of objects. In the case of blocks, the pair of DIDs for each block relationship would be put in a bloom filter, and downstream services (eg, AppViews) would be able to check if a block relationship exists when needed.

There are a couple different ways bloom filters could be distributed. Each repo could have a single bloom filter with all blocks in it, and that gets distributed with the rest of repo content. Or an account's PDS could aggregate blocks for all local accounts privately and distribute a combined bloom filter. Or a small number of trusted 3rd parties could directly receive "private" block info from many PDSs, and publish a combined bloom filter.

We considered a series of designs like this, but there were two main problems we saw:

• first, this only adds an additional degree of "friction". it would still be possible for an even casually curious technical actor to get the bloom filter(s), and run billions of candidate block pairs. while full enumeration of the entire network is hard at the scale of hundreds of millions (N-by-N possible block relationships), usually people would only be curious about a specific community (smaller N), or a handful of accounts vs. the entire network. the set of all DIDs is public and enumerable in atproto. so looking up all blocks to/from a single account or for an entire sub-graph is still pretty easy
• second, the resource overhead and implementation complexity is non-trivial. bloom filters are efficient, but they are much larger than individual blocks. if there is a lot of block "churn" (changes in block preferences), that is amplified as many entirely new bloomfilters, which consume a large amount of disk storage and bandwidth to distribute (at least tends of KByte per change in block status). the raw block information still needs to be retained somewhere, and is now both crucial but private data. it would not be hard to "lazy linger" and only implement blocks in batches, but that introduces latency and a time delay between making a block and having it apply, which is unacceptable in the context of blocks

Maybe the friction of needing to figure out a bloom filter is sufficient! Blocks overall are mostly about "fiction" anyways (people can screenshot, sub-tweet, just log out, etc, to bypass). But the advantage isn't very certain, and the downsides are certain.

[bnewbold]

Label-based block enforcement

Instead of trying to consistently prevent all block-violating interactions across the network, it might be easier to scan for such violations and label them right after the fact.

This would look like a central labeling service which receives the full network firehose, and is also a trusted party that all PDS instances are willing to forward private block metadata to. The labeler would keep a database of allowed/disallowed relationships, and would label replies and quote-posts that violate those rules. Then everybody in the network would be expected to subscribe to this labeling authority and respect the labels, which would result in the content being filtered out consistently.

An added detail would be the need for PDS-to-PDS communication to notify the blockee and their PDS of the expected behaviors. This would usually not result in a notification, and in the ideal case the blockee's PDS would handle all of the mutual-mute and interaction block behaviors, it would only be in cases of bad actor PDSs that violating interactions would even exist.

This proposal would not handle retroactive blocking. That is, third parties would still be able to see (unlabeled/unfiltered) historical replies and other interactions between the two blocking accounts.

[bnewbold]

Interaction Gating

In this proposal, authority for many forms of interaction rests in the relevant account's PDS. It introduces a huge amount of PDS-to-PDS or AppView-to-PDS communication, moving a step closer to the ActivityPub model.

The basic idea is that post threads and quote posts would be the responsibility of the original post account's PDS. To render a post thread, all actors in the network would connect to that PDS to get a "thread skeleton" (base AT-URI identifiers), then hydrate in contents from a regular AppView for display. Block information would not need to leave that PDS, which already has a trust relationship with the blocking account.

[bnewbold]

@zenithlight that would reduce PDS-to-PDS traffic. The signature could also actually come from the account's signing key (facilitated by the PDS), which would work better with future account migration. A big benefit would be that while new writes would block until the PDS has responded (or be impossible if the PDS has downtime), reads would continue to be served, and read volume would not overwhelm a small PDS.

One complexity to work out would be key rotation: when an account (or PDS) signing key is rotated, do all the existing reply post records need to be updated with new signatures? Who is responsible to ensure that actually happens?

This feels like a fairly realistic solution for reply threads and quote posts.

[DavidBuchanan314]

This kind of gating would also work for other scenarios - for example, you could have a followers-only reply section, or "approved replies only" - it's up to the PDS to apply arbitrary criteria for allowing replies.

Rather than signing directly, why not "wrap" replies with a record that points at it? The record would be signed indirectly as a record in the repo, and so key rotation doesn't need any special consideration. It can also be federated though the existing federation mechanisms.

To elaborate, if user B wants to reply to a post by user A, user B creates and publishes a new post record like normal. However, this reply would not yet be visible in compliant clients. User A's PDS sees this record, and if it decides to (e.g. if there are no blocks in place), it creates an "authorizedReply" record, which simply contains a strongref to user B's reply. It acts as an endorsement - "I approve this reply to my post". Compliant clients will see both this endorsement, and the referenced reply, and decide to show it.

This has the bonus effect that 3rd party instances that directly federate with user A but not user B will still become aware of user B's reply, via user A's endorsement record.

[DavidBuchanan314]

Users could decide at time-of-posting whether they want replies to require verification in this way, with a corresponding flag set in the post record. If the flag is not present, replies can default to the original visibility behavior - so that users ok with "PvP" posting don't need to incur the overhead

[DavidBuchanan314]

This would also give users a lot of control over replies to their own posts. If they decide they don't like one, after the fact, they can delete the corresponding "authorizedReply" record.

[bnewbold]

We have separately been planning "interaction controls" to gate reply threads. Either simple "anybody/follows/nobody", or with composed reference to list. And probably OP labels would be applied to the entire thread to allow thread-local moderation, which helps with the "delete this post from my reply thread" feature. All of those mechanisms are public though, the difference with what is being discussed here is doing the gating via PDS interaction.

Another variation on the same ideas would be to only allow replies from a special "allowed-to-interact" list, published publicly similar to follows. Accounts that want to reply would connect to the OP's PDS and request to be added. The a negative reply would be private, a positive would be public (aka, added to the list automatically). All other network actors can see the list state and render accordingly, but the blocks and policy are not public. Solves the key rotation problem with regular repo process. Might scale weird with hundreds of thousands of replies? But even at the highest volume probably not crazy.

The "authorizedReply" concept is interesting. Similar to some ongoing discussions about forum-shaped spaces and interactions, which reply threads are spiritually similar to. It results in some reply amplification (multiple records in multiple repos). Does this need to be implemented for both the root of the reply thread (OP) and parent? If the parent blocks the "leaf" replier? I can't remember the specifics in that case.

Having PDS-to-PDS interaction at all will be a bit of a heavy lift if we ever decide to implement it.

[bnewbold]

Zero-Knowledge Proofs

There may be clever cryptographic tools that could be used to transmit the existence of a block action without having all blocks be enumerable. We asked our technical advisors, who have specific experience in this field, and they felt that there was not likely an off-the-shelf solution that we could realistically deploy in Summer 2023 without significant additional research and security review.

There are almost certainly interesting novel approaches to federated blocking coming from this area of research.

See also: SNARKBlock: Federated Anonymous Blocklisting from Hidden Common Input Aggregate Proofs, from 2022, by Michael Rosenberg, Mary Maller, and Ian Miers.

[daira]

There are two problems with the approach described in the SNARKBlock paper:

1. It requires a user that we are comparing against the blocklist, or some trusted service on their behalf, to do work linear in the blocklist size per attestation. There are various trade-offs for how you split up blocklists, and using newer techniques we can get the constant down (although the paper already includes some of the most obvious optimizations), but the linear-time asymptotic complexity is fundamental to the approach. Eventually you're going to have hundreds of billions of blocks, and there is not likely to be a proof system efficient enough to support that with reasonable latency for the foreseeable future. You can't even upgrade the proof system for those blocks; you're committing to doing those cryptographic operations (I think for each pair of users who try to interact, although like I say there are various trade-offs) for the lifetime of the platform — unless you just drop existing blocks at some point, which would be bad.

2. The blocklist contains the nonces of posts in the clear, and an author also has to know this nonce for their own posts. You don't get the id of the user who blocked you, but on another dimension this is more fine-grained information than you get from a public blocking system. In a public system you only get the fact that you've been blocked by a user, not which post caused them to block you (granted, you could possibly infer which post it was by timing).

Consider the consequences of feeding this data to an large language model AI. The AI gets fine-grained information about which of its posts are blocked, and after a while it gets very, very good at producing content that is propagated without being blocked. This is likely to be content of little merit (with some good stuff, but probably copied good stuff, mixed in) that people nevertheless want to propagate. It's going to be very plausible but completely without understanding, and when you interact with this thing you're going to be frustrated but just not frustrated enough to block it. Sounds like a nightmare to me.

I'm enthusiastic about applications of zk proofs, but I really don't recommend this approach.

[bnewbold]

Trusted AppViews

One proposal would be for accounts to privately register their blocks with their PDS, and then have PDSs forward block metadata to a small number of "blessed" AppViews. The AppViews can help enforce both the mutual-mute behaviors and interaction display behaviors, because they already handle thread and feed hydration, and would have full knowledge of the block graph.

The biggest issue of this approach is figuring out the trust relationship and authority of AppViews. What would a new AppView need to do to receive all private blocks? How would they know when they had all the relevant block graph context such that they could start servicing requests without violating expectations? These are easy questions with public blocks, very hard with private blocks. The incentives are also mixed: it is important for AppViews to enforce block behaviors, but it is also difficult for them to do so. AppView developers and service providers might decide that blocks just aren't worth the hassle and display content with only partial or even zero block metadata.