Optimisations using the Montgomery form of the curve, reduce constraints and multiplications

[HarryR]

Because the Baby JubJub curve is a twisted Edwards curve it has an equivalent Montgomery form.

Using the Montgomery form of the curve it's possible to perform addition and doubling with roughly half the number of constraints/multiplications. This will significantly reduce the complexity of the SNARK circuit, and will give a performance boost for Solidity/EVM based algorithms.

This depends on the relationship between the X point on the Montgomery curve and the Y point on the Edwards curve, and specifically conversion in projective coordinates between the two.

However, because the prime field doesn't lend its self to efficient square roots, e.g. the usual tricks with William's or Pollard's algorithms for modulo square roots, we need to discard the X coordinate from the Edwards curve, and the Y coordinate from the Montgomery form. The Y coordinate of the Edwards form of Baby JubJub is all that's necessary to uniquely identify the point - so in lieu of recovering the X coordinate it contains everything necessary to uniquely identify a point on the curve. The Montgomery form allows addition and doubling using only the X coordinate, which can be translated into into the Y coordinate of the Edwards curve - so therefore we can perform doubling and addition while discarding 50% of the information with no loss of security.

---

In this ticket, the following requirements need to be fulfilled:

• [ ] libsnark code to convert from Edwards XY to Montgomery XZ and Edwards YZ coordinates
• [ ] libsnark addition and doubling on Montgomery XZ coordinates
• [ ] Montgomery ladder implementation
• [ ] Use Montgomery XZ coordinates for Merkle trees using Pedersen hashes.

[barryWhiteHat]

Doing additions in snark in Montgomery forum will cause some problems because it does not have a complete addition law so you will have to build an if loop which adds a bunch of constraints.

So what you will need to do is do half the computations in montgomery forum and then convert to twisted edwards. There are also some checks that zcash do after the conversion https://github.com/zcash/zcash/issues/2230#issuecomment-361063268

[HarryR]

See https://cr.yp.to/ecdh/curvezero-20060726.pdf Theorem 5.1.

So, input points need to be in Edwards X,Y form, each point is validated, and verified that it isn't infinity or one of the low-order points and the y coordinate is non-zero, then it's translated to Montgomery X,Z form.

However, in https://cr.yp.to/newelliptic/twisted-20080313.pdf Theorem 3.4 (pg 6) case 2, shows that for BabyJubJub there will be two more points of order 4 (where u=-1, and [+,-] v=sqrt(a-2)).

So, this validation doesn't need to happen for every bit of scalar multiplication, only for points going into and out of it, and in the case of a merkle tree, for points used as part of the path. The key being that you validate on the Edwards curve first (and avoid its edge cases), before using the Montgomery form of the point.

Yes, it adds a bunch of constraints, but the overhead is much smaller than doing everything in affine, projective extended twisted edwards coordinates.

No if conditions are necessary, nor ifs in loops, just constraints for validity.

[daira]

The Y coordinate of the Edwards form of Baby JubJub is all that's necessary to uniquely identify the point - so in lieu of recovering the X coordinate it contains everything necessary to uniquely identify a point on the curve.

Are you sure? Zcash uses the u-coordinate (X in your notation) as a unique representative of points in the prime subgroup. The v-coordinate (Y in your notation) is not a unique representative; in fact there will be two points P and -P with a given Y, unless X = 0. See the Zcash protocol spec Theorem 5.4.3 (which holds for any complete twisted Edwards curve).

[HarryR]

You are correct, I am wrong, the values n and ORDER-n produce the same v coordinate, where u is negated.

However, I found an oddity, there is a case where a mirror of a randomly chosen point, e.g. (-U, -V) can be turned into (U, V)

while True:
    P = Point.from_hash(urandom(10))   # from_y(...)
    B = Point.from_x(-P.x)
    Q = Point(P.x, -P.y)
    assert JUBJUB_L == JUBJUB_ORDER // JUBJUB_C  # Curve cofactor, 8
    if (-B * (JUBJUB_L-1)) == Q:
        print("A")
        break
    if (B * (JUBJUB_L-1)) == Q:
        print("B")
        break

However, this only applies where I use Point.from_hash, and not when I pick a random scalar then multiply the base point (which would defeat the point).

[HarryR]

Not implemented.