Just a heads up I will be assuming a general familiarity with DIDs, the idea of a DID method and what that entails and the PLC DID method. Go read up on that if you want to understand this post. It's really interesting stuff!

It is not secret that for most atproto nerds the PLC DID method and specifically it's centralised registry is somewhere between the bane of our existence, the worst part of atproto or simply the place we lose most of the people coming from other decentralisation backgrounds. At the very least I don't think most of us would claim the PLC relying on a central (if limited in power) registry is ideal. I think a lot of us have somewhat accepted that this is just the price to pay for the features we need out of a good DID method. If we want a DID method that is "strongly-consistent, recoverable, and allows for key rotation"*¹ then the options are a central registry or blockchains ... no?

I've been thinking about this a lot ... probably an unhealthy amount to be honest!!*² Identity is the thing I think is most important to get really right. Everything else builds on top of it. A weak identity layer will drag a whole network down with it. Especially in a social setting. In fact identity was originally the thing that made me jump ship to atproto!*³ And I've heard from plenty others where this was the case. To me atproto is the closest we have to a shining example of a nearly perfect identity system ... However PLC is a bit of a thorn in the eye of that and it's annoyed me since ... well since i first learned about PLC. So of course I couldn't help myself but get a tad obsessed with trying to find an alternative. Recently a few pieces started to fall into place in my head forming an idea of a possible alternate answer: Read Aligned Wreath of Registries! aka did:rawr*⁴.

Stealing from PLC and tweaking

Bottom line is that overall I do actually quite like a lot of what PLC does! It's one of few DID methods that, to me, manage to have all the features that you realistically need for a DID method that's actually widely useful. Strongly-consistent, recoverable and key rotations are, again if you ask me, a no brainer and largely necessary features of a DID method for me to be able to take it seriously as an option for user accounts. Self-authenticating chains of "operations" are frankly a beautiful approach to the problem space*⁵! So let's steal it! The state of a did:rawr identity's DID document will be defined by a series of operations starting with a creation op that defines the initial state of the DID document and controller/rotation keys and whose hash will become the method specific identifier of the identity. The creation op is followed by a series of update ops that reassert a new state for the identity. An identity may eventually be capped off with a tombstone operation that makes the identity no longer usable, effectively deleting the identity. There are a few things here that I would take this opportunity to amend with how PLC does its operations. Namely

• did:rawr should use the whole SHA256*⁶ hash as the method specific ID, not just the first 120 bits.
• Each operation contains only the active keys and a hashlink to the DID document in some format. This is to allow old DID document states to be forgotten. Both for space saving reasons and for privacy reasons*⁷.
• Using ML-DSA from the get-go or perhaps a hybrid signature system*⁸? If we're going to make a new DID method might as well make it PQ secure from the start so we don't have to go through that pain in a year or two.
• Perhaps removing the cap on 5 keys? I'm not set on that to be honest but I also can't think of that much bad stuff one could do with that.

Okay but none of that tells us anything about how we get rid of the central directory. So let's talk about that! First: what does the central directory even do? It has two roles: consensus: deciding which of potentially multiple valid op branches is the canonical one*⁹ and enforcing the time rules around recovery and distribution: providing op chains to clients during resolution. Distribution I'll tackle below but consensus we should tackle at the operation level. My core idea here is to extend the self-authentication properties to also have the structure of the ops themselves, as well as a set of semantic rules, dictate the canonical branch. If the ops themselves have enough info to arrive at a consensus then we don't need a central service to decide it! we don't even need a consensus mechanism like PoW! This is the "read aligned" part, in a sense registries get aligned with each other at "read time". As long as everyone sees the same ops they will see the same identity state.

... So how do we do that? Or rather how do we do that well. It's not hard to make an algorithm that decides a single branch for everyone. Technically any pure function (This means no involving time by the way! We have to abandon the 72h lockout window or any kind of time based lockout window. Time is not verifiable!) from a set of operations to a specific valid chain will do. In practice though we want an algorithm that results in a system that's actually usable in practice and which still retains recovery and safely rotating keys. I'm going to try to motivate each rule here but they're a bit of a case of me taking the PLC rules, tweaking them to not rely on time and then thinking up a bunch of weird bad things that would cause and coming up with rules that protect against that scenario. So it's a bit of a mishmash in certain ways but I think all well founded ... though somewhat likely I missed something bad that can be done and these rules would need to be tweaked more. Getting these right is very important! The ops themselves being what decide the canonical DID document state means that if something is bad or impractical or exploitable at this level the whole concept falls apart. Not needing any if beyond the ops is how did:rawr gets rid of a central registry. We can no afford these rules being wrong. So! This is what I got right now please do try and break this system so we can improve it if need be ... or figure out that this whole plan is doomed to fail who knows. The basic structure here is that we imagine we are a node that has gotten some set of operations. The rules will assume that each operation has been checked for schematic validity and valid signatures. Any ops that fail either of those are automatically not relevant of course. The rest of the rules exist to pull out one specific branch and crucially one specific "active"/"head" operation that holds the identities current state. This process works by starting from the creation op and choosing one of the possible next operations in the chain one after the other until there are no next candidates.

First of all we again steal the same basic rules that PLC uses:'

• Each operation must be signed by a key in its parent operation.
• Keys are listed in ops in order of authority. Keys listed first "hold more power" than keys listed later and can override anything a weaker key did, but weaker keys can't do so the other way round. Any operation signed by a stronger key will always be chosen over a competing operation signed by a weaker key.

This is the core of recoverability. If a malicious, weaker key does something bad a more powerful key can override that. The big difference from PLC here is that there is no time limit on when this can happen because, say it with me now, time is not verifiable. So we can't rely on that. Now we start diverting more from PLC. Unlike in PLC in did:rawr not all keys can perform all operations, they can all update the state of the DID document of course but there are restrictions on how they're allowed to change the key set.

• An operation that removes a key is invalid if signed by a key that is weaker than the key being removed. Keys may always remove themselves however.

This one isn't strictly necessary as any stronger key could always override an operation in which it's being removed. But I think it's worth having for consistencies sake. It makes the operations much more predictable in practice I'd wager. Removing a stronger key wouldn't do much of anything either even if it was allowed. Since said it could just override it's removal. The one slight downside here is that this means that only the strongest key can sig a tombstone operation since a tombstone operation is really just an update operation that removes all the keys and has different name.

Now perhaps the most confusing rule and the one I came up with last is:

• An operation is invalid if it's parent operation is signed by a weaker key.

This seems strange at first but is needed to maintain the key authority system across the whole chain. This rule avoids a situation like in this figure.

The weaker key could maliciously construct op 4' such that it takes precedence over op 4 which would result in op 5 getting invalidated despite being signed by a stronger key. In and of itself this could be considered a non-issue. The stronger key could just override op 3! Problem solved. But again this is to keep the system more consistent and predictable. Especially around tombstone operations. Imagine a tombstone op 6 with op 5 as its parent signed by the strongest key. Now the weaker key is allowed to revive the DID despite it being tombstoned! Which is likely to cause all kinds of downstream issues and it's even somewhat likely that no one holds the private key of the strongest key anymore so this revival might not even be overrideable! Enforcing that weaker keys can't ever override a stronger key, even across multiple operations is the best option here I think. This does mean that invalidating weaker keys ops is a normal thing to do under this scheme which is something to look out for during implementation. Ops don't just get invalidated as a recovery tool it's a standard thing under this scheme.

Lastly:

• If there are still two or more competing operations signed by the same key then:
  1. first any operation that removes said key takes precedence.
  2. lastly as a tie breaker each remaining operations bits are interpreted as a binary number, biggest number wins.

We need a tie breaker of course. Bit comparison is an easy one here. The rule about removing keys is to avoid a case of a compromised key getting removed but the malicious actor just adding themselves back on with a overriding operation. Quite important!

This was the first set of rules but I posted a draft of this post on the roomy discord to gauge interest a bit and look for glaring holes and dman-os on there pointed me towards situations where multiple highest priority operations get signed in a row, then the highest priority key is removed. This would allow a potential future compromise of that key to take over the identity by branching of in the middle of that series of operations effectively overriding it's own removal down the branch. Bad! This situation is very similar to the one from the image above just a special case that can only happen during key removals where that rule doesn't cut it. We will tackle that with a similar "not strictly needed but good to have to force people to make a robust operation chain" rule:

• An operation that removes the key it's signed with must have the operation that added said key as it's parent.

That should give the key no place to overrule it's own removal. Hopefully you can help find any possible remaining things like that (or maybe you found out I added so many rules it's possible to lock out any operations ... hopefully not!). We'd want to squash as much of that kinda risky structure as possible.

One last last thing to consider here is the DID document hashlink. There's no way to check that the pointed to DID document is actually valid unless you have said document. Making the document being valid part of the validity of an operation is untenable in practice I think. So the head operation will represent the cryptographic state of the identity and the newest hashlink to a valid DID document will be the DID document state (which registries will of course need to store and serve), registries should probably refuse to publish a provided operation if the document isn't valid, but resolution should still be able to handle that case. That is it's invalid to create a DID or update it with an invalid documents hashlink, but it's valid for operations like that to exist during resolution*¹⁰. If no valid document is among the operations then a fallback empty (apart from the required id field and such) document will be the result of resolution.

So that's the rules! I think they cover everything we generally care about ... I sure do hope I didn't forget any of the rules I thought up and that these rules do cover all the edge cases. Do say if you can think of something bad that these rules would allow!

Okay so I can resolve if I have the ops I need ... how do I get those?

Operation distribution! The second thing we need to replace to get rid of a central directory. All the rules above exist such that we don't need to trust any given provider of ops to provide us with the right operations, just enough operations to include the whole active chain. That second caveat is much easier to design around.

My idea here is to lean on many years precedent in distributed systems: DHTs.Distributed hash tables are a well used and well trodden way to distribute self verifying data across a peer to peer network. Quite perfect for this use case if you ask me! A DHT that maps each method specific ID to a list of registries (or peers as other DHT based networks would usually call them) that claim to have ops for said ID. This is the "wreath of registries" part (DHTs are often represented as rings of nodes). This is also how we alleviate needing to trust a single peer to have all an identities operations: Multiple peers can be listed, the more the merrier. During resolution you'd gather up all those registries ops for the identity and apply the op rules on the union to arrive at the DID document. Another big part of the idea here is that each identity would have at least one "retaining registry"*¹¹. Each registry in the network has a set of identities that they retain and make sure are always available on the network. Other registries are encouraged (perhaps even required by spec) to also offer ops for some set of identities, perhaps the latest 50 they resolved or something of that sort, but even without other registries offering ops the retaining registry will always ensure that the identity is resolvable and importantly: The owner of the identity can fully own their retaining registry! And moving retaining registry is easy. Just find a new (or another!) server that's willing to take you*¹². Don't even have to update your identity in any way.

DHTs of course aren't all sunshine and rainbows. In some ways DHTs are one of the distributed primitives that are most vulnerable to attack. Namely from sybil attacks and eclipse attacks. Though quite a lot of work has also been put in to design mitigations for these. And we could offer did:rawr level mitigations in the form of options like users providing extra ops from somewhere else during resolution. The main thing to watch out for there is that it could somewhat undercut the idea of being strongly consistent. I don't think that's too bad though.

Now there are lots of option for how to go about that but I think the only sensible ones are

• Use BitTorrents Mainline DHT
• Use the IPFS Amino public DHT
• Use a DHT purpose made for did:rawr

All three of these come with upsides and downsides. Mainline is attractive due to it's size and age. It's battle tested and definitely won't be going away any time soon. Other DID methods like did:dht and other distributed p2p systems like PKARR and iroh are also building on Mainline for these reasons. It's the one I'm leaning towards right now and have largely been designing for in my head. The main downside is the Mainline was designed for finding peers for torrents not for did:rawr, and while BEP 44 exists and is what did:dht builds on, that system doesn't fit our use case here. Using Mainline would mean translating did:rawr identities to a 160 bit key (Almost certainly just taking its SHA1 hash same as the BitTorrent network does for torrents. Maybe just taking the first 160 bits and using that) and using the same peering record system of APIs that Mainline uses for torrents. I don't know how the BitTorrent network would feel about that to be frank? If they'd consider that network abuse this isn't the direction we should take. But I hope and think they'd be fine with it. 160 bits of entropy is enough that I doubt it would have any impact on normal torrent usage.

Using Amino is attractive in that the design of IPFS Kademlia is a lot closer to what a purpose made DHT would probably look like I think. 256 bit keys being the main thing here. But IPFS Kademlia is very much wrapped up in libp2p and Amino is quite a lot smaller than Mainline, on the order of a few hundred times smaller*¹³ in fact. That's quite a lot smaller! From what I can tell IPFS Kademlia also has put less effort into protecting against sybil attacks though seemingly more effort into protecting against eclipse attacks.

Using a purpose made DHT would of course be nice for making the best fit DHT for the job. But it has the major major downside of needing to bootstrap a network from scratch. I don't think this ones viable however much I wish it was.

Baking a cake means I get to eat it right?

So. Easy peasy lemon squeezy now we can finally kill PLC! ... eh probably not. For many reasons. For one there exists too many existing PLC identities for it to be worth it to just abandon it. We will want to support PLC basically forever. As the PLC org is strengthened and more is done to alleviate the power of the central directory the state of PLC will only improve I hope*¹⁴. It's largely good enough for most people ... probably. It's also not like the scheme I present here doesn't have tradeoffs compared to PLC. Resolution is a lot more involved. Most clients can punt that off to some node to resolve for it but in general resolution is slower to do here. Not a lot slower and not so much slower that I think it's worth worrying about. But maybe others do. It's also just inherently less strongly-consistent. There are more things that can go wrong and a DHT is definitely more fragile in some ways than a central server (and a lot less fragile in others: Tradeoffs). I would claim that it can still fall under the designation of strongly-consistent and reliable but there's absolutely more room for stuff to go just a bit wrong somewhere along the line and two clients end up with different views of the same identity or unable to resolve it at all*¹⁵. Again I don't think that's likely to happen. Especially not to a degree that matters, but there's room for argument. Specifically in the context of atproto there's also simply the fact that adding a new blessed DID method will not be easy. Especially not one that is somewhat involved like this*¹⁶. We can absolutely ease the transition (a largely PLC compatible REST API for one), it will still take a while to ever get ... good, wide, proper support. To me it would probably be worth it. A lot more worth it than other possible and proposed additions if you ask me. But again: Room for argument. But yes I would very much like to eat this cake some years down the line ;)

Also oh my I ended up with a lot of footnotes this time ... sorry about that or you're welcome! Whichever you feel for.