Abstract: This post is part 2 of a detailed explanation of Proof of Reserves. It dives into the construction and history of the Proof of Assets protocol. A light technical know-how is required to read this article. Introduction In a previous blog post, Silver Sixpence highlighted our commitment to advancing the state of Proof of Reserves (PoR) through privacy-preserving and crypto-native solutions. Silver Sixpence is building an open-source software library & web application for PoR to enhance the transparency, reliability, and accessibility of centralised exchange solvency data. Generally, PoR refers to an accounting procedure that digital asset custodians (e.g. centralised cryptocurrency exchanges, aka CEXes) undertake to show that they have enough assets to cover their total user liabilities; it allows the custodian’s customers to verify (in a trustless manner) that the custodian is indeed solvent. PoR consists of 2 steps: Proof of Assets (PoA) and Proof of Liabilities (PoL). In PoA, the exchange demonstrates control of digital assets, while in PoL, the exchange commits to the total assets owed to each user (the liabilities). The essence of PoR lies in comparing the total sum of liabilities to the total sum of assets, with the ultimate goal of ensuring a positive balance sheet (assets - liabilities > 0). In this post, we will focus on PoA; PoL is covered in a previous article. We focus on PoA for a single digital asset to simplify the text, although the principles can be easily extended to multiple. A quick note on the terminology Proof of Solvency generally refers to a wider area than what we are focused on, so this terminology is not used. According to the definitions made by the Chamber of Digital Commerce, we are focusing specifically on Proof of Platform Reserves. Still, the post will use the term Proof of Reserves (PoR) to mean this. PoR can sometimes be meant to be Proof of Assets, but this post does not use the term in that way.[^1]

TL;DR: Proof of Liabilities is one of two protocols used in Proof of Reserves. This post walks through the construction of such a protocol using a Merkle Sum Tree, which allows an exchange to commit to its liabilities without revealing customer information or business-critical data like the exchange’s number of users, individual, and total liabilities. As a public company, Coinbase already proves its reserves through rigorous accounting supported by a strong control environment. On-chain accounting is the future, but more work needs to be done before it’s ready to be implemented at scale. To that end, Coinbase is exploring crypto-native ways to provide proof of reserves. Introduction In our previous blog post, we delved into the collaboration between Coinbase and Silver Sixpence, highlighting our commitment to advancing the state of Proof-of-Reserves (PoR) through privacy-preserving and crypto-native solutions. Silver Sixpence is building an open-source software library & web application for PoR which aims to enhance the transparency, reliability, and accessibility of exchange solvency data. Generally, Proof of Reserves (PoR) refers to an accounting procedure that exchanges undertake to show that they have enough assets to cover their total user liabilities; it allows the exchange’s customers to verify (in a trustless manner) that the exchange is indeed solvent. PoR consists of 2 steps: Proof of Assets (PoA) and Proof of Liabilities (PoL). In PoA, the exchange demonstrates control over the private keys of specific on-chain addresses, while in PoL the exchange commits to the sum total of assets owed to each user (the liabilities). The essence of PoR lies in comparing the total sum of liabilities to the total sum of assets, with the ultimate goal of ensuring a positive balance sheet (assets - liabilities > 0). In this post we will focus on PoL, and PoA will be explored in a subsequent article. To simplify the text, we focus on PoL for a single digital asset, although the principles can be easily extended to multiple. A working implementation of the PoL protocol can be found here. The protocol allows exchanges to perform PoL while keeping hidden a) the number of users of the exchange, b) each user’s identifying information & individual balance, and c) the total sum of the exchange’s liabilities. Below is a snippet of the benchmark data for the implementation (full benchmark results can be found in the repo). The tree build and memory metrics are for a tree of height 32, built using an r7a EC2 instance with 128 cores:

Ethereum is the chain here. Other chains would possibly need a different spec. ZK-SNARK high-level design The idea is to hide the $n$ accounts of the exchange amongst a greater set of addreses of size $N$ (the anonymity set). The exchange will provide ECDSA signatures as evidence that they control the $n$ accounts. Parameters for the snark: [pub] array[N]: Ethereum addresses (anon set) [pub] array[N]: ETH balances for the above addresses [pvt] array[N]: booleans representing which of the above addresses the exchange owns

This is a top-level doc that links to all other docs for this project. What is all of this? This project aims to help create proof of reserves software that centralized exchanges can use. This project is a collaboration between SilverSixpence & kn0x1y, funded by Coinbase. Discord server: https://discord.gg/8yYPJaMnR6 Quick note on the nomenclature One can read more in Nic Carter's blog or the Proof of Reserves report by Chamber of Digital Commerce. These are the 2 sources that are adhered to. The terms can all be related like so:

Original algorithm The shuffle algorithm is used in the NDM-SMT. Excerpt from section 4.3.1: It turns out Durstenfeld’s shuffle algorithm optimized by a HashMap can achieve the goal. The HashMap originally is empty. We start from the first user and repeat the following steps for 𝑛 times to generate a random mapping. For the 𝑖-th user, randomly select a number $𝑘 ∈ [𝑖, 2^𝐻 ]$. If 𝑘 exists as a key in the HashMap, the 𝑖-th user is mapped to HashMap(𝑘). Otherwise the user is mapped to 𝑘. At the end of each iteration, update the HashMap by HashMap(𝑘) = 𝑖.

Maxwell++ tree Otherwise know as a sparse summation Merkle tree, the Maxwell++ tree takes the regular SMT (Maxwell+ with the security fix proposed by Hu, Zhang, and Guo in 2019^[2]) and splits up each leaf node into 2 or more nodes in order to obfuscate user balances. Attack vector Various exchanges use the Maxwell++ tree to do proof of liabilities. Some of the implementations of the tree are fully public (i.e. all leaf nodes are downloadable). If an adversary could piece together a subset of nodes such that they are sure the the subset is exactly all of the nodes that make up a single user then they can use this information to their advantage. The full breadown of attacks that this information allows will not be covered here but one example would be to track a user's balance over time to determine the leverage of their position and then execute trades to force their liquidation. It's now just a problem of figuring out the viability of such an attack. The argument given below hinges on the assumption that humans use round numbers more so than random numbers for their trades i.e. a user is more likely to trade 1 BTC than 1.71640531 BTC. Mathematical argument We need 2 things for this attack to be viable:

This is a first draft 3 issues facing current PoR solutions Dispute resolution: In all existing PoL solutions there is the problem of how to resolve a dispute between user and exchange when a user claims that they are unjustly represented in the proof. If a user is misrepresented in the PoL, or not represented at all, then they will have a hard time convincing everyone. Generally it is the user's word against the exchange's, there is no way to tell which of the user or the exchange is being malicious; even if a few users come out with the same issue it's still not cut and dry because it might be that a bunch of people are trying to give the exchange a bad name. Ideally this problem should be solved for PoL. Knowledge of verifiers: Another issue with existing PoLs is that, over time with many PoLs, if the exchange knows that only some users continuously do the verification then they know which users they can omit from the proof with high likelihood that they will not get caught. This issue only arises when the tree and inclusion proofs are controlled by the exchange, as apposed to having the whole tree public. Controlling the tree is important for a) privacy, because making the tree public can reveal some information about the exchange (total liabilities, number of users) and b) practicality, because the trees can be 10s or 100s of GB in size which means storing and downloading the full tree becomes expensive (especially when there are many PoLs). Friend attack: In privacy preserving PoAs (like the one in Provisions) an exchange can cheat via the friend attack: the exchange asks a friend to send them some tokens while they do the PoA and then they send the tokens back (or their friend gives them their keys). Public PoAs (where the exchange publishes their addresses) are also susceptible to this attack but it is fairly easy to spot when this happens. Collusion between exchanges is another similar attack where exchanges share funds. Provisions does give a method to solve this issue but it requires exchanges to use the same protocol in a specific manner. Goals of a full PoR solution With the above in mind we can make some goals:

This document proposes a way forward with regards to what should be built to aid in the proof of liabilities effort. Summation Merkle Tree Short overview of the evolution of Summation Merkle Trees (SMT) These types of trees were first proposed by Maxwell in 2013^[1]. Basic idea: one takes a regular Merkle tree but each node carries a number as well as a hash. The numbers at the leaf node are set by the tree creator, and each non-leaf node adds together the numbers of it's children to get it's own number. How this is useful for PoL: each leaf node represents a user (hash of the user ID, for example) and the number attached to these nodes are the users' balances. This way the total liability sum will be at the root node. The exchange constructs the tree and publishes the root node and total liability sum. Users are supposed to check themselves that their balance is correctly represented in the tree by requesting that the exchange give them an inclusion proof (i.e. their path up the tree). The more users that check the more confident everyone is that the tree truthfully shows the exchange's liabilities.