# Summa Report

## The Problem Of Solvency

Solvency means the ability of a custodian to cover all liabilities with the assets that the custodian holds. It can be expressed as a simple equation of Assets >= Liabilities. Applied to centralized crypto exchanges (CEX), this translates into CEX holding the amount of cryptocurrencies equal to or greater than the total of all user balances. A particular, more strict case is when the custodian is not allowed to denominate one asset in some other asset.

## Typical Proof of Solvency Architecture

Summa was influenced by Vitalik Buterin's article, in which he discusses a spectrum of crypto exchanges ranging from fully decentralized (DEX) to fully centralized. DEX does not have the problem of proof of solvency (PoS) because all the trading activity is performed on-chain. Even if the DEX architecture allowed a mismatch between the total assets and liabilities, it would immediately be evident to an external observer. CEX, however, is a black box, and no external observer can independently verify the internal state of the CEX.

Most of the existing PoS solutions work in the following way:
- Custodian is choosing a data structure that allows for proof of inclusion and value aggregation (e.g., Merkle sum tree);
- Custodian aggregates the liabilities (user balances) in said data structure and commits to it without revealing the individual liabilities (e.g., generates Merkle sum tree root);
- Custodian reveals the commitment to the public, effectively revealing the claimed total liabilities (the sum values in the Merkle sum tree root);
- Custodian provides the individual inclusion proofs to the users, where inclusion proofs involve commitment as an input to the inclusion verification process;
Publicly revealing the liabilities commitment is an essential part of a PoS protocol, as all verifying users want to be sure that the commitment is the same for everyone. Most (if not all) the existing PoS solutions, including Summa, rely on collaborative verification, where the number of users who is verifying their balances directly affects the credibility of the proof.

Another side of the solvency equation is the assets the custodian holds. Major CEX wallets are well-known and labeled in blockchain explorers. However, the custodian is still required to prove the address ownership for PoS. Theoretically, a signature performed using the address's private key is good enough to prove the address ownership. In practice, however, the CEX security requirements do not always allow frequent (if any) use of their private keys outside of moving the funds, so sometimes the proof of address ownership is based on funds movement or even on traditional external audit. This part of PoS is not critical to how Summa functions, so it will not be given any more attention in this article.

## Summa Technological Choices

Summa aimed to improve the existing PoS solutions to enable more frequent proofs. Frequent PoS is crucial because even if the custodian proved solvency at a given moment, they could go insolvent between two consecutive rounds of PoS without anyone noticing. Reducing the interval between the rounds increases the risk for a cheating custodian to be caught. While aiming for performance improvement, the Summa team has thoroughly explored the trade-offs of different technical approaches and implemented some innovations. The project had three major iterations of the underlying technology, and we will discuss the technological choices, improvements, and trade-offs of each of them based on the architecture mentioned above.

## Summa V1

### Merkle Sum Tree with ZK Proof of Inclusion

Merkle tree is a go-to structure for proving the inclusion of an element into a set. Its advantage is that it has an efficient commitment in the form of a Merkle root. A "vanilla" Merkle tree does not allow for value aggregation, but a Merkle sum tree does. Applied to PoS, Merkle sum tree leaves would represent the individual users (by their unique user IDs) and hold their respective balances. Merkle sum tree sums the balances of each pair of sibling nodes to obtain the balance of a parent node. The operation repeats up to the root, with the root of the tree effectively holding the sum of all the leaf balances, which in the context of PoS is the total liabilities of the custodian. This data structure satisfies both inclusion and aggregation properties. However, it does not preserve user privacy. Each user inclusion proof contains the sibling leaf representing another user, but leaking user balance information is unacceptable. Different approaches to solving this issue have different trade-offs that are presented in the table below:

| Approach | Shuffled leaf split (BitMex) | Proving the whole tree construction in a ZK circuit (Binance) | Proving inclusion in a ZK circuit (Summa V1) |
| -------- | -------- | -------- | -------- |
| Advantages | Fast generation of both commitment and inclusion proof | Full privacy; fast inclusion proof generation; range check | Full privacy; fast commitment generation; range check |
| Disadvantages | Complicated data structure; partial data leakage; no range check | Dramatically slow commitment generation| Slower inclusion proof generation|

After observing the existing solutions, we have concluded that zero-knowledge cryptography (ZK) is necessary to preserve complete privacy and enable range checks on user balances. However, ZK heavily affects performance and should be applied wisely. For example, Binance uses a "vanilla" Merkle tree without a summation, so the balance aggregation is performed on the side. ZK allows them to constrain the tree and the balance aggregation to each other to ensure that the tree is built using the same user balances that were aggregated to obtain the total liabilities. To do so, they prove the entire tree construction and aggregation in a ZK circuit. This operation is so computationally complex that it costs $1000 of machine-hour time for their user base size. In Summa V1, we chose to prove only the user inclusion in a ZK circuit, sacrificing the user inclusion proof performance. This decision was based on the fact that in existing PoS solutions, users verifying the PoS need to request the inclusion proof from the custodian. Therefore, the custodian can generate the inclusion proofs on-demand but not in one go for the entire user base. This implementation detail may seem insignificant, but it opens up an attack vector for a malicious Custodian. Suppose the custodian knows that some users have never verified their proofs during multiple rounds of solvency. In that case, the custodian can exclude them from the aggregated data structure to understate the liabilities. Mitigating this attack became one of the goals of the V2 iteration of Summa.

The range check is an essential feature of ZK-based PoS solutions. It constrains the user balances within an interval from zero to a reasonable maximum value. Without the range check, a malicious Custodian could include some dummy users with negative balances in the aggregated data structure, effectively understating the liabilities. It works similarly with large values that would cause the summation overflow (because in finite field arithmetic, negative numbers appear as large values). With that said, BitMex (and actually any) non-ZK solution is inherently prone to this attack because there is no way for the custodian to prove that they constructed the aggregated data structure without including malicious balances.

The Summa team has chosen the Halo2 proving system, which allows for efficient range checks by leveraging the lookup argument.

### Smart Contract Registry of Liability Commitments

One of Summa's innovations regarding PoS was leveraging the immutability of blockchain smart contracts to enhance user trust in the PoS protocol. In all the observed existing PoS solutions, the proofs and commitments are served in a centralized way through the custodian's web frontend. Storing the commitments in the Summa smart contract makes commitment retrieval part of the PoS trustless and decentralized.

## Summa V2

Summa V2 aimed to further improve the performance of commitment and user inclusion proof generation phases. The Summa team switched from a Merkle sum tree to a univariate polynomial as the primary data structure to achieve that. A polynomial interpolating the user balances is the closest mathematical equivalent to a simple list of those balances in colloquial terms. The reader may wonder how a polynomial enables the aggregation property necessary for a PoS data structure. As it turns out, if a polynomial is interpolating the values over the domain of the powers of a primitive root of unity, the grand total of all interpolated values is equal to the constant term times the number of values. This inherent property is a significant advantage over a Merkle tree-based architecture requiring computationally intensive hashing.

Another advantage of using polynomials over the roots of unity as a data structure for Summa was thanks to the Halo2 proving system using them internally. They can be considered "building blocks" of a PLONK-based ZK framework such as Halo2. Summa V2 uses the Halo2 internal polynomial interpolation directly, resulting in a circuit with fewer constraints. It significantly improves performance, which directly depends on the number of constraints.

As we said in the beginning, a PoS data structure should also allow for proof of inclusion of the user balances. Polynomials allow for efficient proof of inclusion of interpolated values thanks to a commitment scheme known as KZG. Again, Summa was able to take advantage of the fact that the Halo2 system can naturally use the KZG commitment to build the ZK proof, so no extra computation was necessary outside of the ZK framework, as opposed to Summa V1, where the tree is built outside of the circuit.

Another advantage of KZG commitment is that it allows for a batch opening technique (amortized Feist-Khovratovich opening). When using this technique for medium-size user bases (around a few tens of millions), the per-user proof generation time becomes as low as a few milliseconds. It allows the custodian to generate and distribute all inclusion proofs at once, mitigating the attack mentioned above. For example, if the custodian sends all the proofs to the users by email at once, the custodian will not be able to learn which users have not verified their proofs (assuming that no email tracker is used).

Summa V2 is range-checking the data structure in the ZK circuit at the commitment generation phase, as opposed to the inclusion proof generation phase. This places Summa v2 in a similar category as Binance's solution because of the faster inclusion proof generation and slower commitment generation. Summa V2 outperforms the Binance solution in commitment generation time because of the simpler data structure and circuit structure. Comparing Summa V2 to V1 is challenging because V1 applies the ZK proof to the user inclusion instead of the commitment generation. However, the performance difference between V1 and V2 gives us an important insight: there is a trade-off between constraining the commitment generation versus user inclusion by ZK proof.

| Approach | Merkle tree commitment in a ZK circuit (Binance) | Univariate polynomial commitment in a ZK circuit (Summa V2) | Merkle sum tree inclusion in a ZK circuit (Summa V1) |
| -------- | -------- | -------- | -------- |
| Commitment time | Slow | Moderate | Fast |
| Inclusion proof time | Very fast | Fast | Moderate |

After learning about this trade-off, the Summa team has set a goal to reduce commitment and inclusion proof generation time in the following iteration of the project.

## Summa V3

Univariate polynomial interpolation used in Summa V2 has discrete Fourier transform (DFT) as its performance bottleneck. As the number of users grows, the degree of the polynomials also grows. That explains why, for Summa V3, we directed our attention to proving systems that do not use DFT. We chose Hyperplonk, which uses sumcheck protocol. Sumcheck was initially used in ZK cryptography for so-called zero-checks. However, we realized that we could adopt the sumcheck inside the Hyperplonk SNARK to perform the actual check on the sum of all user balances, which is equal to the claimed total. Again, as in Summa V2, this is quite an innovative "hijack" of the ZK-SNARK inner workings to serve the double purpose of both enabling the ZK-SNARK protocol itself and doing the necessary computation that otherwise would have been done explicitly in the circuit by introducing extra constraints. By leveraging Hyperplonk sumcheck and avoiding DFT, Summa V3 improved on the commitment phase performance. However, we have discovered a new attack vector in case of proving the solvency across multiple assets in a single circuit. In Hyperplonk, a single sumcheck checks all the evaluations of the circuit expression summing up to a desired value. The attack vector that we call a "rebalancing attack" allows the custodian to understate one asset balance and overstate the other by the same number. As the sumcheck only checks the sum of all values across all the assets, the equal decrease of one asset's total and equal increase of the other total would not change the total sum. This attack may be beneficial if the custodian is insolvent in some higher-quality asset but has more than enough in another low-quality asset.

## Performance Comparison by Summa versions

The benchmarks were performed with $2^{17}$ userbase.

**Commitment Proof Generation Time (s)**

| N_CURRENCIES | V1 | V2 | V3(V3a) |
| ------------ | ------- | ------- | ------- |
| 100 | 179.165 | 1137.47 | 524.265 |
| 125 | 233.949 | 1402.1 | 661.157 |
| 150 | 271.588 | 1690.59 | 795.963 |
| 175 | 277.176 | 1744.57 | 928.616 |


- In V1, the increase in time becomes minimal, even as the number of currencies increases. In contrast, the time for V2 and V3 increases almost linearly with the number of currencies.
- Benchmarks could not be performed with more than 175 currencies due to the limitations of the benchmark machine’s specifications. This is because V2 and V3 require more RAM than V1.

**Inclusion Proof Generation Time (ms)**

| N_CURRENCIES | V1 | V2 | V3(V3a) |
|--------------|---------|---------|---------|
| 100 | 13965 | 382.833 | 127.333 |
| 125 | 15643.5 | 436.5 | 136.667 |
| 150 | 16972.8 | 454.333 | 136 |
| 175 | 20870.1 | 450.889 | 143.667 |


In the generation of Inclusion Proofs, V3 significantly outperforms V1 and V2, demonstrating its efficiency despite the additional computational requirements for running sum calculations.

## Conclusion

Throughout iteratively improving our PoS solution, we have explored and addressed key trade-offs between using ZK proofs in the commitment and inclusion proof phases.

Applying ZK cryptography techniques to the commitment phase results in fast inclusion proofs but requires specific optimizations. Summa has successfully implemented these optimizations, differentiating our approach from that of others like Binance. The optimization methods used, such as uni- and multivariate sumcheck protocol and amortized KZG openings, are novel to the field of PoS.

Conversely, applying ZK to the inclusion proof phase results in fast commitments but does not allow for fast inclusion proof generation. This limitation exposes a potential attack vector where a custodian could exploit non-verifying users to understate liabilities.

Summa's iterative improvements have led to a better understanding of the trade-offs in PoS solutions for CEX, balancing efficiency and reliability.