Ed25519

Ed25519 is the signature scheme being used in Cardano, and supported in Plutus. Ed25519 is an instantiation of the EdDSA over the Edwards25519 elliptic curve.

Generalised specification

This section presents the generalized signature system EdDSA, and in the parameter section, we present the specific parameters used in Cardano. EdDSA is parametrized with the following parameters. An integer $b\ge 10$, a cryptographic hash function $\text{H}$ producing a $2b$-bit output, and a finite abelian group based on an elliptic curve. An EdDSA, signature consists of the following three algorithms:

• $\text{KeyGen}(1^{\lambda })$ takes as input the security parameter $\lambda$ and returns a key-pair $(x,vk)$. First, it chooses $x\leftarrow \{0,1{\}}^b$. Next, let $(h_0,h_1,\dots ,h_{2b-1})\leftarrow \text{H}(x)$, and compute the signing key, $sk\leftarrow 2^{b-2}+{\sum }_{3\le i\le b-3}{2}^i{h}_i$ . Finally, compute $vk\leftarrow sk\cdot G$, and return $(x,vk)$.
• $\text{Sign}(x,vk,m)$ takes as input a keypair $(x,vk)$ and a message $m$, and returns a signature $\sigma$. Let $r\leftarrow H(h_b,\dots ,h_{2b-1},m)$, and interpret the result as a little-endian integer in $\{0,1,\dots ,2^{2b}-1\}$. Let $R\leftarrow r\cdot G$, and $S\leftarrow (r+H(R,A,M)\cdot sk)\mathrm{mod}q$. Return $\sigma \leftarrow (R,S)$.
• $\text{Verify}(m,vk,\sigma )$ takes as input a message $m$, a verification key $vk$ and a signature $\sigma$, and returns $r\in \{\text{true},\text{false}\}$ depending on whether the signature is valid or not. The algorithm returns $\text{true}$ if the following equation holds and $\text{false}$ otherwise: $$S\cdot G=R+H(R,vk,m)\cdot vk.$$

Parameters of instantiation

In this section we set to describe the concrete instantiation of the algorithm presented above. Not only we describe the Curves and Hash functions used, but we also specify how deserialization happens, as this results in important differences of the acceptance criteria of valid signatures. The algorithm we use is Ed25519¹. However, our implementation slightly differs in the deserialization criteria. The details are as follows:

• Parameter $b$: We set $b=256$
• Curve: We define the curve, and by consequence the finite prime order field, security parameter, cofactor, prime order subgroup and generator. In particular, we use Edwards25519 which is birationally equivalent to Curve25519².
• Hash: As a hashing algorithm we use SHA512.
• Deserialization: A signature is represented by 64 bytes: the first 32 bytes, $b_{[..32]}$, represent the point $R$, and the final 32 bytes, $b_{[\mathrm{32..}]}$, represent the scalar $S$. A public key is also represented as 32 bytes, $b_{pk}$. Deserialization is valid only if:
  • $b_{[\mathrm{32..}]}$, read as a little-endian integer, is smaller than $q$.
  • $b_{[..32]}$ does not represent a low order point (by checking against a precomputed blacklist of size $\text{cofvar}$).
  • $b_{pk}$ does not represent a low order point (by checking against a precomputed blacklist of size $\text{cofvar}$), and when read as a little-endian integer, it is smaller than $p$.