This week was mostly diving into code & different implementation point of view. Reading notes by different people, which they kept while implementing Banderwagon from Bandersnatch. So not much of the theory, but more of reading code and testing out different libraries. So if I try to sum up this week : -

  • Start of the week worked mostly on preparing the slides and the project presentation. You can find the slide here, and the recording here.
  • Going through the Bandersnatch implementation notes
  • Understanding the current implementation of Bandersnatch in Constantine library.
  • Figuring out what else to be needed to done to build Banderwagon over the existing Bandersnatch curve in Constantine Library.
  • Solving the compilation issues of Constantine library, in Apple Silicon M1 chip. ( Since I use this as my main workstation, kinda had to solve this. Not yet a proper fix, but a way around )

Learnings

For Bandersnatch, we use the twisted Edwards curve representation, which is given by the following equation : -

\[E_{E_{a,d}}: ax^2 + y^2 = 1 + dx^2y^2\]

For the bandersnatch curve, the parameters are given by NIST : -

\[a=-5 \\ d = \frac{138827208126141220649022263972958607803}{171449701953573178309673572579671231137}\]

Now generally representing points on the curve is done by the affine coordinates, which is relatively simple and represented as $(x, y)$. But for twisted Edwards curve, we use the projective coordinates, which is represented as $(X, Y, Z)$, where $X = xZ$ and $Y = yZ$.

Currently Bandersnatch is implemented in constantine library. Now Banderwagon would be like a scheme built on top of Bandersnatch to solve the cofactor issue of Twisted Edward curves. This cofactor issue is explained in:

https://loup-vaillant.fr/tutorials/cofactor

Basically secret keys should be modulo a big prime r, but the number of points on a Twisted Edwards curve is either 4r or 8r. And if you choose the wrong point, you land on a subgroup of order 4 or 8 (i.e. only 4 or 8 curve points instead of r)

This lead to a huge double spend vulnerability in Monero in 2017: https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html

A curve with a cofactor of 1, like secp256k1 or BN254 is called a prime order curve and avoids this altogether (but sometimes we don’t have a choice)

There are many zk schemes (like Bulletproofs) that require a prime order curve.

There is a technique called Decaf for cofactor 4 curves to project the computation on a prime order isogenous curve (i.e. a curve with the same order/number of points as the original) and then back.

As I was going through a few implementation notes, I found that the Decaf technique assumes that the Twisted Edwards Curve is complete, for our case as far as I know bandersnatch is not. Later having a chat with @mratsim, I realised what was suggested was a Decaf Style implementation and not the exact Decaf Implementation. So for next week I will be diving into this