What is a Proof of Reserves?

At its heart, Proof of Reserves (PoR) is a crucial system designed to show that a crypto platform genuinely holds the funds it owes to its users. It's how exchanges and custodians can prove, using strong cryptographic methods, that they have enough assets to cover all customer deposits.

Think of it this way: PoR is about enabling transparency. It's a way for platforms to provide clear, verifiable evidence of their financial health. For users, it means gaining confidence that their funds are secure on the platforms they use.

Historically, traditional ways of proving reserves often had drawbacks. They might reveal too much sensitive information about the platform and rely heavily on external auditors without a direct user verification method.

We from OtterSec, in partnership with Backpack, just developed a Proof of Reserves system that can be used to prove CEX solvency. Our Zero-Knowledge Proof of Reserves (PoRv2) was based on OKX Proof of Reserves algorithm since it was the fastest and most efficient one known so far. We also use recursive plonky2 as the algorithm for zero-knowledge proving, but we made some improvements to the circuits for more transparency and verifiable information on the user side, eliminating the need to trust the audit company.

In addition, we also created and open-sourced a PoR verifier server that receives the proofs and validates them.

Why do we use ZK for PoR?

Proving reserves is crucial, but it presents a unique challenge for any platform holding user funds: how do you publicly prove solvency without also exposing sensitive user balance information or revealing proprietary financial details? This is where Zero-Knowledge Proofs (ZKPs) become game-changers.

Simply put, a Zero-Knowledge Proof allows one party to prove to another that a statement is true without revealing any information beyond the validity of the statement itself. Imagine proving you know a secret password without actually telling anyone the password. You confirm you possess the knowledge, but the secret remains yours.

In the context of Proof of Reserves, ZKPs are perfectly suited to solve the privacy paradox. They enable a platform to prove two important things cryptographically:

1. Sum proof: The exchange liability is equal to the sum of all users' balances. (e.g: btc_liability = user1_btc + user2_btc + user3_btc + ...).
2. Non-negativity: All users have a positive net balance. This ensures that the sum proof is not tampered with by users with negative net balances. A user can have negative asset balances (e.g., borrowing BTC) but only if collateralized with other assets.

It is worth noting that we cannot guarantee that all users were included in the ZK analysis. Therefore, if we only used ZKPs to prove those two statements, the exchange could tamper with the sum proof by excluding users from the PoR. That's why we also use a Merkle tree to prove inclusions.

What is a Merkle Tree and how does it help in a PoR?

A Merkle tree is a tree data structure where each leaf node is a cryptographic hash of an individual piece of data (like a user's balance), and every non-leaf node is a cryptographic hash of its child nodes. This structure allows for the entire dataset to be summarized by a single, unique hash at the top, called the Merkle Root.

In the PoR, we can use a Merkle tree to verify the inclusion of each user in the Proof of Reserves. It works like this:

1. The Merkle tree is generated using the leaf nodes as the hashes of the user information (e.g., sha256({id: 1, balances: {"BTC": 0.1, "ETH": 0.2, ...}}));
2. The Merkle tree is made public;
3. Each user can download the Merkle tree and check if their account was included by hashing their account information and checking if the hash is one of the leaves;

In other words, this use of the Merkle tree allows users to easily verify that their individual balance was included in the overall total.

OtterSec PoRv2

We just open-sourced our Proof of Reserves code (PoRv2), which uses the plonky2 ZK algorithm to create a Merkle tree and a final ZK proof that recursively verifies smaller sum and non-negativity proofs.

We named it PoRv2 because we already had a version based on Vitalik's proof of solvency, which was not optimal.

Non-negativity Proof

In our non-negativity proof, the circuit receives the asset balances of each user and the price of each asset. With these inputs, it calculates the account's USD balance and checks if it is greater than 0.

We also check for overflows during summation to prevent tampering in the final result.

Sum Proof

The sum proof verifies a public circuit input that was calculated by summing up all user balances of each asset. (e.g., BTC final: user1_btc + user2_btc ...). Note that each asset's final sum is not USD-based; we calculate the final balance using the asset balance itself.

What are the OtterSec PoRv2 key points?

1. Transparency: It is possible for the exchange to safely disclose the entire Merkle tree so users can verify it without the need for an external auditing company. Also, the code allows asset price commitments and verifications.
2. Time-efficiency: We were able to reduce the amount of time to prove by more than 100 times from our previous version by generating proofs for 750,000 users within 8 minutes using a Mac M3 Pro. Check our benchmark.
3. Memory-efficiency: We also were able to reduce the amount of RAM needed to prove the liabilities of millions of users. Now, we are able to use machines with 16GB.
4. Small-proofs: We were able to reduce the final proof to less than 500KB and each inclusion proof to ~52KB. The only big file that we need to store is the Merkle tree, which doesn't consume more than 200MB if the PoR parameters are finely adjusted. Additionally, instead of storing each inclusion proof in a static file, we provide an efficient method to generate inclusion proofs on demand, eliminating the need for the exchange to store millions of files and conserve disk space and resources.
5. Privacy: We use many cryptographic mechanisms to ensure that the user balances and other private information are kept safe and secret.

ZK Circuits

We use two different ZK circuits to generate the final proof:

1. Batch circuit
2. Recursive circuit

With those two circuits, we can generate the proofs recursive tree:

Note: We are using 512 as BATCH_SIZE and 8 as RECURSIVE_SIZE which indicates how many children each circuit has. This is easily adjustable in the code, and the optimal configuration will depend on the amount of accounts being proved in the PoR.

Note 2: We add empty proofs as padding to chunks that don't have the correct length.

Each non-leaf node in this tree is a ZK proof, which is generated using the related circuit; each circuit also generates the Merkle tree hash of each node, which is included in the Merkle tree.

Leaf Nodes

The leaf nodes are the hashes of the account information. It is calculated in this way:

$h=Poseidon(asset\_balance{s}_0||asset\_balance{s}_1...||SHA256(user\_id)||user\_nonce)$

In other words, all balances are concatenated with the hashed user ID (which can be a uuid, a username or an incremental ID) and with a nonce. The nonce is a random number that serves as a security measure against attackers who could brute-force the hash to find out other users' balances. Since the Merkle tree is a public proof, we need to be careful against these types of data leaks.

Batch Circuit

The batch circuit is the first proven circuit in the PoR algorithm. It receives the account's information (grouped in 512) and generates the ZK proof with those constraints:

Public Inputs

• Asset prices in USD
• Merkle tree hash
• Summed asset balances

Private Inputs

• Users balances
• Merkle tree leaves hashes

Constraints

• $account\_equit{y}_i==\Sigma account\_asset\_balance{s}_i[asset\_num]\ast asset\_prices[asset\_num]$
• $account\_equit{y}_i>=0$ (non-negativity)
• $total\_asset\_balance[asset\_num]==\Sigma account\_asset\_balance{s}_i[asset\_num]$ (sum proof)
• $merkle\_tree\_hash==Poseidon(has{h}_0,has{h}_1,...,has{h}_{511})$ (merkle tree hash)
• $account\_asset\_balance{s}_i[asset\_num]<MAX\_SAFE\_INT/512$ (overflow check) --> overflow check is made this way for performance (note that 512 is actually the BATCH_SIZE)

Here is a visual scheme of the inputs of the batch circuit + how user hashes are generated:

Recursive Circuit

Recursive circuits get eight subproofs as input, verify if all the asset prices are the same, and calculate the summed balances and Merkle hash. Here are the constraints.

Public Inputs

• Summed asset balances
• Asset prices
• Merkle tree hash

Private Inputs

• 8 subproofs

Constraints

• $total\_asset\_balance[asset\_num]==\Sigma subproo{f}_i.public\_input.asset\_balances[asset\_num]$ (sum proof)
• $asset\_price[asset\_num]==subproo{f}_i.public\_input.asset\_prices[0]$
• $asset\_price[asset\_num]==subproo{f}_i.public\_input.asset\_prices[asset\_num]$ (verifies if all asset prices are the same)
• $merkle\_tree\_hash==Poseidon(has{h}_0,has{h}_1,...,has{h}_{31})$ (merkle tree hash)
• checks if each sum is overflowing by checking if the sum of two positive numbers results in a negative one (overflow check)

Here is a visual scheme of the inputs of the recursive circuit. Note that this tree only has three levels (L1, L2, L3). Depending on the number of users, it may have more recursive levels:

Global Proof and Inclusion Proofs

Proving

After proving all batch circuits and all recursive circuits, we have the final proof (which is the ZK proof of the recursive tree root), the entire Merkle tree, and the user nonces. In our code, it is serialized to merkle_tree.json, final_proof.json, and private_nonces.json files.

Using the ZK proof and the Merkle tree, we can already prove the sum of the asset balances and their non-negativity; we refer to this as the "global proof."

For the user inclusion proofs, we get the Merkle tree, the user asset balances, the identification hash, and the nonce to bundle it in one proof file (inclusion_proof_<id>.json). We bundle only a part of the Merkle tree to the inclusion proof file to make the proof smaller.

Verifying

Global Proof

To verify the global proof, the code deserializes the merkle_tree.json and the final_proof.json files and performs these checks:

1. Validate if the final proof was generated with a valid and trusted circuit.
2. Verify the ZK final proof.
3. Verify if asset prices are valid. (It doesn't verify if it matches the real price; you need to do it manually. It only verifies if decimals are valid.)
4. Verify if the Merkle tree root hash is the same as the final proof merkle_tree_hash public input. This ensures that the merkle_tree.json and final_proof.json are linked (they belong to the same global proof).
5. Verify the entire Merkle tree by hashing all the nodes again, starting with the batch circuit, since the verifier won't have the necessary information to hash the leaves again (for privacy). This ensures that the tree was not tampered with.

Inclusion Proof

To verify the inclusion proof, the code deserializes the inclusion_proof_<id>.json file and also the final_proof.json. After that, it performs these checks:

1. Verify the ZK final proof.
2. Verify if the Merkle tree root is the same as in the final proof.
3. Recalculate the user-related node leaf hash.
4. Verify a partial Merkle tree using the recalculated hash (it doesn't contain all the leaves).

PoR Verifier Server

To automate the verification process, we created a verifier server that the exchange can submit the proofs into. Once submitted, the proof is validated and added to the database.

Once the proof was added, any user can enter the website and see its information (see backpack's example):

Here is a breakdown of what fields represent and why they are required:

• Status --> verifies if the proof is valid, ensuring that the information has not been tampered with.
• Proof Timestamp --> when the proof was generated by the exchange.
• Verify Timestamp --> when the proof was verified by the PoR server.
• Proof File URL --> the URL where the proof was downloaded from. Users can download it to verify the proof's validity themselves.
• Prover Version --> the version of PoRv2 used. Using different versions for proving/verifying can result in errors due to ZK circuit discrepancies. Therefore, if you are going to verify the validity of the proof yourself, ensure that you download and use the same prover version as the proof.
• File Hash (SHA256) --> since we only store the URL of the proof, it can be maliciously changed after our verification. SHA256 can be used to prove if the file was modified after the verification. If you are going to verify the proof by yourself, check if the downloaded zip file matches the hash shown on the website.

Also, you can check the exchange's liabilities on the website:

These are the amount of assets that the exchange should have in their reserves to be solvent on each asset. You can match if they have it by checking their reserve wallets on blockchain. You can see backpack's wallets in https://backpack.exchange/reserves and our verifier server for backpack at https://backpack-por.osec.io/.

Self-verification

You, as a user, can verify both proofs by yourself, the inclusion proof to verify if you were included in the PoR total liabilities sum and the global proof to verify if the commitments provided by the exchange are valid.

How to verify if I was included?

If you are a user and want to do the self-verification of inclusion, you will need to follow these steps:

1. Download the PoRv2 executable from our github.
2. Download the inclusion and the final proof files from the exchange (inclusion_proof_<id>.json and final_proof.json) and put the files in the same directory as the PoRv2 app.
3. Open the terminal and execute this: ./plonky2_por verify-inclusion.

This will verify if the proofs are valid and show your asset balances. You will need to verify manually that the balances are correct. Remember that the proofs are not calculated in real-time; you must verify if the balances were correct at the proof generation date. Here is an example of a valid proof being verified:

[!] The following information was used to generate the proof, please manually verify if they are correct:
[!] NOTE: This is not real-time information, verify if the information is correct relative to the time of the proof generation
[!] NOTE2: Some asset balances was rounded by some decimals, verify if they are close enough to the original balance
======================
Proof generation date: 2025-02-22 19:59:59 UTC
Proof generation timestamp (ms): 1740254399944
Number of accounted assets: 100

-----Asset balances-----
ETH: 0
BTC: 1.2
USDC: 0
...
======================
[!] Verifying global proof (trusting circuit data inside the file)...
[+] Global proof is valid!
[!] Verifying inclusion proof...
[+] Inclusion proof root hash is valid! The user is included in the merkle tree!
[+] Successfully verified inclusion proof for file: inclusion_proof_00476816e43cf2efffdabdda7f55c5203bc9e28382c551f83931de02fd364a25.json

[+] All inclusion proofs are valid!
[+] Finished in 13.731875ms!

How can I verify the global proof?

If you want to verify if the global proof is valid, you just need to follow these steps:

1. Download the PoRv2 executable from our github.
2. Download the merkle_tree.json and the final_proof.json files and put them in the same directory as the PoRv2 app. You can download those files from our PoR verifier server (download the zip file and unzip it).
3. Open the terminal and execute ./plonky2_por verify-inclusion. This might take a while to verify since it needs to deserialize a big file and verify the final proof circuit (which involves rebuilding it).

This will verify the global proof and print the asset prices to be manually verified. Note that the asset prices shown are not real-time; you must match them to the price on the proof generation date and time.

[!] Verifying the proof of reserves...
[!] The following information was used to generate the proof, please manually verify if they are correct:
[!] NOTE: This is not real-time information, verify if the information is correct relative to the time of the proof generation
[!] NOTE2: Asset prices was rounded by some decimals, verify if they are close enough to the original price
======================
Proof generation date: 2025-02-22 19:59:59 UTC
Proof generation timestamp (ms): 1740254399944
Number of accounted assets: 100

-----Asset prices-----
BTC: US$ 95000
ETH: US$ 2402.48
...
======================

When verification is completed, and all proofs are valid, the system will print the summed balances of each asset. These are the liabilities of the exchange, which you can use to check if they have reserves to cover it.

[!] Rebuilding root circuit... This might take several minutes...
[+] Root circuit rebuilt successfully!
[!] Verifying final proof...
[+] Proof is valid!
[!] Verifying asset prices...
[+] Asset prices are valid!
[!] Verifying asset decimals...
[+] Asset decimals are valid!
[!] Verifying merkle tree root hash...
[+] Merkle tree root hash is valid!
[!] Verifying merkle tree...
[+] Merkle tree is valid!

[!] The following information is the final needed asset reserves, which was validated by the Zero-Knowledge proof
[!] NOTE: This is not real-time information, the information is relative to the time of the proof generation
[!] NOTE2: We cannot guarantee that all users were included in the proof, but you can check if you were included by verifying the inclusion proof
======================
Proof generation date: 2025-02-22 19:59:59 UTC
Proof generation timestamp (ms): 1740254399944
Number of accounted assets: 100

-----Asset reserves-----
BTC: 1.2
ETH: 5.4
...
======================

[+] All proofs are valid!
[+] Finished in 4.455745214s!

Conclusion

In conclusion, Proof of Reserves serves as a crucial mechanism for crypto platforms, enabling them to demonstrate solvency and gain user trust in a transparent manner. By employing zero-knowledge proofs, platforms can achieve this transparency without exposing sensitive user data, effectively proving total liabilities and ensuring non-negativity while preserving privacy. Our system further refines this process, boosting efficiency and eliminating the need for manual verification.

We are currently working with Backpack to implement this algorithm in production to generate and verify proofs every 24 hours. This marks a significant advancement toward establishing a real-time Proof of Reserves system, particularly given that it offers increased transparency, which is a step forward in reducing the need for external audit companies, as users will be able to verify everything themselves.

For more information about how Backpack Exchange implements Proof of Reserves in practice, you can read their detailed article: Proof of Reserves at Backpack Exchange: Real Transparency, ZK Verified.