Ring Confidential Transactions Discussion

[smoothie]

This thread is specifically for discussing Ring Confidential Transactions as defined and outlined in Shen Noether's RingCT pdfs

My Goal of this thread is to simplify RingCT and its definition as much as possible so others can understand it (including myself)

Disclaimer: I am just a curious mind. I do not pretend to know anything about RingCT and its underlying math/proofs/defintions. I am merely a curious soul trying to understand how this all works. I welcome any and all discussion directly related to the topic of this thread. IF I HAVE WRITTEN SOMETHING WRONG OR INCORRECTLY PLEASE POST OR PM ME ABOUT IT SO I CAN CORRECT IT.

Latest version: https://github.com/ShenNoether/MiniNero/raw/master/RingCT0.5_copy.pdf

This paper is very math heavy and some variables are defined and some aren't.

Hopefully after discussion there can be more clarity on the math that is used within.


Preface/Purpose:

Currently in Monero amounts that are transferred are public to view. Ring CT is an attempt to obfuscate the amount of a transaction (and all of its inputs and outputs) to add more transactional privacy.


Definitions:

MLSAG - Multilayered Linkable Spontaneous ad-hoc group signatures

E - an elliptic curve equation; −x² + y² = 1 + dx²y²;

q: a prime number; q = 2²⁵⁵ − 19

d = -121665/121666

P_j = xG = Public Key

G = Ed25519 base point

l: a prime order of the base point; l = 2²⁵² + 27742317777372353535851937790883648493 =~ 7.25 x 10⁷⁵

x = signer's spend key

I = xH(P_j) = Key Image (unique - no copies/duplicates allowed)

H = hash function returning a point (in practice toPoint(Keccak(Pk)))

h = hash function toScalar(Keccak(Pk))  <---- can take multiple parameters concatenated

m = message

α, s_i, i =/= j, i ∈ {1,...,n} are random values in Z_q (the ed25519 base field)
s_j = α − c_j·x mod l
α = s_j +c_j·x mod l

L_j = αG = s_j·G + c_j·P_j <---- Intermediate value if i = s

R_j =αH(P_j) <---- <---- Intermediate value if i = s

c_j+1 = h(m,L_j,R_j) or  A.K.A. "non-interactive challenge"

σ = (I,c₁,s₁,...,s_n) = Signature

Key Vector = the collection of all public keys Y = (y₁,...,y_r) and corresponding private keys X = (x₁, ..., x_r)

Generalized Ring = [P_ij] where i = 1,...,n and j = 1,...,m = n-members and all of which have EXACTLY m-keys




<Other heading not sure what to call it lol>

1. What I've deduced from reading up until page 6 is that the idea of obfuscating amounts will be accomplished with
"mixing" with n signers that have the same amount of m keys.



2. Also noticed that the equations are recursive mod n. If you don't know what that means that means that for example define the following:

L_j = s_j·G + c_j·P_j

c_j+1 =H(m,L_j,R_j)

Since L_j is part of the definition of c_j+1  and c_j is part of the definition of L_j that is the definition of recursion. A function/equation calling itself within its definition.

The mod portion is the remainder of a division (example: 5 mod 3 = 2).

In the context of this paper c_n+1 = c₁ AND c_n+2 = c₂...and so forth, because (n+1) mod n = 1 and (n+2) mod n = 2


s_j = α − c_j·x mod l
α = s_j +c_j·x mod l


3. With a single c_i value, the P_j values, I (key image), and all the s_j values...

... all other c_k values can be deduced while k =/= i.

This provides space saving of about 1/2 the space/size when creating the signature. <------ is this part of Compact CT?

The signature therefore is:

σ = (I,c₁,s₁,...,s_n)


4. Assuming a GENERAL RING composed of n-member and  EXACTLY m-keys with the following requirements:

a. Exactly 1 of the n-signers gives a signature on all m of their keys.

b. If that same user uses any of those m-keys to in another GENERAL RING SIG then, the two RINGS are linked.


<more to come>



Elliptic-curve overview:

Example #1 with d = 30:

x² + y² = 1 - 30x²y²



Center of the curve is point (0,0) for reference.




Example #2 using the actual curve E as defined above:

<-------- Actual Ed25519 curve used in Monero/cryptonote



As you can see above in the blue is the curve of the equation in the image above it. Here is the site where the graph was generated https://www.desmos.com/calculator/ialhd71we3

Just paste the following into a new Elliptic curve line on the left:

-x^2\ +y^2\ =\ 1\ +\left(\frac{\left(-121665\right)}{121666}\right)x^2\cdot y^2

Question: Why do you only show the graph from -7.25x10⁷⁵ to 7.25x10⁷⁵ on the x-axis?

Answer: Because l as it is defined 2²⁵² + 27742317777372353535851937790883648493 =~ 7.25 x 10⁷⁵

Because we mod the base point G by l in our computations this why the graph essentially "ends" at those points.





Example #3
Now if you play with some of the values on that site you can get a different modified curve that doesn't just look like two parallel lines just to get a gist of how elliptic curves look like when you slightly modify the values:







Example #3
And modifying it one more time you get:







Helpful resources:

ECCHacks - A gentle introduction to elliptic-curve cryptography [31c3]

Online Elliptic Curve Points Graph Generator

Will be editing OP to add more information as I am able to digest it in my limited capacity brain.  

[TPTB_need_war]

I could explain the math for Shen's Ring Confidential Transactions in layman's terms (it really isn't that difficult at all once you think about it in terms of the properties of a modulo operation in math), but I don't have time right now to organize the prose.

Edit: after writing the following it caused me to realize I had overlooked (or conflated) a detail which changed the conclusion of my analysis as follows. Thus I will eventually be explaining the math in layman's terms for (Compact or just) Confidential Transactions and how to combine them with one-time rings of Cryptonote.

Also this is a lower priority right now for me, I now think (recently discovered) that one-time ring signatures are not tenable (against DDoS) for micro-transactions scaling level (regardless whether alone as for Cryptonote, combined with Blockstream's Confidential Transactions as Shen has published, or combined with an improved version of Denis's Compact Confidential Transactions as I claimed to have accomplished but haven't yet published).

Also one-time ring signatures do not obfuscate IP address which means correlation by IP can unmask the rings, so I now view them as a waste of time, because to obfuscate the IP addresses requires a non-autonomous form of mixing (e.g. CoinShuffle) which also provides the same function as a ringa ring function but apparently not in the presence of homomorphic sums.

[smoothie]

Added some images and info to the OP. It's a work in progress.

[smoothie]

There are two hash functions being used.

h <-- takes 3 parameters (m, L_j, R_j)

and

H which used Keccak(P_k)

Not sure what h is for the moment.

[TPTB_need_war]

There are two hash functions being used.

h <-- takes 3 parameters (m, L_j, R_j)

and

H which used Keccak(P_k)

Not sure what h is for the moment.

I don't have Shen's white paper up in front of my face at this moment, but for the hash function applied to the base point H, that is a decomposition of the hash output back to a legal base point on the curve:

...(that did not employ H, the decomposed hash of G)...

...

Where I have seen the decomposition from a Hash function as the base point for breaking the factorability between commitment sets such as in Shen-Noether's design for CT+ CN (where knowing the commitment point of H relative to G, would enable one to cheat)...

Can't just hash a base point on an ECC curve and expect to get back a point on the curve. You have to decompose the ARX confusion (obfuscation of invertibility) provided by the hash function in some way that yields a valid base point. I haven't actually yet learned the details of how this done.  I just know conceptually what it is doing.

I don't really have time to attempt to write up how Shen's Ring Confidential Transactions works at the moment. But when I do, the quality of my prose w.r.t. to layman's understanding should be superior to this very rushed explanation of Winternitz signatures I did in foggy brained state-of-mind in the wee hours of this past night:

More code released into the open source public domain:

https://github.com/shelby3

My winternitz explanation is perhaps the most accessible you will find for a layman:

https://github.com/shelby3/winternitz/blob/master/winternitz/winternitz.h

In that explanation, I think I correctly invented either an improvement to Winternitz signatures, or at least pointed out what afaics is a (just slightly) suboptimal description in the venerable Daniel Bernstein's Post Quantum Cryptography.

[smoothie]

There are two hash functions being used.

h <-- takes 3 parameters (m, L_j, R_j)

and

H which used Keccak(P_k)

Not sure what h is for the moment.

Shen clarified this on Reddit:

H = toPoint(Keccak)

h = toScalar(Keccak(Pk))

[TPTB_need_war]

Shen clarified this on Reddit:

H = toPoint(Keccak)

h = toScalar(Keccak(Pk))

Right that is what I was pointing out in my prior post, that "toPoint" makes sure the result is a valid point on the elliptic curve (i.e. in the field F_p) whereas a normal hash function call assumes the result is valid over the real numbers (i.e. field R). So you use a different hash function depending on whether the input/output are points on the curve or just real numbers.

The point of hashing the base point G to get H in Ring Confidential Transactions, is so that no one knows (nor can find) the commitment value that created (or any other attribute of) H (that would define a suitable factoring relationship to G). This is so that the transaction values are on the base point H and the signing keys are on the base point G, and thus it is implausible to lie about the transaction values. I will need to explain this more carefully when I have time. Btw, you don't really need to know how elliptic curve cryptography works. All you need to really know are it obeys the properties of an abelian group, has the hiding properties of a modulus field (e.g. for the hidden committed values), and in the homomorphic sense that for example adding commitments obeys these properties on the hidden values committed. Note this paragraph is rushed and sloppy so it is not precise.

Btw, I remembered that Cryptonote has a reference to how this "toPoint" is accomplished (and as I said, I haven't yet studied how it is actually accomplished, just knowing what it does is sufficient for now and any Cryptonote coin already has an implementation of it, or appears Keccak includes an implementation as standard):

https://cryptonote.org/whitepaper.pdf#page=17

See section "Notes on the hash function H_p" and its reference to:

[37] Maciej Ulas. Rational points on certain hyperelliptic curves over finite fields. Bulletin of
the Polish Academy of Sciences. Mathematics, 55(2):97–104, 2007.

[smoothie]

made a few updates to the OP.

[newb4now]

Your OP is very good. I cross-posted here since we already have a thread for  CryptoNote technical discussion that includes Confidential Transactions discussions
https://bitcointalk.org/index.php?topic=1190988.msg13170571#msg13170571

[smoothie]

Your OP is very good. I cross-posted here since we already have a thread for  CryptoNote technical discussion that includes Confidential Transactions discussions
https://bitcointalk.org/index.php?topic=1190988.msg13170571#msg13170571

Thanks it's a work in progress... and thanks for the X post. 

[smoothie]

Added description of GENERAL RING (#4) to OP.