Merkle Sum Tree

What Is a Merkle Sum Tree?

A Merkle sum tree is a cryptographic data structure that augments a standard Merkle tree with cumulative value sums at every node. In a regular Merkle tree, each internal node stores only a hash of its children. In a Merkle sum tree, each internal node stores both a hash and the sum of all values in its subtree. The root node therefore contains a hash that commits to every entry in the tree and a total sum representing the aggregate value of all leaves.

The concept was first proposed by Gregory Maxwell in 2013 as a way for Bitcoin exchanges to prove they hold enough funds to cover all customer deposits. Before Merkle sum trees, verifying an exchange's solvency required trusting a third-party auditor. With this structure, each user can independently verify that their balance is included in the exchange's reported total liabilities without seeing any other user's data.

The structure became a focal point of the cryptocurrency industry after the collapse of FTX in November 2022. Vitalik Buterin published a widely cited proposal arguing that every centralized exchange should adopt Merkle sum tree-based proof of reserves, combined with zero-knowledge proofs to address the structure's known limitations.

How It Works

Tree Construction

Building a Merkle sum tree starts at the leaves and proceeds upward, similar to a standard Merkle tree. The key difference is that each node carries both a cryptographic hash and a numeric sum.

1. Each leaf node contains a user's balance and a hash of their identifier (typically a hashed user ID or account number). The hash prevents revealing the user's identity while still committing to their inclusion.
2. Each internal node is computed from its two children: the sum field equals the sum of its children's sums, and the hash field equals the hash of its children's hashes concatenated with their sums.
3. This process repeats upward until a single root node remains. The root's sum is the total of all leaf values (total liabilities), and the root's hash commits to the entire structure.

Merkle Sum Tree (4 users):

            Root
        hash: H(H_AB || 70 || H_CD || 80)
        sum: 150

       /                    \
    Node AB                Node CD
  hash: H(H_A||30||H_B||40)  hash: H(H_C||50||H_D||30)
  sum: 70                     sum: 80

   /       \               /       \
Leaf A    Leaf B        Leaf C    Leaf D
hash: H(alice)  hash: H(bob)   hash: H(carol)  hash: H(dave)
sum: 30         sum: 40        sum: 50          sum: 30

Where:
  H() = cryptographic hash function
  Total liabilities (root sum) = 150

Generating an Inclusion Proof

A Merkle proof in a sum tree works like a standard Merkle proof but includes the sum values at each sibling node. To prove that Alice's 30-unit balance is included in the 150-unit total:

1. Provide Alice's leaf data: her hashed user ID and her balance (30)
2. Provide the sibling at each level: Leaf B (hash and sum of 40), then Node CD (hash and sum of 80)
3. The verifier recomputes each parent hash and sum upward, confirming that the path produces the published root hash and root sum

Verification steps for Alice (balance = 30):

1. Alice knows: her leaf hash H_A, her balance 30
2. Proof contains: (H_B, 40), (H_CD, 80)

3. Compute parent:
   sum_AB = 30 + 40 = 70
   H_AB = H(H_A || 30 || H_B || 40)

4. Compute root:
   sum_root = 70 + 80 = 150
   H_root = H(H_AB || 70 || H_CD || 80)

5. Compare computed root hash and sum
   against the exchange's published values

The proof is O(log n) in size: for a tree with one million users, the proof requires only about 20 sibling nodes. Each user verifies independently without seeing any other user's balance.

Combining with Proof of Assets

A Merkle sum tree proves liabilities (what the exchange owes users), but solvency requires a second component: proof of assets. The exchange must demonstrate it controls on-chain funds at least equal to the root sum. Common approaches include:

• Signing a challenge message with the private keys of known reserve addresses
• Publishing on-chain transactions from reserve addresses that include a specific hash as proof of control
• Using third-party attestations from custodians who hold assets on the exchange's behalf

When combined, proof of liabilities (Merkle sum tree) and proof of assets (on-chain verification) form a proof of solvency: the exchange can demonstrate that its assets exceed its obligations.

Why It Matters

Before Merkle sum trees, exchange customers had no way to independently verify that an exchange held sufficient reserves. Traditional financial audits happen periodically, involve trusted third parties, and provide only a point-in-time snapshot. The FTX collapse revealed that even major exchanges could misrepresent their financial position for extended periods, with customer funds being diverted to related entities.

Merkle sum trees shift trust from auditors to cryptographic verification. Any user can check their own inclusion at any time, and the published root sum makes the total liabilities transparent. While not a complete solution on its own (see limitations below), it represents a significant improvement over opaque, trust-based systems.

For the broader cryptocurrency ecosystem, proof of reserves builds confidence that centralized custodians are not fractionally reserving customer assets. This is particularly relevant for stablecoin issuers and centralized exchanges that hold significant user funds. For a deeper analysis of how stablecoin issuers approach reserve transparency, see the stablecoin proof of reserves evolution research article.

Use Cases

Exchange Proof of Reserves

After FTX's collapse in November 2022, multiple major exchanges adopted Merkle sum tree-based proof of reserves. Binance, OKX, Kraken, Bitget, and Gate.io each published Merkle sum tree roots and provided individual verification tools for their users. Users can look up their leaf in the tree and verify that their balance is included in the reported total. Some exchanges publish regular attestation reports (monthly or quarterly) with updated tree roots.

Stablecoin Reserve Verification

Fiat-backed stablecoin issuers can use Merkle sum trees to prove that total token supply matches reserve holdings. While most stablecoin attestations today rely on accounting firms, on-chain Merkle sum tree commitments could enable real-time, user-verifiable reserve checks without depending on periodic audits.

Custodial Wallet Providers

Any service that holds assets on behalf of users can use Merkle sum trees to prove solvency. This includes custodial wallets, lending platforms, and cryptocurrency brokerages. Users of self-custodial solutions avoid this concern entirely, since they hold their own keys: there is no counterparty whose solvency needs verification. Layer-2 protocols like Spark provide self-custodial ownership while maintaining the convenience of instant, low-cost transfers.

Data Integrity in Financial Systems

Beyond cryptocurrency, Merkle sum trees have applications in any system that needs to prove aggregate values are consistent with individual entries. Regulatory reporting, fund accounting, and supply chain finance can all benefit from cryptographic commitment to itemized totals.

Risks and Considerations

Negative Balance Attacks

A dishonest exchange can insert fake accounts with negative balances into the tree, artificially reducing the root sum (total reported liabilities). For example, if real liabilities total 1,000 BTC, the exchange could add a fake leaf with a balance of -200 BTC, making the root sum appear as 800 BTC. This would let the exchange pass a solvency check while actually being insolvent.

The fix requires proving that every leaf balance is non-negative. This is where zero-knowledge proofs become essential: a zk-SNARK can prove that all balances in the tree are non-negative without revealing the individual balances. Vitalik Buterin's 2022 proposal specifically advocated for this combination.

User Omission

An exchange can simply exclude some users from the tree, reducing reported liabilities. Because users can only verify their own inclusion, a user who is excluded might not know unless they actively check. If 10% of users never verify their proofs, an exchange could omit those users and underreport liabilities by 10%.

Mitigations include encouraging widespread user verification, publishing the total number of accounts alongside the root, and comparing the published total against known on-chain deposit activity. However, no purely cryptographic solution fully prevents user omission without some form of user participation.

Point-in-Time Snapshots

A Merkle sum tree proof represents a single moment. An exchange could temporarily move borrowed funds into its reserves before generating the proof, then return them immediately after. This "window dressing" makes the exchange appear solvent at the snapshot while being insolvent in practice.

More frequent attestations (daily or real-time) reduce this window, but real-time cryptographic solvency proof remains an open problem. Some proposals involve committing to the tree on-chain at unpredictable intervals to prevent preparation.

Off-Balance-Sheet Liabilities

The tree only captures liabilities the exchange chooses to include. Loans from related entities, derivative obligations, or undisclosed debts are invisible to the Merkle sum tree. FTX's insolvency was partly caused by loans to Alameda Research: a liability category that would not appear in a customer-balance Merkle sum tree. This limitation means Merkle sum tree proofs are necessary but not sufficient for full solvency verification.

Privacy Tradeoffs

In a naive implementation, the proof path reveals sibling node balances, leaking partial information about other users' holdings. With enough proofs from different users colluding, it may be possible to reconstruct significant portions of the tree. Hashing user identifiers prevents direct identification, but balance patterns could still enable inference.

Privacy-preserving implementations use zero-knowledge proofs to hide sibling balances during verification. The verifier learns only that their own balance is included in the correct total, without learning anything about other entries.

Merkle Sum Trees vs. Traditional Audits

The ideal approach combines both: cryptographic proof of reserves for real-time user verification alongside traditional audits to catch off-balance-sheet risks. For more on how stablecoin reserves are structured and verified, see the stablecoin reserve transparency and audit research article.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.