between input and output addresses from the mixer. However, Blindcoin loses mix indistinguishability, adds additional cost and delay, and does not eliminate the theft issue.
Decentralized Mixing Protocols. These are based on a
collaboration of untrusted Bitcoin users permuting their
ownership of their coins without any trusted third party.
CoinJoin (Maxwell 2013) relies on participants agreeing on
transaction inputs and outputs to create a group transaction.
CoinShuffle (Ruffing et al. 2014) improves CoinJoin’s
cryptograph layer to solve the internal unlinkability issue.
Altcoin Protocols. This category proposes solutions
based on advanced cryptography to provide strong anonymity, but it must substantially modify Bitcoin. Also, it
requires more storage and computational power per transaction than Bitcoin, which created new cryptocurrencies
such as Monero (2014).
3.2 Bitcoin Wallets
Some works use threshold signature in Bitcoin wallets to
provide a security policy to control sharing of the wallet and
protect it from theft or loss of stored private keys (Goldfeder
et al. 2015; Dikshit and Singh 2017). These approaches have
the additional benefit of providing some anonymity by
hiding the relationship between authorized users and
reducing transaction fees because they use a single key.
4 T-Mix Protocol
T-Mix maintains Mixcoin design properties and enhances its
availability and integrity. It comprises of two entities, a
mixing service M and client Alice. M comprises j mixers,
where M determines the threshold value i-out-of-j mixers
that participate in signing the warranty. M sets up the mixing
parameters and the threshold value i once at the creation of
the mixing service. Based on the threshold signature scheme
in (Ibrahim et al. 2003), these j mixers connect through a
private network. The communication channel is dedicated
because if m i broadcasts a message other mixers will recognize that it came from m i . All j mixers use a master clock
to ensure system synchronism and an agreement protocol
(Berman et al. 1992) to agree on the mixing operation. Alice
must deal with i mixers in the M service to mix her funds.
The mixing parameters are as follows:
v
the value to be mixed,
t 1
the deadline for Alice to send funds to M;
t 2
the deadline for M to return funds to Alice;
k out
the address to which Alice wishes to transfer her
funds;
p
the mixing fee rate Alice will pay;
n
a nonce, used to determine payment of randomized
mixing fee;
w
number of blocks M require to confirm Alice’s
payment.
Other parameters used in the protocol:
k esc
the escrow address, that M provides for Alice to
transfer v;
k’ esc the escrow address, that M uses to transfer v to
Alice’s k out;
K M
the M long-term key;
k in
Alice’s input address;
K out private key of Alice’s output address.
Figure 2 illustrates the protocol steps for mixing Alice’s
funds. The notation {x} K indicates that K signs the message x
and the notation {x} K(1,…,i) indicates that the message x is
signed by threshold (i, j) of the key K.
Step (1). Alice contacts M by multicasting the mixing
request to j mixers, which contains the mixing parameters
encrypted by M’s service public key K M .
Step (1.1). j mixers in M perform the Phase King algorithm (Berman et al. 1992) to agree on whether to accept or
reject Alice’s mixing request.
Step (2a). When M accepts the terms, j mixers create a
threshold escrow address k esc and distribute the private key
without a trusted dealer, as in (Ibrahim et al. 2003). Each
mixer sends a warranty back to Alice, which contains the k esc
address with mixing parameters but signed by a different
mixer key K Mi . Alice receives i warranties signed by i partial
keys.
Step (2b). If Alice does not receive acceptance of i mixers, then Alice’s request is rejected, and k out will be
destroyed.
Step (3). Alice reconstructs the received i signed warranties and verifies signature.
Step (3.1). Invalid warranty. If Alice finds out the
warranty is invalid, she will know that the M service is
compromised and aborts the protocol and destroys the k out .
In this case, Alice cannot publish a complaint to the network to influence the reputation of M because the network
cannot verify whether the whole service has been
compromised.
Step (3.2). Valid warranty. If the warranty is valid, Alice
proceeds with the protocol.
Step (3.2.1). Alice does not pay. If Alice does not transfer
funds to k esc by deadline t 1 , M’s mixers agree to abort the
protocol and delete the record.
Step (4). Alice transfers the agreed value v from her
address k in to k esc by time t 1 . After this step, M is obligated
to transfer an equal value of coins to k out by time t 2 .
294
W. F. Aldamegh and L. A. Alsulaiman
Decentralized Mixing Protocols. These are based on a
collaboration of untrusted Bitcoin users permuting their
ownership of their coins without any trusted third party.
CoinJoin (Maxwell 2013) relies on participants agreeing on
transaction inputs and outputs to create a group transaction.
CoinShuffle (Ruffing et al. 2014) improves CoinJoin’s
cryptograph layer to solve the internal unlinkability issue.
Altcoin Protocols. This category proposes solutions
based on advanced cryptography to provide strong anonymity, but it must substantially modify Bitcoin. Also, it
requires more storage and computational power per transaction than Bitcoin, which created new cryptocurrencies
such as Monero (2014).
3.2 Bitcoin Wallets
Some works use threshold signature in Bitcoin wallets to
provide a security policy to control sharing of the wallet and
protect it from theft or loss of stored private keys (Goldfeder
et al. 2015; Dikshit and Singh 2017). These approaches have
the additional benefit of providing some anonymity by
hiding the relationship between authorized users and
reducing transaction fees because they use a single key.
4 T-Mix Protocol
T-Mix maintains Mixcoin design properties and enhances its
availability and integrity. It comprises of two entities, a
mixing service M and client Alice. M comprises j mixers,
where M determines the threshold value i-out-of-j mixers
that participate in signing the warranty. M sets up the mixing
parameters and the threshold value i once at the creation of
the mixing service. Based on the threshold signature scheme
in (Ibrahim et al. 2003), these j mixers connect through a
private network. The communication channel is dedicated
because if m i broadcasts a message other mixers will recognize that it came from m i . All j mixers use a master clock
to ensure system synchronism and an agreement protocol
(Berman et al. 1992) to agree on the mixing operation. Alice
must deal with i mixers in the M service to mix her funds.
The mixing parameters are as follows:
v
the value to be mixed,
t 1
the deadline for Alice to send funds to M;
t 2
the deadline for M to return funds to Alice;
k out
the address to which Alice wishes to transfer her
funds;
p
the mixing fee rate Alice will pay;
n
a nonce, used to determine payment of randomized
mixing fee;
w
number of blocks M require to confirm Alice’s
payment.
Other parameters used in the protocol:
k esc
the escrow address, that M provides for Alice to
transfer v;
k’ esc the escrow address, that M uses to transfer v to
Alice’s k out;
K M
the M long-term key;
k in
Alice’s input address;
K out private key of Alice’s output address.
Figure 2 illustrates the protocol steps for mixing Alice’s
funds. The notation {x} K indicates that K signs the message x
and the notation {x} K(1,…,i) indicates that the message x is
signed by threshold (i, j) of the key K.
Step (1). Alice contacts M by multicasting the mixing
request to j mixers, which contains the mixing parameters
encrypted by M’s service public key K M .
Step (1.1). j mixers in M perform the Phase King algorithm (Berman et al. 1992) to agree on whether to accept or
reject Alice’s mixing request.
Step (2a). When M accepts the terms, j mixers create a
threshold escrow address k esc and distribute the private key
without a trusted dealer, as in (Ibrahim et al. 2003). Each
mixer sends a warranty back to Alice, which contains the k esc
address with mixing parameters but signed by a different
mixer key K Mi . Alice receives i warranties signed by i partial
keys.
Step (2b). If Alice does not receive acceptance of i mixers, then Alice’s request is rejected, and k out will be
destroyed.
Step (3). Alice reconstructs the received i signed warranties and verifies signature.
Step (3.1). Invalid warranty. If Alice finds out the
warranty is invalid, she will know that the M service is
compromised and aborts the protocol and destroys the k out .
In this case, Alice cannot publish a complaint to the network to influence the reputation of M because the network
cannot verify whether the whole service has been
compromised.
Step (3.2). Valid warranty. If the warranty is valid, Alice
proceeds with the protocol.
Step (3.2.1). Alice does not pay. If Alice does not transfer
funds to k esc by deadline t 1 , M’s mixers agree to abort the
protocol and delete the record.
Step (4). Alice transfers the agreed value v from her
address k in to k esc by time t 1 . After this step, M is obligated
to transfer an equal value of coins to k out by time t 2 .
294
W. F. Aldamegh and L. A. Alsulaiman