The Ed25519 curve

Scalars, points and the one operation all of Monero rests on

Why a curve

We need a "one-way function with a lock": from a secret it's easy to get something public, but not back. And we want to do arithmetic on the public things: add them and multiply them by numbers. An elliptic curve gives exactly that.

Monero uses the same curve as Ed25519 signatures (Daniel J. Bernstein et al.): a twisted Edwards curve

A point is a pair of numbers (x, y) that satisfies the equation. All computation is modulo the prime p, so the "curve" is really a cloud of about 2²⁵⁵ discrete points.

Adding points

Points can be added: P + Q = R, where R is also on the curve. On Edwards curves one formula covers all cases (convenient and safe):

This addition behaves like the ordinary one: it is commutative and associative, there is a "zero" — the point (0, 1) — and every point has an opposite (−x, y).

Multiplying by a number

Multiplying a point by x means adding it to itself x times. Of course nobody adds 2²⁵² times: the "double-and-add" method needs only ~256 doublings and ~128 additions.

The base point G and the order l

Everyone uses the same pre-agreed base point G. Multiply G by 1, 2, 3, … and after l steps you're back at zero:

l is the order of the subgroup generated by G. The curve has 8 times as many points in total (8·l); 8 is called the cofactor. This cofactor is the source of several subtle points in Monero: you'll see a factor of 8 in the one-time address formulas, and in 2017 "small-order points" could have produced several key images for one output (fixed by checking l·I = 0).

Why this works for keys

Take a random x — that's a private key. Compute P = x·G — that's a public key. Publishing P is safe. Crucially, points support algebra:

The second identity is the basis of Diffie–Hellman key exchange: Alice knows a and sees B = b·G; Bob knows b and sees A = a·G. Both can compute the same point a·B = b·A = ab·G, but an outsider can't. One-time addresses are built on this.

The first identity is the basis of Pedersen commitments: amounts hidden in points can be added.

Encoding a point in 32 bytes

A point is stored compactly: write the y coordinate (255 bits, little-endian) and put the parity of x in the top bit of the last byte. x is recovered from y via the curve equation (up to sign — which the bit gives). These are the 32 bytes you see in hex when you look at a Monero public key.

For example, the base point G is written as:

5866666666666666666666666666666666666666666666666666666666666666

(its y = 4/5 mod p, and x is even).

Code

A minimal JavaScript implementation with BigInt — from xmrcrypto.js, used by every tool on this site:

const P = (1n << 255n) - 19n;
const L = (1n << 252n) + 27742317777372353535851937790883648493n;
const D = mod(-121665n * inv(121666n));

// points in extended coordinates (X:Y:Z:T), x = X/Z, y = Y/Z
function add(p, q) {
  const A = mod((p.Y - p.X) * (q.Y - q.X));
  const B = mod((p.Y + p.X) * (q.Y + q.X));
  const C = mod(2n * D * p.T * q.T);
  const Dd = mod(2n * p.Z * q.Z);
  const E = B - A, F = Dd - C, G = Dd + C, H = B + A;
  return { X: mod(E * F), Y: mod(G * H), Z: mod(F * G), T: mod(E * H) };
}

// scalar multiplication: double-and-add
function mul(k, p) {
  let r = ZERO, q = p;
  while (k > 0n) { if (k & 1n) r = add(r, q); q = add(q, q); k >>= 1n; }
  return r;
}