XREX | Exchange User Asset "Liability Proof": Three Generations of Technological Evolution Starting from Merkle Tree

This article is reproduced with permission from XREX.

As mentioned in our previous article "After FTX Bankruptcy: 'Proof of Payment' Can Prove No Misappropriation of User Assets, Not 'Reserve Proof'", cryptocurrency exchanges need to prove that they have not misappropriated user assets by providing a "custodial asset payment capability proof" for user assets. This proof must include "custodial asset proof" and "custodial liability proof" for user assets.

The purpose of the "custodial liability proof" is to prove that the "custodial asset proof" (also known as "reserve proof" by some in the industry) provided by the exchange, which represents the digital assets held in the exchange's wallet on behalf of users, matches the type and quantity of digital assets that users have deposited into the exchange. For example, if a user deposits 1 Bitcoin, both the "custodial liability proof" and "custodial asset proof" should show 1 Bitcoin, not an equivalent or different digital asset.

Advertisement - Please scroll down for more content

By cross-referencing the "custodial asset proof" and "custodial liability proof," it can be determined if an exchange is arbitrarily moving or misappropriating the user assets it custodies.

While "custodial asset proof" is relatively easier to prepare as it involves assets on the blockchain, benefiting from the transparency of blockchain technology, "custodial liability proof" is relatively more challenging because user balance data is stored in centralized databases. There have been algorithms available to verify "custodial liability proof" in the past, evolving through three generations. However, the FTX bankruptcy storm has brought more attention to this technology, leading to more teams and talents willing to invest resources and time to optimize it. One of the earliest technologies applied in the industry in this regard is the Merkle tree, which has sparked many discussions recently.

Note: The "custodial liability proof" discussed in this article mainly focuses on the liability proof of the exchange's custodied user assets, as shown in Figure 2, which covers the user's digital asset balance held in the exchange. Subsequent mentions of "custodial liability" in the article also focus on the discussion area related to custodied user assets.

This article will discuss the three-generation technological evolution starting from the Merkle tree, share the implementation and challenges of "custodial liability proof," and reveal some common cheating methods to help readers understand how to prevent and detect them.

The First Generation of Merkle Tree Proof of Liabilities

The Merkle tree, also known as a "hash tree," is a digital signature technology based on hash algorithms proposed by Professor Ralph Merkle of the Georgia Institute of Technology's Information Security Center in 1988.

Although the Merkle tree gained attention again due to the pursuit of "proof of solvency" after the bankruptcy of FTX, it played a key role in Satoshi Nakamoto's design of the blockchain in the Bitcoin whitepaper in 2008, with three out of seven citations related to the Merkle tree. The Merkle tree is the core of Satoshi Nakamoto's design for a blockchain, especially the "trustless" verification mechanism.

As early as 2013, discussions began in the Bitcoin community on how to apply the Merkle tree to "proof of liabilities" in centralized wallets. In 2014, cryptography expert and Zcash co-founder Bryce “Zooko” Wilcox proposed a concrete implementation discussion, commenting on major centralized platforms at the time, such as BitGO, Bitstamp, Coinbase, Kraken, and about 20 other representative centralized exchanges.

The main advantage of using a Merkle tree to implement "custodial proof of liabilities" is that it allows each user to independently audit the custodial proof of liabilities report. Users do not need to blindly trust the exchange or endorse by auditors; instead, everyone can independently audit at any moment.

The steps of a Merkle tree are as follows:

1. For each type of digital asset, such as Bitcoin, Ethereum, US Dollar stablecoins like USDT, SOL, etc., the exchange generates the "leaves" of the "tree" based on its centralized ledger records. The exchange shuffles and mixes the (ID, balance) data of each user, creates "hash values," also known as "hashes," which are the "leaves" of the "tree," and records the balance sum of each hash.
2. Invite external auditors to assist in manual verification to check if the entire Merkle tree is accurately generated without cheating.
3. The auditor discloses the total "custodial liabilities" and the root hash of the entire Merkle tree but does not include the balance sums of each node and leaf in the tree to protect user privacy.
4. Each user uses the exchange's open-source tools to enter two pieces of information: their ID and balance, to generate their hash and compare it against the auditor's published tree leaves to see if their hash can be found. Finding it means their balance is included in the exchange's custodial proof of liabilities.

The essence of the Merkle tree is to empower each user with independent verification capability. The key is that each user has a "truth": their daily balance.

While a user does not know the balance of any other user, they can verify the correctness of the entire report based on their own balance. If enough users are willing to verify independently and frequently, it is more likely to use this "decentralized" verification method to audit the exchange's automatically issued "proof of liabilities" and automate the entire verification process.

The first generation of Merkle tree implementation for "custodial proof of liabilities" faced three main challenges:

1. The conflict between decentralized auditability and user data privacy.
2. Cheating methods such as "negative balances," where exchanges create fake accounts with negative balances, for example, -1000 bitcoins, to reduce the number of bitcoins in custody, masking misappropriation.
3. Other cheating methods in implementation details.

The first challenge refers to the dilemma of achieving daily (or hourly) publication of "custodial proof of liabilities" by the exchange, allowing each user to independently verify. This means the exchange would have to disclose the leaves of the Merkle tree, namely user balances and the "total balance," although users cannot know whose balances these actually belong to since user names are not public, there are still privacy concerns.

However, if the above data is not disclosed to protect user privacy, the following issues may arise:

1. Each user cannot independently construct the entire "custodial proof of liabilities."
2. External auditors need to intervene to generate and publish the "custodial proof of liabilities" and only disclose part of the Merkle tree with hashes.
3. Each user can only use their balance to verify if the auditor's published "custodial proof of liabilities" includes their balance. They can only verify their balance and whether it has been accounted for by the auditor, but they cannot verify the correctness of the entire report generation process or whether the exchange has used cheating methods such as the previously mentioned negative balances.

Among the exchanges that have implemented and open-sourced their code, each has different considerations. Gate.io (early 2020 Github) and Kraken (2014) choose not to disclose all "balances" and "balance totals" in the Merkle tree and rely on external auditors for verification. BitMEX (late 2021 Github) chooses to disclose the "balances" and "balance totals" of the entire Merkle tree but does not independently do so for all asset categories, only for BTC's "custodial proof of liabilities."

This first-generation Merkle tree proof of liabilities, proposed by Bryce “Zooko” Wilcox in 2013 and discussed by Bitcoin core developers Gregory Maxwell and Peter Todd on the Bitcoin Forum, is commonly referred to as the "Maxwell method" or "Maxwell-Todd method."

The Second Generation Merkle Tree Optimizing Privacy for Proof of Liabilities

The second generation of the Merkle tree does not differ much in algorithm but focuses on implementation, aiming for minimal disclosure of "balances" and "balance totals" to enable decentralized verification of "custodial proof of liabilities" by each user without relying on external auditors.

In the document "Having a safe CEX: proof of solvency and beyond" published by Ethereum founder Vitalik on the 19th of this month, it includes a simple and feasible mechanism:

1. Do not disclose all "balances" and "balance totals" of the entire Merkle tree to everyone.
2. Each user will receive a different part of the "balances" and "balance totals," reducing privacy concerns and achieving minimal disclosure.

The Third Generation Implementation of Proof of Liabilities with Zero-Knowledge Proofs

In 2015, cryptography professor Dr. Gaby Dagher introduced an algorithm using non-interactive zero-knowledge proofs (NIZKP) to significantly enhance privacy and achieve minimal disclosure in the "custodial proof of liabilities" algorithm. Vitalik also announced on the 19th the use of succinct zero-knowledge proofs (zk-SNARK) to achieve the "custodial proof of liabilities" algorithm, and released the code on Github.

Cheating Methods and Prevention in Implementing "Proof of Liabilities"

While there has been research and practical experience in "proof of liabilities," there is still much room for improvement and optimization. In 2019, Professor Kexin Hu of the Chinese Academy of Sciences compiled many cheating methods for Merkle tree proof of liabilities and prevention methods.

This year, Kostas Kryptos, co-founder and chief cryptographer of the new public chain SUI, published a comprehensive overview in "Broken Proofs of Solvency in Blockchain Custodial Wallets and Exchanges", describing various possible cheating methods, such as total amounts being the same but individual numbers being incorrect (e.g., 5 + 5 does not directly equal 4 + 6), and studying representative centralized exchanges such as Kraken, BitMEX, and Gate.io in terms of vulnerabilities in providing "custodial asset proof of solvency," as well as the shortcomings of major accounting firms such as Armanino and Deloitte in their current audit tools.

Many of these methods are intriguing; some cheating methods resemble hacker thinking, while others are akin to magicians deceiving the human brain, and they are worth further study and prevention.

High-Quality "Custodial Proof of Liabilities" Will Become a Fundamental Skill for Exchanges

All participants and users in the Web3 industry should clearly feel this trend and necessity. After the FTX bankruptcy triggered a domino effect, issuing a high-quality "custodial proof of liabilities" is the basic responsibility of all responsible and rigorous centralized platforms. However, even if the exchange issues a "custodial proof of liabilities," under inadequate supervision, malicious operators can always find ways to deceive and cheat.

In view of the above concerns, XREX advocates using decentralized audit methods for "custodial proof of liabilities," automatically publishing daily or hourly and providing sufficient, transparent information and easy verification experiences. This allows every user to exercise their right to independently verify the exchange without hindrance. The more users verify the platform, the more difficult it becomes for the platform to cheat, making such a mechanism more credible. If combined with regular external auditor audits and objective inspections, it adds another layer of protection for users. Therefore, we also call on external auditors to open-source the tools they use for community and participant review.

Only with multiple independent and cross-verifiable participations and verifications can the "custodial asset proof of liabilities" truly fulfill its function. This is not only the responsibility of the exchange but also of the users and all participants. This is the true embodiment of decentralization and the implementation of the spirit of "trust but verify," preventing disasters like FTX from happening again.

This article acknowledges the guidance of Jasmine Tsai, resident accountant at Ri Huan Office and AppWorks, Dien Chang, founder of urCFO and former partner at Deloitte, and Wendy Hsu, CFO advisor at XREX.

Authors of this article from XREX: Wayne Huang, Vince Huang, Yoyo Yu, An-Tsu Chen, Wegin Lee, Nick Liao, Sun Huang, Winston Hsiao.

Related reading in the "Building a Secure Exchange" series:
"After the FTX Bankruptcy: 'Proof of Solvency' Is the Proof of No Misappropriation of User Assets, Not 'Reserve Proof'"