The Depty Admin Test

The depty admin test assesses if an authorization scheme is decentralized, by seeing if a "Depty Admin" named Alice can help Bob:

1. Bob creates a project.
2. Bob authorizes Alice to add other collaborators to Bob's project.
3. Alice authorizes Zach as a collaborator.
4. Can Zach authenticate Alice's authorization by communicating only with Alice?

If the answer is yes, the authorization scheme is decentralied.

In this case "project" is a stand-in for any access-controlled resource. The test is designed to both highlight a common use case, and deal purely in changes to authorization. How an authorization scheme handles changes to the resource itself can be distracting when assessing a scheme.

latency and liveness requirements are two of the biggest sources of slowness in a distributed system. As such: sending fewer, smaller messages and requiring fewer actors to be online at the same time improves improves the overall performance & scaling characteristics of the system.

A decentralized authorization scheme should be able to accomplish the depty admin test with two messages passed, and only require the liveness of two actors at a given time. It should also be able to recurse, making Zach an admin who can in turn help Alice add more colloaborators.

Zach is "only" allowed to communicate with alice for the purpose of proving the system is decentralized. In practice all three actors may be communicating frequently, but forcing all authorization to move through the depty admin removes any implicit star-topology requirements from the network. If Zach were allowed to communicate with, say anyone but Bob, the answer would be easy: use a central coordinating server. This is the exact approach tools like Keybase Teams use.

Local First Auth

Local First Auth (LFA for short) is an authorization scheme based heavily on Keybase Teams. The key contribution of Local First Auth is moving the Keybase sigchain approach into a decentralized context.

Sigchains

From the LFA Sigchain readme:

A signature chain or "sigchain" is a directed acyclic graph of links. Each link:

• is cryptographically signed by the author; and
• includes a hash of the parent link.

This means that the chain is append-only: Existing nodes can’t be modified, reordered, or removed without causing the hash and signature checks to fail.

A signature chain is just data and can be stored as JSON. It consists of a hash table of the links themselves, plus a pointer to the root (the “founding” link added when the chain was created) and the head (the most recent link we know about).

In Keybase the sigchain is govenered by a central server. Sigchains on their own fail the Depty admin test because Zach needs to communicate with keybase servers to authenticate Alice's authorization.

LFA contributes a conflict resolution mechanism to sigchains, allowing multiple disparate peers to synchronize concurrent writes to the same chain, passing the depty admin test in the process.

Sigchains have some nice characteristics:

• All members have the full collaborator "state tree", making it easier to know the full set of actors involved in a team
• Authorization events achieve "happened before" partial ordering. Sigchains can show who was invited, joined, and was removed in logical time

Sigchains have some not-so-nice characteristics:

• Unbounded growth. All replicas must keep the entire chain on hand, meaning the longer a chain is used, the slower it becomes. All efforts to mitigate growth problems boil down to a form of compression, as evidenced by Keybase Teams Sigchain V2 and CRDT Compression in Automerge
• highly divergent branches. Using a merge strategy creates problems where one collaborator in the team doesn't sync with others for a long time (large number of sigchain operations), and then tries to synchronize their own set of local changes, which may conflict. resolving these changes on each replica must be performed deterministically, and may require re-writing large parts of the authorization chain as part of the conflict resolution process. The reason for such large edits comes from humans being out of sync for a while, but the "slow sync" is a result of requiring each replica sync all operations in the sigchain