Yes, I think CoinJoin should be a very good start. But do any really decentralised and fully working implementations of CoinJoin exist already? I don't think so and would be interested to know if they are.
I'm not aware of any either but don't let that deter you from using one of the already existing solutions even if they aren't perfect.
A
decentralized CoinJoin will have difficulty forming transactions (including unequal or equal transaction amounts) that look like this if anyone can join:
https://blockchain.info/tx/e4abb15310348edc606e597effc81697bfce4b6de7598347f17c2befd4febf3b?show_adv=trueA sharedcoin transaction will look something like this:
https://blockchain.info/tx/e4abb15310348edc606e597effc81697bfce4b6de7598347f17c2befd4febf3b (picked at random). As you can see multiple inputs and outputs make the determining the actual sender and receiver more difficult.
The server does not need to keep any logs and transactions are only kept in memory for a short time. However If the server was compromised or under subpoena it could be force...
Because the way it must work is the users sign the transaction first with their requested outputs, then in the second round they sign their payments as inputs to the transaction. If the payment inputs are less than the total, then the transaction is invalid. There is no way to determine who cheated and rate limit them. Thus the saboteur can stomp on every attempt to create a CoinJoin transaction and destroy the decentralized system.
DarkCoin says they can solve this by charging a fee, but you will see I originally proposed that idea in the CoinJoin thread and the requirement is all the participants must be permanently identified and then must use divide-and-conquer to whittle down to who was the saboteur. But identification defeats the mixing!
Thus I have not yet seen a workable decentralized CoinJoin that can scale. And I don't expect one.