One way to defeat the "hide the negative balances inside a subtree of technologically clueless grandmas" attack might be to generate the tree using some easily verifiable deterministic algorithm (ie. alphabetic order of hashes of some user data), and perhaps even have several trees. It's not perfect, but it could help reduce the problems, although perhaps at the expense of some additional privacy.
> And you still don't fix the problem that balances which are unchecked can be diverted.
Okay, I'll admit I might be missing something here; what do you mean by that? The exchange isn't storing each user's bitcoins separately; that requires one TX per user to maintain anyway. It should be storing them all under a single HD wallet and publicly releasing the MPK, so users can take the MPK and use it to verify that the exchange actually has 5000 BTC, the Merkle root says 5000 BTC, and their Merkle branch is correct. The exchange can't spend "unchecked bitcoins" or "checked bitcoins"; they're all just bitcoins under the same HD wallet, and spending any of them would trigger an alarm.
> > And you still don't fix the problem that balances which are unchecked can be diverted.
> Okay, I'll admit I might be missing something here; what do you mean by that?
Say Alice _never_ logs in anymore and the site has noticed this. The site can just go "oh Alice, her balance in now 0" and go and gamble away those coins— sure, their holdings go down, but so do their obligations. Since Alice never logs in anyone, she's not going to protest that her coins are all gone.
Ah okay, that makes sense. You're completely right that that's not really solvable in general.
Unless, of course, we finally switch over to a public/private key based login system and each user's balance sheet is composed of a set of authorized/signed deposits, trades and withdrawals (ie. a full blockchain, but centralized and "mined" only by the exchange's server). I wonder what possibilities that kind of setup would open.
> And you still don't fix the problem that balances which are unchecked can be diverted.
Okay, I'll admit I might be missing something here; what do you mean by that? The exchange isn't storing each user's bitcoins separately; that requires one TX per user to maintain anyway. It should be storing them all under a single HD wallet and publicly releasing the MPK, so users can take the MPK and use it to verify that the exchange actually has 5000 BTC, the Merkle root says 5000 BTC, and their Merkle branch is correct. The exchange can't spend "unchecked bitcoins" or "checked bitcoins"; they're all just bitcoins under the same HD wallet, and spending any of them would trigger an alarm.