Redactable blockchain… Wait, what?

This was my reaction when I was first introduced to the topic. Although there isn’t a hot discussion surrounding the concept, it’s worth exploring it. That’s why I thought it would be meaningful to share some information on the motivation behind the idea, several solutions that were introduced by researchers, and why I think it makes sense to pay attention to the topic.

First things first, there is a chance that your thought right now is: “I thought the whole idea of blockchain is that it’s an immutable and verifiable way of preserving information. I would want it to be immutable under ALL circumstances.”

To clarify Pirate Captain’s opinion, let’s look at an analogy. Nowadays, the Internet is a vast landscape that is home to both great and not-so-great content. And that content is (to some extent) manageable and subject to control. Well, the blockchain bears many similarities to the Internet, it’s a peer-to-peer network, information is stored “on” it, people are free to “upload” information to it. The big difference is that once it’s up there, that data stays there. Forever.

Is this good? Or bad?

Well, of course, it’s good. Immutability kind of makes digital currency possible. However, let’s look at some of the examples when the inherent immutability of blockchain is actually bad:

• Illegal and improper content embedded in transactions – such was found by researchers from RWTH Aachen University as stated in this article
• Illegal distribution of intellectual property
• Potential new laws such as the “right to be forgotten” (Article 17 of the GDPR)
• Lastly, one could also view the inability to update smart contracts and fix bugs as a negative byproduct of immutability. Although the community has managed with those issues so far.

After listing those points, let’s also look at some of the issues with redacting blockchains:

• It’s an extremely controversial and polarizing topic that might bring more harm than good at this time
• The complexity of finding a working solution is high and with some solutions, it will tend to get higher as a blockchain grows and data gets “dug in” further back into the chain
• Who is to say how frequently redactions will be applied?

As with all topics, people are entitled to their opinion, and if you didn’t close the website until now, because mutable blockchains sound preposterous to you, here are some solutions that address mutability.

Hard forks

This is the most straightforward solution. The blockchain is replaced from the current block to the block that will be changed. Although quite simple to explain, hard forks can be extremely costly because a segment of the blockchain has to be re-written.

More solutions that “keep” immutability

Obviously, hard forks are not optimal. There are other ways to implement redactable content while keeping the blockchain immutable.

• The first option I’ll mention is pruning. This is the act of deleting raw data in blocks after some period of new blocks. The strategy is described in Bitcoin’s whitepaper (7. Reclaiming Disk Space) although in a different aspect and not as a way to get rid of “bad” data on the blockchain.
• One option is to store pointers to the data and not the actual data. This way the data is kept in some distributed storage system (IPFS) and to redact the data on the blockchain, one has to change the data in the distributed storage. The pointers in the blockchain remain the same.
• Another approach that covers deleting data and not editing is storing data in an encrypted form and keeping the decryption keys private. That way, deleting data could be equal to deleting the decryption keys.

Solutions that discard immutability

This is the most disruptive type of solution as they effectively institute a new understanding of what the blockchain ledger is. Many questions may arise – what kind of changes will be allowed, are the changes going to be of entire blocks or transactions within a block, permissionless or premissioned?

To get a better overview of the different approaches, I’ll share two solutions born from academic research – one is an example for a consensus/network layer approach in a permissionless setting, the other is an application layer approach in permissioned setting.

Redactable blockchain in permissionless setting

You can read the paper here. Alternatively, you can also check the presentation of the protocol at the 2019 IEEE Symposium on Security and Privacy. Either way, here is a short summary of the protocol:

• It’s a voting-based protocol for block redaction that works with all consensus protocols (PoW, PoS, etc.)
• The main idea is to modify the classical block structure the following way:
  • There are two links between each block (“old” and “new”) and two Merkle roots
  • For each valid block, the “new” and “old” links are the same
• Users can propose to edit blocks via a request mechanism
  • To do that, a user has to propose a substitution block with an updated “new” Merkle root along with the necessary computations (in a PoW scenario, the hashes)
• The miners (again, in a PoW scenario) can then vote for the proposed block. This is done by including the hash of the candidate block in new blocks
• If, after a predetermined voting period, the redaction is approved, the old block is replaced by the proposed block

Redactable blockchain in permissioned setting

This is an application layer approach that sets an example for a protocol in permissioned setting. The paper could be found at this link: Fine-Grained and Controlled Rewriting in Blockchains: Chameleon-Hashing Gone Attribute-Based. To avoid diving deeper into technical details, let’s just summarize it by saying that the ability to edit is based on a cryptographic primitive, called Chameleon Hash functions.

However, since the Chameleon Hash (CH) functions from the linked paper guarantee proper function only under the condition that the trapdoor remains secure, they aren’t the optimal choice. That’s why the researchers who produced the Fine-Grained and Controlled Rewriting protocol set on to build upon an updated version of the CH functions, namely Chameleon Hashes with Ephemeral Trapdoors (CHET).

Taking the CHETs, they created a new cryptographic primitive – Policy-Based Chameleon Hashes (PBCHs).

PBCHs generalize the notion of chameleon-hashes by giving the party computing a hash the ability to associate access policies to the generated hashes. Anyone who possesses enough privileges to satisfy the policy can then find arbitrary collisions for a given hash. We then apply this concept to transaction-level rewriting within blockchains, and thus support fine-grained and controlled modifiability of blockchain objects.

David Derler, Kai Samelin, Daniel Slamanig and Christoph Striecks

In short, PBCHs upgrades CHs by adding 2 things:

1. Attributes – essentially, roles such as “Director”, “Scientist”, “Engineer”, “Manager”, etc.
2. Access structures – Boolean conditions ensuring an entity has a given attribute such as (“Scientist” AND “Engineer”) OR “Manager”

In the end, the innovative protocol produced a solution for efficiently being able to exchange transactions within a block, regardless of the block position within the blockchain, while keeping the hash of the Merkle Tree valid.

So… What does this mean?

If you ask me, nothing essential at this point in time. Although growing with great speed, the adoption of blockchain is still in its early years. We’re seeing the spectrum of practical applications grow each day hand by hand with the increasing user base and that’s what makes it so dynamic and interesting. The newly explored areas in this new technology allow for anything from bugs costing millions in cryptocurrency, scams, and make-money-fast schemes to cutting-edge innovations, research, and a view for a better future. But not to get philosophical, back to the topic of this blog post.

Redactibility is just one of the research areas that are somewhere on the sideline of the main pitch that is today’s blockchain technology. Time will show if it gets picked to play and becomes crucial. There are many moving parts to that. For one, the described permissionless solution is in harmony with Nakamoto’s philosophy, but it would still require time and effort for it to be applied in a real-world blockchain. The second PBCH protocol introduces a strong cryptographic approach to the problem while being an application-layer solution, but at its core, it requires a permissioned setting – something that the crypto community isn’t fond of.

In the end, before even talking about different approaches and solutions to a redactable blockchain, we should have a definitive answer to the more important questions – will the community ever want such a thing hard enough that it actually jumps from the field of research to the real world? Maybe… Who knows? But by all means, it’s worth it to keep an eye on it.