How come https://riot.im (Matrix) manages to sync between devices AND have E2E, while also being federated? How come I can use both WhatsApp and Signal on both my computer and phone (and they stay in sync)?
It looks like in [1] that each device registered to a user has a device_key and when an encrypted message is sent, they user's public devices keys are requested and the message is encrypted for each device. New devices can't see old messages.
The message isn't encrypted for each device; the message is encrypted once for the room, as part of a 'session' of messages - and then the key data for that session is shared with the devices who are allowed to read it. Thus you can share old session key data with other devices if you want, meaning that new devices /can/ see old messages, although we're still working through the UX for that. (Currently the only way to do it is by import/export session key data in settings and transferring it between devices).
Thanks—so there's another layer of encryption over the ever changing (Megolm) key that encrypts the room, if I understand this. Looks like I simplified too much.
Sort of. Just to clerify: the first layer (Olm) provides a secure channel between pairs of devices, used mainly to share Megolm encryption state between them.
The second layer (Megolm) encrypts each sent message once per room, using a ratchet described by session key data. The session key data is shared 1:1 between the appropriate devices (past and future) over Olm.