Source-linked AI summary
Redactable Blockchain in the Permissionless Setting
Dominic Deuber, Bernardo Magri, Sri Aravinda Krishnan Thyagarajan
TL;DR
Immutable permissionless blockchains can contain harmful data that cannot be removed, while earlier redaction approaches introduce scalability or trust problems. The paper presents a policy-governed, consensus-based editable blockchain with public verification and accountability, and reports only tiny validation overhead compared with an immutable chain.
Problem
Permissionless blockchains make stabilized harmful data difficult to remove, while prior redaction solutions are impractical or require additional trust assumptions.
Method
The protocol extends an immutable blockchain with old-state information, policy-governed candidate edits, consensus voting, and public verification.
Results
The protocol provides public verification of approved edits and shows only tiny chain-validation overhead compared with an immutable blockchain.
Takeaways & Limitations
Permissionless blockchain edits can be incorporated when they satisfy a public policy and receive sufficient consensus approval.
Takeaways & Limitations
The basic protocol permits only one edit operation per block, although the paper describes an extension for arbitrary redactions per block.
Abstract
from arXiv · showhide
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.
1 Introduction
Permissionless blockchains provide immutable public data storage but cannot readily remove harmful or illegal content. The paper proposes a decentralized editing protocol using policy-governed consensus voting, public verification, and accountability, with a proof-of-concept showing low validation overhead.
- Motivation: Permissionless blockchains allow arbitrary data insertion but make stabilized data difficult or impossible to remove, creating regulatory and adoption concerns.The paper connects this limitation to harmful content and compliance requirements such as GDPR.
- State of the Art: Prior redaction schemes rely on chameleon hashes, secret sharing, or large-scale MPC, which do not scale cleanly to permissionless systems.The cited alternatives are designed for permissioned settings or leave users control over whether transactions can be mutated.
- Our Contributions: The protocol provides public accountability because network users can verify whether an edit received sufficient votes and satisfied the chain policy.The design is described as decentralized, compatible with Bitcoin-like systems, and independent of the particular consensus mechanism.
- Implementation: The proof-of-concept reports small chain-validation overhead compared with an immutable protocol and minimal additional overhead as redactions increase.The supplied implementation passage states that 5,000 redactions on a 50,000-block chain incur less than 3% overhead relative to a redactable chain without redactions.
- Our Protocol: The protocol lets any user propose an edit, while miners validate candidates and vote during a policy-defined voting period.An approved request replaces the original block with its candidate; otherwise, the candidate is rejected or remains under deliberation.
- Our Protocol: Edited blocks retain old-state information so miners can validate predecessor links, proof of work, and consistency with neighboring blocks.Chain validation checks the old state when an ordinary link is broken and verifies that the edit was approved under the policy.
2 Preliminaries
The paper models a proof-of-work blockchain as a sequence of hash-linked blocks governed by persistence and liveness. Protocol executions are represented as round-based interactions among honest and corrupted parties under an adversarial message-delivery model.
- Blockchain Model: A block contains the previous state hash, data, and a proof-of-work counter, and is valid when its hash output is below the difficulty threshold.The validity condition is validateBlock_D(B) := H(ctr, G(s, x)) < D.
- Blockchain Model: A blockchain is a sequence of valid blocks in which each new block links to the preceding block through its state hash.The chain head is the rightmost block, and a valid block extends the chain.
- Blockchain Properties: Persistence means stabilized transactions remain in the same ledger position or are not replaced by conflicting stabilized transactions.A transaction becomes stable after the block containing it has at least k successor blocks.
- Blockchain Properties: Liveness means an honestly submitted transaction becomes stable after the protocol’s confirmation interval of u slots.This property assumes all honest users attempt to include the transaction.
- Protocol Execution: The formal execution model uses rounds, an environment, honest and corrupted parties, and an adversary that delivers messages without modifying honest broadcasts.The joint execution view includes parties’ inputs, randomness, and received messages.
3 Editing the Blockchain
The editable protocol Γ′ extends an immutable blockchain with candidate edits, old-state information, and policy-based voting. It validates candidates and edited chains while replacing blocks only after sufficient consensus approval.
- Protocol Interface: Γ′ preserves the basic blockchain interfaces while modifying chain and block validation to accommodate edited blocks.It additionally provides interfaces for proposing edits and validating candidate blocks.
- Block Representation: An edited block stores its old state so validators can verify the pre-edit relation even after the block’s data changes.The extended block structure includes the old state, and new blocks compute their predecessor link using current state information.
- Blockchain Policy: A policy accepts a candidate when it reaches the required vote ratio ρ during a voting period of ℓ blocks and satisfies persistence parameter k.The basic policy requires a majority within a predefined interval, while the formal definition uses the threshold ρ.
- Protocol Execution: Each round collects and validates candidate blocks, places valid candidates in pool R, and replaces the original block when policy evaluation returns accept.Rejected candidates are removed, while candidates still under voting remain in the pool.
- Protocol Execution: Users endorse a candidate by including its hash in a newly mined block, after which the extended chain is broadcast only if chain validation succeeds.The protocol’s voting and broadcasting steps operate round by round.
- Validation: Chain validation accepts an edited predecessor link only when candidate validation and policy approval both succeed, while also checking the old-state proof-of-work condition.The protocol is restricted to one edit per block in its basic form, with arbitrary repeated edits described as an extension.
4 Security Analysis
The protocol preserves chain growth and chain quality while replacing ordinary common-prefix semantics with an editable version that admits only policy-approved edits. Its security analysis shows unauthorized edits cannot violate the intended properties under the stated assumptions.
- Security Argument: The editable protocol behaves like the immutable protocol when no edits occur, while approved edits are incorporated through the policy.The common-prefix proof relies on collision resistance to prevent an adversary from producing a different candidate with the same hash.
- Chain Growth: The editable protocol preserves chain growth because edits cannot remove blocks or change chain length.It therefore satisfies (τ, s)-chain growth whenever the underlying immutable protocol does.
- Chain Quality: P satisfies (µ, ℓ)-chain quality for any (k, ℓ, ρ)-policy where ρ > µ.An adversary controlling only a µ fraction of resources cannot approve an edit requiring at least ρ votes without honest-node support.
- Editable Common Prefix: The ordinary common-prefix property does not hold during an in-progress edit, because different honest chains can retain different versions of a block.The protocol therefore introduces editable common prefix, which permits such divergence only when the edit is approved under policy P.
- Security Consequences: The combined properties establish a live and persistent blockchain that is immutable against edits not authorised by policy P.Editable common prefix restricts edits to policy-approved operations, while chain quality prevents disproportionate adversarial block contributions when ρ > µ.
5 Integrating into Bitcoin
The Bitcoin integration adds policy-governed redactions while preserving validation of transaction witnesses and enabling public verification of approved edits.
- Protocol integration: The protocol extends Bitcoin with an editable block structure and a policy governing the requirements and constraints for redaction operations.The integration is designed for one redaction per block, with extensions for multiple redactions described separately.
- Redaction requests: A redaction replaces a transaction with an otherwise identical candidate transaction that removes harmful data.The candidate transaction retains the other fields of the original transaction.
- Redaction requests: Users propose redactions by broadcasting editTx with the original and candidate transaction identifiers, after which valid candidates enter a voting pool.A candidate without a corresponding editTx is treated as spam rather than added to the candidate pool.
- Redaction policy: The basic policy permits only data removal from non-spendable components, forbids altering votes for other redactions, and requires more than 50% of votes across 1024 consecutive blocks.The restriction to non-spendable components is intended to avoid misuse and future chain inconsistencies.
- Block validation: Redaction-aware validation stores the old transaction hash so witnesses remain checkable against the original transaction while the chain verifies the edit request against policy.The edited block also preserves information needed to verify that the redaction was approved in the chain.
- Accountability: During voting, anyone can inspect the original and candidate transactions, and after redaction the data owner can verify removed data against the stored old-transaction hash.This provides both voting-phase accountability and victim accountability.
6 Proof-of-Concept Implementation
The proof-of-concept implementation evaluates validation overhead across chain sizes, redaction counts, and voting periods. It reports tiny overhead relative to immutable chains, at most linear growth with redactions and voting-period length, and less than 3% overhead for 5,000 redactions on a 50,000-block chain.
- Implementation: The Python proof-of-concept implements Bitcoin-like blockchain functionality, including arbitrary data insertion and subsequent redaction.The implementation uses PoW for conceptual simplicity.
- Benchmarking: 50,000 blocks approximate a one-year Bitcoin snapshot, and each experiment averages validation time over 50 runs.Chains contain up to 50,000 blocks, with 1,000 transactions per block.
- Overhead Compared to Immutable Blockchain: Validation overhead compared with an immutable chain is tiny and tends to decrease as chain size grows.With no redactions, the extra check for votes in a new block becomes negligible relative to total verification time.
- Overhead by the Voting Parameters ℓ and ρ: Voting-period overhead is very small for small ℓ and at most linear in ℓ.The validation cost comes from maintaining vote counts across the voting period, with the worst case occurring when ρ = 1.
7 Discussion
The discussion examines attacks against the redactable blockchain and explains how public verification, transaction consistency, fees, and consensus properties address them. It also identifies consensus delays as a protocol-boundary scenario tied to the Editable common prefix property.
- Unapproved Editing: Users can detect unapproved edits by checking whether the exact edit appears in the chain and satisfies the policy.The argument assumes that a majority of miners is honest.
- Scrutiny of Candidate Blocks: Public scrutiny discourages miners from voting for candidate blocks that tamper with transaction inputs or spendable outputs.Such tampering would affect transaction consistency and undermine the ledger’s reliability for monetary use.
- Denial of Service: Transaction fees deter denial-of-service attempts that flood the network with edit requests.The edit transaction may also incur a higher fee as an additional deterrent.
- Double Spend Attacks: Associating edited transactions with their old versions prevents a recipient from exploiting a changed hash for a double spend.Because the edit preserves transaction consistency, the new version remains spent when the old version was spent.
- Consensus delays: Different locally held redacted states could cause consensus delays, but under honest protocol behavior this would violate the Editable common prefix property.The described scenario assumes both sets of redacted blocks were policy-approved.
8 Related work
Related work covers Bitcoin applications, analyses of illicit content, and preventive or incentive-based responses. The cited literature motivates redaction approaches that address harmful data while preserving practical permissionless operation.
- Blockchain applications: Bitcoin’s public-bulletin-board role supports applications including secure multi-party computation, smart contracts, and distributed cryptography.These applications extend beyond Bitcoin’s initial monetary purpose.
- Illicit content: Prior studies analyse the distribution, usage, risks, and incentives associated with illicit content inserted into public blockchains.The cited work includes quantitative analysis of insertion techniques and potential risks.
- Preventive approaches: Other approaches study proactive detection, retaining only monetary information, or discouraging harmful insertions through fees and reduced transaction manipulability.These works address prevention or deterrence rather than the redaction mechanism itself.
A Protocol extension for multiple redactions
The protocol extension supports multiple redactions of a block by storing successive state information and validating each candidate against its prior redaction history. Voting remains policy-based, requiring a threshold ρ within a period of ℓ blocks.
- Proposing an Edit: A proposed subsequent redaction appends the current state information and the block digest when the current state differs from that digest.For the first redaction, the current state equals G(sj, xj).
- Block Validation: The extension represents a block’s redaction history as multiple state components, with y(1) storing the original unredacted state.A block redacted l times is parsed as y(1)||y(2)||...||y(l).
- Voting for Candidate Blocks: A vote endorses a candidate block by placing its candidate hash in a newly mined block during the voting phase.The policy accepts a redaction when the candidate receives at least a ratio ρ of votes within ℓ blocks after proposal.
- Candidate Block Validation: Candidate validation checks the accumulated history and requires votes for each redaction to be present in the chain.The approved candidate block carries information about previous redactions.
- Chain Validation: Chain validation parses the successive state components and invokes extended candidate validation while checking block links and policy acceptance.The extended algorithm preserves the original state while validating later redactions.