Support for Reactions / Aggregations

[matrixbot]

Documentation: https://docs.google.com/document/d/1CnNbYSSea0KcyhEI6-rB8R8u6DCZyZv-Pv4hhoXJHSE/edit
Author: @pik
Shepherd: @ara4n
Date: 25/12/2016
See also: matrix-org/synapse#1633

Currently we have no good way to model 'voting' metadata about messages (e.g. FB likes or Reddit/Slashcode up/downvotes). The best we can do is to synchronise around 'update' messages in the v2 CS-API - this could get very noisy and heavyweight for a typical FB-style "1M likes!" scenario.

We could help mitigate this by coalescing certain updates into the original event - both for server->client and server->server synchronisation. However, this can never work in an E2E crypto world (unless we don't encrypt the vote, which doesn't seem great). Worth noting that an E2E room with lots of participants becomes increasingly insecure to the point that it might as well not be E2E, as the room is only as safe as the security of the clients connected to it, so we might be able to sidestep this in practice somehow. Alternatively, we could try to fix the scalability implications of syncing all these 'like' events by somehow QoSing them: federating them at lower priority; having them semi-ephemeral and parented only to the event they describe to avoid disrupting the main message graph; putting them in a separate message graph; etc.

In a non-e2e world, we could coalesce... I believe having a HS say "150 users Liked this message" is no more open to abuse than trusting a HS to accurately report /any/ message from its users. But then we need a mechanism to de-coalesce on demand (e.g. to actually start paginating through the list of 1M users who hit 'Like').

(Imported from https://matrix.org/jira/browse/SPEC-135)

(Reported by @ara4n)

[matrixbot]

Jira watchers: @ara4n

[matrixbot]

(might be also good to be able to filter on vote count, too, to implement reddit/slashdot style thresholding)

-- @ara4n

[mlopezr]

I would really like this feature implemented.

A trivial solution compatible with end-to-end encryption would be to send an event with a special msgtype and a reference to the "liked" event_id:

{
  "msgtype": "m.reaction",
  "ref_event_id": "$1474582900147371glwtU:matrix.org",
  "body": "+1"
}

One downside is that retrieving all reactions requires parsing all the events that are more recent. This would be inefficient for very old messages. In those situations clients can load all reactions only if explicitly requested by the user.

Do you see any major drawback with this approach?

[mlopezr]

Alternatively, a new client-server API method could be added:

PUT /_matrix/client/r0/rooms/{roomId}/reaction/{refEventId}/{txnId}

{
  "msgtype": "m.reaction",
  "body": "+1"
}

Since the refEventId is in the URL and not in the payload, it can be seen by the server even with E2E, and used to create an index of the reactions to each event that would be sent along with each event when syncing.

This still requires that the server sends reaction updates in order for clients to update the UI with new reactions to messages that were already synced.

[gonight]

The idea of having 'reaction' traffic rank below normal federation traffic seems like a pretty decent solution to the "5M+ Likes" problem, if there was a way to have clients/HS de-prioritize reactions/votes in general and/or do some sort of bulk-packaging/delayed processing that could maybe help the reaction/vote system scale?

[richvdh]

@pik offered some proposals which might help implement this: matrix-org/synapse#1633

[ara4n]

So one way of solving the "5M+ Likes" problem could be to use interactive ZK proofs to avoid servers having to replicate all the reaction objects between each other. It could go something like this:

• Each server tracks all the reactions of its set of users
• Reactions to a given message originating from users on a given server are arranged into a genuine bushy merkle tree (say, each node has 16 children). We could conceivably use the normal federation DAG for this, although we really need to maintain and share the root node of the merkle tree of reaction events (and the roots of all of the branches within that tree).
• When federating, the origin server sends a selection of reaction events to the other servers, gapping to avoid too much traffic. It includes some unsigned metadata on the reactions to assert the current aggregated value of its own reactions.
• Other servers can choose to blindly trust these assertions... or query them, via a new federation API, which queries the details of a set of randomly selected events in the reaction tree in question. The server reports the merkle hashes for the nodes which make up the branches of the randomly selected events, hopefully proving that the hashes are consistent with the root hash of the tree, and that the server really can provide individual nodes which can be proved to be consistent with the hashing information the server has already exposed. (This obviously needs to be made less handwavey).
• Relatively few queries should be needed to have confidence that the origin server does actually have the reaction events it claims to have, and these queries can be processed in parallel.
• Meanwhile the servers can still slowly trickle the reaction events between each other, to avoid centralisation and individual HSes being entirely responsible for asserting reaction information.

Alternatively, one could go the whole hog and use ZK-SNARKs or even ZK-STARKs, but I'm not convinced the ability to provide succinct non-interactive proofs is that useful here, given Matrix is already interactive by default, and the simpler merkle-tree model is much easier to reason about - plus we have all the code hanging around already.