## The State of the Art

All the existing Proof of Solvency instances, both in academia [[1] Ji and Chalkias](https://eprint.iacr.org/2021/1350.pdf), [[2] Boneh et al](https://dl.acm.org/doi/abs/10.1145/2810103.2813674), [[3] Chalkias, Chatzigiannis and Ji](https://eprint.iacr.org/2022/043) and in practice [[4] Binance](https://www.binance.com/en/proof-of-reserves), [[5] Kraken](https://www.kraken.com/proof-of-reserves), [[6] OKX](https://www.okx.com/proof-of-reserves) suffer from the same problem: **they do not achieve finality**. In the context of Proof of Solvency, finality is defined (by me) as the guarantee that once a Proof of Solvency is verified, the exchange can be considered solvent with overwhelming probability. The existing Proof of Solvency instances, generally, follows this scheme:

participant Bob
participant Alice
participant CEX

CEX->Public Bulletin Board: Liabilities State Commitment
CEX->Alice: π
CEX->Bob: π
Alice->Alice: Verify π
Bob->Bob: ...
Bob->Bob: ...

1. The CEX commits to the state of its liabilities
2. The CEX shares a proof to each individual user proving that:
- They have been included in the liabilities with some account data
- The liabilities state matches the commit published in step 1
- The assets of the CEX are greater than the liabilites
4. Each individual user verifies the proof to assess if they have been accounted for in the liabilities with the correct balance, namely the account data matches the combination of their username and their deposits on the CEX denominated in different currencies.

Or, quoting [Ji and Chalkias](https://eprint.iacr.org/2021/1350.pdf), *Most of existing schemes follow the same principle: a prover aggregates all of the user balances using some accumulator and consumers can verify balance inclusion in the reported total amount. This process is probabilistic and the more the users that verify inclusions, the better the guarantee of a non-cheating prover.*

Summa, at the state of the art, follows a very similar approach too.

In such models there's no instant finality: from the point of view of the individual user, verifing the proof only tells that he/she has been accounted for correctly in the liabilities but doesn't give any guarantee that other users' account data haven't been manipulated.

Even worse, these models **do not provide finality at all**. The lack of a unified, public verification process means that it's impossible for a user to tell how many users correctly verified their inclusion in the liabilities accumulator. Therefore, it is impossible to collectively verify the solvency of the exchange with overwhelming probability, namely achieving proof of solvency with **finality**

Considering it's unlikely for all users of the CEX to verify their proof, according to [Ji and Chalkias Failure Probability - section 5](https://eprint.iacr.org/2021/1350.pdf), assuming a user base of 150𝑀 only 0.05% users verifying their proofs can guarantee an overwhelming chance of detecting an adversarial CEX manipulating 0.01% accounts. This is discussed more in depth in [Failure Probability](/pcGLBNa1TUSUrG178YZ6tQ)

Since the verification of the proof happens off-chain, the information of how many users performed a successful verification is not of public domain. Therefore a user **won't ever achieve high confidence that an exchange is indeed solvent**, even if they all successfully verified their individual proof.

## Commit-verify scheme

To solve the issue, Summa makes use of a **commit/verify** design. After the CEX commits to its liabilities state, the users have a time window where they can commit their account data to a blockchain. Since these get published on chain, these information are [common knowledge](https://en.wikipedia.org/wiki/Common_knowledge) across the users of the CEX and beyond.

Once the time window closes, the CEX will be required to generate a Proof of Solvency that checks the inclusion of all the committed account data within the liabilities tree **and** that the liabilites are less than the assets controlled by the CEX.

The proof gets submitted and automatically verified inside a smart contract. If the verification passes, **instant finality** proof of solvency is acheived. In particular, the level of confidence of the proof will be based on the number of users committing during the time window. The more users committed during the time window, the higher the confidence in the proof of solvency, as it decreases the chance that any manipulation of account data by the CEX would go undetected.

## Userflow

This section describes the userflow of such scheme. It focuses on the input and the actions required by the CEX and the users, rather than the underlying technology.

For the sake of the example we consider a CEX in which their users only trade ETH and BTC. The scheme can be trivially extended to every possible crypto assets. A Smart Contract (SummaSC) deployed on Ethereum (or related L2s) will be used for verification of the Proof of Solvency, independently of the type of crypto assets.

Note that **proof of solvency** refers to a snapshot in time. `t` refers to moment in time in which the state of the exchange liabilities and assets is snapshotted. In particular, `t` is a UNIX time stamp used as a snapshot for its liabilities; `eth_block_hash` and `btc_block_hash` represent the hashes of the latest blocks available at `t`.

participant Alice
participant CEX
participant SummaSC

CEX->CEX: Build MST 
CEX->SummaSC: MST Root + Round Info
note over Alice,SummaSC : Commit Time Period Starts
CEX->Alice: Signed Account Data 
Alice->SummaSC: Commit SAD
CEX->Alice: Incentive
note over Alice,SummaSC : Commit Time Period Ends
CEX->SummaSC: Proof of Solvency
SummaSC->SummaSC: Verify POS

1. The CEX extracts all the users' entries from their database `username -> (balanceETH, balanceBTC)`, and build a [Merkle Sum Tree](#Merkle-Sum-Tree) (MST) out of it. The MST represents the state of the liabilities of the CEX at `t`.

**This process is done internally by the CEX, the MST is never shared to the public**

`db.csv`

| username | balanceETH | balanceBTC|
| -------- | ---------- | --- |
| alice | 3223 |155 |
| bob | 100234 |200 |
| carl | 42069 |345995 |

It is important here to use some data that maps to a unique information about a specific user (such as an email or username) as a key of the database. If a generic ID `23432` is used as a key to identify a user, a malicious CEX can reuse the entry for two different users in the case they happen to have the same `balanceETH` and the same `balanceBTC`. More on that in [Broken Proofs of Solvency in Blockchain Custodial Wallets
and Exchanges - section 4.3](https://eprint.iacr.org/2022/043.pdf).

This step doesn’t require auditing or oversight. It also doesn't include any usage of zk proof. Any malicious operation that the CEX can perform here, such as:

- adding users with negative balances
- excluding users
- understating users’ balances

will be detected when the `proof of solvency π` is submitted on-chain for automatic verification. More on that in [Adversarial Scenario](#Adversarial-Scenarios)

2. The CEX commits the state of its liablities on-chain. In particular, the root of the `mst` gets submitted on-chain to the Summa Smart Contract. Note that this commitment doesn't reveal any information about the users' account data, the number of users or the total liabilties of the CEX.

This action kicks off a proof of solvency round. Together with the `mst` root the CEX needs to commit to:
- `t`
- `eth_block_hash`
- `btc_block_hash`
- `signing_public_key` that will be used in the next step
- `commit_time_period_end` identified by an ethereum block hash

Note that the signing key used here doesn't need to be any of the keys used by the CEX to store assets. The role of this key is only to sign messages to be shared with the users and can be safely thrown away at the end of the flow.

3. The commit time period starts. In this phase the CEX shares (for example via email) to each user their Signed Account Data (SAD). These data must be signed using the public key committed in phase2. The account data are snapshotted at time `t`. For example in the case of Alice, the exchange would need to perform the following action:

    account_data = ["alice", "3223", "155"]
    sad = ECDSA.sign(account_data, signing_private_key)

4. Once a user receives their SAD, they need to check:
- the account data match their account data at time `t`.
- the account data have been signed using the `signing_public_key` committed in step 2

This check has to be performed off-chain.

    account_data = ["alice", "3223", "155"]
    sad = ECDSA.verify(account_data, signing_public_key)

If one of the checks fail, the user should raise a flag since it is an indicator that the CEX manipulated the liabilities state. **It's worth noting that in this design, spotting a malicious exchange is as simple as verifying the validity of a digital signature**.

Now the user can **freely** and **permissionlessly** decide whether or not committing their SAD on-chain in exchange for an incentive paid by the CEX.

By publicly committing their SAD, the user is not sacrificing any privacy related to their personal data. That's because the message being signed is an hash of the account data `H(my_maccount_data)` and, even if shared publicly, this doesn't reveal any information about the user `account_data = Alice, BTC=2, ETH=0.001, DOT=5...`. Bruteforcing the hash seems unfeasiable considered the many possible combinations of usernames and related balances denominated in different currencies.

Note that the CEX would be able to tell whether a committed SAD belongs to a user or another. But this is not a problem: since the liabilities state has already been committed in step 2, the CEX can no longer manipulate it in order to exclude users who hasn't committed their SAD on-chain.

Since the CEX is able to tell who commited their SAD, it can also send an incentive to the user that performed this action, for example by adding some cryptocurrencies to their CEX balance.

5. After the commit time period finishes, the CEX has to generate the `proof of solvency π` and submit it on chain to the SummaSC for verification. The proof of solvency, if verified, attests that:
- The CEX controls some assets
- The assets of the CEX are greater than its liabilities. In this case, solvency here is defined on a 1:1 assets basis. Namely $ETHAssets \geq ETHLiabilities$ and $BTCAssets \geq BTCLiabilities$.
- All the user that committed their SAD in phase 4, have been correctly included in the Liabilities Merkle Sum Tree.

In order to do so, the CEX will need to assemble the list of their public keys together with a signature of an arbitrary message `m` and add them to a csv file.

`eth.csv`

| pubKey | signature |
| -------- | ---------- |
| 0x123 | 0xdaf23784 |
| 0x456 | 0xfff99999 |
| 0x789 | 0xabc00111 |

`btc.csv`

| pubKey | signature |
| ---------------------------------- | ---------- |
| 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa | 0x9543aaaa |
| 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2 | 0x54432ffa |
| 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy | 0xdddaaaa9 |

    let π = gen_proof(mst, btc.csv, eth.csv, eth_block_hash, btc_block_hash, round_id);
    // Note that all the data committed at step 2 do not need to be passed 
    // to the api, as they can be retrieved from the summa smart contract 
    // using the round_id

`π` is a zero knowledge proof that gets verified inside a smart contract. If verified, the proof tells that, **according to the liabilities of the CEX snapshotted at time `t`, the users that commited their SAD during the commit time period, the BTC assets owned by the CEX at `btc_block_hash` and the ETH assets owned by the CEX at `eth_block_hash`**, the CEX is solvent.

In this scenario the data related to the public keys of the CEX (and therefore the amount of assets owned by the CEX) are revealed to the public (and stored in the smart contract).

Thanks to the properties of zero knowledge cryptography, the proof submitted on-chain doesn't reveal any information related to sensitive data of the CEX (and its users) to the public, such as:
- Individual user information such as their balances and usernames
- The total number of users
- The total amount of liabilities

Note that:

- A CEX able to verify their Proof of Solvency **only certifies that the CEX is solvent at snapshot in time `t`** and it doesn't tell anything about its solvency at `t+1`. That's why CEXes are encouraged to run Proof Of Solvency rounds on a weekly basis.
- An insolvent CEX won't be able to verify their Proof Of Solvency. Since an invalid proof of solvency would simply revert the transaction of the prover, users from the outside will only be able to tell that **no proof of solvency** has been submitted to the Smart Contract. In particular the smart contract will consider a time window of a day after `commit_time_period_end` in which the CEX can submit a valid zk Proof Of Solvency. Therefore, the user can safely consider that the CEX is insolvent if no proof has been submitted to the summaSC after this time window expires.

## Summa V1 Tech

### Merkle Sum Tree

A Merkle Sum Tree is a binary Merkle Tree with the following properties:
- Each entry of a Merkle Sum Tree is a pair of a username and a balance.
- Each Leaf Node contains a hash and a sum. The hash is equal to H(username, balance). The sum is equal to the balance itself.
- Each Middle Node contains a hash and a sum. The hash is equal to H(LeftChild.hash, LeftChild.sum, RightChild.hash, RightChild.sum). The sum is equal to the sum of the sums of its children.
- The Root Node represents the committed state of the Tree and contains the sum of all the entries' balances.


The same structure can be adapted to support multi assets, for example in the case of support balances denominated in ETH and BTC, the `mst` would look like this:


### Smart Contract

The Summa SC will have the following pseudocode structure

contract SummaSC {

    uint public ROUND_ID;
    
    struct RoundInformation {
        bytes32 mstCommitment;
        bytes32 t;
        bytes32 ethBlockHash;
        bytes32 btcBlockHash;
        bytes32 signingPubKey;
        bytes32 commitTimePeriodEnd;
    }
    
    mapping(uint => RoundInformation) public rounds;
    
    mapping(uint => bytes32[]) public userSADCommitments;
    
    mapping(uint => bytes32 => bool) public hasBeenCommittedForRound;

    struct PublicInput {
        bytes32[] cexBTCPubKey;
        bytes32[] cexETHPubKey;
        bytes32[] cexBTCBalances;
        bytes32[] cexETHBalances;
        bytes32 contentData;
        bytes32 mstRoot;
        bytes32[] accountDataHash;
        bytes32 btc_block_hash;
        bytes32 eth_block_hash;
        bytes32 t;
        bytes32 roundId;
    }
    
    function kickOffRound(
       RoundInformation memory roundInfo 
    ) {
        rounds[ROUND_ID] = roundInfo;
        ROUND_ID += 1
    }
    
    function collectUserCommit(
        bytes32 accountDataHash,
        bytes32 SAD,
        uint roundId
    ) {
        
    // Ensure that the roundId exists
    require(rounds[roundId].commitTimePeriodEnd != 0, "Invalid roundId");

    // Ensure that this SAD has not been committed yet for this round
    require(hasBeenCommittedForRound[roundId][SAD] == false, "SAD has already been committed for this round");

    // verify that SAD is equal to ECDSASign(signing_public_key, accountDataHash) 
    bytes recoveredPubKey = ecrecover(accountDataHash, SAD);
    bytes expectedPubKey = rounds[roundId].signingPubKey;
    require(recoveredPubKey == expectedPubKey, "Invalid SAD");
                        
    userSADCommitments[roundId].push(accountDataHash);
    hasBeenCommittedForRound[roundId][accountDataHash] = true;
    }
    
    function verifyProofOfSolvency(
      PublicInput memory publicInput,
      bytes32[] memory proof  
    ) public {

      // Retrieve the round information
      RoundInformation memory roundInfo = rounds[publicInput.roundId];

      // check that the balances of each public key is matching
      // getEthBalanceAtBlock can be implemented using Axiom
      for (uint i = 0; i < publicInput.cexETHPubKey.length; i++) {
        publicInput.cexETHBalances[i] = getEthBalanceAtBlock(publicInput.cexETHPubKey[i], publicInput.eth_block_hash); 
      }

      // getBTCSumAtBlock needs to be implemented maybe using some Bridge or Oracles
      for (uint i = 0; i < publicInput.cexBTCPubKey.length; i++) {
        publicInput.cexBTCBalances[i] += getBTCSumAtBlock(publicInput.cexBTCPubKey[i], publicInput.btc_block_hash); 
      }

      // Check that content data is equal to m where m is "summa proof of solvency {ROUND_ID}"
      bytes32 expectedContentData = keccak256(abi.encodePacked("summa proof of solvency ", publicInput.roundId));
      assert(publicInput.contentData == expectedContentData);

      // check that t from public input matches the one associated within the rounds mapping associated to that roundID 
      assert(publicInput.t == roundInfo.t);

      // check that btc_block_hash from public input matches the one associated within the rounds mapping associated to that roundID 
      assert(publicInput.btc_block_hash == roundInfo.btcBlockHash);

      // check that eth_block_hash from public input matches the one associated within the rounds mapping associated to that roundID 
      assert(publicInput.eth_block_hash == roundInfo.ethBlockHash);

      // check that mstRoot from public input matches the one associated within the rounds mapping associated to that roundID 
      assert(publicInput.mstRoot == roundInfo.mstCommitment);

      // Check that btc_block_hash and eth_block_hash are the latest block hash available at unix time stamp t. Maybe use an oracle for that
      assert(isLatestBlockAtTime(publicInput.btc_block_hash, publicInput.eth_block_hash, publicInput.t));
    
      // Check if the proof is submitted within the commit time period plus a day
      uint dayInSeconds = 24 * 60 * 60;
      require(block.timestamp <= roundInfo.commitTimePeriodEnd + dayInSeconds, "Proof of solvency submission time has expired");

      // Verify zk proof (the proof verification function needs to be implemented in a separate autogenerated contract)
      assert(verifyZkProof(proof, publicInput));

    }
}

Note that this is likely to be a big proof in terms of size and proving time. Luckly enough, this needs to be performed only once per proof of solvency round.

### π Proof of Solvency

`π` is the proof of solvency that gets sent by CEX to the SummaSC Verifier.

The prover is built using a zkSNARK that has the following pseudocode structure:

circuit ProofOfSolvency {

    pub input cexBTCPubKey[]
    priv input cexBTCPubKeySigs[]
    pub input cexBTCBalances[]
    
    pub input cexETHPubKey[]
    priv input cexETHPubKeySigs[]
    pub input cexETHBalances[]
    
    // message to be signed such as "summa proof of solvency round 1"
    pub input contentData
        
    pub input mstRoot
    
    pub input accountDataHash[]
    priv input accountEthBalance[]
    priv input accountBtcBalance[]
    priv input accountSiblingHashes[][]
    priv input accountSiblingBtcSums[][]
    priv input accountSiblingEthSums[][]

    pub input t
    pub input btc_block_hash
    pub input eth_block_hash
    
    pub input roundId

    // check 1: signatures verification
    cexBTCPubKeySigs[i] === ECDSASignVerify(cexBTCPubKey[i], contentData)
    cexETHPubKeySigs[i] === ECDSASignVerify(cexETHPubKey[i], contentData)
    
    // check 2: membership check    
    verifyMembership(accountDataHash[i], accountEthBalance[i],  accountBtcBalance[i], accountSiblingHashes[i][], accountSiblingBtcSums[i][], accountSiblingEthSums[i][], mstRoot)
    
    // check 3: verifies that sums never overflows 
    RangeCheck254(accountEthBalance[i])
    RangeCheck254(accountBtcBalance[i])
    RangeCheck254(accountSiblingBtcSums[i][j])
    RangeCheck254(accountSiblingEthSums[i][j])
        
    // check 4: No overflow happening when summing CEX balances
    RangeCheck252(cexETHBalances[i])
    RangeCheck252(cexBTCBalances[i])
    
    // calculates rootBalanceEth and rootBalanceBTC (to be performed only once, not for every i)
    
    // check 5: Assets greater than liabilities
    ΣcexETHBalances[i] >= rootBalanceEth
    ΣcexBTCBalances[i] >= rootBalanceBTC
        
    // Dummy square to prevent tampering on t, btc_block_hash, eth_block_hash and roundId.
    // Actually, this is not needed in Halo2
}

#### How does the proof grow?

- Each proof of inclusion (`membership check`) is equal to #LEVELS hashing. Where `LEVELS = log2(n)` where `n` is the number of users of the CEX
- The number of `membership check` to be performed grows linearly with the number of users that committed to their SAD on-chain.
- The number of `ECDSASignVerify` operation grows linearly with the number of wallets owned by the exchange. This operation can be offloaded to the smart contract if it's to intense to process inside a SNARK.
- `check 5: Assets greater than liabilities` needs to be performed ond only once, no matter the number of users that committed to their SAD.

## Adversarial Scenarios

To finish let's consider the cases in which a malicious CEX is trying to create a valid proof of solvency even though they are not solvent at all. They can do that in two different ways: overstating their assets or understating their liabilites.

### Overstating the assets

| Attack Vector | Solution |
| ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| The CEX claims control over public keys they do not actually control | They wouldn't be able to generate a signature that proves ownership of these public keys and therefore won't be able to generate a valid `π` |
| The CEX cooperates with another CEX in order to share a signature when generating their proof of assets | In V1 the public keys are public so everyone will be able to tell that the same public key has been claimed as owned by two different CEXes. In V2 this risk will be mitigated by the nullifier |
| The CEX moves funds between blockchains and, since the blockchain are not synced together, they can: claim they own a certain amount of BTC at `btc_block_hash`, move out all their funds from BTC to ETH after `btc_block_hash`, claim they own a certain amount of ETH at `eth_block_hash`. | In V1 the public keys are public so everyone is able to spot suspect transfers coming in or out the wallets owned by the CEX have been performed around `eth_block_hash` and `btc_block_hash`. The solution to this issue becomes a bit more tricker in V2 |
| The CEX commits the liabilities snapshotted at `t` and proves its solvency against the assets at a `eth_block_hash` delayed in the future or in the past | This won't be allowed since the values `t`,`eth_block_hash` and `btc_block_hash` are committed in step 2 and the smart contract is able to spot any discrepancy |

### Understating the liablities

| Attack Vector | Solution |
| ------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| The CEX excludes a user from the liabilities | If the user commits to the SAD on-chain, the CEX won't be able to generate a valid proof of solvency. In fact, because of the smart contract rules, the CEX must prove this against **all** the user SAD commitments |
| The CEX includes a user within the liabilities with a decreased balance and shares a SAD with the correct balance to the user | Same as above |
| The CEX includes a user within the liabilities with a decreased balance and shares a SAD with the decreased balance to the user | The user is able to spot a discrepancy between their actual balance and the one declared in the SAD. This will allow the user to publicly raise a flag. |
| The CEX adds fake users with a negative balance to the `mst`. | Within zk circuits, all the negative input are converted into Field Elements that are only positive numbers. Therefore each negative balance is turned into a (very large!) positive one. In this case, the malicious CEX ends up overstating their liabilities, which is against their interest |
| The CEX adds fake users to the `mst` | By adding fake users with positive balance, the malicious CEX ends up overstating their liabilities, which is against their interest |
| The accumulated balance overflows the prime in the π generation, resulting in a understated liabilities | One of the constraint of the circuit is that the accumualated balances should never overflow the prime modulus. This is achieve by constraining the indiviudal balances to be in a certain BITS range. For example considering a modulus prime that is between 254 and 255 BITS, the range check on the individual balances can be safely set at 254 bits to avoid any overflow |
| The CEX shares the same proof for different users, resulting in a understated liabilities |This scenario can happen in the case in which there are two users with the exact same balance across the different currencies (which is already unlikely) **and** the CEX is using a system to identify the users in a proof of solvency which is not based on a unique identifier. For example using a generic ID for a user can lead to this attack. Instead, using a unique identifier such as `username` or `email` would avoid that.|
| The CEX generates a Proof of Solvency against a `mst` commitment different from the one committed in step 1 | The proof won't verify since the `mst` root commitment is a public input of the zk proof and the contract will check that it matches the one committed when the proof of solvency round was kicked off.

## Open Issues

- I'm not sure that users of CEX are able to submit an on-chain transaction. Maybe it can be facilitated using a relayer.
- How to design the incentive structure? A base prize for everyone that performs the SAD commitment, a pie that gets shared across every user who committed their SAD or a lottery-style prize?
- Dispute Resolutions, there may be cases in which the SAD received by the user doesn't match their actual balance. In that case the user should raise a flag and open an issue. As pointed out in [Broken Proofs of Solvency in Blockchain Custodial Wallets and Exchanges - section 4.6](https://eprint.iacr.org/2022/043.pdf) *there is no mechanism or protocol in place to resolve a dispute between an exchange and a user against a third party judge*
- Private verification pattern. In the proposed scheme the CEX get to know which users committed their SAD. Since for each proof of solvency round, not all users will commit their SAD, if a malicious CEX learns that some users never commits their CAD, these users can safely be omitted fron the liabilities tree in the next solvency round. Therefore it would be nice to hide users’ verification pattern from the prover.