=Paper=
{{Paper
|id=Vol-3791/paper9
|storemode=property
|title=Data Redaction in Smart-Contract-Enabled Permissioned Blockchains
|pdfUrl=https://ceur-ws.org/Vol-3791/paper9.pdf
|volume=Vol-3791
|authors=Gennaro Avitabile,Vincenzo Botta,Daniele Friolo,Ivan Visconti
|dblpUrl=https://dblp.org/rec/conf/dlt2/AvitabileBFV24
}}
==Data Redaction in Smart-Contract-Enabled Permissioned Blockchains==
https://ceur-ws.org/Vol-3791/paper9.pdf
Data Redaction in Smart-Contract-Enabled Permissioned
Blockchains
Gennaro Avitabile1,† , Vincenzo Botta2,*,† , Daniele Friolo2,† and Ivan Visconti3,†
1
IMDEA Software Institute, Campus de Montegancedo s/n, 28223 Pozuelo de Alarcón, Madrid, Spain
2
Sapienza University of Rome, Piazzale Aldo Moro 5, 00185 Rome, Italy
3
University of Salerno, Via Giovanni Paolo II, 132, 84084 Fisciano, Italy
Abstract
Balancing immutability and compliance with regulations stands as a significant challenge in the realm of
blockchain technology applications. Due to the increase of data-protection requirements (e.g., the General Data
Protection Regulation (GDPR) in the European Union), it is essential to address the problem of deleting data from
a blockchain without compromising the security and transparency of the blockchain itself.
Several works proposed techniques to address the data redaction problem, and the most effective ones are
mainly applicable to permissioned blockchains. In their seminal work, Ateniese et al. [EuroS&P 2017] were
the first to propose a redactable blockchain. Their approach focuses on permissioned blockchains and they
showed how to change the content of a transaction without breaking the chaining among blocks by using special
cryptographic hash function (i.e., chameleon hash functions) and protocols for secure multi-party computation to
make the required distributed computations.
We observe that the redaction technique of Ateniese et al. does not take into account the possibility that the
blockchain includes smart contracts and that a redaction of a transaction might leave inconsistencies in the logic
of the contracts, making some remaining non-redacted transactions invalid. We find this decision rather limiting
since decentralized and publicly verifiable computation guaranteed by smart-contract-enabled blockchains is
indeed necessary for modern applications.
In order to overcome the above limitations of the applicability of the redaction techniques of Ateniese et al.,
we propose a redaction technique with wider applicability that leverages succinct non-interactive arguments of
knowledge (SNARKs) to realize what we call a proof-of-consistency. A SNARK will be computed to show that the
current state of a smart contract is consistent with respect to a previous state since there existed transactions,
now redacted, that produced the current state from a former publicly verifiable state. Therefore, a successful
verification of such a SNARK allows to maintain the consistency of the non-redacted transactions with the state
of the smart contract, and the resulting blockchain maintains public verifiability and consistency in the presence
of redacted transactions.
Keywords
Blockchain, Redaction, Permissioned, Smart Contract, SNARK
1. Introduction
Motivated by the widespread adoption of decentralized platforms, and the requirements imposed by the
GDPR and in general by laws, many techniques have been proposed to erase data from blockchains. As
shown by Matzett et al. [1], even a blockchain like Bitcoin, designed only for financial use, stores illegal
data such as child pornography and dark web services. Because of that, some countries could have
banned blockchain usage. A seminal work from Ateniese et al. [2] proposed a technique that allows
to relax the immutability of a blockchain while still maintaining the consistency of its structure (i.e.,
the validity of previously computed hash pointers) through chameleon hash functions. In a nutshell, a
chameleon hash function is a hash function that has a public hash key and a private trapdoor. Unless
the trapdoor is known, this function achieves collision resistance as a standard hash function. In theory,
knowledge of prior collisions could be exploited to find more collisions for an arbitrary new message,
DLT2024: 6th Distributed Ledger Technologies Workshop, May, 14-15 2024 - Turin, Italy
*
Corresponding author. The majority of the work was done while affiliated with the University of Warsaw.
†
These authors contributed equally.
$ gennaro.avitabile@imdea.org (G. Avitabile); botta.vin@gmail.com (V. Botta); friolo@di.uniroma1.it (D. Friolo);
visconti@unisa.it (I. Visconti)
© 2024 Copyright © 2024 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
even without knowledge of the trapdoor and this must therefore be considered leading to a special
definition of collision resistance. Two things must be noticed here: (1) their solution requires changing
the specifications of the blockchain to use this hash function; (2) the trapdoor must be kept secret by
someone who is trusted, introducing an additional trust assumption in the blockchain. These two points
make the solution of Ateniese et al. suitable for permissioned blockchains in which the governance
maintaining the blockchain is already trusted (the majority of the parties cooperating within the
governance must be honest) and already controls the blockchain’s consensus. To perform the redaction,
a multi-party computation protocol is executed among all the parties of the consortium. Following the
seminal work of [2] several other works proposed redaction techniques for the permissioned setting
[3, 4, 5, 6, 7, 8].
1.1. Blockchain Structure
A blockchain is a series of ordered blocks whose design lies in deploying a chain in which each block is
linked to the previous one. This linking operation is obtained using hash functions. The hash function
is used to make any block dependent on the content of the previous block so that everyone can publicly
verify that the current state of the blockchain was not tampered with. Each block contains data that
can be divided into transactions. Each transaction can contain a coin transfer from some users to other
users or other data that can be stored on the blockchain to make them publicly available and verifiable.
As said before, the hash is used to link the blocks, so a block 𝐵𝑖 in the chain contains a value that
is the hash of the transactions of the previous block 𝐵𝑖−1 together with some additional values that
depend on the consensus mechanism. Even if it seems that the blockchain should be immutable, there
are scenarios in which it is mandatory to delete some data (e.g., in case of compliance with laws and
regulations). Therefore, a technique that allows the editing of the blockchain is highly desirable.
1.2. Previous Solution
Let us give a high-level description of the chameleon-hash-function-based solution of [2]. Each member
of the blockchain consortium, or governance, has a share of a trapdoor of a chameleon hash function.
Whenever a block 𝐵 must be modified, the consortium members agree on a new 𝐵 ′ . Then, to replace 𝐵
with 𝐵 ′ without altering its hash value, the consortium computes a collision in the hash function with a
multi-party protocol executed from the consortium members’ trapdoor shares. The collision-resistance
property of the chameleon hash function and the honest majority of the members of the governance
ensure that when the trapdoor is kept private, the blockchain is consistent and resilient to any chain
tampering attempts.
Since it is needed that the governance is known and fixed, this result is mainly suitable for permis-
sioned blockchains, even though, as the authors of [2] outline, their solution could potentially find
applications also to permissionless blockchains by distributing the trapdoor among the full nodes or a
chosen subset of participants. This is however problematic since the number of full nodes can drastically
change over time, and there is no obligation for the nodes with a share of the trapdoor to remain active
forever (losing the possibility of reconstructing the trapdoor).
We observe that even though one limits the usage of the techniques in [2] exclusively to permissioned
blockchains, there is a major problem: the transactions originally in 𝐵 and modified in 𝐵 ′ may be
somehow related to subsequent transactions. This issue was also highlighted in [9], noting that
removing data from a blockchain transaction can affect multiple related transactions. This makes
deletion challenging without compromising the integrity of a part of the blockchain.
The issue of compromising the integrity of the blockchain becomes more evident when considering
a smart-contract-enabled blockchain. Roughly, a smart contract is a piece of code that can be fed with
inputs coming from valid transactions. A smart contract is associated with a state, and each time an
input is given to the smart contract, the state changes. The current state of the smart contract can be
inferred from the blockchain.
In the presence of a blockchain redaction it is possible that even if the chaining among blocks and
within transactions is consistent, the logic inferred from transactions stored in the blockchain may be
broken. This is evident when considering the state of the smart contract they refer to.
Simple solutions and their drawbacks. A direct approach to fix the problem of maintaining the
consistency of the state of a smart contract in the presence of redacted transactions, still remaining
within the techniques envisioned by Ateniese et al., consists of possibly redacting also subsequent
correlated transactions in such a way that the state of the blockchain remains consistent. We will now
discuss why such a repeated redaction process can be very harmful for those use cases that relied on
data available in smart contracts.
Let us consider as a toy example a smart contract that keeps a counter initialized to 0. Suppose a
transaction 𝑡𝑥1 with the aim of increasing the counter is submitted. The state of the counter is now
increased to 1, assuming 𝑡𝑥1 gets accepted by the blockchain. If subsequent transactions 𝑡𝑥2 , . . . , 𝑡𝑥𝑛
also get accepted, this would lead to a final state having 𝑛 as the value of the counter. It is clear that
if 𝑡𝑥1 is removed from the blockchain, then any transaction that crucially relied on the value of the
counter being 𝑛 would not be consistent anymore. Indeed, the remaining transactions add up to 𝑛 − 1
and not 𝑛. In turn, consistency can be enforced by also redacting those transactions that relied on the
value of the counter being 𝑛, and this in turn might require further redactions severely damaging those
applications that relied on those data that would be removed.
In light of the above discussion, we have the following natural open problem.
Open Problem: Is there a redaction technique for updating a transaction in permissioned smart-contract-
enabled blockchains without affecting other transactions and still maintaining the smart contract in a
consistent state?
We obviously require that all redaction operations do not affect the public verifiability feature of the
blockchain in any way since otherwise, we would end up in the classical setting where clients have to
trust servers.
1.3. Our Solution
At a high level, a smart contract 𝜑 consists of a set of functions 𝑓1 , . . . , 𝑓𝑛 . Transactions point to the
address of a smart contract and contain an input for a smart contract function 𝑓𝑖 . Each function of 𝜑
takes as input the current state of the smart contract (that can be inferred by the blockchain content)
and the input contained inside the transaction that points to 𝜑. Given these two values as inputs, 𝑓𝑖
produces a new state for 𝜑. Note that, by following Ethereum Smart Contracts documentation1 , we do
not allow smart contract functions to read transaction data inside the blockchain, hence we allow only
the smart contract states and the input.
Inspired by the approach of [10], we use the following technique to manage the redaction of a
transaction that changes the state of a smart contract. Let us suppose that a transaction 𝑡𝑥 must be
redacted. Before modifying 𝑡𝑥, the governance checks if there are smart contracts with states that
depend on the execution of 𝑡𝑥 (this can be done efficiently by maintaining this information in some
ad-hoc data structure) and that would have inconsistent states in case 𝑡𝑥 is redacted. Let 𝑡𝑥 be a
transaction that was pointing to some smart contract function in 𝜑. The governance will look for the
subsequent transactions of 𝜑 depending on the state st (i.e., it will look for the transactions directly
affected by 𝑡𝑥). Let 𝑡𝑥1 , . . . , 𝑡𝑥𝑚 be the set of transactions that have to be redacted. Let us assume
that 𝑡𝑥1 , . . . , 𝑡𝑥𝑚 directly affect transactions 𝑡𝑥′1 , . . . , 𝑡𝑥′𝑛 . The governance will generate, for each
transaction 𝑡𝑥′𝑖 , 𝑖 ∈ [𝑛], which prior to the redaction was updating the state of a smart contract to a
specific value, a proof 𝜋𝑖 showing that there were transactions 𝑡𝑥𝑗 , 𝑗 ∈ [𝑚], such that the transaction
𝑡𝑥′𝑖 leads to that given value of the smart contract. After 𝜋1 , . . . , 𝜋𝑛 are generated, the governance
can replace through the techniques of [2] the old transactions with the redacted ones. The proofs
1
https://ethereum.org/en/developers/docs/smart-contracts/
are auxiliary redaction information that can be either added to the redacted blocks or made available
independently.
Going back to our example of updating a counter, if the governance redacts transaction 𝑡𝑥1 , then
the directly affected transaction is 𝑡𝑥2 (other transactions updating the counter and other transactions
using the next values of the counter are indirectly affected) since it was setting two as value of the
counter starting from the value one set by 𝑡𝑥1 . In order to avoid an impact on other transactions, we
need that after executing 𝑡𝑥2 , despite the redaction of 𝑡𝑥1 the value of the counter is still two, and this
should be publicly verifiable as a correct value. With our solution, before deleting 𝑡𝑥1 , the governance
will prepare a proof 𝜋 that certifies that 𝑡𝑥2 is consistent with the state of the smart contract having
two as value of the counter since there existed a transaction 𝑡𝑥1 setting already the value to one. We
call the type of proof described above as proof-of-consistency.
Given this high-level overview of our technique relying on proofs-of-consistency, it is clear that, in
our redaction technique, the state of the blockchain before and after a redaction remains unchanged, and
state consistency can be publicly verified. We remark that our technique can be efficiently implemented
depending on the specific SNARK to be computed, and this can depend on several factors (e.g., the
format of transactions, the computations that they perform, and the complexity of the state of the smart
contract). We also remark that the technique is not applicable to all possible updates of transactions.
For instance, in the above case of the counter, the technique is applicable when 𝑡𝑥1 must be removed,
but it is not applicable when 𝑡𝑥1 must be changed to a transaction aiming at setting the value of the
counter to a value different than one (e.g., through two increments of the counter), since this would
conflict with the fact that after executing 𝑡𝑥2 the value must be two.
2. Related Work and Comparison
Ateniese et al. [2] proposed a mechanism to update block contents in blockchains. Their solution is very
efficient and is mainly applicable to the permissioned setting. Their deletion approach can potentially
go unnoticed by users not actively participating in the redaction process. They rely on the concept
of chameleon hash functions, consisting of equipping hash functions with trapdoors facilitating the
discovery of many preimages for a given digest. In our approach, we depart from their mechanisms and
address the important issue of dealing with the consistency of the permissioned blockchains in which
smart contracts are deployed.
Puddu et al. [11] proposed a protocol where users can define alternative versions, referred to as
“mutations”, for their transactions. These mutations can be activated later through an expensive secure
multi-party computation (MPC) protocol. Approval for a modification request is contingent upon a
voting procedure utilizing proofs of work. In their solution, only the transaction’s creator can allow its
modifications, thereby preventing the deletion of content inserted by malicious entities. Their solution is
thought to work in the permissionless setting, but this approach has the significant drawback of giving
the miners the power to forbid any form of modification to the mined blocks, effectively bypassing the
whole mutation mechanism.
Deuber et al. [12] introduced a redactable blockchain protocol for the permissionless setting. In their
protocol, users can suggest modifications by inscribing proposals directly onto the blockchain. The
approval of redaction proposals is determined through a voting process that combines consensus and
computational power. This protocol requires an online voting procedure on the blockchain since they
operate on a permissionless blockchain and they want to modify the view of all nodes. The drawbacks
of online voting technique are discussed in [13, 10].
Thyagarajan et al. [14] introduced Reparo, which is an enhancement of Deuber et al.’s solution
allowing to redact or modify blocks that are incorporated into the blockchain before the implementation
of the software update containing the redaction protocol. Similar to Deuber et al., Reparo is thought
to be used on permissionless blockchains and relies on resource-intensive and interactive consensus
protocols that necessitate several days for their execution.
Grigoriev et al. [15] proposed a data redaction mechanism based on the RSA cryptosystem, with a
primary focus on permissioned blockchains. The idea is similar to the idea expressed by [2], and the
same issues of [2] about smart contracts (i.e., it is not clear how to modify the transactions subsequent
to a redacted transaction to keep the state consistent) applies also to their work.
Botta et al. [10] designed and implemented a mechanism for securely deleting some data specifically
from the Bitcoin blockchain. Their technique relies on transparent non-interactive succinct arguments
of knowledge, allowing any node to locally delete some data from Bitcoin transactions, still preserving
the public verifiability of the blockchain. Their technique requires that a node that wants to delete
locally some data can do it directly creating a succinct proof that the modified block is the result of a
redaction of a prior block that had the same content except for some neutral data and that produced a
Merkle root that is consistent with the chaining of the blocks. The redaction technique proposed does
not require any coordination among nodes. They apply their technique only to those data of Bitcoin
(i.e., the free texts allowed by coinbase transaction and the one that can be added after an OP_RETURN
instruction) that are irrelevant for the state of the blockchain (i.e., the UTXOs). We will depart from their
technique and generalize it to preserve the consistency of the state of a smart contract in a permissioned
blockchain. A solution similar to [10] was proposed by Larraia et al. [16].
Zhang et al. [5] proposed an enhanced version of [2] in which the redaction proposal can be made
only by authorized users that have a specific secret. This is obtained using decentralized attribute-based
encryption.
Zhou et al. [4] presented a solution for permissioned blockchains, similarly to [2] they use a chameleon
hash function and allow two types of modifications: the transaction modification that can be performed
only by the owner of the transaction and the transaction deletion that can be done by a regulator in case
the transaction must be deleted. To achieve this, each transaction is hashed with a particular chameleon
hash function that depends on the identity of the user that performs the hash. The regulator possesses
a secret key that can be used to derive the secret keys of all other users for the hash function. Every
modification or deletion must be accepted by the consensus mechanism. Moreover, the regulator has
the power to modify all the transactions related to the modified or deleted transaction recovering the
secret key of the owner of the impacted transaction.
Peng et al. [6] also proposed a system based on a voting procedure that is more efficient compared
to [12]. Indeed, the voting procedure is done using an aggregate signature among the parties in the
consortium on a block proposed by a user off-chain, publishing on-chain a way to verify the result of
the ballot.
Wang et al. [17] proposed a different solution for permissioned blockchains based on verifiable delay
functions. In their approach, when a redaction proposal is sent to a supervisor, the supervisor quickly
constructs a chain fork to redact the proposed blocks. This fork is proposed to the leader node and the
accounting nodes. If the produced fork keeps consistency it is spread as the new blockchain. Even if
this solution can be efficient, it requires that the supervisor updates the entire blockchain.
Dai et al. [18] proposed a solution that exploits both the vote solution and the chameleon hash
function, indeed their solution requires a vote to decide if a given block should be substituted, and once
it is decided, it is replaced with the help of the chameleon hash function to keep the consistency of the
links among the blocks.
The limitations of [2] apply essentially to all above works since they do not address consistency of
states of smart contracts and the availability of legitimate transactions, once a prior and correlated
transaction has been redacted.
3. Preliminaries
We will denote by [𝑘] the set {1, . . . , 𝑘}.
3.1. Succinct Non-Interactive Argument of Knowledge
In this paper, we use the notion of succinct non-interactive argument of knowledge (SNARK). We defer
to [19, 20, 21, 22] for a more precise description. Let 𝑅 be a binary relation computable in polynomial
time. We identify with the pair (𝑥, 𝑤) the elements in the relation, where we call 𝑥 the statement and 𝑤
the witness. A SNARK for a relation 𝑅 consists of two probabilistic polynomial-time (PPT) algorithms
Prove and Verify that both have access to a common reference string (CRS), and potentially to a random
oracle (RO) 𝑂:
• Prove(𝐶𝑅𝑆, 𝑥, 𝑤): this is a PPT algorithm that takes as input the 𝐶𝑅𝑆, a statement 𝑥, and a
witness 𝑤 s.t. (𝑥, 𝑤) ∈ 𝑅, and has oracle access to 𝑂. It outputs a proof 𝜋.
• Verify(𝐶𝑅𝑆, 𝑥, 𝜋): this is a deterministic polynomial-time algorithm that takes as input the 𝐶𝑅𝑆,
a statement 𝑥, a proof 𝜋, and has oracle access to 𝑂. It outputs 1 if the proof is accepted, and 0
otherwise.
Prove is used by the prover and Verify by the verifier. Informally, these algorithms must satisfy the
following properties:
• Completeness: An honest prover convinces an honest verifier with overwhelming probability.
• Knowledge Soundness: If a malicious prover Prove* is able to prove a statement 𝑥 with a given
probability 𝑝, there exists a PPT extractor 𝐸 such that if Prove* produces with non-negligible
probability an accepting proof 𝜋 for a statement 𝑥, then 𝐸 with access to the prover outputs a
witness 𝑤 for 𝑥 with overwhelming probability.
• Zero knowledge: The proof computed by Prove does not reveal any additional information apart
the veracity of the claim.
• Succinctness: Verify runs in polynomial time in the size of the statement 𝑥; moreover, the proof
size and the running time of the verifier are sublinear in the size of the witness for 𝑥.
When in the above definition the CRS can not have a trapdoor affecting knowledge soundness and
zero knowledge, a SNARK is usually referred as STARK, where the letter “T” remarks the transparency
of the involved CRS.
3.2. Chameleon Hash Functions
Chameleon hash functions were first introduced in [23]. In this work, we report the definition from
[2]. At a very high level, a chameleon hash function is a cryptographic hash function that contains a
trapdoor. It is hard to find a collision except if the trapdoor is known, indeed knowing the trapdoor it is
possible to efficiently generate collisions.
More precisely a chameleon hash function is a tuple of PPT algorithms 𝐶𝐻 = (𝐻𝐺𝑒𝑛, 𝐻𝑎𝑠ℎ, 𝐻𝑉 𝑒𝑟, 𝐻𝐶𝑜𝑙)
specified as follows.
• (ℎ𝑘, 𝑡𝑘) ← 𝐻𝐺𝑒𝑛(1𝜆 ): The probabilistic key generation algorithm 𝐻𝐺𝑒𝑛 takes as input the
security parameter 𝜆 ∈ N, and outputs a public hash key ℎ𝑘 and a secret trapdoor key 𝑡𝑘.
• (ℎ, 𝜈) ← 𝐻𝑎𝑠ℎ(ℎ𝑘, 𝑚): The probabilistic hashing algorithm 𝐻𝑎𝑠ℎ takes as input the hash key
ℎ𝑘, a message 𝑚 ∈ 𝑀 , and outputs a pair (ℎ, 𝜈) that consists of the hash value ℎ and a check
string 𝜈.
• 𝑑 = 𝐻𝑉 𝑒𝑟(ℎ𝑘, 𝑚, (ℎ, 𝜈)): The deterministic verification algorithm 𝐻𝑉 𝑒𝑟 takes as input a
message 𝑚 ∈ 𝑀 , a candidate hash value ℎ, and a check string 𝜈, and returns a bit 𝑑 that equals 1
if (ℎ, 𝜈) is a valid hash/check pair for the message 𝑚 (otherwise 𝑑 equals 0).
• 𝜈 ′ ← 𝐻𝐶𝑜𝑙(𝑡𝑘, (ℎ, 𝑚, 𝜈), 𝑚′ ): The probabilistic collision finding algorithm 𝐻𝐶𝑜𝑙 takes as input
the trapdoor key 𝑡𝑘, a valid tuple (ℎ, 𝑚, 𝜈), and a new message 𝑚′ ∈ 𝑀 , and returns a new check
string 𝜈 ′ such that 𝐻𝑉 𝑒𝑟(ℎ𝑘, 𝑚, (ℎ, 𝜈)) = 𝐻𝑉 𝑒𝑟(ℎ𝑘, 𝑚′ , (ℎ, 𝜈 ′ )) = 1. If (ℎ, 𝜈) is not a valid
hash/check pair for message 𝑚 then the algorithm returns ⊥.
A chameleon hash function 𝐶𝐻 = (𝐻𝐺𝑒𝑛, 𝐻𝑎𝑠ℎ, 𝐻𝑉 𝑒𝑟, 𝐻𝐶𝑜𝑙) with message space 𝑀 satisfies
correctness if there exists a negligible function 𝜇 for all 𝑚 ∈ 𝑀 such that
[︁ ]︁
Pr 𝐻𝑉 𝑒𝑟(ℎ𝑘, 𝑚, (ℎ, 𝜈)) = 1 : (ℎ, 𝜈) ← 𝐻𝑎𝑠ℎ(ℎ𝑘, 𝑚); (ℎ𝑘, 𝑡𝑘) ← 𝐻𝐺𝑒𝑛(1𝜆 ) ≥ 1 − 𝜇(𝜆).
Ateniese et al. introduced a stronger definition of collision resistance stating that 𝐶𝐻 is collision-
resistant if the following holds: no PPT algorithm 𝒜, given the public hash key ℎ𝑘, can find two pairs
(𝑚, 𝜈) and (𝑚′ , 𝜈 ′ ) that are valid under ℎ𝑘 and such that 𝑚 ̸= 𝑚′ , with all but a negligible probability
and this must hold even when 𝒜 can see an arbitrary number of collisions generated using the trapdoor
key 𝑡𝑘 corresponding to ℎ𝑘.
3.3. Permissioned Smart-Contract-Enabled Blockchains in a Nutshell
To formalize blockchains we rely on the notation of [24]. A blockchain is a chain 𝐶 of blocks, where
each block has the form 𝐵𝑖 = (𝑠, 𝑥, 𝑐𝑡𝑟). Intuitively, 𝑥 is the set of transactions in 𝐵, 𝑠 is the head
of the block and 𝑐𝑡𝑟 is a value used to make the chaining of the hash consistent. A block 𝐵 is valid
if a predicate validblock(𝐵) = 1. The function validblock is arbitrarily chosen by the parties of the
consortium that maintains the blockchain.
The last published block is called the head of the chain, denoted by 𝐻𝑒𝑎𝑑(𝐶). A chain 𝐶 with a head
𝐻𝑒𝑎𝑑(𝐶) = (𝑠, 𝑥, 𝑐𝑡𝑟) can be extended to 𝐶 ′ = 𝐶||𝐵 ′ by attaching a (valid) block 𝐵 ′ = (𝑠′ , 𝑥′ , 𝑐𝑡𝑟′ );
the head of the new chain 𝐶 ′ is 𝐻𝑒𝑎𝑑(𝐶 ′ ) = 𝐵 ′ . The function 𝑙𝑒𝑛(𝐶) denotes the length of a chain
𝐶 (i.e., its number of blocks). For a chain 𝐶 of length 𝑛 and any 𝑘 ≥ 0, we denote by 𝐶 ⌈𝑘 the chain
resulting from removing the 𝑘 rightmost blocks of 𝐶, and analogously we denote by ⌉𝑘 𝐶 the chain
resulting in removing the 𝑘 leftmost blocks of 𝐶. If 𝐶 is a prefix of 𝐶 ′ we write 𝐶 ≺ 𝐶 ′ .
3.3.1. Handling Smart Contracts
Since we are considering smart-contract-enabled blockchains, we provide our formalization of a smart
contract. Recall that each block 𝐵 = (𝑠, 𝑥, 𝑐𝑡𝑟), and 𝑥 is the set of transactions contained in 𝐵.
To account for smart contracts, we consider the following three types of transactions: (i) standard
transactions, (ii) smart contract transactions, and (iii) state transactions. A standard transaction 𝑡𝑥 is a
tuple (addr𝑡𝑥 , data, toaddr), where addr𝑡𝑥 is the address of the transaction, data is either raw data
or smart contract’s inputs as we specify later, and toaddr is either the address of the recipient smart
contract or 0 when 𝑡𝑥 contains raw data.
A smart contract transaction contains a smart contract 𝜑, that is composed of a tuple (addr𝜑 , 𝑓1 , . . . , 𝑓ℓ ).
We will sometimes refer to 𝜑 as a vector, therefore 𝜑[𝑖] corresponds to the 𝑖-th element of the tuple.
In 𝜑, the value addr𝜑 is the address of the smart contract, while 𝑓1 , . . . , 𝑓ℓ are functions. 𝜑 further
initializes a state st0𝜑 containing the initial state of the internal variables of its functions (𝑓1 , . . . , 𝑓ℓ ).
The state transaction contains the state st𝜑 of some smart contract 𝜑2 .
When a standard transaction 𝑡𝑥 = (addr𝑡𝑥 , data, toaddr) is used as an input for 𝜑 = (addr𝜑 , 𝑓1 , . . . , 𝑓ℓ ),
the field toaddr of 𝑡𝑥 matches with the addr𝜑 field of 𝜑 and data will be a pair (𝑖, inp) where inp is
the input to the function 𝑓𝑖 inside 𝜑, with 𝑖 ≤ ℓ.
Let 𝑀 𝑎𝑝𝑇 𝑥𝑆𝐶(𝐶, 𝑡𝑥) be the function outputting the smart contract 𝜑 triggered by 𝑡𝑥 (i.e. 𝜑 inside
𝐶 such that toaddr = 𝜑[1]). 𝑀 𝑎𝑝𝑇 𝑥𝑆𝐶(𝐶, 𝑡𝑥) outputs ⊥ if such smart contract is not found. Further,
let 𝑆𝑡𝐻𝑒𝑎𝑑(𝐶, 𝜑) be a function outputting the index of the last state of 𝜑 inside 𝐶. Given 𝜑, when a
new transaction 𝑡𝑥 with toaddr = addr𝜑 and data = (𝑖, inp) is accepted, the function 𝑓𝑖 inside 𝜑
will create a new state st𝑚 𝜑 with 𝑚 = 𝑆𝑡𝐻𝑒𝑎𝑑(𝐶, 𝜑) + 1. This new state will be inserted in some state
transaction to be published inside a new block of 𝐶.
Since we are indexing smart contracts independently from the smart contract transaction they belong
to, we assume the existence of a function 𝑀 𝑎𝑝𝑆𝑡𝑎𝑡𝑒(𝐶, st) mapping a smart contract state to its own
state transaction together with the corresponding block, and a function 𝑀 𝑎𝑝𝑆𝐶(𝐶, 𝜑) mapping a
smart contract to its own smart contract transaction together with the corresponding block.
2
The information matching st𝜑 to 𝜑 can be the address addr𝜑 of 𝜑 inserted into the state st𝜑 during its creation.
4. The Redaction Technique of [2]
The idea of [2] is to set the hash function used to chain the different blocks in the blockchain, to be a
chameleon hash function.
We borrow the same idea of [2], and stress that the idea of using a hash function to chain blocks
in such a way that some form of consistency is ensured is used in most of the commonly known
blockchains. Then, a consensus mechanism is built on top of this hash-based chaining mechanism. A
validblock algorithm can be arbitrarily defined depending on the consensus mechanism used.
In the solution of [2], only a set of trusted authorities can redact the blockchain. Here, we report the
case of a single trusted authority. However, in [2] it is shown how to generalize it to a decentralized
setting using a secure multi-party computation protocol.
Ateniese et al. [2] extend the block definition of [24] as 𝐵 = (𝑠, 𝑥, 𝑐𝑡𝑟, (ℎ, 𝜈)), where the new
component (ℎ, 𝜈) is the hash/check pair for a chameleon hash. The hash function is defined to be a
chameleon hash (𝐻𝐺𝑒𝑛, 𝐻𝑎𝑠ℎ, 𝐻𝑉 𝑒𝑟, 𝐻𝐶𝑜𝑙), and the validation predicate for a block is the one used
for proof-of-work. Also, the extension of a blockchain is similar to the one described in Section 3.3.
Given a chain 𝐶 with head 𝐻𝑒𝑎𝑑(𝐶) = (𝑠, 𝑥, 𝑐𝑡𝑟, (ℎ, 𝜈)), the extension is obtained attaching a (valid)
block 𝐵 ′ = (𝑠′ , 𝑥′ , 𝑐𝑡𝑟′ , (ℎ′ , 𝜈 ′ )) such that 𝑠′ = 𝐻(𝑐𝑡𝑟, ℎ).
Their algorithm used to redact the blockchain takes as input a set of block indices 𝐼 and |𝐼| transaction
sets {𝑥′𝑖 }𝑖∈𝐼 that are going to replace the original transactions {𝑥𝑖 }𝑖∈𝐼 . For each block 𝐵𝑖 , the algorithm
generates a new collision 𝜈𝑖′ using the collision generation algorithm 𝐻𝐶𝑜𝑙 on input the trapdoor, the
hash ℎ𝑖 included in the 𝑖-th block, 𝑠𝑖 , the old collision value 𝜈𝑖 and the new set of transactions 𝑥′𝑖 . Then,
it generates a new block 𝐵𝑖′ = (𝑠𝑖 , 𝑥′𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖′ )) and outputs the modified chain 𝐶 ′ with the old
blocks 𝐵𝑖 replaced with the new redacted blocks 𝐵𝑖′ .
The formal description of the redaction algorithm3 of [2] is reported in Algorithm 1.
Data: The chain 𝐶 of length 𝑛, a set of block indices 𝐼 ⊆ [𝑛], a set of values {𝑥′𝑖 }𝑖∈𝐼 , and the
chameleon hash trapdoor key 𝑡𝑘.
Result: The redacted blockchain 𝐶 ′
𝐶 ′ ← 𝐶;
Parse 𝐶 ′ as (𝐵1 , . . . , 𝐵𝑛 );
for 𝑖 ∈ [𝑛] do
if 𝑖 ∈ 𝐼 then
Parse the 𝑖-th block of 𝐶 ′ as 𝐵𝑖 = (𝑠𝑖 , 𝑥𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖 ));
𝜈𝑖′ ← 𝐻𝐶𝑜𝑙(𝑡𝑘, (ℎ𝑖 , 𝑠𝑖 ||𝑥𝑖 , 𝜈𝑖 ), (𝑠𝑖 ||𝑥′𝑖 ));
𝐵𝑖′ = (𝑠𝑖 , 𝑥′𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖′ ));
𝐶 ′ ← 𝐶 ′⌈𝑛−𝑖+1 ||𝐵𝑖′ ||⌉𝑖 𝐶 ′ ;
end
end
Algorithm 1: Redaction algorithm from [2].
The above approach is very efficient and can be easily put into practice. Unfortunately, when the
blockchain enables computation of smart contract functions, we observe the following issue.
Let us assume that we have a smart contract 𝜑 stored in some block, and that a transaction 𝑡𝑥
appearing in a block 𝐵 changes the state of 𝜑 from some st to st′ . Let 𝑡𝑥 ˜ be a transaction inside
another block 𝐵 changing the state of 𝜑 from st to st . If the trusted authority redacts the block 𝐵
′ ′ ′′
by modifying 𝑡𝑥, then the resulting state might be different from st′ and in turn 𝑡𝑥˜ might be invalid of
anyway making updates that were not desired by the creator of that transaction, therefore leaving the
smart contract in a state that is inconsistent with the logic of the transactions that were proposed and
approved earlier, ending up to st′′ .
3
In [2] the authors further propose a solution for shrinking a blockchain that we do not report here due to its similarity with
the above redaction algorithm.
To guarantee blockchain consistency (without leaving invalid transactions or transactions doing
something undesired for their creators), the natural solution would require to detect all the correlated
transactions appearing after the modified transaction, and then either modify or remove such transac-
tions if invalid. As said in Section 1.2, such an approach might be extremely hard to implement and
moreover might lead to a huge number of delete transactions related to 𝜑.
5. Our Permissioned Smart-Contract-Enabled Blockchain Redaction
As we said, our solution can be used to improve the current state of the art in the case of redaction on
permissioned smart-contract-enabled blockchains.
From now on, we rely on a little abuse of notation to ensure good readability. We will use the original
definition of 𝑡𝑥 (i.e., 𝑡𝑥 = (addr, data, toaddr)), where data might be (𝑖, inp), everywhere except
when we feed 𝑡𝑥 as an input to a function. In such a case, we refer to the inp field of 𝑡𝑥.
Let us first consider a simplified version of the blockchain in which state transactions are not included
in blocks, but all the states can be inferred by looking at the smart-contract transactions coupled with
the standard transactions.
Let us assume that, at time 𝑡, we have a blockchain 𝐶 = (𝐵1 , . . . , 𝐵𝑡 ). Let us further assume that 𝐵𝑖 =
{𝑠𝑖 , 𝑥𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖 )}, for some 𝑖 ∈ [𝑡 − 2] contains a smart contract 𝜑. Let 𝐵𝑗 = {𝑠𝑗 , 𝑥𝑗 , 𝑐𝑡𝑟𝑗 , (ℎ, 𝜈)},
for some 𝑖 < 𝑗 < 𝑡 be the block containing a transaction 𝑡𝑥 that updates the state of 𝜑 from st𝑘𝜑 to
𝜑 , for some 𝑘 ∈ [𝑆𝑡𝐻𝑒𝑎𝑑(𝐶, 𝜑)]. Let 𝑡𝑥 be the transaction in a block 𝐵ℓ , for some 𝑗 < ℓ ≤ 𝑡 that
st𝑘+1 ˜
updates the state of 𝜑 from st𝑘+1 𝜑 to st𝑘+2
𝜑 .
In case of the redaction of block 𝐵𝑗 , if the transaction 𝑡𝑥 is modified, it might affect the state st𝑘+1 𝜑 .
In turn, it will also affect the consistency of transaction 𝑡𝑥. ˜
As already mentioned, our solution relies on a proof that 𝑡𝑥 ˜ is consistent with st𝑘+1 . This type of
𝜑
proof ensures that all the states subsequent to st𝑘+1 𝜑 are consistent w.r.t. a previous version of the
chain. We call this type of proof proof-of-consistency.
5.1. Proof of Consistency for Smart Contract States
Our proof-of-consistency can be implemented by relying on a SNARK for the Relation 1 described
below.
The statement consists of the transaction 𝑡𝑥 ˜ , two states st and st′′ , two functions 𝑓 and 𝑓 ′ (of the
same smart contract 𝜑), the head 𝑠 of the block 𝐵 to be redacted, and the chameleon hash ℎ together
with its public hash key ℎ𝑘 . The witness, instead, contains the original transaction set 𝑡𝑥 (before
redaction) of the block 𝐵, the redacted transaction 𝑡𝑥 inside 𝑥, and a state st′ . The relation shows that
the function 𝑓 , if triggered by the original transaction 𝑡𝑥 and the state st contained in the statement,
produces a state st′ . st′ is part of the witness since it cannot be computed anymore due to the fact that
the block containing 𝑡𝑥 ∈ 𝑥 will be redacted. The relation further shows that the transaction 𝑡𝑥 ˜ , if given
as an input to 𝑓 ′ together with the non-recomputable state st′ , will consistently produce st′′ . Finally,
to guarantee consistency with the block that will be redacted, the relation shows that the original 𝑥
containing the transaction 𝑡𝑥 that will be later modified produces the same hash ℎ that will appear later
in the redacted block, i.e., the relation shows that the transaction set 𝑥, in the witness, together with 𝑠
and the hash key ℎ𝑘, if given as input to 𝐻𝑎𝑠ℎ, produces a pair (ℎ, ·). During verification, the hash ℎ
to be placed in the statement will be taken from the redacted block. Relation 1 follows:
𝑓 (𝑡𝑥, st) = st′ ∧
{︃ ⃒ }︃
⃒
𝑅= ˜ , st, st′′ , 𝑓, 𝑓 ′ , 𝑠, ℎ𝑘, ℎ), (𝑥, 𝑡𝑥, st′ ))⃒⃒
((𝑡𝑥 𝑓 ′ (𝑡𝑥
˜ , st′ ) = st′′ ∧ . (1)
(ℎ, ·) = 𝐻𝑎𝑠ℎ(ℎ𝑘, (𝑠, 𝑥))
⃒
If we pose ourselves in the settings described at the beginning of the section, then st = st𝑘𝜑 ,
𝜑 , st = st𝜑 , and 𝑥 = 𝑥𝑖 . If a state transaction st updating st through 𝑡𝑥 is stored
st′ = st𝑘+1 ′′ 𝑘+2 ′
inside the blockchain, we have two different cases depending on what the governance wishes to redact:
• If the governance wishes to redact both the state st′ and 𝑡𝑥, the relation to be proven is the same
as above.
• If the governance wishes to redact 𝑡𝑥 but st′ shall remain unchanged in the chain, the relation is
the same as above except that st′ is part of the statement, not the witness.
In the following section, we present our extension of the redaction algorithm of Ateniese et al. with the
integration of our proof-of-consistency.
5.2. Our New Redaction Algorithm
The new redaction algorithm is run by the governance of the blockchain, knowing which blocks with
indexes in 𝐼 ⊆ [𝑛] shall be redacted, together with the new sets of transactions 𝑥′𝑖 for each 𝑖 ∈ 𝐼. For
each block 𝐵𝑖 , parsed as (𝑠𝑖 , 𝑥𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖 )), computes a new collision 𝜈𝑖′ using the trapdoor 𝑡𝑘, ℎ𝑖 , 𝑥𝑖 ,
the old collision 𝜈𝑖 and the new set of transaction 𝑥′𝑖 related to the 𝑖-th block. Then, for each transaction
𝑡𝑥𝑗 in 𝑥𝑗 to be modified with a different transaction 𝑡𝑥′𝑗 in 𝑥′𝑗 , the algorithm identifies the smart contract
𝜑 triggered by 𝑡𝑥𝑗 and the state stℓ𝜑 that is a state update from stℓ−1 𝜑 for some function 𝑓 ∈ 𝜑. Then,
finds for a transaction 𝑡𝑥 in some subsequent block triggering a function 𝑓 ′ ∈ 𝜑 updating stℓ𝜑 to stℓ+1 𝜑
and thus generates a proof-of-consistency showing that 𝑡𝑥𝑗 updates stℓ−1 𝜑 to st ℓ , 𝑡𝑥 updates stℓ to
𝜑 𝜑
stℓ+1
𝜑 , and the original transaction set 𝑥 𝑗 containing 𝑡𝑥 𝑗 , if given as input to 𝐻𝑎𝑠ℎ, lead to the value ℎ
contained in both the original and the redacted 𝑖-th block. The redaction procedure is formally reported
in Algorithm 2.
When dealing with redacted blockchains, we introduce four informal properties that we believe are
the most significant in our context.
Chain Growth: Any chain (either redacted or not) can always be extended with a new (valid) block
issued to the network.
Chain Consistency: Smart contract states must be consistent w.r.t. original data (i.e., existing data
before redaction).
Privacy of Original Data: The auxiliary redaction information should not revel any significant infor-
mation about original data that can not be inferred directly looking at the redacted blockchain.
Minimal Impact Redaction: The redaction procedure only modifies/deletes the minimal amount of
information that is explicitly required to be redacted.
We argue below why the above properties are satisfied by our redaction technique:
Chain Growth: Due to the chameleon property of the hash functions, the hash value of the blockchain
is never modified when transactions are redacted by the governance. Hence, any version of the
chain, either redacted or not, will have the same hash value. Hence, the underlying consensus
mechanism can be used as it is to extend any chain roaming around the network.
Chain Consistency: Chain consistency is guaranteed by the consistency of states of the smart con-
tracts w.r.t their input transactions and the consistency between blockchain hash and data.
Regarding state consistency, when the chain is not redacted, nodes can re-run a smart contract
from the standard transactions that are triggering such a smart contract and check whether all
the intermediate states are consistent, and then check that the blockchain data matches the hash
stored in the chain.
On the other hand, if the chain is redacted, nodes can verify that state consistency was guaranteed
in the chain containing the original transactions thanks to the completeness of the proofs-of-
consistency published by the governance as auxiliary redaction information.
Data: The chain 𝐶 of length 𝑛, a set of block indices 𝐼 ⊆ [𝑛], a set of values {𝑥′𝑖 }𝑖∈𝐼 , and the
chameleon hash trapdoor key 𝑡𝑘.
Result: The redacted blockchain 𝐶 ′ and auxiliary redaction information Π.
𝐶 ′ ← 𝐶;
Π ← {};
Parse 𝐶 ′ as (𝐵1 , . . . , 𝐵𝑛 );
for 𝑖 ∈ 𝐼 do
Parse 𝐵𝑖 as (𝑠𝑖 , 𝑥𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖 ));
Parse 𝑥𝑖 as (𝑡𝑥1 , . . . , 𝑡𝑥𝑚 );
Parse 𝑥′𝑖 as (𝑡𝑥′1 , . . . , 𝑡𝑥′𝑚 );
𝜈𝑖′ ← 𝐻𝐶𝑜𝑙(𝑡𝑘, (ℎ𝑖 , 𝑠𝑖 ||𝑥𝑖 , 𝜈𝑖 ), (𝑠𝑖 |𝑥′𝑖 ));
𝐵𝑖′ = (𝑠𝑖 , 𝑥′𝑖 , 𝑐𝑡𝑟𝑖 , (ℎ𝑖 , 𝜈𝑖′ ));
for 𝑗 ∈ [𝑚] do
if 𝑡𝑥𝑗 ̸= 𝑡𝑥′𝑗 then
Let 𝜑 = 𝑀 𝑎𝑝𝑇 𝑥𝑆𝐶(𝐶 ′ , 𝑡𝑥𝑗 );
if ∃𝑓 ∈ 𝜑 s.t. stℓ𝜑 = 𝑓 (stℓ−1 𝜑 , 𝑡𝑥𝑗 ) for some ℓ ∈ [𝑆𝑡𝐻𝑒𝑎𝑑(𝐶, 𝜑)] then
for 𝑘 ∈ {𝑖 + 1, . . . , 𝑛} do
if ∃𝑡𝑥 ∈ 𝐵𝑘 s.t. 𝑀 𝑎𝑝𝑇 𝑥𝑆𝐶(𝐶 ′ , 𝑡𝑥) = 𝜑 ∧ ∃𝑓 ′ ∈ 𝜑 s.t. stℓ+1 𝜑 = 𝑓 ′ (stℓ𝜑 , 𝑡𝑥)
then
Generate a proof 𝜋 for Relation 1 on input
((𝑡𝑥, stℓ−1 ℓ+1 ′ ℓ
𝜑 , st𝜑 , 𝑓, 𝑓 , 𝑠, ℎ𝑘, ℎ𝑖 ), (𝑥𝑖 , 𝑡𝑥𝑗 , st𝜑 ));
Π ← Π ∪ {𝜋};
break;
end
end
end
end
𝐶 ′ ← 𝐶 ′⌈𝑛−𝑖+1 ||𝐵𝑖′ ||⌉𝑖 𝐶 ′ ;
end
end
Algorithm 2: Redaction algorithm for a permissioned smart-contract-enabled blockchain.
The collision resistance property of the chameleon hash function and the knowledge soundness
of the proofs-of-consistency guarantee that an adversary can forge blockchain data without
knowing the trapdoor key (that is held by the trusted authority) only with negligible probability.
Privacy of Original Data: Thanks to the zero-knowledge property of SNARKs, the auxiliary redaction
information does not disclose any additional information about the original data that could not
already be inferred from the other still existing transactions.
Minimal-Impact Redaction: Our technique only deletes the interested information fixing the directly
affected transactions, without causing changes to indirectly affected transactions within the
blockchain.
6. Conclusions
In this paper, we have shown that the immutability of permissioned smart-contract-enabled blockchains
can be bypassed. First, we showed how previous techniques are insufficient when applied to a stateful
function deployed in a smart contract. Then, we showed how to use SNARKs in several interesting cases
(e.g., when a redaction consists of removing a transaction) to perform the redaction of a transaction
while maintaining consistency of other correlated transactions.
Further directions of great interest are: (i) extending the applicability of permissioned blockchain
redaction to cases that are not resolved by our work, (ii) extending our approach to permissionless
blockchains. Since this is a preliminary research paper, as a promising future research direction, we
aim to rigorously formalize the definitions introduced in Section 5.2 within the context of blockchain
redactions.
Acknowledgements. We thank Vincenzo Iovino for the insightful discussions we had about redaction
techniques in blockchains. The first author received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation program under project
PICOCRYPT (grant agreement No. 101001283), and from the Spanish Government under projects
PRODIGY (TED2021-132464B-I00) and ESPADA (PID2022-142290OB-I00). The last two projects are
co-funded by European Union EIE, and NextGenerationEU/PRTR funds. The second author received
funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation program under project PROCONTRA (grant agreement No. 885666) and by the project
PARTHENON (B53D23013000006), under the MUR National Recovery and Resilience Plan funded by
the European Union - NextGenerationEU. The third author received funding from project SERICS
(PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union
- NextGenerationEU. The last author is member of the Gruppo Nazionale Calcolo Scientifico-Istituto
Nazionale di Alta Matematica (GNCS-INdAM) and his research contribution on this work is financially
supported under the National Recovery and Resilience Plan (NRRP), Mission 4, Component 2, Investment
1.1, Call for tender No. 104 published on 2.2.2022 by the Italian Ministry of University and Research
(MUR), funded by the European Union – NextGenerationEU– Project Title “PARTHENON” – CUP
D53D23008610006 - Grant Assignment Decree No. 959 adopted on June 30, 2023 by the Italian Ministry
of Ministry of University and Research (MUR).
References
[1] R. Matzutt, J. Hiller, M. Henze, J. H. Ziegeldorf, D. Müllmann, O. Hohlfeld, K. Wehrle, A Quantitative
Analysis of the Impact of Arbitrary Blockchain Content on Bitcoin, in: FC 2018, volume 10957 of
LNCS, Springer, 2018, pp. 420–438.
[2] G. Ateniese, B. Magri, D. Venturi, E. R. Andrade, Redactable Blockchain - or - Rewriting History
in Bitcoin and Friends, in: EuroS&P, IEEE, 2017, pp. 111–126.
[3] J. Ma, S. Xu, J. Ning, X. Huang, R. H. Deng, Redactable blockchain in decentralized setting, IEEE
Transactions on Information Forensics and Security 17 (2022) 1227–1242.
[4] G. Zhou, X. Ding, H. Han, A. Zhu, Fine-grained redactable blockchain using trapdoor-hash, IEEE
Internet of Things Journal 10 (2023) 21203–21216.
[5] D. Zhang, J. Le, X. Lei, T. Xiang, X. Liao, Secure redactable blockchain with dynamic support,
IEEE Transactions on Dependable and Secure Computing (2023) 1–14.
[6] C. Peng, H. Xu, H. Liao, J. Tang, T. Tang, Redactable blockchain in the permissioned setting, in:
Science of Cyber Security, Springer, 2023, pp. 460–477.
[7] X. Wu, X. Du, Q. Yang, N. Wang, W. Wang, Redactable consortium blockchain based on verifiable
distributed chameleon hash functions, Journal of Parallel and Distributed Computing 183 (2024)
104777.
[8] Y. Dong, Y. Li, Y. Cheng, D. Yu, Redactable consortium blockchain with access control: Leveraging
chameleon hash and multi-authority attribute-based encryption, High-Confidence Computing 4
(2024) 100168.
[9] I. Visconti, The right to be zero-knowledge forgotten, in: Proceedings of the 2024 International
Conference on Availability, Reliability and Security (ARES), ACM, 2024. doi:10.1145/3664476.
3669973.
[10] V. Botta, V. Iovino, I. Visconti, Towards data redaction in bitcoin, IEEE Trans. Netw. Serv. Manag.
19 (2022) 3872–3883.
[11] I. Puddu, A. Dmitrienko, S. Capkun, 𝜇chain: How to Forget without Hard Forks, IACR ePrint
(2017) 106.
[12] D. Deuber, B. Magri, S. A. K. Thyagarajan, Redactable blockchain in the permissionless setting, in:
S&P 2019, IEEE, 2019, pp. 124–138.
[13] M. S. Dousti, A. Küpçü, Moderated Redactable Blockchains: A Definitional Framework with an
Efficient Construct, in: ESORICS International Workshops, volume 12484 of LNCS, Springer, 2020,
pp. 355–373.
[14] S. A. K. Thyagarajan, A. Bhat, B. Magri, D. Tschudi, A. Kate, Reparo: Publicly Verifiable Layer to
Repair Blockchains, in: FC 2021, volume 12675 of LNCS, Springer, 2021, pp. 37–56.
[15] D. Grigoriev, V. Shpilrain, RSA and redactable blockchains, Int. J. Comput. Math. Comput. Syst.
Theory 6 (2021) 1–6.
[16] E. Larraia, M. S. Kiraz, O. Vaughan, How to Redact the Bitcoin Backbone Protocol, in: IEEE
International Conference on Blockchain and Cryptocurrency (ICBC), IEEE, 2024.
[17] W. Wang, J. Duan, L. Wang, X. Hu, H. Peng, Strongly synchronized redactable blockchain based
on verifiable delay functions, IEEE Internet of Things Journal 10 (2023) 16778–16792.
[18] W. Dai, J. Liu, Y. Zhou, K.-K. R. Choo, X. Xie, D. Zou, H. Jin, Prbfpt: A practical redactable
blockchain framework with a public trapdoor, IEEE Transactions on Information Forensics and
Security 19 (2024) 2425–2437.
[19] R. Gennaro, C. Gentry, B. Parno, M. Raykova, Quadratic Span Programs and Succinct NIZKs
without PCPs, in: EUROCRYPT 2013, volume 7881 of LNCS, Springer, 2013, pp. 626–645.
[20] G. Danezis, C. Fournet, J. Groth, M. Kohlweiss, Square span programs with applications to succinct
NIZK arguments, in: ASIACRYPT 2014, volume 8873 of LNCS, Springer, 2014, pp. 532–550.
[21] J. Groth, On the size of pairing-based non-interactive arguments, in: EUROCRYPT 2016, volume
9666 of LNCS, Springer, 2016, pp. 305–326.
[22] A. Kothapalli, S. Setty, I. Tzialla, Nova: Recursive zero-knowledge arguments from folding schemes,
in: CRYPTO 2022, Springer, 2022, pp. 359–388.
[23] H. Krawczyk, T. Rabin, Chameleon signatures, in: NDSS 2000, The Internet Society, 2000.
[24] J. A. Garay, A. Kiayias, N. Leonardos, The bitcoin backbone protocol: Analysis and applications,
in: EUROCRYPT 2015, volume 9057 of LNCS, Springer, 2015, pp. 281–310.