Edwards curves point compression

In addition to the post about Edwards curves, lats take a look on a useful feature that this curves allow. As I said earlier, the Ed25519 for example, is defined over \(F_{2^{255}-19}\) field, where every value requires 255 bit for the binary representation. So every point will take about 510 bit. Using the point compression algorithm, we can encode every point using only 256 bits by transferring only the \(y\) coordinate.

Using the Edwards curves equation \(ax^2 + y^2 = 1 + dx^2y^2\) we can express the \(x\) coordinate (with an assumption that \(a = -1\)) as \(x^2 = \frac{y^2 - 1}{dy^2 + 1}\), which means that \(x\) can have two possible solutions (+ and -). In the modular terms (since we have an odd modulo \(q\)) it means that \(x\) can have the odd and even representations. This information can be encoded into one bit.

Then, to decode the point coordinates, after separating parity bit from \(y\) coordinate, we have to calculate the root square. There are several methods to deal with the square root in \(F_q\). One of them is to use the feature that \(q = 2^{255} - 19 \equiv 5 (mod 8)\). In the \(F_q\) multiplicative group we have \(q - 1\) elements (then for every \(x \in F_q: x^q = x\)), so for every square \(\alpha = \beta^2\) we have \(\alpha^4 = \beta^8 \rightarrow \alpha^{p+3} = \beta^8 \rightarrow \alpha^\frac{p+3}{8} = \beta\). From the equation \(\alpha^4 = \beta^8\) we can observe that there can be two possible solutions \(\pm\alpha = \beta^2\). In the case when calculated \(\beta\) satisfies \(\beta^2 = -\alpha\) we should multiply it on \(\sqrt{-1}\).

For the \(\sqrt{-1}\) we can follow the same transformations: \(x^2 = -1 \rightarrow x^4 = 1 \rightarrow x^4 = 2^{q-1} \rightarrow x = 2^\frac{q-1}{4}\). The base \(2\) element was selected as the most comfortable element for multiplication.

So finally, for the equation \(x^2 = \frac{u}{v}\) we can calculate \(x' = \sqrt{u/v}\) and check that \(v\cdot x' = -u\) and if so multiply the \(x'\) on \(\sqrt{-1}\). On the final stage, we use the parity bit to check that we’ve recovered same coordinate with same parity.

Edwards curves and EdDSA verification trick

Twisted Edwards curves has a form of \(ax^2 + y^2 = 1 + dx^2y^2\) (for fields with characteristic not 2) where the curve order can be represented as \(l \cdot 2^c\), where \(c\) is a natural number, \(l\) is a big prime number. So, it is obvious that our elliptic group has two subgroups and for the cryptography purposes wew always may select the group defined by the large prime \(l\).

Nevertheless, an attacker can select points from smaller subgroup and this points will be eligible for using in group operations. To ensure that this never can happen, in EdDSA protocol verifier additionally uses the \(2^c\) cofactor to increase the security of the equation \(2^c\cdot rG = 2^c\cdot aG + 2^c t \cdot K\). It ensures that all points are in the lager prime curve subgroup, otherwise multiplication by the cofactor results with infinite point.

Briefly about singular curves

The Weierstrass normal form of elliptic curves (in fields with characteristic != 2 and != 3) \(y^2 = x^3 + ax + b\) over \(Z_p\) field has found many applications in cryptography. But this curve form has also two types: non-singular ( that can be used in crypto) and singular (that can’t). Let’s take a look why singular curves causes problems in cryptography.

Singular curves is the curves where discriminant is equal to zero, so \(4a^3 + 27b^2 = 0\)

In such cases, this curve can be represented in two forms:

1. \(y^2 = x^3\) (when there is a triple root 0) where using mapping \((x, y) \rightarrow \frac{x}{y}\) it gives an isomorphism to additive group ( with same order \(p\)) where discrete logarithm is trivial.

2. \(y^2 = x^2(x + c)\) (when there is a double root 0) where using mapping \((x, y) \rightarrow \frac{y + xc}{y - xc}\) it gives an isomorphism to multiplicative group (with order \(p^2\)) where discrete logarithm problem is easy to solve for default elliptic key sizes.

This both cases are perfectly overviewed in Section 2.10 of Washington’s Elliptic Curves: Number Theory and Cryptography.

Here is an example how to solve discrete logarithm problem for such curves.

Bulletproofs++ implementation

Zero-knowledge range proofs can be shortly introduced as one of the most important algorithms for confidential transactions. After Bitcoin launch lots of cryptographers started to create the solutions to make blockchain transactions more and more anonymous and one of such solution was to hide user balances in cryptographic commitments (in particular - Pedersen commitments). This approach requires the way to check that amounts in transaction corresponds to each other without group order overflowing. That is why a wide variety of range proof protocols appeared.

The Bulletproofs protocol published in 2017 introduced how to verify value range committed in Pedersen commitment. Later, Blockstream cryptographers introduces more efficient protocol Bulletproofs+ that currently implemented in many different platforms e.g - Monero.

The last protocol generation (Bulletproofs++) that is designed to be more efficient the ‘+’ version was introduced in 2022 paper. My partner, Mykhailo Sokolov, and I have spent the last three months thoroughly studying this document in order to develop implementation libraries in Go and Rust that are suitable for use in production projects.It was unexpected to find errors in the original document, rendering the described protocol unusable in its current form. Consequently, we have developed a corrected version of the Bulletproofs++ protocol and are currently in the process of drafting an article to showcase our revisions.

In conclusion, our solution has \(2G\) points advantage over existing Bulletproofs and Bulletproofs+ protocols on proving of one 64-bit value and this advantage will increase for more values per proof.

Our implementation can be found here:

• Rust
• Go