Monero Inflation Checker

☰

5 · The circuit

So we were left with the task of proving that we know the openings (secrets) of our tuple

O, I, C

in zero-knowledge and that they are the same one used to commit to our path up to the root. So we are going to do it using "circuits" and by organizing the proof in a way that we can plug it into the Generalized Bulletproof equation. Let's start defining what is a circuit in cryptography and go through an example to better understand it.

Circuit

We could start from the really basics and talk about the AND/OR operations on bits but instead we are going to skip that and focus on just what is important to understand the circuits in FCMP++, therefore we will talk here only about arithmetic circuits which perform operations with scalar fields (instead of bits) only. Each operation is called a gate and a set of operations to perform a specific task is called a gadget. Let's see with an example how it looks like:

A first example

A circuit is just a computation broken into elementary operations(addition and multiplications) called gates. Take a small one,

z = (x + y) \cdot w .

We compute it in two steps, naming every intermediate value so we can build our system out of elementary operations only. For example at the intermediate value $t$ :

t = x + y (addition, free), z = t \cdot w (multiplication, one gate) .

The addition costs almost nothing so we will not take into account the computation cost for those operations and we will consider only the multiplication costs (one gate per multiplication). So this whole computation is a single multiplication gate sitting on top of some linear combination of coefficients.

A point on a short Weierstrass curve

The previous example is not really used as a gadget in our FCMP++ proof. So let's pick one that is more useful, which is proving that a point is on an elliptic-curve (in our case Helios/Selene). First let's build it theoretically and then with real numbers on a tiny made-up curve so we can have an idea about the actual matrices the prover uses to feed the system. We want to prove that a point $(x, y)$ satisfies

y^{2} = x^{3} + a x + b,

with $a$ and $b$ fixed public constants (these are the constants of each elliptic-curve). Let's introduce the intermediate values computed in three steps:

t_{1} = x \cdot x = x^{2}, t_{2} = x^{3} = t_{1} \cdot x, t_{3} = y \cdot y = y^{2} .

Now write every gate as a left input $a_{L}$ times a right input $a_{R}$ giving the output $a_{O}$ :

gate	$a_{L}$	$a_{R}$	$a_{O}$
1	$x$	$x$	$t_{1}$
2	$t_{1}$	$x$	$t_{2}$
3	$y$	$y$	$t_{3}$

and the wires are tied together by one final relation

t_{2} + a x + b = t_{3},

which is linear (a weighted sum of intermediate values), so it costs no multiplication gate. That is why the on_curve gadget costs only three gates.

A concrete curve and witness

Now let's put numbers on it. Let's work over the small prime field $𝔽_{37}$ (the real system uses a field of roughly $2^{255}$ elements but the arithmetic is the same) so every value stays below $37$ . Now fix:

a = 2, b = 3, y^{2} = x^{3} + 2 x + 3 (\mod 37) .

The point $P = (3, 6)$ lies on it, since $3^{3} + 2 \cdot 3 + 3 = 27 + 6 + 3 = 36 = 6^{2}$ . Its secret values (witness) are

x = 3, y = 6, t_{1} = x^{2} = 9, t_{2} = x^{3} = 27, t_{3} = y^{2} = 36 .

The three multiplication gates look like that:

gate	$a_{L}$	$a_{R}$	$a_{O}$	product
1	3	3	9	$3 \cdot 3 = 9$
2	9	3	27	$9 \cdot 3 = 27$
3	6	6	36	$6 \cdot 6 = 36$

The final matrices

In order to have the full on_curve gadget, we need to fix the linear relation between the secret vectors (witnesses), which is done by wiring the circuit so it obeys the equation of the short Weierstrass curve:

t_{2} + a x + b = t_{3},

And those vectors could be wired as following for example:

row	meaning	constraint
C1	gate 1's inputs are one $x$	$a_{R, 1} - a_{L, 1} = 0$
C2	gate 2 reuses that $x$	$a_{R, 2} - a_{L, 1} = 0$
C3	gate 2 left $=$ gate 1 output $t_{1}$	$a_{L, 2} - a_{O, 1} = 0$
C4	gate 3 squares one $y$	$a_{R, 3} - a_{L, 3} = 0$
C5	the curve equation	$a a_{L, 1} + a_{O, 2} - a_{O, 3} + b = 0$

Now let's write our multiplication gates (private values) as vectors:

a_{L} = [\begin{matrix} 3 \\ 9 \\ 6 \end{matrix}], a_{R} = [\begin{matrix} 3 \\ 3 \\ 6 \end{matrix}], a_{O} = [\begin{matrix} 9 \\ 27 \\ 36 \end{matrix}] .

Those multiplication gates ( $a_{L}, a_{R}, a_{O}$ ) with $a = 2$ , $b = 3$ will act on the public wired circuit (from the table above), represented as matrices below:

W_{L} = [\begin{matrix} - 1 & 0 & 0 \\ - 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & - 1 \\ 2 & 0 & 0 \end{matrix}], W_{R} = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}], W_{O} = [\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ - 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & - 1 \end{matrix}], c = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 3 \end{matrix}] .

And now we can check if it balances:

[\begin{matrix} - 1 & 0 & 0 \\ - 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & - 1 \\ 2 & 0 & 0 \end{matrix}] [\begin{matrix} 3 \\ 9 \\ 6 \end{matrix}] + [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}] [\begin{matrix} 3 \\ 3 \\ 6 \end{matrix}] + [\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ - 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & - 1 \end{matrix}] [\begin{matrix} 9 \\ 27 \\ 36 \end{matrix}] + [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 3 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] .

And we end up with our point (that we knew that is on curve) respecting constraints C1 to C5 and therefore balancing the equation:

\underset{W_{L} a_{L}}{\underset{⏟}{[\begin{matrix} - 3 \\ - 3 \\ 9 \\ - 6 \\ 6 \end{matrix}]}} + \underset{W_{R} a_{R}}{\underset{⏟}{[\begin{matrix} 3 \\ 3 \\ 0 \\ 6 \\ 0 \end{matrix}]}} + \underset{W_{O} a_{O}}{\underset{⏟}{[\begin{matrix} 0 \\ 0 \\ - 9 \\ 0 \\ - 9 \end{matrix}]}} + \underset{c}{\underset{⏟}{[\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 3 \end{matrix}]}} = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] .

Now let's see if that works for a point off the curve: take $(3, 7)$ . Gate 3 now fills $a_{O, 3} = 7^{2} = 12$ , but row C5 still demands $2 \cdot 3 + 27 - 12 + 3 = 24 \neq 0$ , and the proof is rejected because the equation doesn't balance.

The same example in R1CS notation

R1CS (Rank-1 Constraint System) writes the identical circuit a second way: instead of three separate wire vectors it packs every value into one witness $w = (1, x, y, t_{1}, t_{2}, t_{3}) = (1, 3, 6, 9, 27, 36)$ , and each of the four relations becomes one row $(A \cdot w) (B \cdot w) = C \cdot w$ , where $A$ , $B$ , $C$ select the left factor, the right factor, and the output. Symbolically:

constraint	$A$	$B$	$C$
$x^{2} = t_{1}$	(0,1,0,0,0,0)	(0,1,0,0,0,0)	(0,0,0,1,0,0)
$t_{1} \cdot x = t_{2}$	(0,0,0,1,0,0)	(0,1,0,0,0,0)	(0,0,0,0,1,0)
$y^{2} = t_{3}$	(0,0,1,0,0,0)	(0,0,1,0,0,0)	(0,0,0,0,0,1)
$t_{2} + a x + b = t_{3}$	(1,0,0,0,0,0)	(b,a,0,0,1,0)	(0,0,0,0,0,1)

The last row keeps the linear tie inside the same product shape by making one factor the constant wire: $A \cdot w = 1$ and $B \cdot w = b + a x + t_{2}$ . Stacking the rows and filling in $a = 2$ , $b = 3$ gives three $4 \times 6$ matrices, columns ordered $(1, x, y, t_{1}, t_{2}, t_{3})$ :

A = [\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}], B = [\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 3 & 2 & 0 & 0 & 1 & 0 \end{matrix}], C = [\begin{matrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] .

Multiplying by $w = (1, 3, 6, 9, 27, 36)^{⊤}$ and taking the entrywise product gives the same check:

(A w) \circ (B w) = [\begin{matrix} 3 \\ 9 \\ 6 \\ 1 \end{matrix}] \circ [\begin{matrix} 3 \\ 3 \\ 6 \\ 36 \end{matrix}] = [\begin{matrix} 9 \\ 27 \\ 36 \\ 36 \end{matrix}] = C w .

Same numbers, same circuit: R1CS uses one product per row over a stacked witness, while the $a_{L} \cdot a_{R} = a_{O}$ form above splits the products into a single Hadamard line and the sums into the weight matrices. FCMP proves the second form. This fold only shows that the two are interchangeable.

So finally, what we did was to organize our vectors so that the linear combination of them is zero, satisfying the equation below:

W_{L} a_{L} + W_{R} a_{R} + W_{O} a_{O} + W_{C} a_{C} + c = 0

This equation does two jobs. First, it keeps all the constraints inside the public matrices $W_{L}, W_{R}, W_{O}, c$ , so the only unknowns left are our private vectors (the multiplication gates). Second, it lets us check everything later in zero-knowledge: all the rows are folded into a single number, and that number is zero only when every constraint holds. A prover who does not know a valid witness has almost no chance of making it zero.

All gadgets

Here is a list with each gadget (circuit) used in our code and their gate counts (multiplications):

gadget	gates	what it forces
`mul`	1	$a_{L, i} \cdot a_{R, i} = a_{O, i}$
`equality`	0	$a - b = 0$
`inverse`	1	$a \cdot a^{- 1} = 1 \Rightarrow a \neq 0$
`inequality`	1	$(a - b) (a - b)^{- 1} = 1 \Rightarrow a \neq b$
`on_curve`	3	$y^{2} = x^{3} + a x + b$
`incomplete_add_pub`	4	$A + B = C$
`member_of_list`	n−1	$\prod_{i} (L_{i} - m) = 0$
`tuple_member_of_list`	n−1	$\prod_{i} (L_{i} - m) = 0$
`discrete_log`	7	$P = s G$

Let's talk about three notable of them:

Member of list and Tuple member of list

These are the most expensive ones and they prove that the tuple (O,I,C) or a children in the tree is a valid member of a branch. We perform that using the equation below:

\prod_{i} (L_{i} - m) = 0 .

This product is only zero if the value $L_{i}$ (one tuple or child in our tree) is really equal to the desired member $m$ (in our case the member is $O$ or one of the intermediate children that we committed to when we proved that we know a path to the root). Notice that we have $n - 1$ multiplications.

Incomplete addition

Here we are talking about the addition of two Points and not scalars. To prove that $A + B = C$ we will simply use the geometric operations on elliptic-curves and the definitions of a line and our curve.

So the rule for adding points on a curve is simply geometric: a straight line meets a cubic (the short Weierstrass shape) in three places, and the group law defines those three points to sum to zero. So to add $A$ and $B$ we draw the line through them, take the third point $R$ where it hits the curve, and flip that point over the x-axis.

The line through the two points is:

y = λ x + μ, λ = \frac{y_{B} - y_{A}}{x_{B} - x_{A}}, μ = y_{A} - λ x_{A}

To find where it meets the curve, substitute it into the curve equation. The $y^{2}$ disappears and what is left is a cubic in $x$ alone, where $a, b$ are the curve constants:

(λ x + μ)^{2} = x^{3} + a x + b ⟺ x^{3} - λ^{2} x^{2} + (a - 2 λ μ) x + (b - μ^{2}) = 0

That cubic has exactly three roots, and we already know two of them: $x_{A}$ and $x_{B}$ , because $A$ and $B$ are on both the line and the curve. For a cubic the roots must sum to minus the coefficient of $x^{2}$ , so the third root is simply:

x_{A} + x_{B} + x_{R} = λ^{2} ⟹ x_{R} = λ^{2} - x_{A} - x_{B}

That third point $R$ is not yet the answer, it is where the line hit. Flipping it over the x-axis gives the sum:

C = - R, y_{R} = λ (x_{R} - x_{A}) + y_{A}

Since $x_{C}$ and $x_{R}$ are the same number, we can write the whole addition constraints in three formulas:

λ = \frac{y_{B} - y_{A}}{x_{B} - x_{A}}, x_{C} = λ^{2} - x_{A} - x_{B}, y_{C} = λ (x_{A} - x_{C}) - y_{A}

Multiplying the divisions away turns those three statements into three rows, each with exactly one multiplication in it:

\begin{matrix} λ (x_{B} - x_{A}) & = y_{B} - y_{A} \\ λ (x_{C} - x_{A}) & = - y_{C} - y_{A} \\ λ^{2} & = x_{A} + x_{B} + x_{C} \end{matrix}

Therefore, we have so far three gates. The fourth gate is the reason for the word incomplete: the formula divides by $x_{B} - x_{A}$ , so it simply has no answer when the two points share an x coordinate (doubling, or adding a point to its own negative). The gadget therefore has to rule that case out explicitly, and the only way a circuit can say "non-zero" is to exhibit an inverse:

(x_{B} - x_{A}) (x_{B} - x_{A})^{- 1} = 1 \Rightarrow x_{B} \neq x_{A}

That inverse is itself a multiplication and it is one of our gadgets, the inverse, which costs one gate.

Discrete log

This is the most interesting and most tricky part of the circuits and maybe of the whole proof because it takes only seven gates instead of thousands to prove knowledge of an scalar $o$ in $K = o \cdot T$ and is one of the reasons why the whole FCMP++ works within a reasonable amount of time and space.

The explanation deserves a dedicated page which can be found here: discrete-log gadget.

Now that we know about the circuits, let's see what is happening on each layer.

The first layer

Now the gadgets assemble. The bottom layer is the only one that touches the transaction values as it connects the four published points $\tilde{O}, \tilde{I}, \tilde{C}, R$ to a real leaf $(O, I, C)$ in the tree. In the first layer, we do simultaneously four proofs of knowledge of the secrets and one membership. Here is the actual scheme:

O                on_curve + dlog + add     3 + 7 + 4 = 14
I                on_curve + dlog + add     3 + 7 + 4 = 14
R                dlog + dlog + add         7 + 7 + 4 = 18
C                on_curve + dlog + add     3 + 7 + 4 = 14
leaf membership  tuple_member_of_list         38 − 1 = 37
                                                    ----
                                                      97

Each block recovers one hidden point from the disguise that was published on chain. The four relations the circuit proves are:

\begin{matrix} O & = \tilde{O} + o \cdot T \\ I & = \tilde{I} + i \cdot U \\ R & = i^{'} \cdot T - i \cdot V \\ C & = \tilde{C} + c \cdot G \end{matrix}

The first three all have the same shape: a point ( $O$ , $I$ , $C$ ) equals its public disguise ( $\tilde{O}$ , $\tilde{I}$ , $\tilde{C}$ ) plus a blind. The point and the blinding scalar stay hidden but the disguise is public.

$R$ is the odd one, $i^{'}$ blinds the blind. It gets no on-curve check because it is already public, and it is two discrete logs rather than one. What matters here is the $i$ in it. Which is the same scalar as in the $I$ . And that is the key-image weld: it forces one single $i$ onto both $U$ and $V$ , so a prover cannot blind the key image with one scalar and claim another.

Notice that a prover who satisfies $O = \tilde{O} + o \cdot T$ is forced to use, in the membership check, exactly the $O$ that the disguise opened to. This is what joins all circuits together. It is not possible to make a dlog proof of one $O$ and show another in the membership proof because they are wired together. Both prover and verifier must use the same consensus circuit, otherwise the proof will not be valid.

So finally we arrive at 97 gates per input for the first layer.

Every layer above

Past the leaf, every floor is the same small routine but a bit simpler because there are no leaves or direct data from the transaction to connect to. Every floor proves knowledge of the commited points of the path (using the dlog), proves the result is on the curve, adds them, and looks the result up in the branch above by its x-coordinate only:

Selene floor   dlog + on_curve + add + member + node wires  7 + 3 + 4 + (38−1) + 1 = 52
Helios floor   dlog + on_curve + add + member + node wires   7 + 3 + 4 + (18−1) + 1 = 32

Written out for the node $N_{i}$ on floor $i$ , with $(x_{i}, y_{i})$ its coordinates, $C^{(i)}$ its blinded commitment, and $v_{j}$ the $w$ children slots of its parent $N_{i + 1}$ :

\begin{matrix} N_{i} & = J + C^{(i)} - b_{i} \cdot H & recover the node \\ y_{i}^{2} & = x_{i}^{3} + a x_{i} + b & on the curve \\ 0 & = \prod_{j = 0}^{w - 1} (v_{j} - x_{i}) & in the branch above \end{matrix}

The asymmetry is only in the branch width, 38 children on Selene against 18 on Helios. One note: hashing the x-coordinate alone would let a point and its negation share an x, so each node is committed shifted by a fixed public point $J$ (the hash-init), which breaks the sign symmetry.

What was achieved?

So finally we have a better idea on how things are linked to another. We first did SAL and commited to the disguised points ( $\tilde{O}$ , $\tilde{I}$ , $\tilde{C}$ ), then we used circuits to prove knowledge of the openings (secrets) of our tuple ( $O$ , $I$ , $C$ ) and we also used circuits to prove that it is of the leaves sitting on tree in the first layer, next we used circuits again to prove the nodes are also really sitting in the tree and we did that up to the root, where we proved that the whole thing holds because we can open to a valid root.

Alright, now we know the mechanics of the circuits. But what is the idea behind all those calculations? Basically, the prover is the only one who knows the witness vector (or the secret vectors $a_{L}, a_{R}, a_{O}, a_{C}$ ) and the verifier knows the public matrices ( $W_{L}, W_{R}, W_{O}, W_{C}, c$ ), which is part of the consensus. So the idea is that the prover folds his witness vector (secret values) in a hidden way that allows the verifier to check the validity of the proof just by using the public matrices (corresponding to all constraints on those private vectors). And showing how this is done is our next task by developing the Generalized Bulletproof equation:

W_{L} a_{L} + W_{R} a_{R} + W_{O} a_{O} + W_{C} a_{C} + c = 0

← Curves Next: Discrete log →