Device lists can get badly out of sync during federation outages, breaking E2EE

[ara4n]

After the matrix.org breach, there were a lot of UISIs for matrix.org<->elsewhere E2E rooms. Circumstantially we're assuming that this servers ended up with an inconsistent view of the devices present in a room.

Possible causes are:

• If an m.device_list_update EDU gets lost, servers will be stuck with the stale list until the next m.device_list_update from that server, which happens infrequently.
• However, EDUs should not get lost; we should retry m.device_list_updates until we get a 200, so it seems there is a bug here.
• If we see an unrecognised device from a server, should we not re-sync our view of that server's device list anyway?
• In theory we re-sync our view of the device list when we see an m.device_list_update which refers to an unknown previous m.device_list_update. But this might not be working?

(See element-hq/element-web#2996 for the main UISI bug)

[richvdh]

For the record: #4877 was a significant cause of this (people were missing the unique index on device_lists_remote_cache which meant that they ended up ignoring device list updates), but it sounds like other things may have been going on too.

[richvdh]

#5153 looks like another culprit here.

[ara4n]

(have filed #5441 to track an issue i mistook for this one)

[cyphar]

I finally figured out the cause of the above comment and have filed a separate issue for it in #5433.

If we see an unrecognised device from a server, should we not re-sync our view of that server's device list anyway?

Seems to be the most obvious solution, and would fix #5433 too.

[richvdh]

with #5156 done, and #5320 fixing the device_lists_remote_cache index, I think we've fixed most of the known causes of this issue, so I am closing it for now.