Paper 2019/1110

Redactable Proof-of-Stake Blockchain with Fast Confirmation

Jing Xu, Xinyu Li, Lingyuan Yin, Bingyong Guo, Han Feng, and Zhenfeng Zhang

Abstract

Blockchain technologies have received a considerable amount of attention, and immutability is essential property of blockchain which is paramount to applications such as cryptocurrency. However, ``Right to be Fogotten" has been imposed in new European Union's General Data Protection Regulation, making legally incompatible with immutalbe blockchains. Moveover, illicit data stored in immutable blockchain poses numerous challenge for law enforcement agencies such as Interpol. Therefore, it is imperative (even legally required) to design efficient redactable blockchain protocols in a controlled way. In this paper, we present a redactable proof-of-stake blockchain protocol in the permissionless setting with fast confirmation. Our protocol offers public verifiability for redactable chains, and to prevent an adversary from targeted attack, also uses a verifiable random function to randomly select voters for redaction on different slots in a private and non-interactive way. Compared to previous solutions in permissionless setting, our redaction operation can be completed quickly, even only within one block in synchronous network, which is desirable for redacting harmful or sensitive data. Moreover, our protocol is compatible with most current proof-of-stake blockchains requiring only minimal changes. Furthermore, using simulation techniques, we prove that our protocol can achieve the security property of redactable common prefix, chain quality, and chain growth. Finally, we implement our protocol and provide experimental results showing that compared to immutable blockchain, the overhead incurred for different numbers of redactions in the chain is minimal.