  Bitcoin is an immutable permissionless blockchain system that has been
extensively used as a public bulletin board by many different applications that
heavily relies on its immutability. However, Bitcoin's immutability is not
without its fair share of demerits. Interpol exposed the existence of harmful
and potentially illegal documents, images and links in the Bitcoin blockchain,
and since then there have been several qualitative and quantitative analysis on
the types of data currently residing in the Bitcoin blockchain.
  Although there is a lot of attention on blockchains, surprisingly the
previous solutions proposed for data redaction in the permissionless setting
are far from feasible, and require additional trust assumptions. Hence, the
problem of harmful data still poses a huge challenge for law enforcement
agencies like Interpol (Tziakouris, IEEE S&P'18).
  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. 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. As an extra feature, our protocol offers
public verifiability and accountability for the redacted chain. Moreover, 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 that
shows only a tiny overhead in the chain validation of our protocol when
compared to an immutable one.
