# Fine-Grained and Controllably Redactable Blockchain with Harmful Data Forced Removal

Authors: Huiying Hou; Shidi Hao; Jiaming Yuan; Shengmin Xu; Yunlei Zhao
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Notoriously, immutability is one of the most striking properties of blockchains. As the data contained in blockchains may be compelled to redact for personal and legal reasons, immutability needs to be skillfully broken. In most existing redactable blockchains, fine-grained redaction and effective deletion of harmful data are mutually exclusive. To close the gap, we propose a fine-grained and controllably redactable blockchain with harmful data forced removal. In the scheme, the originator of the transaction has fine-grained control over who can perform the redaction and which portions of the transaction can be redacted. The redaction transaction is performed after collecting enough votes from miners. All users can provide the index of the block containing the harmful data to receive rewards, which are borne by the malicious user who initially posted the data. Miners can forcibly remove the harmful data based on the index. The malicious user will be blacklisted if the reward is not paid within a period of time, and any transaction about such user will not be performed later. In addition, the scheme supports the redaction of additional data and unexpended transaction output (UTXO) simultaneously. We demonstrate that the scheme is secure and feasible via formal security analysis and proof-of-concept implementation.


---

## Body

## 1. Introduction

The first application of blockchains is Bitcoin [1, 2], which has revolutionized the financial industry. Ever since, hundreds of such cryptocurrencies rise which do not rely on a central trusted authority. The applications of blockchains go far beyond their use in cryptocurrencies [3–6]. Recently, blockchains have entered numerous domains of applications, such as supply chains, digital twins, insurance, healthcare, or energy. In brief, a blockchain is a decentralized, distributed, potentially public, and immutable log of objects.Blockchains can be of different types. They can be public as Bitcoin or Ethereum, where the consensus protocol is executed between many pseudonymous participants. Here, the blockchain can be read and written by everyone. Such public blockchains can also be viewed as permissionless because everyone can join the system, participate in the consensus protocol, and establish smart contracts. Blockchains, however, can also be private (also called enterprise or permissioned blockchains) such as Hyperledger, Ethereum Enterprise, Ripple, or Quorum. Here, all the participants and their (digital) identities are known to one or more trusted organizations. Actors have write and read permissions. Such private blockchains can thus be viewed as permissioned because they restrict the actors who can contribute to the consensus on the system state to validate the block transactions. Once an object (such as a block or a transaction) is included in the blockchain (be it private or public), it is persisted and cannot be altered ever again. While immutability is a crucial property of the blockchain, it is often desirable to allow breaking the immutability for personal and legal reasons.The debate about the immutability of the blockchain becomes more acute due to the adoption of the General Data Protection Regulation (GDPR) by the European Union (EU). Several provisions of the GDPR are essentially incompatible with the immutable blockchains. In particular, the GDPR imposes that the data have the right to be forgotten, while blockchains such as Bitcoin and Ethereum do not allow to remove any data [7]. In addition, by using the immutability of a blockchain, malicious users can broadcast illegal or harmful data, such as (child) pornography and violence information around the world by spending a small fee. The data will be permanently stored and cannot be modified after they are stable on the chain. It is an enormous challenge for law enforcement agencies such as Interpol [8, 9]. One idea is to “filter” all incoming data to check for malicious content before inserting the data into the chain. However, the recent work of Matzutt et al. [10] showed that the above idea is not feasible. Hence, how to skillfully break the immutability of blockchains is an important and urgent problem to be solved.To solve the above problem, Ateniese et al. [11] first introduced the concept of redactable blockchain and proposed an elegant solution based on chameleon hash functions [12]. The solution addresses the redaction problem of blockchains at the block level, which is coarse grained.The redactable blockchain should meet the following two properties: (1) the originator of a transaction can specify a fine-grained access control policy about who can modify the transaction and which portions of the transaction can be redacted; (2) the harmful information contained in the previous block can be removed. Unfortunately, there is no redactable blockchain that meets both requirements.In this paper, we explored how to effectively realize the fine-grained redactable blockchain. Our thought for realizing fine-grained redaction and effective deletion of harmful data simultaneously is shown in Figure1. In order to support fine-grained access control, a promising way is to adopt the policy-based chameleon hash function (PCH) [13], which allows the originator of a transaction to specify a fine-grained access control policy about who can modify the transaction. However, it may incur the following issue by adopting the PCH. The malicious originator of the transaction may design an access policy that only allows him/her to modify the transaction to store undeletable harmful information in a blockchain. This does not satisfy the second property. To solve the above problem, we try to combine the technology proposed in [14]. The technology allows all users to create removal transactions by spending some transaction fees. Miners then vote on the transaction, and the harmful information is removed if enough votes are collected within a period of time. Obviously, this does not motivate users to actively remove harmful information from the chain because the user is not only rewarded for doing so but also needs to spend transaction fees. In order to motivate users, in this paper, the users create removal transactions without spending transaction fees. If the transaction passes the verification, the originator will obtain the reward paid by the malicious user who posted the harmful information. In addition, this technique only supports the deletion of additional information in the block and needs to store some “old state,” that is, the hash value of the original transaction.Figure 1
The flowchart of the idea.In practice, the redactable blockchains should meet the following three properties: (1) the originator of a transaction can specify a fine-grained access control policy about who can modify the transaction and which portions of the transaction can be redacted; (2) the harmful information contained in the previous block can be removed; (3) the data type that can be redacted is various. In order to support the redaction of various data types, we adopt the idea of the scheme in [15]. In this paper, the blockchain protocol not only supports removing additional information of the block but also redacting UTXO in the transaction. In order to reduce the storage space, we try to adopt a policy-based sanitizable signature [16]. However, in this way, the number of blocks of the signed data cannot be changed, and the set of inadmissible blocks needs to be stored. To solve this problem, we propose an improved policy-based sanitizable signature which allows that the number of blocks of the message m can be changed.


### 1.1. Contributions

In this paper, we first explore how to effectively realize the fine-grained redaction of blockchains while removing the harmful data. We then propose a fine-grained and controllably redactable blockchain protocol with harmful data forced removal. In a nutshell, the contribution of this paper can be summarized as follows:(i)
We propose a fine-grained and controllably redactable blockchain protocol with harmful data forced removal. Our scheme not only supports the usual redaction of transactions but also the forced removal of harmful information in the blockchain. The originator of the transaction can specify a fine-grained access control structure about who can redact the transaction and which portions of the transaction can be redacted. Authorized users may spend transaction fees to initiate a redaction transaction to redact the above transaction. Any user can initiate a transaction that contains the index of the block included harmful information without spending transaction fees. If the block does contain the harmful information, the miner who creates the new block can forcibly delete the harmful information. Thus, the harmful data can be removed; even the malicious users specify an access control that only they can modify the data. The user who provided the index of the block can receive the reward which is borne by the malicious user who initially posted the data. The malicious user will be blacklisted if the rewards are not paid within a period of time, and any transaction about the user will not be performed later. Furthermore, the scheme supports not only the redaction of additional data but also UTXO, i.e., unspent transaction outputs.(ii)
We present an improved policy-based sanitizable signature scheme, which is based on the scheme in [16]. In our scheme, the number of blocks of the signed data can be changed, and the set of inadmissible blocks does not need to be stored. Users who satisfy the access control policy can modify the portions of the signed data that are allowed to be modified. The authorized users can generate the valid signatures for the modified data without interacting with the original signer. The data owner does not need to collect the identities of the candidate authorized users in advance as the proxy signature schemes would require.(iii)
We demonstrate that the proposed scheme is secure and feasible via formal security analysis and proof-of-concept implementation. Specifically, we implement a full-fledged blockchain system, which achieves all the basic functionalities of Ethereum Enterprise. Separately, the blockchain system, including a subset of Ethereum Enterprise’s script language, allows the authorized user to redact the transaction and the miner to delete the harmful data. We evaluate the performance of the blockchain system for chain validation in different scenarios. The results show that the redactable blockchain protocol produces only an insignificant (no more than 3.8%) overhead compared to the immutable blockchain.


### 1.2. Related Work

The concept of sanitizable signature was introduced by Ateniese et al. [17]. A sanitizable signature scheme allows a sanitizer to update the signed data without interacting with the original signer. In order to ensure the security of the scheme, two necessary security requirements are defined in their scheme: (1) unforgeability, that is, only authorized sanitizers can generate the new valid signatures for the updated data; (2) transparency, that is, the updated data and their signatures are indistinguishable from the original information and corresponding signatures. Unfortunately, they did not give a complete definition of the sanitizable signature nor did they provide the formal security analysis. Brzuska et al. [18, 19] provided the formal definition of sanitizable signatures and gave the formalized definition of the basic security requirements. They introduced five formal security requirements, unforgeability, immutability, privacy, transparency, and accountability, and analyzed the relationships between these security requirements. Canard et al. [20] proposed a generic construction of the trapdoor sanitizable signature. In this scheme, the sanitizer can generate the valid signature for the updated data after receiving the trapdoor key from the original signer. Using an accountable chameleon hash, Lai et al. [21] proposed an accountable trapdoor sanitizable signature. However, neither of the above two schemes gives the concrete construction of the sanitizable signature. After that, many concrete sanitizable signature schemes were proposed [22–24]. All of the above sanitizable schemes are not suitable for blockchain rewriting since none of the aforementioned schemes support fine-grained control over candidate sanitizers.Attribute-based encryption schemes can provide fine-grained access control [25–27]. In order to provide fine-grained access control, some attribute-based sanitizable signature schemes are proposed [16, 28–30]. The scheme in [28] did not give the specific construct of the attribute-based sanitizable signature. The scheme in [29] did not support the expressive access structure. The scheme in [30] only provided an all-or-nothing solution for data modification. The number of blocks of the signed data cannot be changed, and the set of inadmissible blocks needs to be stored in [16]. In a real environment of blockchain rewriting, the number of blocks of the transaction may be changed, and the set of inadmissible blocks does not need to be contained in its signature. Therefore, in this paper, we improve the policy-based sanitizable signature scheme [16] and propose an improved policy-based sanitizable signature. In this paper, the number of blocks of the signed data can be changed, and the set of inadmissible blocks does not need to be stored. Furthermore, we present a fine-grained and controllably redactable blockchain protocol with harmful data forced removal based on the improved policy-based sanitizable signature scheme.


### 1.3. Organization

The rest of this paper is organized as follows. InSection 2, we briefly review the preliminaries required in this paper. The system model and design goals are given in Section 3. In Section 4, we introduce the proposed improved policy-based sanitizable signature scheme. We describe the proposed blockchain protocol in Section 5. In Section 6, we introduce the security analysis of the proposed protocol. We evaluate the performance of the proposed protocol in Section 7. Finally, we come to the conclusion in Section 8.


## 1.1. Contributions

In this paper, we first explore how to effectively realize the fine-grained redaction of blockchains while removing the harmful data. We then propose a fine-grained and controllably redactable blockchain protocol with harmful data forced removal. In a nutshell, the contribution of this paper can be summarized as follows:(i)
We propose a fine-grained and controllably redactable blockchain protocol with harmful data forced removal. Our scheme not only supports the usual redaction of transactions but also the forced removal of harmful information in the blockchain. The originator of the transaction can specify a fine-grained access control structure about who can redact the transaction and which portions of the transaction can be redacted. Authorized users may spend transaction fees to initiate a redaction transaction to redact the above transaction. Any user can initiate a transaction that contains the index of the block included harmful information without spending transaction fees. If the block does contain the harmful information, the miner who creates the new block can forcibly delete the harmful information. Thus, the harmful data can be removed; even the malicious users specify an access control that only they can modify the data. The user who provided the index of the block can receive the reward which is borne by the malicious user who initially posted the data. The malicious user will be blacklisted if the rewards are not paid within a period of time, and any transaction about the user will not be performed later. Furthermore, the scheme supports not only the redaction of additional data but also UTXO, i.e., unspent transaction outputs.(ii)
We present an improved policy-based sanitizable signature scheme, which is based on the scheme in [16]. In our scheme, the number of blocks of the signed data can be changed, and the set of inadmissible blocks does not need to be stored. Users who satisfy the access control policy can modify the portions of the signed data that are allowed to be modified. The authorized users can generate the valid signatures for the modified data without interacting with the original signer. The data owner does not need to collect the identities of the candidate authorized users in advance as the proxy signature schemes would require.(iii)
We demonstrate that the proposed scheme is secure and feasible via formal security analysis and proof-of-concept implementation. Specifically, we implement a full-fledged blockchain system, which achieves all the basic functionalities of Ethereum Enterprise. Separately, the blockchain system, including a subset of Ethereum Enterprise’s script language, allows the authorized user to redact the transaction and the miner to delete the harmful data. We evaluate the performance of the blockchain system for chain validation in different scenarios. The results show that the redactable blockchain protocol produces only an insignificant (no more than 3.8%) overhead compared to the immutable blockchain.


## 1.2. Related Work

The concept of sanitizable signature was introduced by Ateniese et al. [17]. A sanitizable signature scheme allows a sanitizer to update the signed data without interacting with the original signer. In order to ensure the security of the scheme, two necessary security requirements are defined in their scheme: (1) unforgeability, that is, only authorized sanitizers can generate the new valid signatures for the updated data; (2) transparency, that is, the updated data and their signatures are indistinguishable from the original information and corresponding signatures. Unfortunately, they did not give a complete definition of the sanitizable signature nor did they provide the formal security analysis. Brzuska et al. [18, 19] provided the formal definition of sanitizable signatures and gave the formalized definition of the basic security requirements. They introduced five formal security requirements, unforgeability, immutability, privacy, transparency, and accountability, and analyzed the relationships between these security requirements. Canard et al. [20] proposed a generic construction of the trapdoor sanitizable signature. In this scheme, the sanitizer can generate the valid signature for the updated data after receiving the trapdoor key from the original signer. Using an accountable chameleon hash, Lai et al. [21] proposed an accountable trapdoor sanitizable signature. However, neither of the above two schemes gives the concrete construction of the sanitizable signature. After that, many concrete sanitizable signature schemes were proposed [22–24]. All of the above sanitizable schemes are not suitable for blockchain rewriting since none of the aforementioned schemes support fine-grained control over candidate sanitizers.Attribute-based encryption schemes can provide fine-grained access control [25–27]. In order to provide fine-grained access control, some attribute-based sanitizable signature schemes are proposed [16, 28–30]. The scheme in [28] did not give the specific construct of the attribute-based sanitizable signature. The scheme in [29] did not support the expressive access structure. The scheme in [30] only provided an all-or-nothing solution for data modification. The number of blocks of the signed data cannot be changed, and the set of inadmissible blocks needs to be stored in [16]. In a real environment of blockchain rewriting, the number of blocks of the transaction may be changed, and the set of inadmissible blocks does not need to be contained in its signature. Therefore, in this paper, we improve the policy-based sanitizable signature scheme [16] and propose an improved policy-based sanitizable signature. In this paper, the number of blocks of the signed data can be changed, and the set of inadmissible blocks does not need to be stored. Furthermore, we present a fine-grained and controllably redactable blockchain protocol with harmful data forced removal based on the improved policy-based sanitizable signature scheme.


## 1.3. Organization

The rest of this paper is organized as follows. InSection 2, we briefly review the preliminaries required in this paper. The system model and design goals are given in Section 3. In Section 4, we introduce the proposed improved policy-based sanitizable signature scheme. We describe the proposed blockchain protocol in Section 5. In Section 6, we introduce the security analysis of the proposed protocol. We evaluate the performance of the proposed protocol in Section 7. Finally, we come to the conclusion in Section 8.


## 2. Preliminaries

### 2.1. Notions

We list the notations used in our scheme in Table1.Table 1
Notations.
NotationMeaningAA monotone collectionUThe attributes’ universeΠA public key encryption schemekThe security parameterPPΠThe public parameters ofΠpkΠ,skΠThe public and private key ofΠmThe messagecThe ciphertextΣA digital signature schemePPΣThe public parameters ofΣpkΣ,skΣThe signer’s public and private key inΣσThe signature inΣLA NP-languageΩA noninteractive proof system forLcrsΩA common reference stringxThe statementωThe corresponding witnessπThe proofPPPCHThe public parameters of PCHskPCH,pkPCHThe master key pair of PCHSThe set of attributesskSThe user’s secret key in PCHhThe hash valuerThe randomnessm′The modified messager′The new randomnessPPP3SThe public parameters of P3SskP3S,pkP3SThe master key pair of P3SskP3Ssig,pkP3SsigThe signer’s key pair in P3SskP3Ssan,pkP3SsanThe sanitizer’s key pair in P3SMThe description of modification


### 2.2. Access Structure

A collectionA∈2U\∅ is an access structure on U, where U denotes attributes’ universe. If a set is contained in A, it is the authorized set. Otherwise, it is an unauthorized set. A collection A is monotone if C∈A for ∀B,C∈A and B⊆C.


### 2.3. Public Key Encryption

A public key encryption schemeΠ consists of the following five algorithms:(i)
PPGenΠ1κ: this algorithm takes the security parameter κ as the input and outputs the public parameters PPΠ.(ii)
KGenΠPPΠ: this algorithm takes the public parameters PPΠ as the input and outputs the public and private key pkΠ,skΠ.(iii)
EncΠpkΠ,m: this algorithm takes the public key pkΠ and the message m as the input and outputs a ciphertext c.(iv)
DecΠskΠ,c: this algorithm takes the private key skΠ and the ciphertext c as the input and outputs the message m.(v)
KVrfΠskΠ,pkΠ: this algorithm takes the public and private key pkΠ,skΠ as the input and outputs 1 if skΠ belongs to pkΠ. Otherwise, it outputs 0.The detailed definition of correctness and security of the public key encryption (PKE) is given in [16]. In this paper, we require correctness and IND-CCA2 security for PKE.Definition 1.
(Π IND-CCA2 security). A public encryption scheme Π is IND-CCA2 secure [16] if for any probabilistic polynomial-time (PPT) adversary A, there exists a negligible function ν such that(1)PrExpA,ΠIND−CCA2k=1−12≤νk.
The corresponding experiment is depicted in Figure2.Figure 2
Π IND-CCA2 security.


### 2.4. Digital Signature

A digital signature schemeΣ consists of the following four algorithms:(i)
PPGenΣ1κ: this algorithm takes the security parameter κ as the input and outputs the public parameters PPΣ.(ii)
KGenΣPPΣ: this algorithm takes the public parameters PPΣ as the input and outputs signer’s public and private key pkΣ,skΣ.(iii)
SignΣskΣ,m: this algorithm takes the private key skΣ and the message m as the input and outputs the signature σ.(iv)
VerfΣpkΣ,m,σ: this algorithm takes the public key pkΣ, the message m, and the signature σ as the input and outputs 1 if σ is valid. Otherwise, it outputs 0.The formal security definition of the digital signature is given in [16]. In this paper, we require correctness and existential unforgeability (eUNF-CMA) for the digital signature.Definition 2.
(Σ unforgeability). A digital signature scheme Σ is unforgeable [16] if for any PPT adversary A, there exists a negligible function ν such that(2)PrExpA,ΣeUNF−CMAk=1≤νk.
The corresponding experiment is depicted in Figure3.Figure 3
Σ unforgeability.


### 2.5. Noninteractive Zero-Knowledge Proof (NIZK)

LetL=x|∃ω:Rx,w=1, where L is a NP-language with associated witness relation R. A noninteractive proof system Ω for the language L consists of the following three algorithms:(i)
PPGenΩ1κ: this algorithm takes the security parameter κ as the input and outputs the common reference string (CRS) crsΩ.(ii)
ProveΩcrsΩ,x,ω: this algorithm takes CRS crsΩ, the statement x, and the corresponding witness ω as the input and outputs the proof π.(iii)
VerifyΩcrsΩ,x,π: this algorithm takes CRS crsΩ, the statement x, and the proof π as the input and outputs 1 if π is valid. Otherwise, it outputs 0.The security of the noninteractive zero-knowledge proof (NIZK) is given in [16]. In this paper, we require completeness for NIZK. In addition to completeness, we require two standard security notions for zero-knowledge proofs of knowledge: zero knowledge and simulation-sound extractability. We define them analogous to the definitions given in [16]. Informally speaking, zero knowledge says that the receiver of the proof π does not learn anything except the validity of the statement.Definition 3.
(completeness). A noninteractive proof system is called complete if for allk∈N, crsΩ←rPPGen1k, x∈L, ω such that Rx,ω=1, π←rProveΩcrsΩ,x,ω, it holds that VerifyΩcrsΩ,x,π.


### 2.6. Policy-Based Chameleon Hashes

A policy-based chameleon hash (PCH) allows the user, who owns attributes’ set that satisfied the access structure, to compute a hash collision [13]. Specifically, a PCH contains the following six PPT algorithms:(i)
PPGenPCH1κ: this is the public parameters’ generation algorithm. It takes the security parameter κ as the input and outputs the public parameters PPPCH.(ii)
MKeyGenPCHPPPCH: this is the master key generation algorithm. It takes the public parameter PPPCH as the input and outputs the master key pair skPCH,pkPCH.(iii)
KGenPCHskPCH,S: this is the user’s secret key generation algorithm. It takes the master secret key skPCH and the set of attributes S⊆U as the input and outputs the user’s secret key skS.(iv)
HashPCHpkPCH,A,m: this is the hash algorithm. It takes the master public key pkPCH, the access structure A∈2U\∅, and the message m as the input and outputs the hash value h and the randomness r.(v)
VerifyPCHpkPCH,m,h,r: this is the verification algorithm. It takes the master public key pkPCH, the message m, the hash value h, and the randomness r as the input and outputs a bit b=1 if h and r are valid. Otherwise, b=0.(vi)
AdaptPCHpkPCH,skS,m,m′,h,r: this is the adaption algorithm. It takes the public key pkPCH, the user’s secret key skS, the message m, the modified message m′, the hash value h, and some randomness r as the input and outputs a new randomness r′.The detailed definition of correctness and security of the policy-based chameleon hash is given in [13].


### 2.7. Policy-Based Sanitizable Signature

A policy-based sanitizable signature (P3S) allows the user, who owns attributes’ set that satisfied the access structure, to modify the data and generate the valid signatures for the modified data [16]. Specifically, a P3S contains the following ten PPT algorithms:(i)
ParGenP3S1λ: this is the public parameters’ generation algorithm. It takes the security parameter λ as the input and outputs the public parameters PPP3S.(ii)
SetupP3SPPP3S: this is the master key generation algorithm. It takes the public parameters PPP3S as the input and outputs the master key pair skP3S,pkP3S.(iii)
KGenSigP3SPPP3S: this is the signer’s key pair generation algorithm. It takes the public parameters PPP3S as the input and outputs the signer’s key pair skP3Ssig,pkP3Ssig.(iv)
KGenSanP3SPPP3S: this is the sanitizer’s key pair generation algorithm. It takes the public parameters PPP3S as the input and outputs the sanitizer’s key pair skP3Ssan,pkP3Ssan.(v)
SignP3SPPP3S,skP3Ssig,m,A,A: this is the signing algorithm. It takes the public parameters PPP3S, the signer’s secret key skP3Ssig, the message m, the description of admission A, and the access structure A as the input and outputs a signature σ.(vi)
AddSanP3SskP3S,pkP3Ssan,S: this is the secret sanitizing key generation algorithm. It takes the master secret key skP3S, the sanitizer’s public key pkP3Ssan, and the set of attributes S as the input and outputs the secret sanitizing key skS for the sanitizer.(vii)
VerifyP3SpkP3S,pkP3Ssig,σ,m: this is the verification algorithm. It takes the master public key pkP3S, the signer’s public key pkP3Ssig, the signature σ, and the corresponding message m as the input and outputs a bit b=1 if the signature σ is valid. Otherwise, b=0.(viii)
SanitizeP3SpkP3S,pkP3Ssig,skP3Ssan,skS,σ,m,M: this is the new signature generation algorithm. It takes the master public key pkP3S, the signer’s public key pkP3Ssig, the sanitizer’s secret key skP3Ssan, the secret sanitizing key skS, the signature σ, the corresponding message m, and the description of modification M as the input and outputs the new signature σ′ for the modified message m′.(ix)
ProofP3SpkP3S,skP3Ssig,σ,m: this is the proof generation algorithm. It takes the master public key pkP3S, the signer’s secret key skP3Ssig, the signature σ, and the corresponding message m as the input and outputs the proof πP3S.(x)
JudgeP3SPPP3S,pkP3S,pkP3Ssig,σ,m,πP3S: this is the proof verification algorithm. It takes the public parameter PPP3S, the master public key pkP3S, the signer’s public key pkP3Ssig, the signature σ, the corresponding message m, and the proof πP3S as the input and outputs a bit b=1 if the proof πP3S is valid. Otherwise, b=0.The detailed definition of correctness and security of the policy-based sanitizable signature is given in [16].


### 2.8. Blockchain Protocol

LetΓ denote an immutable blockchain protocol such as Ethereum Enterprise. The nodes in the blockchain protocol obtain their local chain C based on a common genesis block. The nodes in the blockchain protocol collect transactions in the whole blockchain ecosystem and then package these transactions into a new block. The chain becomes longer as nodes agree on a new block. Nodes can access the blockchain protocol through the following interfaces.(i)
C′,⊥←Γ⋅updateChain: returns the chain C′ if it is the longer and the valid chain in the blockchain ecosystem. Otherwise, it returns ⊥.(ii)
0,1←Γ⋅validateChainC: takes the chain C as the input and outputs 1 iff the chain is valid according to the public set of rules.(iii)
0,1←Γ⋅validateBlockB: takes the block B as the input and outputs 1 iff the block is valid according to the public set of rules.(iv)
Γ⋅broadcastx: takes the transaction x as the input and broadcasts it to all nodes in the blockchain ecosystem.


## 2.1. Notions

We list the notations used in our scheme in Table1.Table 1
Notations.
NotationMeaningAA monotone collectionUThe attributes’ universeΠA public key encryption schemekThe security parameterPPΠThe public parameters ofΠpkΠ,skΠThe public and private key ofΠmThe messagecThe ciphertextΣA digital signature schemePPΣThe public parameters ofΣpkΣ,skΣThe signer’s public and private key inΣσThe signature inΣLA NP-languageΩA noninteractive proof system forLcrsΩA common reference stringxThe statementωThe corresponding witnessπThe proofPPPCHThe public parameters of PCHskPCH,pkPCHThe master key pair of PCHSThe set of attributesskSThe user’s secret key in PCHhThe hash valuerThe randomnessm′The modified messager′The new randomnessPPP3SThe public parameters of P3SskP3S,pkP3SThe master key pair of P3SskP3Ssig,pkP3SsigThe signer’s key pair in P3SskP3Ssan,pkP3SsanThe sanitizer’s key pair in P3SMThe description of modification


## 2.2. Access Structure

A collectionA∈2U\∅ is an access structure on U, where U denotes attributes’ universe. If a set is contained in A, it is the authorized set. Otherwise, it is an unauthorized set. A collection A is monotone if C∈A for ∀B,C∈A and B⊆C.


## 2.3. Public Key Encryption

A public key encryption schemeΠ consists of the following five algorithms:(i)
PPGenΠ1κ: this algorithm takes the security parameter κ as the input and outputs the public parameters PPΠ.(ii)
KGenΠPPΠ: this algorithm takes the public parameters PPΠ as the input and outputs the public and private key pkΠ,skΠ.(iii)
EncΠpkΠ,m: this algorithm takes the public key pkΠ and the message m as the input and outputs a ciphertext c.(iv)
DecΠskΠ,c: this algorithm takes the private key skΠ and the ciphertext c as the input and outputs the message m.(v)
KVrfΠskΠ,pkΠ: this algorithm takes the public and private key pkΠ,skΠ as the input and outputs 1 if skΠ belongs to pkΠ. Otherwise, it outputs 0.The detailed definition of correctness and security of the public key encryption (PKE) is given in [16]. In this paper, we require correctness and IND-CCA2 security for PKE.Definition 1.
(Π IND-CCA2 security). A public encryption scheme Π is IND-CCA2 secure [16] if for any probabilistic polynomial-time (PPT) adversary A, there exists a negligible function ν such that(1)PrExpA,ΠIND−CCA2k=1−12≤νk.
The corresponding experiment is depicted in Figure2.Figure 2
Π IND-CCA2 security.


## 2.4. Digital Signature

A digital signature schemeΣ consists of the following four algorithms:(i)
PPGenΣ1κ: this algorithm takes the security parameter κ as the input and outputs the public parameters PPΣ.(ii)
KGenΣPPΣ: this algorithm takes the public parameters PPΣ as the input and outputs signer’s public and private key pkΣ,skΣ.(iii)
SignΣskΣ,m: this algorithm takes the private key skΣ and the message m as the input and outputs the signature σ.(iv)
VerfΣpkΣ,m,σ: this algorithm takes the public key pkΣ, the message m, and the signature σ as the input and outputs 1 if σ is valid. Otherwise, it outputs 0.The formal security definition of the digital signature is given in [16]. In this paper, we require correctness and existential unforgeability (eUNF-CMA) for the digital signature.Definition 2.
(Σ unforgeability). A digital signature scheme Σ is unforgeable [16] if for any PPT adversary A, there exists a negligible function ν such that(2)PrExpA,ΣeUNF−CMAk=1≤νk.
The corresponding experiment is depicted in Figure3.Figure 3
Σ unforgeability.


## 2.5. Noninteractive Zero-Knowledge Proof (NIZK)

LetL=x|∃ω:Rx,w=1, where L is a NP-language with associated witness relation R. A noninteractive proof system Ω for the language L consists of the following three algorithms:(i)
PPGenΩ1κ: this algorithm takes the security parameter κ as the input and outputs the common reference string (CRS) crsΩ.(ii)
ProveΩcrsΩ,x,ω: this algorithm takes CRS crsΩ, the statement x, and the corresponding witness ω as the input and outputs the proof π.(iii)
VerifyΩcrsΩ,x,π: this algorithm takes CRS crsΩ, the statement x, and the proof π as the input and outputs 1 if π is valid. Otherwise, it outputs 0.The security of the noninteractive zero-knowledge proof (NIZK) is given in [16]. In this paper, we require completeness for NIZK. In addition to completeness, we require two standard security notions for zero-knowledge proofs of knowledge: zero knowledge and simulation-sound extractability. We define them analogous to the definitions given in [16]. Informally speaking, zero knowledge says that the receiver of the proof π does not learn anything except the validity of the statement.Definition 3.
(completeness). A noninteractive proof system is called complete if for allk∈N, crsΩ←rPPGen1k, x∈L, ω such that Rx,ω=1, π←rProveΩcrsΩ,x,ω, it holds that VerifyΩcrsΩ,x,π.


## 2.6. Policy-Based Chameleon Hashes

A policy-based chameleon hash (PCH) allows the user, who owns attributes’ set that satisfied the access structure, to compute a hash collision [13]. Specifically, a PCH contains the following six PPT algorithms:(i)
PPGenPCH1κ: this is the public parameters’ generation algorithm. It takes the security parameter κ as the input and outputs the public parameters PPPCH.(ii)
MKeyGenPCHPPPCH: this is the master key generation algorithm. It takes the public parameter PPPCH as the input and outputs the master key pair skPCH,pkPCH.(iii)
KGenPCHskPCH,S: this is the user’s secret key generation algorithm. It takes the master secret key skPCH and the set of attributes S⊆U as the input and outputs the user’s secret key skS.(iv)
HashPCHpkPCH,A,m: this is the hash algorithm. It takes the master public key pkPCH, the access structure A∈2U\∅, and the message m as the input and outputs the hash value h and the randomness r.(v)
VerifyPCHpkPCH,m,h,r: this is the verification algorithm. It takes the master public key pkPCH, the message m, the hash value h, and the randomness r as the input and outputs a bit b=1 if h and r are valid. Otherwise, b=0.(vi)
AdaptPCHpkPCH,skS,m,m′,h,r: this is the adaption algorithm. It takes the public key pkPCH, the user’s secret key skS, the message m, the modified message m′, the hash value h, and some randomness r as the input and outputs a new randomness r′.The detailed definition of correctness and security of the policy-based chameleon hash is given in [13].


## 2.7. Policy-Based Sanitizable Signature

A policy-based sanitizable signature (P3S) allows the user, who owns attributes’ set that satisfied the access structure, to modify the data and generate the valid signatures for the modified data [16]. Specifically, a P3S contains the following ten PPT algorithms:(i)
ParGenP3S1λ: this is the public parameters’ generation algorithm. It takes the security parameter λ as the input and outputs the public parameters PPP3S.(ii)
SetupP3SPPP3S: this is the master key generation algorithm. It takes the public parameters PPP3S as the input and outputs the master key pair skP3S,pkP3S.(iii)
KGenSigP3SPPP3S: this is the signer’s key pair generation algorithm. It takes the public parameters PPP3S as the input and outputs the signer’s key pair skP3Ssig,pkP3Ssig.(iv)
KGenSanP3SPPP3S: this is the sanitizer’s key pair generation algorithm. It takes the public parameters PPP3S as the input and outputs the sanitizer’s key pair skP3Ssan,pkP3Ssan.(v)
SignP3SPPP3S,skP3Ssig,m,A,A: this is the signing algorithm. It takes the public parameters PPP3S, the signer’s secret key skP3Ssig, the message m, the description of admission A, and the access structure A as the input and outputs a signature σ.(vi)
AddSanP3SskP3S,pkP3Ssan,S: this is the secret sanitizing key generation algorithm. It takes the master secret key skP3S, the sanitizer’s public key pkP3Ssan, and the set of attributes S as the input and outputs the secret sanitizing key skS for the sanitizer.(vii)
VerifyP3SpkP3S,pkP3Ssig,σ,m: this is the verification algorithm. It takes the master public key pkP3S, the signer’s public key pkP3Ssig, the signature σ, and the corresponding message m as the input and outputs a bit b=1 if the signature σ is valid. Otherwise, b=0.(viii)
SanitizeP3SpkP3S,pkP3Ssig,skP3Ssan,skS,σ,m,M: this is the new signature generation algorithm. It takes the master public key pkP3S, the signer’s public key pkP3Ssig, the sanitizer’s secret key skP3Ssan, the secret sanitizing key skS, the signature σ, the corresponding message m, and the description of modification M as the input and outputs the new signature σ′ for the modified message m′.(ix)
ProofP3SpkP3S,skP3Ssig,σ,m: this is the proof generation algorithm. It takes the master public key pkP3S, the signer’s secret key skP3Ssig, the signature σ, and the corresponding message m as the input and outputs the proof πP3S.(x)
JudgeP3SPPP3S,pkP3S,pkP3Ssig,σ,m,πP3S: this is the proof verification algorithm. It takes the public parameter PPP3S, the master public key pkP3S, the signer’s public key pkP3Ssig, the signature σ, the corresponding message m, and the proof πP3S as the input and outputs a bit b=1 if the proof πP3S is valid. Otherwise, b=0.The detailed definition of correctness and security of the policy-based sanitizable signature is given in [16].


## 2.8. Blockchain Protocol

LetΓ denote an immutable blockchain protocol such as Ethereum Enterprise. The nodes in the blockchain protocol obtain their local chain C based on a common genesis block. The nodes in the blockchain protocol collect transactions in the whole blockchain ecosystem and then package these transactions into a new block. The chain becomes longer as nodes agree on a new block. Nodes can access the blockchain protocol through the following interfaces.(i)
C′,⊥←Γ⋅updateChain: returns the chain C′ if it is the longer and the valid chain in the blockchain ecosystem. Otherwise, it returns ⊥.(ii)
0,1←Γ⋅validateChainC: takes the chain C as the input and outputs 1 iff the chain is valid according to the public set of rules.(iii)
0,1←Γ⋅validateBlockB: takes the block B as the input and outputs 1 iff the block is valid according to the public set of rules.(iv)
Γ⋅broadcastx: takes the transaction x as the input and broadcasts it to all nodes in the blockchain ecosystem.


## 3. Problem Formulation

### 3.1. System Model

As shown in Figure4, the system model of the proposed redactable blockchain protocol consists of four entities: the trusted authority (TA), the miners, the users, and the authorized users. Note that the model in this paper is similar to the model in [13]. It is more applicable to permissioned blockchains, such as Hyperledger, Ethereum Enterprise, Ripple, and Quorum.(i)
Trusted authority (TA): trusted authority (TA) is fully honest and responsible for generating the signing private key for users who posted the redactable transaction, issuing the attributes and attributes’ key for authorized users, and sending keys to miners.(ii)
Miners: miners are fully honest and have powerful computing resources. They are responsible for packaging transactions in the network to generate the new block and removing harmful information from the previous blocks.(iii)
Users: users may be malicious. They can post the usual transaction or the transaction containing the index of the block which includes harmful information to the network. Users get fine-grained control over which users can redact their usual transaction and which portions of the transaction can be redacted. The malicious users may specify an access structure that only allows themselves and their conspirators to redact the transaction.(iv)
Authorized users: the authorized users are semihonest in the sense that they can modify the portions of the transaction that are allowed to be modified and generate the new valid signatures for the updated data that are indistinguishable from the signatures that the originator generated for the original transaction.Figure 4
The system model.


### 3.2. Design Goals

In order to realize a “healthy” blockchain protocol, the proposed fine-grained and controllably redactable blockchain with harmful data forced removal should satisfy the following properties:(i)
Controlled redaction: only authorized users can redact the portions of the transaction that are allowed to be redacted.(ii)
Accountability: the authorized user who redacts the transaction can be tracked.(iii)
Correctness: correctness ensures that the redacted blockchain is “healthy.” Specifically, a “healthy” blockchain should meet the following characteristics:(a)
Chain growth: letC1 and C2 denote two chains possessed by two honest users at rounds r1 and r2, respectively. Then, lenC2−lenC1≥τ⋅r2−r1, where τ is the speed coefficient and r2>r1.(b)
Chain quality: generally speaking, the chain quality says that the ratio of adversarial blocks in any segment of a chain held by an honest party is no more than a fraction0<μ≤1, where μ is the fraction of resources controlled by the adversary.(c)
Editable common prefix: the usual common prefix says that ifC1 and C2 are two chains possessed by two honest users at rounds r1 and r2, for r2>r1, C1 is a prefix of C2. It can be formally denoted as C1k≤C2, where C1k is the chain obtained by removing the last k blocks from C1, k∈ℕ is the common prefix parameter. Note that the proposed editable blockchain inherently does not satisfy the common prefix. Suppose the voting phase for the redaction transaction Ti∗ is still on at round r1. At round r2, the voting phase is complete, and Ti∗ replaces Ti, i.e., the redacted block Bi∗ replaces Bi. In C1k, the i-th block is Bi instead of Bi∗ as in C2. Thus, C1k is not the common prefix of C1 and C2. We extend this definition. The chains C1 and C2 satisfy one of the following:(1)
C1k≤C2(2)
The voting phase is complete, andBi∗ replaces Bi if Bi∗∈C2r2−r1+k, Bi∗∉C1k


### 3.3. Threat Model

Definition 4.
(controlled redaction). Controlled redaction ensures that only authorized users can redact the portions of the transaction that are allowed to be redacted. In order to formally describe the controlled redaction, we introduce a game between the challengerC and the adversary A=A1,A2. Here, we consider two adversaries. One of the adversaries is the adversary A1, who does not possess the attributes’ set which satisfies the access control policy. Another is the adversary A2, who tries to redact the inadmissible portions of the transaction. In order to show how A1 and A2 attack the redactable blockchain protocol, we introduce the game between the challenger C and adversaries A1 and A2, respectively.
Firstly, we describe the game between the challengerC and the adversary A1. Trusted authority (group manager) is viewed as a challenger C, and the unauthorized user is viewed as an adversary A1. This game includes the following phases:(i)
Setup phase: the challengerC runs the ParGenP3S and SetupP3S algorithm to generate the public parameters PPP3S and the master private/public key pair skP3S,pkP3S. Then, C holds the master private key skP3S locally. Finally, C sends the master public key pkP3S and the public parameters PPP3S to the adversary A1.(ii)
Query phase:(a)
KGenSanP3S queries: the adversary A1 queries sanitizer’s private/public key pair for the public parameters PPP3S. C runs KGenSanP3S algorithm and returns the private/public key pair x2,y2 to A1.(b)
Sign queries: the adversaryA1 queries the signature for the master public key pkP3S, the signature for the transaction m, the set of admissible blocks A, and the access structure A. C runs KGenSigP3S to generate the signing key and then runs Sign algorithm to produce the signature σ. Finally, C returns the signature σ to A1.(c)
AddSanP3S queries: the adversary A1 queries the sanitizer’s attribute key for skP3S, pkP3SSan, and the attributes’ set S such that AS=0. C runs AddSanP3S algorithm and returns the sanitizer’s attribute key skS←σskS,skS′ to A1.(d)
VerifyP3S queries: the adversary A1 queries the verification result for pkP3S, pkP3SSig, σ, and m. C runs VerifyP3S algorithm and returns the result to A1.(e)
SanitizeP3S queries: the adversary A1 queries the sanitizable signature for pkP3S, pkP3SSig, skP3SSan, skS, m, σ, and m′. C runs SanitizeP3S algorithm and returns the new signature σ′ to A1.(f)
ProofP3S queries: the adversary A1 queries πP3S,pk for pkP3S, skP3SSig, σ, and m. C runs ProofP3S algorithm and returns πP3S,pk to A1.(g)
JudgeP3S queries: the adversary A1 queries the judge result for pkP3S, skP3SSig, σ, and m. C runs JudgeP3S algorithm and returns the result to A1.(iii)
Challenge phase: the adversaryA1 adaptively chooses the authorized user’s attributes’ set SAS=0. Then, A1 runs SanitizeP3S algorithm to generate the challenged signature σ∗ for the challenged transaction m∗. Finally, the adversary A1 sends S,m∗,σ∗ to C.(iv)
Verify phase: the adversaryA1 performs polynomial queries as in the query phase. Consider the adversary A1 has made L queries, and let Q=skS,S,mi,Ai,Ai,σii=1|Q| denote the set of information obtained through these queries. C runs VerifyP3SpkP3S,pkP3SSig,A,A,m∗,σ∗ algorithm and outputs a bit b0. If b0=1, C checks whether there exists an i∈Q,σ∗ such that AS=0. If there is such an i, the challenger C outputs b1=1. Otherwise, C outputs b1=0.
We say that the adversaryA1 wins if b1=1. In the above game, we want to show that the adversary A1, who does not possess the attributes’ set S such that AS=0, should not generate the new valid witness for the transaction. The adversary’s goal is to correctly generate the valid signature σ′ for the transaction m∗. We set the advantage of a polynomial-time adversary A1 in this game to be Prb1=1. We say the proposed scheme satisfies the unforgeability of the signature if for any polynomial-time adversary A1, Prb1=1<1/polyn for sufficiently large n, where poly stands for a polynomial function.
Then, we describe the game between the challengerC and the adversary A2. Trusted authority (group manager) is viewed as a challenger C, and the authorized user is viewed as an adversary A2. This game includes the following phases:(i)
Setup phase: the challengerC runs the ParGenP3S and SetupP3S algorithm to generate the public parameters PPP3S and the master private/public key pair skP3S,pkP3S. Then, C holds the master private key skP3S locally. Finally, C sends the master public key pkP3S and the public parameters PPP3S to the adversary A2.(ii)
Query phase:(a)
KGenSanP3S queries: the adversary A2 queries sanitizer’s private/public key pair for the public parameters PPP3S. C runs KGenSanP3S algorithm and returns the private/public key pair x2,y2 to A2.(b)
Sign queries: the adversaryA2 queries the signature for the master public key pkP3S, the signature for the message m, the set of admissible blocks F, and the access structure A. C runs KGenSigP3S to generate the signing key and then runs Sign algorithm to produce the signature σ. Finally, C returns the signature σ to A2.(c)
AddSanP3S queries: the adversary A2 queries the sanitizer’s attribute key for skP3S, pkP3SSan, and the attributes’ set S such that AS=1. C runs AddSanP3S algorithm and returns the sanitizer’s attribute key skS←σskS,skS′ to A2.(d)
VerifyP3S queries: the adversary A2 queries the verification result for pkP3S, pkP3SSig, σ, and m. C runs VerifyP3S algorithm and returns the result to A2.(e)
SanitizeP3S queries: the adversary A2 queries the sanitizable signature for pkP3S, pkP3SSig, skP3SSan, skS, m, σ, and m′. C runs SanitizeP3S algorithm and returns the new signature σ′ to A2.(f)
ProofP3S queries: the adversary A2 queries πP3S,pk for pkP3S, skP3SSig, σ, and m. C runs ProofP3S algorithm and returns πP3S,pk to A2.(g)
JudgeP3S queries: the adversary A2 queries the judge result for pkP3S, skP3SSig, σ, and m. C runs JudgeP3S algorithm and returns the result to A2.(iii)
Challenge phase: the adversaryA2 adaptively chooses the authorized user’s attributes’ set SAS=1. Then, A2 runs SanitizeP3S algorithm to generate the challenged signature σ∗ for the challenged message m∗ which does not contain all inadmissible blocks. Finally, the adversary A2 sends S,m∗,σ∗ to C.(iv)
Verify phase: the adversaryA2 performs polynomial queries as in the query phase. Consider the adversary A2 has made L queries, and let Q=skS,S,mi,Ai,Ai,σii=1Q denote the set of information obtained through these queries. C runs VerifyP3SpkP3S,pkP3SSig,A,A,m∗,σ∗ algorithm and outputs a bit b0. If b0=1, C checks whether there exists an i∈Q,m∗ which does not contain all inadmissible blocks. If there is such an i, the challenger C outputs b1=1. Otherwise, C outputs b1=0.
We say that the adversaryA2 wins if b1=1. In the above game, we want to show that the adversary A2, who redacts the inadmissible blocks, should not generate the new valid signature. The adversary’s goal is to correctly generate the valid signature σ′ for the message m∗. We set the advantage of a polynomial-time adversary A2 in this game to be Prb1=1. We say the proposed scheme satisfies controlled redaction if for any polynomial-time adversary A2, Prb1=1<1/polyn for sufficiently large n, where poly stands for a polynomial function.Definition 5.
(accountability). We say that the proposed fine-grained and controllably redactable blockchain with harmful data forced removal satisfies accountability if TA can extract signer’s identity from any valid transaction’s signature with nonnegligible probability.


## 3.1. System Model

As shown in Figure4, the system model of the proposed redactable blockchain protocol consists of four entities: the trusted authority (TA), the miners, the users, and the authorized users. Note that the model in this paper is similar to the model in [13]. It is more applicable to permissioned blockchains, such as Hyperledger, Ethereum Enterprise, Ripple, and Quorum.(i)
Trusted authority (TA): trusted authority (TA) is fully honest and responsible for generating the signing private key for users who posted the redactable transaction, issuing the attributes and attributes’ key for authorized users, and sending keys to miners.(ii)
Miners: miners are fully honest and have powerful computing resources. They are responsible for packaging transactions in the network to generate the new block and removing harmful information from the previous blocks.(iii)
Users: users may be malicious. They can post the usual transaction or the transaction containing the index of the block which includes harmful information to the network. Users get fine-grained control over which users can redact their usual transaction and which portions of the transaction can be redacted. The malicious users may specify an access structure that only allows themselves and their conspirators to redact the transaction.(iv)
Authorized users: the authorized users are semihonest in the sense that they can modify the portions of the transaction that are allowed to be modified and generate the new valid signatures for the updated data that are indistinguishable from the signatures that the originator generated for the original transaction.Figure 4
The system model.


## 3.2. Design Goals

In order to realize a “healthy” blockchain protocol, the proposed fine-grained and controllably redactable blockchain with harmful data forced removal should satisfy the following properties:(i)
Controlled redaction: only authorized users can redact the portions of the transaction that are allowed to be redacted.(ii)
Accountability: the authorized user who redacts the transaction can be tracked.(iii)
Correctness: correctness ensures that the redacted blockchain is “healthy.” Specifically, a “healthy” blockchain should meet the following characteristics:(a)
Chain growth: letC1 and C2 denote two chains possessed by two honest users at rounds r1 and r2, respectively. Then, lenC2−lenC1≥τ⋅r2−r1, where τ is the speed coefficient and r2>r1.(b)
Chain quality: generally speaking, the chain quality says that the ratio of adversarial blocks in any segment of a chain held by an honest party is no more than a fraction0<μ≤1, where μ is the fraction of resources controlled by the adversary.(c)
Editable common prefix: the usual common prefix says that ifC1 and C2 are two chains possessed by two honest users at rounds r1 and r2, for r2>r1, C1 is a prefix of C2. It can be formally denoted as C1k≤C2, where C1k is the chain obtained by removing the last k blocks from C1, k∈ℕ is the common prefix parameter. Note that the proposed editable blockchain inherently does not satisfy the common prefix. Suppose the voting phase for the redaction transaction Ti∗ is still on at round r1. At round r2, the voting phase is complete, and Ti∗ replaces Ti, i.e., the redacted block Bi∗ replaces Bi. In C1k, the i-th block is Bi instead of Bi∗ as in C2. Thus, C1k is not the common prefix of C1 and C2. We extend this definition. The chains C1 and C2 satisfy one of the following:(1)
C1k≤C2(2)
The voting phase is complete, andBi∗ replaces Bi if Bi∗∈C2r2−r1+k, Bi∗∉C1k


## 3.3. Threat Model

Definition 4.
(controlled redaction). Controlled redaction ensures that only authorized users can redact the portions of the transaction that are allowed to be redacted. In order to formally describe the controlled redaction, we introduce a game between the challengerC and the adversary A=A1,A2. Here, we consider two adversaries. One of the adversaries is the adversary A1, who does not possess the attributes’ set which satisfies the access control policy. Another is the adversary A2, who tries to redact the inadmissible portions of the transaction. In order to show how A1 and A2 attack the redactable blockchain protocol, we introduce the game between the challenger C and adversaries A1 and A2, respectively.
Firstly, we describe the game between the challengerC and the adversary A1. Trusted authority (group manager) is viewed as a challenger C, and the unauthorized user is viewed as an adversary A1. This game includes the following phases:(i)
Setup phase: the challengerC runs the ParGenP3S and SetupP3S algorithm to generate the public parameters PPP3S and the master private/public key pair skP3S,pkP3S. Then, C holds the master private key skP3S locally. Finally, C sends the master public key pkP3S and the public parameters PPP3S to the adversary A1.(ii)
Query phase:(a)
KGenSanP3S queries: the adversary A1 queries sanitizer’s private/public key pair for the public parameters PPP3S. C runs KGenSanP3S algorithm and returns the private/public key pair x2,y2 to A1.(b)
Sign queries: the adversaryA1 queries the signature for the master public key pkP3S, the signature for the transaction m, the set of admissible blocks A, and the access structure A. C runs KGenSigP3S to generate the signing key and then runs Sign algorithm to produce the signature σ. Finally, C returns the signature σ to A1.(c)
AddSanP3S queries: the adversary A1 queries the sanitizer’s attribute key for skP3S, pkP3SSan, and the attributes’ set S such that AS=0. C runs AddSanP3S algorithm and returns the sanitizer’s attribute key skS←σskS,skS′ to A1.(d)
VerifyP3S queries: the adversary A1 queries the verification result for pkP3S, pkP3SSig, σ, and m. C runs VerifyP3S algorithm and returns the result to A1.(e)
SanitizeP3S queries: the adversary A1 queries the sanitizable signature for pkP3S, pkP3SSig, skP3SSan, skS, m, σ, and m′. C runs SanitizeP3S algorithm and returns the new signature σ′ to A1.(f)
ProofP3S queries: the adversary A1 queries πP3S,pk for pkP3S, skP3SSig, σ, and m. C runs ProofP3S algorithm and returns πP3S,pk to A1.(g)
JudgeP3S queries: the adversary A1 queries the judge result for pkP3S, skP3SSig, σ, and m. C runs JudgeP3S algorithm and returns the result to A1.(iii)
Challenge phase: the adversaryA1 adaptively chooses the authorized user’s attributes’ set SAS=0. Then, A1 runs SanitizeP3S algorithm to generate the challenged signature σ∗ for the challenged transaction m∗. Finally, the adversary A1 sends S,m∗,σ∗ to C.(iv)
Verify phase: the adversaryA1 performs polynomial queries as in the query phase. Consider the adversary A1 has made L queries, and let Q=skS,S,mi,Ai,Ai,σii=1|Q| denote the set of information obtained through these queries. C runs VerifyP3SpkP3S,pkP3SSig,A,A,m∗,σ∗ algorithm and outputs a bit b0. If b0=1, C checks whether there exists an i∈Q,σ∗ such that AS=0. If there is such an i, the challenger C outputs b1=1. Otherwise, C outputs b1=0.
We say that the adversaryA1 wins if b1=1. In the above game, we want to show that the adversary A1, who does not possess the attributes’ set S such that AS=0, should not generate the new valid witness for the transaction. The adversary’s goal is to correctly generate the valid signature σ′ for the transaction m∗. We set the advantage of a polynomial-time adversary A1 in this game to be Prb1=1. We say the proposed scheme satisfies the unforgeability of the signature if for any polynomial-time adversary A1, Prb1=1<1/polyn for sufficiently large n, where poly stands for a polynomial function.
Then, we describe the game between the challengerC and the adversary A2. Trusted authority (group manager) is viewed as a challenger C, and the authorized user is viewed as an adversary A2. This game includes the following phases:(i)
Setup phase: the challengerC runs the ParGenP3S and SetupP3S algorithm to generate the public parameters PPP3S and the master private/public key pair skP3S,pkP3S. Then, C holds the master private key skP3S locally. Finally, C sends the master public key pkP3S and the public parameters PPP3S to the adversary A2.(ii)
Query phase:(a)
KGenSanP3S queries: the adversary A2 queries sanitizer’s private/public key pair for the public parameters PPP3S. C runs KGenSanP3S algorithm and returns the private/public key pair x2,y2 to A2.(b)
Sign queries: the adversaryA2 queries the signature for the master public key pkP3S, the signature for the message m, the set of admissible blocks F, and the access structure A. C runs KGenSigP3S to generate the signing key and then runs Sign algorithm to produce the signature σ. Finally, C returns the signature σ to A2.(c)
AddSanP3S queries: the adversary A2 queries the sanitizer’s attribute key for skP3S, pkP3SSan, and the attributes’ set S such that AS=1. C runs AddSanP3S algorithm and returns the sanitizer’s attribute key skS←σskS,skS′ to A2.(d)
VerifyP3S queries: the adversary A2 queries the verification result for pkP3S, pkP3SSig, σ, and m. C runs VerifyP3S algorithm and returns the result to A2.(e)
SanitizeP3S queries: the adversary A2 queries the sanitizable signature for pkP3S, pkP3SSig, skP3SSan, skS, m, σ, and m′. C runs SanitizeP3S algorithm and returns the new signature σ′ to A2.(f)
ProofP3S queries: the adversary A2 queries πP3S,pk for pkP3S, skP3SSig, σ, and m. C runs ProofP3S algorithm and returns πP3S,pk to A2.(g)
JudgeP3S queries: the adversary A2 queries the judge result for pkP3S, skP3SSig, σ, and m. C runs JudgeP3S algorithm and returns the result to A2.(iii)
Challenge phase: the adversaryA2 adaptively chooses the authorized user’s attributes’ set SAS=1. Then, A2 runs SanitizeP3S algorithm to generate the challenged signature σ∗ for the challenged message m∗ which does not contain all inadmissible blocks. Finally, the adversary A2 sends S,m∗,σ∗ to C.(iv)
Verify phase: the adversaryA2 performs polynomial queries as in the query phase. Consider the adversary A2 has made L queries, and let Q=skS,S,mi,Ai,Ai,σii=1Q denote the set of information obtained through these queries. C runs VerifyP3SpkP3S,pkP3SSig,A,A,m∗,σ∗ algorithm and outputs a bit b0. If b0=1, C checks whether there exists an i∈Q,m∗ which does not contain all inadmissible blocks. If there is such an i, the challenger C outputs b1=1. Otherwise, C outputs b1=0.
We say that the adversaryA2 wins if b1=1. In the above game, we want to show that the adversary A2, who redacts the inadmissible blocks, should not generate the new valid signature. The adversary’s goal is to correctly generate the valid signature σ′ for the message m∗. We set the advantage of a polynomial-time adversary A2 in this game to be Prb1=1. We say the proposed scheme satisfies controlled redaction if for any polynomial-time adversary A2, Prb1=1<1/polyn for sufficiently large n, where poly stands for a polynomial function.Definition 5.
(accountability). We say that the proposed fine-grained and controllably redactable blockchain with harmful data forced removal satisfies accountability if TA can extract signer’s identity from any valid transaction’s signature with nonnegligible probability.


## 4. The Improved Policy-Based Sanitizable Signature

### 4.1. Algorithm Definition

LetPCH denote a policy-based chameleon hash, Ω label a simulation-sound extractable noninteractive zero-knowledge proof (NIZK) system, f be a one-way function, Π denote an IND-CCA2-secure public key encryption scheme, and Σ be an eUNF-CMA-secure signature scheme. Specifically, the improved policy-based sanitizable signature is described as follows:(i)
ParGenP3S1κ: it takes a security parameter κ as the input and outputs PPP3S=crsΩ,PPΠ,PPΣ,PPPCH,f,h, where PPΠ←PPGenΠ1κ, crsΩ←PPGenΩ1κ, PPΣ←PPGenΣ1κ, PPPCH←PPGenPCH1κ, f:Df⟶Rf is a one-way function, and H is a cryptographic hash function.(ii)
SetupP3SPPP3S: it takes PPP3S as the input and outputs skP3S,pkP3S←skPCH,skΣ,pkPCH,pkΣ, where skPCH,pkPCH←MKeyGenPCHPPPCH and skΣ,pkΣ←KGenΣPPΣ.(iii)
KGenSigP3SPPP3S: it takes PPP3S as the input and outputs skP3SSig,pkP3SSig←x1,skΣ′,skΠ,y1,pkΣ′,pkΠ, where x1←Df, y1←fx1, skΠ,pkΠ←KGenΠPPΠ, and skΣ′,pkΣ′←KGenΣPPΣ.(iv)
KGenSanP3SPPP3S: it takes PPP3S as the input and outputs x2,y2, where x2←Df and y2←fx2.(v)
SignP3SpkP3S,skP3SSig,m,A,A: it takes pkP3S, skP3SSig, the message m, the set of admissible blocks A, and the access structure A as the input and outputs ⊥ if A=∅. Otherwise, it outputs σ←h,r,A,σm,A,π,c, where h,r←HashPCHpkPCH,m,A, σm←SignΣskΣ′,pkP3S,pkP3SSig,A,Hi‖m!A,h,A, c←EncΠpkΠ,y1, and π←ProveΩx1,x2,skΠ,σskS:y1=fx1∧c=EncΠpkΠ,y1∧KVrfΠskΠ,pkΠ=1∨y2=fx2∧c=EncΠpkΠ,y2∧VerfΣpkΣ,y2,pkP3S,σskS=1l. Note that l=PPP3S,pkP3S,pkP3SSig,h,r,m,A,A,Hi‖m!A,σm,c.(vi)
AddSanP3SskP3S,pkP3SSan,S: it takes skP3S, pkP3SSan, and the attributes’ set S as the input and outputs the sanitizing key skS←σskS,skS′, where σskS←SignΣskΣ,pkP3SSan,pkP3S and skS′←KGenPCHskPCH,S.(vii)
VerifyP3SpkP3S,pkP3SSig,σ,m: it takes pkP3S, pkP3SSig, σ, and m as the input and outputs 1 if π and σm are valid, VerifyPCHpkPCH,m,r,h=1, and Hi‖m!A can be computed from the message m. Otherwise, it outputs ⊥.(viii)
SanitizeP3SpkP3S,pkP3SSig,skP3SSan,skS,m,σ,m′: it takes pkP3S, pkP3SSig, skP3SSan, skS, m, σ, and m′ as the input. If σskS or σ is not valid, it outputs ⊥. Otherwise, the sanitizer computes r′←AdaptPCHpkPCH,skS,m,m′,h,r, c′←EncΠpkΠ,y2, and π′←ProveΩx1,x2,skΠ,σskS:y1=fx1∧c′=EncΠpkΠ,y1∧KVrfΠskΠ,pkΠ=1∨y2=fx2∧c′=EncΠpkΠ,y2∧VerfΣpkΣ,y2,pkP3S,σskS=1l. Note that l=PPP3S,pkP3S,pkP3SSig,h,r′,m′,A,A,Hi‖m!A,σm,c′. Then, the sanitizer sets σ′,m′←h,r′,A,σm,A,π,c′,m′. If σ′,m′ is not valid, this algorithm outputs ⊥. Otherwise, it outputs σ′,m′.(ix)
ProofP3SpkP3S,skP3SSig,σ,m: it takes pkP3S, skP3SSig, σ, and m as the input and outputs πP3S,pk, where pk←DecΠskΠ,c, πP3S←ProveΩskΠ,x1:pk=DecΠskΠ,c∧KVrfΠskΠ,pkΠ=1∧y1=fx1l, and l=PPP3S,pkP3S,pkP3Sig,σ,pk,m.(x)
JudgeP3SpkP3S,pkP3SSig,pk,πP3S,σ,m: it takes pkP3S, pkP3SSig, pk, πP3S, σ, and m as the input. If σ and πP3S are valid, it outputs 1. Otherwise, it outputs 0.The improved policy-based sanitizable signature replaces the inadmissible block setm!A in [16] with Hi‖m!A to allow that the number of blocks of the message m can be changed, and the set of inadmissible blocks does not need to be stored. Here, m!A denotes the set of blocks that are not allowed to be modified. The security definition and analysis are given in Appendixes A and B, respectively.


## 4.1. Algorithm Definition

LetPCH denote a policy-based chameleon hash, Ω label a simulation-sound extractable noninteractive zero-knowledge proof (NIZK) system, f be a one-way function, Π denote an IND-CCA2-secure public key encryption scheme, and Σ be an eUNF-CMA-secure signature scheme. Specifically, the improved policy-based sanitizable signature is described as follows:(i)
ParGenP3S1κ: it takes a security parameter κ as the input and outputs PPP3S=crsΩ,PPΠ,PPΣ,PPPCH,f,h, where PPΠ←PPGenΠ1κ, crsΩ←PPGenΩ1κ, PPΣ←PPGenΣ1κ, PPPCH←PPGenPCH1κ, f:Df⟶Rf is a one-way function, and H is a cryptographic hash function.(ii)
SetupP3SPPP3S: it takes PPP3S as the input and outputs skP3S,pkP3S←skPCH,skΣ,pkPCH,pkΣ, where skPCH,pkPCH←MKeyGenPCHPPPCH and skΣ,pkΣ←KGenΣPPΣ.(iii)
KGenSigP3SPPP3S: it takes PPP3S as the input and outputs skP3SSig,pkP3SSig←x1,skΣ′,skΠ,y1,pkΣ′,pkΠ, where x1←Df, y1←fx1, skΠ,pkΠ←KGenΠPPΠ, and skΣ′,pkΣ′←KGenΣPPΣ.(iv)
KGenSanP3SPPP3S: it takes PPP3S as the input and outputs x2,y2, where x2←Df and y2←fx2.(v)
SignP3SpkP3S,skP3SSig,m,A,A: it takes pkP3S, skP3SSig, the message m, the set of admissible blocks A, and the access structure A as the input and outputs ⊥ if A=∅. Otherwise, it outputs σ←h,r,A,σm,A,π,c, where h,r←HashPCHpkPCH,m,A, σm←SignΣskΣ′,pkP3S,pkP3SSig,A,Hi‖m!A,h,A, c←EncΠpkΠ,y1, and π←ProveΩx1,x2,skΠ,σskS:y1=fx1∧c=EncΠpkΠ,y1∧KVrfΠskΠ,pkΠ=1∨y2=fx2∧c=EncΠpkΠ,y2∧VerfΣpkΣ,y2,pkP3S,σskS=1l. Note that l=PPP3S,pkP3S,pkP3SSig,h,r,m,A,A,Hi‖m!A,σm,c.(vi)
AddSanP3SskP3S,pkP3SSan,S: it takes skP3S, pkP3SSan, and the attributes’ set S as the input and outputs the sanitizing key skS←σskS,skS′, where σskS←SignΣskΣ,pkP3SSan,pkP3S and skS′←KGenPCHskPCH,S.(vii)
VerifyP3SpkP3S,pkP3SSig,σ,m: it takes pkP3S, pkP3SSig, σ, and m as the input and outputs 1 if π and σm are valid, VerifyPCHpkPCH,m,r,h=1, and Hi‖m!A can be computed from the message m. Otherwise, it outputs ⊥.(viii)
SanitizeP3SpkP3S,pkP3SSig,skP3SSan,skS,m,σ,m′: it takes pkP3S, pkP3SSig, skP3SSan, skS, m, σ, and m′ as the input. If σskS or σ is not valid, it outputs ⊥. Otherwise, the sanitizer computes r′←AdaptPCHpkPCH,skS,m,m′,h,r, c′←EncΠpkΠ,y2, and π′←ProveΩx1,x2,skΠ,σskS:y1=fx1∧c′=EncΠpkΠ,y1∧KVrfΠskΠ,pkΠ=1∨y2=fx2∧c′=EncΠpkΠ,y2∧VerfΣpkΣ,y2,pkP3S,σskS=1l. Note that l=PPP3S,pkP3S,pkP3SSig,h,r′,m′,A,A,Hi‖m!A,σm,c′. Then, the sanitizer sets σ′,m′←h,r′,A,σm,A,π,c′,m′. If σ′,m′ is not valid, this algorithm outputs ⊥. Otherwise, it outputs σ′,m′.(ix)
ProofP3SpkP3S,skP3SSig,σ,m: it takes pkP3S, skP3SSig, σ, and m as the input and outputs πP3S,pk, where pk←DecΠskΠ,c, πP3S←ProveΩskΠ,x1:pk=DecΠskΠ,c∧KVrfΠskΠ,pkΠ=1∧y1=fx1l, and l=PPP3S,pkP3S,pkP3Sig,σ,pk,m.(x)
JudgeP3SpkP3S,pkP3SSig,pk,πP3S,σ,m: it takes pkP3S, pkP3SSig, pk, πP3S, σ, and m as the input. If σ and πP3S are valid, it outputs 1. Otherwise, it outputs 0.The improved policy-based sanitizable signature replaces the inadmissible block setm!A in [16] with Hi‖m!A to allow that the number of blocks of the message m can be changed, and the set of inadmissible blocks does not need to be stored. Here, m!A denotes the set of blocks that are not allowed to be modified. The security definition and analysis are given in Appendixes A and B, respectively.


## 5. The Proposed Protocol

### 5.1. An Overview

The workflow of the proposed blockchain protocol can be described as follows. Firstly, users can generate a local chainC based on the common genesis block genesis and initialize the redaction transaction list R, the removal transaction list D, the penalty payment transaction list P, and the blacklist L to be empty. After that, users run Γ⋅updateChain to obtain the longest chain in the blockchain network. When the user wants to redact the previous transaction, he/she first broadcasts a redaction transaction by spending some transaction fees. The transaction will be added to the list R if it is valid. The miners vote on the transaction. The transaction can be executed if enough votes are collected within a period of time as shown in Figure 5. When a user finds harmful information contained in a block, he/she creates a removal transaction containing the index of the block without spending transaction fees. Miners create new blocks that contain at least one transaction in D and one in P if they are not empty. The miner removes the harmful information from the block according to the provided index. Meanwhile, the miner generates a penalty payment transaction added to P as shown in Figure 6. The transaction will be removed from list P after the penalty is paid by the malicious user. If the malicious user fails to pay the penalty within a period of time, he/she will be added to the blacklist L. After that, all transactions relating to the malicious user will never be performed.Figure 5
The redaction of the transaction. (a) Proposing a redactionA∗ for a transaction A. (b) After a successful voting phase, A∗ replaces A in the chain.
(a)(b)Figure 6
The removal of harmful information.


### 5.2. Description of the Proposed Protocol

The proposed blockchain protocol runs in a sequence of roundsr and consists of the following six algorithms (Figures 7–10):(i)
Initialization: get the local chainC←genesis, where genesis denotes a common genesis block. Set round r←1, and initialize empty lists R, D, P, and L.(ii)
Chain update: at the beginning of each roundr, users run C′,⊥←Γ⋅updateChain to get the longest chain C′ in the blockchain network.(iii)
Propose a redaction: the user proposes a redaction of the transactionTA by spending some transaction fees.(a)
Firstly, the user creates a redaction transactionredactT using the new transaction TA∗ as shown in Figure 7. In this process, the improved policy sanitizable signature is used to generate the witness for the transaction. We can see from Figure 7 that the hash values h for TA and TA∗ are the same. Therefore, the hash value of this block will not be changed after redacting the transaction.(b)
Then, he/she runsΓ⋅broadcastTA∗ to broadcast the redacted transaction to the blockchain network.(c)
Finally, miners add the transactionrdactT to the list R if the data τ2 are UTXO. Otherwise, the transaction is discarded.(iv)
Propose a removal of harmful information when the user finds that the transactionTD, contained in the block with the index I, has the harmful information.(a)
Firstly, as shown in Figure8, the user creates a removal transaction removeT, which does not cost transaction fee and contains the block’s index I and the transaction TD.(b)
Then, he/she broadcasts the transactionremoveT.(c)
The transactionremoveT will be added to the list D if the block I does contain the harmful information. Meanwhile, the penalty payment transaction TP will be created and added to the list P. As shown in Figure 9, the transaction TP contains the amount of the penalty pen and the address ad of the malicious user who posts the harmful information. The transaction TP will be removed from the list P after the malicious user pays the penalty.(v)
Redacting the chain:(a)
For the candidate transactionTA in the list R, the miner substitutes it with the new transaction TA∗ if the voting process on it has been completed and enough votes v≥ρ have been collected within a period of time t. The transaction TA is discarded if the votes v<ρ within a period of time t. If the voting on TA is still in progress, nothing will be done. Here, ρ denotes the threshold of votes and can be specified by consensus among all users in the blockchain network.(b)
For the candidate transactionTD in the list D, the miner removes the harmful information from TD which is contained in the block with the index I.(c)
For the candidate transactionTP in the list P, the miner first verifies whether the malicious user pays the penalty within a period of time t1. If the malicious user pays the penalty, the transaction is removed from P. If the malicious user does not pay the penalty within a specified period of time, the user is added to the blacklist L, and the transaction TP is removed from the list P.(vi)
Creating a new block: the miner collects all transactions from the network for ther−th round and builds a new block B which meets the following conditions:(a)
It contains at least one transaction inD and one in P if they are not empty.(b)
It contains a voteHTA on the candidate transaction in the list R if the voting on TA is still in process and the miner is willing to endorse.(c)
All transactions contained in it comply with the usual transaction rules in the Ethereum Enterprise blockchain, and the validation process is shown in Figure10.Figure 7
The transactionredactT.Figure 8
The transactionremoveT.Figure 9
The transactionpenatlyT.Figure 10
The verification of the received transactionT.Finally, if all blocks contained in the local chainC satisfy Γ⋅validateBlockB=1 and Γ⋅validateChainC=1, the miner extends the local chain C←C‖B and broadcasts the extended chain to the blockchain network.


## 5.1. An Overview

The workflow of the proposed blockchain protocol can be described as follows. Firstly, users can generate a local chainC based on the common genesis block genesis and initialize the redaction transaction list R, the removal transaction list D, the penalty payment transaction list P, and the blacklist L to be empty. After that, users run Γ⋅updateChain to obtain the longest chain in the blockchain network. When the user wants to redact the previous transaction, he/she first broadcasts a redaction transaction by spending some transaction fees. The transaction will be added to the list R if it is valid. The miners vote on the transaction. The transaction can be executed if enough votes are collected within a period of time as shown in Figure 5. When a user finds harmful information contained in a block, he/she creates a removal transaction containing the index of the block without spending transaction fees. Miners create new blocks that contain at least one transaction in D and one in P if they are not empty. The miner removes the harmful information from the block according to the provided index. Meanwhile, the miner generates a penalty payment transaction added to P as shown in Figure 6. The transaction will be removed from list P after the penalty is paid by the malicious user. If the malicious user fails to pay the penalty within a period of time, he/she will be added to the blacklist L. After that, all transactions relating to the malicious user will never be performed.Figure 5
The redaction of the transaction. (a) Proposing a redactionA∗ for a transaction A. (b) After a successful voting phase, A∗ replaces A in the chain.
(a)(b)Figure 6
The removal of harmful information.


## 5.2. Description of the Proposed Protocol

The proposed blockchain protocol runs in a sequence of roundsr and consists of the following six algorithms (Figures 7–10):(i)
Initialization: get the local chainC←genesis, where genesis denotes a common genesis block. Set round r←1, and initialize empty lists R, D, P, and L.(ii)
Chain update: at the beginning of each roundr, users run C′,⊥←Γ⋅updateChain to get the longest chain C′ in the blockchain network.(iii)
Propose a redaction: the user proposes a redaction of the transactionTA by spending some transaction fees.(a)
Firstly, the user creates a redaction transactionredactT using the new transaction TA∗ as shown in Figure 7. In this process, the improved policy sanitizable signature is used to generate the witness for the transaction. We can see from Figure 7 that the hash values h for TA and TA∗ are the same. Therefore, the hash value of this block will not be changed after redacting the transaction.(b)
Then, he/she runsΓ⋅broadcastTA∗ to broadcast the redacted transaction to the blockchain network.(c)
Finally, miners add the transactionrdactT to the list R if the data τ2 are UTXO. Otherwise, the transaction is discarded.(iv)
Propose a removal of harmful information when the user finds that the transactionTD, contained in the block with the index I, has the harmful information.(a)
Firstly, as shown in Figure8, the user creates a removal transaction removeT, which does not cost transaction fee and contains the block’s index I and the transaction TD.(b)
Then, he/she broadcasts the transactionremoveT.(c)
The transactionremoveT will be added to the list D if the block I does contain the harmful information. Meanwhile, the penalty payment transaction TP will be created and added to the list P. As shown in Figure 9, the transaction TP contains the amount of the penalty pen and the address ad of the malicious user who posts the harmful information. The transaction TP will be removed from the list P after the malicious user pays the penalty.(v)
Redacting the chain:(a)
For the candidate transactionTA in the list R, the miner substitutes it with the new transaction TA∗ if the voting process on it has been completed and enough votes v≥ρ have been collected within a period of time t. The transaction TA is discarded if the votes v<ρ within a period of time t. If the voting on TA is still in progress, nothing will be done. Here, ρ denotes the threshold of votes and can be specified by consensus among all users in the blockchain network.(b)
For the candidate transactionTD in the list D, the miner removes the harmful information from TD which is contained in the block with the index I.(c)
For the candidate transactionTP in the list P, the miner first verifies whether the malicious user pays the penalty within a period of time t1. If the malicious user pays the penalty, the transaction is removed from P. If the malicious user does not pay the penalty within a specified period of time, the user is added to the blacklist L, and the transaction TP is removed from the list P.(vi)
Creating a new block: the miner collects all transactions from the network for ther−th round and builds a new block B which meets the following conditions:(a)
It contains at least one transaction inD and one in P if they are not empty.(b)
It contains a voteHTA on the candidate transaction in the list R if the voting on TA is still in process and the miner is willing to endorse.(c)
All transactions contained in it comply with the usual transaction rules in the Ethereum Enterprise blockchain, and the validation process is shown in Figure10.Figure 7
The transactionredactT.Figure 8
The transactionremoveT.Figure 9
The transactionpenatlyT.Figure 10
The verification of the received transactionT.Finally, if all blocks contained in the local chainC satisfy Γ⋅validateBlockB=1 and Γ⋅validateChainC=1, the miner extends the local chain C←C‖B and broadcasts the extended chain to the blockchain network.


## 6. Security Analysis

In this section, we analyze the security of the fine-grained and controllably redactable blockchain protocol with harmful data forced removal in terms of correctness, controlled redaction, and accountability.Theorem 1.
(correctness). The correctness of a blockchain consists of the following three aspects:(1)
Chain growth: if the based immutable blockchain protocolΓ satisfies chain growth, the extended editable blockchain protocol Γ′ also satisfies chain growth.(2)
Chain quality: if the based immutable blockchain protocolΓ satisfies chain quality, the extended editable blockchain protocol Γ′ also satisfies chain growth for any ρ>μ. Here, ρ denotes the ratio of blocks containing the votes of the redacted transaction within a period of time.(3)
Common prefix: if the based immutable blockchain protocolΓ satisfies the common prefix, the extended editable blockchain protocol Γ′ also satisfies the common prefix.Proof.
(1)
Chain growth: we note that the redaction inΓ′ cannot reduce the length of the chain C by removing a block from the chain. Thus, the redact operations have no effect on the length of the chain. In conclusion, Γ′ satisfies chain growth if Γ satisfies chain growth.(2)
Chain quality: suppose the adversaryA posts a malicious redaction transaction Ti∗ for the previous transaction Ti. A mines at most μ ratio of blocks in the voting phase because the adversary only has μ computational power. Thus, Ti∗ cannot be performed due to ρ>μ. In conclusion, only the honest redaction transaction Ti∗ can be performed and added to the chain.(3)
Common prefix: if the chainC2 is not redacted, Γ′ runs as the immutable blockchain Γ. Thus, Γ′ satisfies the common prefix. If the chain C2 is redacted and the redacted block Bi∗ replaces Bi in C2, the voting phase for the block Bi∗ is completed, and enough votes are received. In conclusion, the extended editable blockchain protocol Γ′ also satisfies the common prefix.Theorem 2.
(controlled redaction). In the proposed scheme, for each PPT adversaryA, it is computationally infeasible to generate a valid signature for the redacted transaction.Proof.
To prove this theorem, we consider two types of adversaries. One of the adversaries is the adversaryA1 who does not possess the attributes’ set which satisfies the access control policy. Another is the adversary A2, who tries to redact the inadmissible portions of the transaction. In order to show how A1 and A2 attack the redactable blockchain protocol, we introduce the two games between the challenger C and adversaries A1 and A2, respectively. Firstly, we define a game between the challenger C and the adversary A1.
Game 1: in Game 1, both the challengerC and the adversary A1 perform as defined in the security definition.(i)
Setup phase: the adversaryA1 does as in the “Threat Model.”(ii)
Query phase: the adversaryA1 does as in the “Threat Model.”(iii)
Challenge phase: the adversaryA1 adaptively chooses the authorized user’s attributes’ set SAS=0. Then, A1 runs SanitizeP3S algorithm to generate the challenged signature σ∗ for the challenged transaction m∗. Finally, the adversary A1 sends S,m∗,σ∗ to C.(iv)
Verify phase: the adversaryA1 performs polynomial queries as in the query phase. Consider the adversary A1 has made L queries, and let Q=skS,S,mi,Ai,Ai,σii=1Q denote the set of information obtained through these queries. C runs VerifyP3SpkP3S,pkP3SSig,A,A,m∗,σ∗ algorithm and outputs a bit b0. If b0=1, C checks whether there exists an i∈Q,σ∗ such that AS=0. If there is such an i, the challenger C outputs b1=1. Otherwise, C outputs b1=0.
Supposeb1=1, that is, the adversary A1 wins, we can say that the adversary A1 breaks the security of the policy-based sanitizable signature because the adversary’s goal is to correctly generate the valid signature σ′ for the transaction m∗. According to the security of the policy-based sanitizable signature (unforgeability), the probability of each adversary, who does not possess the attributes’ set S such that AS=0, is negligible.
Then, we define a game between the challengerC and the adversary A2.
Game 2: in Game 2, both the challengerC and the adversary A2 perform as defined in the security definition.(i)
Setup phase: the adversaryA2 does as in the “Threat Model.”(ii)
Query phase: the adversaryA2 does as the adversary A2 in the query phase.(iii)
Challenge phase: the adversaryA2 adaptively chooses the authorized user’s attributes’ set S (AS=1). Then, A2 runs SanitizeP3S algorithm to generate the challenged signature σ∗ for the challenged message m∗ which does not contain all inadmissible blocks. Finally, the adversary A2 sends S,m∗,σ∗ to C.(iv)
Verify phase: the adversaryA2 performs polynomial queries as in the query phase. Consider the adversary A2 has made L queries, and let Q=skS,S,mi,Ai,Ai,σii=1Q denote the set of information obtained through these queries. C runs VerifyP3SpkP3S,pkP3SSig,A,A,m∗,σ∗ algorithm and outputs a bit b0. If b0=1, C checks whether there exists an i∈Q,m∗ which does not contain all inadmissible blocks. If there is such an i, the challenger C outputs b1=1. Otherwise, C outputs b1=0.
Supposeb1=1, that is, the adversary A2 wins, we can say that the adversary A2 breaks the security of the policy-based sanitizable signature because the adversary’s goal is to correctly generate the valid signature σ′ for the transaction m∗. According to the security of the policy-based sanitizable signature (immutability), the probability of each adversary, who redacts the inadmissible blocks, is negligible.
In conclusion, the proposed blockchain protocol achieves controlled redaction. In other words, only authorized users can redact the admissible portions of the transactionTi.Theorem 3.
(accountability). In the proposed blockchain protocol, trusted authority (group manager) can extract the identity of the originator of the transaction or the authorized user from any valid witness with nonnegligible probability.Proof.
We prove accountability by a sequence of games.(i)
Game 0: as Game 0 in [16].(ii)
Game 1: as Game 0, but we replacecrsΩ with the one generated by crsΩ,τ←SIM11κ, i.e., the simulator SIM1 takes the security parameter 1κ as the input and then outputs crsΩ,τ. Finally, the challenger C keeps the trapdoor τ and starts simulating all proofs.(iii)
Assume towards contradiction that the adversary behaves differently. We can then build an adversaryℬ which breaks the zero-knowledge property of the underlying proof system. The reduction works as follows. Our adversary ℬ receives crsΩ from its own challenger and embeds it into PPP3S and generates all other values honestly. All proofs are then generated using the oracle provided and embedded honestly. Then, whatever A outputs is also output by ℬ. PrS0−PrS1 is negligible, where PrSX denotes the advantage of the adversary in Game X. Note that this also means that all proofs are now simulated, even though they still prove valid statements.(iv)
Game 2: as Game 1, but we replacecrsΩ with the one generated by crsΩ,τ,ξ←ξ11κ, i.e., the simulator ξ1 takes the security parameter 1κ as the input and then outputs crsΩ,τ,ξ. Finally, the challenger C keeps the trapdoors τ and ξ. Let E2 be the event that A can distinguish this replacement with nonnegligible probability. Moreover, note that, by definition, crsΩ is exactly distributed as in the prior hop.(v)
As we only keep one additional value, i.e.,ξ, this is only an internal change. PrS1−PrS2 is negligible.(vi)
Game 3: as Game 2, but we abort if the adversary outputs validpk∗,m∗,σ∗ for which we cannot (as the holder of skP3SSig) calculate pk which makes JudgeP3Spk∗,pkP3SSig,pk,πP3S,σ∗,m∗ output 0. Let this event be E3.IfE3 occurs, we have a bogus proof π contained in σ∗ as it proves a false statement. Thus, ℬ proceeds as in the prior game (doing everything honestly, but using simulated proofs and simulated crsΩ) and can simply return the statement claimed to be proven by π and π itself. PrS2−PrS3 is negligible.In conclusion, the proposed blockchain protocol achieves accountability.


## 7. Performance

In this section, we first give functionality comparison among our redactable blockchain protocol and several related redactable blockchain protocols [11, 13–15]. Then, we analyze the computational burden of our redactable blockchain protocol through several experiments.


### 7.1. Functionality Comparison

We give functionality comparison among our scheme and the related schemes [11, 13–15]. As shown in Table 2, our scheme is the only one that satisfies all of the following properties: fine-grained access control, controllable edit, accountability, and supporting the redaction of both additional information and UTXO. The schemes in [11, 14] cannot support fine-grained access control. The scheme in [13] cannot effectively support harmful data deletion. All of these related redactable blockchain protocols cannot support controllable edit, accountability, and the editing of both additional information and UTXO.Table 2
Comparison of functionality among our redactable blockchain protocol and related protocols.
ProtocolsFine-grained access controlControllable editHarmful data deletionAccountabilityData type[11]××√×Additional information[13]√×××Additional information[14]××√×Additional informationOurs√√√√Additional information and UTXO


### 7.2. Proof-of-Concept Implementation

To evaluate the practicality of the proposed blockchain protocol, we implement a full-fledged blockchain system in Python 3.5.3, which is carried out on a desktop with an Intel Core (TM) i5-4300 CPU @ 2.13 GHz and 8.0 GB RAM.The blockchain system can achieve all the basic functionalities of Ethereum Enterprise. Separately, the blockchain system, including a subset of Ethereum Enterprise’s script language, allows the authorized user to redact the transaction and the miner to delete the harmful data. We rely on the PoW consensus mechanism as Ethereum Enterprise does.We evaluate the performance of the blockchain system for chain validation in different scenarios. In order to measure the cost time of chain validation, we validate chains containing different number of blocks and redaction transactions. A new chain is created and validated 50 times in each experiment, and the cost time of chain validation is the arithmetic mean of the run time of all runs. Each chain consists of up to 50,000 blocks, which approximate a one-year snapshot of the Ethereum Enterprise. Each block includes 1000 transactions (Figures11–14).(i)
Overhead Compared to the Immutable Blockchain. In order to evaluate the overhead of the redactable blockchain protocol with no redactions performed compared to the immutable blockchain, in the series of experiments, the length of chains ranges from 10,000 to 50,000 blocks. As shown in Figure 11, the redactable blockchain protocol has only a more tiny overhead than the immutable blockchain. With the increase of the length of the chain, the overhead is smaller. The reason is that the only extra step of the redactable blockchain is to check if any votes are contained in the new block. The run time of this step is negligible compared to the time of chain validating when the length of the chain is larger enough.(ii)
Overhead by the Number of Redactions. In order to evaluate the overhead of the redactable blockchain protocol with the increasing number of redactions compared to the redactable blockchain with no redaction, in the series of experiments, the number of redactions ranges from 1000 to 5000. As shown in Figure 12, the overhead is linear in the number of redactions because we need to collect the votes for the redaction in the voting phase.(iii)
Overhead by the Number of Removals. In order to evaluate the overhead of the redactable blockchain protocol with the increasing number of removals compared to the redactable blockchain with no removal, in the series of experiments, the number of removals ranges from 1000 to 5000. As shown in Figure 13, the overhead is linear in the number of removals because the miner generating the new block needs to remove the harmful information from the previous block.(iv)
Overhead by the Voting Parameterρ. In order to evaluate the overhead of the redactable blockchain protocol with different voting periods, in the series of experiments, we set that the number of redactions is 1000, and the threshold ratio of the votes is ρ≥1/2. As shown in Figure 14, the overhead is small and is most linear in the voting period.Figure 11
The overhead of the redactable blockchain without performing redaction compared to the immutable chain.Figure 12
The overhead of the redactable blockchain for an increasing number of redactions compared to the redactable chain with no redaction.Figure 13
The overhead of the redactable blockchain for an increasing number of removals compared to the redactable chain with no removal.Figure 14
The overhead of the redactable blockchain for increasing voting periods compared to the redactable chain on a fixed voting period.


## 7.1. Functionality Comparison

We give functionality comparison among our scheme and the related schemes [11, 13–15]. As shown in Table 2, our scheme is the only one that satisfies all of the following properties: fine-grained access control, controllable edit, accountability, and supporting the redaction of both additional information and UTXO. The schemes in [11, 14] cannot support fine-grained access control. The scheme in [13] cannot effectively support harmful data deletion. All of these related redactable blockchain protocols cannot support controllable edit, accountability, and the editing of both additional information and UTXO.Table 2
Comparison of functionality among our redactable blockchain protocol and related protocols.
ProtocolsFine-grained access controlControllable editHarmful data deletionAccountabilityData type[11]××√×Additional information[13]√×××Additional information[14]××√×Additional informationOurs√√√√Additional information and UTXO


## 7.2. Proof-of-Concept Implementation

To evaluate the practicality of the proposed blockchain protocol, we implement a full-fledged blockchain system in Python 3.5.3, which is carried out on a desktop with an Intel Core (TM) i5-4300 CPU @ 2.13 GHz and 8.0 GB RAM.The blockchain system can achieve all the basic functionalities of Ethereum Enterprise. Separately, the blockchain system, including a subset of Ethereum Enterprise’s script language, allows the authorized user to redact the transaction and the miner to delete the harmful data. We rely on the PoW consensus mechanism as Ethereum Enterprise does.We evaluate the performance of the blockchain system for chain validation in different scenarios. In order to measure the cost time of chain validation, we validate chains containing different number of blocks and redaction transactions. A new chain is created and validated 50 times in each experiment, and the cost time of chain validation is the arithmetic mean of the run time of all runs. Each chain consists of up to 50,000 blocks, which approximate a one-year snapshot of the Ethereum Enterprise. Each block includes 1000 transactions (Figures11–14).(i)
Overhead Compared to the Immutable Blockchain. In order to evaluate the overhead of the redactable blockchain protocol with no redactions performed compared to the immutable blockchain, in the series of experiments, the length of chains ranges from 10,000 to 50,000 blocks. As shown in Figure 11, the redactable blockchain protocol has only a more tiny overhead than the immutable blockchain. With the increase of the length of the chain, the overhead is smaller. The reason is that the only extra step of the redactable blockchain is to check if any votes are contained in the new block. The run time of this step is negligible compared to the time of chain validating when the length of the chain is larger enough.(ii)
Overhead by the Number of Redactions. In order to evaluate the overhead of the redactable blockchain protocol with the increasing number of redactions compared to the redactable blockchain with no redaction, in the series of experiments, the number of redactions ranges from 1000 to 5000. As shown in Figure 12, the overhead is linear in the number of redactions because we need to collect the votes for the redaction in the voting phase.(iii)
Overhead by the Number of Removals. In order to evaluate the overhead of the redactable blockchain protocol with the increasing number of removals compared to the redactable blockchain with no removal, in the series of experiments, the number of removals ranges from 1000 to 5000. As shown in Figure 13, the overhead is linear in the number of removals because the miner generating the new block needs to remove the harmful information from the previous block.(iv)
Overhead by the Voting Parameterρ. In order to evaluate the overhead of the redactable blockchain protocol with different voting periods, in the series of experiments, we set that the number of redactions is 1000, and the threshold ratio of the votes is ρ≥1/2. As shown in Figure 14, the overhead is small and is most linear in the voting period.Figure 11
The overhead of the redactable blockchain without performing redaction compared to the immutable chain.Figure 12
The overhead of the redactable blockchain for an increasing number of redactions compared to the redactable chain with no redaction.Figure 13
The overhead of the redactable blockchain for an increasing number of removals compared to the redactable chain with no removal.Figure 14
The overhead of the redactable blockchain for increasing voting periods compared to the redactable chain on a fixed voting period.


## 8. Conclusions

In this paper, we proposed a fine-grained and controllably redactable blockchain with harmful data forced removal. Our scheme not only supports the usual redaction of transactions but also the forced removal of harmful information in the blockchain. The originator of the transaction could specify a fine-grained access control structure about who could redact the transaction and which portions of the transaction could be redacted. Any user could initiate a transaction that contains the index of the block which included harmful information without spending transaction fees. If the harmful information is contained in a block, it was forced to be deleted by the miner who created the new block. The user who provided the index of the block could receive the reward which was borne by the malicious user. The malicious user would be blacklisted if rewards were not paid within a period of time, and any transaction about the user would not be performed later. Furthermore, the scheme supported not only the redaction of additional data but also UTXO. Finally, we demonstrated that the scheme was secure and feasible via formal security analysis and proof-of-concept implementation.Note that the proposed fine-grained and controllably redactable blockchain protocol with harmful data forced removal is suitable for permissioned blockchains, such as Hyperledger, Ethereum Enterprise, Ripple, and Quorum. There is another type of blockchain called permissionless blockchain, such as Bitcoin and Ethereum. Constructing the redactable permissionless blockchain protocol is a challenge and an interesting open problem. In our future work, we will also focus on designing more sophisticated solutions to the redactable permissionless blockchain protocol.



---

*Source: 3680359-2021-05-29.xml*