old events retrieved via get_missing_events can be incorrectly rejected and break room state

[richvdh]

matrix.org received an event $b3jshYEAbEzWDq59fBAH5uAgahkixRzH7siauucqDYU (depth 64), one of whose prev_events $B85oucGHA3dkCUZRFM8Oph3kerpMX_EBnVjqcb2KH24 (depth 63) was unknown (because it had been created on a third server which didn't yet know about matrix.org's join, incidentally, though I don't think that is relevant).

matrix.org therefore called get_missing_events to fetch missing events. The implementation of get_missing_events is simply to do a breadth-first walk of the prev_events chain until the limit (of 10 events) is reached. (The algorithm stops if it encounters an event mentioned in earliest_events in the request, but that's not relevant here.) In this case, we encountered an event $hXn_OY2NWvBllJh8J1YM1bG6m3JPkEy9SHqPEDa9v4s (depth 61) which had a prev_event link to $sjhYxI2p-zzfjYcG-RpYZdSxxnng78X-MSaoVBacB5E (depth 42), so the results included three events from that area of the dag, the earliest of which was $uNwva8-n5XSYELKA2B4EptNuBakditcVgg5u1q2pcBQ (depth 40).

Now, I think that at this point, the room's min_depth was greater than 42, since this was the first PDU received after matrix.org's join (at depth 56). So the received events were flagged as outliers at https://github.com/matrix-org/synapse/blob/v1.0.0/synapse/handlers/federation.py#L239.

We then call _process_received_pdu (normally with state=None), which in turn calls _handle_new_event (NB with no auth_events param), which then calls prep_event.

_prep_event first attempts to calculate the auth_events (since none were passed in), however it does this based on the state at the event and compute_event_context assumes (probably correctly) that we do not have the state for an outlier. We therefore end up with an empty auth_events, so auth fails immediately because that's nonsense.

So I think the essence of the problem here is that it's an outlier which arrives via a different code path to normal, and it just generally not being handled correctly. But oh boy, this code is an impenetrable, poorly-commented mess.