Introduction
Blockchain technology is traditionally defined by its immutability. While this "append-only" nature ensures security and trust in financial transactions, it creates significant challenges when the ledger hosts illegal content, sensitive personal data, or buggy smart contract code. Presented at EuroS&P 2017, this research proposes a framework for "redactable blockchains," allowing authorized parties to surgically rewrite or delete blocks without breaking the underlying cryptographic chain.
The Problem of Absolute Immutability
The authors identify four critical issues stemming from permanent data storage:
- Abusive Content: Illegal material uploaded to public blockchains (like Bitcoin) creates legal liabilities for node operators.
- Privacy Regulations: Frameworks like GDPR grant individuals the "Right to be Forgotten," a requirement fundamentally at odds with immutable ledgers.
- Smart Contract Vulnerabilities: Critical flaws in code often necessitate contentious hard forks to rectify, as seen in the DAO attack on Ethereum.
- Blockchain Bloat: Immutability prevents the pruning of irrelevant historical data, hindering long-term scalability.
Proposed Framework: Chameleon Hash Functions
The core technical innovation is the replacement of standard hash functions (e.g., SHA-256) with Chameleon Hash Functions. These are "trapdoor" functions that allow a party possessing a secret key to find collisions—different inputs that result in the same hash output.
Key Technical Features
- Trapdoor Mechanism: With the secret key, an entity can change a message $m$ to $m'$ such that $H(m) = H(m')$. This allows for block modification without altering the hash stored in the subsequent block.
- Secret-Coin Construction: To prevent "key exposure"—where revealing one collision allows others to recover the secret key—the authors utilize a "secret-coin" chameleon hash. This ensures the system remains secure even after multiple redactions.
- The "Scar": Every block includes a "Randomness" field. When a block is redacted, this field is updated to satisfy the collision. This acts as a permanent, visible "scar," signaling to auditors that a modification occurred.
Governance and Trust
The paper outlines two primary models for managing the redaction trapdoor:
- Centralized: A single regulator or trusted organization holds the key.
- Decentralized: The key is distributed among multiple parties (e.g., major mining pools) using Secure Multi-Party Computation (MPC). A redaction can only proceed if a predefined threshold of participants agrees.
Implementation and Performance
The authors developed a proof-of-concept prototype by modifying Bitcoin Core (v0.12). Testing on a regression network demonstrated that the system is highly efficient:
- Negligible Overhead: Block creation time with chameleon hashes is nearly identical to standard SHA-256.
- Rapid Redaction: Finding a collision to redact a block takes approximately 10 milliseconds on standard server hardware.
- Scalability: The performance of redaction and deletion algorithms is independent of the number of transactions within the block.
Discussion and Limitations
Redactable blockchains offer a "surgical" alternative to "hard forks." While a hard fork to fix an old block would invalidate all subsequent history, a redaction keeps the rest of the chain cryptographically intact. Furthermore, the design is "history independent," meaning new nodes joining the network see a consistent chain without needing to know its modification history.
However, the system introduces a significant trust trade-off. The security of the entire history relies on the protection of the trapdoor keys. If compromised, an attacker could rewrite the ledger at will. Additionally, while the paper provides the technical means for redaction, the social and political questions of who should decide what gets deleted remain an open area for future policy research.
Summary updated