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 efective 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.
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. [
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.
Let us give a high-level description of the chameleon-hash-function-based solution of [
Since it is needed that the governance is known and fixed, this result is mainly suitable for
permissioned blockchains, even though, as the authors of [
We observe that even though one limits the usage of the techniques in [
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-contractenabled blockchains without afecting other transactions and still maintaining the smart contract in a consistent state?
We obviously require that all redaction operations do not afect 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.
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 [
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 afected transaction is 2 (other transactions updating the counter and other transactions using the next values of the counter are indirectly afected) 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 eficiently 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 diferent 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.
Ateniese et al. [
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, efectively 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 [
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 [
Botta et al. [
Zhang et al. [
Zhou et al. [
Peng et al. [
Wang et al. [17] proposed a diferent 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 eficient, 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 [
We will denote by [] the set {1, . . . , }.
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 afecting knowledge soundness and zero knowledge, a SNARK is usually referred as STARK, where the letter “T” remarks the transparency of the involved CRS.
Chameleon hash functions were first introduced in [ 23]. In this work, we report the definition from
[
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 collisionresistant 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 ℎ.
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 = [
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. 2The information matching st to can be the address addr of inserted into the state st during its creation.
The idea of [
We borrow the same idea of [
In the solution of [
Ateniese et al. [
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 [
Result: The redacted blockchain ′ ′ ← ; Parse ′ as (1, . . . , ); for ∈ [] do if ∈ then
Parse the -th block of ′ as = (, , , (ℎ, )); ′ ← (, (ℎ, ||, ), (||′)); ′ = (, ′, , (ℎ, ′)); ′ ← ′⌈− +1||′||⌉′; end end
The above approach is very eficient 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 diferent 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′′.
3In [
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 transactions 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 .
updates the state of from st+1 to st+2.
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 st+1, for some ∈ [(, )]. Let ˜ be the transaction in a block ℓ, for some < ℓ ≤ that
In case of the redaction of block , if the transaction is modified, it might afect the state st+1. In turn, it will also afect 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.
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+1, st′′ = st+2, and = . If a state transaction st′ updating st through is stored inside the blockchain, we have two diferent 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.
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 diferent 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, ifnds 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 information 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 contracts 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-ofconsistency 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, stℓ+1, , ′, , ℎ, ℎ), (, , stℓ)); Π ← Π ∪ { }; break; end end end end ′ ← end
′⌈− +1||′||⌉′; 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 afected transactions, without causing changes to indirectly afected transactions within the blockchain.
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 insuficient 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). [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 Eficient 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.