Paper 2021/223

Escaping from Consensus: Instantly Redactable Blockchain Protocols in Permissionless Setting

Xinyu Li, Jing Xu, Lingyuan Yin, Yuan Lu, Qiang Tang, and Zhenfeng Zhang


Blockchain technologies have received a great amount of attention, and its immutability is paramount to facilitate certain applications requiring persistent records. However, in many other use-cases, tremendous real-world incidents have exposed the harm of strict immutability. For example, illicit data stored in immutable blockchain poses numerous challenges for law enforcement agencies such as Interpol, and millions of dollars are lost due to the vulnerabilities of immutable smart contract. Moreover, ``Right to be Forgotten" (a.k.a. data erasure) has been imposed in new European Union's General Data Protection Regulation, thus causing immutable blockchains no longer compatible with personal data. Therefore, it is imperative (even legally required) to design efficient redactable blockchain protocols in a controlled way. In this paper, we propose a new redaction strategy to decouple the voting stage for redaction from the underlying consensus layer, where a committee with sufficient honest fraction is selected firstly and then the committee members would vote for the redaction. Based on this new strategy, we present a generic approach of designing redactable blockchain protocol in the permissionless setting with instant redaction, applied to both proof-of-stake (PoS) blockchain and proof-of-work (PoW) blockchain with just different instantiations to randomly select ``committee members'' according to stake or computational power. Our protocol can maintain the same adversary bound requirements and security assumption as the underlying blockchain (e.g., 1/2 adversary bound and various network environments), which is compatible with most current blockchains requiring only minimal changes. It also offers public verifiability for redactable chains, where any edited block in the chain is publicly verifiable. Compared to previous solutions in permissionless setting, our redaction operation can be completed instantly, even only within one slot for the best-case scenario of PoS instantiation, which is desirable for redacting harmful or sensitive data. Correspondingly, our redaction verification in the blockchain is also instant. Furthermore, we define the first ideal protocol of redactable blockchain following the language of universal composition, and prove that our protocol can achieve the security property of redactable common prefix, chain quality, and chain growth. Finally, we develop a proof-of-concept implementation, and conduct extensive experiments to evaluate the overhead incurred by redactions. The experimental results show that the overhead remains minimal for both online nodes and re-spawning nodes, which demonstrates the high efficiency of our design.

Available format(s)
Publication info
Preprint. Minor revision.
BlockchainProof-of-StakeProof-of-WorkRedactable Blockchain
Contact author(s)
xinyuli1920 @ gmail com
xujing @ iscas ac cn
lingyuan2018 @ iscas ac cn
luyuan @ iscas ac cn
qiang tang @ sydney edu au
zhenfeng @ iscas ac cn
2021-12-07: last of 4 revisions
2021-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xinyu Li and Jing Xu and Lingyuan Yin and Yuan Lu and Qiang Tang and Zhenfeng Zhang},
      title = {Escaping from Consensus: Instantly Redactable Blockchain Protocols in Permissionless Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2021/223},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.