[Redactable Blochchain in the Permissionless Setting]

Hello all,

greetings from Dominic Deuber (Friedrich Alexander University, Germany), Bernardo Magri (Aarhus University, Denmark) and myself, Sri Aravinda Krishnan Thyagarajan (Friedrich Alexander University, Germany). Our recent research work on Redactable Blochchain in the Permissionless Setting has been accepted and will be presented at the 40th Symposium on IEEE Security & Privacy 2019, Oakland (https://www.ieee-security.org/TC/SP2019/program-papers.html).

The problem of harmful data insertion into the Bitcoin blockchain is well motivated and poses a huge challenge for law enforcement agencies like Interpol (Tziakouris, IEEE S&P'18). In a step towards addressing this issue, in 2017 Ateniese et al. proposed the first Redactable blockchain protocol albeit in the permissioned setting. Their motivation was to redact (potentially harmful) contents from the chain and they achieved this by the use of Chameleon Hash functions. Their protocol works with finesse in the permissioned setting while proving to be impractical in case of a permissionless system like Bitcoin. Apart from the performance issues of doing a secret sharing among several thousand nodes in the P2P network of Bitcoin, they do not guarantee any notion of accountability for who/what/when some data point was redacted from the chain which we consider as violating the fundamental characteristic of the Bitcoin blockchain's public verifiability.

In our work we propose the first efficient redactable blockchain for the permissionless setting that is easily integrable into Bitcoin, and that does not rely on heavy cryptographic tools or trust assumptions (apart from the ones already required by Bitcoin). Our protocol uses a consensus-based voting and is parameterised by a policy that dictates the requirements and constraints for the redactions; if a redaction gathers enough votes the operation is performed on the chain.

Our protocol offers public verifiability and accountability for the redacted chain. It is possible for the users in the network to actively scrutinise a redaction before it gets approved. After a redaction happens, any user can verify (1) where the redaction was performed (2) if it was approved by policy of the network and (3) if both the original (un-redacted) and redacted chains were/are indeed valid. Moreover, post a redaction, our protocol guarantees protection against any user who makes a 'false victim' claim.

We provide formal security definitions and proofs showing that our protocol is secure against redactions that were not agreed by consensus. Additionally, we show the viability of our approach with a proof-of-concept implementation in Python that shows only a tiny overhead (of less than 3%) in the chain validation of our protocol when compared to an immutable one.

You may find the full version of the paper here. We would be glad to hear your feedback and suggestions on our work. Talk to us if you're interested in collaborating for a future work!