Bitcoin Transactions & Privacy (part 2)
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment