This post was first published on Medium.

The implosion of the FTX cryptocurrency exchange, with billions of missing customer funds, is the latest example of exchange insolvency in cryptocurrency history. The story dates back to 2014 when the oldest and largest exchange Mt. Gox, which handles 70% of bitcoin exchanges, lost 850,000 bitcoins from its users.

Many users today prefer to store their cryptocurrency assertions with centralized exchanges for ease of use similar to online banking, to avoid the difficulty and risk of managing cryptographic keys themselves.

Unfortunately, storing assets with an exchange puts users at risk of the exchange losing them due to external or internal theft.

We show an exchange method for cryptographically prove its solvency, i.e. that its assets cover its liabilities. Proof does not disclose any private information, including its customers, addresses it controls, and its total responsibilities. The proposed methods can be complementary to the confidence audit, which can be costly, or be applied independently.

Naive approach

A rudimentary approach for an exchange to demonstrate its creditworthiness is to publicly disclose the responsibilities of all users and Bitcoin addresses it controls. Any party can calculate the total of its liabilities and its assets, and thus check whether it is fully solvent.

Each user can independently verify that they are in the accountability dataset. The exchange can be intercepted if it misses a user.

The exchange can prove its possession of the private key at any address, by digitally signing or moving the balance to a new address.

This full transparency approach is obviously problematic as it leaks commercially sensitive information about the exchange and its users. We need an alternative that preserves privacy.

Cryptographic primitives

Pedersen’s Commitments

Pedersen’s commitment to a message X is defined as

Crypto Exchanges

g and H are independent generators of an elliptic curve. r is a random value called the blinding factor.

Unlike a hash-based pledge such as SHA256, Pedersen’s pledge is additively homomorphic. This means that without knowledge of the two values ​​x and y, one can add their corresponding commitments to calculate a commitment to their sum.

Crypto Exchanges

Zero-Knowledge Range Test (ZKRP)

A ZKRP is a special type of Zero-Knowledge evidence that shows that a number falls within a certain range, without disclosing the number. Bulletproof is an effective ZKRP build.

Proof of Assets

In proof of assets (aka, proof of reserves), an exchange acts as a prover of its total assets and any party can act as a verifier.

To prevent the exchange’s private data from leaking, the following measures are taken.

1. More anonymity addresses are added to the full set of assets, whose private key is not known to the exchange. This obscures the set of addresses owned by the exchange.

Crypto Exchanges

2. A ZKP such as zk-SNARK is used to prove the following statement for each address:

Either I know the private key corresponding to the address and the commitment is for the balance of the address

Where

I don’t know the private key and the commitment is 0.

Crypto Exchanges

3. The total asset balance can be obtained by adding all the individual liabilities proven in step 2. Note that the total asset, which is proprietary and sensitive, is not disclosed, only its Pedersen liability.

The end result is a Pedersen Commitment to Total Assets commit (assets) that the exchange knows the private keys for a subset of Bitcoin addresses in the full set.

Proof of Passive

Next, an exchange proves the total amount of coins it owes to all of its customers. Each client verifies that it is included.

Summation Merkle Tree

To do this, the exchange organizes all users into a variation of the Merkle tree. Each sheet represents a user and their balance. Compared to a canonical Merkle tree, the summation Merkle tree makes two modifications.

  1. Besides the hash, a balance field is added in each node. The balance of a node is the sum of its two children.
  2. Instead of a hash such as SHA256, a Pedersen pledge is used.

Crypto Exchanges

The root of the tree contains the total liability commitment. The exchange signs the root and publishes it to, for example, Bitcoin.

Each customer can request a Merkle proof of their inclusion against the published root. If enough customers verify independently, a cheating exchange can be detected with high probability.

Range test

A dishonest exchange can cheat by including fake users with a negative balance and thereby reducing their total liabilities. To prevent this attack, the exchange also provides a ZKRP to each foil client with a non-negative balance, without disclosing the balance itself.

Note that the exchange has no incentive to add fake users with a positive balance, as this increases their liabilities.

proof of solvency

Crypto Exchanges

Once the exchange completes proof of assets and liabilities, we can calculate the commitment of its balance.

commit(balance) = commit(asset) — commit(passive)

The exchange has two ways to prove that the balance is non-negative, i.e. the exchange is solvent.

  1. Open Escrow directly.
  2. Prove that the balance is non-negative using ZKP, given its commitment.

Discussion

Our proof of credit is only a preliminary step for exchanges to increase transparency and build customer confidence. There are many other steps to take for it to be adopted in practice, where an exchange releases the proof on a regular basis.

For example, a cabal of insolvent exchanges may collude by covering the individual liabilities of each exchange with their collective assets. Essentially, nothing prevents assets from a single Bitcoin address from being used in proof of credit for various exchanges. To counter this attack, proof of an exchange’s assets must prove that the address set is disjoint from that of another exchange.

References

[1] Privacy Preserving Proof of Credit Provisions for Bitcoin Real World Crypto Exchanges 2016: Slides

[2] A ZK-SNARK-Based Proof-of-Asset Protocol for Bitcoin Exchanges

Watch: CoinGeek New York Presentation, FYI: Better Information Tools for a More Legal Blockchain Industry

width=”562″ height=”315″ frameborder=”0″ allowfullscreen=”allowfullscreen”>

New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn about bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.