Immutable doesn't necessarily mean that it's literally impossible to rewrite history or redact history. It's more a change in the default of how things are done

Immutable doesn't necessarily mean that it's literally impossible to rewrite history or redact history. It's more a change in the default of how things are done. Some merkle tree variants directly support deletions. You keep around the hash of the deleted subtree, so the overall structure still has a verifiable hash history, but you lose the data that generated the hash. Another simple approach is to use per user encryption keys, and when a user wants deletion just nuke their key in the system that stores keys.