5.1 · The Discrete Log gadget

Before we can start talking about our goal, which is to prove that $K=o·T$ in zero-knowledge, it makes sense to review some math and theories that will help us with the proof.

1 · Zeros and a poles

Simply put, on an ordinary polynomial, a zero is a point where the function vanishes and a pole is a point where the function blows up.

For example, the polynomial below has 2 as a zero of multiplicity 1, and 5 as a zero of multiplicity 3.

and the rational function below has 5 as a pole of order 3.

For a rational function $f$ on an elliptic curve:

• $f$ has a zero at $P$ if $f(P)=0$.
• $f$ has a pole at $P$ if $f$ becomes infinite at $P$.
• The order tells us the multiplicity, and is written ${ord}_P(f)$.

For the two functions above:

2 · Divisors: definitions

Let's play with $E$, the toy elliptic curve $y^2=x^3+2x+11$ over ${𝔽}_{103}$, whose 97 points are all multiples of $T=(2,34)$.

A divisor on $E$ is a finite formal sum

On this curve, we could have for instance:

Its degree is

which for that divisor is

For a nonzero rational function $f\in {𝔽}_{103}(E{)}^{\times }$, its principal divisor is

with ${ord}_P(f)$ positive at a zero and negative at a pole. A principal divisor always has degree zero.

For example, the line function

meets the curve at three points, whose sum is $O$, so

On this curve the line through T and 4T meets it again at −5T = (70,26). Its slope and intercept are one subtraction and one inversion, every step modulo 103:

and it does vanish at the third point, −5T = (70,26):

so its divisor is

3 · Weil reciprocity

Reading a function at a divisor means evaluating it at every point of that divisor and multiplying them if the multiplicity is positive or dividing them if negative:

Weil reciprocity states that for two nonzero rational functions the two evaluations below must agree:

Notice that neither side has to know how the other was built.

Take f(x), monic of degree four in x alone. Every factor is a vertical (x = 2, x = 25, and so on, is a zero), so it vanishes at a point and its reflection in the elliptic curve, and all of its poles sit at O:

Each root is the x coordinate of two points of the curve, one the reflection of the other, and every one of them is a multiple of T:

Therefore:

and the line through the three points A = (4,17), B = (6,41), C = (31,32):

Reading f at the three points of div ℓ, and ℓ at the eight points of div f:

We get the same result!

4 · The logarithmic derivative

The result above is nice but still not usable. What if we could take the logarithmic derivative on both sides of the Weil Reciprocity equation considering that we have as functions a polynomial and a line? Let's consider a generic line passing through $A,B,C$ and a generic polynomial with zeros at $P$, each with multiplicity $n_P$.

The divisor of the line is $[A]+[B]+[C]-3[O]$ and the divisor of $f$ is ${\sum }_P{n}_P[P]-\left({\sum }_P{n}_P\right)[O]$, so applying the Weil reciprocity and reading each function at the other's divisor gives

Now record that if we have an ordinary polynomial function (which is the case of a line and a nonzero polynomial), then:

gives

which is simply proven by:

and dividing that by $F(z)$ leaves only the sum term:

Now take $\frac{d}{d\mu }\log$ of both sides and develop them side by side. The line is read the way the implementation reads it, $\ell (P)=\lambda x_P+\mu -y_P$, so that $d\ell (P)/d\mu =1$ and no sign survives the differentiation:

Since we have:

then, writing the curve's tangent slope at $c$ as $m(c)=\frac{3x^2+2}{2y}$, the first row reads $dy/d\mu =m(c)d{x}_c/d\mu$. Substituting it into the second and solving for the speed:

What do we finally achieved after looking at the left and right side now?

Is that true and does that hold still? On the quartic order polynomial and the line above, both sides come to the same field element:

and on the other side, one term per zero of f:

Everything so far holds for any $f$ and the formula below is very powerful!

Before we proceed, let's stop for a minute and think about what this equation is telling us. The first thing we see is that everything is linear. We have just sums of factors. The second thing is that we manage to make a sum related to the zeros of the polynomials as only three sums in the left side, no matter the size of the polynomial and its roots! So what we could naturally ask is what what if we could encode the secret value that we want to prove as a polynomial? And that is exactly what we will see next.

For that we will keep using a small example representing our elliptic curve and constants and apply all the operations that the code would be doing in the real proof to visualize what is happening. Therefore, consider that we have:

all 96 points of the curve, in order of their multiple:

  1T (2,34)    2^0 T     25T (82,9)              49T (24,9)              73T (26,51)
  2T (25,37)   2^1 T     26T (71,97)             50T (7,70)    -K        74T (100,94)
  3T (84,18)             27T (10,102)            51T (14,65)   merge     75T (42,34)
  4T (72,50)   2^2 T     28T (86,76)             52T (20,74)             76T (59,69)
  5T (70,77)             29T (41,101)            53T (16,15)             77T (51,10)
  6T (97,68)   merge     30T (6,41)    B         54T (18,76)             78T (68,74)
  7T (80,40)             31T (53,57)             55T (40,98)             79T (52,98)
  8T (85,23)   2^3 T     32T (1,23)              56T (49,82)             80T (4,17)    A
  9T (66,75)             33T (15,29)             57T (17,23)   merge     81T (92,10)
 10T (98,59)             34T (38,67)             58T (47,102)            82T (102,27)
 11T (62,92)             35T (76,87)             59T (19,25)             83T (96,90)
 12T (46,102)            36T (63,10)             60T (11,98)             84T (31,32)   C
 13T (31,71)             37T (11,5)              61T (63,93)             85T (46,1)
 14T (96,13)             38T (19,78)             62T (76,16)             86T (62,11)
 15T (102,76)            39T (47,1)              63T (38,36)             87T (98,44)
 16T (92,93)   2^4 T     40T (17,80)   merge     64T (15,74)             88T (66,28)
 17T (4,86)              41T (49,21)             65T (1,80)              89T (85,80)
 18T (52,5)              42T (40,5)              66T (53,46)             90T (80,63)
 19T (68,29)             43T (18,27)             67T (6,62)              91T (97,35)
 20T (51,93)             44T (16,88)             68T (41,2)              92T (70,26)
 21T (59,34)             45T (20,29)             69T (86,27)             93T (72,53)
 22T (42,69)             46T (14,38)             70T (10,1)              94T (84,85)
 23T (100,9)             47T (7,33)    K = 47T   71T (71,6)              95T (25,66)
 24T (26,52)   merge     48T (24,94)             72T (82,94)             96T (2,69)

1 · Decompose the scalar

We will first fix on how many values we want to represent our secret scalar and then choose the coefficients $d_i$ such that they simultaneously satisfy two conditions:

For our scalar $o$ = 47, the decomposition procedure starts from the ordinary little-endian bits

and then moves weight between adjacent slots until the coefficient sum is exactly 7:

Weighted sum. $1+2+4+3·8+16=47$

Digit sum. $1+1+1+3+1=7$

As you noticed, we can re-write our point $K$ by multiplying the weighted sum for the base point scaled by a factor. Let's do it.

2 · The interesting set S

Define $T_i=2^{i}T$. Since

move $K$ to the left:

And now all points sum to the identity and we have the interesting set below.

There are eight finite points (counting the multiplicity). Seven from the digit sum, plus the single point $-K$.

Great! We have the set of points (related to our secret scalar) which we want to be the roots of a polynomial function so that we don't need to evaluate that function on those roots but actually in three points (a line) only by using the Weil reciprocity.

3 · The polynomial

Given the eight points of $S$, which sum to $O$:

Our problem is to find one function $f$ whose zeros are exactly those points, with those multiplicities, and no pole except at infinity:

First, let's see how the shape of $f$ looks like. The elliptic curve equation replaces every $y^2$, so nothing above the first power of $y$ survives and the final form of the divisor should look like:

The solution is simple in theory but could be cumbersome to achieve in practice. One way to understand the problem is by looking at the degree that our polynomial should have (shown by the equation below) and by looking how many equations we have (given by the points of our interesting set).

As we can see, we have as many equations as unknows and the problem basically becomes just answering the question: how do I interpolate a polynomial of degree N (so N+1 variables) given that I have N+1 points? There are many methods like the Lagrange interpolation, Newton interpolation, solve the Vandermonde matrix system and so on. What makes more sense numerically though is to use the Barycentric Lagrange interpolation, which is exactly what the code does.

Instead of going through all the tiring matrices multiplications and how that works, we will jump to the answer and just verify that it is correct for our example:

and they are correct because they verify:

Now we want to use the equation that we previously derived:

Now let's see if this equation balances and then let's discuss what was achieved here.

First let's draw 2 points (A and B) and derive the third one (C), which is determined because they are in a line. Let's use $A=(4,17)$ and $B=(6,41)$, so $C=-(A+B)=(31,32)$, and the line through them is $y=12x+72$.

Now the derivative of f is:

And finally we can just evaluate the equation on each of those values:

Now the other side:

and we see that they balance. But how is the proof using this result? How does the prover enter the information about $K=oT$ ? How does the verifier get convinced that the equation above is satisfied, and what is it that he evaluates?

To answer those questions we first have to look on what the prover and the verifier are doing:

From the prover and verifier perspectives

The first thing that we need to have in mind is that those calculations are part of a circuit. We are not going to reveal the secret values but they are going to be commited into a point using the Pedersen Vector Commitment and at the same time they enter as the wires of the circuit, which the verifier never sees. The prover will then fold all the secret information of all the circuits together in the terms of the Generalized Bulletproofs (GBP). The verifier then will only be able to check if folded values (which are blinded) really satisfies the GBP equation. Another way of thinking about it is considering that the verifier must verify the R1CS equation $Aw.Bw=Cw$ , with the matrices $A$,$B$,$C$ being public. If the prover folds $w$ into a GBP proof and commit to its value, the verifer can be convinced that the prover provided a valid $w$ which satisfies the ($A$,$B$,$C$) matrices because the verifier can use those matrices to reconstruct the challenges on the witness and only a vector $w$, that satisfies that system can balance the equation provided by the verifier's challenge.

The commitments

Now let's look how the prover folds the polynomials (containing the information of the zeros of our set of interest, which is the decomposition of our secret value) and folds the point $K=oT$

Selene, 256 slots per commitment, a 253-bit scalar:

Here are the $C$ commitments and what they contain:

The cost of discrete log

So we finally created a mechanism to prove that K=oT via circuits where the prover does it in zero-knowledge and the verifier is convinced about it because he provides the circuits (or constraints) that the prover must obey.