Private Message and Groups

To sum up

What I like in the Private Messages today is:

They are part of the main feed. So they are replicated without disclosing the recipients by non-recipients followers.
A node that replicates it is not responsible of what it contains.
Forward secrecy
A node that is not a recipient of the message can discover who are the recipients. (actually with a small modif, we could prevent a recipient to discover the other recipients)

What I don't like mainly, as yet mention by @staltz , is the cost in CPU. Each node need to try to decrypt each private message whatever it is a recipient of not. The second point being that it does not cope with the 'blobs' encryption, which means that we need a second mechanism if we want day to support it.

From what I understood of Private Group, my main concerns are:

subfeeds usage. That implies that somewhat you have to disclose that you are part of a group by following the subfeeds. We leak appartenance to and ownerships of the group.
single key for all members. I think it makes the management of groups over complex. I think the Signal approach based on sender keys with sender periodic renew based on group changes make things easier.

Some ideas to improve:

Private One to One conversation:

Using the principles of double Rachet algorithm of Signal and of Sender key encryption.

When A start a conversation with B, it sends the parameter of the key generation Rachet algorithm of the future encryption keys and conversation tags. They are encrypted with B public key like today for Private Message. Let call it a Private Conversation Anchor.

Then for each message it sends in clear the next conversation tag and the payload encrypted with the next encryption key according to 2 parallel Rachet sequences. Periodically, it "restarts" the session by resending new random parameters via a new Private Conversation Anchor.

That mean that a followers of A need only to try decrypt the Private Conversation Anchor messages. When B decrypts a Private Conversation Anchor for which he is the recipient, it can initiate the Rachet sequence on its side. After, all it need to check of the following messages is the presence of the next expected conversation tag which is in clear. If is matching, then it decrypts the payload with the current key and can compute the next key and conversation tag.

Note 1: this unidirectional. A to B. If B answer to A, it needs to establish a conversation channel the same way starting with a Private Conversation Anchor to A Note 2: A can send the same Private Conversation Anchor message parameters to C, D, E, F, etc. and all will be able to detect and decrypt the messages encrypted by A using the corresponding Rachet sequence. None of them can discover the others. When A want to remove D, it just need to re-initiate with new Private Conversation Anchor and D will not even know that he was removed from the conversation. Note 3: when adding a C to the channel, A can choose to either choose to send the initial parameters and a backlink to the first private message so that C can read past messages, or only the ongoing parameters, so that C can only read subsequent messages.

I think this can simply resolve the scalability issue that would be cause by Private Message today if they were used extensively.

Private Groups: based on that Private one way channel with multiple recipients

Let's start with one Admin.

As the group creator, I start a Private one way channel and emit a Private Conversation Anchor for all members. The first message is then the set of members.

The members can accept the invitation by creating their own Private one way channel and emit Private Conversation Anchor for all members.

Adding members: is straight forward, Admin notifies existing members via its private channel to them, and each existing members emit an anchor for the new one.

Removing members: is not much more complex. Admin send a new Anchor for all remaining members, then send a message to notify them of the member removed. In reaction, each remaining members remit an anchor for the remaining members.

The main problem is of course for large groups, that implies at initiation N^2 anchors, at addition of member N anchors and for removal N^2 anchors.

One way to resolve for large groups and make it more log(n) would be a kind of gossip tree transmissions of the new anchor parameters with a FCC mechanism to ensure an eventual consistency. But that is more complex and maybe for later.

With more admins

One possible way would be to use a OR-Set CRDT to manage jointly the membership. Note: I have not yet investigated all possible scenarios and there is probably some drawbacks when admins are trying to removing then each others. It may aims at the need to create some additional fallback mechanism that "designate" a new admin from the member based on some static rule (for instance the smallest identity among the members using memcmp comparison)

ssbc / ssb2-discussion-forum