9

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!

9

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?

  • Amazing response, I haven't seen anything else that explains it as well as this one. However, I think it's incomplete. How do one know that the Pedersen Commitment given corresponds to the key image given? Is there a key image for the pedersen commitment that we're missing in this explanation? I could theroetically have two transactions A and B where A moves a large amount of XMR and B is a dummy transaction. Then, I could give two different key images: One for A, and One for B, using the Pedersen Commitment for the much larger transaction A. – Nicholas Pipitone Nov 16 '18 at 1:46
  • Oh, I see. If the sender tried to use a public key from index i and commitment from index j, so that D - C_j was known but doesn't match index i, then when the hash calculations wrapped back around to index i the sender would not be able to solve for s_i. This is because D - C_i no longer match (And leave an H term). – Nicholas Pipitone Nov 16 '18 at 7:44
  • I think you have a misunderstanding. We don't need to think about key images for Pedersen Commitments because each commitment is always paired with its corresponding output public key in the blockchain. Key images for output keys will suffice for preventing double spend. – kenshi84 Nov 18 '18 at 3:02
  • I wasn't understanding why the public key and the commitment had to be from the same index, since I was thinking I could solve for s_i for another index. I understand now why they have to line up. – Nicholas Pipitone Nov 18 '18 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.