Bitcoin Transactions & Privacy (part 1)

gistfile1.txt

This document is an attempt to define metrics quantifying the degree of privacy provided by a bitcoin transaction.


Objectives

Definition of metrics measuring the resistance of a transaction to a set of attacks against users privacy.

Attacks considered in the scope of these metrics are:
- Merged Inputs Heuristic: methods identifying the inputs controlled by a same entity
- Coinjoin Sudoku: methods identifying the links existing between the inputs and outputs of a transaction 

These metrics can be applied to all bitcoin transactions but are specifically useful for qualifying the "quality" of joint transactions (CoinJoin, SharedCoin, ...).



Entropy of a Transaction

The idea of this metric comes from a discussion with Greg Maxwell (1).
He was suggesting a notion of "Coinjoin Entropy" measuring how many possible mappings of inputs to outputs are possible given the values of the txos.

Considering that the number of combinations may be very high (b/o the combinatorial explosion created by coinjoin transactions) it's wise to define the notion of entropy: 

E = log2(N)

with:
E = entropy of the transaction
N = number of combinations (mappings of inputs to outputs)

Basically, it's the Shannon Entropy with the hypothesis that all events have the same probability (i.e. no additional information giving a "preference" to specific combinations).



Examples

Example 1: Basic Payment Transaction
* https://oxt.me/transaction/dcba20fdfe34fe240fa6eacccfb2e58468ba2feafcfff99706145800d09a09a6
* N = 1
* E = 0
* The unique interpretation is: [(I1,I2,I3,I4,I5,I6)=>(O1,O2)]


Example 2: Ambiguous Transaction
* https://oxt.me/transaction/8c5feb901f3983b0f28d996f9606d895d75136dbe8d77ed1d6c7340a403a73bf
* N = 2
* E = 1
* Interpretations are:
  - [(I1)=>(O2), (I2)=>(O1)]
  - [(I1,I2)=>(O1,O2)]


Example 3: Basic Coinjoin Transaction (DarkWallet)
* https://oxt.me/transaction/8e56317360a548e8ef28ec475878ef70d1371bee3526c017ac22ad61ae5740b8
* N = 3
* E = 1.585
* Interpretations are:
  - [(I1)=>(O1,O2), (I2)=>(O3,O4)]
  - [(I1)=>(O3,O2), (I2)=>(O1,O4)]
  - [(I1,I2)=>(O1,O2,O3,O4)]
* Note: 
  O2 and O4 are the change outputs of the coinjoin transaction.
  For all combinations we have I1=>O2 and I2=>O4. 
  We say that I1 is deterministically linked to O2 and I2 is deterministically linked to O4.




Observations

- Computation of the metric becomes quickly expensive when privacy tools like coinjoin are used to build the transaction (no surprise here).

- It's possible to decrease the computational cost thanks to side-channel information allowing to reduce the size of the problem space (e.g. inputs controlled by a same entity can be merged in a single input).
  For example, these information can be provided by any heuristic allowing to cluster addresses (merged inputs, change address, ...).
	
- From this notion of Entropy, we can derive several metrics qualifying a transaction:
  - Intrinsic Entropy: it's the value computed without any additional information, when the transaction is considered separately from the blockchain.
  - Actual Entropy: it's the value taking into account additional information. On my hand I've worked on this one because I think it's the one which matters the most to users.
  - Max Entropy: it's the value associated to a perfect coinjoin transaction having a structure similar or close to the evaluated transaction.
    A perfect coinjoin is a coinjoin with all inputs having the same amount and all outputs having the same amount.
    Here, we call structure the tuple (#inputs, #outputs)
		 
    Per se, Max Entropy isn't very interesting but it becomes much more useful when used to compute the following ratios:

  	Wallet efficiency = Intrinsic Entropy - Max Entropy (expressed in bits)
	  This metrics may be a proxy for qualifying the efficiency of a wallet when it builds a coinjoin transaction.
	  Wallet efficiency can also be expressed as a ratio: IntrinsicNumberOfCombinations(tx) / NumberOfCombinations(closest perfect coinjoin).

	Blockchain efficiency = Actual Entropy - Max Entropy (expressed in bits)
	  This metrics may be a proxy for qualifying the efficiency of the whole ledger/ecosystem in term of protection of users privacy.
	  Blockchain efficiency can also be expressed as a ratio: ActualNumberOfCombinations(tx) / NumberOfCombinations(closest perfect coinjoin) 

- Rule: Actual entropy of a bitcoin transaction is a dynamic value susceptible to decline over time. At best, it will stay constant. It will never increase.



Limitations

- This metric is susceptible to be tricked by specific patterns of transactions like steganographic transactions.
  A steganographic transaction aims to hide the real payment inside a "fake" payment.
  Its fingerprint is similar to a classic payment but it differs from a classic payment by involving the payee in the payment process.
  
  Example: UserA must pay 1.5btc to UserB. UserB (the payee) collaborates to the process by providing an input.
		
  UserA 2btc --           -- 0.5btc UserA (change)
	       \    T1   /
		|-------|	
	       /         \
  UserB 1btc --           -- 2.5btc UserB

  This transaction is indistinguishable from a classic payment (User1 provides 2 inputs. 1 output goes to the payee, 1 output is change).
  According to our previous definition, we have E(T1)=0 instead of E(T1)=1 (i.e. classic payment + steganograhic transaction)


- This metric is a first good proxy for measuring privacy at transaction level. A transaction with a high entropy is likely to provide better privacy to the users. 
  But, as illustrated by the "Coinjoin Sudoku" attack (2), this metric fails to detect privacy leaks occuring at the lower level of specific inputs/outputs.
  Therefore, this metric shall be completed by additional metrics (see part 2)



Implementation

I've developed a python implementation of an algorithm computing this metric.
This implementation surely deserves the title of "worst possible solution": brute force algorithm, no parallelization, no optimization of the algorithm (memoization), ...
The unique optimization used by this implementation is a reduction of the problem space thanks to information provided by external heuristics.
As a direct consequence of this brute force approach, processing is limited to the most simple transactions (with #inputs <= 10 & #outputs <= 10).
Anyway, I was confident this implementation might crunch a good portion of the bitcoin ledger (60-70% of the transactions) so I've decided to keep it for a first round of tests.



Tests & Results

- Processing of transactions from block 1 to block 388602 (December 2015)

- #Txs (Total)     		= 97,977,912 (100,00%)
- #Txs with entropy computed    = 96,597,663 ( 98,59%)
- #Txs not processed 		=  1,380,249 (  1,41%)

TBH, I wasn't expecting such a large coverage ratio for this first round. I'm not sure it's great news for privacy.


Analysis of the unprocessed transactions

It's almost certain that a subset of these transactions is composed of true Coinjoin/SharedCoin transactions. 
But it's also likely that another part is composed of large transactions with low entropy (classic payments with a large number of inputs and 2 outputs, ...).
A better/smarter implementation may allow the refinement of these results. To be done...


Analysis of the transactions processed

Cumulative distribution of txs per #combinations (loglog scale): http://i.imgur.com/jms8tpi.png
This distribution measures the probability of a transaction with #combinations >= value

Cumulative distribution of txs per entropy (linlog scale): http://i.imgur.com/NlLBL5W.png
This distribution measures the probability of a transaction with entropy >= value

Around 85.47% of the transactions processed have a null entropy (i.e. they have inputs & outputs deterministically linked)
Around 14.52% of the transactions processed have E(tx) >= 1 (i.e. they're as good or better than "ambiguous" transactions)
Around 1.89% of the transactions processed have E(tx) >= 1.585 (i.e. they're as good or better than the most basic coinjoin transactions)

In best case scenario, we may have around 3.3% of the transactions with an entropy greater or equal to the entropy of a basic coinjoin but it's likely that the real value is somewhere between 2% and 3%.
Note that it doesn't imply all these transactions have a coinjoin structure. They just produce higher entropies like coinjoin transactions.


References

(1): G.Maxwell - CoinJoin: Bitcoin privacy for the real world  (https://bitcointalk.org/index.php?topic=279249.msg7117154#msg7117154)
(2): K.Atlas - Coinjoin Sudoku (http://www.coinjoinsudoku.com/)

Wrong example and probably wrong about Shannon naming of the entropy, it's just AFAIK Shannon's intuition was using the logarithm and ended up working in practice, but as I'm trying to look it up, I can see there's much more to this, anyway I won't spend much time on this, as it's less relevant to the conversation. Rather I'd get back to my tailor made example that was wrong and can't help but wondering if it's not that simple to construct such example, then maybe maximizing the subsets could give roughly the same result in practice as the Knapsack way where probabilities between i/o, i/i, o/o and come up with entropy from that.

Anyway, as a side note, the Knapsack paper's goal was to create unequal output mixing and only as a side effect they had to work out a mathematical model on how to score mixes. IMO this spinoff research is more applicable than the original goal itself, as the original goal suffers from lack of further research:

• How to do it trustlessly?
• Is it really more efficient than equal amount mixes across transaction chains?

Regarding the trustlessness aspect I'm not sure if it's even possible as mixing networks rely on standard package sizes in one way or another.
Regarding always creating unequal amounts to maximize Knapsack entropy in a single transaction, it makes sense but does it makes sense when we extend it to transaction chains and compare it with standard amount mixes? Remixes are frequent and creating standard output amounts facilitates mixes on the inputs of the remixes. Thus it may very well be the case where the Knapsack entropy of a tx chain would be ultimately greater with standard amounts than the Knapsack entropy maximizing method on single transaction.

Side note aside, what would be the Knapsack entropy anyway?

With Knapsack we can calculate the probabilities of links, but from there we have to get to entropy somehow.

1. Maybe the most obvious improvement would be that those links would be weighed by amounts as a 30% probable link between 1BTC and 100BTC isn't equivalent to a 30% link between 1BTC and 2BTC.
2. Then maybe we could say that the total volume of a mix would be 1, instead of 47.5BTC so we can compare different mixes regardless the volume.
3. Finally add them together?

Example. So for tx 1, 2 -> 1, 1, 1 we would get the following:

Sub mappings:
1,2 -> 1,1,1
1 -> 1 | 2 -> 1,1
1 -> 1 | 2 -> 1,1
1 -> 1 | 2 -> 1,1

Input match probabilities:
1 - inputs: 2(0.25) | outputs: 1(0.5) 1(0.5) 1(0.5)
2 - inputs: 1(0.25) | outputs: 1(0.75) 1(0.75) 1(0.75)

Output match probabilities:
1 - outputs: 1(0.5) 1(0.5) | inputs: 1(0.5) 2(0.75)
1 - outputs: 1(0.5) 1(0.5) | inputs: 1(0.5) 2(0.75)
1 - outputs: 1(0.5) 1(0.5) | inputs: 1(0.5) 2(0.75)

This is how far Knapsack goes. Next thing could be to normalize the amounts to 1 based on the total volume for comparisions between transactions, which is 3BTC, so then the amounts would be 1/3, 2/3 -> 1/3, 1/3, 1/3.

And then maybe add the amounts together and multiply them with the link probabilities?

• 1BTC input links to other inputs and outputs: (1/3 + 2/3) * 0.25 + (1/3 + 1/3) * 0.5 + (1/3 + 1/3) * 0.5 + (1/3 + 1/3) * 0.5
• 2BTC input links to other inputs and outputs: (2/3 + 1/3) * 0.25 + (2/3 + 1/3) * 0.75 + (2/3 + 1/3) * 0.75 + (2/3 + 1/3) * 0.75
• 3 times 1BTC output links to other outputs: 3 * ((1/3 + 1/3) * 0.5 + (1/3 + 1/3) * 0.5)

The result of this would be 5.75 = (1/3 + 2/3) * 0.25 + (1/3 + 1/3) * 0.5 + (1/3 + 1/3) * 0.5 + (1/3 + 1/3) * 0.5 + (2/3 + 1/3) * 0.25 + (2/3 + 1/3) * 0.75 + (2/3 + 1/3) * 0.75 + (2/3 + 1/3) * 0.75 + 3 * ((1/3 + 1/3) * 0.5 + (1/3 + 1/3) * 0.5).

And the Boltzmann (not Shannon, I hope I name it properly now) entropy for 3 interpretations would be 1.58.

I'm far from sure my calculations are correct, but it communicates the idea. Is this how entropy based on link probabilities should be calculated? Or there's a better way to do it?