Gmaxwell's “prove how (non)-fractional your Bitcoin reserves are” scheme
iwilcox.me.uk
iwilcox.me.uk
"I think that as a community we should start demanding these services continually prove that they are not fractional reserve. We cannot effectively eliminate the need for trust in these sorts of services, but we can certainly confine the exposure and eliminate a lot of this drama. With Bitcoin it's technically possible to prove an entity controls enough coin to cover its obligations— and even to do so in ways that don't leak other business information, and so we should. But this isn't something specific about MTGox, it's something we should demand from all services holding large amounts of third party Bitcoins. I wouldn't even suggest MTGox should do it first, rather— it sounds like a great move for their competition to differentiate themselves."
Here's the takeaway:
"This would leak the total holdings, and some small amount of data about the number of accounts and distribution of their funds, but far far less than all the account balances. Importantly, though— it could be implemented in a few hundred lines of python."
In case anyone from Coinbase is reading: you have a unique opportunity to be the first webwallet service to implement this, and thereby make the entire bitcoin community instantly fall in love with you. It would also set a minimum standard of quality for webwallet services in general, which would add a lot of value to the bitcoin ecosystem. It seems like this might be a pretty big business opportunity.
This guy seems to be everywhere! He's a prolific Wikipedia contributor (administrator + many thousands of edits), and was also the guy behind the dump of a ton of pre-1923 JSTOR documents to the Pirate Bay, which in part helped pressure JSTOR to un-paywall its old/PD articles (http://arstechnica.com/tech-policy/2011/07/swartz-supporter-...).
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.
[ -1000, 1000, 2000, 2000 ]
[ -1000, 1000, 2000, 2000 ]
[ 0, 4000 ]
[ 4000 ]
Case 1: other people withdraw first.
[ -1000, 1000, 0, 0 ]
[ 0, 0 ]
[ 0 ]
Case 2: you withdraw first.
[ -1000, 0, 2000, 2000 ]
[ -1000, 4000 ]
[ 3000 ]
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.
... 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.
> 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.
> 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.
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.
In that discussion we applied a merkel-sum tree data-structure— a pet datastructure that I'd previously proposed for making compact proofs of blockchain invalidity in Bitcoin (in order to make a future bitcoin world where no one runs full nodes safe from inflation and theft by miners)— to PT's bank fraud proofing application.
You may find the log interesting: https://people.xiph.org/~greg/bitcoin-wizards-fraud-proof.lo...
Search for "auditable off-chain transactions" and "Merkle-sum-tree"
(I left in a lot of unrelated stuff since it makes the meandering conversation make a bit more sense. Though a lot of this continues a long running dialog about cryptographic-wankery that has been going on for years)
Ultimately these schemes require the use of a jamming free broadcast network of some kind... otherwise they run into the same problems certificate transparency has where you can substitute the commitment on the fly. Fortunately, Bitcoin provides a global consensus mechanism which could be used to directly attach the commitment to the coins being spoken for.
My email is in my profile, and I'm happy to Skype chat with anyone who wants to help.
I'll flesh it out a bit better tomorrow.
While systems like that have many applications— and should be used where they can, they aren't a replacement for large scale markets like MTGox or for ultra-low-cost instant payment systems.
What happens as businesses (overstock, etc) start accepting bitcoin? Will bitcoin never be able to handle to volume of an amazon or walmart?
The same applies to overstock, coinbase is doing their transaction processing and it's likely most of those are off chain as well as coinbase is a broker and has plenty of coin and dollars in house and is likely where purchasers in the US got their coin anyway as well is also likely being the users online wallet; they settle up daily with an exchange to keep their supply at necessary levels.
Bitcoin isn't ready for mass adoption yet; the infrastructure is still being put into place and the 7 transaction limit has to be removed and exceeded by quite a bit to grow the point of being able to handle large volume kind of stuff. In the meantime, and probably even after, off chain transactions will likely be how most scale is achieved.
https://blockchain.info/charts/n-transactions-per-block
Lots of other interesting charts there. In any case, it doesn't really matter as to the main point that exchanges don't do on block trading, the volume would be far too great for what the network can handle.
You also must make sure that all customers are seeing the same root, and that you can't do funny business like constantly update it to swap out which customers you're robbing. (e.g. it should be a daily or weekly updated thing).
As for the negative values, I wasn't thinking of robbing anyone, but just pretending you are solvent when really you're not. I'm not sure I see what you mean by "swap out which customers you're robbing", could you expand?
When customer A logs in you give them one root and show them their balance (and B has a balance of 0). When customer B logs in— oops balances just update— you show them a new root, and in that one B has a balance of 100.
So you need to pin the commitments strongly enough so that the prover can't swap them out at will.
Of course, if many people were connected at the same time, this would quickly become perilous gymnastics for the exchange.
Though it could be a good way for new/small exchanges to differentiate themselves and gain trust of the community, which could force larger and larger exchanges to do the same until it's common practice (as mentioned has happened with provably-fair gambling sites)
What kinds of terms people choose to transact under is their own business— but all the better when we can be more confident those terms are being followed.
I have no idea whether this is a good idea or if it would work as a business.
In the alternative scenario, economists describe loaning from demand deposits (at a higher interest rate) with a phrase like "the bank is selling liquidity".
Fractional Reserve banks enable you to have your money and be loaned out at the same time(thereby stretching the money supply like an elastic rubber band).
Full Reserve banks ONLY loan out money which was specifically deposited to them for the purposes of being able to be loaned out.
Banks can still make loans simply by offering certificates of deposit. This is the above-board way of loaning out people's money -- you make it absolutely clear that taking it out early has a cost, because the money is locked up in (hopefully) profitable ventures.
Would that be less profitable for the banks? Not really -- they would just adjust their prices to compensate, by charging fees on idle money that's instantly redeemable.
And if you let a secondary market for CDs flower, customers can still get good liquidity. Just in a way that's better subject to market discipline.
That doesn't really sound like a better alternative.
You do realize that modern finance depends on this notion?
For example, Banks need no more than 10% of a loan as cash on hand.
Modern finance also causes some very serious societal problems, in my opinion.
And arguably, the invention of dual-entry accounting in the early Renaissance -- a self-auditing system similar in many ways to nullc's proposal -- played a much bigger part in the beginning of modern economic development than did fractional reserve banking.
I'm just sayin', theory is nice and all, but examples from real practice are more interesting. Fractional reserve banking has been widely in use for hundreds of years in countries which have prospered far more than the general run of humanity has. Show me a capitalist economy that (1) outlawed fractional reserve banking and (2) functions better in some tangible way than the rest of the developed world, and you've got an argument more compelling than a chapter from a textbook of Austrian economics.
>and you've got an argument more compelling than a chapter from a textbook of Austrian economics.
Another ad hominem.
And you didn't even address my point about double-entry accounting, which shares a striking similarity in some ways to this proposal. Way to mount an effective argument.
I've been using http://coinmkt.com
I regrettably used MtGox.com. I'm kicking myself now.
I've tried coinmkt but I don't like it. Their fees aren't great their deposit and withdrawal methods are limited and there are fees on deposits and withdrawals at least there were when I gave it a try.
I'd say Bitstamp has a very good track record, and what's wrong with Slovenia? It's probably about on the level of the Czech Republic in terms of economic freedom, development, level of corruption (relatively low), output, business practices, etc. Would doing business with a Czech company make you nervous?
In business culture, Slovenia looks toward Germany more than toward the former Eastern Block (of which it was never a part).
I mean, Bitstamp's owners are public people. I feel pretty confident that they're not going to run off with their depositors money. Is there something else that you're concerned about?
But I agree, if you want to just buy coins, Coinbase is a good start. And Kraken is looking very good, too, particularly if you're a serious trader (that's who they appear to target).
I thought the "locale" comment was about Slovenia, a country that not many people are informed about and unfairly associate with former Eastern Block crime syndicates.
And yes, the international wire fees do add up. Do any U.S. exchanges currency offer ACH?
Anyway, best bet is to use several exchanges to take advantage of arbitrage opportunities and to distribute the risk.
If you quickly transfer in, exchange, and transfer out you don't need quite as much trust.
Why is this? Seriously, that alone could prevent so much fraud and misuse of funds. Every public company could have a digitally-signed bank balance, updated in real time.
You could use it to show that USD obligations jive with third party audits, insurance, or accounts in a bank if you could get the bank to produce signed attestations... though the trust isn't eliminated there, just shuffled around.
already pleading it to brazilian exchanges.