Messages is end-to-end encrypted. The key is stored in iCloud backups if they’re enabled (and if I recall correctly the messages on your device are backed up as part of an iCloud backup as well), but you can turn those backups off.
> [1]For Messages in iCloud, if you have iCloud Backup turned on, your backup includes a copy of the key protecting your messages. This ensures you can recover your messages if you lose access to your Keychain and your trusted devices. When you turn off iCloud Backup, a new key is generated on your device to protect future messages and isn't stored by Apple.
> If you forget your password or device passcode, iCloud Data Recovery Service can help you decrypt your data so you can regain access to your photos, notes, documents, device backups, and more. Data types that are protected by end-to-end encryption—such as your Keychain, Messages, Screen Time, and Health data—are not accessible via iCloud Data Recovery Service. Your device passcodes, which only you know, are required to decrypt and access them. Only you can access this information, and only on devices where you're signed in to iCloud.
> [1]For Messages in iCloud, if you have iCloud Backup turned on, your backup includes a copy of the key protecting your messages. This ensures you can recover your messages if you lose access to your Keychain and your trusted devices. When you turn off iCloud Backup, a new key is generated on your device to protect future messages and isn't stored by Apple.
> If you forget your password or device passcode, iCloud Data Recovery Service can help you decrypt your data so you can regain access to your photos, notes, documents, device backups, and more. Data types that are protected by end-to-end encryption—such as your Keychain, Messages, Screen Time, and Health data—are not accessible via iCloud Data Recovery Service. Your device passcodes, which only you know, are required to decrypt and access them. Only you can access this information, and only on devices where you're signed in to iCloud.
[1] https://support.apple.com/en-us/HT202303