Bitcoin Transactions & Privacy (part 3)

## gistfile1.txt
Context

This third part is about known and potential attacks against the privacy provided by tools like coinjoin.


Known attacks & weaknesses

- Linkability of inputs and outputs

A good illustration of this attack is Coinjoin Sudoku (see (1) for details).
Coinjoin Sudoku tries to detect flaws in the mixing algorithm by considering the transaction alone (it computes the intrinsic values of the metrics).
It is worth noting this kind of attack can be repeated over time by computing actual values whenever new side-channel information are gathered (address clustering, ...).


- Inputs merging

Coinjoin Sudoku can also be used to cluster addresses associated to several inputs.
The principle is: if several inputs are deterministically linked to a same output, addresses associated to these inputs can be clustered together.

Let's note that detection of deterministic links is a strong constraint which can be relaxed.
A probabilistic approach is sometimes enough to detect inputs which are likely to be controlled by a same entity.

Example:
This transaction (https://oxt.me/transaction/7d588d52d1cece7a18d663c977d6143016b5b326404bbf286bc024d5d54fcecb) is a coinjoin with 4 participants and a "coinjoined amount" of 0.84077613 BTC.
There's 5 inputs which leads us to think that 2 inputs are controlled by a same participant.
The natural next step is to find the inputs with amount < coinjoined amount (inputs 4 and 5).
In this specific case, it seems reasonable to infer these 2 inputs are controlled by a same entity.

Notes:
- inputs 4 & 5 have identical link probability vectors
- the severity of these leaks depend on the specific context of the coinjoin transaction (1 round vs several rounds, ...)


- "Hell is other people"

A "weakness" of joint transactions is their reliance to multiple participants.
The main consequence is that your actual privacy relies on your best practices but it also relies on the best practices of other participants.

A classic example of this point is a joint transaction with 2 participants:

  i1: UserA 1btc --           -- o1: 0.8btc UserA (coinjoined output)
	           \    T1   /-- o2: 0.2btc UserA (change output)
		    |-------|
	           /         \-- o3: 0.8btc UserB (coinjoined output)
  i2: UserB 2btc --           -- o4: 1.2btc UserB (change output)

Let's say that UserB uses strong privacy policies but UserA lacks of practice.

Further in time:
- at time t1: UserA pays 0.7btc with the coinjoined output and gets a change of 0.1btc
- at time t2: UserA pays 0.25btc by merging the change of its payment and the change of the coinjoin.

As a direct consequence:
- o1 and o2 are deterministically linked to i1
- o3 and o4 are deterministically linked to i2 => UserB has lost the protection provided by the coinjoin transaction without any action done !

Rules:
- Use several rounds of coinjoin transactions to decrease this risk,
- Preferably use systems implying more than 2 users for a joint transaction.


Potential Attacks

Fingerprinting

The idea here is that Link Probability Matrices can be used as a fingerprint of transactions.

Example:
Here are 2 coinjoin transactions built with DarkWallet
- https://oxt.me/transaction/8e56317360a548e8ef28ec475878ef70d1371bee3526c017ac22ad61ae5740b8
- hhttps://oxt.me/transaction/812bee538bd24d03af7876a77c989b2c236c063a5803c720769fc55222d36b47

When inputs and outputs are ordered by increasing amounts, these 2 transactions have an identical LPM:
  | 1.          0.33333333 |
  | 0.33333333  1.         |
  | 0.66666667  0.66666667 |
  | 0.66666667  0.66666667 |

For now, it's not clear to me if this kind of fingerprinting can be used to discriminate between several coinjoin implementations.
That may be a good subject of research for the future.


Deanonymization of Coinjoin Transactions

This one is an idea which has been on my mind for months. The goal is to infer links between inputs & outputs of chained conjoin transactions.
I think the theoretical idea is sound but its practical use against real transactions remains to be tested.

The main consequence of this attack is that one round of coinjoin is not enough.
Don't get me wrong. I don't mean that 2, 3, ... rounds are better. I mean that 1 round of coinjoin is like no coinjoin at all.

Consequences for several rounds remain to be studied. If the attack is proven to be successful, consequences might be worse for some coinjoin services.


References

(1): K.Atlas - Coinjoin Sudoku (http://www.coinjoinsudoku.com/)
	Context

	This third part is about known and potential attacks against the privacy provided by tools like coinjoin.


	Known attacks & weaknesses

	- Linkability of inputs and outputs

	A good illustration of this attack is Coinjoin Sudoku (see (1) for details).
	Coinjoin Sudoku tries to detect flaws in the mixing algorithm by considering the transaction alone (it computes the intrinsic values of the metrics).
	It is worth noting this kind of attack can be repeated over time by computing actual values whenever new side-channel information are gathered (address clustering, ...).


	- Inputs merging

	Coinjoin Sudoku can also be used to cluster addresses associated to several inputs.
	The principle is: if several inputs are deterministically linked to a same output, addresses associated to these inputs can be clustered together.

	Let's note that detection of deterministic links is a strong constraint which can be relaxed.
	A probabilistic approach is sometimes enough to detect inputs which are likely to be controlled by a same entity.

	Example:
	This transaction (https://oxt.me/transaction/7d588d52d1cece7a18d663c977d6143016b5b326404bbf286bc024d5d54fcecb) is a coinjoin with 4 participants and a "coinjoined amount" of 0.84077613 BTC.
	There's 5 inputs which leads us to think that 2 inputs are controlled by a same participant.
	The natural next step is to find the inputs with amount < coinjoined amount (inputs 4 and 5).
	In this specific case, it seems reasonable to infer these 2 inputs are controlled by a same entity.

	Notes:
	- inputs 4 & 5 have identical link probability vectors
	- the severity of these leaks depend on the specific context of the coinjoin transaction (1 round vs several rounds, ...)


	- "Hell is other people"

	A "weakness" of joint transactions is their reliance to multiple participants.
	The main consequence is that your actual privacy relies on your best practices but it also relies on the best practices of other participants.

	A classic example of this point is a joint transaction with 2 participants:

	i1: UserA 1btc -- -- o1: 0.8btc UserA (coinjoined output)
	\ T1 /-- o2: 0.2btc UserA (change output)
	\|-------\|
	/ \-- o3: 0.8btc UserB (coinjoined output)
	i2: UserB 2btc -- -- o4: 1.2btc UserB (change output)

	Let's say that UserB uses strong privacy policies but UserA lacks of practice.

	Further in time:
	- at time t1: UserA pays 0.7btc with the coinjoined output and gets a change of 0.1btc
	- at time t2: UserA pays 0.25btc by merging the change of its payment and the change of the coinjoin.

	As a direct consequence:
	- o1 and o2 are deterministically linked to i1
	- o3 and o4 are deterministically linked to i2 => UserB has lost the protection provided by the coinjoin transaction without any action done !

	Rules:
	- Use several rounds of coinjoin transactions to decrease this risk,
	- Preferably use systems implying more than 2 users for a joint transaction.



	Potential Attacks

	Fingerprinting

	The idea here is that Link Probability Matrices can be used as a fingerprint of transactions.

	Example:
	Here are 2 coinjoin transactions built with DarkWallet
	- https://oxt.me/transaction/8e56317360a548e8ef28ec475878ef70d1371bee3526c017ac22ad61ae5740b8
	- hhttps://oxt.me/transaction/812bee538bd24d03af7876a77c989b2c236c063a5803c720769fc55222d36b47

	When inputs and outputs are ordered by increasing amounts, these 2 transactions have an identical LPM:
	\| 1. 0.33333333 \|
	\| 0.33333333 1. \|
	\| 0.66666667 0.66666667 \|
	\| 0.66666667 0.66666667 \|

	For now, it's not clear to me if this kind of fingerprinting can be used to discriminate between several coinjoin implementations.
	That may be a good subject of research for the future.


	Deanonymization of Coinjoin Transactions

	This one is an idea which has been on my mind for months. The goal is to infer links between inputs & outputs of chained conjoin transactions.
	I think the theoretical idea is sound but its practical use against real transactions remains to be tested.

	The main consequence of this attack is that one round of coinjoin is not enough.
	Don't get me wrong. I don't mean that 2, 3, ... rounds are better. I mean that 1 round of coinjoin is like no coinjoin at all.

	Consequences for several rounds remain to be studied. If the attack is proven to be successful, consequences might be worse for some coinjoin services.


	References

	(1): K.Atlas - Coinjoin Sudoku (http://www.coinjoinsudoku.com/)