This article has been accepted for publication in IEEE Transactions on Computers.

This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 1

Redactable Blockchain From Decentralized

Chameleon Hash Functions, Revisited
Cong Li, Qingni Shen∗ , Zhonghai Wu∗

Abstract—Recently, redactable blockchains have attracted at- function. Subsequently, redactable blockchains can be divided
tention owing to enabling the contents of blocks to be re-written. into two types, the centralized one and the decentralized one.
The existing redactable blockchain solutions can be classified as In centralized solutions (e.g. [1]–[3]), a single blockchain node
two categories, the centralized one and decentralized one. In
centralized solutions, a single blockchain node possessing the possessing the trapdoor can perform the redaction operation.
trapdoor conducts redaction operations. However, they suffer But they suffer from the issue of single point of failure. By
from the issue of single point of failure. In decentralized solutions, contrast, in decentralized solutions (e.g. [4]–[6]), a certain
redaction operations are performed by numerous blockchain number of blockchain nodes cooperatively redact the blocks.
nodes cooperatively. But there also exists the issue of inefficiency However, they also have their own flaws. For the solution [4],
or requiring a trusted party in these solutions. Subsequently, Jia
et al. proposed a redactable blockchain solution from a decen- the voting process is time-consuming. For the solution [5],
tralized chameleon hash function (DCH) they designed, which it is inflexible due to merely supporting (n, n)-threshold, and
supports the threshold redaction, traceability and consistency insecure owing to suffering from an attack presented in the
check. Nevertheless, after carefully analyzing their solution, we literature [7]. And for the solution [6], requiring a trusted party
find that it fails to achieve the security they claimed by presenting in the trapdoor generation actually breaks the decentralized ar-
a concrete attack. To resolve this security issue, we propose
a novel chameleon hash function scheme that achieves strong chitecture of the system, and meanwhile it lacks the capability
collision-resistant security while maintaining simple and efficient of traceability. To cope with the above problems, Jia et al. [8]
as the building block. Based on it, we then present an improved firstly proposed a new decentralized chameleon hash function
DCH scheme with sufficient security, so that the redactable (DCH), in which the trapdoor is generated in a distributed
blockchain from it can resist the presented attack. Theoretical manner. Then they presented a redactable blockchain based
and experimental analyses demonstrate that improved DCH
achieves efficiency comparable to DCH. on DCH, achieving the threshold redaction, traceability and
consistency check. Nonetheless, we find that there exists a
Index Terms—Cryptanalysis, Redactable blockchain, Decen- severe security flaw in their redactable blockchain. In this
tralization, Chameleon hash function.
paper, to resolve the aforementioned security issue, we focus
on designing a novel DCH with sufficient security to build a
I. I NTRODUCTION secure redactable blockchain.

B lockchain is a promising technology allowing appli-

cations and services to be fully decentralized without
relying on any trusted third party. It has the feature of
A. Contribution
immutability, which means that once transactions are recorded The contributions of our work can be summarized as
on the blockchain after reaching the consensus, they can- follows.
not be tampered with. But in the meantime, this feature • We identify a security vulnerability in Jia et al.’s
also results in some issues, for instance, not supporting to redactable blockchain solution [8] and then present a
remove inappropriate content and being incompatible with concrete attack on it. The attack reveals that in their
legislations in numerous countries and organizations. To make solution, the malicious full node can redact blocks that
the blockchain redactable, Ateniese et al. [1] proposed the have not been redacted before without permissions from
notion of redactable blockchain based on the chameleon hash a sufficient number of other full nodes, provided that the
Cong Li is with the School of Computer Science, Peking University,
original block1 by redaction. at the same height has ever
Beijing 100871, China, also with the National Engineering Research Center been redacted.
for Software Engineering, Peking University, Beijing 100871, China, also with • We design a novel chameleon hash function that achieves
the Key Laboratory of High Confidence Software Technologies of Ministry
of Education (Peking University), Beijing 100871, and also with the PKU-
strong collision-resistant security while maintaining sim-
OCTA Laboratory for Blockchain and Privacy Computing, Peking University, ple and efficient as the building block. Then based on it,
Beijing 100871, China. E-mail: li.cong@pku.edu.cn. we propose an improved DCH with sufficient security,
Qingni Shen and Zhonghai Wu are with the School of Software and
Microelectronics, Peking University, Beijing 102600, China, also with the
so that the redactable blockchain from it can resist the
National Engineering Research Center for Software Engineering, Peking attack we present. Additionally, we also provide security
University, Beijing 100871, China, also with the Key Laboratory of High Con- analyses for our basic chameleon hash function and
fidence Software Technologies of Ministry of Education (Peking University),
Beijing 100871, and also with the PKU-OCTA Laboratory for Blockchain
improved DCH.
and Privacy Computing, Peking University, Beijing 100871, China. E-mail:
qingnishen@ss.pku.edu.cn, wuzh@pku.edu.cn. 1 The original block denotes the block created by generation, rather than
∗ Corresponding authors: Zhonghai Wu; Qingni Shen. generated

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 2

• We firstly give the detailed theoretical analysis of DCH can revoke the collision finding capability of the subordinate
[8] and improved DCH. We then implement them and private key. Furthermore, they also used the witness transaction
conduct a series of experiments. Both results demonstrate to record modifications and related status. Xu et al. [12]
that improved DCH has efficiency comparable to DCH, presented a redactable blockchain with k-time modification
and more compact randomness with reducing the size by and a monetary penalty. Concretely, it leverages a 1-degree
50% compared to DCH. polynomial with k instantiations to limit the number of redact-
ing operations, utilizes a digital signature to realize efficient
B. Organization privilege delegation, and signs the attribute set and public key
of the modifier to enable fine-grained redacting control.
In the remainder of this paper, Section II introduces main Derler et al. [13] brought forward a transaction-level
literatures about redactable blockchains. Then Section III redactable blockchain with fine-grained rewriting control
describes the background knowledge of this work, includ- mechanism. They introduced the notion of policy-based
ing notations, bilinear pairings and the core parts of Jia et chameleon hash function (PCH). In PCH, an expressive access
al.’s redactable blockchain solution [8]. Subsequently, Sec- policy is employed to substitute the public key in generating a
tion IV presents a concrete attack on their solution and chameleon hash value, and any trapdoor holder whose attribute
discusses the major reason causing the security flaw. Next, set satisfies the policy can find collisions. After that, redactable
Section V proposes an improved DCH scheme with a stronger blockchains based on accountable PCH [14], [15], revocable
collision-resistant security, which can be leveraged to build the PCH [16], [17], revocable and traceable PCH [18], PCH
redactable blockchain against the presented attack. Afterward, with online/offline and outsourced computation [19] were put
Section VI provides performance evaluations for improved forward successively.
DCH. Eventually, Section VII summarizes our work. Recently, Shen et al. [20] designed a redactable blockchain
that supports fully editing operations and blockchain state
II. R ELATED WORK verification. Li et al. [21] built a redactable blockchain offering
Redactable blockchain in the centralized setting. Ateniese et transaction consistency and public accountability by introduc-
al. [1] proposed the notion of redactable blockchain, which ing the notion of non-interactive chameleon hash function.
leverages chameleon hash functions to replace traditional Dai et al. [22] presented a practical redactable blockchain,
cryptographic hash functions used in the blockchain. They which solves the issues of auditable editing and trapdoor
defined the enhanced collision-resistance (E-CollRes) notion. management simultaneously, based on a smart contract voting
They also designed a generic construction of E-CollRes secure protocol, new block structure and chameleon hash function. In
chameleon hash function and gave two instantiations. Derler addition, several literatures [23]–[25] studied non-chameleon-
et al. [2] rigorously studied relations among the existing hash-based redactable blockchains.
collision-resistance notions and defined a stronger notion, Redactable blockchain in the decentralized setting. Ateniese
dubbed full collision-resistance (F-CollRes). They then pre- et al. [1] introduced a framework to build redactable block-
sented a generic construction of F-CollRes secure chameleon chains in the decentralized setting. In their solution, the
hash function and provided an instantiation. Besides, they chameleon hash function is extended to DCH, where the
built a redactable blockchain based on their chameleon hash trapdoor key is shared employing a t-out-of-n secret sharing
function. Astrizi et al. [9] put forward a redactable blockchain scheme during the key generation phase and is reconstructed
based on the preimage chameleon hash function they designed. if the number t′ of input shares exceeds the threshold value
Compared with chameleon hash functions in the literatures [1], t during the collision finding phase. However, the generic
[2], theirs relies on neither public-key encryption schemes nor construction with E-CollRes they brought forward cannot be
non-interactive zero-knowledge proofs, but employs a subset applied in the decentralized solution, since it requires to
of chameleon hash functions, where one can find first preim- decrypt the randomness from the ciphertext, which may lead
ages, not only second-preimages when holding the trapdoor. to the collision exposure issue when working in the distributed
Huang et al. [10] brought forward a redactable blockchain manner. Deuber et al. [4] proposed a redactable blockchain so-
with scalability, update and anonymity. To build their solution, lution in the permissionless setting by employing a consensus-
they designed two cryptographic schemes, namely the time based voting. It is fully decentralized and does not rely on
updatable chameleon hash function (TUCH) and linkable-and- any heavy cryptographic primitives. Nonetheless, owing to
redactable ring signature (LRRS). In TUCH, the randomness voting for redaction and traversing blocks to check whether
is merely valid in some specific time interval (e.g. an hour the consensus reaches or not, its performance decreases with
or a minute) and needs to be updated periodically. In LRRS, the number of transactions growth. Huang et al. [5] built a
signatures can be redacted to fresh messages by the designated redactable consortium blockchain for Internet-of-Things (IoT),
trapdoor holder and linked if they were signed by the same dubbed RCB, without a trusted authority. To realize their
user. Jia et al. [11] proposed a redactable blockchain achieving solution, they presented a DCH and an accountable-and-
self-management of personal data and supervision of improper sanitizable chameleon signature. Nevertheless, Gao et al. [7]
content. They designed a stateful chameleon hash function gave an attack on Huang et al.’s RCB [5] and pointed it
with revocable subkey (sCHRS) as the underlying building out to be insecure. Zhang et al. [6] put forward a reusable
block to prevent the redaction power from being abused by and redactable blockchain with a fixed size in space, dubbed
the malicious data owner. In sCHRS, the master private key Re-chain. They also proposed a DCH to offer the redactable

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 3

capability. However, it is not completely decentralized as it The bilinear pairing used in this paper is symmetric, i.e.
requires a trusted entity to participate in the trapdoor genera- e(u, v) = e(v, u), ∀ u, v ∈ G.
tion process. Jia et al. [8] presented a redactable blockchain
based on a DCH and a new structure they designed, which C. Review of Jia et al.’s redactable blockchain
stores the redaction history. It supports the threshold redacting
We briefly review the core parts of Jia et al.’s redactable
and proactive updating features. They also utilized an RSA
blockchain [8]. Concretely, they are DCH, the block genera-
accumulator to realize an efficient consistency check. Wu et
tion, block redaction and consistency check phases. For more
al. [26] brought forward a redactable consortium blockchain.
details, please refer to the literature [8].
To conform to characteristics of consortium blockchain, they
1) Decentralized chameleon hash function: Let G be a
firstly proposed a verifiable DCH (VDCH) to let multiple
GDH group of prime order p, g is a generator of G and
nodes determine the redaction operation cooperatively and
ID : {0, 1}∗ → Z∗p .
check the correctness of shares. They then designed a new
• KeyGen({1λ , 1t }ti=1 ) → {pk, ski }ti=1 . Take a security
consensus protocol based on verifiable threshold signatures
parameter and the number t of participants as inputs, the
to speed up the redaction process and prevent malicious
participant Pi (i ∈ [t]) executes as follows.
nodes from recovering and abusing the trapdoor of VDCH. Pt−1
Zhang et al. [27] proposed a transaction-level redactable – Pick a (t − 1)-degree polynomial fi (x) = j=0 ai,j xj ,
∗
blockchain supporting multiple authorities and enriching fine- where ai,0 , ..., ai,t−1 ∈ Zp are the random coefficients of
grained redaction control. They designed a multi-authority fi (x).
PCH (MAPCH) based on a multi-authority attribute-based – Send (fi (ID(Pj )), (g fi (ID(P1 )) , ..., g fi (ID(Pt )) ), g ai,0 ) to
encryption (MA-ABE) [28] and CHET [29]. Moreover, they Pj , where j ∈ [t]\{i}.
also provided a formal security proof of MAPCH. Ma et – When obtaining (fj (ID(Pi )), (g fj (ID(P1 )) , ..., g fj (ID(Pt )) ),
al. [30] further presented a new transaction-level redactable g aj,0 ) from Pj ,Qcheck whether (g, fj (ID(Pi )), g fj (ID(Pi )) )
t
blockchain that supports to be rewritten in a fine-grained is correct and k=1 g λk ·fj (ID(Pk )) = g aj,0 holds, where
Qt ID(Pj )
way and does not require the fully trusted central authority. λk = j=1,j̸=k ID(Pj )−ID(P k)
mod p.
Qt
They introduced the notion of decentralized PCH (DPCH) and – Compute the public key g s ← j=1 g aj,0 , where s =
Pt
put forward a DPCH instantiation using an MA-ABE [28], a j=1 aj,0 mod p, P and the trapdoor key (also dubbed the
CHET [29] and a digital signature [31]. Additionally, they also t
private key) si ← j=1 fj (ID(Pi )) mod p = f (ID(Pi )),
proved their DPCH secure and practical. Zhang et al. [32] Pt
where f (x) = j=1 fj (x). Return the key pair (g s , si ).
brought forward a redactable blockchain achieving dynamic
• Hash(pk, m) → (h, r). Take a public key g s and a
support and decentralized redaction. They proposed a dynamic
message m ∈ {0, 1}∗ as inputs, the algorithm calculates
and decentralized attribute-based chameleon hash function
u ← H(g s , m), where H : G × {0, 1}∗ → G is a cryptographic
(DACH) with delegation, which provides the capability of
hash function, and picks a random exponent e ∈ Z∗p . It returns
dynamic redaction committee changing for their solution.
the hash value h ← g e um and the randomness r = (g e , g se ).
DACH was constructed by leveraging a decentralized attribute-
• ReHash(pk, (m, r)) → h. Take a public key g s and an
based encryption [33] and CHET [29].
original message/randomness pair (m, r = (g e , g se )) as inputs.
It computes u ← H(g s , m) and returns the hash value h ←
III. P RELIMINARIES g e um .
A. Notation • Verify(pk, (m, r), (m′ , r′ )) → 0/1. Take a public key g s ,
For an algorithm A(·), we use y ← A(x) or A(x) → y an original message/randomness pair (m, r = (g e , g se )) and
′ ′
to denote a call of A on input x with y as output and write an another message/randomness pair (m′ , r′ = (g e , g se )) as
y = A(x; r) to emphasize that it is a deterministic algorithm inputs, and compute u ← H(g s , m). Finally, it returns 1 if
′ ′ ′ ′
with an internal randomness r as the auxiliary input. For a g e um = g e um and (g, g s , g e , g se ) is a Diffie-Hellman tuple
private algorithm A(κ, ·) with some secret information κ, such simultaneously; otherwise, it returns 0.
as the secret key, we use OκA (·) to denote the corresponding • Collision({ski , pk, (m, r), m′ }ti=1 ) → {r′ }ti=1 . Take
def
query oracle. For n ∈ N, we define [n] = {1, 2, ..., n}. For a trapdoor key si , a public key g s , an original mes-
def sage/randomness pair (m, r = (g e , g se )) and a fresh message
a, b ∈ N and a ≤ b, we define [a, b] = {a, a + 1, ..., b}. m′ ∈ {0, 1}∗ as inputs, the participant Pi (i ∈ [t]) executes as
follows.
′ ′
B. Bilinear pairings – Compute g e ← g e um−m , where u ← H(g s , m).
′
Let G, GT be two multiplicative cyclic groups of prime – Calculate ηi ← (g e )λi ·si , where λi =
Qt ID(Pj )
order p, g be a generator of G and e be a bilinear map such j=1,j̸=i ID(Pj )−ID(Pi ) mod p, and send η i to P j,
that e : G × G → GT with the following properties: where j ∈ [t]\{i}.
′
a b
• Bilinearity: ∀ u, v ∈ G and a, b ∈ Zp , e(u , v ) = – When Qt obtaining (η1 , ...ηi−1 , ηi+1 , ..., ηt ), ′ compute g se
′ ′
ab
e(u, v) . ← j=1 ηj and return a new randomness r = (g e , g se ).
• Non-degeneracy: e(g, g) ̸= 1. 2) Block generation: Any of blockchain nodes can generate
• Computable: ∀ u, v ∈ G, e(u, v) can be computed effi- a transaction and broadcast it to all full nodes. Assume the
ciently. height of current block on-chain is h − 1. Then a full node P

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 4

runs Algorithm 1 to create a new block, which includes the header0 and r0 are the header and randomness of the
valid transactions tx, as the original block at height h. original block of height h respectively, and {s1 , ..., st′ +1 }
are the trapdoor keys of above t′ + 1 full nodes.
Algorithm 1: Block Generation (4) P assembles a part of the redaction request req (i.e.
1 procedure GENREQ(B, tx, g s , g) addrtx , m root′ , last hash′ ), the corresponding hash
2 begin values hashtx′ of tx′ and the randomness r′ into data
3 header′ , r′ , acc′ ← GetHR(B) = (addrtx , hashtx′ , m root′ , last hash′ , r′ ), and then
4 prev hash ← packages data into a transaction txreq . Subsequently, it
DCH.ReHash(g s , (header′ − r′ , r′ )) broadcasts txreq in the network. The request data can
5 if DH(g, g s , r′ ) then be verified by running DCH.Verify(g s , (header − r, r),
6 for item in tx do ((prev hash, last hash′ , m root′ , acc), r′ )). If this al-
7 if RedactTx(item) then gorithm returns 1, it is valid; otherwise, it is invalid.
8 last hash′ ←GetSH(item) (5) Some full node packages txreq in a block. Next, all
9 acc′ ← ACC.Insert(acc′ , last hash′ ) blockchain nodes redact the original block header header
10 end to a new header header′ = (prev hash, last hash′ ,
11 end m root′ , acc, r′ ) successively, after txreq is recorded on
12 acc ← acc′ the blockchain.
13 m root ← MHT(tx) 4) Consistency check: The consistency check works as
R
14 e ← Z∗p follows.
15 r ← (g e , g se ) 1) The client submits a query (h, hashB ) to a blockchain
16 header ← Con(prev hash, ⊥, m root, acc, r) node, where hashB is the hash value of the block B’s
17 return (header, tx) header.
18 end 2) Subsequently, the blockchain node finds the block B
19 return ⊥ and the proof locally using this query. If B has been
20 end redacted, it gets the membership proof locally or by
running the GenMem algorithm of the RSA accumulator
3) Block redaction: The full nodes have the capability of ACC. Otherwise, it obtains the non-membership proof
redacting transactions in blocks that have not been redacted. locally or by running the GenNonMem algorithm of
Assume a full node P needs to redact the transactions tx in ACC. Finally, it sends B along with the proof to the
a block B of height h, it firstly checks whether B has been client.
redacted through the RSA accumulator acc. If so, the redaction 3) After obtaining the requested block and proof, the client
operation fails; otherwise, it continues to run the following carries out an integrity check on this block. If the block
protocol. passes this check, it continues to check the consistency of
(1) The full node P and the blockchain nodes generate the block by running the CheckMem or CheckNonMem
new transactions tx′ = (tx′1 , ..., tx′γ ) to replace the algorithm of ACC locally, or with the aid of a blockchain
transactions tx = (tx1 , ..., txγ ), whose addresses are node.
addrtx = (addrtx1 , ..., addrtxγ ). Then P checks the
signatures of txi and tx′i , for each i ∈ [γ].
(2) P generates a redaction request. The transactions tx with IV. C RYPTANALYSIS OF J IA ET AL .’ S REDACTABLE
addresses addrtx in B are substituted with tx′ , and the BLOCKCHAIN
new root m root′ of Merkle hash tree is created. Then
the hash value last hash′ of the redacted block header According to the threat model of literature [8], the adversary
header = (prev hash, last hash, m root, acc, r) is 1) cannot compute the randomness without the trapdoor key
computed. Eventually, a redaction request req = of DCH, and 2) cannot redact the block when the number of
(last hash′ , addrtx , tx′ , m root′ ) is generated and sent compromised full nodes does not exceed the threshold value.
to other full nodes by P . Nonetheless, in this section, we will show Jia et al.’s solution
(3) After receiving the redaction request req, full nodes [8] does not meet the above two security requirements.
{P1 , ..., Pn }\{P } find the block B via last hash′ . Sub-
sequently, they judge whether B has been redacted using
the same method as P does, and verify the signatures A. Cryptanalysis of DCH
of txi and tx′i , for each i ∈ [γ]. Suppose t′ of n
full nodes {P1 , ..., Pt′ } approve req, they then return For DCH in Section III-C1, once given a collision (m, r =
′ ′
their identities {ID(P1 ), ..., ID(Pt′ )} to P . If t′ ≥ t (t (g e , g se ), m′ , r′ = (g e , g se ), h), any user U can find more
is the threshold value), these full nodes {P, P1 , ..., Pt′ } collisions (for the message m) without employing the trapdoor
can run DCH.Collision({si , g s , ((header0 − r0 ), r0 key. We assume that a new message/randomness pair is
t′ +1 ′′ ′′
), (prev hash, last hash′ , m root′ , acc)}i=1 ) to gen- (m′′ , r′′ = (g e , g se )), and display how U calculates the
′ ′
erate a new randomness r′ = (g e , g se ). Note that, randomness r′′ below.

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 5

Fig. 1. An attack on Jia et al.’s redactable blockchain.

′ ′
Firstly, U has the equation that h = g e um = g e um , and 3) Once the number of full nodes that approve req0 (in-
then computes Eq. (1), (2), (3) as cluding Phonest itself) is more than the threshold value,
′ ′ these full nodes can run the Collision algorithm of
g se usm = g se usm , (1)
the underlying DCH to generate a new randomness r′
sm−sm′ se′ se
u =g /g , (2) cooperatively.
s
u = (g se′
/g )se 1
m−m′ . (3) 4) Phonest calculates the hash values hashtx′0 of tx′0 .
Then Phonest assembles a request data0 = (addrtx0 ,
s
After obtaining u , U further calculates Eq. (4), (5) as hashtx′0 , m root′ , last hash′ , r′ ) and packages it into a
′′ ′′
g e = g e um−m , (4) transaction txreq0 .
′′ ′′ ′ m−m′′
5) Some full node (e.g. the miner) verifies txreq0 and
g se = g se (us )m−m = g se (g se /g se ) m−m′ . (5) packages it in the block ②. Then after txreq0 is recorded
′′
By now the randomness r is generated. Subsequently, the on the blockchain, all blockchain nodes redact header0 to
′′ ′′
validity of the pair (m′′ , r′′ = (g e , g se )) can be checked a new block header header′ = (prev hash, last hash′ ,
′′ ′′
by running the Verify algorithm (i.e. g e um = g e um−m ·
′′ m root′ , acc, r′ ) and the block ③ (at height h) is gener-
′′ ′ ′ ′′ ′′
um = g e um = h = g e um and (g, g s , g e , g se ) is a Diffie- ated.
Hellman tuple). 2. Henceforth, there are two blocks at height h. Under this
Thus, in DCH, once some message/hash value pair has ever circumstance, a malicious full node P attempts to redact the
been found a collision, it can be found more collisions without transactions tx in the block ③ to the new transactions tx e
using the trapdoor key. without approvals from other full nodes. The specific steps
are:
B. A concrete attack 1) P substitutes the transactions tx with tx e = (txe 1 , ..., tx
e γ)
Based on the issue of DCH mentioned above, we give a according to its will, where the address of tx is addrtx =
concrete attack on Jia et al.’s redactable blockchain [8]. The (addrtx1 , ..., addrtxγ ).
detailed process of the attack is shown in Fig. 1. 2) P generates the new root m root′′ of Merkle hash tree.
1. In the original state, there is an original block at height Then it computes the hash value last hash′′ of the
h (i.e. the block ①), whose header is header0 = (prev hash, redacted block header header′ .
last hash, m root, acc, r0 ). Then some honest full node 3) P utilizes the vulnerability of the underlying DCH
′′ ′′
Phonest intends to redact the transactions tx0 in the block to calculate a fresh randomness r′′ = (g e , g se )
① to the new transactions tx′0 . The steps are: for (prev hash, last hash′′ , m root′′ , acc) by taking
1) Phonest replaces the transactions tx0 with tx′0 , where the header0 and r0 as inputs without the involvement of
address of tx0 is addrtx0 . other full nodes.
2) Phonest calculates the new root m root′ of Merkle hash 4) P calculates the hash values hashtx e of transactions
tree and the hash value last hash′ of the redacted block tx
e and packages the request data = (addrtx , hashtx e,
header header0 . Then Phonest generates a redaction m root′′ , last hash′′ , r′′ ) into a transaction txreq . Sub-
request req0 = (last hash′ , addrtx0 , tx′0 , m root′ ) and sequently, P broadcasts txreq in the blockchain net-
sends it to the other full nodes. work. Apparently, the request data can pass the va-

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 6

lidity check since DCH.Verify(g s , (header′ − r′ , r′ ), A. Proposed chameleon hash function construction
((prev hash, last hash′′ , m root′′ , acc), r′′ )) = 1. In this part, we give a concrete construction of our proposed
5) Some full node verifies txreq and packages it in chameleon hash function. The key differences between the-
the block ⑤. Then after txreq is recorded on the state-of-art chameleon hash function proposed by Chan et
blockchain, all blockchain nodes redact header′ to al. [36] and ours are outlined below. Firstly, their design
header′′ = (prev hash, last hash′′ , m root′′ , acc, r′′ ) idea is hashing without the public key of chameleon hash
and the block ⑤ is generated. function. From this idea, they designed the hash structure
3. For the consistency check, according to Algorithm 1 without using the public key and the randomness as a non-
in Section III-C2, when the full node packages a redaction interactive zero knowledge (NIZK) proof. Their scheme can
transaction in the block, it will add the hash value of redacted resist the key replacement attack they proposed and naturally
block header from the redaction transaction to the digest of achieve full indistinguishability. By contrast, our design idea is
all redacted blocks. So when txreq0 from Phonest is packaged reducing the collision-resistance of chameleon hash function
in the block ②, acc′ ← ACC.Insert(acc, last hash′ ) is run. to the EU-CMA security of signature. Based on this, we
Similarly, when txreq from the malicious full node P is pack- firstly leveraged the equation r′ = r · σ/σ ′ to establish a
aged in the block ④, acc′′ ← ACC.Insert(acc′ , last hash′′ ) link between our scheme and the underlying signature, and
is also executed. Apparently, this invalid redaction can pass instantiated it with the BLS signature. Then we designed the
the consistency check. hash and randomness structures to render the verification of
Consequently, the attack is launched on Jia et al.’s solu- validity of the hash/randomness pair (h, r) feasible. Secondly,
tion [8] successfully. Chan et al.’s scheme [36] achieves full security, namely full
collision-resistance and full indistinguishability. The strong
security is their major concern. By comparison, ours achieves
C. Revisiting the reason standard collision-resistance and indistinguishability, which
The reason of causing the security flaw of Jia et al.’s provides good efficiency and sufficient security for redactable
solution [8] is that the collision-resistant security of DCH blockchains. Balancing the performance and security is our
is not sufficient for the redactable blockchain application. design goal. Thirdly, Chan et al.’s chameleon hash func-
For simplicity, setting the number of parties in DCH to 1, tion construction [36] is a generic construction from a one-
it degrades into a chameleon hash function working in the way function and a simulation-sound extractable NIZK (SSE
centralized manner, which achieves the key exposure freeness NIZK) proof, which is general and has more application sce-
(KEF) [34], [35]. In this way, one can better observe the narios. The ECC-based construction is only an instantiation. In
underlying reason from the security model level. Specifically, contrast, ours is a direct construction without relying on SSE
KEF can guarantee that the adversary cannot find collisions NIZK (a relatively heavy cryptographic primitive), which is
for the label (i.e. u = H(g s , m) in DCH) that has never more practical and efficient.
been submitted to the collision oracle. Nevertheless, it cannot The construction is described as follows.
prevent the adversary from finding collisions for the label • PGen(1λ ) → pp: Output the public parameters pp =
that has ever been submitted. Unfortunately, to maintain the (D, H), where D = (G, GT , g, p, e) is the description of
same hash value, the blocks at the same height in Jia et pairing group and H : {0, 1}∗ → G is a collision-resistant
al.’s solution [8] need to share the same label, rather than hash function.
leverage new and different labels. Informally, an original block • KeyGen(pp) → (pk, sk). Output the public key/secret
at some height being redacted means that the corresponding key pair (pk, sk) = (y, x), where x ∈ Zp is a random exponent
label has been submitted to the collision oracle. As a result, and y = g x .
the adversary is potential to find more collisions for this label. • Hash(pk, m) → (h, r): Parse pk as y and m ∈ {0, 1}∗ ,
Hence, the (decentralized) chameleon hash function with KEF choose a random exponent ξ ∈ Zp , calculate h ← H(m)g ξ
(or the analogous security level) is not suitable for building and r ← y ξ . Return the hash value/randomness pair (h, r).
redactable blockchains, which fails to provide the sufficient • Verify(pk, m, r, h) → 0/1: Parse pk as y and m ∈
collision-resistance and may lead to security flaws. {0, 1}∗ . Return 1 if e(h/H(m), y) = e(g, r); otherwise, return
0.
• Collision(pk, sk, m, m′ , r, h) → r′ . Parse pk as y, sk as x
V. I MPROVED DCH and m, m′ ∈ {0, 1}∗ . Verify whether Verify(y, m, r, h) = 1. If
not, return ⊥; otherwise, calculate r′ ← r · (H(m)/H(m′ ))x .
Our construction of improved DCH proceeds in two steps. Return the fresh randomness r′ .
Firstly, we present a chameleon hash function construction
as the underlying building block, which provides a suffi-
cient security while maintaining simple and efficient. We B. Improved DCH construction
then propose an improved DCH construction based on the The construction of improved DCH is described below.
proposed chameleon hash function, which has a stronger • PGen(1λ ) → pp: Output the public parameters pp =
collision-resistant security compared with Jia et al.’s DCH [8]. (D, H), where D = (G, GT , g, p, e) is the description of
Moreover, we conduct correctness and security analyses for pairing group and H : {0, 1}∗ → G, ID : {0, 1}∗ → Z∗p are
improved DCH. collision-resistant hash functions.

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 7

• KeyGen(pp, {1t }ti=1 ) → {pk, ski }ti=1 . The participant • For the hash value/randomness pair (h, r′ ) generated by
Pi (i ∈ [t]) executes the following protocol, where t is the the Collision algorithm with the tuple (m, m′ , r, h) as
number of participants. input, we have
Pt−1
– Pick a (t − 1)-degree polynomial fi (x) = j=0 ai,j xj , e(h/H(m′ ), y) = e(H(m)g ξ /H(m′ ), g x )
where ai,0 , ..., ai,t−1 ∈ Z∗p are the random coefficients of
= e(g ξ · H(m)/H(m′ ), g x )
fi (x).
– Send (fi (ID(Pj )), (g fi (ID(P1 )) , ..., g fi (ID(Pt )) ), g ai,0 ) to = e((g x )ξ · (H(m)/H(m′ ))x , g)
Pj , where j ∈ [t]\{i}. = e(r · (H(m)/H(m′ ))x , g)
– When obtaining (fj (ID(Pi )), (g fj (ID(P1 )) , ..., g fj (ID(Pt )) ), = e(r′ , g)
g aj,0 ) from Pj ,Q check whether (g, fj (ID(Pi )), g fj (ID(Pi )) )
t = e(g, r′ ).
is correct and k=1 g λk ·fj (ID(Pk )) = g aj,0 holds, where
Qt ID(Pj )
λk = j=1,j̸=k ID(Pj )−ID(P k)
. Hence, the correctness of improved DCH is proven.
– Compute the public key y = g x ←
Qt aj,0 Collision-resistance. There are generally two approaches to
j=1 g ,
Pt calculate a collision, namely, through the existing collisions
where x = j=1 aj,0 , and the private key xi ←
Pt and a trapdoor. For the first approach, the collision-resistance
f (ID(P )) = f (ID(Pi )), where f (x) =
Ptj=1 j i
of improved DCH can be reduced to that of the underlying
j=1 fj (x). Output (pk, ski ) = (y, xi ). chameleon hash function. According to the definition of its
• Hash(pk, m) → (h, r): Parse pk as y and m ∈ {0, 1}∗ , collision-resistance (refer to Appendix A2), there does not
choose a random exponent ξ ∈ Zp , calculate h ← H(m)g ξ exist a PPT adversary A who can find a collision for a
and r ← y ξ . Return the hash value/randomness pair (h, r). fresh message m′ even if A is allowed to access to the
• Verify(pk, m, r, h) → 0/1: Parse pk as y and m ∈ collision oracle polynomial times. Therefore, improved DCH
{0, 1}∗ . Return 1 if e(h/H(m), y) = e(g, r); otherwise, return is secure enough to resist the attack presented in Section IV-B.
0. For the second approach, since employing the Share and
• Collision({pk, ski , m, m′ , r, h}ti=1 ) → {r′ }ti=1 . The par- Reconstruct algorithms of the secret sharing scheme in the
ticipant Pi (i ∈ [t]) parses pk as y, ski as xi and m, m′ ∈ trapdoor generation and collision finding phases respectively,
{0, 1}∗ . Then Pi executes the following protocol. there is no PPT adversary A who can reconstruct the trapdoor
key x or compute the term ((H(m)/H(m′ ))x , if A acquires at
– Calculate ηi ← (H(m)/H(m′ ))λi ·xi , where λi =
Qt ID(Pj ) most t − 1 shares. Hence, the malicious full node also cannot
j=1,j̸=i ID(Pj )−ID(Pi ) , send ηi to Pj , where j ∈ [t]\{i}. bypass the decentralization mechanism to redact any block.
Qt ηj from all Pj , where j ∈ [t]\{i}, calculate
– After getting In a nutshell, even though the original block at some height
r′ ← r · j=1 ηj and return the fresh randomness r′ . has been redacted, the malicious full node still cannot redact
Unlike Jia et al.’s DCH [8], the actual random exponent blocks at this height.
ξ employed in generating the hash value h is hidden behind Indistinguishability. The proof for the indistinguishability of
the randomness r in the improved DCH construction, such that improved DCH is analogous to that of the proposed chameleon
the hash value cannot be recalculated leveraging the public key hash function (refer to Appendix B3). The detailed proof is
pk and the original message-randomness pair (m, r) any more. therefore omitted here.
Hence, a small modification needs to be made to the redactable
blockchain structure (refer to Section III-A in the literature VI. P ERFORMANCE ANALYSIS
[8]), which is that the rand field needs to be extended to store In this section, we evaluate performance of DCH [8] and
the hash value of current block as well as the randomness. We improved DCH.
rename this extended field as curr_hash&rand.
A. Theoretical analysis
C. Correctness and security analyses In Table I, we give the theoretical analysis of Jia et al.’s
DCH [8] (shortened to DCH in the rest of the paper) and
In this section, we demonstrate improved DCH achieving improved DCH from the aspects of computation and storage
correctness, collision-resistance and indistinguishability. costs, respectively. For the computation cost aspect, we mainly
Correctness. The correctness analysis of improved DCH is consider the exponentiation operation in G (i.e. E), the hash
described below. calculation operation with G as the output space (i.e. HG ), the
• For the hash value/randomness pair (h, r) generated by pairing operation (i.e. P ) and the Diffie-Hellman tuple check
the Hash algorithm with the message m as input, we operation in GDH group (i.e. V), since they are time-intensive.
have In terms of the KeyGen and Collision algorithms, we count
the number of aforementioned operations one participant exe-
e(h/H(m), y) = e(H(m)g ξ /H(m), y) cutes. For the storage cost aspect, we take the element length
= e(g ξ , y) in G (i.e. |G|) and the element length in Zp (i.e. |Zp |) into
consideration.
= e(g, y ξ )
For the KeyGen algorithm, DCH and improved DCH
= e(g, r). basically have the same efficiency. For the Hash algorithm,

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 8

improved DCH is superior to DCH, which costs 1 less E. running Ubuntu (22.04.3 LTS) in WSL4 . Besides, we sample
For the Verify algorithm, provided that the GDH group is 1000 times and take the average execution time for each
implemented with pairing, V is equal to 2P . In this situation, experiment.
improved DCH is also prior to DCH with costing 2 less E.
For the Collision algorithm, due to the difference between the TABLE II
chameleon hash value’s structures, improved DCH costs ap- C OMPARISON BETWEEN DCH AND IMPROVED DCH ON EXECUTION TIME
OF VARIOUS ALGORITHMS BASED ON DIFFERENT TYPES OF PAIRINGS
proximately 1 more HG (in regard to computational overhead,
HG ≫ E) than DCH does. Pairing Scheme KeyGen Hash Verify Collision
In the meantime, for the sizes of a public key, a secret
key and a chameleon hash value, improved DCH costs the DCH [8] 19.48 3.52 3.4 2.66
Type A
same bit lengths with DCH. For the size of a randomness, Improved DCH 19.11 3.49 2.14 3.45
improved DCH requires |G| less bit lengths than DCH does, DCH [8] 41.28 10.47 11.93 9.19
Type E
since the randomness of improved DCH consists of merely one Improved DCH 41.18 10.35 9.22 14.32
term (i.e. y ξ ). In summary, although improved DCH enhances Type F
DCH [8] 37.19 0.64 14.14 0.44
the security in comparison with DCH, it still has efficiency Improved DCH 37.18 0.46 13.72 0.23
comparable to DCH. The unit of execution time for each algorithm is millisecond (ms).

TABLE I
Table II displays the execution time of all algorithms in
C OMPARISON BETWEEN DCH AND IMPROVED DCH ON THE DCH and improved DCH for one participant based on different
THEORETICAL COMPUTATION AND STORAGE COSTS types of pairings, where the total number of participants is set
to 5. For the KeyGen algorithm, improved DCH nearly has
Algo./Compo. DCH [8] Improved DCH the same execution time as DCH, regardless of the underlying
KeyGen (t2 + t)E (t2 + t)E pairing varying. It has the best performance on the Type A
Hash 3E + HG 2E + HG pairings, spending about 19.1 ms, and the worst performance
Verify 2E + V + HG 2P + HG on the Type E pairings, costing approximately 41.2 ms. For
Collision 2E + HG E + 2HG the Hash algorithm, improved DCH merely has a very slight
advantage over DCH on the Type A and Type E pairings. But
|pk| |G| |G| on the Type F pairings, the advantage is obvious, with reducing
|sk| |Zp | |Zp | execution time by 28.13%. For the Verify algorithm, improved
|h| |G| |G| DCH achieves better performance than DCH in all types of
|r| 2|G| |G| pairings, where the gaps are 1.26 ms, 2.71 ms and 0.42 ms
Algo./Compo.: algorithm or component, t: the number of involved par- on the Type A, Type E and Type F pairings, respectively. In
ticipants, E: the exponentiation operation in G, HG : the hash calculation contrast, for the Collision algorithm, DCH is more efficient
operation with G as the output space, V: the Diffie-Hellman tuple check
operation in the GDH group, P : the pairing operation, |pk|: the size of than improved DCH on the Type A and Type E pairings,
a public key pk, |sk|: the size of a secret key sk, |h|: the size of a costing 0.79 ms and 5.13 ms less respectively. Nonetheless,
chameleon hash value h, |r|: the size of a randomness r, |G|: the element on the Type F pairings, improved DCH spends 0.21 ms less.
length in G, |Zp |: the element length in Zp .
The reason is that in this type of pairings, HG is relatively
efficient, thus not dominating the execution time of algorithm.
Considering that both of the KeyGen and Collision algo-
B. Experimental analysis rithms are affected by the number t of participants, we further
evaluate the relationship between the execution time and t
We implement DCH [8] and improved DCH in Pairing through several experiments, where the results are shown in
Based Cryptography Library (PBC) (version 0.5.14) [37] and Fig. 2. Fig 2a and Fig 2c display the changing of KeyGen’s
and C++ 17. We employ the default Type A, Type E and execution time in DCH and improved DCH along with t
Type F pairings from PBC, where the Type A pairings are varying from 5 to 45 with 4 as the step size, respectively.
constructed on the elliptic curve y 2 = x3 + x over the field Apparently, regardless in Fig. 2a or Fig. 2c, the execution
Fq (|q| = 512 bits and the bit length of order r is 160 time increases quadratically with the growth of t, reaching
bits), the Type E pairings2 are constructed on elliptic curve around 1280ms, 2770ms, 1420ms on the Type A, Type E and
y 2 = x3 + ax + b over the field Fq (|q| = 1024 bits and the Type F pairings when t = 45. Fig. 2b and Fig. 2d show the
bit length of prime r is 160 bits), and the Type F pairings changing of Collision’s execution time in DCH and improved
are constructed on the elliptic curve y 2 = x3 + b over the DCH along with t increasing from 5 to 45 with 4 as the step
field Fq (the bit length of order r is 160 bits). Subsequently, size, respectively. By contrast, the execution time in Fig. 2b
numerous experiments are carried out on a desktop PC with and Fig. 2d is insensitive to the growth of l. Specifically, in Fig.
Intel Core(TM) i5-13600KF (3.5GHz * 14) and 4GB RAM3 2b, the gaps between the maximum and minimum execution
time are only 0.15 ms, 0.45 ms and 0.08 ms on the Type A,
2 This type of pairings is constructed using the complex multiplication
method. 4 WSL is the abbreviation of Windows Subsystem for Linux, which allows a
3 Note that, the total memory size of PC is 32GB, but the memory size Linux environment to run on the Windows machine directly without a separate
allocated by WSL for running Linux is 4GB. virtual machine.

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 9

[2] D. Derler, K. Samelin, and D. Slamanig, “Bringing order to chaos: The

case of collision-resistant chameleon-hashes,” in Proceedings of the 23rd
IACR International Conference on Practice and Theory of Public-Key
Cryptography (PKC 2020). Edinburgh, UK: Springer, May 4-7 2020,
pp. 462–492.
[3] Y. Li and S. Liu, “Tagged chameleon hash from lattices and application
to redactable blockchain,” Cryptology ePrint Archive, Paper 2023/774,
2023.
[4] D. Deuber, B. Magri, and S. A. K. Thyagarajan, “Redactable blockchain
in the permissionless setting,” in Proceedings of 2019 IEEE Symposium
on Security and Privacy (SP 2019). San Francisco, CA, USA: IEEE,
May 19-23 2019, pp. 124–138.
(a) KeyGen of DCH (b) Collision of DCH [5] K. Huang, X. Zhang, Y. Mu, X. Wang, G. Yang, X. Du, F. Rezaeibagha,
Q. Xia, and M. Guizani, “Building redactable consortium blockchain
for industrial internet-of-things,” IEEE Trans. Ind. Informatics, vol. 15,
no. 6, pp. 3670–3679, 2019.
[6] J. Zhang, Y. Lu, Y. Liu, X. Yang, Y. Qi, X. Dong, and H. Wang, “Serving
at the edge: A redactable blockchain with fixed storage,” in Proceedings
of the 17th International Conference on Web Information Systems and
Applications (WISA 2020). Guangzhou, China: Springer, September
23-25 2020, pp. 654–667.
[7] W. Gao, L. Chen, C. Rong, K. Liang, X. Zheng, and J. Yu, “Security
analysis and improvement of a redactable consortium blockchain for
industrial internet-of-things,” Comput. J., vol. 65, no. 9, pp. 2430–2438,
2022.
[8] M. Jia, J. Chen, K. He, R. Du, L. Zheng, M. Lai, D. Wang, and F. Liu,
(c) KeyGen of improved DCH (d) Collision of improved DCH “Redactable blockchain from decentralized chameleon hash functions,”
Fig. 2. Execution time analysis on the KeyGen and Collision algorithms of IEEE Trans. Inf. Forensics Secur., vol. 17, pp. 2771–2783, 2022.
DCH and improved DCH under different numbers of participants based on [9] T. L. Astrizi and R. Custódio, “Redacting blockchain without exposing
different types of pairings. chameleon hash collisions,” in Proceedings of the 21st International
Conference on Cryptology and Network Security (CANS 2022). Dubai,
United Arab Emirates: Springer, November 13-16 2022, pp. 339–358.
[10] K. Huang, X. Zhang, Y. Mu, F. Rezaeibagha, and X. Du, “Scalable and
Type E and Type F pairings. And in Fig. 2d, the gaps in the redactable blockchain with update and anonymity,” Inf. Sci., vol. 546,
same condition are merely 0.18 ms, 0.6 ms and 0.08 ms on pp. 25–41, 2021.
the corresponding pairings. [11] Y. Jia, S. Sun, Y. Zhang, Z. Liu, and D. Gu, “Redactable blockchain
supporting supervision and self-management,” in Proceedings of 2021
In a nutshell, the result of the above experimental analysis ACM Asia Conference on Computer and Communications Security
on DCH and improved DCH is basically consistent with that (AsiaCCS 2021). Virtual Event, Hong Kong: ACM, June 7-11 2021,
of theoretical analysis in Section VI-A, demonstrating that pp. 844–858.
[12] S. Xu, J. Ning, J. Ma, X. Huang, and R. H. Deng, “K-time modifiable
improved DCH is comparably efficient as DCH. and epoch-based redactable blockchain,” IEEE Trans. Inf. Forensics
Secur., vol. 16, pp. 4507–4520, 2021.
VII. C ONCLUSION [13] D. Derler, K. Samelin, D. Slamanig, and C. Striecks, “Fine-grained and
controlled rewriting in blockchains: Chameleon-hashing gone attribute-
In this work, we identified a security flaw in Jia et al.’s based,” in Proceedings of the 26th Annual Network and Distributed
redactable blockchain solution [8] and brought forward a System Security Symposium (NDSS 2019). San Diego, California, USA:
The Internet Society, February 24-27 2019.
concrete attack on it. To build a secure redactable blockchain, [14] Y. Tian, N. Li, Y. Li, P. Szalachowski, and J. Zhou, “Policy-based
we firstly presented a novel chameleon hash function scheme chameleon hash for blockchain rewriting with black-box accountabil-
with balancing the security and performance as the underlying ity,” in Proceedings of 2020 Annual Computer Security Applications
Conference (ACSAC 2020). Virtual Event/Austin, TX, USA: ACM,
building block. Then based on the basic scheme, we proposed December 7-11 2020, pp. 813–828.
an improved DCH scheme that achieves a stronger security [15] S. Xu, X. Huang, J. Yuan, Y. Li, and R. H. Deng, “Accountable and
than Jia et al.’s DCH does [8], where the redactable blockchain fine-grained controllable rewriting in blockchains,” IEEE Trans. Inf.
Forensics Secur., vol. 18, pp. 101–116, 2023.
from it can resist the attack we brought forward. Subsequently,
[16] S. Xu, J. Ning, J. Ma, G. Xu, J. Yuan, and R. H. Deng, “Revocable
we provided security analyses for both of our schemes. Finally, policy-based chameleon hash,” in Proceedings of the 26th European
we conducted the theoretical analysis and experimental eval- Symposium on Research in Computer Security (ESORICS 2021). Darm-
uation for DCH [8] and improved DCH. Both results reveal stadt, Germany: Springer, October 4-8 2021, pp. 327–347.
[17] Y. Tian, A. Miyaji, K. Matsubara, H. Cui, and N. Li, “Revocable policy-
that improved DCH offers efficiency comparable to DCH [8]. based chameleon hash for blockchain rewriting,” Comput. J., vol. 66,
no. 10, pp. 2365–2378, 2023.
ACKNOWLEDGMENT [18] G. Panwar, R. Vishwanathan, and S. Misra, “Retrace: Revocable and
traceable blockchain rewrites using attribute-based cryptosystems,” in
We appreciate the anonymous reviewers for their construc- Proceedings of the 26th ACM Symposium on Access Control Models
tive suggestions. This work was supported by the National Key and Technologies (SACMAT 2021). Virtual Event, Spain: ACM, June
16-18 2021, pp. 103–114.
R&D Program of China (Grant No. 2022YFB2703301). [19] L. Guo, Q. Wang, and W.-C. Yau, “Online/offline rewritable blockchain
with auditable outsourced computation,” IEEE Trans. Cloud Comput.,
vol. 11, no. 1, pp. 499–514, 2023.
R EFERENCES
[20] J. Shen, X. Chen, Z. Liu, and W. Susilo, “Verifiable and redactable
[1] G. Ateniese, B. Magri, D. Venturi, and E. R. Andrade, “Redactable blockchains with fully editing operations,” IEEE Trans. Inf. Forensics
blockchain - or - rewriting history in bitcoin and friends,” in Proceedings Secur., vol. 18, pp. 3787–3802, 2023.
of 2017 IEEE European Symposium on Security and Privacy (EuroS&P [21] J. Li, H. Ma, J. Wang, Z. Song, W. Xu, and R. Zhang, “Wolver-
2017). Paris, France: IEEE, April 26-28 2017, pp. 111–126. ine: A scalable and transaction-consistent redactable permissionless

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
 This article has been accepted for publication in IEEE Transactions on Computers. This is the author's version which has not been fully edited and
content may change prior to final publication. Citation information: DOI 10.1109/TC.2025.3544878

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 10

blockchain,” IEEE Trans. Inf. Forensics Secur., vol. 18, pp. 1653–1666, Cong Li received his Ph.D. degree from Peking
2023. University, Beijing, China, in 2022. He is currently
[22] W. Dai, J. Liu, Y. Zhou, K. R. Choo, X. Xie, D. Zou, and H. Jin, a postdoctoral fellow at School of Computer Sci-
“PRBFPT: A practical redactable blockchain framework with a public ence, Peking University, Beijing, China. His research
trapdoor,” IEEE Trans. Inf. Forensics Secur., vol. 19, pp. 2425–2437, interests include applied cryptography, blockchain,
2024. cloud security and privacy-preserving computing.
[23] M. Florian, S. A. Henningsen, S. Beaucamp, and B. Scheuermann,
“Erasing data from blockchain nodes,” in Proceedings of 2019 IEEE
European Symposium on Security and Privacy Workshops (EuroS&P
Workshops 2019). Stockholm, Sweden: IEEE, June 17-19 2019, pp.
367–376.
[24] C. K. Pyoung and S. J. Baek, “Blockchain of finite-lifetime blocks with
applications to edge-based IoT,” IEEE Internet Things J., vol. 7, no. 3,
pp. 2102–2116, 2020.
[25] R. Matzutt, B. Kalde, J. Pennekamp, A. Drichel, M. Henze, and
K. Wehrle, “How to securely prune bitcoin’s blockchain,” in Proceedings
of 2020 IFIP Networking Conference (Networking 2020). Paris, France:
IEEE, June 22-26 2020, pp. 298–306.
[26] X. Wu, X. Du, Q. Yang, N. Wang, and W. Wang, “Redactable consortium
blockchain based on verifiable distributed chameleon hash functions,” J.
Parallel Distributed Comput., vol. 183, p. 104777, 2024.
[27] Z. Zhang, T. Li, Z. Wang, and J. Liu, “Redactable transactions in
consortium blockchain: Controlled by multi-authority CP-ABE,” in Pro-
ceedings of the 26th Australasian Conference on Information Security
and Privacy (ACISP 2021). Virtual Event: Springer, December 1-3
2021, pp. 408–429. Qingni Shen received the Ph.D. degree from In-
[28] Y. Rouselakis and B. Waters, “Efficient statically-secure large-universe stitute of Software Chinese Academy of Sciences,
multi-authority attribute-based encryption,” in Proceedings of the 19th Beijing, China, in 2006. She is currently a professor
International Conference on Financial Cryptography and Data Security of School of Software and Microelectronics, Peking
(FC 2015). San Juan, Puerto Rico: Springer, January 26-30 2015, pp. University, Beijing, China. Her research interests
315–332. include operating system and virtualization security,
[29] J. Camenisch, D. Derler, S. Krenn, H. C. Pöhls, K. Samelin, and privacy preserving in cloud and big data, trusted
D. Slamanig, “Chameleon-hashes with ephemeral trapdoors - and ap- computing. She is a senior member of IEEE, ACM
plications to invisible sanitizable signatures,” in Proceedings of the 20th and CCF member. She is now serving for many
IACR International Conference on Practice and Theory in Public-Key international conferences, including TrustCom, Se-
Cryptography (PKC 2017). Amsterdam, The Netherlands: Springer, cureComm and ever as the chair of publicity com-
March 28-31 2017, pp. 152–182. mittee or the member of program committee of ICICS in 2017, 2015, 2013,
[30] J. Ma, S. Xu, J. Ning, X. Huang, and R. H. Deng, “Redactable 2011, 2009 and 2007.
blockchain in decentralized setting,” IEEE Trans. Inf. Forensics Secur.,
vol. 17, pp. 1227–1242, 2022.
[31] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil
pairing,” J. Cryptol., vol. 17, no. 4, pp. 297–319, 2004.
[32] D. Zhang, J. Le, X. Lei, T. Xiang, and X. Liao, “Secure redactable
blockchain with dynamic support,” IEEE Trans. Dependable Secur.
Comput., vol. 21, no. 2, pp. 717–731, 2024.
[33] A. B. Lewko and B. Waters, “Decentralizing attribute-based encryption,”
in Proceedings of the 30th Annual International Conference on the
Theory and Applications of Cryptographic Techniques (EUROCRYPT
2011). Tallinn, Estonia: Springer, May 15-19 2011, pp. 568–588.
[34] X. Chen, F. Zhang, and K. Kim, “Chameleon hashing without key expo-
sure,” in Proceedings of the 7th International Conference on Information
Security (ISC 2004). Palo Alto, CA, USA: Springer, September 27-29
2004, pp. 87–98. Zhonghai Wu received the Ph.D. degree from Zhe-
[35] X. Chen, F. Zhang, H. Tian, B. Wei, and K. Kim, “Discrete logarithm jiang University, Hangzhou, China, in 1997. Previ-
based chameleon hashing and signatures without key exposure,” Comput. ously he worked as a postdoctor and senior research
Electr. Eng., vol. 37, no. 4, pp. 614–623, 2011. fellow in Institute of Computer Science and Technol-
[36] K. Y. Chan, L. Chen, Y. Tian, and T. H. Yuen, “Reconstructing ogy, Peking University, Beijing, China. Since then he
chameleon hash: Full security and the multi-party setting,” in Proceed- has been involved both in research and application
ings of the 19th ACM Asia Conference on Computer and Communica- development of distributed system and multimedia
tions Security (ASIA CCS 2024). Singapore: ACM, July 1-5 2024, pp. applications. He is currently the executive president
1076–1091. of School of Software and Microelectronics, Peking
[37] B. Lynn. The pairing-based crytography library. [Online]. Available: University, Beijing, China. His research interests
http://crypto.stanford.edu/pbc/. include context-aware services, embedded software
and system, cloud services and security, and open innovation.

Authorized licensed use limited to: The Ohio State University. Downloaded on February 25,2025 at 02:21:11 UTC from IEEE Xplore. Restrictions apply.
© 2025 IEEE. All rights reserved, including rights for text and data mining and training of artificial intelligence and similar technologies. Personal use is permitted,
but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.