Source: https://vitalik.ca/general/2022/11/19/proof_of_solvency.html
For simpliciy, we'll only consider ETH for now. So, CEX wants to prove that it has
List of all users along with their eth balance with the CEX:
This list includes all the users. All
- Create a vector from
$U$ :$$V = [hash(u_0,salt_0),a_0,...,hash(u_{2^l-1}, salt_{2^l-1}),a_{2^l-1}]$$ Note that the length now is$2^l+1$ . - Create
$P(x)$ as the langrange polynomial to commit:$P(\omega^i) = V_i$ .$comm(P)$ is the KZG commitment. - To each user u_i, send the opening proof of
$V_{2i},V_{2i+1}$ (user hash and balance).
We need to prove that all
This can be done via a SNARK:
Define another polynomial
Some assumptions:
- The maximum user balance is under
$2^{k-1}$ (so fits in$k-1$ bits). - The total number of users is
$2^l$ . -
$z$ is is an order$2^l\cdot k$ -th root of unity (reason will be clear eventually).
Consider the sequence of tuples:
Every
Consider any tuple
- The first element is always
$0$ . - The subsequent elements are expanded by a bit(
$0$ or$1$ ) from the previous element except the last element. - The second to last element is equal to the
$a_i$ .
This ensures that
The constraint on the last element in each tuple ensures that the sum of all user balances is
The last element of the last tuple has to be
- Derive the average user balance
$\overline{a}$ :$\frac{a}{2^l}$ . - Define
$I(z^{k-1})$ , the last element of the$0_{th}$ tuple as$a_0-\overline{a}$ : - Define
$I(z^{(i+1)k-1})$ , last element of$i>0$ tuple as:$$a_i+ (last\ element\ of\ the\ previous\ sequence)-\overline{a}$$
With this, our equations become:
With these equations, we can create a SNARK out of it in Halo2.