Table of Contents
A new paper by a prominent group of European blockchain researchers takes a fresh look at a question we have considered before here: how reliable are standard blockchain analysis techniques? The paper presents a fascinating new perspective on the question by considering a range different definitions for "accurate" and then working through the numbers. What they find is that performance varies wildly – from nearly flawless to 0% correct – depending on which of several sensible definitions you adopt and which service you look at.
This paper is groundbreaking for another reason too: all the testing is done using official data collected as part of EU regulatory requirements. So these tests are run entirely on real data, using real government sources for service addresses, and the tests are run on clearly-defined algorithms with carefully-specified definitions. This is excellent.
The study focuses on the well-known co-spend heuristic, referred to in the paper as the "multi-input heuristic" (MIH). As this work was done by academics and the exact details of their implementation are available for inspection we will use MIH to refer to the specific flavour of co-spending used here. There are many minor parameters to fix when implementing co-spending and the major analytics companies have consistently refused to provide their exact algorithms. Here, at least, we can be specific about what is being tested.
And the key finding in the paper is that for many sensible definitions of accuracy, and for many real world services, MIH performs poorly.
To dig in to this result we first need to explain why "accurate" is not a clear word. Only then can we sketch what the various proposed definitions are. And finally we will briefly give our views on this paper's results and make a few legal comments. Generally speaking this work adds to the growing pile of evidence that blockchain analysis as it is practiced today is not like a traditional forensic science at all and should not be treated by legal systems as though it has "forensic" reliability.
Why Accuracy Is Hard to Define
At first glance, judging whether some tool is accurate or not looks easy: measure what fraction of the time it gives the right answer. The problem is that a tool like MIH is used for clustering. And clustering is not a simple test where we can simply mark off right and wrong. Yes it is a "math problem." But the grade school understanding of how to mark a math test is manifestly inadequate for the task at hand.
We will give two simple examples to make clear why "accuracy" is unclear here. But first we have to establish the setup. Imagine you are looking at a large collection of blockchain data but you have no idea what any of the services are. MIH is then some kind of tool to group addresses together into clusters you suspect correspond to individual services. But you do not know, or care, what those services are called. It makes no sense to say "what % of the Binance addresses are correct?" because you have no clue which cluster or clusters correspond to Binance. Your clustering software has never seen the word Binance. It only understands blockchain data.
So now for the first example of what is unclear. You might pick a single Binance address, find which cluster it sits in, and then try to measure accuracy. Already we have a problem. We can measure what % of the addresses in that cluster are Binance. Call that I for "in." Then we can measure what % of Binance addresses sit outside that cluster. Call that O for "out." These two numbers, together, give some measure of accuracy for the Binance clustering. So maybe I and O together capture accuracy? No. If we pick a different starting address for Binance that sits in a different cluster we will get different answers. Already we can see this is hard when accuracy is less than 100%.
When accuracy is 0% or 100% the details of our definition do not matter. But those cases are irrelevant for the real world. We fear part of the problem with assessing blockchain analysis is that many non-technical people doing the analysis do not even understand their own framing is defective. And it is not just "you are asking the wrong question." It is a richer shortcoming: you are expecting a scalar answer (i.e. a single error rate) when any sensible procedure generates a higher dimensional result.
The I vs O pairing further motivates a second idea. Instead of looking at accuracy for a single service. Now try to measure all the services we know about together by asking what fraction of addresses of the same services sit in the same clusters. For all the services at once. Here we are looking at pairs of addresses and asking if they were correctly clustered together or separately. This gives a single number. But if our scheme spreads a single service across dozens of clusters we might find very few or very many pairwise matches depending on the sizes of those clusters. Is it better to have a small number of large clusters none of which maps cleanly to a single service or a large set of small clusters each of which is pure but none of which captures an entire service? Both are bad. This too is hard when accuracy is not 0% or 100%.
A simpler case is where almost all the addresses for a single service fall into a single cluster. Then you get some % of members of that cluster which are wrong and some other % of members which are outside the cluster. If both those numbers are small – and it would not hurt if both those numbers were about the same too – then you can maybe present an error rate based on those observations. But this kind of simple scheme only works when the service exhibits very few errors of all types. Things kind of go from 100% accuracy to 95% accuracy to "yeah this measurement process does not work anymore" as your answer. This is not a usable scheme if it turns out the tools make even relatively small mistakes. And it is clearly wrong to assume the service is very accurate and then use a scheme to measure accuracy that only works when the service is very accurate. If an accuracy test cannot fail it is not an accuracy test.
Some Definitions
The paper presents a range of accuracy definitions. Among these are two accuracy schemes the authors refer to as "per-wallet" and "pairwise" which roughly correspond to the ideas presented above. Per-wallet looks at accuracy address-by-address taking the address with the largest number of members from a given service as that service's cluster. Pairwise does something like what is described above, looking at pairs of addresses and measuring when they are in the same cluster.
For each of these approaches there are four basic statistical measures we can compute: false positive, true positive, false negative and true negative. This is just basic statistics and these raw measures are maybe not the best for analysis. In the paper the authors use, as in common in many applications, precision and recall. For this application precision roughly means "when two addresses are clustered together how often are they really part of the same service?" And recall roughly means "what % of a service's addresses are clustered together as a single service?" Alongside these two measures the paper also looks at the F1 score which is a standard way of averaging precision and recall together to get a single number. So at this point we have six different accuracy definitions.
This study is particularly well designed in that seven services of widely-varying sizes are all tested together. So these measures can be run in aggregate and for each service individually. With a wide range of service sizes we may be able to say things like "MIH works better for large services than small ones" or "performance is highly variable across small services but consistent across large ones" or maybe something else. Experimental design is all about ensuring your experiment is capable of generating interesting conclusions. With six measures across seven clusters, plus the aggregate "all services" cluster, we now have 48 numbers for accuracy.
And in fact the setup goes a bit further. Two more measures of accuracy – the Normalized Mutual Information (NMI) and Adjusted Normalized Mutual (aNMI) Information – are computed for the aggregate "all services" case and something known as the Average Error Rate (AER) is computed for each service and in the aggregate case. The mutual information measures attempt to capture how well a computed set of clusters covers the correct set of clusters. And the AER measures how well a given service is clustered across all the clusters that might correspond to that service. None of these measures is new; all come from the literature in these kinds of statistical methods. It is well known in science that "accurate" is not a precise word for use cases such as these.
In total there are 58 accuracy measures reported in this paper. The lowest is 0% and the highest is 100%. At a high level, then, "it depends."
Results
A range from 0% to 100% accuracy tells us little. We need to dig a bit deeper to learn anything. The first thing to note is that the pairwise accuracy numbers are generally better than the per-wallet numbers. And the per-wallet numbers are only good for the largest cluster. The pairwise statistics are likely dominated by the largest cluster and relatively few addresses being mis-classified as members of that cluster. But even for the largest cluster accuracy was not 100%. And many smaller clusters have near-zero or actual-zero accuracy on some measures. If that is somewhat confusing: fret not. The results are decidedly mixed and messy. The only simple conclusion we can draw from this work is that MIH does not "just work." It fails at a high rate on real data in real tests. Yes, it also works well in some cases. But the very fact that performance varies from "excellent" to "horrible" on real data is proof the thing is nothing like, for example, DNA testing.
MIH does not correctly separate out services into single clusters. Yes, it is able to group together a gigantic service relatively reliably. But you only need a few addresses associated with a smaller service to be incorrectly lumped into the large cluster to decimate accuracy for the smaller service. The study finds a far higher accuracy rate for the largest service when compared to all the others. At a minimum this establishes that performance varies a lot depending on the service you are looking at. It is not safe to assume MIH works. And the paper studies real services. These are real results on real data and MIH is failing a large fraction of the time.
Then we get to the broader clustering measures. NMI, aNMI and AER all give accuracy roughly around 50% when measured across the entire data set. AER ranges from 0% to 100% per-service. None of this is confidence inspiring. Cluster structure, overall, is not reliably recovered by MIH.
Discussion
If all the measures came in above 90%, or between 35% and 50%, or somehow in a narrow range we would be able to say with confidence that MIH has that sort of accuracy. But instead we end up with a lot of caveats. MIH does look reliable for, as an example, identifying that a given unknown address is in fact a member of an existing, known and large service when MIH claims that it is. We find high precision for the pairwise measures both in aggregate and for the large service. So this kind of inclusion clustering is fine. This is entirely consistent with results presented elsewhere. MIH looks to work for a specific use case, on a specific type of service. But that is about it. For everything else it ranges from a coin flip to completely useless.
What if we are trying to determine which addresses are and are not parts of some unknown smaller service? What if we find two addresses that we think are related that get clustered into different clusters? Can we say anything? Not really. The paper describes this issue wonderfully:
Reporting only aggregated pairwise scores can therefore mask extreme heterogeneity across services, reinforcing the need to complement dataset-level reporting with entity-level performance measures.
That is a dry technical way of saying "just because MIH can achieve 95%-99% accuracy on Coinbase and Binance does not mean anyone should trust it for smaller or more obscure services which might behave differently."
This is a real, practical, problem for law enforcement. Why? Because law enforcement rarely if ever needs to rely on blockchain analysis to establish an address is part of a major exchange. If the exchange will respond to law enforcement queries then the exchange can simply confirm it controls the addresses directly. The tool may work for finding leads. Or not. All that matters is the false positive rate is low enough law enforcement is willing to spend time chasing down those leads. Once an exchange confirms they own a given deposit address, and provides the police with the KYC documents, clustering stops being important.
Procedurally it may be necessary to show reliance on clustering was reasonable to initiate the search or ask the exchange or continue some investigation. But that is an extremely low bar in every jurisdiction. The police are generally welcome to waste their own time chasing down pointless leads. Once an exchange confirms they own a given address things change. Proving guilt requires measuring evidence against a higher standard. But the exchange's confirmation of ownership is going to meet that standard. The clustering need not come into it at all.
Clustering only matters when there is no responsive entity to vouch for ownership and control. Those are the situations where a case may rest largely on the reliability of the analytics. And those are also the cases where this paper tells us the analytics are least reliable. The state of the art in research looks to be that MIH should not be used as evidence in court. Why? Because in the cases where it works well something better and more reliable – direct evidence from an exchange or similar – should be available with none of the caveats. And the cases where that corroboration is not available are the cases where MIH is known to be unreliable.
This reframes a number of issues. If someone asserts MIH is being used in a case where we expect it to be reliable: why are they not instead presenting direct evidence from a service provider and bypassing the accuracy debate entirely? If they have such evidence it is far better. If they do not: how do they actually know we are in the reliable situation? And then when MIH is all that we can provide because of the nature of the service, or information, or investigation or whatever: why should we trust the tool in a situation where it is known to be error-prone? Based on the evidence we have today there is no case where MIH should be the best available evidence and presumed to be accurate. There should either be better evidence available or no reason to trust the tool at all. That is today's state of the art.
Blockhead
