Incorrect encoding for Twisted Edwards curve points?

[secure12]

https://datatracker.ietf.org/doc/html/rfc8032#section-3.1 says that

x is negative if the (b-1)-bit encoding of x is
lexicographically larger than the (b-1)-bit encoding of -x.

which is equivalent of saying that x is negative if x > (p - 1) / 2 (mod p).

However, the negative mask 0x80 is included when x & 1n === 1n, which seems wrong.
https://github.com/paulmillr/noble-curves/blob/main/src/abstract/edwards.ts#L398C1-L403C6

Example:
The Baby JubJub curve can be defined with twistedEdwards with these parameters:

const bjj = twistedEdwards({
  // Params: a, d
  // a: 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000
  a: 21888242871839275222246405745257275088548364400416034343698204186575808495616n,
  // d: 0x1aee90f15f2189693df072d799fd11fc039b2959ebb7c867d075ca8cf4d7eb8e
  d: 12181644023421730124874158521699555681764249180949974110617291017600649128846n,
  // Finite field 𝔽p over which we'll do calculations
  // Same value as bn254 Fr (not Fp)
  // r: 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
  Fp,
  // Subgroup order: how many points curve has
  // order: 0x60c89ce5c263405370a08b6d0302b0bab3eedb83920ee0a677297dc392126f1
  n: 2736030358979909402780800718157159386076813972158567259200215660948447373041n,
  // Cofactor
  h: 8n,
  // Base point (x, y) aka generator point
  // gx: 0x1561ff836ce19d358a4eb7a4c199e94c377c749ae6f2a277f1f9195afe553f9f
  // gy: 0x25797203f7a0b24925572e1cd16bf9edfce0051fb9e133774b3c257a872d7d8b
  Gx: 9671717474070082183213120605117400219616337014328744928644933853176787189663n,
  Gy: 16950150798460657717958625567821834550301663161624707787222815936182638968203n,
  hash: sha512,
  randomBytes,
});

The base point of Baby Jubjub is

> base = bjj.ExtendedPoint.BASE
Point {
  ex: 9671717474070082183213120605117400219616337014328744928644933853176787189663n,
  ey: 16950150798460657717958625567821834550301663161624707787222815936182638968203n,
  ez: 1n,
  et: 15014178954710068635101994852562410703552202821082335589223725347673973320715n,
  _WINDOW_SIZE: 8
}

base.ex is positive, because

> base.ex > (bjj.CURVE.Fp.ORDER - 1n) / 2n
false

So it's encoding should be 8b7d2d877a253c4b7733e1b91f05e0fcedf96bd11c2e572549b2a0f703727925 (positive x), instead of

> bjj.ExtendedPoint.BASE.toHex()
'8b7d2d877a253c4b7733e1b91f05e0fcedf96bd11c2e572549b2a0f7037279a5'

The encoding as ...7925 is consistent with other libraries (e.g. gnark-crypto)

[paulmillr]

I don't see how it's "equivalent". The spec says nothing about "bigger than half of curve order". Do you have any specifications with test vectors that validate this behavior? The goal is to conform to vectors, and we have plenty of those.

And & 1 test can be testing for half of curve order in little-endian notation.

[paulmillr]

Does it make sense to at least have an option

No. It is not a popular behavior: just a bunch of bugs in a few libraries which make it incompatible.

perhaps, open issues in those libraries instead.

[secure12]

As you said, there is no test vectors for encoding and decoding Ed25519 points, let alone other twisted Edwards curves in general. If there is no right or wrong, then "bugs" is not the right word to describe the incompability.

The encoding is from the Ed25519 paper and the Ed25519 spec. If noble curves was aimed to be extendable to (Edwards) curves that hasn't been defined in your library, it would have maximal compatibility with other popular libraries (which are not buggy). It would be a 3-line change.

My solution works for me so feel free to dismiss this thread.

[paulmillr]

Well there are test vectors for public keys, signatures, wycheproof, etc. And when I change code to

bytes[bytes.length - 1] = x > ((CURVE.Fp.ORDER - 1n) / 2n) ? 0x80 : 0;

they all fail. That means the encoding is wrong.

[secure12]

At the end of the day, it boils down to whether other twisted Edwards curves should follow to the same encoding as Ed25519. Unfortunately, any answer will be opinion-based since I haven't found any spec for other twisted Edwards curves.

[paulmillr]

Agree. Please continue with your fork for now. This will need more votes to be included.