krakenfx / krakendb Goto Github PK

This is slight duplication, since I already invited you to comment on and participate in the standard we're trying to develop for interoperability between implementations, but I'm raising this issue to make that invitation more obvious to people just browsing your project.

The current implementation of its auditing mechanism allows Kraken to subvert the auditing process even if the auditor is fair and all users verify their inclusion in the Merkle tree. Specifically, because the salt is not tied to the specific user account, Kraken can deceive users by performing the following attack: First, it detects users that possess the exact same amount of bitcoin. Next, it uses the exact same salt for all of them. Finally, it includes each amount with its salt only in one node of the Merkle tree.

In this case, all users will be able to verify their inclusion in the tree. This is because they will see one node which corresponds to their salt and exact amount and the path to the root will verify.

Furthermore, the auditor will not see any foul play; they will verify that the claimed Merkle tree has nodes which sum up correctly to the root node (a proof of liabilities) and that the bitcoin addresses owned by Kraken contain enough funds to cover them (a proof of assets).

Unfortunately, this is not enough – the fact that multiple users see the same nodes means that the amounts are overlapping and hence multiple liabilities can be covered by the same assets. For example, if 4 Kraken users, A, B, C, and D have each deposited bitcoins as follows:

• A: 1 bitcoin
• B: 1 bitcoin
• C: 2 bitcoins
• D: 2 bitcoins

Then Kraken can generate the salt "aaaa" for users A and B and the salt "dddd" for users C and D. Then the Merkle tree would have two leafs; leaf A which contains the plaintext "1" for the amount and the salt "aaaa" and leaf D which contains the plaintext "2" for the amount and the salt "dddd". Then Kraken can present the salt "aaaa" to both users A and B and the salt "dddd" to both users C and D. These users would successfully verify their inclusion in the Merkle tree.

Kraken could then claim to the auditor they they have only 2 users: User A and User D. The auditor would then sum up the Merkle tree to a total amount of 3 bitcoins in liabilities. Then Kraken could illustrate a proof of assets worth 3 bitcoins. However, Kraken would be insolvent in this case; they have a total liability of 6 bitcoins, but only assets to cover 3 bitcoins.

The solution to this security problem is to change the salt to be the hash of a nonce and personally identifiable information for the user, for example the first name, last name, and email address concatenated. The personally identifiable information does not have to be revealed to the auditor; the auditor can only see the hash of that information, which will be treated as the salt. However, the user can verify that the salt was generated correctly. Here's an example:

nonce = rand()
salt = SHA256(nonce || firstname || lastname || email)

In the context of proving liabilities, customers are not interested in whether they or other customers owe the exchange small amounts, and aren't in possession of enough information to understand the situations surrounding negative balances even if they do see them in neighbouring nodes. While it adds a very slight burden to the exchange in terms of having to prove a little more in assets than they actually owe customers, this situation should be so exceptional, the amounts concerned so small, and exchanges so liquid, that it shouldn't cause any significant problem. Keeping negative balances present means there's a risk of users coming to accept them as normal (from Kraken and others), giving evil exchanges freedom to cheat.