This article was first published on November 22, 2022 on tw.xrex.io in Mandarin

As we have discussed in a previous article titled “Proof of Solvency Rather Than Proof of Reserves Will Demonstrate User Assets Have Not Been Misappropriated,” a valid proof of custodial asset solvency is necessary for an exchange to prove it has not been misappropriated user assets. The solvency proof should include both custodial assets and custodial liabilities.

The purpose of “proof of custodial liabilities” is to prove that the “proof of custodial assets” (some peers call it “proof of reserves”) presented by the exchange indeed demonstrates digital assets belonging to the user held in the exchange’s wallet is equivalent to the type and quantity of digital assets deposited by users in the exchange. When the user deposits 1 Bitcoin, there should also be 1 Bitcoin in the “proof of custodial liabilities” and “proof of custodial assets,” rather than other digital assets of equal or unequal value.

Only by cross-examining the “proof of custodial assets” and “proof of custodial liabilities” can we discover whether an exchange has arbitrarily moved or embezzled user assets under its custody.

The “proof of custodial assets” is relatively easy to prepare, as they are on-chain assets that benefit from blockchain’s open and transparent technical characteristics. On the other hand, the “proof of custodial liabilities” is tricky to prepare, as users’ balance data exists in a centralized database.

In fact, algorithms meant to verify the “proof of custodial liabilities” already exist, and it has gone through three generations of evolution. The technology has received more attention due to the FTX bankruptcy, with increasingly more teams and talents willing to invest resources and time in optimizing. The earliest technology to be adopted by the industry in this regard is the Merkle tree which has recently sparked many discussions.

Note: The “proof of custodial liabilities” in this article focuses on the proof of liabilities of the user assets in the custody of the exchange. As shown in Figure 2, it is the scope covered by the red box, namely the balance of digital assets the user has deposited in the exchange. The “custodial liabilities” in the article also focuses on the user’s custodial assets.

This article discusses three generations of the technological evolution of the Merkle tree. Besides sharing the implementation and challenges of “proof of custodial liabilities,” it also reveals some common ways to cheat so that readers can know better how to identify and prevent cheating.

The First Generation of Merkle Tree

Also known as “hash tree,” Merkle tree is a digital signature technology based on hash algorithm proposed by Professor Ralph Merkle in 1988, head of Georgia Tech Information Security Center.

Merkle Tree seems to have come back into the spotlight because of the FTX bankruptcy. There are only seven quotations in the Bitcoin: A Peer-to-Peer Electronic Cash System published by Satoshi Nakamoto in 2008, and three of them are related to the Merkle tree. Merkle tree plays a core role in Satoshi Nakamoto’s blockchain design, especially the “trustless” verification mechanism.

In 2013, there were voices in the Bitcoin community discussing how to apply the Merkle tree to the “proof of liabilities” on centralized wallets. Bryce “Zooko” Wilcox, a well-known cryptographer and one of the founders of the cryptocurrency Zcash, put forward a specific implementation discussion in 2014, also commenting on the main centralized platforms at that time, including BitGO, Bitstamp, Coinbase, Kraken, and about 20 other significant centralized exchanges.

The main advantage of creating the “proof of custodial liabilities” with a Merkle tree is that each user has the independent audit capability for the report on the proof of custodial liabilities. People no longer need to blindly trust the exchange or accountants who endorse it. Instead, everyone can conduct independent audits anytime.

The steps of using a Merkle tree are as follows:

1. For each type of digital assets, such as Bitcoin, Ethereum, USDT, SOL, etc., the exchange will generate the bottom layer of the “tree” according to its centralized ledger. The data of each user (ID, balance) is mixed up to recreate the “hash value,” namely the “leaves” on the “tree,” as well as adding up the balance sum of each hash.
2. Invite external accountants to assist in manual audits to check whether the entire Merkle tree is generated accurately and without cheating.
3. The accountants announce the total “custodial liabilities” and the root hash of the entire Merkle tree, without including the balance sum of each node and each leaf in the entire tree to protect user privacy.
4. Each user uses the open-source code tool from the exchange by entering two pieces of information, including his/her own ID and balance, to generate his/her own hash. He/she can look for his/her own hash by cross-referencing the leaves on the entire tree published by the accountants. If that’s the case, it means that the balance has been included in the proof of liabilities of the exchange.

The spirit of the Merkle tree is to endow each user with independent verification capabilities. The key lies in the fact that each user has the “truth” in the form of his/her daily balance.

Although a user will not know the balance of any other user, he/she can verify the correctness of the report with the “truth” in the form of his/her own balance.

If there are enough users willing to perform independent verification and do so frequently, it is more likely that this “decentralized” verification method will be used to audit the “proof of liabilities” automatically presented by the exchange, and the entire verification process can be automated.

The first-generation Merkle tree faces the following three challenges when applied to the “proof of custodial liabilities:”

1. The decentralized audit capability conflicts with the privacy of user data.
2. The cheating method of “negative balance” means that the exchange creates fake accounts with a negative balance, such as -1000 Bitcoins, so as to reduce the number of Bitcoins in custodial liabilities and cover up the fact of misappropriation.
3. Cheating on other implementation details.

The first challenge refers to that if the exchange is to publish the “proof of custodial liabilities” every day (or hour), and allow each user to verify independently, it means that the exchange will publish the leaves of the Merkle tree, namely the user balance and the “total balance” of the entire tree. Although people cannot find out to whom these “balances” belong as the user names are not disclosed, privacy concerns still exist.

However, if the aforementioned information is not disclosed in consideration of user privacy, the following problems may arise:

1. Each user cannot create the entire “proof of custodial liabilities” independently.
2. External accountants are required to intervene to generate and publish the “proof of custodial liabilities” and the Merkle tree with only the hash part.
3. Each user can only use his/her own balance to verify whether the “proof of custodial liabilities” published by the accountant contains his/her own balance. That is to say, they can only verify their own balance and whether it has been included in the accountant’s calculation, but there is no way to verify the correctness of the entire report’s generation process, and there is no way to verify whether the exchange has used some of the aforementioned cheating methods, for example, negative balance.

Among the exchanges with implementation and open source code, each has different considerations. Both Gate.io (Github in early 2020) and Kraken (2014) chose not to disclose all “balances” and “balance sum” in the Merkle tree. Instead, they rely on external accountants for the audit. BitMEX (Github at the end of 2021) chose to disclose the “balance” and “balance sum” of the entire Merkle tree, but did not do it separately for all asset types, only for BTC’s “proof of custodial liabilities.”

This first-generation Merkle tree proof of liabilities was proposed by Bryce “Zooko” Wilcox in 2013, and was discussed on the Bitcoin Forum by two core developers of Bitcoin, Gregory Maxwell, and Peter Todd. Therefore, it is also known as the “Maxwell method” or “Maxwell-Todd method.”

Second-Generation Merkle Tree Proof of Liabilities with Optimized Privacy

The algorithm of the second-generation Merkle tree is not much different from that of the first generation. The main improvement is that in terms of implementation, it achieves the minimum disclosure of “balance” and “balance sum,” so that the “proof of custodial liabilities” can be decentralized for self-verification by each user without relying on external accountants.

Vitalik, the founder of Ethereum, published an article titled “Having a safe CEX: proof of solvency and beyond” on November 19th, which includes a simple and feasible mechanism:

1. Do not disclose all balances and the sum balance of the entire Merkle tree to everyone.
2. Each user will get a different part of the balance and the balance sum, which reduces privacy concerns and achieves minimum disclosure.

Proof of Liabilities Implemented by the Third Generation of Zero-Knowledge Proofs

Dr. Gaby Dagher, a professor of cryptography, published a set of non-interactive zero-knowledge proof (NIZKP) in 2015 to greatly improve privacy and achieve minimum disclosure for the “proof of custodial liabilities” algorithm. On Nov 19, Vitalik also created a “proof of custodial liabilities” algorithm based on zero-knowledge proof protocol (ZK-SNARK), as well as published a set of open-source codes on Github.

Cheating and Prevention Methods in the Implementation of “Proof of Custodial Liabilities”

Although the “proof of liabilities” has a record of research and implementation in the past, there is still a lot of room for improvement and optimization. The devil is in the details. With over 15 years of experience in information security, the XREX team knows that no matter how perfect the algorithm is, there are still many ways for the exchange to cheat with the number of details in the implementation.

In 2019, Kexin Hu, a professor at the Chinese Academy of Sciences, collected many ways of cheating on the Merkle tree proof of liabilities, as well as ways to prevent them.

This year, Kostas Kryptos, co-founder and chief cryptographer of the new blockchain SUI, compiled detailed information in his “Broken Proofs of Solvency in Blockchain Custodial Wallets and Exchanges.” Not only are various ways of cheating clearly described, for example, the balance sum remains the same while individual numbers are incorrect ((5 +5) is not directly equal to (4+6)), but it also studied the loopholes in prominent centralized exchanges, such as Kraken, BitMEX, Gate.io, etc., in providing proof of custodial asset solvency, as well as the shortcomings of current audit tools adopted by large accounting firms such as Armanino and Deloitte.

Many of these tricks are highly interesting. Some cheating methods follow the logic of hackers, and others are nothing short of what magicians do to deceive the human brain. It is worth studying for the purpose of prevention.

High-quality “Proof of Custodial Asset Solvency” Will Become the Default for Exchanges

All participants and users of the Web3 industry should be able to clearly feel this trend and rigid demand. With the domino effect caused by the FTX bankruptcy, presenting a high-quality “proof of custodial asset solvency” is the basic responsibility of all centralized platforms with a sense of responsibility and self-discipline. However, even if all exchanges issue a “proof of custodial asset solvency,” companies with ill intent can always find ways to deceive and cheat in the context of insufficient supervision.

Considering the aforementioned hidden concerns, XREX proposes to use a decentralized audit method to create “proof of custodial liabilities” which is automatically published daily or hourly, providing sufficient and transparent information as well as a simple verification experience. This allows every user easy access to exercise the right to independently verify an exchange. The more users verify the platform, the harder it is for the platform to cheat, giving the mechanism more credibility. Combined with regular audits by external accountants and objective inspections, the mechanism will add another layer of protection for the users. Here, we also call on external accountants to make the source code of the tools they use open for review by all participants in the community.

Only with such multi-party participation and verification that is independent and comparable to each other layer by layer, can the “proof of custodial asset solvency” truly play its role. The responsibility lies not only with the exchange but also with all users and participants. This is the only way to truly realize the spirit of decentralization and “don’t trust, verify,” so that the FTX disaster can hopefully be prevented in the future.

Special thanks go to Jasmin Tsai, resident accountant of C&R International Law Office and AppWorks, Dien Chang, founder of urCFO and former partner of Deloitte Taiwan, and 徐懿文, CFO, and XREX consultant, for their guidance.

This article is co-authored by the following XREX members: Wayne Huang, 黃建超, 尤芷薇, An-Tsu Chen, Wegin Lee, Nick Liao, Sun Huang, and 蕭滙宗.

Other “Building Safe Exchanges Together” articles you might be interested in:
Proof of Solvency Rather Than Proof of Reserves Will Demonstrate User Assets Have Not Been Misappropriated