Topic: How to determine common ownership of addresses? (Inspired by Shamir's paper) (Read 1969 times)

Under what model?  Under a model that allows you to sniff the keyboards of their creators you can distinguish them.  If I hand you a transaction in isolation, however, you can not distinguish the cases as there is no information to distinguish the cases— a transaction U generated from inputs X and Y paying Z and Q is bitwise identical no matter if was authored by one party or two.

If you propose a model conditioned on other history about X and Y— if there is any, e.g.  if users reused addresses— you might say that it's more or less likely to be one kind or another _but_ you could say that about X and Y no matter if U existed or not, the information did not come from U.

I looked at the threads you initiated and saw a very lively discussion of the points I raised. However, some of the participants take the extreme position that if something can not be measured with complete accuracy, or if all the possible sources of error can not be characterized with their precise statistical distribution, then one should not even try to carry out a scientific research or to draw any conclusions from available data. With such an approach, one would never try to study any sufficiently complex issue. To demonstrate this point, consider the crucial problem of estimating how many poor people live in the US, which can have major consequences on the social policy and budgets of local and federal authorities. As a researcher, you will always have to make some arbitrary choices about where is the poverty line, about your sources of data (if you use tax returns, do you know how many people cheat in their declarations and which types of wealth are not properly measured by these returns? If you use a questionnaire, do you know exactly how truthful are the answers?), about the family unit analyzed (in case someone has no personal income but his close relatives living with him have high salaries), etc etc. If you specify your exact research methodology, explain the possible sources of error, and use best efforts to extract the best possible conclusions from all the available data,  the research can be extremely valuable even when the conclusions do not perfectly match the ground truth.

Indistinguishable under which lens? "Yeah, these all look the same to me" doesn't cut it. Can you prove information-theoretically that no information can be obtained?

You have a bunch of linked addresses which you believe are in a single wallet. You check if the transactions involving these addresses make sense with the coin selection algorithm. If they don't you check which addresses can be unlinked to end up with something that makes more sense.

It does not. Decenteralized mixing and joint payments can produce transactions which are indistinguishable at the transaction level from regular common ownership transactions.

You can't even say much about coin selection behavior without knowing in advance the full content of the wallet,

but the accuracy of this guess depends on access to the ground truth on both sides.

You can ask services what are their volumes. (Some publish them without being asked).

Decentralized mixing (of the kind I know anyway) has a characteristic format, you can try to detect it and filter these transactions for linking addresses.

[sarcasm]Let's all stop doing any research then.[/sarcasm]
We shouldn't take the research for more than what it is, but we want "what it is" to be as good as possible.

They used blockexplorer.com; I don't think discrepancy between their data and the true blockchain is a problem in practice; and this is off-topic for this thread.

[sarcasm]Let's all stop doing any research then.[/sarcasm]
We shouldn't take the research for more than what it is, but we want "what it is" to be as good as possible.

I think people who said they did it wrong aren't expecting them to revise the paper, just to let them know that their research is flawed and will always be.

Heck, they can't even be sure they got the real blockchain instead of a fake one fed to them by whatever site they scraped it from.

The errors from making these assumptions are systemic, not random. It would be a methodological error to treat them as random errors.

You can't even give a distribution over the bias without knowing other difficult or impossible to measure cofounding factors (e.g. amount of decenteralized mixing and joint payment transactions, volume on various services, etc).

I'm not asking for a reliable identification. I'm asking for identification which is as good as possible for the purpose of statistical analysis of the data. This means it should have as little bias and as little variance as possible.

It's weak for reasons other than the ones listed. Coin selection tries to minimize change, so it doesn't tend to link much— especially if you use addresses once and in some clients like armory linking is explicitly avoided.  So you can have a bunch of coins in a common wallet and still not that much linkage— witness their enormous underestimation of instawallet.

What you're asking for— reliable identification of common ownership— is not possible in Bitcoin _by design_ because the pseudoanonymity of the participants is how we achieve any privacy at all, and thats diluted by combining addresses.

Unless you get people to tell you, you can't determine common ownership of addresses.

For the purpose of statistical analysis of the data, what would be the best way to determine common ownership of addresses?

1. While the notions of a bitcoin and of an address are completely clear, the notion of an owner is quite fuzzy since it can not be derived in a precise way from the available data (this may be a feature ofthe scheme, rather than a bug!). There are several ways how to deal with this issue:

1.1 Ignore it completely, and derive from the graph only statistical information about the behavior of addresses. However, we believe that this will completely distort many types of statistical informationwe try to extract from the graph, e.g., what is the distribution of the number of bitcoins that users keep, how many bitcoins they receive and spend, how big are their typical transactions, etc. Since thescheme enables (and even encourages)  users to keep multiple addresses and to constantly shuffle bitcoins internally among their accounts, we believe that it is essential to find a way to distinguish between"internal" and "external" transactions, and thus to determine in some way what is the common ownership of different addresses.

1.2 Use our methodology, which is to assume that in most of the transactions, sending bitcoins from multiple addresses indicates that all these accounts are owned by a single entity. This classification istechnically easy to apply, but it creates two types of errors: We underestimate the common ownership of accounts just because we never saw it in the given transactions, and we overestimate it sinceoccasionally there may be multiple owners who send bitcoins in a single transaction. All the anecdotal evidence we saw so far indicates that overall we tend to underestimate the number of addresseswhich are associated with a single entity (as was demonstrated in the case of Instawallet, in which we found only about 1/3 ot the actual addresses associated with it), and that the errors in the otherdirection, while they exist, are not likely to distort our statistical conclusions in a major way.

1.3 Use a different methodology, which will be closer to the ground truth, and which can be derived either from the available data, or from reliable alternative sources. Here we need your help insuggesting such a methodology, which will be discussed by and accepted by most of the bitcoin community as better representing the issue of common ownership. It is always easier to complain about theshortcomings of one methodology than to suggest a better one!