[aston]

Say you were a shady Bitcoin banker with 5000 BTC in deposits, and you wanted to steal 1000 while still looking like you're on the up-and-up by implementing this idea.

First, you announce that you only have 4000 BTC in deposits. Then you build this tree, and at the very bottom layer you add a node with a -1000 balance. You pair that node with your (or a conspirator's) real node holding more than 1000 so that any node above yours (read: everyone else) sees a positive balance at every point in the tree. Everyone can verify they're in the tree, the numbers add up to what you claimed publicly, but you're now successfully running a fractional reserve! And the only way to uncover such a scheme would be to publish all of the balances for every account.

Am I missing something?

Edit for clarity: the node you pair with is your own, so that no real user sees the negative sum.

[vbuterin]

Suppose the balance sheet is:

    [ -1000, 1000, 2000, 2000 ]

The Merkle tree is:

    [ -1000, 1000, 2000, 2000 ]
    [ 0, 4000 ]
    [ 4000 ]

You actually owe 5000 BTC, but it seems like you owe 4000 BTC. Seems so far so good. The problem is, what happens if you try to take advantage of this opportunity.

Case 1: other people withdraw first.

    [ -1000, 1000, 0, 0 ]
    [ 0, 0 ]
    [ 0 ]

Nobody knows that anything nefarious has gone on. However, everyone else has successfully gotten their money out so you've actually defrauded no one.

Case 2: you withdraw first.

    [ -1000, 0, 2000, 2000 ]
    [ -1000, 4000 ]
    [ 3000 ]

Now, the other 2 users actually can see that something is wrong, because the Merkle branch will have a -1000 BTC node sticking out.

So in theory, as long as there exist users who don't check their Merkle branches, and those users are identifiable, it probably is possible to run a slight fractional reserve undetected. So the protocol is suboptimal. But it's not really "broken". I do wonder if it can be improved though, perhaps with some kind of ZKP protocol.

[nullc]

Oh sure, you can sum and compare the balances under ZKP and even hide the total amount. But the problem is that as soon as you invoke a ZKP for general computation you take into the realm of barely practical moon math.

... And you still don't fix the problem that balances which are unchecked can be diverted.

In the IRC log I posted I went on to suggest that a service could have a rule that _permitted_ them to take your balance if you don't check it periodically— e.g. they could just withdraw it into their own pocket. You could prove you checked it (or that you tried and they wouldn't let you). By doing so you'd actually create a real incentive for people to check, though I suspect boobytrapped balances wouldn't be very welcome.

Regardless— it still confines the extent of fraud that is possible.

[vbuterin]

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.

[nullc]

> > 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.

[vbuterin]

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.

[nullc]

Go read that IRC log. :)

[tlrobinson]

Discussed here: https://news.ycombinator.com/item?id=7278325