Multilinear KZG Commitment

We choose a Multilinear KZG commitment scheme to commit to the user balance polynomials for the compatibility with Halo2 API (more on that later). In brief, a Multilinear KZG commitment is a single finite field element $C$ that uniquely represents a polynomial $B(X)$.

It is impossible to reconstruct the polynomial from the commitment, so our requirement of user privacy is satisfied because it is impossible to infer any evaluations of the polynomial from the single-value commitment $C$.

During the reveal (aka opening) phase, the committed value $C$ is used along with the claimed polynomial evaluation $B(x)$ to provide a succinct proof $\pi$ verifying that the value $B(x)$ is indeed an evaluation of a polynomial $B(X)$ at point $x$ and corresponds to the original commitment $C$. Therefore, KZG commitment allows the Custodian to individually provide the opening proofs $\pi_i$ to each user to prove that the polynomial $B(X)$ indeed evaluates to the user balance $b_i$ at the point $x_i = ⟨i⟩$, where ⟨i⟩ is the bit binary representation of i. Knowing $\langle C, B(⟨i⟩),\pi\rangle$, the user is able to verify the opening.

Proof Of Inclusion

As described in the Multilinear KZG section, individual users would receive the KZG opening proofs $\langle C, B(⟨i⟩),\pi_i\rangle$ at their specific point $⟨i⟩$ and they would be able to check that

• the opening evaluation is equal to their balance: $B(⟨i⟩) = b^i$;

• the opening proof $\pi_i$ corresponds to the public KZG commitment $C$.

The caveat is that if two or more users have the same cryptocurrency balance value, a malicious Custodian could give them the same KZG proof because the user index $i$ is defined by the Custodian. We will use the following technique to mitigate this:

• the Custodian has to additionally commit to another polynomial that evaluates to the hashes of user IDs at the specific user points: $H(⟨i⟩) = h_i$;

• the user ID should be known to the user (e.g, the email address used to register with the Custodian), so the user can check that the value $h_i$ is indeed the hash of their ID;

• the Custodian then gives two KZG commitments and two opening proofs to the user - $\langle C_B, B(⟨i⟩),\pi_B\rangle$ proving the balance inclusion into the balances polynomial, and $\langle C_H, H(⟨i⟩),\pi_H\rangle$ proving the user ID hash inclusion into the ID hash polynomial.