They should have third party software performing the Merkle construction once a day lets say. A second "third party program" could verify individuals account holdings (crypto only mind you) by checking hash values. This program would be encrypted and stored on exchange servers by a third party. Then individuals could be assigned personal private keys to decrypt and run the verification software as they please. The private keys could be stored locally on customer devices.
Encrypting and MACing the verification software would ensure the exchange themselves could not alter this software. As long as enough users verified their holdings periodically they might be able to prove the exchange was not holding less coins than that declared by the daily merkle tree.
This is not an audit of course, more like an inventory check. I am I missing something?
We can do much, much better than that.
Exchanges can work together form m-of-n multisig pool in which to store customer deposits, then audit each other continually in real time, provided that they can provide cryptographically secure proof of liabilities.
This arrangement is called a
voting pool.
Proof of solvency alone is pretty much pointless, since a fraudulent exchange can prove solvency right up until they decide to take the bitcoins and run.
The voting pool arrangement means that no exchange can unilaterally refuse to honor withdrawal requests - they have to convince a majority of the exchanges simultaneously.
So once they are deployed we should see a substantial reduction in the amount of exchange fraud, at least on the Bitcoin side (there's no such thing as multisig for USD).