Bitcoin Transactions & Privacy (part 2)

gistfile1.txt

Context

In part 1 of this document, we've defined the entropy of a transaction.
This metric is a first good proxy to qualify the degree of privacy provided by a transaction but it fails to detect privacy leaks occuring at lower levels (1).
In this second part, we define 2 complementary fine-grained tools/metrics: the Link Probability of 2 utxos (LP) and the Link Probability Matrix (LPM) of a transaction.


Link Probability of 2 UTXOs

We call Link Probability of a tuple (tx input, tx output) the probability that a link exists between the 2 utxos.

Link Probability is defined by:

  LP(i,o,tx) = #CombinationsWithLink(i,o) / #Combinations(tx)

with:
  tx: a bitcoin transaction
  i: an input from Tx
  o: an output from Tx
  #Combinations(tx): Total number of combinations associated to tx (see part 1)
  #CombinationsWithLink(i,o): Number of combinations of tx with a link between i and o



Link Probability Matrix of a transaction

We call Link Probability Matrix of a transaction tx, a matrix defined by:

  LPM[m,n] = LP(I[n], O[m], tx)

with:
  tx: a bitcoin transaction
  I: ordered list of tx inputs
  O: ordered list of tx outputs



Observations

- Computation of these 2 metrics (LP & LPM) can be integrated in the algorithm used to computed the entropy of a transaction

- Detection of deterministic links (Coinjoin Sudoku) is computationally cheaper than computing LP or LPM (smaller problem space).

- Like the Entropy of transactions, these 2 metrics can be declined in several variants: Intrinsic, Actual, ...

- The concept of LP and LPM may be extended beyond a single transaction and applied to:

    - a sequence of transactions [TX_1, TX_2, ..., TX_J]
      with:
        TX_j: jth transaction of the sequence
        I: ordered list of TX_1 inputs
        O: ordered list of TX_J outputs

    - a transactions tree [TX_1_1, TX_2_1, ..., TX_J_1, TX_J_K]
      with:
	TXj_k: kth transaction at level j
        I: ordered list of TX_1_1 inputs
        O: ordered list of transaction outputs at level J

    - a connected graph of transactions [TX_1_1, TX_1_2, ..., TX_J_1, TX_J_K]
      with:
	TXj_k: kth transaction at level j
        I: ordered list of transaction inputs at level 1
        O: ordered list of transaction outputs at level J

    - a set of multiple connected graphs of transactions.
      A typical use case is the study of a bitcoin mixer as done by M.Moser (2).
      It requires additional information provided by external heuristics or side-channel sources.
      Introducing these informations is akin to define links between utxos not explicitly stored in the blockchain.

- LPM may be useful to determine the quality of a joint transaction.
  From my observations, beyond the individual LP values composing the matrix, the homogeneity of LP values for a given input (output) might be an additional indicator of the privacy provided by a transaction.
  It may be especially true for the Actual declination of the metric which might help to measure how much the privacy provided by the transaction is damaged by the subsequent transactions.
  
- LPM may also find some use as a fingerprint of transactions (see part 3). To be confirmed.



Implementation

Computation of LP & LPM is integrated in the algorithm used to compute the entropy of transactions (see part 1).
Moreover, an option allows to limit the process to the detection of deterministic links.


(1): K.Atlas - Coinjoin Sudoku (http://www.coinjoinsudoku.com/)
(2): M.Moser - Anonymity of Bitcoin Transactions (https://www.wi.uni-muenster.de/sites/default/files/public/department/itsecurity/mbc13/mbc13-moeser-paper.pdf)