Proof Of Liabilities
How does Proof-of-Liabilities work?
Each user of the exchange has their private balance information encoded in a leaf node of a Merkle tree. The value of the leaf node for each user is obtained by hashing their username and their list of balances. The user leaf nodes are arranged in a 4-ary tree, where the value of each parent node is obtained by computing the hash of the value of the 4 child nodes.
The Proof-of-Liabilities zk-SNARK takes as input a list of users and their liabilities at the exchange and executes the following steps:
It asserts that all user balances are nonnegative,
It computes the sum of all user balances,
It computes the Merkle tree that aggregates user balances in the manner described above,
It reveals (to the top-level Solvency zk-SNARK) the computed user-balance sum and the value of the Merkle root node.
The user-balance sum is only revealed to the top-level zk-SNARK so that it can be compared against the assets held by the exchange. In particular, the exact values of the user-balance sum and the assets held by the exchange are not revealed by the top-level Solvency zk-SNARK.
On the other hand, the hash value of the Merkle root node is revealed by the top-level Solvency zk-SNARK so that each user of the exchange can independently verify that their balance was properly included and accounted for in the user-balances sum.
Specifically, as part of the ZeKnow Solv protocol, each user of the exchange is given a receipt, which is the sequence of node values from the user’s leaf node to the value of the root node. The user can independently verify that their balance was properly accounted for in the user-balances sum by checking:
That the balances encoded in their leaf node match their balances on the exchange,
That the hash of the nodes at each level of the Merkle branch matches the provided value of the parent node (i.e. check that they were given a valid Merkle branch).
How do I check that my receipt is a valid proof that my balances were included in the Proof-of-Liabilities protocol?
There are two steps you should take to check that your receipt is a valid proof that your balances were included in the Proof-of-Liabilities:
Verify that your username and balances included in the leaf node match your username and balances on the exchange. Details on this step are provided in an answer below.
Verify that the Merkle branch included in your receipt is valid, and that the final node in the branch matches the Merkle root associated with the corresponding proof. Details on this step are provided in an answer below.
We provide a website that you can use to automatically verify your receipts: https://solvenscan.io.
Sample code that you can use to verify your receipt manually can be found here: https://github.com/proven-dev/solvency/blob/main/verify_receipt.py
How is my account information encoded in a leaf node of the Merkle tree?
As part of the ZeKnow Solv protocol, you will receive a cryptographic receipt-of-inclusion for each proof published by an exchange that includes your balances. There are three components in the receipt that determine your leaf hash: your username, your list of balances, and a nonce. You should verify that the username field matches your username on the exchange (to ensure that the receipt is uniquely yours) and that the value of the listed balances match your balances on the exchange (to ensure that your balances were accurately counted in the sum of user balances). The nonce component exists in order to increasing the entropy of the information to be hashed. This ensures that no information is revealed about your account in the Merkle branch revealed to other users.
Your leaf hash is obtained from these three components via the following steps:
Compute the SHA512 hash of the concatenation of your username and the provided nonce.
Truncate the output of the hash to the 252 most significant bits to obtain your
account_id.Encode your account balances into BN254 field elements. The ZeKnow Solv protocol uses 42 bits to represent the balance of each token and it supports proofs for up to 18 distinct tokens, so we use three BN254 field elements to encode all user balances.
A user’s BTC balance is represented in Satoshis and is included in the least significant 42 bits of the first BN254 field element.
The ETH balance of a user is rounded up to the nearest 10^(-7) of an ETH and included in the 84th through 43rd bits of the first BN254 field element.
The space reserved for the remaining 16 tokens is currently set to 0.
Finally, the leaf hash value is computed by taking the arity-4 Poseidon hash of the values
[account_id, balance_elt1, balance_elt2, balance_elt3].
How do I check that the Merkle branch included in my receipt is valid?
The Merkle branch included in your receipt is a length n list of 4-tuples, where the k-th item in the list corresponds to the k-th level of the merkle tree (using the convention that the leaf nodes are included in the first level of the merkle tree) and the elements of each 4-tuple are your node value and your sibling node values.
To verify that your receipt is valid, take the following steps:
Verify that your leaf hash value is equal to one of the values in the first tuple in the list.
For each tuple in the list:
Compute the arity-4 Poseidon hash of all values included in the tuple
If you are not at the end of the branch: Verify that the output of the hash is equal to one of the values in the subsequent tuple in the list.
If you are at the end of the branch: Verify that the output of the hash matches the Merkle root.
We provide a website for verifying your receipts automatically: https://solvenscan.io.
Sample code for verifying your receipts manually can be found here: https://github.com/proven-dev/solvency/blob/main/verify_receipt.py
Last updated