Thanks both for the replies.
Can't you make it simpler: encrypt the data, store the encryption key separately and move the raw data to cold storage. If user wants to erase, delete the encryption key avoiding massive recompute from cold store. Do you think this is better approach? This is not efficient, but in large scale (peta bytes) this could work.
Developers make mistakes, if they miss encrypting due to some bug in the code, and they want to fix it, then the hash chaining will be a problem though.
Good one. QQ. If you store it hash chained, how are you handling GDPR erasure requests? Isn't that supposed to erase within 30 days for GDPR instead of 180? Do you recreate the chain or soe sort of Pseudonymization or anything else?