Exploring Decentralized Proof-of-Solvency Systems

Synopsis

Much has been said lately about cryptographic schemes that provide a “proof of solvency,” but much less about the trust assumptions needed to decentralize and deploy them in practice. 

Generally, centralized intermediaries will find it difficult to cryptographically prove solvency without external entities participating in manual and lengthy auditing processes. However, harnessing external parties frequently introduces nuances and requires users to trust centralized intermediaries. 

This doesn’t necessarily mean that only two extremes exist—fully centralized or fully decentralized on-chain—as might be discerned from Vitalik’s post. Oracle technology can help decentralize proof systems off-chain with minimized trust, without relying on end-users posting everything on-chain themselves. 

This post explores several viable paths for oracles to help operate proof systems off-chain. Oracles form a decentralized off-chain network that coordinates tasks by consensus. They can aid in carrying out proof tasks with no single point of centralization or trust by coordinating the output as a group. 

The post focuses on one type of cryptographic proof systems, proof of liabilities (“PoL”), and how to create transparency around the total liabilities maintained by an exchange. It should be noted that other opportunities for oracle roles, in particular in proofs of assets or reserves, are left outside the scope here. The post is organized in two parts:

  • A discussion of challenges in deploying and operating PoL techniques with an emphasis on privacy and trust minimization as goals. 
  • A discussion of potential directions for harnessing oracles as a minimal-trust external aid in the operation of PoL systems.   

Why are there CEXes?

Centralized intermediaries operate on blockchains like Ethereum in various forms, and they probably will continue to do so for the time being.

Centralized crypto exchanges (CEX) are prevalent for a number of reasons: They provide users convenience through tools and mobile apps; they maintain escrow of user secrets and support recovery; they cover compliance requirements such as KYC and anti-fraud/AML protection; and (ironically) they promote user privacy, hiding individual users behind an omnibus account holder on-chain. 

In some cases, a CEX provides essential services like onboarding/offboarding to fiat or other assets which are held outside the blockchain. For example, a stablecoin issuer tokenizes user deposits in fiat, which is held in fiat reserve at a custodian, and then mints stablecoins on-chain that represent 1-1 the money held in reserve. It can be difficult to decentralize stablecoin issuance because it tokenizes assets in the fiat world which must be owned by a centralized entity. 

Another popular form of intermediary is a token wrapping bridge, which enables a user that has liquidity held up on one blockchain (e.g., Bitcoin) to wrap tokens from that chain and mint the equivalent amount of synthetic (wrapped) tokens on another chain. Many such bridges are centralized or have points of centralization in charge of liquidity. 

The bottom line is that until DEXes provide convenience and support to users that parallel CEXes, they are likely here to stay. Unfortunately, recent events demonstrated vividly that trusting intermediaries to keep adequate collaterals is risky.

What Do We Mean by Proof of Solvency?

Transparency is key to financial stability and responsible conduct. Users should favor services that pledge to prove their solvency.

Solvency has two sides: The total liabilities (user deposits) that a CEX has toward its customers on one side and the total assets it holds in reserve as collateral that may be redeemed by users.

A diagram showing how liabilities and assets interoperate within a centralized exchange.

Consequently, cryptographic schemes that enable transparent reporting by a CEX, exposing its solvency for scrutiny/audit, fall into two large categories: 

  • Exposing information/proof about liabilities for auditing and scrutiny, namely, the total deposit balances an entity maintains on behalf of its users. This is known as proof of liabilities (“PoL”). There are cryptographic schemes that can prove claims about the sum total of liabilities, without revealing individual items in the sum.
  • Exposing information/proof that the entity reserves sufficient assets as collateral to back its liabilities, also known as proof of reserves. There are cryptographic schemes that can prove claims about the sum-total of CEX assets held on-chain or relayed from another chain, without revealing individual account addresses/balances. 

It is important to note that neither of these schemes alone or jointly “prove” solvency in a legal or regulatory sense. For example, proof of liabilities doesn’t prove that a CEX has no other liabilities and their priority in case of a bankruptcy situation. Likewise, proof-of-reserves doesn’t prove that money held in the reserve is not doubly used as collateral for other liabilities. Our discussion focuses purely on proof-of-solvency technology and the challenges it surfaces.  

Exposing Information about Liabilities with a Summation Merkle-Tree (“SMT”)

A custodial exchange keeps individual user accounts private as most user actions are netted or settled off-chain. When bulk transactions hit the main chain, they are done in aggregate and hide individual user actions behind an omnibus wallet account. 

However, the very same mechanism that provides privacy also shrouds the total liabilities the CEX holds in user balances. 

PoL refers to a cryptographic technique through which a CEX can pledge a commitment of the total liabilities (deposits) it maintains on behalf of its users. Users should favor CEXes that agree to routinely and openly pledge to their total liabilities. As explained above, providing visibility into an entity’s liabilities is an essential component in providing transparency on solvency. 

Maxwell & Todd proposed a PoL system based on end-user participation in auditing. It is based on a core cryptographic scheme that allows a CEX to commit publicly to its total liabilities without sacrificing user privacy. Each user can then “opt in” and individually verify that the liabilities include him/her. Should the CEX misreport liabilities, it risks being detected: the more users participate in auditing, the higher the chance of being detected as cheating. 

At the core of the PoL method is a cryptographic construction called a Summation Merkle-Tree (“SMT”). A basic SMT works as follows.

  • Each leaf in the tree contains in the clear an individual user account balance, and a hash of a tuple consisting of a user identifier and their balance. In notation, a leaf node stores ( amount, hash(user-id, amount) ).
  • Each inner node in the tree combines its children, left and right, summing their amounts and hashing them. In notation, an inner node with children L, R, stores ( L.amount +  R.amount, h(L, R) ).
  • Periodically, the CEX publishes the root of the SMT as a commitment to its sum-total of liabilities. 

It’s worth noting that an SMT is required for security—a vanilla Merkle-tree is not secure for proof-of-liabilities—but the basic SMT described above exposes individual balances and aggregate sums of subsets. 

There have been many variants of the original Maxwell & Todd PoL scheme. For example, DAPOL (Distributed Auditing Proofs of Liabilities) and DAPOL+ and GPOL enhance it with improved privacy guarantees, such as hiding partial sums of liabilities, the total number of users, and the like. In particular, DAPOL+ extends the basic SMT above by storing in leaf-nodes a Pederson commitment to user amounts, which hides the original amount and all internal sums (including the root). Commitments are combined by multiplication instead of addition. DAPOL+ also pads the tree with zero nodes to hide the total count of users. Last, it incorporates lightweight zero-knowledge range-proofs of node values, preventing the prover from injecting negative amounts or overflow when multiplying two children nodes.

Benefits and Challenges with SMT Systems

SMT is one kind of an authenticated membership data-structure. It allows us to verify inclusion, namely, that a particular item exists in the tree, via a succinct proof which is the path from the leaf containing the item to the root. In the PoL context, an SMT allows checking that a particular user—identified by a user-id—and its balance are included in the tree. 

A PoL based on SMT has several benefits. First, it has a succinct commitment—simply posting the root of the tree—which reveals no personal identifying information about individual users. Second, it can provide users with inclusion proofs of their user balances, allowing users to perform a “distributed audit” of a PoL by self-checking that their own balance is reflected correctly in such a proof, without compromising their privacy. This is the “distributed” part in the name DAPOL.

However, the operations involved in orchestrating an SMT-based auditing via user self-checks are far from trivial:  

  1. A CEX needs to regularly Merkelize its liabilities and publish the root at a safe place.
  2. Users need to opt-in to participate in self-checks.
  3. Someone needs to regularly trigger user self-check actions.
  4. There must be an SMT service providing users with inclusion-proofs against a fresh root.
  5. There must be a service or software for users to verify an inclusion-proof against a published root.

There are potential failures associated at each step, such as users unable to obtain proofs, a proof being out-of-sync with the latest published root(s) because a balance has changed, users raising bogus alerts, and other scenarios that the system as a whole needs to address. 

Generally, the challenges emerging in SMT-based PoL systems fall into several categories:

Freshness: A key component in operating the PoL is an “SMT-server” that provides individual inclusion-proofs to end-users. This server needs to store a full copy of the SMT which is sizable. It reflects account balances of potentially hundreds of millions of users, potentially padded with additional “noise” for privacy. Such a data structure may take up hundreds of gigabytes. Furthermore, an SMT-server needs to refresh information frequently. For otherwise, when user balances change, verifying could fail because the data is stale and not because the CEX would have committed fraud. Last, note that the server needs to store not only one copy, but maintain a history of versions in order to handle disputes. 

Completeness: Participation in self-checks is going to be only partial. Unfortunately, this makes it possible for the CEX to deliberately omit users. Note that it suffices for the service to omit a small set of users (e.g., with high balances) to substantially skew a “proof” of liabilities. If the CEX itself operates the SMT-service, there might be considerable sophistication in such omissions: They may be based on users’ opt-ins, or a user may be omitted until it triggers a self-check and then delayed until the next root is published, etc. 

Privacy: If the CEX defers to an external entity to operate the PoL, then the basic SMT scheme exposes information about users–such as their CEX user-id, their account balance distribution—as well as strategic business information about the CEX—such as trends in user activity. Implementing privacy-preserving SMT schemes like DAPOL+ requires more effort and computational resources. 

Dispute handling: If a user complains that their balance is omitted, they may need to expose their user-id and balance. Another type of dispute may occur if a user complains that they did not receive a response from the SMT-service, again requiring the user-id and balance to be exposed. Therefore, users may be reluctant to pursue a dispute process because it is time constraining and due to potential loss of privacy.  Last, but not least, there must be a robust way to distinguish checks that fail legitimately, because a user balance has changed since a proof has been posted, from checks that indicate a genuine problem with the proof.

For additional discussion of issues with PoL systems, see further resources at the bottom of the post.

Minimizing Trust in PoL Systems

The issues highlighted above underscore a conundrum: 

  • On one hand, operating the entire PoL system by the CEX itself has many vulnerabilities which a dishonest CEX could exploit, e.g., Completeness and Dispute-handling issues highlighted above. Therefore, the operation of the PoL and the self-check verification tools/services should ideally be autonomous from the CEX. 
  • On the other hand, for a separate entity to cope with Freshness and Privacy issues indicated above, as well as interact directly with users, requires considerable effort. As a result, in the past, several existing CEX who provided proof-of-liabilities chose to operate the PoL themselves. 

This conflicting incentive structure is at the crux of the PoL debate. 

Oracles can help decentralize PoL so that it is not controlled by a CEX without requiring all information to be posted on-chain. They can aid in various proof tasks on a decentralized off-chain network, that coordinates actions with no single point of centralization or trust, and forms consensus on the output as a group. 

There are many ways to harness the power of decentralized oracle technology in the PoL context. Below, we explore a few preliminary ideas.  

First idea. Oracles can aid on the CEX side. Oracles can store on behalf of the CEX the SMT of commitments to end-user account balances and serve user self-checks. This requires oracles to synchronize with the CEX regularly, but it doesn’t mean that oracles see personal user information or business-sensitive CEX information. In particular, techniques like DAPOL+ (mentioned above) hide all user personal information and their balances in a privacy-preserving SMT. The main advantage when oracles serve end-users self-checks is preventing manipulation by the CEX after it commits to a state of accounts. Oracles also ensure regular state updates. Last, oracles can alleviate the need for each CEX to implement its own PoL and pave the way for an industry PoL standard.

A diagram showing how oracles can store the SMT of commitments on behalf of the CEX.

Second idea. Oracles can help orchestrate inclusion self-checks on behalf of end-users. Doing this solves one of the biggest obstacles to operationalizing PoL because when users are required to perform self-checks, they may not follow the process correctly or give up if they need to wait long; they may be reluctant to raise alerts; and if users raise an alert, it might be disputed by the CEX. Oracles can help beyond initiating self-checks. They can coordinate actions resulting from self-checks, such as reporting success and handling alerts. Doing this by a majority consensus makes alerts credible and alleviates the need for end-users to handle alerts and enter disputes.  

A diagram showing how oracles can help orchestrate inclusion self-checks on behalf of end users.

Third idea. Oracles can automate the triggering of self-checks on behalf of end-users. For example, they can perform provably unbiased random selection of users and ensure that self-checks are not rigged; they can guarantee checks are carried regularly; and/or they can trigger checks in response to certain conditions, e.g., on-chain CEX activity. Making this idea workable may require oracles to hold certain user information, such as a database of opt-in user names to sample from. Furthermore, in order to fully automate self-checks, oracles may need to act as proxies for users and read-access their balances.     

A diagram showing how oracles can automate the triggering of self-checks on behalf of end users.

Summary

To recap, users should favor services that pledge to prove their solvency but services need external aid to carry out proof tasks. The preliminary ideas explored above demonstrate the important role oracles can play in operating proof systems, focusing on one type of proof, namely SMT-based PoL systems. There may be many other proof systems where oracles can enable transparent reporting while minimizing trust.

If you are interested in exploring how Chainlink oracles can help bring increased transparency to your platform or application, reach out to an expert here.

Further Resources