In ringct, how are the range proofs kept separate from the pedersen commitments in a transaction?

Question

Are the range proofs and pedersen commitments part of a transaction? Or are they not kept in a transaction at all?

Answer 1

Suppose the sender wants to create a Pedersen Commitment to the amount of 23 XMR for a new output pubkey in a transaction. Without range proof, the sender simply creates the commitment as:

C = a G + 23 H

where a is a random scalar.

With range proof, there's an assumption in the protocol that any committed amount falls within a certain range; let's say such a range is 0,1,...,31. (In practice it's [0, 2^64), see the code.) Since we can represent the amount of 23 XMR in the binary form as:

23 = 1 + 2 + 4 + 16

The sender creates a commitment as:

C_0 = a_0 G + 1 H
C_1 = a_1 G + 2 H
C_2 = a_2 G + 4 H
C_3 = a_3 G
C_4 = a_4 G + 16 H
C = C_0 + C_1 + C_2 + C_3 + C_4

where {a_i} are random scalars. The idea of range proof is that the sender knows a private key of either C_i or C_i - 2^i H. Therefore, the sender can prove that the committed amount falls within the range [0,32) by generating 5 ring signatures containing two pubkeys each:

R_0 = {C_0, C_0 - H}
R_1 = {C_1, C_1 - 2 H}
R_2 = {C_2, C_2 - 4 H}
R_3 = {C_3, C_3 - 8 H}
R_4 = {C_4, C_4 - 16 H}

Borromean ring signature is suitable here for reducing the signature size.

Answer 2

latex

MRL's paper is confusing, it's better to read the source code.

There is a new output we want to make a "range proof".

$C=aG+10H$

$10$ is the amount, $a$ is the secret key. G and H are different base point.

We split it in four, we get:

$C_0=a_0G+0 \times 1H$

$C_1=a_1G+1 \times 2H$

$C_2=a_2G+0 \times 4H$

$C_3=a_3G+1 \times 8H$

because $2+8=10$. $a_i$ is random.

For the first line, we get $(C_0,C_0 - 1 \times 1H)$ these two points.

We know:

1. The first point's secret key is $a_0$.

2. We can't compute the second point's secret key.

3. The difference between the tow points is $1H$.

We sign a ring signature on these two points, a ring contains only two points.

$L_0= \alpha G$

$\alpha$ is random.

$q_1=H(L_0)$

$H()$ is a hash function to covert a point to scalar.

$L_1=s_1G+q_1P_1$

$s_1$ is random, $P_1$ is the second point.

$q_0=H(L_1)$

$s_0= \alpha -q_0a_0$ since $L_0= \alpha G=s_0G+q_0P_0=( \alpha G -q_0a_0)G+q_0P_0$

It's easy to verify this signature because:

$L_0+L_1=(s_0+s_1)G+(q_0+q_1)H$

The second line is similar but we should change the order of $(P_0,P_1)$ because we only know the second point's secret key.

At last we make four range proof.

In practice, the code is a little different for security.

Answer 3

Range proofs and and commitments are both kept in the transaction. Version 2 transactions (the ringct ones) now calculate transaction id a bit differently from v1 transactions, by hashing a set of hashes of several parts of the transaction, to allow future pruning of the range proofs. In that hypothetical future, range proofs will thus not be part of the (pruned) transaction anymore. Commitments will still be part of the transaction in that case.