owned this note
owned this note
Published
Linked with GitHub
# P2P Mixing and Unlinkable Bitcoin Transactions
###### tags: `Tag(HashCloak - DC Net Readings)`
Author(s):Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate
Paper: [https://eprint.iacr.org/2016/824.pdf](https://eprint.iacr.org/2016/824.pdf)
### Table of Contents
[toc]
:::info
>Abstract: Starting with Dining Cryptographers networks (DC-net), several peer-to-peer (P2P) anonymous communication protocols have been proposed. Despite their strong anonymity guarantees none of those has been employed in practice so far: Most fail to simultaneously handle the crucial problems of slot collisions and malicious peers, while the remaining ones handle those with a significant increased latency (communication rounds) linear in the number of participating peers in the best case, and quadratic in the worst case. We conceptualize these P2P anonymous communication protocols as P2P mixing, and present a novel P2P mixing protocol, DiceMix, that only requires constant (i.e., four) communication rounds in the best case, and $4 + 2f$ rounds in the worst case of $f$ malicious peers. As every individual malicious peer can prevent a protocol run from success by omitting his messages, we find DiceMix with its worst-case linear-round complexity to be an optimal P2P mixing solution.
>
>On the application side, we find DiceMix to be an ideal privacy-enhancing primitive for crypto-currencies such as Bitcoin. The public verifiability of their pseudonymous transactions through publicly available ledgers (or blockchains) makes these systems highly vulnerable to a variety of linkability and deanonymization attacks. DiceMix can allow pseudonymous users to make their transactions unlinkable to each other in a manner fully compatible with the existing systems. We demonstrate the efficiency of DiceMix with a proof-of-concept implementation. In our evaluation, DiceMix requires less than 8 seconds to mix 50 messages (160 bits, i.e., Bitcoin addresses), while the best protocol in the literate requires almost 3 minutes in a very similar setting. As a representative example, we use DiceMix to define a protocol for creating unlinkable Bitcoin transactions.
>
>Finally, we discover a generic attack on P2P mixing protocols that exploits the implicit unfairness of a protocol with a dishonest majority to break anonymity. Our attack uses the attacker’s realworld ability to omit some communication from a honest peer to deanonymize her input message. We also discuss how this attack is resolved in our application to crypto-currencies by employing uncorrelated input messages across different protocol runs.
:::
![](https://i.imgur.com/glia1vK.png)
## III. SOLUTION OVERVIEW
Our core tool to design an efficient P2P mixing protocol is a Dining Cryptographers Network (DC-net) [14]. We describe an example of a DC-net involving two users.
* Suppose that two peers $p_1$ and $p_2$ share a key $k$ and that one of the peers ($e.g.$, $p_1$) wishes to anonymously publish a message $m$ such that $|m| = |k|$.
* For that, $p_1$ publishes $M_1 := m ⊕ k$ and $p_2$ publishes $M_2 := k$.
* An observer can compute M1 ⊕ M2, effectively recovering $m$.
The origin of this message is hidden:
* Without knowing the secret $k$, the observer cannot determine which peer published $m$.
Besides the need for pairwise symmetric keys, which can be overcome by a key exchange mechanism, there are two key issues to deploy a DC-net in practice with an arbitrary number of peers.
1. Making it possible that all peers can publish a message simultaneously.
2. Ensuring termination of the protocol even in the presence of malicious disruptors, while preserving anonymity.
### A. Handling Collisions
Each peer $p ∈ P$ in the mixing seeks to anonymously publish her own message $m_p$.
* Naively, they could run $|P|$ instances of a DC-net, where each peer randomly selects one instance (or slot) to publish her message.
* However, even if all peers are honest, two peers can choose the same slot with high probability, and their messages are unrecoverable [27].
* Instead, we follow the paradigm of handling collisions by redundancy [12], [20]:
* Assume that messages to be mixed are encoded as elements of a finite field $\mathbb{F}$ with characteristic greater than the number $n$ of peers.
* Given $n$ slots, each peer $i$, with message $m_i$, publishes $m^j_i$ (i.e., $m_i$ to the $j$-th power) in the $j$-th slot.
* This results in having a collision from all peers for each of the slots.
* Using addition in $\mathbb{F}$ instead of XOR to create DC-net messages, the $j$-th collision results on the $i$-th power sum $S_i = \sum_{i}m^j_i$.
* Now, we require a mechanism to extract the messages mi from the power sums $S_i$.
* Let assume that there are $n$ peers in a run of the DiceMix protocol. At the end of it, the peers can compute the power sums:
![](https://i.imgur.com/WL4YrlB.png)
* This can be then used to obtain the values of $x_1, . . . x_n$ using Newton’s identities [28].
* For that, let $f(x) = a_nx^n + a_{n−1}x_{n−1}+. . .+a_1x+a_0$ be a polynomial such that $f(x) = 0$ have roots $x_1, x_2, . . . , x_n$.
* Now, we know that $a_n = 1$ given that it is the coefficient of $x^n$ resulting from the product of $(x − x_1) · . . . · (x − x_n)$. Newton’s identities state that:
![](https://i.imgur.com/jdR7i2b.png)
* From here, we know all the $P_i$ so that we can easily recover the $a_i$.
* Now, once we know the coefficients for the polynomial $f(x)$, we can factorize it.
* The $n$ roots are the $n$ values that we were looking for.
### B. Handling Disruption and Ensuring Termination
Recovering the messages only works when all peers honestly follow the protocol. However, a peer could disrupt the DCnet by simply using inconsistent DC-net messages. Then we must ensure that the protocol will still eventually terminate successfully.
When a candidate set $M$ is determined, every honest peer checks whether her input message is indeed in $M$.
Depending on the outcome of this check:
* The peer either starts the confirmation subprotocol to confirm a good M.
* Or reveals the secret key used in the key exchange to determine who is responsible for an incorrect $M$.
. We face two challenges on the way to successful termination.
1. *Consistent Detection of Disruption:* The first challenge is to ensure that indeed $M$ does not contain any honest message.
* Only then will all honest peers agree on whether disruption has occurred and take the same control flow decision at this stage of the protocol, which is crucial for termination.
* To overcome this challenge, every peer must provide a non-malleable commitment (e.g., using a hash function) to its DC-net vector before it sees the vectors of other peers.
* Malicious peers are now forced to create their DC-net vectors independently of the DC-net vector (and the unpredictable input messages) of honest peers.
* Thus, the redundant encoding of messages ensures that a malicious peer is not able to create a malformed DC-net vector that results in a distortion of only a subset of the honest peers.
* Intuitively, to distort some messages but keep some other message $m$ of a honest peer intact, the malicious peer must influence all power sums consistently.
* This, however, would require a DC-net vector that depends on $m$ which is prevented by the non-malleability of the commitments.
* This ensures that all honest peers agree on whether $M$ is correct or not, and take the same control flow decision.
2. *Exposing a Disruptor:* The second challenge is that the misbehaving peer is not trivially detected given the sender anonymity property of DC-nets.
* To overcome this, every peer is required to reveal the secret key used in the initial key exchange.
* Then every peer can replay the steps done by every other peer and eventually detect and expel the misbehaving peer from a new run.
* Note that the revelation of the secret keys clearly breaks sender anonymity for the current run of the protocol.
* However, the failed run will be discarded and a new run with fresh cryptographic keys and fresh messages will be started without the misbehaving peer.
* An important guarantee provided by DiceMix is that if a protocol run fails, the honest peers agree on the set of malicious peers to be excluded.
> Personal Note: Much better than only being to select one malicion peer each run (PreFi?*)
* Although this is critical for termination, this aspect has not been properly formalized or addressed in some previous P2P mixing protocols [17], [45], [49] supposed to ensure termination.
## IV. THE DICEMIX PROTOCOL
In this section we present DiceMix, an efficient P2P mixing protocol, which terminates in only $4+2f$ rounds in the presence of $f$ malicious peers.
### A. Building Blocks
1. *Digital Signatures:* We require a digital signature scheme (KeyGen, Sign, Verify) unforgeable under chosen-message attacks (UF-CMA).
* The algorithm KeyGen returns a private signing key $s_k$ and the corresponding public verification key $v_k$.
* On input message $m$, Sign($s_k, m$) returns $σ$:
* A signature on message $m$ using signing key $s_k$.
* The verification algorithm Verify($p_k, σ, m$) outputs true iff $σ$ is a valid signature for $m$ under the verification key $v_k$.
2. *Non-interactive Key Exchange:* We require a non-interactive key exchange (NIKE) mechanism (NIKE.KeyGen, NIKE.SharedKey) secure in the CKS model [13], [24].
* The algorithm NIKE.KeyGen($id$) outputs a public key $npk$ and a secret key $nsk$ for given a party identifier $id$.
* NIKE.SharedKey($id_1, id_2, n{sk}_1, n{pk}_2, sid$) outputs a shared key for the two parties and session identifier sid.
* NIKE.SharedKey must fulfill the standard correctness requirement that for all session identifiers $sid$, all parties $id_1, id_2$, and all corresponding key pairs ($npk_1 , nsk_1$) and ($npk_2 , nsk_2$).
* It holds that NIKE.SharedKey($id 1, id 2, nsk 1, npk 2 , sid$) = NIKE.SharedKey($id_2, id_1, nsk_2, npk_1 , sid$).
* Additionally, we require an algorithm NIKE.ValidatePK($npk$), which outputs true if and only if $npk$ is a public key in the output space of NIKE.KeyGen.
* And we require an algorithm NIKE.ValidateKeys($npk, nsk$) which outputs true iff $nsk$ is a secret key for the public key $npk$.
Static Diffie-Hellman key exchange satifies these requirements [13], given a suitable key derivation algorithm such as NIKE.SharedKey$(id_1, id_2, x, g^y) · ·= K((g^{xy}, {id_1, id_2}, sid))$ for a hash function $K$ modeled as a random oracle.
3) *Hash Functions:* We require two hash functions H and G both modeled as a random oracle.
4) *Conventions and Notation for the Pseudocode:* We use arrays written as ARR[i], where $i$ is the index. We denote the full array (all its elements) as ARR[].
### B. Contract with the Application
In the following, we specify the contract between the DiceMix and the application calling it. We start with two guarantees provided by DiceMix to the application and then we describe features required on the application by DiceMix.
1. *Guarantees Provided to the Application:* The confirmation subprotocol is provided with two guarantees.
1. DiceMix ensures that all honest peers call the confirmation subprotocol in the same communication round with the same parameters; we call this property agreement.
2. To ensure that no peer can refuse confirmation for a legitimate reason, e.g., an incorrect set $M$ not containing her message, our protocol ensures that all honest peers deliver the same and correct message set $M$.
* Consequently, the confirmation subprotocol CONFIRM($i, P, M$) can safely assume that peers refusing to confirm are malicious. We call this *validity*.
* The purpose of both of these guarantees is to ensure correct functionality of the confirmation subprotocool, and the guarantees are only provided if the bulletin board is honest. As a consequence, it is up to the confirmation subprotocol to fail safely if they do not hold.
* *Agreement:* Assume that the bulletin board is honest.
* Let $p$ and $p'$ be two honest peers in a protocol instance.
* If $p$ calls CONFIRM($i, P, M$) in some communication round $r$, then $p'$ calls CONFIRM($i, P, M$) with the same message set $M$ and final peer set $P$ in the same communication round $r$.
* *Validity:* Assume that the bulletin board is honest.
* If honest peer $p$ calls CONFIRM($i, P, M$) with message set $M$ and final peer set $P$, then:
* For all honest peers $p'$ and their messages $m_p'$ , we have $m_p' ∈ M$,
* And we have $|M| = |P|$.
2. *Requirements on the Application:* Next, we specify the guarantees that the application must provide to DiceMix to ensure proper function.
* We assume that input messages generated by GEN() are encoded in a prime field $\mathbb{F}_q$, where $q$ is larger than the number of peers in the protocol.
* Also, we assume w.l.o.g. that the message $m$ returned by GEN() has sufficient entropy such that it can be predicated only with negligible probability.
* This can be ensured by a randomized encoding such as encoding $m$ as $m||r$ for a sufficiently large string $r$.
We require two natural properties from the confirmation subprotocol
1. Correct Confirmation: States that a successful call to the subprotocol indeed confirms that the peers in $P$ agree on $M$.
* Even if the bulletin board is malicious, we require the following:
* If a call to CONFIRM($i, P, M$) succeeds for peer $p$, then all honest peers in P have called CONFIRM($i, P, M$)
* (i.e., if the call returns an empty set $P_{malicious} = ∅$ of malicious peers refusing confirmation).
2. Correct Exclusion: states that in an unsuccessful call, the confirmation subprotocol identifies at least one malicious peer, and no honest peer is falsely identified as a malicious peer.
* Assume that the bulletin is honest.
* If CONFIRM($i, P, M$) returns a set $P_{malicious} \neq ∅$ for peer $p$, then CONFIRM($i, P, M$) returns the same set Pmalicious for every honest peer $p'$.
* Furthermore, the returned set $P_{malicious}$ does not contain honest peers.
### C. Protocol Description
We describe the DiceMix protocol in Algorithms 1 and 2.
> The black code is the basic part of the protocol; the blue code handle several concurrent runs offline peers.
1. *Single Run of the Protocol (Black Pseudocode):* The protocol starts in START-DICEMIX(), which receives as input:
* A set of other peers $P$.
* Our own identity *my*.
* An array VK[] of verification keys of the other peers.
* Our own signing key $sk$.
* And a predetermined session identifier $sid$.
A single run of DiceMix consists of four rounds.
1. Key exchange - (KE): Just uses the NIKE to establish pairwise symmetric keys between all peers (DC-KEYS()).
* Then each peer can derive the DC-net pads from these symmetric keys (DC-PAD()).
2. Publishing DC-net commitments - (CM): Each peer commits to her DC-net vector using hash function H.
* Adding randomness is not necessary, because we assume that the input messages contained in the DC-net vector have sufficient entropy.
* Publishing of Commitments - (DC): The commitments are opened in the third round. They are non-malleable and their purpose is to prevent a rushing attacker from letting his DC-net vector depend on messages by honest peers, which will be crucial for the agreement property.
* After opening the commitments, every peer has enough information to solve the DC-net and extract the list of messages by solving the power sums (DC-RES()).
4. Every peer checks whether her input message is in the result of the DC-net.
* Agreement will ensure that either every peer finds her message or no honest peer finds it.
If a peer finds her message, she proceeds to the confirmation subprotocol.
* Otherwise, she outputs her secret key.
* In this case, every other peer publishes her secret key as well, and all peers can replay each other protocol messages for the current run.
* This will expose the misbehaving peer and honest peers will exclude him from the next run.
2. Concurrent Runs of the Protocol (*Blue Pseudocode*): A simple but inefficient way of having several runs is to start a single run of the protocol and only after misbehavior is detected, start a new run without the misbehaving peer.
* This approach requires $4 + 4f$ rounds, where $f$ is the number of disruptive peers (assuming that CONFIRM() takes one round).
* To reduce the number of communication rounds to $4 + 2f$, we deploy concurrent runs as exemplified in Fig. 2.
* We need to address two main challenges:
1. When a peer disrupts the DC-net phase of run $i$, it must be possible to “patch” the already started run $i+ 1$ to discard messages from misbehaving peers in run $i$.
* For that, run $i$ must reach the last phase (SK or CF) before run $i + 1$ reaches DC phase.
* Until run $i+ 1$ sends the DC message, it can can be patched as follows:
* In the DC phase of run $i+1,$ honest peers broadcast not only their DC-net messages, but also in parallel they reveal (RV) the symmetric keys shared in run $i + 1$ with malicious peers detected in run $i$.
3. Handling Offline Peers (*Blue Pseudocode*): If a peer $p$ has not provided a (valid) broadcast message to the bulletin board (in time), all honest peers will agree on that fact, and exclude the unresponsive peer.
* Observe that for missing messages from the first two broadcasts (KE and CM), the current run can be continued.
* Peers not sending KE are just ignored in the rest of the run.
* Peers not sending CM are handled by revealing symmetric keys exactly as done with concurrent runs.
> Observe that this crucially ensures that even in the presence of passively disrupting peers, only 4 + 2f communications rounds are necessary.
![](https://i.imgur.com/yY6e1Xv.png)
![](https://i.imgur.com/h9jJ9Wl.png)
### D. Security and Correctness Analysis
In this section, we discuss why DiceMix achieves all required properties, namely the security properties sender anonymity and termination as well as the guarantees validity and agreement that the application may rely on.
1. ***Sender Anonymity:*** Consider a protocol execution in which a honest peer $p$ succeeds with message $m_p$ and final peer set $P$, and let $p' ∈ P$ be another honest peer.
* We have to argue that the attacker cannot distinguish whether $m_p$ belongs to $p$ or $p'$.
Since both $p$ and $p'$ choose fresh messages $m_p$, $m_p'$ , and fresh NIKE key pairs in each run, it suffices to consider only the successful run $i$.
* Since $p$ succeeds in run $i$, the call to CONFIRM(i, P, M) has succeeded.
* By the “correct confirmation” property of CONFIRM(. . .), $p'$ has started CONFIRM(i, P, M) in the same communication round as $p$.
* By construction of the protocol, this implies two properties about $p'$:
1. $p'$ will not reveal her secret key in round SK.
2. Peer $p'$ assumes that $p$ is not excluded in run $i$, and thus has not revealed the symmetric key shared with p in round RV. * (Part (2) is only relevant in the concurrent variant of the protocol.)
As the key exchange scheme is secure in the CKS model and the public keys are authenticated using signatures, the attacker cannot distinguish the random DC-nets derived from the symmetric key between $p$ and $p'$ from random pads.
* Thus, after opening the commitments on the pads, $p$ has formed a proper DC-net with at least $p'$.
* The security guarantee of original Chaum’s DC-nets [14] implies that the attacker cannot distinguish $m_p$ from $m_{p'}$ before the call to CONFIRM(i, P, M).
> Now, observe that the execution of subprotocol CONFIRM(i, P, M) does not help in distinguishing, since all honest peers call it with the same arguments, which follows by the “correct confirmation” property as we have already argued. This shows sender anonymity.
2. ***Validity:*** To show validity, we have to show that if honest peer $p$ calls CONFIRM(i, P, M) with message set $M$ and final peer set $P$, then:
* *(i)* for all honest peers $p'$ and their messages $mp'$, we have $m_p' ∈ M$, and
* *(ii)* we have $|M| = |P|$.
* For the first part of validity, recall that we assume the bulletin board to be honest for validity, so every peer receives the same broadcast messages.
* Under this assumption and the assumption that the signature scheme is unforgeable, a code inspection shows that after receiving the DC message, the entire state of a protocol run $i$ is the same for every honest peer, except for:
* The signing keys.
* The own identity *my*.
* And the message $m$ generated by GEN().
* From these three items, only $m$ influences the further state and control flow, and it does so only in the check $m ∈ M$ at the end of RUN(. . .).
We now show as intermediate step that in every run $i$, the condition $m ∈ M$ (in the last part of RUN(. . .)) is either true for all honest peers or is false for all honest peers.
> Note that also $M$ is entirely determined by broadcast messages and thus the same for all honest peers.
* Let $p$ and $p'$ be two honest peers with their input messages $m_p$ and $mp'$ in run $i$, and assume for contradiction that the condition is true for $p$ but not for $p'$. (i.e., $m_p ∈ M$ but $m_p' \notin M$.)
* This implies that at least one malicious peer $a$ has committed to an ill-formed DC-net vector in run $i$, (i.e., a vector which is not of the form ($m_a, m^2_a, . . . , m^n_a)$ with $n ≥ 2$.)
* Since $m_p ∈ M$, this ill-formed vector left the message mp intact.
* This implies that the attacker has information about the other DC-net vectors.
A simple algebraic argument shows that even for the second power, it is not feasible to come up with additive offset to the power sum that changes some of the encoded messages but leaves others intact:
* To change some $m_p'$ to $m^{'}_p + δ$, knowledge of $(m_p' + ∆)^2 − m^2_{p'} = 2m_{p'}∆ + ∆^2$ and thus knowledge of $m_p'$ is necessary.
> As the message H(dc, DC[ ]) implements a hiding, binding and non-malleable commitment on DC[ ]; it is infeasible, even for a rushing malicious peer a, to have committed to an ill-formed vector that leaves mp intact. This is a contradiction, and thus the condition $m ∈ M$ evaluates equivalently for all honest peers.
Now observe that the condition $m ∈ M$ determines whether CONFIRM(. . .) is called.
* That is, whenever CONFIRM(i, P, M) is called by some honest peer $p$, then $m_p' ∈ M$ for all honest peers $p'$.
* This shows the first part of validity.
* For the second part of validity (|M| = |P|).
* Observe that in the beginning of an execution and whenever $P$ changes, a new run with $|P|$ peers is started, each of which submits exactly one message.
* This shows validity
3. ***Agreement:*** : To show agreement, we have to show that for all runs $i$, if one honest peer $p$ calls CONFIRM(i, P, M) in some round, then all honest peers $p'$ call CONFIRM(i, P, M) in the same round.
* This follows from validity.
* By the first part of validity, we know that some honest peer calls CONFIRM(i, P, M), then $m_p' ∈ M$ for all honest peers $p'$ in run $i$.
* By construction of the protocol, $m_p' ∈ M$ this is exactly the condition that determines whether $p'$ calls CONFIRM(i, P, M).
* Thus all honest peers p 0 call CONFIRM(i, P, M) in the same round.
4. ***Termination:*** Now, we show why the protocol terminates for every honest peer. We have already argued above (for validity) that in the presence of an honest bulletin board, all honest peers take the same control flow decision (whether to call CONFIRM(. . .) or not at the end of each run). We can thus distinguish cases on this control flow decision.
* If CONFIRM(. . .) is called in a failed run, then it returns the same non-empty set of malicious peers (by the “correct exclusion” property), and those peers will be excluded by every honest peer.
* If CONFIRM(. . .) is not called in a run, then there must have been disruption by at least one malicious peer.
* Replaying all protocol messages of this run (with the help of then published secret keys) clearly identifies at least one malicious peer.
* And since all honest peers run the same code (BLAME(. . .)) on the same inputs to do so, they will all exclude the same set of malicious users.
We have shown that in each failed run, all honest peers exclude the same non-empty set of malicious peers. Eventually, we will reach one of two cases.
1. The number of unexcluded peers will drop below 2.
* In that case the protocol is allowed to fail and thus there is nothing to show.
2. We will reach a run in which all peers behave honestly (whether they are controlled by the attacker or not).
* This run will successfully terminate, which shows termination.
### E. Variants of the Protocol
The design of DiceMix follows the P2P paradigm, and consequently, we do not expect the bulletin board to implement any real functionality or perform any computation. The bulletin board is a simple broadcast mechanism and may be replaced by a suitable reliable broadcast protocol [47].
However, if one is willing to require a more sophisticated bulletin board with dedicated functionality, the efficiency of DiceMix can be improved. (It is important to note that even a dedicated bulletin board is still only trusted for termination and not for anonymity.)
**Dropping the Commitment Phase:** Recall that the purpose of the non-malleable commitments is to prevent malicious peers from choosing their DC vectors depending on the DC vectors of the honest peers.
* Assume that the bulletin board supports secure channels, and broadcasts the messages in the DC round only after all peers have submitted their messages.
* Then independence is ensured with a honest bulletin board, and we can drop the CM (commitment) round.
* This is secure because the independence of the DC vectors is only necessary for termination but not for anonymity, and we trust the bulletin board for termination already.
* A serial protocol execution (without concurrency) will then follow the pattern ”KE (DC CF/SK)+”, where the plus indicates that these phases are performed once or several times. (key exchange, publish commits to dc messages, accept results/publish keys of malicious node)
* With the help of concurrency, we can run the key exchange (KE) concurrently to the confirmation phase (CF/SK), and reduce the number of rounds to $3 + 2f$ (assuming that the confirmation phase takes one round.)
* An example run is depicted in Fig. 3.
* Note that a revelation of symmetric keys (RV in the original protocol) will not be necessary anymore, because the malicious peers to exclude are determined before the DC round of second run
* Moreover, a dedicated bulletin board can perform the expensive computation of solving the equation system involving the power sums, and broadcast the result instead of the DC vectors.
* The bulletin board would then also be responsible for handling inconsistent messages in the SK run.
* It would then announce the malicious peers after having received all secret keys.
* This saves communication in the rounds DC and SK.
* Again, security is preserved, because we trust bulletin board for termination.
![Uploading file..._2wel4ngig]()
## V. PERFORMANCE ANALYSIS
In this section, we analyze the performance of DiceMix. We first analyze the communication costs, and then evaluate the running time with the help of a prototype implementation. Our results show that DiceMix is practical and outperforms existing solutions.
![](https://i.imgur.com/YihObIP.png)
![](https://i.imgur.com/WZdpTzv.png)
Using concurrent runs, DiceMix needs $(c + 3) + (c + 1)f$ communication rounds, where $f$ is the number of peers actually disrupting the protocol execution, and $c$ is the number of rounds of the confirmation subprotocol.
* In the case $c = 1$ such as in our Bitcoin mixing protocol (Section VI), DiceMix needs just $4 + 2f$ rounds.
The communication costs per run and per user are dominated by the broadcast of the DC-net array DC$[my][ ]$ of size $n·|m|$ bits, where $n$ is the number of peers and $|m|$ is the length of a mixed message.
* All three other broadcasts have constant size at any given security level.
### A. Prototype Implementation
We have developed a proof-of-concept implementation of DiceMix based on an existing implementation of the Dissent protocol [17].
* This unoptimzed implementation encompasses the complete functionality to enable testing a successful run of DiceMix without disruptions.
> The implementation is written in Python and uses OpenSSL for ECDSA signatures on the secp256k1 elliptic curve (as used in Bitcoin) at a security level of 128 bits. We use a Python wrapper for the Pari-gp library \[33\] to find the roots of the power sum polynomial.
1. *Testbed:* We tested our DiceMix implementation in Emulab [52].
* Emulab is a testbed for distributed systems that enables a controlled environment with easily configurable parameters such as network topology or bandwidth of the communication links.
* We simulated a network setting in which all peers (10 Mbit/s) have pre-established TCP connections to a bulletin board (1 Gbit/s); all links had a delay of 50 ms.
* We used different Emulab machines (2.2–3.0 GHz) to simulate the peers.
* Note that the slowest machine is the bottleneck due to the synchronization enforced by the broadcasts.
* We ran the protocol with a varying number of peers, ranging from 5 to 50.
* Each peer had as input for the mixing a 160-bit message (e.g., a Bitcoin address).
2) *Results:*
1. We measured wall-clock time, averaged over all peers.
* As shown in Fig. 4, we observe that even with 50 participants, DiceMix runs in less than 8 seconds.
2. we measured computation time.
* The results are depicted in Fig. 5.
* We considered the average total computation time spent by a peer (purple line), and the average computation time excluding solving the equation system involving the power sums (i.e., green line).
3) *Optimization:* We observe that solving the equation system is quite expensive, namely about 2 seconds for 50 peers.
* To demonstrate that this is mostly due to lack of optimization, we developed an optimized stand-alone application for this step in C++ using the FLINT number theory library [29], which provides a highly optimized implementation of the Kaltofen-Shoup algorithm for polynomial factorization over finite fields [32].
* Our optimized application solves the equation system involving the power sums in about 0.15 seconds for 50 peers on a 2.10 GHz (Intel Core i7-4600U) machine, using 6 MB of DDR3-1600 RAM.
* This shows that optimizations can reduce the running time of the protocol further.
4. *Conclusion:* The experimental results show that even our unoptimized implementation of DiceMix scales to a large number of peers and outperforms state-of-the-art P2P mixing solutions such as CoinShuffle [45] and Dissent [17] considerably.
* In comparison, CoinShuffle (as an optimized variant of the Dissent shuffle protocol) needs slightly less than 3 minutes to complete a successful run of the P2P mixing protocol in a very similar test environment with 50 peers.
## VI. EFFICIENT COIN MIXING IN BITCOIN
Several different heuristics to link Bitcoin payments sent or received by a particular user have been proposed in the literature [1], [3], [34], [40], [44], [46].
* Ultimately, cryptocurrencies such as Bitcoin using a public Blockchain may in fact provide less anonymity than traditional banking.
* Coin mixing has emerged as a technique to overcome this problem while maintaining full compatibility with current Bitcoin protocol.
* We propose CoinShuffle++, a highly efficient coin mixing protocol resulting from the application of DiceMix to the Bitcoin setting.
### B. Security Goals
The protocol must guarantee correct balance, a security property of interest when the P2P mixing protocol is leveraged to mix output accounts that enable privacy preserving transactions in payment systems.
* Correct Balance: If the P2P mixing protocol succeeds for peer $p$, then balance of $p$’s output account is at least $β$ (ignoring transaction fees), where $β$ is mixing amount in the P2P mixing protocol.
* In negative case, the total balance of the accounts of $p$ is not reduced (ignoring transaction fees).
### C. The CoinShuffle++ Protocol
CoinShuffle++ leverages DiceMix to perform a Bitcoin transaction where the input and output accounts for any given (honest) peer cannot be linked. In particular, CoinShuffle++ creates a fresh pair of signing-verification Bitcoin keys and returns the verification key to implement GEN().
* Then, for the confirmation subprotocol CONFIRM(. . .), CoinShuffle++ uses CoinJoin [37], [39] to perform the actual mixing.
* A CoinJoin transaction allows a set of peers to mix their coins without the help of a third party.
* In such a transaction, peers set their current Bitcoin accounts as input and a mixed list of fresh Bitcoin accounts as output.
* Crucially, peers can verify whether the thereby constructed transaction transfers the correct amount of coins to their fresh output account and only if all peers agree and sign the transaction, it becomes valid.
* So in the case of CoinShuffle++, the explicit confirmation provided by DiceMix is a list of valid signatures, one from each peer, on the CoinJoin transaction.
> Note that DiceMix guarantees that everybody receives the correct list of outputs accounts in the confirmation subprotocol. So a peer refusing to sign the CoinJoin transaction can safely be considered malicious and removed.
We define CoinShuffle++ in Algorithm 3. There, we denote by CoinJoinTx$(VK_{in}[], VK_{out}[], β)$ a CoinJoin transaction that transfers $β$ bitcoins from every input to every output account (where $β$ is a pre-arranged parameter). Moreover, we denote by Submit$(tx, σ[ ])$ the submission of tx including all signatures to the Bitcoin network.
1. *Security Analysis:* Observe that CoinShuffle++ adheres to the requirements specified in Section IV-B.
* Thus, sender anonymity and termination in CoinShuffle++ are immediate. (We refer to [39] for a detailed taint-based analysis on the privacy implications of CoinJoin-based protocol providing sender anonymity.)
* Correct balance is enforced by the CoinJoin paradigm:
* By construction, a peer signs only transactions that will transfer his funds from her input address to her output address.
> *(assuming they meant her 3x here)
2. *Performance Analysis:* In our performance analysis of DiceMix (Section V), GEN() creates a new ECDSA key pair and CONFIRM(. . .) obtains ECDSA signatures from all peers (using their initial ECDSA key pairs) on a bitstring of 160 bits.
* This is almost exactly CoinShuffle++, so the performance analyses of DiceMix carries over to CoinShuffle++.
3) *Practical Considerations:* There are several considerations when deploying CoinShuffle++ in practice.
1. Bitcoin charges transactions with a small $fee$ to prevent DoS attacks.
2. The mixing amount $β$ must be the same for all peers but peers typically do not hold the exact mixing amount in their input Bitcoin account.
3. After honestly performing the CoinShuffle++ protocol, a peer could spend her bitcoins in the input account before the CoinJoin transaction is confirmed, in an attempt of double-spending.
* All these challenges are easy to overcome.
* We refer the reader to the literature on CoinJoin based mixing, e.g., [37], [39], [45], for details.
*Compatibility and Extensibility:* Since CoinJoin transactions work in the current Bitcoin network, CoinShuffle++ is immediately deployable without any change to the system.
* Moreover, the fact that DiceMix is generic in the CONFIRM(. . .) function allows to define variants of CoinShuffle++ to support a wide range of crypto-currencies and signature algorithms, including interactive signature protocols. cryptocurrencies.
* For example, the integration of Schnorr signatures is planned in an upcoming Bitcoin software release [8].
* This modification will enable aggregate signatures using a interactive two-round protocol among the peers in a CoinJoin transaction [38].
* Given that signatures are often the largest individual part of the transactions, this enhancement greatly reduces the size of transactions and thus the transaction fee, thereby making mixing using CoinJoin transactions even cheaper.
![](https://i.imgur.com/fSU3h5c.png)
## VII. RELATED WORK IN CRYPTO-CURRENCIES
In the following we overview the literature on privacypreserving protocols for crypto-currencies. Related work for P2P mixing protocols is discussed throughout the paper.
### A. Privacy-preserving Crypto-currencies
**Zerocoin** [41] and its follow-up work Zerocash [4], whose implementation Zcash is currently in an alpha stage [54], are crypto-currencies protocols that provide anonymity by design.
* Although these solutions provide strong privacy guarantees, it is not clear whether Zcash will see widespread adoption, in particular given its reliance on a trusted setup due to the use of zkSNARKS.
**CoinShuffle++** builds on top of Bitcoin, and thus can be deployed immediately and seamlessly without requiring any changes to the Bitcoin protocol.
* Bitcoin is by far the most widespread crypto-currency and will most probably retain this status in the foreseeable future, so users are in need of solutions enhancing privacy in Bitcoin.
The **CryptoNote** design [51] relies on ring signatures to provide anonymity for the sender of a transaction.
* In contrast to CoinShuffle++, an online mixing protocol is not necessary and a sufficient anomyity set can be created using funds of users currently not online. However, this comes with two important drawbacks for scalability.
1. CryptoNote requires each transaction to contain a ring signature of size $O(n)$, where $n$ is the size anonymity set, whereas our approach based on CoinJoin needs only constant space per user.
* Storing the ring signatures requires a lot of precious space in the blockchain, and verifiying them puts a large burden on all nodes in the currency network.
* (In other words, the advantage of CoinShuffle++ is that it moves the anonymization work to an online mixing protocol, which is independent of the blockchain.)
2. CryptoNote is not compatible with pruning, a feature supported e.g., by the Bitcoin Core client [7].
* Pruning reduces the storage requirements of nodes drastically by deleting old blocks and spent transaction once verified.
* This is impossible in CryptoNote because anonymity ensures that it is not entirely clear whether a transaction has been spent or not.
* A CoinJoin-based approach such as CoinShuffle++ does not suffer from this problem and is compatible with pruning.
### B. Centralized Mixing Services
**Blindly Signed Contracts** [31] proposes a centralized mechanism based on the combination of blind signatures and smart contract to solve both mentioned challenges, i.e., theft and anonymity.
* However, the adoption of this approach requires a protocol change, which can be implemented as a soft-fork in the current Bitcoin blockchain.
* Moreover, this mechanism requires four Bitcoin transactions per peer, three of them to be confirmed sequentially.
* Even when using potentially risky one-block confirmations, this implies that mixing takes 30 minutes on average and transaction fees for four transactions per peer.
* The follow-up work TumbleBit [30] proposes a mechanism fully compatible with Bitcoin but still requires at least two blocks to be confirmed sequentially.
> CoinShuffle++ uses a single transaction for all peers and thus requires much less time and fees from the peers.
### C. Other P2P Approaches
**CoinParty**[55] is a protocol where a set of mixing peers is used to mix coins from the users. In this approach, they assume that 1/3 of the mixing parties are honest.
* However, this trust assumption is not in line with the Bitcoin philosophy, and much worse, it is unclear how to realize it in a P2P setting without strong identities, where Sybil attacks are easily possible.
* CoinShuffle++, instead, does not make any trust assumption on the mixing participants, except that there must be two honest peers, which is fundamental requirement for any protocol providing anonymity.
### D. Sybil-Resistant Approaches
**Xim** [6] improves on its related previous work [3] in that it uses a fee-based advertisement mechanism to pair partners for mixing, and provides evidence of the agreement that can be leveraged if a party aborts.
* Even in the simple case of a mixing between two peers, Xim requires to publish several Bitcoin transactions in the Bitcoin blockchain, what takes on average at least 10 minutes for each transaction.
> CoinShuffle++ instead requires to submit a single transaction to the Bitcoin blockchain independently on the number of peers. Moreover, although CoinShuffle++ does not prevent malicious peers from disrupting the protocol, it provides a mechanism to identify the misbehaving peer so that it can be excluded and termination is ensured.
## VIII. A DEANONYMIZATION ATTACK ON STATE-OF-THE-ART P2P MIXING PROTOCOLS
In this section, we show a deanonymization attack on stateof-the-art P2P mixing protocol.
At the core of the problem is handling of passive disruption, i.e., peers that appear to be offline.
* However, it turns out that the ability to finish the protocol without a particular peer $p$ is a serious problem for this peer’s anonymity.
* In fact, we will describe an attack enabling a network attacker to break the anonymity of peer $p$!
![](https://i.imgur.com/TS93fDQ.png)
* This is not at all a problem if peer $p$ is proven to be an active disruptor and thus malicious.
* However, sacrificing the anonymity of $p$ is a serious issue and renders any protocol insecure if $p$ just appears to be offline.
* Peer p could in fact be honest, because there is no “smoking gun” that allows the other peers to conclude that $p$ is malicious.
* To the best of our knowledge, this security problem has been overlooked in the literature so far.
> Personal Note: More recent literatrue seems to suggest that with a PoS system these users may simply lose their potential reward from a round where they are inactive, without hindering their anonymity.
## IX. CONCLUSIONS
In this work we present DiceMix, a P2P mixing protocol based on DC-nets that enable participants to anonymously publish a set of messages ensuring sender anonymity and termination.
* DiceMix avoids slot reservation and still ensures that no collisions occur, not even with a small probability.
* This results in DiceMix requiring only 4 rounds independently on the number of peers, and $4 + 2f$ rounds in the presence of $f$ misbehaving peers.
* We have implemented DiceMix and showed its practicality to enable privacy preserving operations in several scenarios.
We use DiceMix to implement CoinShuffle++, a practical decentralized coin mixing for Bitcoin. Our evaluation results show that CoinShuffle++ is a promising approach to ensure sender anonymity in Bitcoin requiring no change in the current Bitcoin protocol.