Late one afternoon in March, Stefan Thomas walked into a slick, brick-and-beam top-floor office on San Francisco’s Market Street. The office, typical of spaces in the city’s burgeoning tech corridor, is populated by employees of bitcoin exchange Kraken.

By the time he walked in, the afternoon sun was dying, and most employees had left. Only the company CEO Jesse Powell was there, with one other employee.

After the obligatory greetings and general chit-chat, Thomas sat down at Powell’s desk, broke out an Ubuntu virtual machine on a sleek, silver Mac computer, and got to work.

He was here to prove that Kraken possessed the bitcoins it claimed to have.

Following February's panic about events at Mt. Gox, when the Japanese-based site had imploded spectacularly, taking 850,000 bitcoins with it, and leaving distraught users in its wake, Powell wanted to reassure his own users that his exchange wasn’t operating a fractional reserve.

He couldn’t very well audit his own company, though, which is why Thomas was quietly typing away at his temporary desk.

So, who is Stefan Thomas, and why is he the person Powell called?

Thomas is Chief Technical Officer at Ripple Labs, a company that created its own payment protocol and prides itself on a transparent public ledger of transactions.

He was involved in bitcoin from an early stage, having produced the now famous What Is Bitcoin video, and piloted WeUseCoins – an online guide to bitcoin. He has also been the driving force behind BitcoinJS, the JavaScript implementation of the bitcoin protocol.

In short, when it comes to the technology underpinning bitcoin, Thomas knows his stuff.

“Stefan is local, he was available on short notice, he's trusted by the community and one of the few people competent enough to perform the audit,” said Powell, adding:

The audit involved two different sets of data.

The first was the balance of bitcoins that Kraken held in storage, in its own publicly visible bitcoin addresses.

The second was the set of addresses that made up its customer accounts. You can think of the first as its assets, and the second as its liabilities, because each bitcoin held in a user account was effectively a bitcoin that the exchange would have to pay back at some point.

Kraken was seeking to prove that it held more bitcoins in storage than customers had in their accounts, which involved checking the totals of each of those sets of addresses.

So, how did Thomas do it?

The basis for the Kraken audit was the 'Merkle tree', which is a system for improving the integrity of a collection of data.

In the bitcoin block chain, the Merkle tree is used to store the transactions in a particular block. Its advantage is that it can easily produce a single hash (known as the Merkle root), which effectively hashes all the transactions in the tree.

Small groups of transactions are hashed together, and then the results of those hashes are hashed together yet again. This continues until the final hash produces the single Merkle root. This root can be used to affirm the contents of any address in the tree.

There is a Merkle tree (and corresponding root) for both the liability (customer balances) and the asset (Kraken’s wallet) sides of the audit.

To produce the asset hash, Thomas was given the public addresses of Kraken’s entire wallet. He could then get the contents of those addresses from the public bitcoin blockchain.

To collect and hash that data, he used a tool written by Michael Grønager, Kraken’s COO, called Cryptoshi, which is designed to manipulate different wallet structures.

Cryptoshi uses libcoin, a cryptocurrency library based on the original Satoshi client that became the bitcoin core reference product. Thomas describes Cryptoshi as “a Swiss army knife for cryptocurrency.”

On the asset side, Thomas could assume that the Merkle tree for Kraken’s own wallet included all of the addresses under its control. It wouldn’t make sense for the exchange not to include them, if it wanted him to include its entire balance in his analysis.

However, things are more complex on the liabilities side (the bitcoins held in Kraken’s customer addresses), for two reasons.

Firstly, a dishonest exchange trying to deceive an auditor might want to exclude customer accounts from the liabilities tree, because each of these accounts adds to the amount that the exchange owes in coins.

The easiest way to prove that it didn’t do that is simply to publish all of the balances and addresses in the tree, along with the Merkle root.

That way, anyone could simply add the contents of those addresses, and check that the balance matches that of the hashed tree. Then they could hash that same tree, and ensure that its Merkle root matched the one published as part of the audit.

That’s where the second challenge comes in. Most exchanges don’t want all of that information made public, said Thomas.

Publishing balances and addresses is a potential privacy issue, and could also reveal sensitive information about how they handle their wallets. A sum of all balances is also competitively sensitive information.

“[Kraken was] trying to err on the side of caution and try not to publish that information,” Thomas explained.

Instead, Thomas checked the sum of balances privately and testified that there were more assets than liabilities. Kraken then followed a recommendation initially proposed by bitcoin core developer Gregory Maxwell.

[post-quote]

Maxwell advised exchanges to publish the Merkle root publicly. Then, when a user connects, display their account balance at the time of the audit privately to them, along with the pieces of the tree that lie between their address and the root of the tree.

In effect, this gives the user a branch of the tree, enabling them to prove that they were at least included in this branch when it was hashed. This way the user is reassured that their address was included in the audit.

It is up to users to run a test, checking that their address was included in the overall hash, and the more such tests that occur from different branches, the greater the probability that an exchange will get caught out if it omits any addresses.

Does this mean that the balance is foolproof? Sadly, no.

“With any audit, there are some pretty big holes that you can't cover,” says Thomas, explaining.

Kraken points to other shortcomings in the process on its own page, describing the audit process. Firstly, the exchange can’t prove that others haven’t misappropriated its private keys, meaning that it can’t demonstrate unequivocally that it has exclusive access to the bitcoins in its wallet.

Secondly, the auditor has to be technically capable and trustworthy, because there are still some areas of the process where a dishonest exchange could mislead them, or for the auditor to mislead the public, possibly in collaboration with the exchange.

“A lot of these things are difficult to verify or prove,” said Thomas, adding:

Essentially, this kind of audit is “better than nothing,” explained Thomas, who subsequently carried out another audit along similar lines for bitcoin trading platform Bitfinex.

This kind of audit may not be watertight, but it’s a best effort in a fast-changing environment, and exchanges like Kraken and Bitfinex are leading the way in reassuring customers shaken by the Mt. Gox affair.

How far should audits go, though, and what else can be done to ensure that exchanges are operating properly?

It turns out that there’s a lot more that could be done. In the second part of this investigation (coming soon), we’ll discuss those options, and some of the exchanges that are exploring them.

Audit image via Shutterstock