After the support for the toHex() was extended for curves with equation in Twisted Edwards form, I was able to start writing the implementation. So summing up what I did this week : -

  • Completed the curve addition to curves_declaration.nim
  • Implemented the optimized equality check for the points on the Banderwagon subgroup
  • implemented the subgroup check from bandersnatch to bandwerwagon
  • implemented the map_to_field for banderwagon
  • working on the serialization and deserialization of the points on the Banderwagon

Now while working on the serialization part I realized a lot of things are missing and need to implement them as I go forward with them. The BLS12-381 encoding was implemented. But the standard there required for to send the Y-coordinate of the point on the curve. But the Banderwagon is a cofactor-4 curve and hence the Y-coordinate is not unique. So we had to figure out a way to send the Y-coordinate of the point on the curve. So the standard is to send the X-coordinate and the sign of the Y-coordinate. This is because the X-coordinate is unique and the sign of the Y-coordinate can be easily computed from the X-coordinate and the Y-coordinate.

Now this feature calculating the Y co-ordinate from the X co-ordinate is not implemented in constantine library. And this would be quite a big thing to add considering that I have to keep the constant-time-arithmetic in mind as that is one of the most important feature of the library. So I am working on this and will be raising a PR for this soon.

Now I will be explaining the things I wrote in a technical way. So if you are someone who wants to write Banderwagon you can read and do the necessary.

Equality Check for Banderwagon

The equality check for banderwagon is different from what is there in bandersnatch. For the equality check in banderwagon we first need to check if the points for which we are checking the equality are (0, 0) or not, thus for equality between points P & Q

  • if P.x & P.y both are zero, then abort or return false
  • if Q.x & Q.y both are zero, then abort or return false
  • if above both are non-zero then check for equality by the following
    • if P.x * Q.y == Q.x * P.y then return true (equality holds)
    • else return false (equality doesn’t hold)
\[\frac{x_1}{y_1} \stackrel{?}{=} \frac{x_2}{y_2}\]

Subgroup Check for Banderwagon

Checks if the point is in the quotient subgroup. The group law does not change because what we quotiented by was a subgroup. These are still points on the bandersnatch curve and form a group under point addition. This is to be used to check if the point lies in the Banderwagon while importing a point from serialized bytes.

For performing the subgroup check you need to first calculate $1-aX^2$. Once this is calculated we need to check if it is a square or not, i.e. if it is a quadratic residue in $\mathbb F_p$

Map to Field in Banderwagon

Since we are only dealing with the points $(x, y)$ & $(-x, -y)$ which are considered equal, we can create the following injective maps from the quotient group to the field $\mathbb F_p$

  • $\frac{x}{y}$
  • $x \times y$

Since $y \neq 0$, $\frac{x}{y}$ is never undefined. For banderwagon, the choice was made to use $\frac{x}{y}$, because in projective coordinates, $\frac{x}{y} = \frac{X}{Y}$, while $xy = \frac{XY}{Z^2}$

Next ??

Currently working in serialization and deserialization, would write the details of them in the next week update. This then you can track the progress here