Topic: [ANN] Kraken Passes Cryptographically Verifiable Proof of Reserves Audit (Read 40017 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.

I'd settle for a multi party audit, with him being involved. Say him plus two others would suffice.

Good job Kraken 

...which means he is at least capable of understanding what is going on and also verifying that no random sh*t is being presented to him.

I would not trust some random 20-years-in-the-business auditor from PWC to do this stuff. Mabye it could be possible to develop something REALLY fool proof and let this be run by a notary (obtain code, check + note down checksums of executables, post output of tools, sign this data)?

These things are unfortunately still too "techy"/strange for someone who audits fiat holdings (they in return usually just trust bank statements by the way). Until then we'll have to deal with Bitcoiners auditing other Bitcoiners I fear.

He could have cured cancer that doesn't change the fact that he is an individual in the industry.

He is also Admin of this board here, wrote BitcoinJS and helped Bitcoin adoption a lot a few years back with the weusecoins video...

Still I agree that it is not ideal to have just someone trusted to look at these numbers instead of publishing bitcoin holdings and user balances.

+1

Why is an industry insider doing your audits? How friendly are you with this Stefan character? How do we know he does not have some ulterior motive in proving your solvency? Because he works for Ripple? Lol, come on.

That's just stupid, to insinuate Kraken would run away with user deposits, it's funded by Roger Ver for christ sake...

Can I make the audit myself using the tools given ?
Or do i need access to the database of Kraken ?

Techniques for doing that exist, but are quite a way off and probably quite a burden for exchanges today (and perhaps always).  So we settle for the best we can get in the meantime, which is: let any customer who cares to check, do so.  If they notice discrepancy they can at least make an informed decision to trade elsewhere.  While they can't provide independently verifiable evidence of what their balance was meant to be (without advanced techniques it comes down to customer's word against exchange's), I suspect if enough users got cheated they'd kick up a stink and a cheating exchange would get called out.

Ultimately, until those advanced techniques are openly available and tested, the burden lies with you, the customer, to actually:

• perform checks regularly
• protest loudly and publicly about discrepancies
• vote with your feet by moving to exchanges which offer this
• vote with your feet by ditching exchanges which implement this incorrectly

How to prove that claim 2 is true? Unless all the customers report their balance in a public poll and no fake reporting

+1

Yes, see https://github.com/olalonde/proof-of-solvency


This problem is addressed in the standard proposed here: https://github.com/olalonde/proof-of-liabilities/#leaf-node

By the way, I'm not sure I understand how Kraken users are supposed to do the verification. Are they given a tree in order to compute the root? If so, would anyone mind sharing the tree they were given so that I can make http://syskall.com/proof-of-liabilities/#verify compatible with their format (this will reveal your balance on Kraken)? Let's be realistic, most users will never verify the code if it involves writing some code.

Good to heard that!
Great job guys!

Great work guys, congratulations.

I'm afraid one piece of the puzzle seems still open to me. The audit proves that everyone's balance is represented in the Merkle tree, but not that the same bitcoins aren't backing two people's accounts at the same time. That is, there's no way to check against the following scenario:

USER1 audit page:
Submission code: 379377cd8190f9bf
Amount: 0.01500000

USER2 audit page:
Submission code: 379377cd8190f9bf
Amount: 0.01500000

Thankfully, this proof gap can be resolved without an auditor, and in an anonymous way.

I propose the following three-step scheme. (step 1) Kraken generates a 64-bit nonce for each account in the system. They publish this nonce on each user's account page, as follows:

USER1 audit:
Submission code: 379377cd8190f9bf
Nonce: fa132f44d7e35e0f
Amount: 0.01500000

(step 2) Kraken publish a signed document with the anonymized account name for each submission code:

$submission_code: sha256($nonce || ":" || $username)

For USER1 in our example, sha256("fa132f44d7e35e0f:USER1")=b7000194f1327aeb9b16f6104333fc889dd2f4c3cdba1eb3500d91ca5efc8208, so the document would contain:

379377cd8190f9bf: b7000194f1327aeb9b16f6104333fc889dd2f4c3cdba1eb3500d91ca5efc8208

(step 3) Users will verify not only that their submission code exists in the Merkle tree, but also that the submission code cannot correspond to any other account by calculating the sha256 as above and verifying that it corresponds to the submission code.

(end of scheme)

The only drawback I see is that this will make public the number of accounts in the Merkle tree, but I don't think this should be a problem.

Let me know what you think.

It would be good to involve a well-known traditional accountancy for this. There are all kinds of standards that could be useful, such as SSAE 16. Note that I'm not talking about permits here, but voluntary audits by a trusted third party.

great stuff.
always good to have transparency, best luck Kraken, here's to the future. 

thanks kraken for doing the audit with crypto-prrof.
imho much more trustworthy than with an auditor.

This is a great news, after all this bad news about exchanges going bankrupt or getting hacked...

It will be amazing if the Bitcoin Foundation or whomever with right authority creates a small team of Independent Auditors funded by the exchanges to do regular checks. This way people can at least have little bit more faith in the system. We cannot trust the exchanges to self-regulate considering what happened at MtGox.

Exchanges can get verified quarterly and the report of the audit can be made public... Just a thought...

Digressing a little bit, but there's many ways to do it. The general theme is that coins that haven't been traded for 24 hours (say) get moved to an M of N wallet. Coins in open orders, or coins that have recently been traded remain in a pooled hot wallet.

It's excellent news that Kraken have provided an independently verifiable declaration of liabilities, using the Merkle technique, and provided open source tools to do it.  Let's hope they also progress to independently verifiable proof of assets and adapt their tool to emerging standards, because then they can just automate the whole process and prove reserves daily, and customers can choose any interoperable verifier.

Also to consider: does this qualify for comboy's offer of free promotion at bitcoinity?  Technically I think CryptX.io and peat.io had implementations first, but AFAIK both were pre-launch at the time.

For those of you who might be considering implementing the scheme, please consider making your implementation compatible with  https://github.com/olalonde/proof-of-liabilities#specification (there are about 3 implementations following this spec now) to allow interoperability with verification tools. Also, see the online tools at http://olalonde.github.io/proof-of-liabilities and higher level description of the scheme at https://iwilcox.me.uk/2014/proving-bitcoin-reserves

We need the proofs to be verifiable automatically (through a browser extension for example) if we ever want this kind of scheme to work in practice.

Regardless, thumbs up to Kraken for being more transparent about solvency.

Not if they don't want to tell everybody every single Bitcoin address they control. Claim 1 might be possible using the block chain and that info, Claim 2 can be partially verified by Kraken users (actually it can only be falsified by Kraken users - as soon as one single Kraken customer can prove that they had a different balance than what was audited or that they aren't included, the audit can be considered fake).

There could be ways for exchanges to cheat here (e.g. leave out accounts that were not used in months for the account balances) but the more they cheat, the higher the risk that they are caught.

Is this a process that can be automated / carried out without an outside auditor?

Great stuff.

Bitstamp already did this. (Edit: An audit of their funds and user balances.)

I wonder when we will see BTC-e, BitStamp and Cryptsy doing this to verify your funds are safe and secure ? That's never going to happen in my opinion.

Gox and VirCurex have been robbed extensively, I see no reason why the others mentioned above would be immune.

I suspect Bitstamp is going to be the next one.

How should that be possible in an exchange setting with sub-milisecond response times for trading?

Sigh, no, you've missed the point.  This wasn't a security audit, this was a cryptographically provable proof of funds.  And no, he didn't have access to the user funds, that's part of the point of doing it this way.

Kraken leading the way!! Thanks Stefan.

+1... Kraken proves nothing to the potential customer

I think we've missed the point here. By showing me that you have access to every users funds, you show me that at any point you can disappear with those funds.

I would prefer to see a report that the users have access to 100% of their funds and the exchange cannot access any of those funds. This is not hard to do now we have M of N signatures, why are exchanges wrapping software around naked private keys and declaring themselves secure.

First let me just say I welcome this sort of action. It's what the community needs!


Ok I'm probably being a noob here - but how dows this proove that Kraken actually control these bitcoins? They could have just given you a list of bitcoins that happen to be in the blockchain. Was there something signed by the private key to prove they actually control these?

*Edit:*
Just looked at the code. It has the following:


Where message and signature are provided in the audit file, and verifier does some stuff with public keys that I can't claim to fully grasp but I will trust as being a valid cryptographic check.
 
So the implication is that Stefan provided Kraken with a message and Kraken used the private keys of the corresponding addresses to sign this message to prove Kraken had them. Would be great if this was made clearer.

Excellent work btcx

Well, "Claim 1" could be improved if the message can be chosen by the auditor (e.g. to being the headline of a large newspaper on audit day + a few random words/numbers that the auditor reveals as close as possible to the audit time (it'll take some time to generate signatures after all)). It is not clear if it was done that way.

great ! looking forward to use your service one day

amazing!

keep up the good work.

the next step: completely trust-less audit mechanism. I seem to remember that gmaxwell proposed something along this line...

anyway I'm more than happy for this achievement

edit1: found out gmazwell proposal, https://iwilcox.me.uk/2014/nofrac-orig

This is why we needed the Gox fiasco to wake us up and demand proof of solvency from exchanges.

This is Bitcoinland. Big Brother won't hold your hand and protect you from evil scammers so you won't have to use your head too much (and then go ahead and scam you himself ) it is your responsibility and we need to demand high quality services and weed out the bad eggs by not doing business with them ourselves.

Good job Kraken!

Awesome.

https://www.kraken.com/security/audit

Big thanks to Stefan Thomas, CTO of Ripple Labs (founder of WeUseCoins.com, BitcoinJS, and Bitcointalk admin), for being our volunteer auditor.

Timing didn't work out for Stefan to post this himself but he will confirm as soon as he is available:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

=====BEGIN AUDIT REPORT=====

AUDITOR: Stefan Thomas
AUDITED ENTITY: Payward, Inc., https://www.kraken.com
ROOT HASH: 306daae528dc137c9053554c45e90a631ef859490a3ede651d488135602500a3
BLOCK HEIGHT: 289859
RESULT: >100% reserves


March 22, 2014
San Francisco

This post is to report on an audit I performed for the Kraken Bitcoin exchange on March 11th, 2014 and March 22nd, 2014 at their offices here in San Francisco. I've not received any payment for this audit - my personal goal with this is to help improve the stability of and confidence in the math-based currency industry overall.


Statement
=========

The audit process is designed to allow the auditor - in this case me, Stefan Thomas - to verify that the total amount of bitcoins held by Kraken matches the amount required to cover an anonymized set of customer balances. I am attesting to is the root hash of a merkle tree containing all balances that were considered in the audit. If you are a customer of Kraken, you'll be able to verify using open-source tools that your balance at the time of the audit is part of this root hash. If it is and if you believe that I am trustworthy, then you can be confident that your balance was covered by 100% reserves at the time of the audit.

Compared to audits performed by other exchanges, this approach is very strict while still maintaining absolute privacy for customers. The most difficult part of an audit is normally to verify that the exchange is not under-reporting the number and balances of account holders. With this approach each account holder can verify that they were considered in the audit.

Trust in this type of audit still requires trust in the auditor. For now, this will rest on my shoulders, but Kraken have expressed interest in doing regular audits with different auditors each time. This serves to renew the audit and also to increase the confidence in the audit process and the validity of the result.


Claims
======

Claim 1: Kraken controls a certain amount of Bitcoins.

Proof: Kraken provided a JSON file with a list of their Bitcoin addresses and balances. I used the `cryptoshi audit` command in libcoin to verify the JSON file against a copy of the block chain.

The version of libcoin used was commit f8c66accf2af88c039bd7c6678da7a338b8befa0.

Here is the audit code used:

https://github.com/libcoin/libcoin/blob/f8c66accf2af88c039bd7c6678da7a338b8befa0/applications/cryptoshi/cryptoshi.cpp#L637-691


Claim 2: The amount from claim 1 is greater than the amount contained in the root hash of balances.

Proof: Kraken provided a binary file containing a set of user balances. This binary file can read and manipulated using the tool "krakendb".

The version of krakendb used was commit 78d3504a7d68256a9a664125fa86a224c479ad42

Available at: https://github.com/payward/krakendb

To calculate the sum of all balances in the tree as well as a merkle tree of all balances, I used the "krakendb root" command. The root hash was:

306daae528dc137c9053554c45e90a631ef859490a3ede651d488135602500a3

The actual holdings were very slightly (< 0.5%) above the required holdings, meaning Kraken had greater than 100% reserves at the audit block height.

// Stefan Thomas

=====END AUDIT REPORT=====

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)

iQIcBAEBAgAGBQJTLkKtAAoJEMlHNwCksIvzZkkP/04wdVeyYd8kKMJWKl1nP1OG
6PD1C01NdOTvsyrRUd9/h2mRc4xmH+IC5WwjhrTStOiiUIKarGb/MlHC5JsMXbQm
+NtxL8+Kbjk0DITCbydEur9udKIWi/CG/ja4aMT1jfOoMqtCNcRLl/4BjsOKUNXS
GZBP0rZTE1yqqlN/rAulQvqeoytWx6LMl9F2qoJ+EZflIRsykJPt8kXNZJudK3nR
yfNzvqa4gHoD07uIxPzTuQJXX4trGXW9K1mXsNJxqIjbR+seEANJMAS4G367Q7D8
quyhAXH8HEEk+isXHa9YXWAe1wgzV9TCYf5yoM+Ki3iWN+CcqSNAGvRAs11Vwjyt
BplgUeN+yyRLvw4cfhvn7cyBmrDBMsKo9sG5yS+Ql6HC7M4+PXp8UaR+DySgttVS
khRuSyiTssmDr/poUwx4R3jj9sn9QoUXMQTHgY56x0YO2TDHlaW/aA2uE6gSABXG
VPIoCKoukjy+W4Q4FSnpYpAQtmWRnsm63DlsMLDZvVg/45uu3/7AmKxtkvkAwwFA
vMZCIhK+VzEZT59A59JO5w/DMglsEZDXXOPV3/G0bR5+P8bpnH2W9BKOIeXtxFGn
360FF9TP2mMfQUCaqa9piLpNokGs8Nl8fb5S9+lxHkqPgw0ZikbmyLcf1h7bXx4W
ssacpTH1s0f5fAiIR5Uo
=zu+r
-----END PGP SIGNATURE-----