I do understand that for two addresses to be on the same side of a transaction, they must be within the same wallet, since one private key is used to sign a transaction.
However, how is WalletExplorer able to put a name to some of these wallets?
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.Sign up to join this community
What walletexplorer does is called address clustering. When you spend bitcoins, your wallet will take input from several txouts belonging to several addresses depending on amount to be spend. So walletexplorer works on a simple heuristic:
More detail about this method can be seen in this paper by Reid and Harrigan. Of course, this method will fail in case of mixers and coinjoin transactions. There are advanced ways to even detect transaction that go through mixers, but I don't think wallet explorer does that
To find name of wallets it can scrap forums like bitcointalk, some addresses are tagged publicly in blockchain.info, also it can has bots trade on major exchanges to get their addresses.