Propagating Elliptic Curve Points over the Network - Encoding of Banderwagon Points

So this week was pretty much figuring out the implementation of the encoding of the points on the Banderwagon curve. While writing the code for the encoding I realized that the constantine library doesn’t have the feature to calculate the Y-coordinate from the X-coordinate. So I had to implement that first. Summing up what I did this week : -

• Implemented the Y-coordinate calculation from the X-coordinate for the Banderwagon curve
• Implemented the serialization system for the points on the Banderwagon curve
• Implemented the deserialization system for the points on the Banderwagon curve

Track the issue -> here and the PR -> here.

Calculating the Y-coordinate from the X-coordinate

Lets first explore the mathematical angle of this. From the equation of the curve as we can deduce the the formula for calculating the Y-coordinate from the X-coordinate

$$y^2 = \frac{1-ax^2}{1-dx^2}$$

Now we nedd to take the square root of $y^2$, and that would be out result but we need to abort if the square does not exist. Now all these operations are not very easy to write in constantine as cannot compute and just return the value, why?
Any field or curve elements, we pass them as var parameter, which we need to return.Returning large elements is one of the source of slowness in all those Rust libraries.

Serialization of the points

When serialising a point, remember we want $(x,y)$ and $(-x,-y)$ to serialise to the same bitstring. This can be done by taking the sign of the $y$ co-ordinate, multiplying it by the $x$ co-ordinate and sending the result as a bit string. This works since

$$serialize(x,y) = sign(y) \times x \\ serialize(-x,-y) = -sign(y) \times -x = sign(y) \times x$$

Ok much of maths, so how do we implement it in code? Also what exactly is the implementation of $sign()$ function. Lets see the process of serialization

• convert the Projective point to Affine point
• calculate the $sign(y)$, how?
• • check if $y$ is lexicographically largest or not. This means to check if the $y$ is greater than or equal to $\frac{p-1}{2}$ or not.
• • if $y$ is lexicographically largest then $sign(y) = 1$ i.e we do not alter any sign of $x$ co-ordinate
• • else if $y$ is not lexicographically largest then $sign(y) = -1$ i.e we negate the $x$ co-ordinate
• convert the $x$ co-ordinate to bytes, it should be of length $32$ bytes, in Big-Endian format
• return a bool/success_status upon successful serialization

Deserialization of the points

The deserialization is the reverse of the serialization. We need to first check if the $x$ co-ordinate is a valid point on the curve or not. If it is not a valid point on the curve then we abort. If it is a valid point on the curve then we need to check if the it is a quadratic residue or not.
If it is not a quadratic residue then we abort. If it is a quadratic residue then we need to check if the $y$ co-ordinate is lexicographically largest or not. Let’s see how should we go about it

• Receive $t=sign(y) \times x$ . This will be a bit string (32, bytes)
• Interpret the bit string $t$ as a field element $F_p$ in the interval $[0,p−1]$. The interpreted field element is now denoted $x$
• Using the curve equation, calculate $y^2 = \frac{1-ax^2}{1-dx^2}$ and load it into a point
• Check if the point is on the curve or not. (subgroup check $1-ax^2$)
• do the lexicographically largest check, and if it is not lexicographically largest then negate the $x$ co-ordinate
• finally return bool/status_code upon successfull deserialization

Next ?

Do an extensive testing with test cases and after a review from @mamy merge to the constantine