Building on Knaccc's answer.
Curve25519
The first step to build an Elliptic curve library is to define a field of prime characteristic. In this case, the field is 2^255 - 19, I denote this with K. In most eprints it is denoted as F_p.
We then define a curve over this field of prime characteristics. The curve that we define in this case is a Montgomery curve called Curve25519. Where the points on the curve are in K. Not every point is on the Montgomery curve, just like regular curves. It is only the set of points whose x and y value satisfy the curve equation. The set of points which are on the curve is defined as M(K). These points form a Group.
Comparing Curve25519 and Ed25519
First, they are both defined over the same prime field K. But Ed25519 has a different curve equation. We know that there is a Group of points which are on the Montgomery curve denoted M(K). So the question is whether, the Group of points on Ed25519 are the same points?
Lets denote the group of points on Ed25519 as E(K). There is a relationship between Curve25519 and Ed25519, it's called a birational equivalence: https://crypto.stackexchange.com/questions/43013/what-does-birational-equivalence-mean-in-a-cryptographic-context
The link above explains it very well, in short, there is a way to transform Curve25519 to look like Ed25519 except for a few points. These are called the exceptional points.
This means that M(K) and E(K) have roughly the same amount of points. The exceptional point, only comes up in the affine mapping, so can be avoided if we use projective.
In short, we can think of there being a mapping from M(K) to E(K). We are actually interested in E(K), but I mentioned Curve25519 first because Ed25519 came from it, in the relationship mentioned above.
Order of E(K)
The next question is "How many points are in the Group E(K)?"
There is paper by Craig Costello which says that the order must be even for both Edwards and Montgomery Curves.* In our case, the order is 8q. Where q is prime.
By lagranges theorem, E(K) can be decomposed into smaller groups which are multiples of its order. One group has has q points E_1(K) and the other group has 8 points E_2(K). This has been slightly simplified, see the link that knaccc posted above.
We are now looking at three groups E(K), E_1(K) and E_2(K).
Notice that the points in E_1(K) and E_2(K) are in E(K) since E_1(K) and E_2(K) are just decompositions of EK(). This means that E_1(K) and E_2(K) are subsets of E(K). We can go further and show that they are both subgroups.
Small subgroup
The points in E_2(K) have order 8. This means that if I take any point in E_2(K) and add it to itself 8 times, then I will arrive at a special point called the identity point. You can think of it as the zero point.
For example; if P \in E_2(K) then P + P + P + P + P + P + P + P = 0 . Instead of manually writing out the additions I could have equivalently written 8P = 0. This is known as scalar multiplication. In the case of 8P , 8 is the scalar.
The points in E_1(K) have order q. This means that in order to arrive at 0. You need to add the point to itself q times. ie if P \in E_1(K) then qP = 0.
The number 8 is small and all points in E_2(K) have an order of 8. We call this subgroup the small-order subgroup.
Contrasting, q is a prime and is large and all points in E_1(K) have an order of q. We call the subgroup E_1(K) the prime order subgroup.
E_1(K) and E_2(K)
So what's the problem? The problem is a mixture of two things:
- We cannot force the user to use either E_1(K) or E_2(K). We have to assume that they have taken points from E(K).
- You can mix points in E_1(K) and E_2(K) together.
Constructing the attack
Context: You are only allowed to use a point once. Using the point twice is analogous to double spending.
Goal: The attacker will attempt to use a point twice.
- Pick a point in E_1(K). Lets call it P.
- Pick 2 points in E_2(K). lets call them R_1 and R_2.
- Compute T_1 = P + R_1 and compute T_2 = P + R_2.
The attacker tells Alice "T_1 is his point, you can use it to check on the blockchain when I make a payment."
The attacker tells Bob "T_2 is my point, you can use it to check on the blockchain when I make a payment".
These two points look different. But when we multiply it by a number that is a multiple of 8. We see that R_1 and R_2 disappear and the points become equivalent.
8 * T_1 = 8 (P + R_1) = 8 * P + 8 * R_1 = 8P + 0 = 8P.
As knaccc said above, whenever the scalar is a multiple of 8, the part that comes from E_2(K) disappears. So it looks like we have different points, but when multiplied by a multiple of 8, we can make the point be equivalent. This means that the attacker does not need to know the private key to T_1 or T_2. He just needs to sign with the private key for P.
This has lead to attacks as seen in this link : How does the recent patched key image exploit work in practice?
If I have not explained it well so far, essentially E_2(K) is bad and E_1(K) good!
Getting rid of E_2(K)
The way that Monero uses is called a subgroup check, and we essentially check if T_1 is in the prime subgroup, in our case this is E_1(K). To check if a point is in a specific subgroup, you multiply that point by the subgroup order and check if you get the identity (zero) point.
Let's take T_1 again and multiply it by the order of the prime subgroup.
q * T_1 = q (P + R_1) = q * P + q * R_1 = 0 + q*R_1 = qR_1.
If our point T_1 was in E_1(K), then it would have produced the identity. Since we did not arrive at the identity point, we know that this point has components in E_2(K).
This check is great and does what we want but it is also expensive to multiply by that large prime q. We must do this to every point we receive before running any verification procedure.
This check guarantees that a point is always in E_1(K). You can think of it as mapping E(K) -> E_1(K), where the order of E_1(K) is q.
What if we could build a group of order q from E(K)? This would also solve our problem. This is essentially what Ristretto does. You can think of it as E(K) -> 2E(K)/E[4] . Notice that it does not map to E_1(K). E_1(K) and 2E(K)/E[4] are groups of prime order, but they do not contain the same points. E_1(K) contains points which are in the prime order subgroup of E(K) while 2E(K)/E[4] contains points which form a prime order subgroup from E(K).
Ristretto
Ristretto is an extension on Decaf: https://www.shiftleft.org/papers/decaf/decaf.pdf
Above we alluded to the relationship between Curve25519 and Ed25519. There is another type of relationship that curves can have which we call an isogeny. In the Decaf paper, it cites a paper which shows that there is a family of curves whom are all isogenous to each other.
Furthermore, when we transform one curve to another curve, it can pick up a factor. For example, given two curves E' and E'' which are 2-isogenous, we have functions which maps points between E' and E'' and each map will double the corresponding point on the other curve. Here is a link to a test case for a 2-isogeny: https://github.com/cloudflare/circl/blob/master/ecc/goldilocks/isogeny_test.go#L21
The test in the link maps a point from E' to E'', then immediately maps the point back to E' . This means that the resulting point on E' will be 4 times the original point.
Decaf does not work outright for Ed25519, but it does for Curve25519, however since Curve25519 and Ed25519 are birationally equivalent. The formulas can be modified to map to Ed25519 through Curve25519. This is what Ristretto does along with few other modifications: https://ristretto.group/details/isogenies.html#from-montgomery-to-edwards-via-isomorphism
So far, we have a family of curves, one of which is a Montgomery curve in our case Curve25519 and we have Ed25519 which can be mapped to, by any one of the family of curves through Curve25519. The only important curve in the family of curves worth mentioning is the Jacobi quartic curve. The Jacob curve is 2-isogenous to the Curve25519.
Encoding the point
Let's say I have a point P in E(K). Recap that E(K) is the group of points on the Ed25519 curve. First we use our birational map the point to Curve25519. So the point is now a point in M(K).
From the decaf paper, we know that there is a 2-isogeny from the Montgomery Curve to the Jacobi quartic. We apply this isogeny and our point is mapped to a point on the Jacobi quartic, but since it is a 2-isogeny it also picks up a factor of 2. If P was in the small-order subgroup E_2(K) then when we map it to the Jacobi quartic we would only need to double the corresponding Jacobi point twice in order to get the identity element.
What is the importance?
Instead of checking if our point is in the correct subgroup, our strategy will be to now group all points which differ by a point of order 4 and force an algorithm to output a specific point. All of the points which differ by a point of order 4 are exactly all of the points which were equivalent when we multiplied by a scalar which was a multiple of 8 in E_1(K).
To see this, let P \in E_1(K) and let R_1, R_2 \in E_2(K)
Compute T_1 = P + R_1 . When T is mapped to the Jacobi quartic, it picks up a factor of 2.
2 * T_1 = 2 * P + 2* R_1
2 * T_2 = 2 * P + 2* R_2
Notice that because R_1 was doubled, it is now an order of 4 away from the identity point. So T_1 and T_2 differ by a point of order 4, when we apply the isogeny to map it to the Jacobi quartic. Notice also that P + 0 also differs by a point of order 4 and is also in this group of point which differ by a point of order 4.
Why is this important?
The Jacobi quartic has a really succinct representation for all of it's points which differ by a point of order 2. But for this explanation, lets pretend it is by an order of 4, the logic still follows through. :https://ristretto.group/details/isogeny_encoding.html#encoding-mathcal-j--mathcal-j2
As the link mentions, it is possible to consistently pick one of the points in the set of points which differ by an order of 2(again lets pretend it says 4), by enforcing two sign checks. These two can be easily programmed into an algorithm.
Another example of a sign check, is when you are sending a point to another user. You take the Y co-ordinate and use a bit to denote the sign of the X co-ordinate. In this case, you are distinguishing between the negative and positive-ness if the X co-ordinate. This check is usually done on the Edwards curve Ed25519.
Contrasting, this check is computed on the Jacobi quartic curve, which is not the curve that we are doing arithmetic on. It is Ed25519. Fortunately, the encoding can be transported to Ed25519 https://ristretto.group/details/isogeny_encoding.html#transporting-an-encoding-along-an-isogeny
So we make our sign choices in the Jacobi quartic, then we transport these sign choices to the correct curve.
Summary
When you compress a point, you use a 2-isogeny to transport the point to the Jacobi quartic, picking up a factor of 2, you then make two sign choices which picks a specific point. When you decompress a point you check that these two checks are satisfied on the Jacobi quartic curve, which means that this point is the specific point out of all of the points which differ by a point of order 4. Then you transport the point to the Ed25519 curve.
Important Details
In the above sentence, I said specific point , I did not say a point that is in E_1(K). The point that we pick as a representative can be in E_2(K) , we just need to consistently pick the same point, which our sign check allows.
_Question: So If we can pick a point in E_2(K) , how does Ristretto solve the prime group problem?_
Ristretto does not force a point to be in E_1(K). It builds a prime order group from E(K). And it does this by always picking the same point out of the possible 8 equivalent points. This new Ristretto group will have prime order, because it is always picking 1 out of the 8 possible points.
Does this really solve the problem?
We can formulate the problem another way. Each Point in E(K) had 8 different equivalent points. No matter which one of these 8 equivalent points you give the Ristretto algorithm, it will give you exactly the same one. The other 7 points are no longer representable.
Caveat
There is are two security caveats. We are assuming that all points are passed through the Ristretto ENCODING algorithm.
If the points are modified at a later point, after going through the encoding algorithm. Then it is possible to simply change the representative point that was chosen.
This is why you must only add Ristretto points with Ristretto points. Ie only the representatives of the set of points should be used. You should never mix a RistrettoPoint with an EdwardsPoint, because the EdwardsPoint you are mixing with, may not be the representative for the set of possible points. This is mentioned in the IETF you linked, at the end I think.
Thing I have omitted or lied about
The Jacobi quartic actually has a succinct representation for points which differ by an order of 2, and Ristretto applies an extra step to transform the points which differ by an order of 4 to points which differ by an order of 2. This is explained in the torquing section, but is not important to understand most of Ristretto.
Hope that helps. If any mistakes are found, please feel free to correct them.
742eefe877d713693985a6e0e1376033cf115f3c8d02f7c40a1ee68d75824d39or results replicated using a few Monero constructs % echo -n "no" | bx base16-encode | bx sha256 | bx sha512 | cut -c 1-64 | ./clamp | ./sc_reduce32 | ./secret_key_to_public_key742eefe877d713693985a6e0e1376033cf115f3c8d02f7c40a1ee68d75824d39. Finally, libsodium's Ristretto functionality is documented at doc.libsodium.org/advanced/point-arithmetic/ristretto