When we talk about blockchains, often most celebrated feature is 'immutability' - that blockchains can't be changed once they have been created. Aside from this being only being about 95% true, there's a question of whether this is always really a good thing.
For transactions there's no argument about whether permanence is essential to proper functioning, although for other applications it's not as clear. For example, companies around the world are exploring identity blockchains and in this context it may be a lot less true. Will companies like ShoCard, Onename and Cambridge Blockchain be able to overcome these concerns?
We have two principle concerns when it comes to deletion of records and identity. First, there's the concern that users will have false information about them listed online as this brings its own problems if it can't be properly corrected and the false records totally expunged. Second, and more importantly, there are clear regulations requiring that identity information being deleted under certain circumstances (e.g. EU Directive 95/46/EC provides 'the right to be forgotten' and the Protection of Freedom Act 2012 (UK) forces the deletion of DNA records after 6 months).
Clearly, in any Blockchain system, the absolute deletion of records of impossible. This is because blocks subsequent to the one containing the information will make reference backwards in the chain and alterations, including deletions, will result in a complete fork.
There are some other options. First, if all data is encrypted when it's placed on a blockchain then the private keys can be deleted and, in theory, that should make the information totally inaccessible but, in reality, that's fraught with challenges (think about if the private key was ever recovered or if stronger brute force methods became available in 15 years).
Second, If only hashes were ever placed on a blockchain then the destruction of the full records will suffice although any system like this means data has to be transferred away from the blockchain; reducing its functionality.
Third, a non-blockchain distributed ledger could implement a consensus algorithm that allows records to be properly deleted - through some type of 'delete X, authorised by Y' message. Clearly, all records would have to be encrypted to stop full nodes just retaining copies after the 'delete' transactions has been received. that said, a simple majority voting algorithm could handle a 'delete' message - when nodes received the delete command they remove that record but keep a copy of the signature initially used to sign it to stop the transaction being sent again and accepted.
A Distributed Ledger like this would certainly lose functionality elsewhere but it would be within EU and UK law and would give reassurance to potential customers that where erroneous data about them was uploaded it could be properly removed without leaving residual suspicion.