Escaping From Consensus: Instantly Redactable Blockchain Protocols in Permissionless Setting

Xin Yu Li, Jing Xu, Ling Yuan Yin, Yuan Lu, Qiang Tang, Zhen Feng Zhang

Research output: Contribution to journalArticlepeer-review


Blockchain technologies have drawn a lot of attentions, and its immutability is paramount to applications requiring persistent records. However, tremendous real-world incidents have exposed the harm of strict immutability, such as the illicit data stored on Bitcoin and the loss of millions of dollars in vulnerable smart contracts. Moreover, “Right to be Forgotten” has been imposed in new General Data Protection Regulation (GDPR) of European Union, which is incompatible with blockchain's immutability. Therefore, it is imperative to design efficient redactable blockchain in a controlled way. In this paper, we present a generic design of redactable blockchain protocols in the permissionless setting, applied to both proof-of-stake and proof-of-work blockchains. Our protocol can (1) maintain the same adversary bound requirement as the underlying blockchain, (2) support various network environments, (3) offer public verifiability for any redaction, and (4) achieve instant redaction, even only within one slot in the best case, which is desirable for redacting harmful data. Furthermore, we define the first ideal protocol of redactable blockchain and conduct security analysis following the language of universal composition. Finally, we develop a proof-of-concept implementation showing that the overhead remains minimal for both online and re-spawning nodes, which demonstrates the high efficiency of our design.

Original languageEnglish (US)
Pages (from-to)1-20
Number of pages20
JournalIEEE Transactions on Dependable and Secure Computing
StateAccepted/In press - 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


  • Bitcoin
  • Blockchain
  • Blockchains
  • Internet
  • Peer-to-peer computing
  • proof-of-stake
  • proof-of-work
  • Proposals
  • Protocols
  • redactable blockchain
  • Technological innovation


Dive into the research topics of 'Escaping From Consensus: Instantly Redactable Blockchain Protocols in Permissionless Setting'. Together they form a unique fingerprint.

Cite this