Understanding Ed25519 Key Generation, Signing, and Verification in Solana

Purpose

During Solana development the author was confused about how Ed25519 generates public keys, signatures, and verifies them, so they documented the process for future reference.

Algorithm Overview

The official flowchart shows the following components:

seed(k): a random 32‑byte value, the core of the private key (left half).

pubkey(A): the public key, which forms the right half of the private key.

msg(M): the message to be signed.

R: the left half of the signature, a random value.

S: the right half of the signature, verification data.

Step 1 – Public‑key Generation

After a 32‑byte seed is generated, it is hashed with SHA‑512 to produce a 64‑byte digest. A scalar a is derived from the hash, then multiplied by the base point B on the Edwards curve to obtain point A. The point is encoded as a 32‑byte public key, which also serves as the right half of the Solana private key.

def publickey(sk):
    """Generate the public key for a given private key."""
    h = H(sk)
    a = 2**(b-2) + sum(2**i * bit(h, i) for i in range(3, b-2))
    A = scalarmult(B, a)
    return encodepoint(A)

import os, base58
from ed255191 import publickey
seed = os.urandom(32)
pk = publickey(seed)
solana_secret_key = seed + pk
print("Public Key 32 bytes:", base58.b58encode(pk))
print("Solana Private Key 64 bytes:", base58.b58encode(solana_secret_key))

Step 2 – Message Signing

The signing function derives a random scalar r from a portion of the private‑key hash and the message, guaranteeing a unique R for each message. The challenge c is the hash of the concatenation of R, the public key, and the message. The signature consists of R and S = (r + c·a) mod l, where a is the private scalar.

def signature(m, sk, pk):
    """Generate an Ed25519 signature."""
    h = H(sk)
    a = 2**(b-2) + sum(2**i * bit(h, i) for i in range(3, b-2))
    r = Hint(h[b//8 : b//4] + m)
    R = scalarmult(B, r)
    S = (r + Hint(encodepoint(R) + pk + m) * a) % l
    return encodepoint(R) + encodeint(S)

sign = signature(b"123", seed, pk)
print("signature the 123:", base58.b58encode(sign))

Step 3 – Signature Verification

The verifier splits the 64‑byte signature into R (first 32 bytes) and S (last 32 bytes), recomputes the challenge c, and checks the equality S·B = R + c·A. If the equality holds, the signature is valid.

def checkvalid(s, m, pk) -> bool:
    """Verify a given signature."""
    if len(s) != b//4: raise Exception("Signature length is wrong")
    if len(pk) != b//8: raise Exception("Public-key length is wrong")
    R = decodepoint(s[:b//8])
    S = decodeint(s[b//8:b//4])
    A = decodepoint(pk)
    c = Hint(encodepoint(R) + pk + m)
    if scalarmult(B, S) != edwards(R, scalarmult(A, c)):
        raise Exception("Signature does not pass verification")
    return True

valid = checkvalid(sign, b"123", pk)
print("valid:", valid)

Reference Implementation

The remainder of the article provides a complete Python implementation of the Ed25519 primitives used above, including:

SHA‑512 hash function H.

Modular exponentiation expmod and modular inverse inv.

Curve constants b, q, l, and base point B.

Point recovery xrecover, point addition edwards, and scalar multiplication scalarmult.

Encoding/decoding helpers encodeint, encodepoint, decodeint, decodepoint, and bit extraction bit.

High‑level functions publickey, signature, and checkvalid.

This code can be copied and executed to experiment with Solana‑compatible keys and signatures, offering a hands‑on understanding of the Ed25519 algorithm.