The more I think about these things, the more I distrust cloud providers, and want my own hardware.
Do you really trust these companies enough to hand them the keys to all your data? Is there really any way to provide secrets to your app without trusting the hosting provider?
If your keys leaked, you'd probably have to assume you lost all of the data up to that point. To secure the data going forward, you'd need to generate a second key per user for all of the future data. Well, and hopefully shore up the security problems!
I agree, though, that an immutable ledger like this complicates things in a way that you-shouldn't-mutate-but-can datastores do not.
I'm currently working on this problem in application to blockchains. The plan ATM is to implement cryptographic snapshots of the data, where the old transactions are erased but their proof is available.