You can use cryptoshredding: have an encryption key for each user (stored outside of this ledger) and encrypt all PII with that key. Throw away the key if the user wants you to delete their data.
But then you must also plan for what happens when that encryption is broken. So I think you also need to control and protect your storage in order to make that a safe strategy.
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 think it's worse than just losing the data. If you operate a public cryptography ledger with users data in EU and do it under some company name, you won't be able to comply with the "right to be forgotten" or how it's called.
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.
