Summa
GitHubTelegram
V2
V2
  • Introduction
    • Overview
    • Protocol Flow
    • Resources
  • CRYPTOGRAPHIC PRIMITIVES
    • Zero-Knowledge Proof
    • Univariate Polynomial Grand Sum
    • KZG Commitment Scheme
  • Backend
    • summa-solvency
  • Circuits
    • Univariate Grand Sum
  • Smart Contract
    • Summa.sol
      • Solidity API
    • Verifiers
  • Benchmarks
  • Open Issues
Powered by GitBook
On this page
  • Proof Of Solvency
  • Proof Of Inclusion
  1. CRYPTOGRAPHIC PRIMITIVES

KZG Commitment Scheme

PreviousUnivariate Polynomial Grand SumNextsumma-solvency

Last updated 1 year ago

We choose a KZG commitment scheme to commit to the user balance polynomials for the compatibility with Halo2 API (more on that later). In brief, a KZG commitment is a single finite field element CCC that uniquely represents a polynomial B(X)B(X)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 CCC.

During the reveal (aka opening) phase, the committed value CCC is used along with the claimed polynomial evaluation B(x)B(x)B(x) to provide a succinct proof π\piπ verifying that the value B(x)B(x)B(x) is indeed an evaluation of a polynomial B(X)B(X)B(X) at point xxx and corresponds to the original commitment CCC. Therefore, KZG commitment allows the Custodian to individually provide the opening proofs πi\pi_iπi​ to each user to prove that the polynomial B(X)B(X)B(X) indeed evaluates to the user balance bib_ibi​ at the point xi=ωix_i = \omega^ixi​=ωi. Knowing ⟨C,B(ωi),π⟩\langle C, B(\omega^i),\pi\rangle⟨C,B(ωi),π⟩, the user is able to verify the opening.

More broadly, the KZG commitment allows the prover to open the polynomial at any point, and we will later see how it benefits our case.

Proof Of Solvency

Using the described polynomial construction technique and the KZG commitment, it is sufficient for the Custodian to "open" the KZG commitment at x=0x = 0x=0:

⟨C,B(0),πx=0⟩:B(0)=a0+a10+a202+...+an−10n−1=a0\langle C, B(0),\pi_{x=0}\rangle: B(0) = a_0 + a_10 + a_20^2 + ... + a_{n-1} 0^{n-1} = a_0⟨C,B(0),πx=0​⟩:B(0)=a0​+a1​0+a2​02+...+an−1​0n−1=a0​

The total liabilities can then be calculated by multiplying the a0a_0a0​ value by the number of users:

S=na0S = n a_0S=na0​

Proof Of Inclusion

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

the opening evaluation is equal to their balance: B(ωi)=biB(\omega^i) = b^iB(ωi)=bi;

the opening proof πi\pi_iπi​ corresponds to the public KZG commitment CCC.

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 iii 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)=hiH(\omega^i) = h_iH(ωi)=hi​;

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 hih_ihi​ is indeed the hash of their ID;

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