Topic: [ANN] Kraken Passes Cryptographically Verifiable Proof of Reserves Audit (Read 40018 times)

thx Stefan for the Audit


and kraken too - a customer who found back to you again - thx to the trading machine upgrade

Looking into kraken 01-04-2017 found this post url under the audit tab
posting a reminder to lookup other exchanges too
nic

This is truly excellent news... "proof of concept" (exchange solvency) is finally here!

Just the root hash and an opaque proof of computation that asserts the audit code ran on the full (hidden) data.

How should that work for example with Bitcoin balances where messages are signed by private keys? You need to know the pubkeys to verify these messages, and this means you leak all addresses in the process.

They don't have to! Verified computation allows you to reduce it down to a binary yes/no result without revealing the entire balance.

Well when you open an account on exchange you deposit onto an M of N wallet which you use to do transactions. Once deposit is verified the account is active and you can do transaction on exchange virtually, but for each one you authorize the amount from that wallet using the 2 out of 3 key you have.
The trades happens virtually and instantaneously, the real solvency lags behind, but it only noticeable only if you want to withdraw right the way.

Thanks for bringing up negative balances, that's something I should have covered in my audit report. Their tool prints a warning if any negative balances are included and I would have refused the audit at that point.

I think the way forward will definitely be the standards-based approach that you yourself and others are advocating. Just based on the conversation I've had with different exchanges on the subject of audits, I don't think they like publishing their total holdings for a variety of reasons, so it would be nice if the standard specified the best possible procedure under that constraint.

To be clear, by listing those issues above I'm not accusing them of summing incorrectly; I'm just saying there are obvious simple issues that undermine the implementation.  Even once those are addressed, the Merkle approach is not magic crypto fairy dust; it's always been down to the customers to verify their inclusion; but provided they do fix these issues and you do check, you can at least check your data and be certain you're represented.  Even if they'd included other balances in the tree and a sum at the top, you'd have no way to verify any amount anywhere except your own.


It could be summed up as "you can verify for yourself that you're included in what I audited [bar caveats above], then decide for yourself whether you trust me".

I should add to the caveats above: exchanges should investigate ways to deliver partial trees to customers without knowing whether they've been read.  Otherwise an evil exchange has a better chance of identifying accounts which never check, either through being lazy or being dormant; that would let them hide negating balances as neighbours and reduce their liability declaration.  It's not obvious to me from the screenshot and I'm not a Kraken customer, but if clicking "audit" generates a page fetch or anything other traffic to Kraken, that's the worst case.  Ideally you want trees made available to all customers with zero detectable traffic regardless of whether they log in, although besides e-mailing trees out to customers in a monthly zip or something, I haven't really given much thought to the best way to do that.  (E-mailing trees wouldn't be a privacy issue^[1], because a fully stripped-down tree contains nothing but your nonce for your leaf; you add your balance and e-mail/other user-chosen info before hashing.)

To quote Kraken's audit page: "To date, audits produced by the Bitcoin industry have been opaque, superficial" --- I agree (beats the crap out of BTC-e and Bitstamp); their approach isn't ideal (I really wish they'd either make asset proofs independently verifiable or markedly improve their auditing) but it's potentially a significant step forward.  They seem to recognise it's just the start; they do say "We hope to receive feedback from the community that will help us and others to improve this process for future audits."  I think they should be given credit for aiming to make somewhat open, independently verifiable claims, describing some shortcomings and --- provided they actually consider and respond to it --- for soliciting feedback.

[1] Well, unless your mail provider is evil and is actively guessing your balance and probing by hashing all possibilities, but then they're also probably seeing your password reset e-mails and withdrawal confirmations.

Oh, so all they are proving is that they built the accounts into *some* tree structure, which may or may not have summed balances correctly.

This whole thing is just basically a guy saying "trust me bro, i audited them, your funds are there".

They made the decision that an auditor was to be the one to check assets against the liability sum.  Since you can't see their asset sum, their liability sum is not useful to you; only your inclusion in that number (and the elimination of other foul play) matters.  That means their trees and verifier need only hash your sum, not feed it up the tree as all five other implementations do.

However, olalonde and I decided to look more closely at what freedoms the existing code might give them...

Let's assume the auditor checked a fresh copy of the code out of GitHub and built it himself on a known-good machine (we have to assume, because unfortunately he doesn't say).  Fix:state explicitly that you checked hashes, built from source and ran on your own machine.

They've openly made a choice to include accounts with negative balances.  As discussed in the issue I've raised, I think this is a bad idea.  To summarise the points:

• genuine negative balances may often never be repaid, just as a customer who walks out of a bar after getting too much change from a 50 may never come back, so negative balances don't reduce your liabilities
• negative balances may be used for foul play, and it should be made as hard as possible for foul play to go undetected, so negative balances must not become a normal thing (much better to hear from your exchange "our assets only cover 99.8% of our liabilities" than enable cheating)
• users can't distinguish genuine negative balances from real ones, so including them gives no useful information

So while their tool appears to list negative balances explicitly while building the tree from accounts data, we'll also have to assume (because unfortunately, he doesn't say) that any listed negative balances were justified by Kraken and proven to be real users expected to make good, not fake accounts inserted to falsely lower liabilities.  Fix: disallow negative liabilities, as described, specified in a draft standard and implemented elsewhere.  Alternatively, explicitly state what the sum of negative liabilities was and that you were given satisfactory proof that those accounts belonged to real people.

No unique user-chosen information was included in the Merkle tree leaf hash.  That means their tool could group all users with the same balance, give them all the same nonce (which they call the "Submission code" in their documentation), and convince them all that a single entry in the tree represented every one of them.  The subversion possible this way depends on how many customers have identical balances, or balances close enough to not notice.  Because the exchange can deliver nonces after the audit, this is possible even if the auditor is running the exact code published and it's working as expected.  Fix: inclusion of unique user-chosen info (such as e-mail address) in the hash, as described, specified in a draft standard and implemented elsewhere.  (If it's a requirement that auditors don't see this, hash it with the nonce first.)

Edit: linkify "leaf hash"

Edit: add "Because the exchange can deliver nonces after the audit,"

The point of the cryptography is not to make the audit easier for the auditor, it is to make a 3rd party auditor unnecessary. To make it that such that anybody can verify their balances and the availability of funds to cover them, continuously and without need of a 3rd party auditor. You should know that, Stefan.

The technology to do this has been described, even constructions which don't involve public revelation of total holdings (just the boolean yes/no answer to the solvency test). We as a community should be demanding this level of audit-ability from the services that we use, and refusing to use services which do not provide this level of accountability (as well as working towards decentralized, trustless solutions so we no longer need these solutions in the first place).

Isn't this merkle method supposed to include the total number of BTC with the root hash?  Otherwise user verification isn't even a valid proof of liabilities.  So assuming it was done right, what was the total number of BTC kraken have, according to the root hash?

If Kraken's devs care to join in with developing/implementing a standard, then Olivier Lalonde already has one in development.

You can encourage them to join in by commenting on the github issue.

Edit: remove superfluous "already" from "already has one already in development"

Thought I'd chime in! Sorry for not posting earlier, I'm currently in Paris for the W3C Web Payments Workshop, which has meant a pretty busy day yesterday.


Totally understood, please think of this audit as a first step in the right direction.

When I agreed to do the audit, a big factor was Kraken's assurance that they'd be building on it, meaning they'd repeat it with other auditors and further improvements to the audit process. I imagine eventually that will involve professional accountancy firms, audits of fiat accounts and audits covering a span of time as opposed to just a snapshot.

There are already a couple good suggestions for tweaks/improvements for next time in this thread, so I think that you'll see more audits and continuous improvement of the process as we move towards an industry standard.


The point of the cryptography is to make the audit easier for the auditor. It would normally be very hard for me to determine that Kraken gave me a complete list of their user accounts. Using the merkle tree structure I don't verify that point at all, I can sign a message saying which list of accounts I audited and users themselves can verify that they were part of that list. (Speaking of which, please help to get as many people as possible to do that! Being a JavaScript nerd, I'd especially love to see a browser-based tool as well.)

The original post claims to contain a signed message by a third party auditor who is independent from Kraken, rather than any cryptographic proof. (As an aside: I am unable to verify the author of the message because the PGP key is not obviously connected to the strong set or signed by any key I directly recognize. I am also unable to verify the Independence of the auditor.)

I am unclear as to why this is being described as a "Cryptographically Verifiable Proof of (100%) Reserves" since the security of the audit ultimately rests on the honesty, integrity, and computer security of the auditor (while operating from inside Kraken's offices) and not cryptography.  The audit is also apparently not complete: until a non-trivial portion of customers "verify using open-source tools that your balance at the time of the audit is part of this root hash". I am unable to find instructions for customers to perform this step.

Please be aware that this is absolutely no different than a centralized audit. There are no cryptographic assurances at work here...

Well, first of all, a law wouldn't stop them from claiming it and "running away" anyways. But I don't think any specific law is needed, since existing law already covers the case of a crooked exchange that hides behind cries of "WOLF" while it feasts on lamb every night. Disclaimer: I'm not a lawyer, so take my opinion with a large grain of salt.

When you transfer your BTC to an exchange (for whatever reason), bailment comes into play. I'm not sure if the bailment is gratuitous or whathaveyou, but what's important is that a bailment is created. And if that's the case, then the exchange is under a legal obligation to not only not run away with your BTC but to actually safe-keep it to varying standards.

We need more traders at localbitcoins.com to build a real resilient distributed exchange. Centralized exchange is a dead end, currently there is no law preventing them from claiming most of the bitcoins were stolen by hackers then running away with customer funds

In my view, most of the exchanges are no different than bucket shops, just size differs

You are right to be skeptical: after all this is about your money, and you shouldn't rely on any one person's opinion or assurances. So I do understand what you mean.

I am sure that all the reputable exchanges are taking steps to not only increase the frequency of manual audits but to also institute automated checking/auditing so as to provide additional assurances to their clients. But these sort of tools and technical solutions can take a while to develop and deploy.

In the interim period, having reputable industry leaders, like Stefan (alt: Andreas) do this sort of audit/review with Kraken (alt: Coinbase) can only be a net benefit to the exchanges, to you and to the community.