# kzg-solvency

Witness table

- Note that I modified P a little. In this way it is easier to set certain constraints. Think about the witness table as chunks of 16 rows that only represent a single user over 2 columns.

| P | I |
| ----------------- | ---- |
| `H(Alice, 66466`) | 0 |
| 20 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 1 |
| 0 | 2 |
| 0 | 5 |
| 0 | 10 |
| 0 | 20 |
| 0 | -165 |
| `H(Bob, 82277`) | 0 |
| 50 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 0 |
| 0 | 1 |
| 0 | 3 |
| 0 | 6 |
| 0 | 12 |
| 0 | 25 |
| 0 | 50 |
| 0 | -300 |
| ... | ... |

### Constraint 1

We want to enforce that $I(x) = 0$ for all the xs included in the set $A$ such that $A = \{\omega^{16*0}, \omega^{16*1}, ..., \omega^{16*(n-1)}\}$. Where $n$ is the number of users. This can be translated into the following constraint:

$I(x) = Q_{1}(x) * Z_{1}(x)$

- $Z_{1}(x)$ is the vanishing polynomial built over the element of the set $A$ such that $Z_{1}(x) = (x - \omega^{16*0}) * (x - \omega^{16*1}) * ... * (x - \omega^{16*(n-1)})$.
- $Q_{1}(x)$ is the quotient polynomial obtained as result of dividing $I(x)$ by $Z_{1}(x)$

### Constraint 2

We want to enforce that $I(x) = P(\omega^{-13} * x)$ for all the xs included in the set $B$ such that $B = \{\omega^{16*0 + 14}, \omega^{16*1 + 14}, ..., \omega^{16*(n-1) + 14}\}$. Where $n$ is the number of users. This can be translated into the following constraint:

$I(x) - P(\omega^{-13} * x) = Q_{2}(x) * Z_{2}(x)$

- $Z_{2}(x)$ is the vanishing polynomial built over the element of the set $B$.
- $Q_{2}(x)$ is the quotient polynomial obtained as result of dividing $I(x) - P(\omega^{-13} * x)$ by $Z_{2}(x)$

### Constraint 3

We want to enforce that $(I(x) - 2 * I(\omega^{-1} * x)) * (I(x) - 2 * I(\omega^{-1} * x) - 1) = 0$ for all the xs included in the set $C$ such that $C = \{\omega^{(16*0) + 1}, \omega^{(16*0) + 2}, ..., \omega^{(16*0) + 14}, \omega^{(16*1) + 1}, \omega^{(16*1) + 2}, ..., \omega^{(16*1) + 14}, ..., \omega^{(16*(n-1)) + 1}, \omega^{(16*(n-1)) + 2}, ..., \omega^{(16*(n-1)) + 14}\}$. Where $n$ is the number of users. This can be translated into the following constraint:

$(I(x) - 2 * I(\omega^{-1} * x)) * (I(x) - 2 * I(\omega^{-1} * x) - 1) = Q_{3}(x) * Z_{3}(x)$

- $Z_{3}(x)$ is the vanishing polynomial built over the element of the set $C$.
- $Q_{3}(x)$ is the quotient polynomial obtained as result of dividing $(I(x) - 2 * I(\omega^{-1} * x)) * (I(x) - 2 * I(\omega^{-1} * x) - 1)$ by $Z_{3}(x)$

### Constraint 4

We want to enforce that $I(x) - I(\omega^{-16} * x) - I(\omega^{-1} * x) - K = 0$ for all the xs included in the set $D$ such that $D = \{\omega^{16*1 + 15}, \omega^{16*2 + 15}, ..., \omega^{16*(n-1) + 15}\}$. Where $n$ is the number of users. $K$ is the constant `total_users/total_count`. This can be translated into the following constraint:

$I(x) - I(\omega^{-16} * x) - I(\omega^{-1} * x) - K = Q_{4}(x) * Z_{4}(x)$

- $Z_{4}(x)$ is the vanishing polynomial built over the element of the set $D$.
- $Q_{4}(x)$ is the quotient polynomial obtained as result of dividing $I(x) - I(\omega^{-16} * x) - I(\omega^{-1} * x) - K = 0$ by $Z_{4}(x)$

### Protocol

#### Commitment Phase

participant CEX
participant Verifier

Verifier->CEX: Trusted Setup
CEX->Verifier: Com(I), Com(P), Com(Q1), Com(Q2), Com(Q3), Com(Q4)

#### Proof of User Opening

- Must be performed by the actual user

participant CEX
participant User Verifier

User Verifier->CEX: index i
CEX->User Verifier: Opening Proof of P at omega^i and omega^i-1

#### Proof of Solvency

- Can be performed by anyone, even a smart contract verifier

participant CEX
participant Verifier

Verifier->CEX: random value r
CEX->Verifier: Opening Proof of I and Q1 at r
CEX->Verifier: Opening Proof of Q2 at r and of P at r * omega^-13
CEX->Verifier: Opening Proof of Q3 at r and of I at r * omega^-1
CEX->Verifier: Opening Proof of Q4 at r and of I at r * omega^-16
Verifier->Verifier: Verify constraints

- For Schwartz-Zippel Lemma if the constraint holds true for a random value r, the constraint holds true for every x in the domain F with overwhelming probability.

### To Dos

- [ ] Modify witness generation function for P column
- [ ] Update constraint 1
- [ ] Update constraint 2
- [ ] Add constraint 3
- [ ] Add constraint 4