How do we know that a user owns multiple private keys?

Question

I am reading a data analysis paper on bitcoin, and there is a phrase I do not get:

We use the Bitcoin transaction data set obtained from Stanford Network Analysis Project. All Bitcoin transactions are documented in a public ledger and are in the currency unit called the Bitcoin(BTC). The data set contains all Bitcoin transactions beginning from the network’s creation until April 7th, 2013. For each transaction, there can be multiple sender and receiver addresses. Furthermore, multiple addresses can belong to a single user.

I do not get this last sentence. Yes, surely a user can create multiple private keys. However, how do we know that a user created multiplie private keys if we are not that user?

The dataset given in this paper is very large (6,336,769 users), so they must apply some algorithm to group private keys belonging to each user. What it would be?

Answer 1

There are multiple articles available in internet which contain that paragraph. For example: http://cs229.stanford.edu/proj2014..., https://arxiv.org/pdf/1611.03942.pdf, etc

Each one seems to attribute the origin of the data to different sources, but the numbers act as a fingerprint (6,336,769 nodes and 28,143,065 edges), so it can be traced back to a work by Ivan Brugere which seems to have been available in the past, but not now, at compbio.cs.uic.edu, and from which some docs remain at github.

From them he refers to the work "An Analysis of Anonymity in the Bitcoin System" by Fergal Reid and Martin Harrigan:

Suppose U is, at first, incomplete in the sense that each vertex represents a single public-key rather than a user and that each directed edge between a source and a target represents an input-output pair of a single transaction, where the input's public-key corresponds to the source and the output's public-key corresponds to the target. In order to perfect this network, we need to contract each subset of vertices whose corresponding public-keys belong to a single user.

... as noted by Nakamoto: "Some linking is still unavoidable with multi-input transactions, which necessarily reveal that their inputs were owned by the same owner. The risk is that if the owner of a key is revealed, linking could reveal other transactions that belonged to the same owner."

And closing the argument, in an extensive work covering the same dataset:

Analyzing the Bitcoin Network: The First Four Years - Matthias Lischke and Benjamin Fabian, Institute of Information Systems, Humboldt-Universität zu Berlin, Spandauer Str. 1, 10178 Berlin, Germany (CC BY 4.0):

The user information is organized by the second group of files [...], where a “user” is a grouping of public keys that were used as inputs into a single transaction (user owns the private key to each address) as proposed by Reid and Harrigan. Each line [...] is a grouping of public keys as illustrated in Figure 3:

Answer 2

However, how do we know that a user created multiplie private keys if we are not that user?

We can't. User can create keys using any computation mechanism(pen & paper, abacus, etc.). Protocol is one-party and does not need any third-party(website, server, etc.)

some algorithm to group private keys belonging to each user. What it would be?

Usually, they first apply Union-Find graph algorithms. After they do some analysis at this stage, they assume that in this reduced entity graph, all inputs to a transaction belong to the same entity. This was maybe true early-on in history of bitcoin, but joining coins is pretty common now. Receiver associated with certain senders only are created as self loops etc. The entity graph is kept on reducing, applying transitive, commutative, associative etc. closure on it and studied.

Answer 3

From what i know from what your asking, a person was able have multiple address if they make multiple of it or have a wallet which keeps multiple address in one place.

Answer 4

I will try to answer this, though not sure about the extent of it being held true.

It says:

Furthermore, multiple addresses can belong to a single user.

It says "can" not "must"

Let me say this with an example.

There are say 5 transactions with transaction ID as: trans1, trans2, trans3, trans4 and trans5

The addresses involved are addr1, addr2, addr3, addr4, addr5, addr6 & addr7

Initial Balances:

addr1: 1 BTC

addr2: 2 BTC

addr3: 1 BTC

addr4: 0 BTC

addr5: 0 BTC

addr6: 0 BTC

addr7: 0 BTC

Transactions occured (considering negligible fees):

trans1: addr1 (1BTC) > addr6 (1BTC)

trans2: addr2 (2BTC) > addr5 (2BTC)

trans3: addr3 (1BTC) > addr4 (1BTC)

trans4: addr4 (1BTC) & addr5 (1BTC) > addr7 (2BTC)

trans5: addr5 (1BTC) & addr6 (1BTC) > addr7 (2BTC)

Final Balances:

addr1: 0 BTC

addr2: 0 BTC

addr3: 0 BTC

addr4: 0 BTC

addr5: 0 BTC

addr6: 0 BTC

addr7: 4 BTC

Now considering transaction trans1, trans2 & trans3 to have occured due to some payment settlement. And that gives us no clue whether these receiving addresses are held by a single person or not.

Whereas for the transaction trans4 & trans5 to have occured, the user requires the private key of address addr4, addr5 & addr6. Thus giving us a hint that this "can" (not must) belong to a single person.

Another assuring thing about this belongs to a single person is, these converges to a single address, i.e. addr7. Though this might be someone else, and might be another payment settlement.

Thus, the data analysis paper says:

Furthermore, multiple addresses "can" belong to a single user.