I like the ART (Asynchronous Ratcheting Tree) of MLS. It indeed can handle larger scale group chats better than Signal and the like. I've been hunting for a suitable option to decentralize Discord.

There might be imperfect ways to solve the two disadvantages.

Clients have to store decrypted messages when keys become useless as new ones are created. This creates a risk of data loss since the data is stored locally, not decentralized across relays. You can't put the decrypted data on a relay because then the relay could read the messages.

One solution could be taking all your decrypted messages and encrypting them with a new key, one that's not part of the ART. This key would be unique to the user. Then, the user could encrypt all these decrypted messages with that new key and store the encrypted data archive on relays. That way, even if the user loses their device, the encrypted messages would still be on relays, provided they've backed up that single key.

To tackle the other disadvantage, we can piggyback off the solution to the last disadvantage. New users joining the group chat could ask the people who invited them to the group chat for a copy of their encrypted archive of decrypted previous messages. The inviters could delete messages they don't want to share, but the user could request a copy from multiple group chat participants to mitigate this risk. If all older members do this “sharing” for newer members, then the newish members should still be able to share the oldest messages with the latest joining members. nostr:note1qyqzzmz5etpzkwlgsarrkrm0wdrq0ury5lerkay8rswduthpt0pqy9r68d