Some immutable data structures can cope with missing data. Merkle trees are an example: to validate that a leaf is part of the tree, you don't need any of the other leafs (only their direct or indirect hashes). For the Bitcoin blockchain, it has been designed so that transactions where all outputs have been spent can be pruned, after the spending transactions have been validated. It wouldn't be hard to extend this to prune "illegal" transactions, even after they've been included in valid blocks; the only consequence would be that a node wouldn't be able to validate other transactions spending these "illegal" transactions (so it would have to risk accepting an invalid transaction, or rejecting a valid transaction, in both cases risking being on the wrong side of a fork).

You would still have the history of those transaction(s) before they were pruned though...

Simply encrypt the data and upon “deleting it” instead delete the encryption key. This is similar to concerns about backups.

Sure, crypto-shredding seems like a great approach for some things.

But in many cases the whole reason systems use these structures in the first place is so that there's transparency and public verifiability.

> Recitations in GDPR require systems to be designed with privacy in mind. Immutable structures like the Bitcoin blockchain or Merkle trees in other applications would seem to be fundamentally incompatible with some GDPR privacy requirements.

And against whom would I claim my rights, for example: my right to be forgotten (Article 17: The data subject shall have the right to obtain from the controller the erasure of personal data concerning him or her without undue delay [...])?

In the case of a distributed blockchain, who is the controller as defined by the GDPR?

And even if one could identify a controller (say, in the case of a blockchain under centralized control), there are still exceptions to the rights of data subjects. Privacy is key to the GDPR, but not an absolute.

Every person running a full node would theoretically be a controller in that case. But as you say, you could probably make a "business requirements" case if it's just a certificate. Right to be forgotten does not include the right to demand people forget that you owe them money, for example.

What gets more complex is if you put non-business-related "sensitive" personal data in an immutable system, e.g. if you're building an illegal blacklist of union organisers.

I'm not sure it's that shocking a result that data impacted by GDPR may not be stored in an immutable format, given that the law requires you to mutate it under certain circumstances.

There's probably an interesting computer science problem here in how to create a data structure that retains as many advantages as possible from the immutable data structures, but still allows compliance with the GDPR.

It's an attack on memory, part of the War On General Purpose Computing.