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
  • Preliminaries
  • Modular Arithmetic
  • Roots Of Unity In Modular Arithmetic
  • Roots Of Unity Example
  • Special Property Of The Sum Of Roots of Unity
  • Data Structure & Commitment Scheme
  • Grand Sum Of The Polynomial Evaluations
  1. CRYPTOGRAPHIC PRIMITIVES

Univariate Polynomial Grand Sum

Preliminaries

Modular Arithmetic

An intuitive example of modular arithmetic from our daily life is the "clock arithmetic". When we see "19:00" boarding time on a boarding pass, we know that it corresponds to "7" on the clock face. Formally, in this case we perform the modular reduction by the modulus 12:

19≡7(mod12)19 \equiv 7\pmod{12}19≡7(mod12)

because the clock face only has twelve hours marked on it.

Roots Of Unity In Modular Arithmetic

An integer ω\omegaω is an nnn-th root of unity modulo ppp if ωn≡1(modp)\omega^n \equiv 1 \pmod{p}ωn≡1(modp)

In other words, ωn\omega^nωn "wraps around" due to modular reduction to yield exactly 111. A particular case is when no integers smaller than nnn yield 111 modulo ppp. In this case, ω\omegaω is called a primitive root of unity: ωk≢1(modp)\omega^k \not\equiv 1 \pmod{p}ωk≡1(modp) for any 0<k<n0 < k < n0<k<n.

Roots Of Unity Example

Let's observe a finite field of order p=7p = 7p=7: F7=0,1,2,3,4,5,6\mathbb{F}_7 = {0, 1,2,3,4,5,6}F7​=0,1,2,3,4,5,6. Let's see that 222 and 444 are the 3rd roots of unity in such a field:

  • 23≡8≡1(mod7)2^3 \equiv 8 \equiv 1 \pmod{7}23≡8≡1(mod7), so 2 is a 3rd root of unity modulo 7.

  • 43≡64≡1(mod7)4^3 \equiv 64 \equiv 1 \pmod{7}43≡64≡1(mod7), so 4 is another 3rd root of unity modulo 7.

111 itself is a root of unity, too, and is called a trivial root of unity.

Special Property Of The Sum Of Roots of Unity

Let's consider a finite field Fp\mathbb{F}_pFp​ that has nnn-th roots of unity. Let ω\omegaω be a primitive nnn-th root of unity in Fp\mathbb{F}_pFp​, which means ωn=1\omega^n = 1ωn=1 and no smaller positive power of ω\omegaω equals 111.

The nnn-th roots of unity in Fp\mathbb{F}_pFp​ are 1,ω,ω2,…,ωn−11, \omega, \omega^2, \ldots, \omega^{n-1}1,ω,ω2,…,ωn−1.

Claim: 1+ω+ω2+…+ωn−1=01 + \omega + \omega^2 + \ldots + \omega^{n-1} = 01+ω+ω2+…+ωn−1=0 (the sum of all the roots of unity in a finite field is equal to zero).

Proof:

Consider the sum S=1+ω+ω2+…+ωn−1S = 1 + \omega + \omega^2 + \ldots + \omega^{n-1}S=1+ω+ω2+…+ωn−1. We can multiply SSS by ω−1\omega - 1ω−1, noting that ω−1≠0\omega - 1 \neq 0ω−1=0 so that such a multiplication preserves the equality:

(ω−1)S=(ω−1)(1+ω+ω2+…+ωn−1)(\omega - 1)S = (\omega - 1)(1 + \omega + \omega^2 + \ldots + \omega^{n-1})(ω−1)S=(ω−1)(1+ω+ω2+…+ωn−1)

Expanding the right hand side, we get:

ω+ω2+ω3+…+ωn−(1+ω+ω2+…+ωn−1)\omega + \omega^2 + \omega^3 + \ldots + \omega^n - (1 + \omega + \omega^2 + \ldots + \omega^{n-1})ω+ω2+ω3+…+ωn−(1+ω+ω2+…+ωn−1)

Notice that if we were to expand further, every term except ωn\omega^nωn and −1-1−1 would cancel out:

(ω−1)S=ωn−1(\omega - 1)S = \omega^n - 1(ω−1)S=ωn−1

Since ω\omegaω is a primitive nnn-th root of unity, ωn=1\omega^n = 1ωn=1. So, ωn−1=0\omega^n - 1 = 0ωn−1=0. Therefore:

(ω−1)S=0(\omega - 1)S = 0(ω−1)S=0

If the product of two factors is zero, at least one of them must be zero. We already established that ω−1≠0\omega - 1 \neq 0ω−1=0, thus SSS must be zero: S=0S = 0S=0. Therefore,

1+ω+ω2+…+ωn−1=0\boxed{1 + \omega + \omega^2 + \ldots + \omega^{n-1} = 0}1+ω+ω2+…+ωn−1=0​

Let's also check it on our previous toy example of F7\mathbb{F}_7F7​ and n=3n = 3n=3: 1+2+4=7≡0(mod7)1 + 2 + 4 = 7 \equiv 0 \pmod{7}1+2+4=7≡0(mod7).

Let's see how we can take advantage of the sum of all roots of unity being zero when applied to the proof of solvency.

Data Structure & Commitment Scheme

The desired commitment scheme for Summa should have the following properties:

  • Committing to the total liabilities of the Custodian that is the sum of all user balances;

  • Allowing to publicly reveal the total liabilities without revealing any information about user balances;

  • Allowing to prove the individual user inclusion into the commitment without revealing any information about other user balances;

  • Preserving the user privacy and hiding the user data (namely the user cryptocurrency balances);

  • Outperform the Merkle sum tree in both commitment phase and proving phase.

We will demonstrate how a polynomial commitment can be used to achieve all of these properties.

Let's consider a polynomial B(X)B(X)B(X) that evaluates to an iii-th user balance bib_ibi​ at a "user's point" - some value xix_ixi​ that is designated for this specific user:

B(xi)=biB(x_i) = b_iB(xi​)=bi​.

We can call it a user balance polynomial. It is quite easy to construct such a polynomial using the Lagrange interpolation. The formula for the polynomial that interpolates these data points is:

B(X)=∑i=1nbi⋅Li(X)B(X) = \sum_{i=1}^{n} b_i \cdot L_i(X)B(X)=i=1∑n​bi​⋅Li​(X)

Where Li(X)L_i(X)Li​(X) is the Lagrange basis polynomial defined as a product:

Li(X)=∏j=1 j≠inX−xjxi−xjL_i(X) = \prod_{\substack{j=1 \ j \neq i}}^{n} \frac{X - x_j}{x_i - x_j}Li​(X)=j=1 j=i​∏n​xi​−xj​X−xj​​

A polynomial constructed using the Lagrange interpolation is known to have the degree d=n−1d = n - 1d=n−1 where nnn is the number of users (and the number of the corresponding balance evaluation points). The resulting polynomial should look like the following:

B(X)=a0+a1x+a2x2+...+an−1xn−1\boxed{B(X) = a_0 + a_1x + a_2x^2 + ... + a_{n-1} x^{n-1}}B(X)=a0​+a1​x+a2​x2+...+an−1​xn−1​

Let's choose the xix_ixi​ values as the iii-th degrees of an nnn-th root of unity (assuming that we are performing all the calculations in the prime field with a sufficiently large modulus):

B(ωi)=bi\boxed{B(\omega^i) = b_i}B(ωi)=bi​​ where ω\omegaω is the nnn-th primitive root of unity and i∈0..n−1i\in0..n-1i∈0..n−1.

Grand Sum Of The Polynomial Evaluations

To prove the solvency of the Custodian, we need to find its total liabilities by summing up all the user balances and to prove to the public that the sum is less than the assets owned by the Custodian. An individual iii-th user balance is the evaluation of the polynomial at the ωi\omega^iωi value corresponding to the user:

B(ωi)=bi=a0+a1(ωi)1+a2(ωi)2+...+an−1(ωi)n−1B(\omega^i) = b_i =a_0 + a_1(\omega^i)^1 + a_2(\omega^i)^2 + ... + a_{n-1} (\omega^i)^{n-1}B(ωi)=bi​=a0​+a1​(ωi)1+a2​(ωi)2+...+an−1​(ωi)n−1

Let's calculate the sum SSS of all the user balances as the sum of the polynomial evaluations:

S=∑i=0..n−1B(ωi)=a0+a1ω0−1+a2(ω0−1)2+⋯+an−1(ω0−1)n−1++a0+a1ω1−1+a2(ω1−1)2+⋯+an−1(ω1−1)n−1++a0+a1ω2−1+a2(ω2−1)2+⋯+an−1(ω2−1)n−1+⋮+a0+a1ωn−1+a2(ωn−1)2+⋯+an−1(ωn−1)n−1=(let’s factor out each ai)\begin{align*} S = \sum\limits_{i=0..n-1} B(\omega^i)& = &a_0\quad& + &a_1\omega^{0\phantom{-1}}\quad & + & a_2(\omega^{0\phantom{-1}})^2\quad & + & \cdots\quad & + & a_{n-1} (\omega^{0\phantom{-1}})^{n-1} +\\ & + &a_0\quad& + &a_1\omega^{1\phantom{-1}}\quad & + & a_2(\omega^{1\phantom{-1}})^2\quad & + & \cdots\quad & + & a_{n-1} (\omega^{1\phantom{-1}})^{n-1} +\\ & + &a_0\quad& + &a_1\omega^{2\phantom{-1}}\quad & + & a_2(\omega^{2\phantom{-1}})^2\quad & + & \cdots\quad & + & a_{n-1} (\omega^{2\phantom{-1}})^{n-1} +\\ &&&&&\vdots \\ & + &a_0\quad& + &a_1\omega^{n-1}\quad & + & a_2(\omega^{n-1})^2\quad & + & \cdots\quad & + & a_{n-1} (\omega^{n-1})^{n-1} =\\ \\ \rlap{\text{(let's factor out each $a_i$)}} \end{align*}S=i=0..n−1∑​B(ωi)(let’s factor out each ai​)​=+++​a0​a0​a0​a0​​++++​a1​ω0−1a1​ω1−1a1​ω2−1a1​ωn−1​+++⋮+​a2​(ω0−1)2a2​(ω1−1)2a2​(ω2−1)2a2​(ωn−1)2​++++​⋯⋯⋯⋯​++++​an−1​(ω0−1)n−1+an−1​(ω1−1)n−1+an−1​(ω2−1)n−1+an−1​(ωn−1)n−1=​
=na0+a1(ω0+ω1+ω2+⋯+ωn−1⏟=0)+⋯+an−1(ω0+ω1+ω2+⋯+ωn−1⏟=0)n−1=(using the property of the sum of all roots of unity inside the parentheses being zero)=na0\begin{align*}&=n a_0 + a_1(\underbrace{\omega^0 + \omega^1 + \omega^2 + \cdots +\omega^{n-1}}_{=0}) + \cdots + a_{n-1}(\underbrace{\omega^0 + \omega^1 + \omega^2 +\cdots+ \omega^{n-1} }_{=0})^{n-1} = \\ &\rlap{\text{(using the property of the sum of all roots of unity inside the parentheses being zero)}} \\\quad \\&= n a_0 \end{align*}​=na0​+a1​(=0ω0+ω1+ω2+⋯+ωn−1​​)+⋯+an−1​(=0ω0+ω1+ω2+⋯+ωn−1​​)n−1=(using the property of the sum of all roots of unity inside the parentheses being zero)=na0​​

Therefore, the grand sum of the user balances is simply the constant coefficient of the polynomial times the number of users:

S=∑iB(ωi)=na0\boxed{S = \sum\limits_{i} B(\omega_i) = n a_0}S=i∑​B(ωi​)=na0​​

As it turns out, the Halo2 proving system is internally using the roots of unity as XXX coordinates for the polynomial construction, and we will later see how we can take advantage of that.

PreviousZero-Knowledge ProofNextKZG Commitment Scheme

Last updated 1 year ago