Can someone walk me through a simple example to explain how RingCT works?

Question

Original: https://www.reddit.com/r/Monero/comments/5irg81/questions_regarding_the_cryptography_behind_ringct/

---

I just read the RingCT paper, and there are a couple things that could use some clearing up for me.

What is the m (message?) value that is used in all of the hashes (and one of the indexes for the signature)? Is this our mixin value?

Also, does the actual signature in the RingCT implementation contain the presumably long list of randomly generated s-values? And are all of those s values generated independently from one another? Are they basically the equivalent of the q and w random scalars chosen in the CryptoNote whitepaper?

Can someone walk me through a simple example showing how many of these random numbers must be generated for a given transaction? For instance, if I want to send to one person 18.37 XMR with a mixin of 4.

If there really are so many additional parameters, as seems to be the case, why exactly does RingCT take up less space on the blockchain?

Thank you so much!

Answer 1

Let's say you'll use two of your outputs, 12.34 XMR and 7.89 XMR and send 18.37 XMR to your recipient for a fee of 0.022 XMR and change of 1.838 XMR. If you use mixin of 4, you'll be creating two rings with 5 output keys contained in each. You'll pick a secret index between 1 and 5 for each ring, so let's say you picked 2 for the first and 4 for the second. I.e., you know the private keys of these two output public keys:

P_2^1 = x^1 G
P_4^2 = x^2 G

Here, underbar is used for denoting an index in a given ring (1,...,5), while hat is used for denoting the index of an input (1 or 2). You also know the masks for the Pedersen Commitment paired with P_2^1 and P_4^2:

C_2^1 = a^1 G + 12.34 H
C_4^2 = a^2 G + 7.89 H

Then, you choose dummy ring partners to create two rings:

( P_1^1, P_2^1, P_3^1, P_4^1, P_5^1 )
( P_1^2, P_2^2, P_3^2, P_4^2, P_5^2 )

Note that each P_i^j has its associated Pedersen Commitment C_i^j. Now you generate what's called pseudo output for each ring (which is not officially described in MRL-0005, see Issue #6 in the GitHub repository):

D^1 = b^1 G + 12.34 H
D^2 = b^2 G + 7.89 H

where b^1 and b^2 are random scalars. These pseudo outputs are recorded in the transaction. Let us define another pubkey:

Q_i^j = D^j - C_i^j

Important thing to note here is that you know the secret keys of:

Q_2^1 = (b^1 - a^1) G = z^1 G
Q_4^2 = (b^2 - a^2) G = z^2 G

These secret keys are needed for signature generation. You also need to generate two key images:

I^1 = x^1 HashP(P_2^1)        // HashP(.) outputs an EC point
I^2 = x^2 HashP(P_4^2)

With these ingredients at hand, you can generate the signature as follows: first randomly pick alpha^1 and beta^1 and compute:

L_2^1 = alpha^1 G
R_2^1 = alpha^1 HashP(P_2^1)
S_2^1 = beta^1 G
c_3^1 = HashS(Msg, L_2^1, R_2^1, S_2^1)     // HashS(.) outputs a scalar

Here, Msg is the message describing the transaction: e.g., which output pubkeys constitute each ring, the fee, the newly generated output pubkeys, etc.

Then you randomly choose r_3^1 and s_3^1 and compute:

L_3^1 = c_3^1 P_3^1 + r_3^1 G
R_3^1 = c_3^1 I^1   + r_3^1 HashP(P_3^1)
S_3^1 = c_3^1 Q_3^1 + s_3^1 G
c_4^1 = HashS(Msg, L_3^1, R_3^1, S_3^1)

You repeat this computation two more times with the index being incremented, and the index goes back from 5 to 1:

c_1^1 = HashS(Msg, L_5^1, R_5^1, S_5^1)
L_1^1 = c_1^1 P_1^1 + r_1^1 G
R_1^1 = c_1^1 I^1   + r_1^1 HashP(P_1^1)
S_1^1 = c_1^1 Q_1^1 + s_1^1 G
c_2^1 = HashS(Msg, L_1^1, R_1^1, S_1^1)

And you do a trick to r_2^1 and s_2^1 as:

r_2^1 = alpha^1 - c_2^1 x^1
s_2^1 = beta^1  - c_2^1 z^1

This makes the following magic possible:

c_2^1 P_2^1 + r_2^1 G            = c_2^1 P_2^1 + (alpha^1 - c_2^1 x^1) G            = alpha^1 G
c_2^1 I^1   + r_2^1 HashP(P_2^1) = c_2^1 I^1   + (alpha^1 - c_2^1 x^1) HashP(P_2^1) = alpha^1 HashP(P_2^1)
c_2^1 Q_2^1 + s_2^1 G            = c_2^1 Q_2^1 + (beta^1  - c_2^1 z^1) G            = beta^1 G

I.e., the hashed value c_3^1 becomes independent of (c_2^1,r_2^1,s_2^1).

For anyone but you, the resulting sequence of numbers (c_1^1, ..., c_5^1) looks really magical because the following special relationship holds:

c_2^1 = HashS(Msg, <some value depending on (c_1^1, r_1^1, s_1^1)>)
c_3^1 = HashS(Msg, <some value depending on (c_2^1, r_2^1, s_2^1)>)
c_4^1 = HashS(Msg, <some value depending on (c_3^1, r_3^1, s_3^1)>)
c_5^1 = HashS(Msg, <some value depending on (c_4^1, r_4^1, s_4^1)>)
c_1^1 = HashS(Msg, <some value depending on (c_5^1, r_5^1, s_5^1)>)

No one but you can create this and know which keys are fake, hence the unforgeability and anonymity of the ring signature scheme.

This way, the first ring signature is generated:

R^1 = [ Msg, (P_1^1,...,P_5^1), (C_1^1,...,C_5^1), I^1, D^1, c_1^1, (r_1^1,...,r_5^1), (s_1^1,...,s_5^1) ]

In practice, P_i^j and C_i^j are stored somewhere in the blockchain and the signature contains only indices of them. You do exactly the same computation for the other ring R^2.

You'll also create two new output pubkeys along with their associated commitments corresponding to 18.37 XMR for your recipient and 1.838 XMR for your change. You randomly choose e^1 and e^2 such that

b^1 + b^2 = e^1 + e^2

and compute two commitments:

E^1 = e^1 G + 18.37 H
E^2 = e^2 G + 1.838 H

This way, anyone can observe that the total amount is the same before and after the transaction:

D^1 + D^2 = E^1 + E^2 + 0.022 H

(I omitted the range proof part which is needed to ensure that every amount in a commitment is between 0 and 2^64 .)

See also: Can I manually check consistency of Pedersen Commitments in RingCT?