Group chats high level protocol


#1

Hello,
we are revamping the group chat protocol and it would be good to get some feedback before we pull the trigger.

I am going to describe the current idea being implemented so that and hopefully I can get some constructive feedback. This is not related to encryption as this is handled at a layer above, only deals with group membership changes.

basic idea

Basically the idea is that the problem is simply “how to keep a piece of state (group membership) synchronized across peers?”

To solve the problem we can use techniques used before to synchronize state: we will build the state from a set of events that are propagated among peers.

Because there’s no acknowledgement between peers, we don’t know that the message has been delivered, so group membership updates are exchanged with each message.
That is necessary to avoid relaying on the delivery of a single message for communication to happen.

Group membership updates are propagated also among peers who haven’t published updates themselves, for example A publishes an update / B receives the updated, B will propagate A update in the next message (potentially with their own update, if any change in membership originated).

format

The format of the message is:

{
    "chat-id": "string",
     "updates": [ {
        "signature": "signature-containing-chat-id-and-hash-of-events",
        "clock-value": 1, // We need to be able to order events if originating from different peers
        "events": [
          {"type": "name-changed", "name": "chat-name"},
          {"type": "member-added", "member": "public-key"},
          {"type": "admin-added", "member": "public-key"}
        ]
     },
     ]
  }

operations

Upon receiving a message, the peer will:

  1. Validate the signature by building an hash of the events + clock-value + chat-id, to make sure the event cannot be re-used/re-ordered in different chats.
  2. If validation is successful it will merge the events with the local events and apply those events and build a project of the chat membership, which will then be used.
  3. If any change in membership has happened, a system message is produced and displayed in the chat (“Blah has joined”, etc). This messages are local to the peer and they might not be the same among them (out of order messages/messages being dropped), they represent the moment things have changed for the local peer, not for the whole group.

type of events

The type of events are:
name-changed: The name of the chat has been changed
member-added: A member has been added
member-removed: A member has been removed
admin-added: A member has been granted admin privileges
admin-removed: An admin has forfeited admin privileges

rules

We need a set of rules to apply those events so that changes are authorized and the resulting state is the same across peers (conflict free).

  1. Events are totally ordered by clock-values, ties are broken by event-type/public-key
  2. Only admins can issue a name-changed event
  3. Only admins can issue a add-member event
  4. Only admins can issue a add-admin event
  5. Admins can issue a remove-member event on members (not on admins), members can issue a remove-member on themselves.
  6. Only admins can issue a remove-admin event, and they can only remove themselves.
  7. add-admin on a non-existing member, invites the member in the chat has well
  8. An admin cannot forfeit their role if no other admin is in the chat

Basically we want to avoid having power struggles between admins, so once a user is made an admin only they can forfeit willingly their role, at which point they can leave the chat (or be removed by another admin), issuing a remove member on themselves.

Rule 7 is needed to avoid giving power to admin to veto another admin, by issuing a back-dated remove-member after they saw an add-admin event.

observations

currently the whole chat history/membership is naively propagated with each message, that would only be necessary for when new users join, theoretically we can avoid propagating the history when we know that it has been successfully delivered (I can send just the delta). This optimization does not require a protocol change (just a matter of publishing the delta event instead of the history).

Events can be compacted to further optimize and avoid long histories, this can be done once we are sure no out-of-order messages are still in flight. (thinking about using a plural version of each event from the start {type: 'members-added', members: []}

We use public key signatures to authenticate messages, that basically invalidates plausible deniability on group membership, but given that currently all messages are signed and we have no PD, it won’t change the state of things. Adding PD is technically difficult and cumbersome so not the right moment.

extending the protocol

Invalid events are currently silently ignored, so new events can be added and processed only by peers who understand them.

Other options explored

  1. Sending always the current state versioned:
    This is problematic as it’s difficult to resolve conflicts (remove/added of members) and to make it a conflict-free replicated data structure we’d have to use probably OR sets. It was the initial plan, but seems less flexible.
  2. Send commands, do not propagate
    This is what we had before, the trouble is that it does not work well with dropped messages/or out of order messages

Thoughts, ideas, concerns?


#2

For comparison, do we know how others similar protocol are achieving this?

Any shortcomings you can think of?


#3

Sure,
for the mechanics of the protocol (how to keep state synchronized), similar ideas:



https://docs.mongodb.com/manual/core/replica-set-oplog/
https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type ( Operation-based CRDTs)

For group membership rules they are fairly arbitrary and up to us, I feel it seems like sensible options, namely:

  1. Admins can make other people admins
  2. Admins can invite
  3. Admins cannot be removed other then from theselves
  4. Members can leave

The drawbacks/shortcomings of this approach are for example:

  1. Complexity, conceptually is harder than “just send the updated state”, but I think once you grasp it it’s easier to reason about, as a more holistic approach.

  2. Bandwidth cost is higher, but you can make it almost identical to “just send the last update” without changing the protocol (at that point if a message is dropped or not received state won’t be synchronized properly, that would be identical mode of operation as we had before)


#4

I was more thinking about protocols of existing chats :slight_smile:

Do you plan to use CRDTs?


#5

Most of the exists chats protocol literature deals with either non-p2p or non-gossip protcol, so I took inspiration mainly from distributed databases (other than the rules, which are built on top of it).

In terms of CRDTs, the thinking is, that:

  1. Is an operation-based CRDTs, where all the updates are propagated by default (can be changed to propagate only the latest updates without changing the protocol)

  2. The actual data structure is basically a LWW-Element-Set totally ordered by clock-values (the timestamp) with a bias towards inclusion (identical clock-values we apply remove before adds )

Whether is truly a CRDT I won’t be betting any money on it, but given the set of rules listed above the definition:

" In distributed computing, a conflict-free replicated data type ( CRDT ) is a data structure which can be replicated across multiple computers in a network, where the replicas can be updated independently and concurrently without coordination between the replicas, and where it is always mathematically possible to resolve inconsistencies which might result."

should stand valid


#6

With regards to the group admin rules I think what you proposed is sensible. Some other points to consider:

  • If a person is invited to a chat do they get dropped into the group chat or do they need to accept the invitation first? For reference Wechat and I think Telegram requires user to “join” the group whilst Whatsapp just puts the user in the group chat. Personally I’m in favour of having to accept the invite, hopefully on a page that has meta data about the group chat (members, group name, group specific extensions, who invited you).

  • If I understand points 6 and explanation of rule 7 correctly it sounds like the system works whereby there is a founder admin who then can appointment admins. Those admins can then appoint other admins. Admins may remove themselves or any member.

I dont think that will resolve group politics, I’ve seen childish behaviour in group chats of admins having naming wars, rapidly changing the name of the group or one admin invites a member, anther admin removes the member and then the original admin invites them back.

The simplest way to resolve this could be by having a super admin (group founder), the final authority on what happens with a group of admins who have same rights as super admin except that they maybe removed by super admin. A super admin may transfer super admin rights and is unable to leave the group chat with super admin status.

If this was a regular chat company I’d probably be ok with the super admin/admin solution above, but I don’t feel thats the right way according to status principles. I also don’t know what is the right structure for decentralised private chat room governance. Voting comes to mind but I’m not sure because application of governance is a bit of mine field.

Is it possible to have a system whereby the group founder sets up the rules of the group chat before hand? Perhaps a series of templates to choose from? Governance protocols inside of chat inform the quality of the chat and I dont think this should be dictated by us but discovered with users through experimentation.


#7

If a person is invited to a chat do they get dropped into the group chat or do they need to accept the invitation first?

currently it would be just dropped in the chat, we could though just don’t allow messages to be received until the user agrees (sort of muting the chat), without changing the protocol. So effectively for the end-user it would be identical, but messages would be relayed even if the user has not confirmed attendance. If the user actively decline the invitation then other peers are notified and will stop sending messages.

In this way we avoid relaying on a single message (the user accepting the chat invitation) for communication to happen, and the user-flow is exactly as what you described.

Super-admin stuff seems sensible and should be easy enough to accommodate now, having different rules as of now is a bit premature, as I would like to push this out as soon as ready to get feedback, but it is a good idea, so I might leave room for that in the protocol (but can’t guaranteed group chats with different rules will be compatible with older versions)


#8

We could potentially push out 3 versions, if easy to do so as of now:

  1. Super admin
  2. Admins
  3. Everyone an admin

defaulting to 1 possible, and then give the ability to create different policies


#9

Thanks for the detailed description @cammellos!

I really like @Graeme’s idea of policies that can be set by a creator (a.k.a. admin). And also support the idea of releasing an early version to learn about how group chat is used.

For future consideration
Could the model shift between (2) and (3)? For example:

  • A creator starts out as an admin, but as soon as other people join, they join as admin as well.
  • A creator starts out as an admin, sets up a code of conduct and as soon as people join and sign these they become an admin.

Is there any way we can listen for a set of codewords at a topic level? For example:

  • If everyone is an admin and we wouldn’t want chats to be deleted by accident and give equal power to all participants, is it possible to have a system where everyone would need to type or hit DELETE inside or outside of the chat to confirm.

#10

@hester by signin you mean cryptographically sign? in general we tend not to use signatures unless necessary as they prevent plausible deniability. I don’t see the difference between 2 and 3, can a use in 3 join but not sign?

codewords at the topic level would just be protocol messages exchanged, I don’t think we need a text protocol on top of that, for the specific case, a chat is never deleted (same as a public chat), people just stop tuning in, did you have any other user case in mind?

In any case probably what we will do is just push out a version as described above, but let’s keep the conversation going , especially between you and @Graeme so we can iterate on it and try out different things.


#11

Thank you for putting this thread together.

I’m very supportive of introducing MVP group chat features and iterating based on demand and community feedback.

A few thoughts:

  • Does group chat work across multiple devices?
  • Is there a viable path to start with an MVP and update the protocol and features over time whilst ensuring some degree of backward compatibility for basic chat features?
  • I’m very interested in SNT utility in the future. For example a paid members only private group chat. Is there a path to that?

Can’t wait to see this in nightlies asap :slight_smile: Perhaps we can add a specific disclaimer to private group chats when creating or joining? Or some other opt-in measure? It would be great to be using this but also communicate with users that it is experimental.


#12
  1. Currently no, but the system to make it work is there, just dormant so that’s something we can look at

2 & 3) It’s fairly difficult at this stage of the product. If we knew roughly what we wanted, it would be possible to make room for in the protocol. Here the options are quite open (from using SNT to super-admin, to codewords). Granting basic chat functionalities is probably possible, degrading to a previous version if one of the members has a less-recent version

Overall in my opinion think we should revisit the decision to consider nightlies used by end-user, I feel use at your own risk is a better approach (as an example we would have had a couple of days of testing for group chats, and they would not have been disabled by the validation PR as the test team would have likely spotted that). But probably this is for another discussion.


#13

I think if we are looking to get something out as soon as possible then best to start with a group chat framework which is as simple as possible. Something along the lines for our own use case, like everyone been an admin (that way we do not need to build add admin interface) and user are thrown into a chat group (don’t have to create a “join” page).

To add governance features to group chats, off the top of my head would require:

  • Some form of extension so that a user may create group chat governance policies/tools without having to dig into Status core code base.
  • Some form of notification service to let a user know they have been invited.
  • UI to cater to for implementing governance polices for a group chat.Both setting up the policies on creation of group and to executing policies to make a decisions in chat.
  • UI for joining a group chat.

A lot of these governance tools are on chain and will very likely be on some form of side chain in the near future (fingers crossed). Many governance tools depend on some token holding to manage rights or stake value.

A problem I foresee is the decoupling of wallet address/whisper key. It might mean the user loses privacy of their wallet holdings in order to participate in a private group chat which uses crypto-economic incentives/governance.

@Hester I’m keen to take this further, can start with research on existing chat apps and pulling in the smart contract guys for ideas on how to run decentralised governance policies in chat.