Concurrency: how to unwind admission to the group?

[HerbCaudill]

I'm a bit stuck, trying to think of a clean solution to a subtle set of concurrency scenarios.

We deal with concurrency using "strong-remove" principles: a removal action (removing a member from the group, or from an admin role) wins in the case of any conflict.

Example:

1. Alice and Bob are admins
2. Alice and Bob are disconnected
3. Alice removes Bob from the group
4. Concurrently, Bob invites Charlie
5. Alice and Bob reconnect
6. Bob's invitation of Charlie is discarded because Bob was concurrently being removed from the group

That all works fine if Alice and Bob reconnect before Charlie uses the invitation.

The problem arises if between steps (4) and (5), Charlie actually uses the invitation and is admitted to the group while Alice is still disconnected.

If Bob's invitation is discarded, then Charlie's admission to the group also has to be discarded. But there was never a removal action — the resulting group state would show that Charlie never was in the group.

Unfortunately the reality is that Charlie did join the group, and got a full copy of the signature chain.

If Charlie were actively removed from a group, a couple of important things would happen: (1) His client app would be told that he'd been removed, so it can attempt to clean up (e.g. erase their stored copy of the chain); and (2) any keys he had access to would be rotated.

As noted in #25, I can envisage a solution to (1) that involves rethinking the mechanics of discarding invalid actions. But (2) is trickier: Keys can only be rotated by someone who has access to them. So in the process of calculating state from the chain, we'd need a mechanism for flagging keys that need to be rotated, so that the next admin who sees the chain in this state can take care of it. (And, ideally, a way to prevent multiple admins from doing so simultaneously.)

[ept]

I think this situation needs to be handled with some care, as otherwise it could be a vector for Bob to circumvent his removal. For example, when Bob sees that he is being removed, he invites Charlie, who is actually an alias controlled by Bob. Bob can back-date his addition of Charlie to make it concurrent with Alice's removal of Bob. Moreover, once Charlie is admitted to the group, he adds Donna; Donna adds Erin; etc (all of these are aliases controlled by Bob).

In order to prevent Bob from doing this, we need Alice's removal of Bob to not only invalidate Bob's addition of Charlie, but also any chains of user additions starting with Charlie. However, we need to be careful not to remove any users who were added by Bob prior to Alice's removal of Bob, since these users may be long-standing honest group members.

Section 6 of this paper draft outlines a graph algorithm that does this, although the presentation of the algorithm is a bit confusing and I think we could explain it better.

[HerbCaudill]

Thanks, Martin. I've gotten that far (detecting and canceling invitations made directly or indirectly by someone who has concurrently been removed). My current problem is a bit more in-the-weeds, and has to do with cleaning up the mess afterwards. Currently if Charlie joins and then his invitation is annulled because of this kind of conflict, everyone else lives happily ever after, as if Charlie had never joined. But Charlie did join and so he has the signature chain, so his client app should be told to purge it (assuming it's well-behaved); and someone needs to rotate any keys he might have seen.

None of this is insoluble, but it does require me to rethink some things specific to this implementation.

1. Currently when we're calculating the group's state from the chain, any actions that we've invalidated because of concurrency issues are simply discarded, and can't enter into the calculation. Instead, I think I'll need to mark those actions as invalid but still feed them through the reducer, so that e.g. an invalidated JOIN can be treated as a REMOVE.

2. We don't have a way of alerting the group that certain keys need to be rotated. Currently key rotation only happens as part of a conscious REMOVE action by an admin. In the case where someone is removed not by an admin's action but as a mechanical result of the conflict resolution logic, there's not necessarily an admin around to rotate the keys. So we need a completely new mechanism to add an alert to the group's state that certain keys need to be rotated, and to react appropriately to that alert.