# Privacy-Preserving Redactable Blockchain for Internet of Things

Authors: Yanli Ren; Xianji Cai; Mingqi Hu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In the traditional blockchain system, data is public and cannot be redacted. With the development of blockchain technology, the problem that the data cannot be altered will be more serious once it is written on the chain. Recently, some redactable blockchain schemes have been proposed. However, most of the schemes are based on the public blockchain, and the users’ identities and transaction data may be disclosed. To solve the problem of privacy disclosure, we propose a privacy-preserving transaction-level redactable blockchain. In the proposed scheme, symmetric encryption and ring signature are used to protect transaction data and the users’ identities, respectively. In order to prove the legality of data redaction, the transaction sender can reveal the invalid users’ identities and transaction data in an anonymous environment. To construct a transaction-level redactable blockchain, the users only need to replace a single transaction to complete the data redaction instead of replacing the entire block. The experimental results show that the proposed scheme saves 20% of the redaction time compared to the previous privacy-preserving blockchains, so the redaction efficiency is higher.


---

## Body

## 1. Introduction

In January 2009, blockchain was invented as the underlying technology of Bitcoin [1], which merged the important achievements in some fields such as modern cryptography and distributed network. After the emergence of Bitcoin, the blockchain network has supported massive transfer transactions steadily in a purely distributed manner [2]. Especially, the combinations of blockchain technology and the Internet of things (IoT) begin to appear in large numbers, which proves that the blockchain is a good solution to the basic needs of distributed networks [3, 4]. For example, the blockchain is used to ensure the safety and anticounterfeiting traceability of the food supply chain [5].With the wide application of blockchain technology in E-government, military, and medical fields [6–8], the problem that the data cannot be altered will be more serious. The continuous growth of data in the blockchain leads to a dramatical increase in storage space and data verification cost, which will result in the continuous decline of the number of the full-nodes and intensify the trend of centralization in blockchain. Moreover, the computational overhead for the nodes to verify historical data will also increase, which is unfriendly to some IoT devices with limited computing resource [9]. Therefore, redacting or deleting the useless data will be an important means to improve the performance and scalability of the blockchain.Recently, some redactable blockchains have been proposed [10, 11]. However, the users’ identities and transactions are public. Even if the IoT devices simply apply pseudonyms when acting in the blockchain, they can only provide limited identity privacy. The adversary can still trace the transparent block data to find out the relations between the identities and transactions and analyze the real identities of the users [12]. Moreover, in the process of data redaction, the personal information of the redactors may be revealed. Due to the wide applications of IoT devices, the data owners do not want to leak the identity privacy or business secrets to their competitors. Therefore, it is extremely important to propose a privacy-preserving redactable blockchain to simultaneously protect the privacy of the users and rectify the incorrect data.


### 1.1. Privacy-Preserving Blockchain

An important feature of blockchain is data transparency, which means that the identity and transaction data in public blockchain are transparent. However, for some companies or users, data is extremely important to maintain their strong competitiveness, and sharing data may bring some security challenges. Therefore, more and more privacy-preserving mechanisms on blockchain have been proposed by researchers. At present, the most popular solutions to protect the identity privacy are ring signature [13], mixing services [14], and noninteractive zero-knowledge proof [15], and the most common methods to protect the data privacy include zero-knowledge proof, homomorphic encryption, and commitment schemes [16].


### 1.2. Redactable Blockchain

In [10], the concept of redactable blockchain is first raised. The main idea of their protocol was to keep the block hash link compatible with the current state when a redaction happens. They use a special hash function called chameleon hash [17] to replace the traditional collision-resistant hash function, where collisions of the hash can be computed with trapdoors. Thus, a collision can be calculated to keep the hash linked as usual. In this work, the authors improve the chameleon hash protocol and solve the key exposure problem in the previous chameleon hash and also provide the formal security analysis of their new protocol. However, in this scheme, a trusted-party is needed to control the trapdoor of chameleon hash, which violates the idea of decentralization of the blockchain, and the redaction operation does not represent the opinions of the whole system. Moreover, this scheme can only realize data redaction at the block-level. Once a data is redacted, the whole block needs to be replaced.Later, Deuber et al. proposed a history dependent redactable scheme [11], which is dependent on the history of the transaction data. They propose a redactable protocol in the permissionless setting, which can be integrated to Bitcoin easily. The scheme preserves the original transaction merkle root to keep the hash linked if a block is altered. In their scheme, complex cryptographic tools or trusted parties are not used, and the experiment proves that their scheme is an efficient and feasible protocol. However, in this scheme, consensus-based voting is used during the process of redaction, and this will lead to the privacy disclosure of the redactor. Moreover, this scheme also realizes data redaction at the block-level, but not on the transaction-level. Once a data is redacted, the whole block needs to be replaced.Most of the redactable blockchains are realized on the block-level, which means that transactions can only be redacted by a block as a unit. Recently, a transaction-level redactable blockchain was proposed [18], where only the hash collision of the redacted transaction should be found. They propose a policy-based chameleon hash, which combines the ciphertext-policy attributed based encryption (CP-ABE) algorithm with a chameleon hash scheme. In their scheme, the attributes of a user should satisfy the access structure of the CP-ABE algorithm [18]. The chameleon hash collision can only be found when a user obtains the short-term and the long-term trapdoors at the same time.However, all of the solutions to blockchain redaction ignore the issue of data privacy disclosure. Recently, a deletable blockchain was proposed \cite{cai2019privacy}, where the identities and transactions of the users are well protected when a block is deleted. In order to delete a block in an anonymous environment, the real identities or the transaction data are disclosed through traceable ring signature or Petersen commitment. Moreover, a linkable multisignature scheme was proposed to prevent the disclosure of the users’ identities, which can trace an adversary if he generates a signature more than one time. However, the block can only be deleted by the sender of a transaction but cannot be redacted. Thus, it is urgent and meaningful to propose a redactable blockchain without disclosing the identities and transaction data of the users.


### 1.3. Our Contributions

(1)
We propose a privacy-preserving redactable blockchain protocol without disclosing the identities and transaction data of the users. A threshold ring signature and a symmetric encryption algorithm are separately used to protect the users’ identities and transaction data.(2)
The proposed blockchain is a fine-grained transaction-level redactable one. The block data can be redacted on the transaction level instead of block level, which means that other transactions in the block do not need to be changed when one transaction is redacted.(3)
We formalize four security requirements for a privacy-preserving redactable blockchain including identity privacy, data privacy, chain quality, and common prefix and prove that our proposed protocol is provably secure based on symmetric encryption and threshold ring signature.(4)
The efficiency of the proposed protocol is demonstrated by a series of experiments. The result shows that the time of redacting a transaction is about twice that of creating a block, and the proposed protocol can save about 20% of computational costs than the previous ones.


## 1.1. Privacy-Preserving Blockchain

An important feature of blockchain is data transparency, which means that the identity and transaction data in public blockchain are transparent. However, for some companies or users, data is extremely important to maintain their strong competitiveness, and sharing data may bring some security challenges. Therefore, more and more privacy-preserving mechanisms on blockchain have been proposed by researchers. At present, the most popular solutions to protect the identity privacy are ring signature [13], mixing services [14], and noninteractive zero-knowledge proof [15], and the most common methods to protect the data privacy include zero-knowledge proof, homomorphic encryption, and commitment schemes [16].


## 1.2. Redactable Blockchain

In [10], the concept of redactable blockchain is first raised. The main idea of their protocol was to keep the block hash link compatible with the current state when a redaction happens. They use a special hash function called chameleon hash [17] to replace the traditional collision-resistant hash function, where collisions of the hash can be computed with trapdoors. Thus, a collision can be calculated to keep the hash linked as usual. In this work, the authors improve the chameleon hash protocol and solve the key exposure problem in the previous chameleon hash and also provide the formal security analysis of their new protocol. However, in this scheme, a trusted-party is needed to control the trapdoor of chameleon hash, which violates the idea of decentralization of the blockchain, and the redaction operation does not represent the opinions of the whole system. Moreover, this scheme can only realize data redaction at the block-level. Once a data is redacted, the whole block needs to be replaced.Later, Deuber et al. proposed a history dependent redactable scheme [11], which is dependent on the history of the transaction data. They propose a redactable protocol in the permissionless setting, which can be integrated to Bitcoin easily. The scheme preserves the original transaction merkle root to keep the hash linked if a block is altered. In their scheme, complex cryptographic tools or trusted parties are not used, and the experiment proves that their scheme is an efficient and feasible protocol. However, in this scheme, consensus-based voting is used during the process of redaction, and this will lead to the privacy disclosure of the redactor. Moreover, this scheme also realizes data redaction at the block-level, but not on the transaction-level. Once a data is redacted, the whole block needs to be replaced.Most of the redactable blockchains are realized on the block-level, which means that transactions can only be redacted by a block as a unit. Recently, a transaction-level redactable blockchain was proposed [18], where only the hash collision of the redacted transaction should be found. They propose a policy-based chameleon hash, which combines the ciphertext-policy attributed based encryption (CP-ABE) algorithm with a chameleon hash scheme. In their scheme, the attributes of a user should satisfy the access structure of the CP-ABE algorithm [18]. The chameleon hash collision can only be found when a user obtains the short-term and the long-term trapdoors at the same time.However, all of the solutions to blockchain redaction ignore the issue of data privacy disclosure. Recently, a deletable blockchain was proposed \cite{cai2019privacy}, where the identities and transactions of the users are well protected when a block is deleted. In order to delete a block in an anonymous environment, the real identities or the transaction data are disclosed through traceable ring signature or Petersen commitment. Moreover, a linkable multisignature scheme was proposed to prevent the disclosure of the users’ identities, which can trace an adversary if he generates a signature more than one time. However, the block can only be deleted by the sender of a transaction but cannot be redacted. Thus, it is urgent and meaningful to propose a redactable blockchain without disclosing the identities and transaction data of the users.


## 1.3. Our Contributions

(1)
We propose a privacy-preserving redactable blockchain protocol without disclosing the identities and transaction data of the users. A threshold ring signature and a symmetric encryption algorithm are separately used to protect the users’ identities and transaction data.(2)
The proposed blockchain is a fine-grained transaction-level redactable one. The block data can be redacted on the transaction level instead of block level, which means that other transactions in the block do not need to be changed when one transaction is redacted.(3)
We formalize four security requirements for a privacy-preserving redactable blockchain including identity privacy, data privacy, chain quality, and common prefix and prove that our proposed protocol is provably secure based on symmetric encryption and threshold ring signature.(4)
The efficiency of the proposed protocol is demonstrated by a series of experiments. The result shows that the time of redacting a transaction is about twice that of creating a block, and the proposed protocol can save about 20% of computational costs than the previous ones.


## 2. Preliminaries

Some definitions and algorithms utilized in the proposed protocol are introduced in this section.


### 2.1. An Introduction of Blockchain

Assume thatBj−1,Bj,Bj+1 are three adjacent blocks in a blockchain. As shown in Figure 1, the j-th block is denoted as Bj=sj,xj,ctrj. The block can point to its previous block through the hash value sj∈0，1k. All of the transactions packaged in a block are contained in xj∈0，1∗, and ctr∈ℕ is the result of the PoW puzzle [20]. The users check whether the block Bj is valid or not by the following inequality:(1)validateBlockDBj=H1ctrj,H2sj,xj<D,where the parameter D is the target difficulty coefficient of the PoW consensus mechanism. H1,H2:0,1∗⟶0,1k are two different cryptographic hash functions.Figure 1
Block structure in a blockchain.A blockchain is composed of a series of blocks, which have solved the PoW puzzle. The newly created block points to its previous block through the hash value. We denote the length of a chainlenC, and the rightmost block of chain C can be denoted as lenC=x′,s′,ctr′. It should be noted that a blockchain can be an empty chain, which is denoted as C=E.The chainC will be updated as C′=C‖Bj+1 if a new block Bj+1 is generated and validated by the users, and at present, the last block of the chain C′ is the block Bj+1. For any q≥0, Cq is denoted as the chain after deleting the rightmost q blocks. Note that Cq can be an empty chain if q is larger than n, where n is the length of a chain C. If the prefix of chain C1 is C2, we write C1≼C2.


### 2.2. Redactable Protocol in the Public Blockchain

In this subsection, we introduce a redactable blockchain protocol [11], which will be used in our paper. The main contribution is that it preserves the old state oj=H2sj,xj of a block, which is actually the merkle root of the old transactions. As shown in Figure 2, a block is linked to its predecessor by two links, an old hash link (solid arrow) and a new hash link (dashed arrow), and sj+1=H1ctrj,H2sj,xj,oj holds [11]. When the block Bj is redacted, the new hash link between the block Bj and Bj+1 is broken (marked by a red cross) because sj+1≠H1ctrj,H2sj,xj∗,oj. However, Bj+1 can still point to Bj successfully through the old hash link (solid arrow) since the merkle root of the old transaction (old state) is still preserved. The reason is shown as follows:(2)sj+1=H1ctrj,oj,oj=H1ctrj,H2sj,xj,oj.Figure 2
The redacted block can still be linked by the old state.Please see reference [11] for the details.


### 2.3. Threshold Ring Signature

The following algorithms are commonly included in at,n threshold ring signature (TRS) scheme, where t0≤t≤n is the value of the threshold, n is the number of the ring members, and t<n [21]:TRS_Setup: on input security parameterλ, it outputs the public keys pk1,…,pkn and private keys sk1,…,skn of n ring membersTRS_Sign: on input a messagem∈0，1∗, a ring containing n members with n public keys pk1,…,pkn, and private keys sk1,…,skn of t members, it outputs a threshold ring signature σ on the message mTRS_Verify: on input a messagem, a signature σ and public keys pk1,…,pkn of n members in a ring, it outputs 0 or 1 to indicate accepting or rejecting the signature


## 2.1. An Introduction of Blockchain

Assume thatBj−1,Bj,Bj+1 are three adjacent blocks in a blockchain. As shown in Figure 1, the j-th block is denoted as Bj=sj,xj,ctrj. The block can point to its previous block through the hash value sj∈0，1k. All of the transactions packaged in a block are contained in xj∈0，1∗, and ctr∈ℕ is the result of the PoW puzzle [20]. The users check whether the block Bj is valid or not by the following inequality:(1)validateBlockDBj=H1ctrj,H2sj,xj<D,where the parameter D is the target difficulty coefficient of the PoW consensus mechanism. H1,H2:0,1∗⟶0,1k are two different cryptographic hash functions.Figure 1
Block structure in a blockchain.A blockchain is composed of a series of blocks, which have solved the PoW puzzle. The newly created block points to its previous block through the hash value. We denote the length of a chainlenC, and the rightmost block of chain C can be denoted as lenC=x′,s′,ctr′. It should be noted that a blockchain can be an empty chain, which is denoted as C=E.The chainC will be updated as C′=C‖Bj+1 if a new block Bj+1 is generated and validated by the users, and at present, the last block of the chain C′ is the block Bj+1. For any q≥0, Cq is denoted as the chain after deleting the rightmost q blocks. Note that Cq can be an empty chain if q is larger than n, where n is the length of a chain C. If the prefix of chain C1 is C2, we write C1≼C2.


## 2.2. Redactable Protocol in the Public Blockchain

In this subsection, we introduce a redactable blockchain protocol [11], which will be used in our paper. The main contribution is that it preserves the old state oj=H2sj,xj of a block, which is actually the merkle root of the old transactions. As shown in Figure 2, a block is linked to its predecessor by two links, an old hash link (solid arrow) and a new hash link (dashed arrow), and sj+1=H1ctrj,H2sj,xj,oj holds [11]. When the block Bj is redacted, the new hash link between the block Bj and Bj+1 is broken (marked by a red cross) because sj+1≠H1ctrj,H2sj,xj∗,oj. However, Bj+1 can still point to Bj successfully through the old hash link (solid arrow) since the merkle root of the old transaction (old state) is still preserved. The reason is shown as follows:(2)sj+1=H1ctrj,oj,oj=H1ctrj,H2sj,xj,oj.Figure 2
The redacted block can still be linked by the old state.Please see reference [11] for the details.


## 2.3. Threshold Ring Signature

The following algorithms are commonly included in at,n threshold ring signature (TRS) scheme, where t0≤t≤n is the value of the threshold, n is the number of the ring members, and t<n [21]:TRS_Setup: on input security parameterλ, it outputs the public keys pk1,…,pkn and private keys sk1,…,skn of n ring membersTRS_Sign: on input a messagem∈0，1∗, a ring containing n members with n public keys pk1,…,pkn, and private keys sk1,…,skn of t members, it outputs a threshold ring signature σ on the message mTRS_Verify: on input a messagem, a signature σ and public keys pk1,…,pkn of n members in a ring, it outputs 0 or 1 to indicate accepting or rejecting the signature


## 3. Privacy-Preserving Redactable Blockchain

This section describes a privacy-preserving redactable blockchain protocolΓ', which can redact the block data on the transaction-level without disclosing the transaction data and the identities of the users.


### 3.1. Syntax of Privacy-Preserving Redactable Blockchain

We construct a privacy-preserving redactable blockchain protocolΓ′, which contains the following four algorithms:0,1⟵Γ′.validateReqC,j,i,txi∗,m,K: on inputting a chain C, an index j of the redacted block, an index i of the redacted transaction, an initial candidate transaction txi∗, the old transaction data m, and the old encryption key K, it returns 1 if the redaction request is valid; otherwise, it returns 0.0,1⟵Γ′.validateCandTxC,txi∗∗,j: on inputting a chain C, a final candidate transaction txi∗∗ and an index j, it returns 0 if txi∗∗ is valid; otherwise, it returns 1.0,1⟵Γ′.validateChainC: on inputting a chain C, it returns 1 if the chain is valid; otherwise, it returns 0.0,1⟵Γ′.validateBlockB: on inputting a block B, it returns 1 if the block is valid; otherwise, it returns 0.


### 3.2. Our Proposed Protocol

In the proposed protocol, a regular transaction is denoted astx=EKm,RSig, where m is the transaction data including the input and output of a transaction, E⋅ is a symmetric encryption algorithm, EKm is the ciphertext of the transaction data using a key K and RSig is a ring signature to protect the identity privacy of the users. H:0，1∗⟶0，1k is a cryptographic hash function. The block data is denoted as x=tx1,tx2,…,txp, where p is the number of the transactions packaged in each block.


#### 3.2.1. Proposing a Redaction Request

Once a user joins in the blockchain system, he needs to generate a public key as his identity, and a private key, which will be used to generate a signature. If a miner wants to participate in a redaction process, he can apply for the key generation algorithm of the threshold ring signature system to get another key pair when he joins the blockchain system. The key generation algorithm is executed by a trusted party, such as certification authority (CA). It should be noted that the private key generated by the user as the identity is different from that generated by the TRS system, where the former is used to generate the ring signatureRSig to protect the identity of the users, and the latter is used to generate the threshold ring signature TRS to allow redacting a transaction in a block.If a user wants to propose a redaction request for the transactiontxi in block Bj, he discloses the transaction encryption key K and the encrypted transaction data m first. Then, he generates a new transaction m′, picks up a new encryption key K′, and calculates Hm,K′,m′,K, EK′m′, ring signature RSig′ and a ring signature S on Hm,K′,m′,K. Next, the user generates an initial candidate transaction txi∗=EK′m′,RSig′,Hm,K′,m′,K,S. Finally, the user broadcasts the redaction request rj,i=j,i,txi∗,m,K to the whole network. Note that two ring signatures are both generated by the data owner, who randomly chooses two rings including some users on the chain, and compute the signatures by the public keys of these users.


#### 3.2.2. Joining a Redaction Operation

When a miner in the blockchain receives a redaction request, he invokes Algorithm1Γ′.validateReq to judge whether the redaction request is valid or not. If the redaction request is valid, he votes for the redaction by putting his vote result in the latest block he mines. If the number of miners who approve of the redaction request exceeds the threshold t of the threshold ring signature, these miners generate a threshold ring signature TRS jointly on the redaction message. Finally, a final candidate transaction txi∗∗ is generated and broadcasted to the network, where txi∗∗=txi∗‖TRS.


#### 3.2.3. Validating a Redaction Operation

Everyone can verify whether a final candidate transaction is valid or not by invokingΓ′.validateCandTx (Algorithm 2). If the final candidate transaction txi∗∗ is valid, the user replaces the old transaction txi in block Bj with the final candidate transaction txi∗∗ in their local chain. The process of redacting a transaction is shown in Figure 3.Figure 3
Proposing a redaction for the transactiontxi of block Bj.


## 3.1. Syntax of Privacy-Preserving Redactable Blockchain

We construct a privacy-preserving redactable blockchain protocolΓ′, which contains the following four algorithms:0,1⟵Γ′.validateReqC,j,i,txi∗,m,K: on inputting a chain C, an index j of the redacted block, an index i of the redacted transaction, an initial candidate transaction txi∗, the old transaction data m, and the old encryption key K, it returns 1 if the redaction request is valid; otherwise, it returns 0.0,1⟵Γ′.validateCandTxC,txi∗∗,j: on inputting a chain C, a final candidate transaction txi∗∗ and an index j, it returns 0 if txi∗∗ is valid; otherwise, it returns 1.0,1⟵Γ′.validateChainC: on inputting a chain C, it returns 1 if the chain is valid; otherwise, it returns 0.0,1⟵Γ′.validateBlockB: on inputting a block B, it returns 1 if the block is valid; otherwise, it returns 0.


## 3.2. Our Proposed Protocol

In the proposed protocol, a regular transaction is denoted astx=EKm,RSig, where m is the transaction data including the input and output of a transaction, E⋅ is a symmetric encryption algorithm, EKm is the ciphertext of the transaction data using a key K and RSig is a ring signature to protect the identity privacy of the users. H:0，1∗⟶0，1k is a cryptographic hash function. The block data is denoted as x=tx1,tx2,…,txp, where p is the number of the transactions packaged in each block.


### 3.2.1. Proposing a Redaction Request

Once a user joins in the blockchain system, he needs to generate a public key as his identity, and a private key, which will be used to generate a signature. If a miner wants to participate in a redaction process, he can apply for the key generation algorithm of the threshold ring signature system to get another key pair when he joins the blockchain system. The key generation algorithm is executed by a trusted party, such as certification authority (CA). It should be noted that the private key generated by the user as the identity is different from that generated by the TRS system, where the former is used to generate the ring signatureRSig to protect the identity of the users, and the latter is used to generate the threshold ring signature TRS to allow redacting a transaction in a block.If a user wants to propose a redaction request for the transactiontxi in block Bj, he discloses the transaction encryption key K and the encrypted transaction data m first. Then, he generates a new transaction m′, picks up a new encryption key K′, and calculates Hm,K′,m′,K, EK′m′, ring signature RSig′ and a ring signature S on Hm,K′,m′,K. Next, the user generates an initial candidate transaction txi∗=EK′m′,RSig′,Hm,K′,m′,K,S. Finally, the user broadcasts the redaction request rj,i=j,i,txi∗,m,K to the whole network. Note that two ring signatures are both generated by the data owner, who randomly chooses two rings including some users on the chain, and compute the signatures by the public keys of these users.


### 3.2.2. Joining a Redaction Operation

When a miner in the blockchain receives a redaction request, he invokes Algorithm1Γ′.validateReq to judge whether the redaction request is valid or not. If the redaction request is valid, he votes for the redaction by putting his vote result in the latest block he mines. If the number of miners who approve of the redaction request exceeds the threshold t of the threshold ring signature, these miners generate a threshold ring signature TRS jointly on the redaction message. Finally, a final candidate transaction txi∗∗ is generated and broadcasted to the network, where txi∗∗=txi∗‖TRS.


### 3.2.3. Validating a Redaction Operation

Everyone can verify whether a final candidate transaction is valid or not by invokingΓ′.validateCandTx (Algorithm 2). If the final candidate transaction txi∗∗ is valid, the user replaces the old transaction txi in block Bj with the final candidate transaction txi∗∗ in their local chain. The process of redacting a transaction is shown in Figure 3.Figure 3
Proposing a redaction for the transactiontxi of block Bj.


## 3.2.1. Proposing a Redaction Request

Once a user joins in the blockchain system, he needs to generate a public key as his identity, and a private key, which will be used to generate a signature. If a miner wants to participate in a redaction process, he can apply for the key generation algorithm of the threshold ring signature system to get another key pair when he joins the blockchain system. The key generation algorithm is executed by a trusted party, such as certification authority (CA). It should be noted that the private key generated by the user as the identity is different from that generated by the TRS system, where the former is used to generate the ring signatureRSig to protect the identity of the users, and the latter is used to generate the threshold ring signature TRS to allow redacting a transaction in a block.If a user wants to propose a redaction request for the transactiontxi in block Bj, he discloses the transaction encryption key K and the encrypted transaction data m first. Then, he generates a new transaction m′, picks up a new encryption key K′, and calculates Hm,K′,m′,K, EK′m′, ring signature RSig′ and a ring signature S on Hm,K′,m′,K. Next, the user generates an initial candidate transaction txi∗=EK′m′,RSig′,Hm,K′,m′,K,S. Finally, the user broadcasts the redaction request rj,i=j,i,txi∗,m,K to the whole network. Note that two ring signatures are both generated by the data owner, who randomly chooses two rings including some users on the chain, and compute the signatures by the public keys of these users.


## 3.2.2. Joining a Redaction Operation

When a miner in the blockchain receives a redaction request, he invokes Algorithm1Γ′.validateReq to judge whether the redaction request is valid or not. If the redaction request is valid, he votes for the redaction by putting his vote result in the latest block he mines. If the number of miners who approve of the redaction request exceeds the threshold t of the threshold ring signature, these miners generate a threshold ring signature TRS jointly on the redaction message. Finally, a final candidate transaction txi∗∗ is generated and broadcasted to the network, where txi∗∗=txi∗‖TRS.


## 3.2.3. Validating a Redaction Operation

Everyone can verify whether a final candidate transaction is valid or not by invokingΓ′.validateCandTx (Algorithm 2). If the final candidate transaction txi∗∗ is valid, the user replaces the old transaction txi in block Bj with the final candidate transaction txi∗∗ in their local chain. The process of redacting a transaction is shown in Figure 3.Figure 3
Proposing a redaction for the transactiontxi of block Bj.


## 4. Protocol Description

In this subsection, we introduce each algorithm in the proposed protocol in detail.Algorithm1 can validate whether a redaction request is valid or not. The miners generate a threshold ring signature if the validation of step 5 to step 9 all passed.Algorithm 1:validateReq (implements Γ′.validateReq).
Input: BlockchainC, redaction request rj,i=j,i,txi∗,m,KOutput: 0/1(1)
Parse the originalj -th block Bj∗=sj,xj∗,ctrj,oj;(2)
Parse the old block dataxj=tx1,tx2,…,txp;(3)
Replace the old transactiontxi with the initial candidate transaction txi∗;(4)
Parse the new block dataxj∗=tx1,tx2,…,txi∗,…,txp;(5)
Parse the redactedj-th block Bj∗=sj,xj∗,ctrj,oj;(6)
IfvalidateBlockBj∗=0, return 0;(7)
Parse the initial candidate transactiontxi∗=EK′m′,RSig′,Hm,K,m′,K′,S.(8)
CalculateEKm using the disclosed transaction data m and encryption key K.(9)
CompareEKm with the ciphertext in the original transaction. If not equal, return 0;(10)
Validate the ring signatureS contained in the redacted transaction txi∗ and compare the message signed by S with the digest Hm,K,m′,K′, if not equal return 0;(11)
Return 1.Algorithm2 can validate whether a final candidate transaction is valid or not. This algorithm first checks whether the redacted block Bj∗ is valid or not. In line 6, Algorithm 2 checks the validity of the threshold ring signature TRS. In line 11, it checks the old hash link from Bj∗ to Bj−1 and the hash link from Bj+1 to Bj∗. The final candidate transaction can be considered valid if the hash link of block Bj can point to the previous block correctly. The user can replace the old transaction with the final candidate transaction in his local chain.Algorithm 2:validateCandTx(implements Γ′.validateCandTx).
Input：ChainC, a final candidate transaction txi∗∗, an index j of the blockOutput：0/1(1)
Parsexj∗=tx1,tx2,…,txi∗,…,txp;(2)
ParseBj∗=sj,xj∗,ctrj,oj;(3)
Parsetxi∗∗=txi∗‖TRS.(4)
ifvalidateBlockBj∗=0 then(5)
return 0;(6)
ifTRS is invalid then(7)
return 0;(8)
Compare the message signed byTRS and the hash of the redaction request, If not equal, return 0;(9)
ParseBj−1=sj−1,xj−1,ctrj−1,oj−1;(10)
ParseBj+1=sj+1,xj+1,ctrj+1,oj+1;(11)
ifsj∗=Hctrj−1,oj−1,oj−1∧sj+1=Hctrj,oj,oj then(12)
return 1;(13)
else(14)
return 0;Algorithm3 describes how to validate a chain C in our system. This algorithm checks the chain C from the beginning to the end. Users only have to validate the head of the chain C if the length of a chain is 1. Otherwise, blocks should be validated one by one. In line 8, the users first check the current link between the neighboring blocks; if the link is broken, then the users check the old link in line 10. The users accept the block if the old link can point to the previous block successfully, and the candidate block is valid.Algorithm 3:validateChain(implements Γ′.validateChain).
Input: ChainC=B1,B2,…,Bn of length n.Output: 0/1(1)
j:=n;(2)
ifj=1 then(3)
returnvalidateBlockB1;(4)
whilej≥2 do(5)
ParseBj=sj,xj,ctrj,oj;(6)
ifvalidateBlockBj=0 then(7)
return 0(8)
ifsj=H1ctrj−1,H2sj−1,xi−1,oj−1 then(9)
j=j+1;(10)
else ifsj=H1ctrj−1,oj−1,oj−1 then(11)
j=j+1;(12)
else(13)
return 0;(14)
return 1;(15)
return 1Algorithm4 describes how to validate a block B in our system. All of the transactions in the block should be checked using some predefined validation rules. In line 2, this algorithm checks whether the block B has solved the PoW puzzle or not. If the block has been redacted before, the old state of B should be checked to judge whether the block has solved the PoW puzzle or not.Algorithm 4:validateBlock(implements Γ.validateBlock).
Input: BlockB=s,x,ctr,oOutput: 0/1(1)
if all the transactions inx are valid then(2)
ifH1ctr,H2s,x,o<D∨H1ctr,o,o<D then(3)
return 1;(4)
else(5)
return 0;(6)
else(7)
return 0;


## 5. Security Analysis

The following contents provide security analysis of our privacy-preserving redactable blockchain protocolΓ′. The original public redactable blockchain protocol Γ satisfies two security requirements: chain quality and common prefix. Supposing that the protocol is a secure and reliable system, the proposed protocol Γ′ also satisfies these two requirements. Most importantly, Γ′ can protect the users’ identities and transaction data simultaneously. The following description will clearly illustrate that the proposed protocol is provably secure based on threshold ring signature, symmetric encryption, and the blockchain protocol proposed in [11].


### 5.1. Identity Privacy

The subsection states that the users’ identities are private in our protocol.Theorem 1.
The redactable blockchain scheme realizes the privacy of the users’ identities if the threshold ring signature is anonymous.Proof.
Proof. The game is executed between an adversaryA and a simulator ℬ. At the beginning of the game, ℬ is given a tuple Y,V0,V1,M,TRSM,Y,Vb, where b∈0,1, V0,V1 are both subsets of Y with same size, M is the redaction message including the redaction reasons and timestamp, and TRSM,Y,Vb is the threshold ring signature generated by Vb. Assuming that adversary A obtains the users’ identities with a nonnegligible probability in the proposed protocol, simulator ℬ can obtain the identities of the real signers with a nonnegligible probability in the threshold ring signature:Setup. The simulator sets up the blockchain system and sends the public parameters TRS⋅,E⋅,H⋅ to the adversary, where TRS⋅ is a threshold ring signature scheme, E⋅ is a symmetric encryption algorithm, and H⋅ is a secure hash function.Oracle Queries. The adversary simulates the following oracles:Transaction Generation Oracle. Adversary A sends an index j, some transactions collected from the blockchain system. The simulator ℬ returns a block txi:=EKmi,RSigi.Transaction Redaction Oracle. Adversary A sends a block index j, a transaction index i, an initial candidate transaction txi∗, an old transaction message m and an old transaction encryption key K, a redaction message M and two sets Y and V to the simulator, where Y is a public key set, V is a subset of Y and V≠V0orV1. The simulator returns the corresponding final candidate transaction txi∗∗=txi∗‖TRSM,Y,V.Challenge. The simulator ℬ generates the final candidate transaction txi∗^=txi∗^‖TRSM,Y,Vb, where M contains the disclosed transaction data m and encryption key K included in transaction txi∗^. Then, he transmits txi∗∗^ to the adversary A. A outputs b′∈0,1 and then ℬ submits b=b′. Assuming that A can guess the users’ identities successfully with a probability of more than 1/2, the simulator ℬ can distinguish the identities of the real signers with a probability of more than 1/2, and it contradicts the anonymity of the threshold ring signature. Therefore, it is impossible for the adversary A to guess the identities of the signers in a threshold ring signature successfully with a probability of more than 1/2, and the proposed redactable protocol can protect the users’ identities effectively.


### 5.2. Data Privacy

The subsection states that the transaction data in our blockchain system is private.Theorem 2.
The redactable blockchain scheme realizes the privacy of transaction data if the symmetric encryption algorithm is indistinguishable against chosen plaintext attack (IND-CPA) secure.Proof.
The game is executed between an adversaryA and a simulator ℬ. Assuming that adversary A can guess the transaction data with a nonnegligible probability in the proposed protocol, the simulator ℬ can distinguish the plaintext with a nonnegligible probability in the symmetric encryption scheme:Setup. The simulator sets up the blockchain system and generates a symmetric encryption algorithm E and an encryption key K and then sends the public parameters E to the adversary. The encryption key K is kept secret itself.Oracle Queries. The adversary simulates the following oracles:Encryption Oracle. The adversary sends the plaintext of transaction data m to the simulator. The simulator returns the corresponding ciphertext tx:=EKm,RSig, where EKm is the ciphertext of m by using the symmetric encryption algorithm, and RSig is the ring signature of the simulator on the ciphertext EKm.Challenge. Adversary A sends a tuple m0,m1,K0,K1,EKbmb to the simulator. Then, ℬ randomly chooses b∈0,1 and computes EKbmb. Note that EKbmb has never been queried in the Encryption oracles. Next, the simulator ℬ generates the ring signature RSig∗ on the ciphertext EKbmb and transmits the transaction ciphertext tx∗:=EKbmb,RSig∗ to adversary A.
A outputs b′∈0,1 and then ℬ submits b=b′. Assuming that A can guess the transaction data successfully with a probability of more than 1/2, the simulator ℬ can distinguish the ciphertext of two plaintexts with a probability of more than 1/2, and it contradicts the IND-CPA security of the symmetric encryption schemes. Therefore, it is impossible for the adversary A to guess the plaintext of transaction data successfully with a probability of more than 1/2, and the proposed redactable protocol can protect the transaction data effectively.


### 5.3. Chain Quality

This property points out that the proportion of adversary blocks in a blockchain is limited by the computing capabilities held by the adversaries.Definition 1.
The property ofμ,ℓ chain quality is parameterized byμ∈ℝ andℓ∈ℕ, which states that, for any part of the chain composed by ℓ continuous blocks held by the honest party, the proportion of adversarial blocks is at most μ, where μ is used to evaluate the computing capabilities of the adversaries.Theorem 3.
Γ′ satisfies μ,ℓ-chain quality if the public immutable blockchain satisfies μ,ℓ-chain quality for any t,n threshold ring signature where t/n>μ.Proof.
Proof. Different from the public immutable blockchain, we provide the function of transaction redaction in an anonymous environment. In order to increase the proportion of malicious blocks in the chain and break the chain quality property, adversaryA could redact an honest transaction txi of block Bj into a malicious transaction txi∗∗. We prove that the probability of replacing an honest transaction with a malicious one by the adversary A is negligible.
Suppose that adversaryA proposes an initial candidate transaction txi∗ to an honest transaction txi of block Bj. Limited by computing resources, the adversary A can only mine μ ratio of blocks during the phase of threshold ring signature generation. However, the proposed scheme requires that the ratio of redaction supporters to generate the threshold ring signature has to be at least t/n, where t/n>μ. The adversary A cannot be approved by t honest users and generate a valid t,n threshold ring signature TRS. Therefore, the adversary A needs to create an “honest looking” initial candidate transaction txi∗˜≠txi∗ such that Htxi∗˜=Htxi∗, where H is a collision-resistant hash function. Next, the adversary A deceives the honest users, and the honest users ensure the initial candidate transaction txi∗˜ by generating a threshold ring signature TRS. Then, the adversary A creates the final candidate transaction txi∗∗˜=txi∗˜‖TRS successfully and redacts the chain with the “honest looking” final candidate transaction txi∗∗˜. However, the chance of creating such a transaction txi∗˜ is negligible, since it violates the collision-resistance property of the hash function H. To sum up, the proof of Theorem 3 is established.


### 5.4. Common Prefix

The property of common prefix is parameterized byk∈ℕ, which states that if there are two honest users, and they hold two different chains C1 and C2 respectively, the number of the far right different blocks of these two chains is at most k. The game is also executed between an adversary A and a simulator ℬ.Definition 2.
For any two different chainsC1 and C2 held by two honest users U1 and U2 respectively, it holds that(3)C2k≼C1,C1k≼C2.
As shown in (3), C1k and C2k are denoted as the chain resulting from deleting the k far right blocks of chain C1 and C2.
However, Definition2 cannot be used directly in our new redactable protocol Γ′. Consider that if a redaction request ri,j and the corresponding final candidate transaction txi∗∗ were approved, an honest user U1 updates the chain C1 at time t1 and he replaces the old transaction txi with txi∗∗ in his local chain. However, another honest user U2 may not update the chain C at time t1 timely. In this case, C1k⊀C2 and C2k⊀C1, which violates Definition 3.
Therefore, a new definition was described as follows for the new privacy-preserving redactable protocolΓ′. Note that the redacted block is denoted as Bj∗.Definition 3.
For any two different chainsC1 and C2 held by two honest users U1 and U2 respectively, it holds that(1)
C1k≼C2 and C2≼C1(2)
For any redacted blockBj∗∈C1l2−l1+k and Bj∗∉C2k, or block Bj∗∈C2l2−l1+k and Bj∗∉C1k, it satisfiesΓ′.validateCandTxC,txi∗∗,j=1Theorem 4.
Γ′ satisfies the property of k-editable common prefix if the public immutable blockchain satisfies the property of k-common prefix.Proof.
Proof. Assume that the adversaryA proposes a final candidate transaction txi∗∗ to redact an honest block Bj in chain C2. The chain C2 is redacted by an honest user U1 later. However, the adversary A cannot create another final candidate transaction txi∗∗˜≠txi∗∗ such that Htxi∗∗˜˜=Htxi∗∗ because of the collision-resistance property of hash function H. Since the final candidate transaction txi∗∗ is accepted by the honest user U1, it must be the case that txi∗∗ contains a valid threshold ring signature TRS and is approved by most of the honest users in the system. To sum up, the proof of Theorem 4 is established.


## 5.1. Identity Privacy

The subsection states that the users’ identities are private in our protocol.Theorem 1.
The redactable blockchain scheme realizes the privacy of the users’ identities if the threshold ring signature is anonymous.Proof.
Proof. The game is executed between an adversaryA and a simulator ℬ. At the beginning of the game, ℬ is given a tuple Y,V0,V1,M,TRSM,Y,Vb, where b∈0,1, V0,V1 are both subsets of Y with same size, M is the redaction message including the redaction reasons and timestamp, and TRSM,Y,Vb is the threshold ring signature generated by Vb. Assuming that adversary A obtains the users’ identities with a nonnegligible probability in the proposed protocol, simulator ℬ can obtain the identities of the real signers with a nonnegligible probability in the threshold ring signature:Setup. The simulator sets up the blockchain system and sends the public parameters TRS⋅,E⋅,H⋅ to the adversary, where TRS⋅ is a threshold ring signature scheme, E⋅ is a symmetric encryption algorithm, and H⋅ is a secure hash function.Oracle Queries. The adversary simulates the following oracles:Transaction Generation Oracle. Adversary A sends an index j, some transactions collected from the blockchain system. The simulator ℬ returns a block txi:=EKmi,RSigi.Transaction Redaction Oracle. Adversary A sends a block index j, a transaction index i, an initial candidate transaction txi∗, an old transaction message m and an old transaction encryption key K, a redaction message M and two sets Y and V to the simulator, where Y is a public key set, V is a subset of Y and V≠V0orV1. The simulator returns the corresponding final candidate transaction txi∗∗=txi∗‖TRSM,Y,V.Challenge. The simulator ℬ generates the final candidate transaction txi∗^=txi∗^‖TRSM,Y,Vb, where M contains the disclosed transaction data m and encryption key K included in transaction txi∗^. Then, he transmits txi∗∗^ to the adversary A. A outputs b′∈0,1 and then ℬ submits b=b′. Assuming that A can guess the users’ identities successfully with a probability of more than 1/2, the simulator ℬ can distinguish the identities of the real signers with a probability of more than 1/2, and it contradicts the anonymity of the threshold ring signature. Therefore, it is impossible for the adversary A to guess the identities of the signers in a threshold ring signature successfully with a probability of more than 1/2, and the proposed redactable protocol can protect the users’ identities effectively.


## 5.2. Data Privacy

The subsection states that the transaction data in our blockchain system is private.Theorem 2.
The redactable blockchain scheme realizes the privacy of transaction data if the symmetric encryption algorithm is indistinguishable against chosen plaintext attack (IND-CPA) secure.Proof.
The game is executed between an adversaryA and a simulator ℬ. Assuming that adversary A can guess the transaction data with a nonnegligible probability in the proposed protocol, the simulator ℬ can distinguish the plaintext with a nonnegligible probability in the symmetric encryption scheme:Setup. The simulator sets up the blockchain system and generates a symmetric encryption algorithm E and an encryption key K and then sends the public parameters E to the adversary. The encryption key K is kept secret itself.Oracle Queries. The adversary simulates the following oracles:Encryption Oracle. The adversary sends the plaintext of transaction data m to the simulator. The simulator returns the corresponding ciphertext tx:=EKm,RSig, where EKm is the ciphertext of m by using the symmetric encryption algorithm, and RSig is the ring signature of the simulator on the ciphertext EKm.Challenge. Adversary A sends a tuple m0,m1,K0,K1,EKbmb to the simulator. Then, ℬ randomly chooses b∈0,1 and computes EKbmb. Note that EKbmb has never been queried in the Encryption oracles. Next, the simulator ℬ generates the ring signature RSig∗ on the ciphertext EKbmb and transmits the transaction ciphertext tx∗:=EKbmb,RSig∗ to adversary A.
A outputs b′∈0,1 and then ℬ submits b=b′. Assuming that A can guess the transaction data successfully with a probability of more than 1/2, the simulator ℬ can distinguish the ciphertext of two plaintexts with a probability of more than 1/2, and it contradicts the IND-CPA security of the symmetric encryption schemes. Therefore, it is impossible for the adversary A to guess the plaintext of transaction data successfully with a probability of more than 1/2, and the proposed redactable protocol can protect the transaction data effectively.


## 5.3. Chain Quality

This property points out that the proportion of adversary blocks in a blockchain is limited by the computing capabilities held by the adversaries.Definition 1.
The property ofμ,ℓ chain quality is parameterized byμ∈ℝ andℓ∈ℕ, which states that, for any part of the chain composed by ℓ continuous blocks held by the honest party, the proportion of adversarial blocks is at most μ, where μ is used to evaluate the computing capabilities of the adversaries.Theorem 3.
Γ′ satisfies μ,ℓ-chain quality if the public immutable blockchain satisfies μ,ℓ-chain quality for any t,n threshold ring signature where t/n>μ.Proof.
Proof. Different from the public immutable blockchain, we provide the function of transaction redaction in an anonymous environment. In order to increase the proportion of malicious blocks in the chain and break the chain quality property, adversaryA could redact an honest transaction txi of block Bj into a malicious transaction txi∗∗. We prove that the probability of replacing an honest transaction with a malicious one by the adversary A is negligible.
Suppose that adversaryA proposes an initial candidate transaction txi∗ to an honest transaction txi of block Bj. Limited by computing resources, the adversary A can only mine μ ratio of blocks during the phase of threshold ring signature generation. However, the proposed scheme requires that the ratio of redaction supporters to generate the threshold ring signature has to be at least t/n, where t/n>μ. The adversary A cannot be approved by t honest users and generate a valid t,n threshold ring signature TRS. Therefore, the adversary A needs to create an “honest looking” initial candidate transaction txi∗˜≠txi∗ such that Htxi∗˜=Htxi∗, where H is a collision-resistant hash function. Next, the adversary A deceives the honest users, and the honest users ensure the initial candidate transaction txi∗˜ by generating a threshold ring signature TRS. Then, the adversary A creates the final candidate transaction txi∗∗˜=txi∗˜‖TRS successfully and redacts the chain with the “honest looking” final candidate transaction txi∗∗˜. However, the chance of creating such a transaction txi∗˜ is negligible, since it violates the collision-resistance property of the hash function H. To sum up, the proof of Theorem 3 is established.


## 5.4. Common Prefix

The property of common prefix is parameterized byk∈ℕ, which states that if there are two honest users, and they hold two different chains C1 and C2 respectively, the number of the far right different blocks of these two chains is at most k. The game is also executed between an adversary A and a simulator ℬ.Definition 2.
For any two different chainsC1 and C2 held by two honest users U1 and U2 respectively, it holds that(3)C2k≼C1,C1k≼C2.
As shown in (3), C1k and C2k are denoted as the chain resulting from deleting the k far right blocks of chain C1 and C2.
However, Definition2 cannot be used directly in our new redactable protocol Γ′. Consider that if a redaction request ri,j and the corresponding final candidate transaction txi∗∗ were approved, an honest user U1 updates the chain C1 at time t1 and he replaces the old transaction txi with txi∗∗ in his local chain. However, another honest user U2 may not update the chain C at time t1 timely. In this case, C1k⊀C2 and C2k⊀C1, which violates Definition 3.
Therefore, a new definition was described as follows for the new privacy-preserving redactable protocolΓ′. Note that the redacted block is denoted as Bj∗.Definition 3.
For any two different chainsC1 and C2 held by two honest users U1 and U2 respectively, it holds that(1)
C1k≼C2 and C2≼C1(2)
For any redacted blockBj∗∈C1l2−l1+k and Bj∗∉C2k, or block Bj∗∈C2l2−l1+k and Bj∗∉C1k, it satisfiesΓ′.validateCandTxC,txi∗∗,j=1Theorem 4.
Γ′ satisfies the property of k-editable common prefix if the public immutable blockchain satisfies the property of k-common prefix.Proof.
Proof. Assume that the adversaryA proposes a final candidate transaction txi∗∗ to redact an honest block Bj in chain C2. The chain C2 is redacted by an honest user U1 later. However, the adversary A cannot create another final candidate transaction txi∗∗˜≠txi∗∗ such that Htxi∗∗˜˜=Htxi∗∗ because of the collision-resistance property of hash function H. Since the final candidate transaction txi∗∗ is accepted by the honest user U1, it must be the case that txi∗∗ contains a valid threshold ring signature TRS and is approved by most of the honest users in the system. To sum up, the proof of Theorem 4 is established.


## 6. Experiments

Several experiments are executed to test the efficiency of our work. We give the time of block redaction and block generation and compare the efficiency of the proposed protocol with that of the previous ones. We mainly focus on the time-consuming operations in these protocols, and the most expensive operations for generating and redacting a block are separately solving the PoW puzzle and generating a threshold ring signature.We conduct our experiments on a computer with a 64-bit Win 10 operating system, 8.0 GB RAM and Intel(R) Core(TM) i7-5500 CPU @ 2.4 GHz processor. We use the IntelliJ IDEA 2020 compiler and Java language to implement our programs. The JPBC 2.0.0 library is used to generate elliptic curve groups and pairings. The elliptic curve groups and pairings are used in the threshold ring signature scheme [22]. The AES algorithm is used to encrypt the transaction data.We test multiple times to get the average values as the final measurement results from each experiment. It should be noted that the number of the consecutive zero of the hash prefixes is defined as the difficulty level. For example, the difficulty level is 5 when the number of consecutive zeros of the hash prefixes is 5.


### 6.1. Time Consumption of Generating a Block and Redacting a Transaction

We first test the computational overhead for generating a block. As shown in Figure4, the overhead of generating a block is almost a constant, i.e., 2.894 s and 15.127 s, when the difficulty level is set as 4 and 6, respectively. The reason is that the overheads of generating a block depend on the difficulty of the POW puzzle instead of the percentage of the users participating in the redaction operation. We also test the overheads for redacting a transaction, which is much more important, and the time to redact a transaction actually determines the efficiency of our proposed scheme. As shown in Figure 5, the time consumption increases when the percentage of the users participating in a redaction operation grows, and the time consumption of redacting a transaction is not affected by the difficulty. The reason is that the time of redacting a transaction is mainly determined by the time of generating a t,n threshold ring signature, which depends on the value of threshold t.Figure 4
Time consumption of generating a block.Figure 5
Time consumption of redacting a transaction.In Table1, we give the time of redacting a transaction when the difficulty level is 5 and the percentage of the users participating in the redaction operation is 80%. The experimental results indicate that the average time of generating a block and redacting a transaction is separately 4580 ms and 7088 ms, and the time of redacting a transaction is about twice that of generating a block. Therefore, redacting data on a block is efficient in the proposed protocol.Table 1
The time consumption of block generation and redaction.
Time (ms)Block1Block2Block3Block4Block5AverageBlock generation487543504586410942174580Block redaction701668896875695968307088In order to describe the change of the block structure before and after the block is redacted more clearly, the block 23 is used as an example to illustrate what happens when a block is redacted. The original block information from block 22 to block 24 in the current blockchain is shown in Figure6. Suppose that the second transaction in block 23 needs to be redacted. In order to redact the transaction, the owner of transaction tx2 discloses the encrypted transaction data and the encryption key as the redacting reasons, and then a new transaction tx2∗ is generated to replace the old transaction tx2. Moreover, the POW puzzle of the new block 23∗ is solved. The users in the blockchain reached a consensus to redact the block and generate a threshold ring signature TRS to approve the redaction operation. The new redacted block information from block 22 to block 24 is shown in Figure 7.Figure 6
The original block information from block 22 to block 24.Figure 7
The new redacted block information from block 22 to block 24.


### 6.2. Efficiency Comparison

This experiment is intended to compare the efficiency of our proposed redactable protocol with that of [11, 19], where a privacy-preserving deletable blockchain and a public redactable blockchain are proposed.In the following experiments, we generate redactable and deletable chains. The length of these two chains and the number of block modifications are the same in each experiment. As shown in Figure8, the number of block redactions or deletions ranges from 10 to 40, and the overhead ratio is from 76% to 84%, and thus the average time of a redaction in the proposed protocol is about 80 percent of that in the deletable chains [19]. The reason is that our protocol needs to generate a ring signature only once, and the protocol in [19] needs to generate a traceable ring signature twice. Therefore, a transaction redaction is more efficient in the proposed protocol than that of deleting a block in [19].Figure 8
Block redaction overhead compared to deletable blockchain [19].To compare the efficiency of our work and that of [11], we both generate privacy-preserving redactable and public redactable chains. The length of these two chains and the number of block modifications are kept the same. As shown in Figure 9, the number of redactions ranges from 10 to 40, and the overhead ratio is from 30% to 41%, and thus the average time of redacting a transaction in the proposed protocol is about three times that in the public chains [11]. The reason is that our protocol uses more time-consuming operations, including the threshold ring signature and symmetric encryption in the redacting process to protect identities and data of the users. Therefore, the proposed protocol spends more time than the protocol in [11].Figure 9
Transaction redaction overhead compared to the public redactable blockchain [11].Next, we give a time comparison of redaction for these three protocols, and the results are shown in Table2. We can see that, in the protocol of [19], it takes an average of 8904 ms to delete a block. However, the protocol can only delete the whole block by the data owner, and it cannot redact a single transaction in the block. In our protocol, it takes an average of 7088 ms to redact a transaction, which is about 79.6% of the time for deleting a block in [19]. In the protocol of [11], it takes an average of 2552 ms to redact a transaction, which is about 36.0% of the time for redacting a transaction in the proposed redactable blockchain. However, the identities of the users and the transaction data are all public in the protocol of [11]. Thus, the proposed protocol can realize the redaction on the transaction-level, while the identities of the users and transaction data are also private.Table 2
The time comparison for block redaction.
Time (ms)Block 1Block 2Block 3Block 4Block 5AverageCai et al. [19]873990698630875493288904Deuber et al. [11]219428892970264520722552Our work701668896875695968307088Finally, we compare the proposed protocol with those in [11, 19], and the results are shown in Table 3. It is concluded that our protocol provides the function of transaction redaction, transaction deletion without disclosing the identities of the users and the transaction data. Although the protocol in [19] realizes the deletion of block data, the transaction redaction is not allowed. In the protocol of [11], transaction redaction is allowed, but the identities of the users and transaction data are public. The proposed protocol constructs a transaction-level redactable blockchain, and the users only need to replace a single transaction to complete the data redaction instead of replacing the entire block. However, the protocol [11, 19] can only achieve block-level redactable blockchain.Table 3
The comparison of three redactable blockchain protocols.
RedactionDeletionIdentity privacyData privacyTransaction levelBlock levelCai et al. [19]✕✔✔✔✕✔Deuber et al. [11]✔✔✕✕✕✔Our work✔✔✔✔✔✕


## 6.1. Time Consumption of Generating a Block and Redacting a Transaction

We first test the computational overhead for generating a block. As shown in Figure4, the overhead of generating a block is almost a constant, i.e., 2.894 s and 15.127 s, when the difficulty level is set as 4 and 6, respectively. The reason is that the overheads of generating a block depend on the difficulty of the POW puzzle instead of the percentage of the users participating in the redaction operation. We also test the overheads for redacting a transaction, which is much more important, and the time to redact a transaction actually determines the efficiency of our proposed scheme. As shown in Figure 5, the time consumption increases when the percentage of the users participating in a redaction operation grows, and the time consumption of redacting a transaction is not affected by the difficulty. The reason is that the time of redacting a transaction is mainly determined by the time of generating a t,n threshold ring signature, which depends on the value of threshold t.Figure 4
Time consumption of generating a block.Figure 5
Time consumption of redacting a transaction.In Table1, we give the time of redacting a transaction when the difficulty level is 5 and the percentage of the users participating in the redaction operation is 80%. The experimental results indicate that the average time of generating a block and redacting a transaction is separately 4580 ms and 7088 ms, and the time of redacting a transaction is about twice that of generating a block. Therefore, redacting data on a block is efficient in the proposed protocol.Table 1
The time consumption of block generation and redaction.
Time (ms)Block1Block2Block3Block4Block5AverageBlock generation487543504586410942174580Block redaction701668896875695968307088In order to describe the change of the block structure before and after the block is redacted more clearly, the block 23 is used as an example to illustrate what happens when a block is redacted. The original block information from block 22 to block 24 in the current blockchain is shown in Figure6. Suppose that the second transaction in block 23 needs to be redacted. In order to redact the transaction, the owner of transaction tx2 discloses the encrypted transaction data and the encryption key as the redacting reasons, and then a new transaction tx2∗ is generated to replace the old transaction tx2. Moreover, the POW puzzle of the new block 23∗ is solved. The users in the blockchain reached a consensus to redact the block and generate a threshold ring signature TRS to approve the redaction operation. The new redacted block information from block 22 to block 24 is shown in Figure 7.Figure 6
The original block information from block 22 to block 24.Figure 7
The new redacted block information from block 22 to block 24.


## 6.2. Efficiency Comparison

This experiment is intended to compare the efficiency of our proposed redactable protocol with that of [11, 19], where a privacy-preserving deletable blockchain and a public redactable blockchain are proposed.In the following experiments, we generate redactable and deletable chains. The length of these two chains and the number of block modifications are the same in each experiment. As shown in Figure8, the number of block redactions or deletions ranges from 10 to 40, and the overhead ratio is from 76% to 84%, and thus the average time of a redaction in the proposed protocol is about 80 percent of that in the deletable chains [19]. The reason is that our protocol needs to generate a ring signature only once, and the protocol in [19] needs to generate a traceable ring signature twice. Therefore, a transaction redaction is more efficient in the proposed protocol than that of deleting a block in [19].Figure 8
Block redaction overhead compared to deletable blockchain [19].To compare the efficiency of our work and that of [11], we both generate privacy-preserving redactable and public redactable chains. The length of these two chains and the number of block modifications are kept the same. As shown in Figure 9, the number of redactions ranges from 10 to 40, and the overhead ratio is from 30% to 41%, and thus the average time of redacting a transaction in the proposed protocol is about three times that in the public chains [11]. The reason is that our protocol uses more time-consuming operations, including the threshold ring signature and symmetric encryption in the redacting process to protect identities and data of the users. Therefore, the proposed protocol spends more time than the protocol in [11].Figure 9
Transaction redaction overhead compared to the public redactable blockchain [11].Next, we give a time comparison of redaction for these three protocols, and the results are shown in Table2. We can see that, in the protocol of [19], it takes an average of 8904 ms to delete a block. However, the protocol can only delete the whole block by the data owner, and it cannot redact a single transaction in the block. In our protocol, it takes an average of 7088 ms to redact a transaction, which is about 79.6% of the time for deleting a block in [19]. In the protocol of [11], it takes an average of 2552 ms to redact a transaction, which is about 36.0% of the time for redacting a transaction in the proposed redactable blockchain. However, the identities of the users and the transaction data are all public in the protocol of [11]. Thus, the proposed protocol can realize the redaction on the transaction-level, while the identities of the users and transaction data are also private.Table 2
The time comparison for block redaction.
Time (ms)Block 1Block 2Block 3Block 4Block 5AverageCai et al. [19]873990698630875493288904Deuber et al. [11]219428892970264520722552Our work701668896875695968307088Finally, we compare the proposed protocol with those in [11, 19], and the results are shown in Table 3. It is concluded that our protocol provides the function of transaction redaction, transaction deletion without disclosing the identities of the users and the transaction data. Although the protocol in [19] realizes the deletion of block data, the transaction redaction is not allowed. In the protocol of [11], transaction redaction is allowed, but the identities of the users and transaction data are public. The proposed protocol constructs a transaction-level redactable blockchain, and the users only need to replace a single transaction to complete the data redaction instead of replacing the entire block. However, the protocol [11, 19] can only achieve block-level redactable blockchain.Table 3
The comparison of three redactable blockchain protocols.
RedactionDeletionIdentity privacyData privacyTransaction levelBlock levelCai et al. [19]✕✔✔✔✕✔Deuber et al. [11]✔✔✕✕✕✔Our work✔✔✔✔✔✕


## 7. Conclusion

In this paper, we propose a privacy-preserving redactable blockchain based on the old state of the block. A symmetric encryption algorithm and a threshold ring signature are separately used to protect the transaction data and the users’ identities during the process of redaction. All of the users can check whether a redaction operation is valid or not according to the threshold ring signature and the old link of the redacted block. The experiments’ results indicate that the proposed protocol is efficient and effective, and the identities of the users and the transaction data are also private.



---

*Source: 4485311-2021-09-20.xml*