2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)

Redactable Blockchain using Enhanced Chameleon

Hash Function
1st Kondapally Ashritha 2nd Sindhu M 3rd Lakshmy KV
TIFAC-CORE in Cyber Security, TIFAC-CORE in Cyber Security, TIFAC-CORE in Cyber Security,
Amrita School of Engineering, Amrita School of Engineering, Amrita School of Engineering,
Coimbatore, Coimbatore, Coimbatore,
Amrita Vishwa Vidyapeetham, India Amrita Vishwa Vidyapeetham, India Amrita Vishwa Vidyapeetham, India
ashrithakondapally@gmail.com m sindhu@cb.amrita.edu kv lakshmy@cb.amrita.edu

Abstract—Immutability is a core principle of blockchain plat- the feature of redactablilty in distributed ledger platforms like
forms that help all participants to have an exact global log of blockchain, it is important to make sure that the possibility of
transactions. Immutability is easier to achieve in permissioned validators cheating the network is minimum.
blockchain platforms where a trusted group are the validators.
In public platforms, this vital property of blockchain can be Since blockchain is basically a trust less distributed system,
achieved only through decentralized economic mechanisms like 100% cheating immunity cannot be guaranteed. In these
Proof-of-Work(PoW). Blockchain along with the concept of asset systems, the probability of a user cheating is inversely pro-
tokenization provides liquidity to markets like stock trading and portional to the amount of investments he has made on the
exchange other intangible objects. With changes in regulatory particular blockchain platform. For example, in Bitcoin, the
policies and/or government laws, there could be a requisite to
alter the contents in such markets. We propose an idea of using probability of a miner who owns 20% mining power of the
Chameleon hash functions that will enable modification of a overall network will cheat is very minimal since he has a
block without changing other block contents. In our proposal, the considerable amount of economic interest on bitcoin whereas
trapdoor key used to redact a block is split among major valida- a normal user with almost zero mining power will not have
tors and is reconstructed using Multi-Party Computation(MPC). lots at stake even if bitcoin platform falls. Thus the power
Redaction happens when the major validators agree the suggested
changes by digitally signing the proposal. This eliminates the of redactability should only be given to those who owns a
need to rely on a trusted party. We also propose an idea of using substantial amount of mining power.
second trapdoor key that will be with the creator of the block. In blockchain 1.0, which is mainly designed for carrying
This can be used in scenarios where the block redaction should out financial transactions, the need for reversing a transaction
not happen without the consent of the creator. is not required. But with the concepts of asset tokenization
Index Terms—Chameleon hash function, Blockchain, Multi-
party Computation, Ephemeral key, Secret Sharing, Digital
where most of the tangible and intangible objects of the
Signatures real world are converted into crypto tokens and binded with
the blockchain platform, there could occur scenarios where
redaction is necessary. For example, consider a scenario where
I. I NTRODUCTION
a land asset is converted into a crypto token and published in
Blockchain technology brings together two important as- the blockchain, later if the land laws of respective country
pects that shape the new internet. The idea of decentralization changes, the blockchain platform will be obliged to change
along with de-duplication has found enormous applications the content related to that asset. Redactability of blockchain
ranging from basic financial transactions to complex smart can be achieved by generating blocks using a special type
contracts. Blockchain technology is built in such a way that of hash function called Chameleon Hash Function (CHF) [2].
once the data is published in the chain, it cannot be removed Chameleon hash functions will have corresponding trapdoor
or modified [1]. This key principle of immutability is very key using which one or many blocks can be redacted depend-
important in order to achieve data integrity in a trust less dis- ing upon the design.
tributed network. Even though 100% immutability can never In private or permissioned blockchain, the key can be in the
be theoretically promised in blockchain environment, strong hands of a Trusted Third Party (TTP) who can solely redact
economic practices like Proof-of-Work (PoW), Proof-of-Stake the blocks in the blockchain. This trusted third party can be
(PoS) gives a practical assurance that only one common determined based upon voting of validators who are fixed in
ledger is maintained. In permissioned blockchain platforms case of permissioned blockchain. For example, in Ripple, the
like Ripple where the validators are fixed, it is easy to achieve 18 validator nodes can vote among themselves and elect a node
immutability. It is always debatable to provide power to certain as the TTP. However, such kind of voting mechanism is not
people to modify the already existing contents of a blockchain possible in a public network where there are no fixed validators
as that would hinder the normal users to use the blockchain for voting and there exists a very minimal trust between the
where they have to trust unknown parties. Hence before adding users [3]. In such a scenario, we are proposing to split the

978-1-5386-9533-3/19/$31.00 ©2019 IEEE 323

 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)

trapdoor key into n shares and distribute among the major a single entity to a group of entities. It facilitates a secure way
miners. The probability that the miners will pool together and of storing and transmitting confidential information as shares
cheat on the network is very less because of the economic [4]. Specific conditions should be satisfied to reveal the secret
investments they are putting in. For example, in Bitcoin, the information. Each of n participants is provided with one share
trapdoor key can be split into 7 shares and distributed among each, and any group of t (threshold) or more participants can
the top 7 miners, ranked based upon the number of blocks combine their shares to generate the secret information.
published. For example, if a user wants to divide a secret S into two
The paper is organized in the following manner: Section parts, he can choose a random S1 as first secret and determine
II describes basic cryptographic notations and definitions that S2 by performing an XOR operation with S and S1 as inputs.
are used throughout this paper. Section III explains the existing Shamir’s threshold scheme is based on polynomial interpo-
model and flaws in it. Section IV describes the proposed archi- lation that allows any k out of n participants to recover the
tecture, security aspects of the new model. In Section V, we secret. The secret S is divided into n shares S1 , . . . , Sn in
look into different applications of the proposed architecture. such a way that:
The paper concludes in Section VI where future works and
1) It is easy to reconstruct the secret S with the knowledge
challenges are discussed.
of any k or more Si shares.
II. C RYPTOGRAPHIC T ERMINOLOGIES 2) The secret remains completely undetermined with the
knowledge of any k − 1 or fewer Si shares.
A. Chameleon Hash Function
This scheme is known as (k, n) threshold scheme. If k = n,
Chameleon hash functions are special type of cryptographic
then every share Si of the secret S is required to reconstruct
hash functions which can generate hash collisions efficiently
the secret.
with the knowledge of the trapdoor key.
Consider a message m and a randomly chosen parameter r.
Given a trapdoor key tk, the trapdoor holder can find the pairs
(m, r) and (m0 , r0 ) using chameleon hash function such that
CH(m, r) = CH(m0 , r0 ) where CH() represents chameleon
hash function. Note that the messages m and m0 should be
different i.e., m 6= m0 .
A standard chameleon hash function consists of efficient
algorithms such as Key Generation (HG), Hash Generation
(H), Hash Verification (HV ) and Hash Collision (HC) which
is specified as follows:
CH = (HG, H, HV, HC)
n
1) HG(1 ) = (hk, tk): It takes the security parameter
Fig. 1. (k, n) secret sharing scheme
n ∈ N as input, and gives public hash key hk and a
secret trapdoor key t as output.
Shamir’s secret sharing scheme is a type of Linear Secret
2) H(hk, m) = (h, z): It takes hash key hk, a message Sharing (LSS) scheme that is known to have lot of vulnera-
m ∈ M , and a random value r ∈ R as input, and bilities. Therefore, to improve the security we are proposing
produces a pair (h, z) that contains the hash value h to use a Non-Linear Secret Sharing (NLSS) scheme.
and a check string z.
C. Secure Multi-party Computation
3) D = HV (hk, m, (h, z)): It takes a message Multi-Party Computation (MPC) is a method in which the
m ∈ M , the hash value h, and a check string z as parties jointly compute a function over their private inputs
input, and outputs a bit D that equals 1 if (h, z) is a [5]. The inputs are obtained in the form of shares from secret
valid hash pair for the message m, otherwise D equals 0. sharing scheme.
Consider a Multi-party computation in which n users,
4) C = HC(t, (h, m, z), m0 ): It takes the trapdoor key
u1 , u2 , ..., un each have their input data, d1 , d2 , ..., dn respec-
t, a valid tuple (h, m, z), and a new message m0 ∈ M
tively. All the users compute the value of a public function f
as input, and outputs a new check string z 0 such that
on their input data: f (d1 , d2 , ..., dn ) while keeping their own
HV (hk, m, (h, z)) = HV (hk, m0 , (h, z 0 )) = 1 inputs secret.
For example, consider two parties Alice and Bob, with
B. Secret Sharing inputs A and B respectively. To find out the highest value
Secret Sharing is a group oriented cryptographic method of the two inputs, without revealing their individual values to
that allows shifting the knowledge of secret information from each other, consider the following two cases:

324
 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)

1) There exists a trusted party to whom the participants is computed by randomly trying out different values for
send their respective inputs and the trusted party calcu- Randomness parameter so that the modified content along
lates the maximum value amongst the two and reports with Randomness gives the same hash as it was before.
the same to both Alice and Bob.
2) When there is no trusted party, Alice and Bob performs
a two party computation (a generic model of Multi-party
computation), with each other and then result will only
reveal who has the highest value not the input figures of
individual parties.
D. Digital Signatures
A Digital Signature is a mathematical scheme that is used
for protecting the authenticity of digital documents. A signa-
ture is said to be valid if and only if it provides authentication,
non-repudiation as well as integrity. They are widely used
in financial transactions to detect forgeries. Digital signatures Fig. 2. Redactable Blockchain
usually use asymmetric cryptography which gives the receiver
Consider a blockchain platform that uses previous hash
a trust that the message was sent by the original sender and
value, PrevHash, the final merkle hash of proposed trans-
is not tampered.
actions, Transactions and a random value r. If a validator
A digital signature [6], [7] scheme typically consists of 3
proposes changes to a block with hash value s, he can modify
phases namely Key generation (G), Signing (S) and Signature
the previous hash value and/or the transaction contents that
Verification (V ).
will modify the Transactions value. The random value r will
1) Key Generation: A Security parameter r is randomly be modified such that the final hash value s will not change.
and 1r is given as input. Public key pk and its corre- This is important because the next blocks in the blockchain
sponding private key sk is obtained as output. are linked to blockchain with hash value s.
(pk, sk) ← G(1n ) For example, if a validator want to change the PrevHash s
and transactions Merkle root hash x and random value r of a
2) Signing: The private key sk, that is generated is used block to new PrevHash s0 and new transactions Merkle root
for signing a message m and produces a signature t. hash x0 , he has to determine a hash collision value r0 that
t ← S(sk, m) will make the final hash value unchanged using a chameleon
hash function CH(). (Refer Figure 3)
3) Signature Verification: The message m, public key
pk and signature t is given as input to the verification CH(s, x, r) = CH(s0 , x0 , r0 )
algorithm and it either accepts (D=0) or rejects (D=1)
the message.
D ← V (pk, x, t)
For correctness, S and V must satisfy
P r[(pk, sk) ← G(1n ), V (pk, x, S(sk, m)) = accepted] = 1
III. E XISTING S YSTEM
In the existing model of redactable blockchain [8], the
trapdoor key k is generated initially and is split into n shares
Fig. 3. Redactable Blockchain internal structure
by using Linear Secret Sharing scheme. The n shares are
distributed among the top n validators. To redact a block,
all the n validators need to perform a secure Multi-party A. Issues in Existing System
computation to regenerate the trapdoor key. By using the key 1) No Content Verification: During redaction, when a
k, the validator can redact one block or any number of blocks. chosen validator redacts a block, the contents inside the
During the block verification process, the validators compute block are not verified by other validators. They only
hash collision of the new and the previous content so that the calculate a hash collision value that will make sure that
hash does not change. (Refer Figure 2) the overall hash value of the block remains unaltered.
A block contains three pieces of information, the Thus, malicious validator can modify the contents as he
P revHash, T ransactions and a random parameter wishes.
Randomness. The P revHash and T ransactions values 2) Secret sharing: The model is based on linearly splitting
are determined by the miner and Randomness is used the secret shares and hence is vulnerable to many attacks
in order to add redactability feature. The hash collision like Tompa-Woll attack.

325
 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)

3) Single trapdoor key: Since only one trapdoor key is 1) ParGen: A security parameter λ is taken as input and
used, once a validator regenerates the trapdoor key [9], the public parameter ppch is obtained as output.
he can use it multiple times on multiple blocks.
ppch ← P arGen(1λ )
4) No consent of initial block publisher: Redaction is
done without the knowledge of the actual block pub- 2) KGen: The public parameter ppch is taken as input and
lisher. In platforms where block reward is provided, the private key pkch and public key skch are obtained
there exists some scenarios where the publisher should as output.
also be involved while redacting the block.
(skch , pkch ) ← KGen(ppch )
IV. P ROPOSED S YSTEM
.
In this section, we will be focusing upon the issues of the
3) Hash: It takes the public key pkch , and a message m
existing model discussed in section III-A and propose design
as input and produces a hash h, randomness r, and the
models that can reduce if not eliminate them.
ephemeral trapdoor key tk as output.
A. Content Verification
(h, r, tk) ← Hash(pkch , m)
If a validator wants to redact a block, he should first
compute the trapdoor key by collaborating with other share .
holders of the key. Before publishing a block, the validator has 4) HashChk: It takes as input the public key pkch , a
to first broadcast the changes among the key holders. The chain message m, a hash h, and randomness r. It outputs a
will be redacted only if all the validators agree the suggested decision bit d ∈ {true, f alse}, which indicates whether
changes by digitally signing the newly proposed block. In this the hash is correct or not.
way, one validator cannot solely modify contents of any block d ← HashChk(pkch , m, r, h)
without the agreement from other validators.
5) Adapt: It takes skch , the old message m, the old
B. Secret Sharing
randomness r, the new message m0 , the hash h, and
In Tompa-Woll attack, one of the validators can submit a the trapdoor information tk as input and outputs a new
false share such that only he can be able to obtain the correct randomness r0 for the message m0 .
secret. This is mainly due to the linearity property. To resist
from this attacks, we are proposing an idea of using Non- r0 : r0 ← Adapt(skch , m, m0 , r, h, tk)
Linear Secret Sharing [10], [11] instead of Shamir’s secret D. Consent from block publisher
sharing which is a type of Linear Secret Sharing scheme.
By keeping the ephemeral key with the initial block pro-
Cheatings [12] can be corrected in non-linear schemes by
poser, the validator will require permission from the parent
using decoding techniques like Read-Solomon codes.
block publisher to make changes to a particular block. (Refer
A Non-linear secret sharing scheme (k, n) for n parties such
Table I)
that
1) any k or more shares will regenerate the secret value. TABLE I
2) no information about the secret can be obtained with C OMPARISON OF E XISTING AND P ROPOSED MODELS
k − 1 or fewer shares.
Property Existing Model Proposed Model
An access structure is a function that is usually defined as
the collection of shares that can be used for reconstructing a Secret Sharing LSS NLSS
secret. Unlike Linear secret sharing, in Non-linear secret shar- Ephemeral Key No Yes
ing scheme, the access structure cannot be realized because a
Content Verification No Yes
non-linear function is used in a way that the structure of each
and every share is different and hence a malicious user cannot Multiple Block Redaction Yes No
regenerate the secret by submitting a false share. Initial Publisher Approval No Yes
C. Ephemeral Trapdoor Key
By using an ephemeral key that is specific to a particular
block, along with the trapdoor key we can restrict the modifi- E. Architecture
cations a validator can make. Now, in order to redact a block, In the proposed system, we are using an ephemeral trapdoor
the validator will require both the trapdoor key that has to key K that is specific to a particular block S. This key K will
be regenerated by performing secure Multi-party computation be with the initial proposer of the block S. The transactions
with other validators as well as the ephemeral key that can be x inside the block S is locked with the key K. By this
given to the initial proposer of the block. way, to modify the transaction x to x0 , the permission of the
A chameleon hash function with ephemeral initial block publisher is required. (Refer Figure 4). The main
trapdoor key [13] is a tuple of five algorithms trapdoor key is split using a Non-linear secret sharing scheme
(P arGen, KGen, Hash, HashChk, Adapt) and shared among the top n validators of the blockchain

326
 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)

relinquish the secret ephemeral key after a particular amount

of time.
With little modifications, this can also be extended to
regenerate the main trapdoor key where a holder of one share
is planning to leave the network.

V. A PPLICATIONS
Redactability is easier to achieve in private blockchain
because the validators are fixed whereas in a public blockchain
Fig. 4. Block Structure in Redactable Blockchain using Ephemeral trapdoor where anyone could mine a block. In this section, we will
key explain about the two different proposals based on the type of
blockchain in detail.
platform. To redact a block, all the validators will have to A. Permissioned Blockchain
perform a secure Multi-party computation to regenerate the
Consider a permissioned blockchain with n permanent
secret trapdoor key. Further, before publishing the modified
validators. Here, the trap- door key k will be split into n shares
block, all the share holders of the trapdoor key will have to
using non-linear secret sharing. In this case, we do not need an
agree to the changes by digitally signing the transaction. By
ephemeral key since any block will be published by the fixed
this way, we can make sure that while redacting a block all
validators who already have the share of the main trapdoor
the major validators and also the initial block publisher verify
key.
and agree with the modified content.
1) Deletion of a Block: There could be scenarios where a B. Public Blockchain
particular block S contain entire list of spam transactions. In
In a public blockchain like Bitcoin, anyone could join a
such cases, the validators could either delete the transactions x
network and publish a block, it is theoretically impossible to
of the block S and hence publish the block S with transactions
split the main trapdoor key and give shares to all the miners.
x0 = 0. This is similar to the architecture proposed in section
By specifically considering Bitcoin where a pool of seven
IV-E. This solution is not ideal because we are storing a block
miners publish most of the blocks, the trapdoor key can be
S with no content in it. (Refer Figure 5) By slightly modifying
divided into seven shares and distributed among them. But,
the architecture in section IV-E, we can delete the entire block
for a particular block, the publisher could be someone who is
from the blockchain. For example, if a validator wants to delete
not among the top seven miners. Thus, we need an ephemeral
a block S which has a succeeding block S2 and a preceding
trapdoor key to make sure that the initial proposer is also
block S1, he can achieve it by changing the PrevHash of block
involved in the redaction process.
S2 from s to s1.
In such cases, the PrevHash should also be locked with C. Other Applications of Chameleon Hash Functions
the ephemeral key. The ephemeral key K of the block to be 1) Sanitizable Signatures: There exist some environments
deleted is used to remove the link of the block S from the where the different users can access same data depending
blockchain. on their role. For example, consider a medical report in
which few portions of the data remain confidential and only
higher authorities can be able to access it. The authentication
and integrity is usually achieved by using digital signatures.
Sometimes there can be situations where an authorized third
party should modify the content in the document. But, if the
original signer of the document is not available or his/her key
is expired etc., then authorized third party should be able to
sign the document with a valid signature on behalf of original
signer without contacting him/her. This can be achieved by
using Sanitizable Signatures. The signer and the trusted party
Fig. 5. Block Deletion in Blockchain agree upon the mutable portions of the document before the
modification such that the trusted party can modify only those
2) Revoking the Ephemeral Key: In Public blockchain portions.
platforms where anyone can mine a block, the ephemeral Consider a case where a trusted party wants to modify a
key will be lost if the validator with relatively low mining document. The original signer of the document t will partition
power mines a block and then leaves the network. Now, it it into some n blocks. The signer selects some blocks out of
will be impossible to redact a block as the ephemeral key is n blocks and signs it by computing the chameleon hash using
not available. To eradicate such circumstances, we propose a the public key pk of third party. Now, as the private key sk
ephemeral key revocation scheme where the miner will have to is with the third party only he can be able to compute hash

327
 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)

collision and thus modify the selected portions of the block [8] Ateniese, Giuseppe, et al. ”Redactable blockchain-or-rewriting history
without changing the signature i.e., the signature is valid. in bitcoin and friends.” Security and Privacy (EuroS&P), 2017 IEEE
European Symposium on. IEEE, 2017.
2) Wireless Sensor Networks (WSN): Sensors are used in [9] Ateniese, Giuseppe, and Breno de Medeiros. ”On the key exposure
Wireless Sensor Network (WSN) to collect the information problem in chameleon hashes.” International Conference on Security in
about temperature, sound, etc., at different locations, process Communication Networks. Springer, Berlin, Heidelberg, 2004.
[10] Zhang, WeiGuo, Xi Sun, and JunPo Yang. ”On constructing 1-cheating
and send it back to the destination. Usually, a Multi- hop immune secret-sharing functions.” International Journal of Computer
network contains n number of nodes in which each and every Mathematics 89.1 (2012): 30-34.
node contains one or more sensors. Sensor nodes can transfer [11] dela Cruz, Romar, and Huaxiong Wang. ”Cheating-immune secret
sharing schemes from codes and cumulative arrays.” Cryptography and
the information to other sensor nodes via a base station. The Communications 5.1 (2013): 67-83.
information should not be altered during the transmission. If [12] Pieprzyk, Josef, and Xian-Mo Zhang. ”On cheating immune secret
two nodes say n1 and n2 wants to communicate with each sharing.” Discrete Mathematics and Theoretical Computer Science 6.2
(2004): 253-264.
other, they must authenticate themselves before data transfer. [13] Camenisch, Jan, et al. ”Chameleon-hashes with ephemeral trapdoors.”
Authentication can be achieved by using Chameleon hash IACR International Workshop on Public Key Cryptography. Springer,
function in which both the nodes n1 and n2 share a key k Berlin, Heidelberg, 2017.
[14] Nakamoto, Satoshi. ”Bitcoin: A peer-to-peer electronic cash system.”
through secure channel such that only the key holders can (2008).
compute the hash collisions. [15] Antonopoulos, Andreas M. Mastering Bitcoin: unlocking digital cryp-
3) Chameleon Signatures: In chameleon signature scheme, tocurrencies. ” O’Reilly Media, Inc.”, 2014.
the signer of a particular message m uses chameleon hash
function to compute the hash h. This hash can be signed by
using any signing algorithm. For example, if user A wants
to send a message to user B such that no other users should
be able to know information about the message, then user A
uses the chameleon hash function of user B, computes hash
h and signs it using any digital signature algorithm. When
user B receives the signature he can be able to verify that
the signature is valid by computing hash collision. In this
way, authentication is guaranteed and the signature is non-
transferable.

VI. C ONCLUSION
The proposed model guarantees content verification as well
as improves the security of secret sharing mechanism by
using a Non-linear methods of secret sharing. By introducing
a second trapdoor key, this model also make sure that the
redaction does not happen without consent of the initial
publisher of the block. The content in the block can be verified
using digital signatures Since, ephemeral key is created for
every block, key management will be an issue. By introducing
Keyless schemes, system can be further improved.

R EFERENCES
[1] Zyskind, Guy, and Oz Nathan. ”Decentralizing privacy: Using blockchain
to protect personal data.” Security and Privacy Workshops (SPW), 2015
IEEE. IEEE, 2015.
[2] Bellare, Mihir, and Todor Ristov. ”A characterization of chameleon hash
functions and new, efficient designs.” Journal of cryptology 27.4 (2014):
799-823.
[3] Ambili, K. N., M. Sindhu, and M. Sethumadhavan. ”On Federated and
Proof Of Validation Based Consensus Algorithms In Blockchain.” IOP
Conference Series: Materials Science and Engineering. Vol. 225. No. 1.
IOP Publishing, 2017.
[4] Feldman, Paul. ”A practical scheme for non-interactive verifiable secret
sharing.” Foundations of Computer Science, 1987., 28th Annual Sympo-
sium on. IEEE, 1987.
[5] Goldreich, Oded. ”Secure multi-party computation.” Manuscript. Prelim-
inary version 78 (1998).
[6] Rivest, Ronald L., Adi Shamir, and Leonard Adleman. ”A method for
obtaining digital signatures and public-key cryptosystems.” Communica-
tions of the ACM 21.2 (1978): 120-126.
[7] https://en.wikipedia.org/wiki/Digital signature

328