Monero Inflation Checker

☰

4 · Two Curves

Now we need to show how we can build a special and efficient Merkle tree with the goal of proving membership of an output (in our case a tuple

O, I, C

) in zero-knowledge. We will first talk about the practical tools that we need for that (the elliptic-curves used), then how we use these tools (which operations we are allowed to do and how the "hash" of the Merkle tree is defined), then we will see how Monero organizes its hundreds of millions of transactions in this special Merkle tree and finally how we can start creating the membership proof in zero-knowledge.

The curves

Monero has used so far just one major elliptic-curve: Ed25519. But now we are going to expand our repertoire and add to it two more curves (Helios and Selene) and another intermediate one (Wei25519). Let's look at their shapes:

curve	form	equation	base field	scalar field
Ed25519	twisted Edwards	$- x^{2} + y^{2} = 1 + d x^{2} y^{2}$	$𝔽_{p}$	$𝔽_{ℓ}$
Wei25519	short Weierstrass	$y^{2} = x^{3} + a x + b$	$𝔽_{p}$	$𝔽_{ℓ}$
Helios	short Weierstrass	$y^{2} = x^{3} + a x + b$	$𝔽_{p}$	$𝔽_{q}$
Selene	short Weierstrass	$y^{2} = x^{3} + a x + b$	$𝔽_{q}$	$𝔽_{p}$

A short recap: the base field is the field the curve is defined over (where the points live), so a point's coordinates are elements of it. The scalar field is where the multipliers live, the numbers $k$ you are allowed to write in $k \cdot P$ . Each field's cardinality is its subscript and we have for them:

\begin{matrix} p & = 2^{255} - 19 & (1) \\ q & = 2^{255} - 11686397589588510723982429389243424941 & (2) \\ ℓ & = 2^{252} + 27742317777372353535851937790883648493 & (3) \end{matrix}

The exact constants we have for Monero curves

The three sizes, in hexadecimal

p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
q = 0x7ffffffffffffffffffffffffffffffff735481d1969f317f9850b68df11df53
ℓ = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed

and in decimal

p = 57896044618658097711785492504343953926634992332820282019728792003956564819949
q = 57896044618658097711785492504343953926623305935230693509004809574567321395027
ℓ =  7237005577332262213973186563042994240857116359379907606001950938285454250989

Ed25519 · over $𝔽_{p}$ · order $8 ℓ$ · cofactor $8$

- x^{2} + y^{2} = 1 + d x^{2} y^{2}, d = - \frac{121665}{121666} mod p

Wei25519 · over $𝔽_{p}$ · order $8 ℓ$ · the same group as Ed25519, relabelled

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

a = 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa984914a144
b = 0x7b425ed097b425ed097b425ed097b425ed097b425ed097b4260b5e9c7710c864

Helios · over $𝔽_{p}$ · order $q$ · cofactor $1$

y^{2} = x^{3} - 3 x + b

b   = 0x26bdec0884fe05f20cb42071569fab6432be360d07da8c5b460b82b980fd8c60

Selene · over $𝔽_{q}$ · order $p$ · cofactor $1$

y^{2} = x^{3} - 3 x + b

b   = 0x38c40d10c226ef3bc597c2e1e25bc748e3401c3d031d14ca2265f309ba81efe4

The goal here is not to give the full theory of elliptic-curves nor a full review of those curves (as they were seriously done here) , but just to introduce the basic tools we need to understand the full FCMP proof as a whole. Therefore, two questions will guide us through that.

Why do we need the curve Wei25519?
Why do we need the curves Helios and Selene?

Let's briefly answer each of them:

1) Why do we need the curve Wei25519?

Monero's outputs live on Ed25519 and it will stay like this for a while (as we have millions of outputs on chain). But there is one big issue with that. We cannot simply perform the circuits (the operations we will be doing in zero-knowledge over Helios and Selene) on them because they need to be in the short Weierstrass form. So we need a way to convert Ed25519 points into short Weierstrass and the curve named "Wei25519" is just that.

2) Why do we need the curves Helios and Selene?

The intuition behind the idea of using two curves is simple: we need to "hash" the leaves of our Merkle tree and we need to perform operations with that hash in zero-knowledge. Wouldn't it be great if we could perform the same operations, like scalars times points all over the proof? Let's do it by defining our hash function: the Pedersen vector commitment (the $v_{i}$ are the children and the $G_{i}$ the node's generators):

C = v_{1} \cdot G_{1} + v_{2} \cdot G_{2} + \dots + v_{n} \cdot G_{n}

Notice now how the layers can be connected. Into the commitment go the children, which are plain numbers (scalars). Then the output is a single point, the parent node. Now climb one floor: the parent must itself become a child, so it has to enter the next commitment as a number (scalar). But a point is not a number, it is a pair of numbers (it has $x$ and $y$ coordinates). So we throw one away and we keep only one, the $x$ . The catch is that a curve carries two kinds of numbers: coordinates that live in the base field and scalars that live in the scalar field. So a coordinate coming out of one floor is a legal child on the floor above only when the scalar field of the curve above is the base field of the curve below. And with that we build a nice hash function for our special Merkle tree that has alternating elliptic-curves.

Those two curves that form a cycle with each other are called Helios and Selene.

Notice also that our hash function still has the properties that we want and moreover it is homomorphic.

Binding. The prover cannot reopen $C$ to a different list. Two openings of the same point would subtract to a discrete-log relation among the independent generators, which nobody can produce. This is why a node commits to its children once and for all.
Hiding. The blind $mask \cdot h$ is a uniformly random point, so $C$ is uniformly random and leaks nothing about the $v_{i}$ . This is why a blinded node can be published on the chain and reveal nothing about the outputs beneath it.
Homomorphic. Adding commitments adds their contents: the sum of two commitments is a commitment to the sums. This is why linear relations among hidden values can be checked by a verifier who only ever sees points, and it is the reason "the parent hash was computed correctly" is always valid because committing to the children already is the parent. In math terms, consider $C = \sum_{i} v_{i} \cdot G_{i} + mask \cdot H$ and $C^{'} = \sum_{i} v_{i}^{'} \cdot G_{i} + {mask}^{'} \cdot H$ , then

C + C^{'} = \sum_{i} (v_{i} + v_{i}^{'}) \cdot G_{i} + (mask + {mask}^{'}) \cdot H

The special Merkle tree

Alright. Now we know the tools that we have at hand (our hash function) so let's see how Monero's special Merkle tree is built: So, to combine $w$ children into their parent node, put each child as the scalar in front of its own dedicated generator, add them all up, and start the sum from a fixed public point $init$ :

H = init + a_{1} \cdot G_{1} + a_{2} \cdot G_{2} + \dots + a_{w} \cdot G_{w}

Notice that $a_{1}, \dots, a_{w}$ are the children being hashed: each a plain number (a field element), not a point. As we saw above, the idea is to build a Merkle tree out of those curve cycles (in our case Helios and Selene) so each layer of the Merkle tree has its own elliptic-curve. So Selene's points are the scalars of Helios and the other way round. The $G_{1}, \dots, G_{w}$ are fixed independent NUMS (nothing-up-my-sleeve) generators (either on Helios or Selene depending on the layer), one reserved slot per child position, and $init$ is a fixed public starting point. So $H$ is a single curve point that stands for the whole group of children below it (our replacement for the SHA-256 hash of a node).

And what are the leaves of our first layer? They are the outputs themselves: each output contributes with its six coordinates $(O_{x}, O_{y}, I_{x}, I_{y}, C_{x}, C_{y})$ , and with $w_{s}$ outputs bundled under one first-floor node, that node's sum runs over $6 \times w_{s}$ scalars, one generator each.

For Monero, the width of one node on Selene is $w_{s} = 38$ and the width of one node on Helios is $w_{h} = 18$ .

Here is how the whole thing stacks up, drawn for a 6-layer tree. Reading it from the bottom: the leaves are the real outputs and every node above is one hash of the row below it (the hash can also be called Pedersen Vector Commitment).

■ Ed25519 (the real outputs) ■ Selene (layers 1, 3, 5) ■ Helios (layers 2, 4, 6)

Follow the coordinates as they cross floors. The output points $O, I, C$ live on Ed25519 then they are transformed into Wei25519 and their coordinates are numbers that happen to be the scalars Selene works with, so the layer-1 node $H_{1}$ (the $H$ of the equation above) is a Selene point. The coordinates of a Selene point are, in turn, the scalars Helios works with, so $H_{2}$ is a Helios point, then its coordinates are Selene scalars again, so $H_{3}$ is Selene, and the two curves keep taking turns up to $H_{6}$ , the root.

Proving that I know the tuple $O, I, C$ without revealing it

Alright. We know the tools we can use (Pedersen Vector Commitments) and how Monero organizes its hundreds of millions of transactions (with the special Merkle tree that intercalates two elliptic-curves on each floor). Now we can start showing how a prover can prove knowledge of his outputs (the tuple $O, I, C$ ) without leaking any information. Before we proceed, it is useful to reiterate our goal again: we want to prove that our output is on chain and for that we will:

prove that we know the path from the leaves up to the root of our output
prove that we know the secrets of those outputs

We will focus on 1) here and see how we solve 2) with the introduction of circuits.

In order to prove that we know the path from our leaves until the root, we will simply commit the hash of every children (a node) with a blinding factor up to the root. A verifier looking at those committed points must believe that the prover knows the path if he can prove that the difference of the committed new root is the same as the real and public root by a difference of the blinding factor that the prover will prove knowledge about.

To make it more visual, let's recap how each node (that builds the path) is defined: On every floor, we apply the hash equation (shown below) using different curves for points or scalars depending on the floor that we are ( $J$ is just a public point for domain separation). And the last node is the root.

N = J + \sum_{j} v_{j} \cdot G_{j}

And the root (the last node) is simply

R_{tree} = J + \sum_{j} v_{j} \cdot G_{j}

Now we want to prove knowledge of that path but not revealing it. So let's build a blinded version of each path:

C_{G}^{(i)} = \sum_{j = 0}^{L_{i} - 1} v_{j} \cdot G_{j} + b_{i} \cdot H

And the root of our blinded version is simply

C_{root} = \sum_{j} v_{j} \cdot G_{j} + b \cdot H

Notice that $J$ is not inside the commitment. What travels on chain is only the children plus the blind. The verifier adds $J$ back itself when it checks the root, which is why the difference below still cancels.

Since we have homomorphism (explained above), if we can prove knowledge that we know the difference $b \cdot H$ and that the nodes and children that we used are real ones, then we convinced the verifier that we know the path and that our output is on chain. Wait, there are too many ifs here. Let's start with the first one, how we prove knowledge on the blinds? For the root, this is simply done by a Schnorr Proof of knowledge (PoK) as shown in equations below. For the blinds of the branches underneath it things are a bit more complicated and they are proven inside the circuits, which the next page explains how exactly.

\underset{claimed}{\underset{⏟}{J + C_{root}}} - \underset{actual}{\underset{⏟}{R_{tree}}} = (J + \sum_{j} v_{j} G_{j} + b H) - (J + \sum_{j} v_{j} G_{j}) = b \cdot H

Call that leftover point $X = b \cdot H$ . If the prover used the real root's children, the difference is purely a multiple of $H$ . Any tampering with a child would leave a residue on some $G_{j}$ that no blind can absorb. So proving the top is honest is exactly proving knowledge of the $b$ in $X = b \cdot H$ , which is a plain Schnorr proof: sample a nonce $r$ , send $R = r \cdot H$ , take the Fiat-Shamir challenge $c$ , and answer $s = r + c b$ . The verifier's one line is

s \cdot H \overset{?}{=} R + c \cdot X

which is exactly the equation that the code checks. The whole root PoK proof is $(R, s)$ which are 64 bytes.

Commiting to the tree

Nice! Now the second question. How can the verifier be sure that the path we handed over really belongs to our own output, and not to somebody else's? Nothing so far stops a prover from taking any path he likes and climbing it up to the root. To fully answer that we need to know about the "circuits", but shortly, consider that there is a magic "circuit" with many magic operations and one of them is called "DLog" which proves knowledge of the blinding factor used to blind the path, on each floor, from the root until the leaves, where our tuple $O, I, C$ is located. The magic circuit also wires our tuple $O, I, C$ with the commited $\tilde{O}, \tilde{I}, \tilde{C}$ . So in the end, everything is connected! If we start from the published $\tilde{O}, \tilde{I}, \tilde{C}$ , the circuit connects them to $O, I, C$ , then those are connected to the path up to the root. And voilà! A prover cannot fool the verifier because it is the verifier (or the consensus code) who provides that circuit (and how it is wired!). The prover only enters his secret values and the final proof is something that looks random but the verifier can still validate it. To illustrate how the commitment to the path and the blinds work, have a look at the $C_{G}$ terms that the prover publishes before constructing the GBP proof.

The

C_{G}

terms

Here is an example showing the values and the meaning of the C terms in a 1-in/2-out transaction which can be seen at proof anatomy page. We have one input on a six-floor tree, which means 16 terms on Selene and 15 on Helios. Every one of them looks the same:

C_{i} = \sum_{j} v_{j} G_{j} + b_{i} H

but the list of values v_j represent different things.

The path from leaf to root:

term	what the `v_j` are	what it is for
Selene C0	the 38 leaves of our branch, as 228 coordinates	the leaf floor, the one holding our tuple; its blind is opened by Helios C3–C6
Helios C0	the 18 children of this floor, as 18 coordinates	floor 1 of the path; its blind is opened by Selene C12–C13
Selene C1	the 38 children of this floor, as 38 coordinates	floor 2 of the path; its blind is opened by Helios C7–C10
Helios C1	the 18 children of this floor, as 18 coordinates	floor 3 of the path; its blind is opened by Selene C14–C15
Selene C2	the 38 children of this floor, as 38 coordinates	floor 4 of the path; its blind is opened by Helios C11–C14
Helios C2	the 18 children of the root, as 18 coordinates	the top of the path; its blind is the one the Schnorr proof above opens, and it is the only floor no DLog touches

Wiring the published tuple to the real one. Five DLogs, each one its digits then its divisor.

term	what the `v_j` are	what it is for
Selene C3	the 253 digits of the blind on `O`, and the opened point's x	wires `O` to the published `O~`
Selene C4	the divisor for those digits, and the opened point's y	the second half of that same DLog
Selene C5	the 253 digits of the blind on `I`, over `U`, and the opened point's x	wires `I` to the published `I~`
Selene C6	the divisor for those digits, and the opened point's y	the second half of that same DLog
Selene C7	the divisor of the same blind over `V`, and no digits of its own	pins one blind across `U` and `V`: it reads Selene C5's digits
Selene C8	the 253 digits of the blind of that blind, over `T`, and the opened point's x	opens the key image blind
Selene C9	the divisor for those digits, and the opened point's y	the second half of that same DLog
Selene C10	the 253 digits of the blind on `C`, over `G`, and the opened point's x	wires `C` to the published `C~`
Selene C11	the divisor for those digits, and the opened point's y	the second half of that same DLog

Opening the floors' blinds. Each floor's DLog is committed on the other curve, which is why these two groups face each other.

term	what the `v_j` are	what it is for
Selene C12	the 255 digits of the blind of Helios C0	opens the blind of that Helios floor
Selene C13	the divisor for those digits	the second half of that same DLog
Selene C14	the 255 digits of the blind of Helios C1	opens the blind of that Helios floor
Selene C15	the divisor for those digits	the second half of that same DLog
Helios C3	the first 128 of the 255 digits of the blind of Selene C0	opens the blind of that Selene floor
Helios C4	the remaining 127 digits, and the opened point's x	the rest of those digits
Helios C5	the divisor's y coefficient and its first 126 yx coefficients	the divisor for those digits
Helios C6	the rest of the divisor, and the opened point's y	the second half of that same DLog
Helios C7	the first 128 of the 255 digits of the blind of Selene C1	opens the blind of that Selene floor
Helios C8	the remaining 127 digits, and the opened point's x	the rest of those digits
Helios C9	the divisor's y coefficient and its first 126 yx coefficients	the divisor for those digits
Helios C10	the rest of the divisor, and the opened point's y	the second half of that same DLog
Helios C11	the first 128 of the 255 digits of the blind of Selene C2	opens the blind of that Selene floor
Helios C12	the remaining 127 digits, and the opened point's x	the rest of those digits
Helios C13	the divisor's y coefficient and its first 126 yx coefficients	the divisor for those digits
Helios C14	the rest of the divisor, and the opened point's y	the second half of that same DLog

So now we are ready to proceed and understand how the circuits work. But before we continue, let's pause for a minute and have a look on how the final FCMP++ proof looks like on the blockchain: proof anatomy. We commited to $\tilde{O}, \tilde{I}, \tilde{C}$ , we provided an ownership proof (SAL) and we committed to the path and blinds of our enote with $C_{G}$ terms. Moreover the top of that path is legit, because the Schnorr proof (PoK - Proof of Knowledge) states that we know the difference from the commited root and the real (public) root.

← Merkle tree Next: Circuit →