Is there are written code for mapping public address to an user?

Question

I read about 2 theoretical ways we can do it

1) When a single transaction has multiple input addresses, we can assume that those addresses belong to the same wallet, thus to the same user. We should bear in mind that users do not share private keys. In fact many users may use web wallets which have pools, so those services will be treated as a single user.

2) Secondly, you can exploit the change mechanism in transactions. The entire value of unspent output should be sent back to the user as change. Bitcoin, in order to improve anonymity, produces a shadow address which collects back the change that results from any transaction. So when a single transaction has 2 outputs, you have to predict which one of the output addresses is actually belonging to the same user that initiated the transaction. If one of those two outputs has never appeared before in the blockchain, while the other has, then we can assume that the one that never appeared before is the shadow address.

But is there any public code available which is able to achieve this in an optimum and optimise algorithm, I wrote an algorithm but its O(n^2), and the dataset currently is just too huge for such algo to work.

Answer 1

You can write both of those queries in a way that takes nearly linear time and space.

1. Make a hash table that maps addresses to "neighbor addresses." A neighbor address is an address that was used as an input alongside another address. To find the addresses a user owns, query the hash table for the address. Add all of the addresses that are neighbors of that address. Recurse for all of the neighbors.

   This can be created in O(n*k) time and space. (n = number of transactions, k = average number of inputs from distinct addresses per transaction)

2. Make a hash table that maps addresses to the block they were first seen in. For each address of each transaction, you check the hash table to see if it has been seen yet. If not, you create an entry for it, pointing to the current block and transaction. Then, while querying, you can quickly tell if a transaction contains addresses that have been seen for the first time.

   This can be created in O(n) time and space. (n = number of inputs)

(It doesn't need to be a hash table specifically. Other approaches would work too.)