This has been a perpetual problem we’re trying to solve at our org and while I was on that team I was pushing for the idea of macaroons (we just use JWT and we suffer many headaches because of it).

My suggestion at the time was macaroons with some hierarchal PKI - servers themselves have a macaroon that delegates the permission to sign tokens that meet certain criteria, delegated by us the root organization. So in most situations a typical key hierarchy would look like “root key -> signing servers -> normal services -> bearer token”.

If a token is stateless then this just becomes another caveat and signature - show me that you have the authority to sign this key under this attenuation. Signing server? You should only be signing keys for key services. Data service? You should only be issuing tokens with X caveat. Etc.

If you want revocation though it’s not really stateless - at minimum you have to store a list of revoked tokens until the parent tokens that issued them have expired. In fact you would want to build this as a routine capability on every single level - signing services should rotate their own keys (this is that “clearing caveats” thing) and issue their own revocations, and then the assertion is that any signing from that key is invalid from that moment forward. Similarly, if a browser session wants to refresh its token, it needs to commit to never using the old one again, for the lifespan of the IAM token, and we need to track that for the lifespan of the IAM token. But there is a defined TTL after which you can clear the revocation - and it’s the lifespan of the token used to issue it.

Which is a very Redis-with-cross-region-replication sort of task, or perhaps Postgres for persistent backing. The good news is that there is no logical split-brain, the mere fact that another region issued a revocation is ipso facto all you need to know, when and why it happened is kinda irrelevant to the fact that the token is now revoked.

In other words - signing servers probably have an IAM representing them as an instance, with their own internal secret/private key, which is used to issue their own "bearer token" (public key) which rotates periodically. And when they do a clearing etc they are the authority that signs that the new macaroon is valid. And after some time their own bearer token is revoked (eg after 2pm any signings are invalid) and they rotate to signing with a new bearer token.

If you are going to rely on propagating revocation efficiently it needs to be a routine fact that’s occurring regularly, right? And if you don’t see a revocation from a signing server on some expected timeframe, it is probably in fact a sign of split-brain occurring… you’ve lost a server or a region and it’s in fact dubious to continue accepting that token anyway.

So this sort of leads to an inherent “valid -> historically valid but not for new tokens -> expired” lifecycle that mirrors the IAM/bearer model that clients also use.

This actually closes the "fail open" nature of the revocation - it is impossible to have a "split brain" in the usual sense of revocation not propagating to a region etc, because you know that a signing-server key isn't valid for more than 15 minutes anyway etc. And perhaps you could even add a "parentKey" field and use the bearer token itself as a carrier of these revocations (if the user has a new key and it's validly signed, then SOMEONE must have revoked the old key...) although I haven't rigorously thought that one through.

I am drawn to this revocation idea like a moth to a flame despite knowing how much complexity is going to live in making sure that service doesn’t ever go down or lose data or go split-brain. But if you are doing this “clearing” idea at least you don’t end up with a giant tree of historical caveats and sub-signatures.

On the other hand the reality is that really nobody wants true stateless especially for browser tokens… “log me out everywhere” is practically table stakes and that implies some kind of revocation. And revocation is implicitly state - it’s either valid or revoked, that’s state even if you aren’t mutating the token itself, you’re still mutating the validity of the token. Even if it’s a global “user revoked all tokens at 2pm” it’s still mutating state etc. The idea of revocations lets the “happy path” be stateless, and handle this smaller amount of replication of revocations etc, but otoh it’s still very load-bearing and revocations fail-open. But since the token is limited in time and scope anyway, that’s potentially a valid tradeoff…

But I haven't actually implemented any of this, so, take it for what it's worth.