synapse
synapse copied to clipboard
element-hq
State reset in #rust:matrix.org (room version 10)
Description
We have just experienced a state reset in the newly upgraded #rust:matrix.org (room version 10). These are all the m.room.join_rules events in the room:
synapse=# SELECT * FROM events WHERE room_id = '!rmJmWEyNJNeBFfzLyh:xiretza.xyz' AND type = 'm.room.join_rules' ORDER BY depth;
topological_ordering | event_id | type | room_id | content | unrecognized_keys | processed | outlier | depth | origin_server_ts | received_ts | sender | contains_url | instance_name | stream_ordering | state_key | rejection_reason
----------------------+----------------------------------------------+-------------------+---------------------------------+---------+-------------------+-----------+---------+-------+------------------+---------------+-----------------------+--------------+---------------+-----------------+-----------+------------------
10 | $pkIC9wCS-hb8wcDJWqoAmrZDr0bQULaqGvNDwtWjhws | m.room.join_rules | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | | | t | f | 10 | 1705313193913 | 1705313194290 | @xiretza:xiretza.xyz | f | master | 5523323 | |
562 | $yRR415bJULHyipJnf1KIyVFvgX0TtDA0_G3NoYHP6p4 | m.room.join_rules | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | | | t | f | 562 | 1705315776319 | 1705315777172 | @ruma_mod:flipdot.org | f | master | 5524042 | |
565 | $N4ca1QfFRzW5T2r207Dc1RbmfE-KNFWl3RfRGbWlOPI | m.room.join_rules | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | | | t | f | 565 | 1705316369263 | 1705316369330 | @xiretza:xiretza.xyz | f | master | 5524086 | |
567 | $wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8 | m.room.join_rules | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | | | t | f | 567 | 1705316380899 | 1705316381730 | @ruma_mod:flipdot.org | f | master | 5524092 | |
571 | $Wr-cCbrzPfxhd5KEx6EpK2Xr9UlKawMjxn-VK2U-tHY | m.room.join_rules | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | | | t | f | 571 | 1705316419468 | 1705316419629 | @xiretza:xiretza.xyz | f | master | 5524105 | |
(5 rows)
-
It was initially created as
public$pkIC9wCS-hb8wcDJWqoAmrZDr0bQULaqGvNDwtWjhws{ "type": "m.room.join_rules", "depth": 10, "hashes": { "sha256": "czinN/Fu7oD/rY5kz5I7oVEpBqPxKfYAgEZTw0t+d+Y" }, "origin": "xiretza.xyz", "sender": "@xiretza:xiretza.xyz", "content": { "join_rule": "public" }, "room_id": "!rmJmWEyNJNeBFfzLyh:xiretza.xyz", "unsigned": { "age_ts": 1705313193913 }, "state_key": "", "signatures": { "xiretza.xyz": { "ed25519:a_xHzI": "py1E8KgeOx0HXSAqxqfMa1cb0k0axHnaqGhBkLlDlmwdRde+1FPKArrCJ7PRTwKT9un8AcziOQCb21r3GiFmDw" } }, "auth_events": [ "$44zEG_KubJAQt2i3dmEuyuLFwOTWLtzsSEZ4j9DCORw", "$L29_VSvHx5ub38vFMKEH5rm992icCBeSqn6HoxGkJ00", "$dpON2f4sQQdkBZsUgCoK0-qXGqgnSU_lC5hD7ypLtRU" ], "prev_events": [ "$AgSJx8nwGtevC3zCSu6XuY_s_SbefGUktxVKq1cfBOg" ], "origin_server_ts": 1705313193913 } -
It was then set private by the overeager moderation bot
@ruma_mod:flipdot.org($yRR415bJULHyipJnf1KIyVFvgX0TtDA0_G3NoYHP6p4) and immediately made public again ($N4ca1QfFRzW5T2r207Dc1RbmfE-KNFWl3RfRGbWlOPI) -
The bot hadn't had enough and made it private again:
$wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8{ "type": "m.room.join_rules", "depth": 567, "hashes": { "sha256": "gUC4IsLZ7+mTdkJsznIBtEY2CaPq933ve39Te7TOr/E" }, "origin": "flipdot.org", "sender": "@ruma_mod:flipdot.org", "content": { "join_rule": "invite" }, "room_id": "!rmJmWEyNJNeBFfzLyh:xiretza.xyz", "unsigned": { "replaces_state": "$N4ca1QfFRzW5T2r207Dc1RbmfE-KNFWl3RfRGbWlOPI" }, "state_key": "", "signatures": { "flipdot.org": { "ed25519:a_gJzK": "CbZhADyF3EksrCv11k2YDJM2kn25P/5ZRXXSQyi0UIEsVvSNzB6FgSNbyvgYnZ3auEAfittla3+b2PzmJqDjCA" } }, "auth_events": [ "$L29_VSvHx5ub38vFMKEH5rm992icCBeSqn6HoxGkJ00", "$MMT8cHk32dWVtcfpT_wuODNeodIDkjx7ipUSGDvKyVU", "$sLcf5E0Jdk8htF2LVXAIRFy849ViT5E1b_Ai-g1OlG4" ], "prev_events": [ "$QUlbCxG_-UrNZLfzEa6Q_Bve-BcpLaCSu1VmW-S6oHQ" ], "origin_server_ts": 1705316380899 } -
The bot was tamed and the room was made public again:
$Wr-cCbrzPfxhd5KEx6EpK2Xr9UlKawMjxn-VK2U-tHY{ "type": "m.room.join_rules", "depth": 571, "hashes": { "sha256": "z8JTidXIVtdNz+i8q45NGbsku5C8fSiU3JLiJ4pXOWg" }, "origin": "xiretza.xyz", "sender": "@xiretza:xiretza.xyz", "content": { "join_rule": "public" }, "room_id": "!rmJmWEyNJNeBFfzLyh:xiretza.xyz", "unsigned": { "age_ts": 1705316419468, "replaces_state": "$wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8" }, "state_key": "", "signatures": { "xiretza.xyz": { "ed25519:a_xHzI": "rFgSIbG/1Ma+fHMhzLFae8A3fQp3B/7eeRWEZ7pff8m+vcZq1wMMQIlyj9t+3tEwhNxLR53z9FWi+x+BesqeDA" } }, "auth_events": [ "$44zEG_KubJAQt2i3dmEuyuLFwOTWLtzsSEZ4j9DCORw", "$L29_VSvHx5ub38vFMKEH5rm992icCBeSqn6HoxGkJ00", "$MMT8cHk32dWVtcfpT_wuODNeodIDkjx7ipUSGDvKyVU" ], "prev_events": [ "$Kx2u0YC1neFX7hK-2mzv2qp_yJuNzZtFBEChlbkzXjE" ], "origin_server_ts": 1705316419468 }
The problem is that the very last state event ($Wr-cCbrzPfxhd5KEx6EpK2Xr9UlKawMjxn-VK2U-tHY) was first accepted, then reset back to $wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8:
synapse=# SELECT * FROM current_state_delta_stream WHERE room_id = '!rmJmWEyNJNeBFfzLyh:xiretza.xyz' AND type = 'm.room.join_rules' ORDER BY stream_id ASC;
stream_id | room_id | type | state_key | event_id | prev_event_id | instance_name
-----------+---------------------------------+-------------------+-----------+----------------------------------------------+----------------------------------------------+---------------
5523316 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | $pkIC9wCS-hb8wcDJWqoAmrZDr0bQULaqGvNDwtWjhws | | master
5524042 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | $yRR415bJULHyipJnf1KIyVFvgX0TtDA0_G3NoYHP6p4 | $pkIC9wCS-hb8wcDJWqoAmrZDr0bQULaqGvNDwtWjhws | master
5524086 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | $N4ca1QfFRzW5T2r207Dc1RbmfE-KNFWl3RfRGbWlOPI | $yRR415bJULHyipJnf1KIyVFvgX0TtDA0_G3NoYHP6p4 | master
5524092 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | $wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8 | $N4ca1QfFRzW5T2r207Dc1RbmfE-KNFWl3RfRGbWlOPI | master
5524105 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | $Wr-cCbrzPfxhd5KEx6EpK2Xr9UlKawMjxn-VK2U-tHY | $wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8 | master
5534237 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | $wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8 | $Wr-cCbrzPfxhd5KEx6EpK2Xr9UlKawMjxn-VK2U-tHY | master
(6 rows)
synapse=# SELECT * FROM current_state_events WHERE room_id = '!rmJmWEyNJNeBFfzLyh:xiretza.xyz' AND type = 'm.room.join_rules';
event_id | room_id | type | state_key | membership | event_stream_ordering
----------------------------------------------+---------------------------------+-------------------+-----------+------------+-----------------------
$wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8 | !rmJmWEyNJNeBFfzLyh:xiretza.xyz | m.room.join_rules | | | 5524092
(1 row)
How can this happen? Why was it first accepted, then reset again?
Steps to reproduce
Unknown. It was fine for a while, then everything fell apart.
Homeserver
xiretza.xyz
Synapse Version
1.98.0
Installation Method
Other (please mention below)
Database
single PostgreSQL server, migrated long ago (before this room existed), no backup restore
Workers
Single process
Platform
Arch Linux x86_64, Hetzner VM
Configuration
Nothing out of the ordinary except for an unrelated appservice (https://github.com/mautrix/telegram)
Relevant log output
Unfortunately it's been rotated out, the only thing I caught was this (an invite that was considered invalid by my HS because the inviting user's join was invalidated by the state reset):
Jan 17 08:38:05 matrix synapse[866918]: synapse.federation.federation_server: [_process_incoming_pdus_in_room_inner-60668] handling received PDU in room !rmJmWEyNJNeBFfzLyh:xiretza.xyz: <FrozenEventV3 event_id=$I4x3asUzJGjzdhCarvVwzgV3S7qboSYC0U_yYML8Roo, type=m.room.member, state_key=@kaplan:matrix.org, outlier=False>
Jan 17 08:38:05 matrix synapse[866918]: synapse.handlers.federation_event: [_process_incoming_pdus_in_room_inner-60668-$I4x3asUzJGjzdhCarvVwzgV3S7qboSYC0U_yYML8Roo] event's auth_events are different to our calculated auth_events. Claimed but not calculated: [<FrozenEventV3 event_id=$43Qzc0IWd7svVtPb2g7kBB1TdLitBdwNANmZECGVxp0, type=m.room.member, state_key=@k900:0upti.me, outlier=False>]. Calculated but not claimed: []
Jan 17 08:38:05 matrix synapse[866918]: synapse.handlers.federation_event: [_process_incoming_pdus_in_room_inner-60668-$I4x3asUzJGjzdhCarvVwzgV3S7qboSYC0U_yYML8Roo] While checking auth of <FrozenEventV3 event_id=$I4x3asUzJGjzdhCarvVwzgV3S7qboSYC0U_yYML8Roo, type=m.room.member, state_key=@kaplan:matrix.org, outlier=False> against room state before the event: 403: @k900:0upti.me not in room !rmJmWEyNJNeBFfzLyh:xiretza.xyz.
The event $I4x3asUzJGjzdhCarvVwzgV3S7qboSYC0U_yYML8Roo:
{
"type": "m.room.member",
"depth": 1497,
"hashes": {
"sha256": "ooRpsb1zy/s0gIMbZRYOn91rzpMezeg8MVqQJUaZxbw"
},
"origin": "0upti.me",
"sender": "@k900:0upti.me",
"content": {
"is_direct": false,
"membership": "invite"
},
"room_id": "!rmJmWEyNJNeBFfzLyh:xiretza.xyz",
"unsigned": {
},
"state_key": "@kaplan:matrix.org",
"signatures": {
"0upti.me": {
"ed25519:qTw53QCu": "kUPI+Enir37bq5mDxEGiVpcOXSucAvB5r14cLKBW4ucWv6o8bbrX87WcscDHeutn00xLFu4DFxfIKs1t/IoaCw"
},
"matrix.org": {
"ed25519:a_RXGa": "6sfhtQSolw369A27VChah0SahTh6kD4xRL1j+alIQeI4QOiCjY0w/DHlEp/TuDlA5hiCrFz1ZrWKICPMRraoCg"
}
},
"auth_events": [
"$43Qzc0IWd7svVtPb2g7kBB1TdLitBdwNANmZECGVxp0",
"$MMT8cHk32dWVtcfpT_wuODNeodIDkjx7ipUSGDvKyVU",
"$L29_VSvHx5ub38vFMKEH5rm992icCBeSqn6HoxGkJ00",
"$wZf26aec3qefZJTf88ggSS9nxEDY3V1pZeWhfrSzMF8"
],
"prev_events": [
"$3AcINsCNEvEW6TEgbIa8kdVIRorNItfJnW-iEnsHwWw"
],
"origin_server_ts": 1705480685022
}
Anything else that would be useful to know?
No response
Since we haven't found any way to debug this, and opening an issue here is probably akin to shouting into the void, we've tombstoned the room yet again and made a new one. The old one is still there and still broken, if anyone has any suggestions for debugging, I'm all ears (ping @xiretza:xiretza.xyz).
we've tombstoned the room yet again and made a new one
I'm afraid this was probably the right/pragmatic move, but sorry for the trouble all the same. Staffing is very tricky at the moment.
The "new" room (!ifW4td0it0scmZpEM6:computer.surgery) just exploded again and has been upgraded to !3zRfld5APWSQIwNZWQ:computer.surgery. It lasted over a year!
I suspect that Matrix state resolution is fundamentally impossible to implement correctly. Here is what I believe to be a proof:
- In the sence of PACELC, Matrix is an PA/EL system: writes can succeed without a majority of nodes confirming them. This is necessary to prevent denial of service attacks.
- Therefore, there is no total order of messages.
- In an order-free system, events be commutative, associative, and idempotent to avoid data loss.
- An access control restriction that prevents someone from joining a room (when they were previously allowed to join) fundamentally must not commute with them joining that room:
- If the person tries joins the room while they are still able to join, they should be part of the final room.
- If the person tries joins the room after they are no longer allowed to join, they should not be part of the final room.
- The requirements (3) and (4) contradict each other.
Does this analysis include matrix' notion of "soft failed" events, which is decided per-server and not necessarily the same on all servers?
No, but that would make things potentially even worse and cause divergence between servers.
I’m not aware of a good solution here. The only options I can think of all have serious drawbacks:
- Have a single server (or cluster of servers) that enforces a total order of messages and through which all events must flow. This allows supporting all of the features of a traditional centralized system, but means that if the server goes down, the room goes down with it.
- Adjust the set of supported events to ensure that they all commute with each other and do not erase existing state. This would mean losing features, such as the ability to make a public room private. Room access controls would only be allowed to become monotonically less restrictive in this model. I suspect this is incompatible with being able to effectively moderate a room.
- Accept that users’ messages can be clobbered by events, such as rooms being made private, that happened a potentially unbounded time in the past.
@DemiMarie You touch on a lot of the core properties of the federation protocol which I've been working on over the past few months. The quick answer is Matrix does:
Accept that users’ messages can be clobbered by events, such as rooms being made private, that happened a potentially unbounded time in the past.
When we talk about "state resets" though, we aren't talking about this. There exists scenarios where state can reset which are expected to occur in the protocol, as you allude to. When we talk about "state resets" in the context of this issue, we mean unexpected cases where events have caused state to reset e.g changing your display name should not cause the room state to reset, but banning a user in the past could cause state to reset if that user set the room name, it will need to be rolled back.
I've been playing around with the idea of removing sources of non-monotonicity as you allude to:
Adjust the set of supported events to ensure that they all commute with each other and do not erase existing state. This would mean losing features, such as the ability to make a public room private. Room access controls would only be allowed to become monotonically less restrictive in this model. I suspect this is incompatible with being able to effectively moderate a room.
..and for the vast majority of rooms on the network this would actually be fine, because few rooms actually exhibit non-monotonic behaviour (PL demotions, bans, join rules becoming more restrictive, etc). However, a significant subset of large public rooms do exhibit non-monotonicity so this can't be a general solution (although you can imagine a world where if room upgrades were seamless then any non-monotonic action could cause a new room to be created, which creates its own problems but does provide a synchronisation point for other servers). It's worth noting that in order to introduce sources of non-monotonicity you are required to have privileged access (to be an admin/mod) in the room.
No, but that would make things potentially even worse and cause divergence between servers.
Soft-failed events have no impact on state resolution, only on the delivery of the event to client's timelines, precisely for this reason.
For more information from an academic angle:
- Jacob, F., Beer, C., Henze, N., Hartenstein, H. (2020). Analysis of the Matrix Event Graph Replicated Data Type. arXiv preprint arXiv:2011.06488.
- Jacob, F., Hartenstein, H. (2024). To the Best of Knowledge and Belief: On Eventually Consistent Access Control. kit.edu
@DemiMarie You touch on a lot of the core properties of the federation protocol which I've been working on over the past few months. The quick answer is Matrix does:
Accept that users’ messages can be clobbered by events, such as rooms being made private, that happened a potentially unbounded time in the past.
When we talk about "state resets" though, we aren't talking about this. There exists scenarios where state can reset which are expected to occur in the protocol, as you allude to. When we talk about "state resets" in the context of this issue, we mean unexpected cases where events have caused state to reset e.g changing your display name should not cause the room state to reset, but banning a user in the past could cause state to reset if that user set the room name, it will need to be rolled back.
Would it make sense to have an option to sacrifice decentralization (but not federation) in exchange for much simpler and easier-to-reason-about behavior? That would be:
Have a single server (or cluster of servers) that enforces a total order of messages and through which all events must flow. This allows supporting all of the features of a traditional centralized system, but means that if the server goes down, the room goes down with it.
and I suspect it might well be chosen by rooms that are often under attack, which are the ones most likely to need non-monotonic actions. RIght now, any such room is very likely to run into bugs like this, and may exhibit extremely confusing behavior even if it does not. It also is the only reasonable way I can think of to perform fail-closed synchronous moderation, such as holding messages until a bot has scanned them.
You're absolutely right. There are proposals in the works that come close to sacrificing aspects of decentralisation so there can be a gatekeeper to scan messages for spam.
That being said, Matrix's fundamental novelty is that you do not need to talk to any other server in order to communicate in a room, so it's highly unlikely we would sacrifice decentralisation in general. Where to draw the line and how to opt-in to this is an outstanding problem area.
I think that decentralization is great for end-to-end encrypted communication between mutually trusting users. In this case, the servers can’t do any reasonable moderation anyway, as all of the data is encrypted. Metadata currently isn’t encrypted but should be.
For large public rooms, moderation is far more important, and the price of decentralization may well be too much to pay. Not having a linearizable history is a huge loss in this case, especially because my understanding is that Matrix’s competitors have it. Furthermore, being able to effectively moderate a room (including with non-monotonic actions) is a safety requirement.
That being said, Matrix's fundamental novelty is that you do not need to talk to any other server in order to communicate in a room, so it's highly unlikely we would sacrifice decentralisation in general. Where to draw the line and how to opt-in to this is an outstanding problem area.
4 months later.. I'm still working on this, and I think it is technically feasible to strike the right balance.
The key insight in the intervening months is to make ordering lazy. Servers must be allowed to send events when fully disconnected from the network to preserve the partition tolerance property, but their final order is pending until some "ordering server" confirms its final resting place in the execution order. The ordering server may very well be the creator's server, or some other dedicated server with good uptime, but the critical property is that if this server dies, the room continues to exist and function, it's just that events sent during this time are no longer final. A room with a permanently absent ordering server woud thus exist like all Matrix rooms do today, so it's hardly a deal breaker should the creator disappear. Critically, public rooms are moderated, increasing the chance of an authorised server being around to provide ordering.
A lot needs to happen before such a system can come into play on the Matrix network, if we even want to go down this route, but that's my general thinking at this time.
For public rooms you probably want to reject writes if the authoritative entities (human moderators, mod bots, ordering servers, policy servers, whatever) are unavailable, otherwise you have fail-open moderation which is not great. At that point, you might as well centralize writes to a single server so that you don't have to deal with DAG problems for no reason. Reads could still be permitted while the write server is down via read replicas on other servers participating in the room. Getting rid of the DAG would also make it possible to fully delete spam too which would be nice, instead of only being able to redact its content while still taking space in the DAG forever. Adding an ordering server concept to Matrix is basically this but with worse moderation properties and vastly more complicated implementation.
For private rooms, I think E2EE on top of a delta-state CRDT where permissions (e.g. PL, membership, etc.) can only be granted but never revoked is probably sufficient. Making it impossible to revoke permissions more or less obviates the need for state resolution since the merging function is to simply union everything. Private rooms are typically small enough so that it's easy to get social consensus on which replacement room to move to in case permissions do need to be revoked.
I think your proposal is reasonable but your reasoning makes too many leaps to come to your conclusion.
Firstly, not all rooms have the same moderation concerns, even public rooms if used on a permissioned network (e.g basically every company and org not publicly federating using Matrix). Basing the protocol around perceived moderation concerns don't accurately model all the ways the protocol is used in practice. Even if this were true, it's a huge leap to go from "you must talk to an authoritative entity" to "centralise authoritative entities onto a single entity". It completely skips the fact that you may still be able to talk to some but not all authoritative entities. Centralising destroys partition tolerance which is a key property of Matrix. If you have a group of servers on the Moon and a group of servers on Earth and the link goes down, you really don't want users to be unable to communicate just because the authoritative entity was on the wrong side of the link.
Secondly, you don't need to remove the DAG to get rid of spam, you just need a way to compact it. Your statement is like me saying that no one should use any append only data structure for the same reason, neglecting that the actual problem is knowing if that data is actually needed in the future or not. In other words, finality.
Adding an ordering server concept to Matrix is basically this but with worse moderation properties and vastly more complicated implementation.
This is unhelpful FUD. You can't possibly know this because you don't know the full proposal because I don't even know the full proposal yet.
For private rooms, yes that's an option, and is something the Berty folks choose to do. If you remove all forms of non monotonicity from your protocol then as Demi eloquently mentioned:
Adjust the set of supported events to ensure that they all commute with each other and do not erase existing state. This would mean losing features, such as the ability to make a public room private. Room access controls would only be allowed to become monotonically less restrictive in this model. I suspect this is incompatible with being able to effectively moderate a room.
The majority of private rooms on the current network do not exhibit non monotonic changes in PL events. However, when non monotonicity is required it's often for critical reasons. This also assumes public/private rooms are immutable properties of the room, which I think is sensible but isn't a property that we currently have in the protocol. Notably, public rooms temporarily get made private during spam waves.
Adding an ordering server concept to Matrix is basically this but with worse moderation properties and vastly more complicated implementation.
This is unhelpful FUD. You can't possibly know this because you don't know the full proposal because I don't even know the full proposal yet.
I mean it seemed to me like the proposal would be "take Matrix's existing data structure and algorithm, and bolt on a new algorithm" which seems straightforwardly more complicated to implement. You can't get rid of stateres if you want "the final order [to be] pending until some 'ordering server' confirms its final resting place", because that means you still need a way to determine the pending order, which means you need stateres. It also seems straightforwardly weaker than my proposal in terms of moderation because of this "pending" state and its afforded partition tolerance.
Secondly, you don't need to remove the DAG to get rid of spam, you just need a way to compact it.
And how do you propose to do that?
Notably, public rooms temporarily get made private during spam waves.
I wouldn't phrase it this way, I would say this room is still a public room but that it has temporarily disabled joining.
it's a huge leap to go from "you must talk to an authoritative entity" to "centralise authoritative entities onto a single entity".
You're right. For some reason when I wrote that comment I didn't think to elaborate on that part. Basically the way I see the moderation problem is that you can have partition tolerance XOR strong moderation. This is because partition tolerance means moderation actions on one side of a partition will not take effect on the other side(s) of the partition. I do think it's possible to do better availability-wise than having literally a single write node though, for example, a room could have a set of trusted nodes which do consensus, and as long as some subset of those nodes can reach consensus, writes can be accepted.
Firstly, not all rooms have the same moderation concerns
Alright, so maybe there are three types of rooms:
- Public rooms where writes should fail if authorities are unavailable.
- Public rooms where writes should succeed if authorities are unavailable.
- Private rooms.
My personal conclusions are:
- Type 1 rooms might be best served by a protocol where a set of consensus-doing trusted servers determine whether writes are accepted. Disadvantage is that the set of trusted servers will typically be small and so won't have maximal partition tolerance. Advantages are that you can have strong moderation and don't need to treat room state/timeline events as a DAG, which simplifies how ordering is determined, simplifies implementation in general, and makes it trivial to fully delete abusive events.
- Type 2 rooms might be best served by a delta-state CRDT protocol with an extra ordering facility bolted on (such as in your proposal). Disadvantage is that moderation can't be as strong due to the added partition tolerance, that it will likely be more complicated than current Matrix to implement, and that it will still be possible to have state splits within the set of pending events. Advantage is maximal partition tolerance.
- Type 3 rooms might be best served by a delta-state CRDT protocol with a purely monotonic merging function. Disadvantages are that permissions (e.g. PL, membership) cannot be revoked without replacing the room. Advantages are that it will never experience state splits and that it has maximal partition tolerance.
(Also, assuming a protocol and implementations that work reliably (big assumption), I don't see a reason to have E2EE public rooms (either type) or non-E2EE private rooms.)
However, when non monotonicity is required it's often for critical reasons.
I'd rephrase this to "when permissions are required to be revoked in private rooms, it's often for critical reasons", and I'd agree with that. But a monotonic merging function doesn't preclude this really, you can still replace the room to have the effect of revoking permissions.
it's a huge leap to go from "you must talk to an authoritative entity" to "centralise authoritative entities onto a single entity".
You're right. For some reason when I wrote that comment I didn't think to elaborate on that part. Basically the way I see the moderation problem is that you can have partition tolerance XOR strong moderation. This is because partition tolerance means moderation actions on one side of a partition will not take effect on the other side(s) of the partition. I do think it's possible to do better availability-wise than having literally a single write node though, for example, a room could have a set of trusted nodes which do consensus, and as long as some subset of those nodes can reach consensus, writes can be accepted.
Do you mean availability XOR strong moderation? A distributed system can’t avoid partitions, but it can choose how it reacts to them.
Would it be sufficient to require that there is at least one active moderator for a partition to accept writes? If strong moderation requires that a system be PC/EC (in the sense of PACELC), this means that all writes must be funneled through a set of mutually trusting nodes. This would be a very radical change to the Matrix protocol: instead of federation being mostly peer-to-peer, a room configured to be PC/EC would be a centralized chat system with federated identity. The only systems I know of that achieve both strong consistency and decentralization are public blockchains, and the mechanisms by which they achieve this are both prohibitively expensive and come with restrictions (such as being append-only) that are just as catastrophic from a moderation perspective.
I also consider policy servers to be abandoning decentralization: all events must be funneled through a policy server, and the service providing it is a single point of failure for the entire room. Given that Matrix was forced to introduce policy servers, I think it is reasonable to conclude that decentralization and effective moderation are mutually incompatible. Since effective moderation is an absolute requirement in many scenarios for both legal and safety reasons, decentralization will need to be sacrified.
Do you mean availability XOR strong moderation?
Oops, yes.
Would it be sufficient to require that there is at least one active moderator for a partition to accept writes?
For type 2 rooms, yes. For type 1 rooms, no, because there's no way to differentiate between active/inactive moderators and network partitions.
This would be a very radical change to the Matrix protocol
Yes, although I think such a change is very much warranted, and there would still be two other room types that remain more current-Matrix-shaped.