transactions on the blockchain (Biryukov and Khovratovich
2014; Fleder et al. 2015; Maesa et al. 2016, 2017). When at
least one transaction’s address is linked to the real user’s
identity, then all the user’s past and future transactions may
be exposed, which compromises anonymity. Figure 1 shows
the classification of proposed solutions to address this Bitcoin privacy issue, which we will discuss in Sect. 3.
1.2 Mixing Service
Mixing protocols maintain anonymity by hiding the map
between the transaction’s input and output addresses (Bitcoin Wiki 2018). Based on the way of mixing, we classify
them into two categories: centralized and decentralized
mixing protocols (see Fig. 1).
Mixcoin (Bonneau et al. 2014) is a centralized mixing
service that hides the relationship between two transacting
parties. Mixcoin introduced a mix of indistinguishability
property in which the mixing transactions cannot be distinguished from non-mixing transactions. This property uses a
normal Bitcoin transaction with fresh addresses for each
mixing operation. This increases anonymity against passive
attacks. Although Mixcoin contains concepts that increase
anonymity, it has shortcomings in protecting against active
attacks and integrity issues as discussed in Sect. 2.2.
1.3 Contribution of the Research
Our contributions in this paper are as follows:
• Increased service availability by redesigning the protocol
to accommodate threshold cryptography, which prevents
the service from being a single point of failure, as the
active attacker needs to compromise j − i + 1 mixing
servers to make the mixing service unusable.
• Increased service integrity as tampering with the number
of coins or output address requires compromised j −
i + 1 mixers.
• Valid proof of the theft complaint by proving ownership
of the addresses published in the theft complaint.
The paper is organized as follows: Sect. 2 presents the
background, Sect. 3 discusses related work, Sect. 4 describes
T-Mix, and Sect. 5 presents conclusions and suggests future
work.
2 Background
In this section, we present a high-level description of
threshold cryptography and the basic Mixcoin model.
2.1 Threshold Cryptography
A cryptographic mechanism allows a group of users to
participate in encrypting or decrypting data or verifying a
digital signature (Shamir 1979). In a threshold signature, an
(i, j) threshold indicates that the private key splits into
j pieces, which are shared and distributed over j participants.
Each participant receives a share of the private key. Any
subset of participants with size equal or greater than i can
construct a digital signature, while the subset with size less
than i cannot. Verifying the validity of the threshold digital
signature requires first reconstructing i signatures then verifying these using the associated public key.
The main feature of threshold signatures is that the private key is never stored in a single location, which ensures
that no single point of failure exists from which to steal the
private key. The attacker also cannot reconstruct or reveal
the private key without knowing i partial private keys
(Boneh and Shoup 2017). Bitcoin protocol uses the Elliptic
Curve Digital Signature Algorithm (ECDSA) as public key
cryptography (Bitcoin Wiki 2017) and its threshold signature (Ibrahim et al. 2003) is compatible with Bitcoin
(Goldfeder et al. 2015).
2.2 Mixcoin
Mixcoin provides a mixing service with a cryptography
layer. If Alice has coins at her address k in and wants to
transfer her fund to a fresh address k out without linking the
two addresses, she contacts a mixer M who offers a mixing
service in exchange for a fee. When Alice and M agree on
the mixing terms, Alice sends her funds to M’s escrow
address k esc . At the agreed time, M sends an equal value to
k out . Besides the mixing fees, M has a virtual reputation to
maintain, which incentives M to act honestly. Mixcoin
design is based on the following properties:
1. Accountability: Mixcoin guarantees that it can detect
when M misbehaves, by giving Alice a signed warranty,
that roughly says: “If Alice sends me v coins by time t 1 , I
will send back v coins to her k out by time t 2 ”. This signed
warranty enables Alice to prove M’s misbehavior by
Privacy Solutions for Bitcoin
Altcoin Protocols
Mixing Protocols
Centralized Mixing
Decentralized Mixing
Fig. 1 Privacy solutions for improving Bitcoin anonymity
292
W. F. Aldamegh and L. A. Alsulaiman
2014; Fleder et al. 2015; Maesa et al. 2016, 2017). When at
least one transaction’s address is linked to the real user’s
identity, then all the user’s past and future transactions may
be exposed, which compromises anonymity. Figure 1 shows
the classification of proposed solutions to address this Bitcoin privacy issue, which we will discuss in Sect. 3.
1.2 Mixing Service
Mixing protocols maintain anonymity by hiding the map
between the transaction’s input and output addresses (Bitcoin Wiki 2018). Based on the way of mixing, we classify
them into two categories: centralized and decentralized
mixing protocols (see Fig. 1).
Mixcoin (Bonneau et al. 2014) is a centralized mixing
service that hides the relationship between two transacting
parties. Mixcoin introduced a mix of indistinguishability
property in which the mixing transactions cannot be distinguished from non-mixing transactions. This property uses a
normal Bitcoin transaction with fresh addresses for each
mixing operation. This increases anonymity against passive
attacks. Although Mixcoin contains concepts that increase
anonymity, it has shortcomings in protecting against active
attacks and integrity issues as discussed in Sect. 2.2.
1.3 Contribution of the Research
Our contributions in this paper are as follows:
• Increased service availability by redesigning the protocol
to accommodate threshold cryptography, which prevents
the service from being a single point of failure, as the
active attacker needs to compromise j − i + 1 mixing
servers to make the mixing service unusable.
• Increased service integrity as tampering with the number
of coins or output address requires compromised j −
i + 1 mixers.
• Valid proof of the theft complaint by proving ownership
of the addresses published in the theft complaint.
The paper is organized as follows: Sect. 2 presents the
background, Sect. 3 discusses related work, Sect. 4 describes
T-Mix, and Sect. 5 presents conclusions and suggests future
work.
2 Background
In this section, we present a high-level description of
threshold cryptography and the basic Mixcoin model.
2.1 Threshold Cryptography
A cryptographic mechanism allows a group of users to
participate in encrypting or decrypting data or verifying a
digital signature (Shamir 1979). In a threshold signature, an
(i, j) threshold indicates that the private key splits into
j pieces, which are shared and distributed over j participants.
Each participant receives a share of the private key. Any
subset of participants with size equal or greater than i can
construct a digital signature, while the subset with size less
than i cannot. Verifying the validity of the threshold digital
signature requires first reconstructing i signatures then verifying these using the associated public key.
The main feature of threshold signatures is that the private key is never stored in a single location, which ensures
that no single point of failure exists from which to steal the
private key. The attacker also cannot reconstruct or reveal
the private key without knowing i partial private keys
(Boneh and Shoup 2017). Bitcoin protocol uses the Elliptic
Curve Digital Signature Algorithm (ECDSA) as public key
cryptography (Bitcoin Wiki 2017) and its threshold signature (Ibrahim et al. 2003) is compatible with Bitcoin
(Goldfeder et al. 2015).
2.2 Mixcoin
Mixcoin provides a mixing service with a cryptography
layer. If Alice has coins at her address k in and wants to
transfer her fund to a fresh address k out without linking the
two addresses, she contacts a mixer M who offers a mixing
service in exchange for a fee. When Alice and M agree on
the mixing terms, Alice sends her funds to M’s escrow
address k esc . At the agreed time, M sends an equal value to
k out . Besides the mixing fees, M has a virtual reputation to
maintain, which incentives M to act honestly. Mixcoin
design is based on the following properties:
1. Accountability: Mixcoin guarantees that it can detect
when M misbehaves, by giving Alice a signed warranty,
that roughly says: “If Alice sends me v coins by time t 1 , I
will send back v coins to her k out by time t 2 ”. This signed
warranty enables Alice to prove M’s misbehavior by
Privacy Solutions for Bitcoin
Altcoin Protocols
Mixing Protocols
Centralized Mixing
Decentralized Mixing
Fig. 1 Privacy solutions for improving Bitcoin anonymity
292
W. F. Aldamegh and L. A. Alsulaiman