Since my last diary, I published the proposal for permissioned data. Thatās the big kahuna folks! Give it a read. Since then, I went to Dweb camp and Local-First Conf where I got the chance to meet and hang with lots of awesome folks building stuff on the protocol. Thereās clearly a lot of excitement & energy around permissioned data. I failed to read the fine print on accepting a 3D printed keychain from and agreed to have the protocol done in 2 weeks time. Weāll see if I can follow through on that š
Some quick housekeeping/updates:
Check out that proposal & give me feedback over here
Things are still changing! I expect updates to the proposal before we reach an "official spec". Though I suspect the big picture is pretty firm at this point.
Based on community input, we removed the member list from the design
I made a forum post about returning to the
at://scheme. This is still undecided, but I continue to lean in that direction which the current proposal reflectsWe have a community working group going to spec out "Atmospheric groups/communities" (think
standard.sitefor communities). Check it out and join the convo if you're interested in this work.I'm working on an alpha version of the protocol & PDS. I'm hoping to have that out in the next couple weeks. I've been conferencing the last week & Iāll be at the IETF in Vienna next week. But it will be coming soon! Several folks in the ecosystem already have working implementations of the current proposal which is amazing to see
Alright, so the outcome of Diary 6 was that we got a "space credential" for accessing data in a space. This diary is going to get into what you actually do with that credential. In other words, how that data is stored and synced between parties.
The quick & dirty of it
Zooming out, let's remember what we're trying to achieve here: a network that basically feels the same as public broadcast atproto. As I described in the second diary:
"users publish records, those records are canonically stored in the userās PDS, applications crawl PDSes and sync data to build their own views..."
To keep things symmetric, we probably want the following in our sync protocol:
a user-owned repository
a cryptographic commitment over the repository so that a syncer can know that it has a complete copy of the user's data
a pull-based sync protocol, likely operation-based
You can see a full description of the proposed permissioned repository & sync protocol in the proposal that I recently published. It generally mirrors the public broadcast protocol in semantics, but differs in a few important ways. I'll spend this post walking through each of those differences.
Before we get into it, the through-line on all of this is that public broadcast data is substantially different from permissioned data. It's not even just a āpublic vs privateā thing. Public broadcast data is "on the record" in some sense. It's archival, self-authenticating, redistributable, and published to "the public commons". Permissioned data is deliberately none of those things. The techniques and mechanisms that give public broadcast data those qualities are not a good fit for permissioned data.
I'd argue this turns out to be a good thing, as we get a substantially lighter-weight repo & sync protocol on the other end!
MST vs multiset hash
The MST (Merkle Search Tree) has almost become synonymous with atproto (thatās the data structure for the public repository, donāt worry you donāt need to know what it is). However, we're not planning to use it for permissioned data. I've received some pushback that, even if it's not the correct data structure for the job, we should still use it for familiarity's sake and to "unite" the protocols.
To contextualize this decision: I believe that if the permissioned data protocol is successful it will have at least an order of magnitude more data (likely even more than that) than the public broadcast protocol. This isn't an "old vs new" protocol thing. It's just that most of the things we do online, even the public stuff, are not intended to be "manifestly public" in the way that the public broadcast protocol is. I believe it's much more important that we choose the right tool for this job rather than trying to maintain similarity to a protocol with likely significantly less traffic/data.
The MST is a heavy data structure. To prove a single record, you need all of the data from that record as well as every structural node of the MST up to the commit (usually between 3-7 nodes) and finally the commit which includes the signature. This is a lot of data. It's also difficult/complex to produce an MST and proof. Logical complexity can be solved in code, but MST operations generally require PDSes to hang on to the full representation of the merkle tree which brings all sorts of operational hardships (MSTs & Postgres donāt play super nice).
The big thing you get out of using a merkle tree is "partial sync" with a special case of that being a proof for a single record. This is very important for the public broadcast protocol where a user has a repo containing all of their data. Many apps only want some small piece of that, and they want the sync of that small piece to be self-authenticating without requiring the entire repository.
Permissioned data differs in this regard because all published data is situated in a particular space. The space provides the sync boundary, and in most cases syncers will want to sync the entire repository in the space. Partial sync is less important, and I expect single-record proofs will rarely be needed. Another way of putting it is that the āpartialā sync for permissioned data comes from the space (as a space is only āpartā of all of a userās permissioned data) rather than from slicing into a repository.
One thing we absolutely do want to retain from the MST is the idea of a "root hash" of the data. This is some small value that can serve as an integrity check that you possess the entire data set.
If we get rid of the need for partial sync or individual record proofs, thereās a much lightweight data structure that we can use that still commits over the entire repository: a multiset hash. If a hash is a unique fingerprint for some piece of data, a multiset hash is a fingerprint for a collection of items. It's computed order-independent and items can be added/removed incrementally.
For our use case, we can model a permissioned repo as a collection of strings: collection/rkey/record_cid.
Comparing hashes
The simplest version of a multiset hash is an XOR-of-hashes (this probably isn't actually classified as a multiset hash, but whatever it helps give the intuition). Take each item in the set, hash it, and XOR the hashes together. Updates are easy! If you create an item, you just XOR it into the set. If you delete it, you XOR it out.
Unfortunately, these are susceptible to Wagner's Generalized Birthday Attack. I'll avoid getting into all the details & tradeoffs of that attack. I think you could argue that for our use-case, there's actually not a clear attack to pull off with that (it's kinda a self-own to do so). But in cryptography, you never want to have to make a justification like that. And it's a bit of a category error to sign or MAC something that isn't itself cryptographically secure.
So what then? Well Elliptic Curve Multiset Hashes (ECMH) are intended to respond to exactly this! Unfortunately, these get broken by quantum computers via Shor's algorithm, and I was strongly encouraged by Filippo to not use them.
The Wagner-and-Shor-secure multiset hash is an LtHash. This thing is actually pretty slick & turns out to be (I think) even simpler than ECMH. It's basically a āØfancyāØ XOR of hashes.
You can think of XOR-of-hashes as taking each bit of your current hash, then either adding or subtracting the bit in the same position from the hash of the item you're adding/removing, and then taking the result modulo 2 (in modulo 2, add & subtract end up having the same result: an "XOR").
LtHash is the same basic operation, but you take a bigger hash (2048 bytes instead of 32), split it into 2-byte ālanesā, add/subtract each lane, and then take the result of that modulo 2^16. It's basically XOR-of-hashes in mod 65536 instead of mod 2. It's really pretty simple and turns out to be like 80 lines of very readable code.
The only downside is that the state is 2kb rather than 32 bytes. This is trivial state to keep around but still a bit heavier on the wire than we'd like to send. So both sides of the sync protocol are encouraged to maintain the full 2kb LtHash as state, however when the hash is signed or sent on the wire, we instead send the sha256 of the full hash.
Deniable signatures
Even if you've never heard of the MST, you probably know that we're signing stuff in atproto. This is what makes it "self-authenticating". It lets you rebroadcast data & is the bedrock of trust for our network.
However, I strongly believe that in the context of permissioned data, asymmetric signatures on data are an anti-pattern. I'd argue they give you the exact opposite thing you want. The point of permissioned data is that things within a space should only be visible in that space. Asymmetric signatures are a mechanism for allowing things to be redistributed outside of that space. If a piece of data breaks out of its access boundary, it's transmitted with an irrevocable proof of its authenticity.
The current proposal introduces a deniable signing scheme based on HMACs. This is a common approach in things like OTR, TLS and Signal (tho the exact scheme is a bit different).
Richard Barnes wrote up a great post on this and argued that deniability is not something that we should go out of our way for. Basically that messages generally leak via screenshots or other mechanisms, and the existence of signatures is negligible to the breach if it matters at all.
"Experience shows that when leaks like this happen, cryptography just isn't a major factor; see the DNC emails vis Ć vis DKIM or Signalgate with Signal, and of course the innumerable breaches where no cryptographic proof is available. At best, the black market gets a little more efficient by virtue of the ultimate customer of the data having less trust in the infiltrator middleman."
Also real quick: I really appreciate Richard for engaging with the proposal. I meant to respond earlier, but I was trying to get the proposal over the line & have been conferencing since then. I extended how much I would have otherwise said in this section in order to respond to his post :)
The null hypothesis that we should compare our design to is not the public broadcast protocol, it's other permissioned spaces on the modern web. In that context, I can't think of a single example in which unencrypted data is asymmetrically signed by users.
One way of looking at this is to say "does signing even matter at all" - for permissioned data (in the sense of deniability) but also for public data (in the sense of authenticity). I'm not trying to be flippant. I think you can look at the current state of the network and make the sincere case that signatures actually don't matter. Most apps use jetstream or microcosm. Even the apps that use the relay often don't bother checking signatures. The number of services doing full sync v1.1 semantics is very low.
So why bother signing stuff? Well every time you sync from jetstream or microcosm, since you don't rely on asymmetric signatures, you instead rely on your trust relationship with that service.Those trust relationships are able to evolve because consumers always have recourse to a fully authenticated & complete sync protocol. This is similar to the general "credible exit" argument in atproto - do the easy thing based on a trust relationship with recourse to the hard thing in case that relationship turns sour.
The existence of signatures "greases the wheels" on these trust relationships.
I think of signatures on permissioned data similarly. I don't want to "grease the wheels" on data escaping containment. Ideally data never escapes its access boundary. But it will. And when it does, it should be a social situation to navigate, not a technical one. Whether you trust the data should be a question of existing social relationships, reputability & trust. Consensus emerges socially, over time, about whether and how much a given leak can be trusted. If we sign the data, that consensus emerges in milliseconds regardless of the leaker.
Will this matter in court or the next time DNC emails leak? I'm not sure. But most users aren't going to court. There are many things that happen before "going to court" or becoming a national news story, and deniability is just as important in all of these everyday scenarios. In the cited examples, the leaks were published by credible sources and received a lot of attention. (Also Iād argue DKIM signatures were relevant especially in the case of the DNC leak, though we can argue how load-bearing that was).
By asymmetrically signing data, we lower the required trust level for a leaker down to zero. A leaker can be credible with no prior trust and with no analysis by trusted institutions. Meanwhile, even large corpuses of data (like the election emails) are becoming easier to fabricate through AI, increasing the importance of cryptographic authenticity and thus providing a different kind of deniability.
Privacy issues exist on the modern web in which your data is generally held by one application. We're increasing the cardinality of that relationship. Every additional app that has access to your data increases your exposure risk. I think this requires a complementary mechanism that lowers, or at least does not raise, your risk in the event of a leak.
Syncing without a relay
As I just discussed, permissioned data cannot be rebroadcast because it does not have an asymmetric signature. What does this mean for our super-duper global rebroadcasting machine - the relay?
Well, it means we can't do that. And downstream syncers always need to go directly to PDSes to sync. Donāt fret, this is fine! Relays were always an optimization over syncing directly from the PDS.
(Quick vibe note: I think a relay makes a lot of sense for global broadcast, but is itself at odds with permissioned data. Basically, I don't "miss" relays in this design. I think, as a role, they don't match the problem space.)
What does sync look like? Repos have a rev (basically a logical clock) that works similar to public broadcast repos. A syncer says "can I get everything that happened to this repo since my last rev". The PDS sends that as a list of operations, along with the MAC'd multiset hash. The syncer applies all of those operations to its own state and verifies it matches the hash that the PDS sent. If this fails for whatever reason and the syncer can't recover, they fall back to syncing the entire repo structure (which they can then diff in order to determine which records they need).
That's it! Abstractly, this is basically exactly Sync 1.1 semantics, but without requiring tricks like "operation inversion" because we're working with a simpler data structure than the MST.
I know everyone loves the firehose, and you might say "why can't we just keep the same WebSocket interface on the PDS?" A few reasons:
The Relay manages the complexity of the connection logic. It's a lot of work for applications to juggle thousands of WebSocket connections. Much easier to make HTTP requests.
Each PDS hosts many repositories, each requiring a different credential. Managing credentials for all these repositories over a single WebSocket is a lot of complexity.
Many PDSes have very low throughput. For them, getting a write out involves sending a notification to a relay, spinning up a websocket, sending one event, then just waiting for that connection to die. HTTP request is much simpler/direct and generalizes well to both large & small hosts.
HTTP/2 offers things like multiplexing & header compression. Even for big hosts with lots of throughput, I expect it to be comparable in terms of resource-usage to a WebSocket.
Don't despair over your lack of a firehose! I'm serious, this is such a lighter-weight protocol. I think application devs will really warm up to it. I also expect many applications will deploy a small sidecar to wrangle complexity rather than doing so themselves.
Write notifications
If everything is pull-based, we still need a way to make the system feel "real-time". In other words, syncers need to know when to pull so they can get updates shortly after writes.
For this, we introduce a very light-weight write notification. Repo hosts notify a space host when they write, and the space host fans this out to all syncers.
Write notifications are expected to come mainly from the space host, but can ultimately come from anywhere. They can be re-tried & re-sent without complications.
This is not an authoritative push. Ultimately it's best effort (though it should be best effort). But if a syncer ever misses a notification, they'll notice on the next sync (because of the multiset hash) and will automatically self-heal.
Thatās all folks!
That's basically the whole design of the protocol. Of course this series was mainly intended to provide intuition for the problem space and then motivate a particular solution, so we glossed over a lot of the little details and mechanisms along the way. You can find the latest on all of those in the proposal.
I'll probably write one more diary post, an addendum of sorts that goes over all the changes we made from the diaries along the way, including the URI scheme and removing the member list.
In the meantime, if youāre interested in participating in the formal standardization of the (public) protocol, I encourage you to join the IETF mailing list and participate in the upcoming working group meeting (on July 23). If youāre interested & have any questions, feel free to reach out.
Thanks again to everyone who's been following along & giving me feedback along the way :)