How can Cryptographic Proofs Provide a Guarantee of Financial Solvency?

Rather than relying on auditors, technology could allow anyone to independently verify that cryptocurrency businesses are behaving well on an ongoing basis.

Originally published on CoinCenter, on September 19, 2018

Photo by rawpixel on Unsplash

Catastrophic hacks of crypto exchanges have pushed industry leaders to adopt periodic solvency audits, to assure customers and regulators that the exchange is in the black, or has “full reserve”. This process is manual, costly, and prone to misuse. This note describes a better way to address solvency auditing and other financial statements using blockchains and modern zero knowledge proofs of computational integrity.

The Mt. Gox hack and its aftermath

Mt. Gox was the largest Bitcoin exchange of its day, handling over 70% of all Bitcoin transactions. But around Q1 2014 rumors regarding its solvency started circulating, and those were confirmed when, in Q2 2014, the exchange abruptly shut down and filed for bankruptcy. The reason? 850,000 BTC were missing. Oops. That’s $5.8 Billion USD at today’s prices. It is not clear yet whether it was an inside job, an external hack or a combination of both, but what is clear is that slowly, over the course of many months, funds were being funneled to Bitcoin addresses outside the control of the exchange, unbeknownst to customers.

How could such a grand theft have gone unnoticed? Surely the rapid growth in BTC volume and value caught Mt. Gox unprepared, with not enough time to beef up operational security. Partly this was because open blockchains are irreversible — once a transaction has appeared on the blockchain it is nearly impossible to remove it without catastrophic implications to the whole ecosystem. But if there was some way to allow customers to monitor the solvency of the exchange, alarm bells could have been sounded earlier, and crisis averted.

Because of this incident (and several other smaller exchange hacks), leading crypto exchanges nowadays invite external auditors on a regular basis to conduct solvency audits on behalf of regulators and customers. During such an audit, the exchange will prove to the auditor that it actively controls (via cryptographic keys) more assets than its liabilities to customers. The auditor is asked to prepare a balance sheet and post its solvency bottom line on some public forum, announcing: “as of today, this exchange is in the black”. (Notice that the solvency audit checks if the exchange has full reserve but the techniques discussed below could be adopted to fractional reserve solvency audits, as required by commercial banks).

Drawbacks of manual solvency audits

This solvency audit has several drawbacks. It is manual and costly; it is dangerous from an operational security standpoint because some information about usage of the sensitive secret keys controlling billions of dollars in crypto assets will be revealed to external parties (the auditor); and what’s most worrisome is that an exchange that has been compromised can still cover this up by omitting a few customer liabilities from the balance sheet. After all, there’s no easy way for the auditor to know that each and every customer has been accounted for and so, the exchange must be trusted on this matter.

Solvency audit desiderata

Given the problems above, what goals should the solvency audit process achieve? First, it should prevent business secrets of the exchange from being leaked. Second, each and every customer should to be able to verify that her liabilities have been accounted for in the solvency audit, to improve transparency and public oversight. Third, the process should involve no external auditor at all, as this will reduce costs and security attack surface; in other words, we seek a self-audit process, executed solely by the crypto exchange. Fourth and last, even though no external party is involved in the audit, it should prevent rogue exchanges from “cooking their books”. Wait, but doesn’t privacy (1st goal) contradict transparency (2nd goal), and doesn’t self-auditing (3rd goal) compromise soundness (4th goal)? Is it possible to achieve all of them simultaneously? Surprisingly, the answer is yes, as we now explain.

Sealed envelopes, blockchains and computational integrity

If privacy was not an issue, regulators could simply require exchanges to publish their detailed balance sheets for all to see. This would certainly allow public oversight to prevent “cooking books” by omitting liabilities because those customers whose liabilities are omitted would raise a public cry. Alas, privacy considerations rule out this simple solution.

A second attempt to solve the problem is for regulators to demand that an exchange show its detailed balance sheet in private to each and every customer, say, by sending each of them a monthly report. Putting aside the problem of leaking private business information to external parties, a rogue exchange that is actually in the red could still cheat each customer by presenting it with a specific balance sheet that includes her liabilities but omits enough other liabilities to reach positive balance. Detecting this would require customers to share their (confidential) financial data, which is unlikely. Therefore, our solution, presented next, will require exchanges to post a single public “anchor” for each (monthly) balance sheet, and then provide personalized information to each customer, such that the customer can verify that the information presented to her refers to the single public anchor. Furthermore, that anchor will “bind” the exchange to a single balance sheet, yet it will not compromise the financial privacy of the exchange.

Indeed, there is a way for the exchange to take all of its private data — secret keys, assets, customer accounts and liabilities, place them inside a small sealed envelope and put that envelope somewhere where the company cannot tamper with it. This envelope now serves as the needed “anchor” for the balance sheet. Now, the exchange will use new cryptographic tools (explained below) to simulate a trusted auditor that is given access to the contents of the envelope. Magically, these tools allow honest exchanges to create convincing proofs for each customer, proofs that leak no information about the contents of the envelope. At the same time, the very same tools make it intractably hard for rogue exchanges to create convincing proofs for statements that are inconsistent with the data inside the sealed envelope. This “self-audit” capability is the product of the powerful combination of blockchains and zero knowledge proofs.

Commitment schemes as sealed envelopes

The digital analog of sealed envelopes has been safely used by computers for decades, cryptographers call these envelopes cryptographic commitments. Irrespective of the size of the electronic data placed inside, the sealed envelope version of it (its commitment) is typically tiny, 32 characters long.

Placing the exchang’s sealed envelope in a tamper-proof place is also achievable today, thanks to decentralized blockchains. Satoshi’s core innovation was the creation of a public ledger that is not controlled by any one party and which is practically irreversible. Strong computational requirements and economic incentives back this irreversibility. Indeed, Bitcoin’s blockchain is already serving as a trusted timestamping service. So we see that exchanges can efficiently and securely place sealed envelopes (commitments) that contain within them all the data needed to perform personalized solvency audits for each customer, and the only missing part in our story is explaining how to prove to regulators, and to the general public, that the data inside the envelopes is valid, without revealing any additional information that would compromise customer privacy. This is precisely where zero-knowledge proofs come in handy.

Zero-knowledge proofs as trusted auditors

Zero-knowledge (ZK) proofs are like grocery receipts on steroids. Each proof is a string of characters (like a receipt) that enforces computational integrity, i.e., it convinces us — the verifiers — that the end result of a computation is correct. Grocery receipts convince us that the total sum we need to pay is correct, and ZK proofs, their beefed up version, are powerful enough to address any computation and convince us that its output is correct. Furthermore, ZK proofs preserve privacy, which means that the proof (string of characters) teaches us nothing about the inputs of the computation. It’s like a grocery receipt that (i) shows only the total sum, (ii) blanks out individual item prices and quantities, yet (iii) convinces the customer that the sum she should pay is accurate. Finally, some ZK proofs are extremely efficient: checking them (say, using a smartphone) takes fractions of second, even if the computation being discussed is long and hard to compute; think of it as a receipt covering millions of items, which can be checked in a blink of an eye.

Let’s outline our solution for the solvency audit problem, that achieves all of the four goals stated above (privacy, transparency, self-auditing, and soundness). It involves three steps. The first two steps are easy to implement using off-the-shelf technology; the third step uses ZK proofs that are now entering the market:

1. The exchange places in a sealed envelope all the data that it would have presented to a trusted auditor for the purpose of proving solvency to each customer. This data includes all secret keys controlled by the company, all assets it controls and all customer liabilities. Recall that the sealed envelope is short (32 characters) and reveals no information about its contents to anyone who views it.
2. The exchange posts the sealed envelope (all 32 characters) onto a blockchain, like Bitcoin.
3. For each customer, the exchange now reads the contents of the sealed envelope and produces a personalized ZK proof of solvency (a “receipt on steroids”) for that particular customer. This computation has two public outputs (and all inputs to it are “blanked out” to preserve privacy). The two outputs are: (i) a single bit signalling whether the exchange is in black or red, and (ii) the account value of this particular customer.

The privacy preserving aspect of this proof means that the customer learned nothing about what’s in the sealed envelope (other than her own account information, which she knew in the first place). The magic of ZK proofs is that they are “proofs” in the mathematical sense of the word: all true statements can be proved, and only true statements can be proved. Therefore, the exchange cannot cheat its customers and claim it is in the black if it’s actually in the red, nor can the exchange mess around with the account information inside the envelope to fool particular customers by changing their account information. The exchange has one way, and only one way, to move forward: prove correct statements and produce correct personalized solvency audits.

The status of ZK proof technology

The theory of ZK proofs was invented in the mid-1980’s. The technology has improved dramatically over the past few years, to the point it is of commercial relevance. Three prominent proof systems are mentioned currently: ZK-SNARK (used by Zcash and a few others), ZK-STARK (commercialized by StarkWare, and sponsored by the Ethereum Foundation), and Bulletproofs (being explored by the Monero cryptocurrency).

Concluding thoughts

The 3-step process described above for performing personalized solvency audits with no trust assumptions can be applied to other types of financial statements(including income, equity, and cash flow statements). Financial statements have been around for millennia, ever since humans started writing things down. The technology used to prepare and record them has evolved from clay tablets(4,000 years ago) to sheets of paper to digitally signed files. But thus far, ensuring their correctness always involved either trusting the business making the statement, or trusting an external (human) auditor to vouch for it. The combination of blockchains, commitments and, most importantly, ZK proofs, may remove these trust assumptions in the future and rely on transparent and democratic auditing, by the public, for the public.

Further reading

• Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges[Dagher, Bunz, Bonneau, Clark, Boneh; ACM CCS 2015]
• zkLedger: Privacy-Preserving Auditing for Distributed Ledgers [Narula, Vasquez, Virza; NSDI 2018]

Eli Ben Sasson
StarkWare Industries