Procedure for calculating taint?

Question

I'd like to understand taint analysis quantitatively. Blockchain.info offers a service that will calculate taint, but I've found no good explanation for how taint is calculated.

The best (and only) explanation I've found so far appears in the paper Anonymity of Bitcoin Transactions:

The taint analysis works by calculating the percentage of the amount of bitcoins that might origin from another address, thus revealing connections in the transaction graph. In the simplified example in Figure 4, A₁ and A₃ would have a taint of 75% and A₂ a taint of 25%. However, it can only detect direct connections in the graph and does not consider any context information.

This explanation is confusing. Taint is measured between two pseudonyms (addresses). It's not a property of a particular pseudonym. The paper seems to be missing the part that says the taint scores for A₁, A₂, and A₃ are relative to A₄. If so, then the scores make sense.

However, it's not clear what would happen for more complex chains of ownership. For example, imagine another pseudonym, A₅ that pays A₁ 5 BTC. What would be the taint score between A₅ and A₄?

I've seen this, but it doesn't discuss how to compute a taint score between two pseudonyms.

What I'd like to see is the outline of a step-by-step procedure for calculating taint, as done by Blockchain.info. If I had to guess, here's how the procedure would look:

1. Find two pseudonyms, S (source) and T (target). Funds flow from S to T.
2. Using the block chain, find a chain of ownership C_i from each coin controlled by S to T.
3. For each chain of ownership C_i, find the lowest valued coin transfer m_i.
4. Sum all m_i, giving m.
5. Sum the value of all outputs received through T, giving s.
6. Taint is defined as m/s.

Using this procedure would give a taint score of 50% between A₅ and A₄ (2 / 4).

Is this correct?

Answer 1

I think I have an answer. It's not clear if this is how blockchain.info does it, but I'm not sure it matters, either.

Taint is very similar to the everyday experience of diluting a liquid.

Imagine starting with three glasses. One glass contains orange juice. The second contains water. The third is empty.

Pouring some or all of the orange juice into the empty glass doesn't dilute it at all. However, pouring a 1:1 mixture of orange juice and water into the empty glass dilutes the orange juice.

We can define a metric called dilution factor. Dilution factor equals the final volume contained in the formerly empty glass divided by the volume of orange juice added. The dilution factor for a 1:1 mixture is therefore 2 (2 / 1). If no dilution takes place, then the dilution factor is 1. More generally:

dilution factor = V₂ / V₁ if V₂ > V₁

dilution factor = 1 if V₂ <= V₁

We can add another empty glass and dilute again. For example, we can take half of the diluted orange juice and dilute it with an equal volume of water. This gives a second dilution factor of 2.

The overall dilution factor equals the cumulative product of the dilution factor at each step. In this case, it is 4 (2 x 2).

Now imagine that monetary value is like a liquid, and an output is like a container. We can do dilution analysis just like we did with orange juice.

In this case, the dilution factor tells us how diluted the value of an output in a chain of ownership has become relative to a downstream output. Provided that the limits of this metric are clear, it can be useful.

The liquid being diluted is "taint". In this model, "taint" would be the multiplicative inverse of dilution factor. A dilution factor of 2 implies a taint of 50% (1/2).

Returning to the question posed above, given this chain of ownership, find the dilution factor between A₅ and A₄:

A₅(5 BTC)->A₁(2 BTC)->A₃(3 BTC)->A₄(4 BTC)

The dilution factors are, from left to right: 1; 3/2; 4/3. Multiplying them together gives 1 x 3/2 x 4/3, or 2. This is a 50% taint, the same answer as I got above.

However, the answer postulated in my original question is wrong in that it doesn't account for serial dilution. Consider this chain of ownership:

A₅(1 BTC)->A₁(5 BTC)->A₃(3 BTC)->A₄(4 BTC)

The serial dilution factor is 5 x 1 x 4/3, or 20/3.

Simply dividing the final value by the minimum value upstream gives a dilution factor between A₅ and A₄ of 4/1.