Introduction

This document is WORK IN PROGRESS. While the document
has this warning, check with your local cryptographer
whether the final solution is correct for your 
particular use case.

This document forms the IOG Cryptography Handbook, which aims to provide a go-to for engineers having to make a choice on which implementations to use for given cryptographic primitives. This document contains a specification of all the cryptographic primitives being used in production, or in testing phase, and at least a reference to the ongoing efforts of other cryptographic primitives.

The target audience for the Handbook is everyone working on a project associated with an IOG product, or within the Cardano ecosystem. This is also the set of target contributors for the Handbook! Anyone can submit a change proposal as a PR (see 'Contributing').

Purpose

The purpose of this handbook is both descriptive and to list existing implementations:

• Firstly, it lists particular implementations for given cryptographic primitives that are being used, or have been reviewed, by IOG matter experts.
• Secondly, it describes the cryptographic primitives in detail (or points interested reader to further material), to allow engineers to choose alternative implementation which are compatible with the primitives used by IOG.

Goals

The goals of the Handbook are to:

• Provide a place to record all cryptographic libraries being used in IOG projects.
• Present a sufficient level of detail of the cryptographic primitives to allow engineers to make independent decisions without having to contact matter experts or look into the source code.
• Encourage consistency across the organization in order to minimize cognitive overheads from unnecessary differences.
• Avoid implementing of primitives that already exist and/or are being used in IOG.
• List common mistakes when handling with these type of libraries.

Non-goals

The following are explicitly not goals of the Handbook:

• The recommended libraries are by no means flawless. As in any piece of software, the libraries hereby listed can have bugs.
• Provide an exhaustive list of all available implementations in all languages. We only have a limited number of cryptographers, and this list will grow as we look into existing implementation of used primitives.

The Handbook is very new and will gradually acquire more content over time. We hope to improve all of this over time!

Contributing

If a project needs a particular primitive, which is not present in this document, the mechanism to include is simple. Add an issue to the repo, specifying why such a primitive is of interest, and how it would be used. To make the discussion more effective, it is also of interest to link references to the specification, or available implementations.

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.

Implementation and bindings

We currently relly in the implementation available in version 1.0.18 of libsodium. We have analysed, and recommend, bindings in the following languages:

• Haskell: Available in cardano-base
• Rust: Made available by the original author of libsodium
• Javascript: Made available by the original author of libsodium (among others)

There also exist other implementations that offer a compatible signing algorithm which do not require the full usage of libsodium. The list we have analaysed and recommend is the following:

• Rust: ed25519-dalek, using the verify_strict() function.
• Javascript: tweetnacl-js, though the verification criteria of this library is more permissive, meaning that a valid signature for tweetnacl-js might not be valid for Cardano.

Common mistakes

An ed25519 signature consists of two values $(R,s)$, where $R$ is an elliptic curve point and $s\in {\mathbb{Z}}_q$ is a scalar. A common mistake when deserialising the scalar $s$ is to compute it modulo $q$ in case that $s$ is larger than $q$. This must be avoided, specifically in consensus critical scenarios.

Another common mistake is what criteria to use when deserialising an elliptic curve point. If none of the libraries listed above are used, the engineer should carefully read the sections below to understand the details, and the verification criteria used in Cardano.

KES

In Cardano, nodes use Key Evolving Signatures (KES). This is another asymmetric key cryptographic scheme, also relying on the use of public and private key pairs. These signature schemes provide forward cryptographic security, meaning that a compromised key does not make it easier for an adversary to forge a signature that allegedly had been signed in the past.

In KES, the public verification key stays constant, but the corresponding private key evolves incrementally. For this reason, KES signing keys are indexed by integers representing the step in the key's evolution. Since the private key evolves incrementally in a KES scheme, the ledger rules require the pool operators to evolve their keys every time a certain number of slots have passed. The details of when these keys are evolved are out of the scope of this document, and the reader is directed to the ledger spec.

Implementation and bindings

The Cardano compatible KES implementations are

• Haskell: Available in cardano-base
• Rust: Available in crates.io

The particular instantiation used in Cardano is of depth 6. An improvement on the representation of signatures is being worked on, and planned to be included in the next HF. This compact representation is available in both the Haskell library and the rust counterpart.

Note: The secret key representations of both libraries are not compatible. A padding strategy can be made to use Haskell generated data in Rust, but not vice-versa. To see this padding trick, you can look in the interoperability tests of the rust library.

Common mistakes

The main building block of KES is its underlying signature scheme, Ed25519. We refer the reader to the common mistakes section of Ed25519.

BIP32-ed25519

BIP32-ed25519 is an adaptation of the BIP32 proposal for deterministic key generation for the Ed25519 curve which has non-linear key space.

Implementation and bindings

We currently have two implementations of BIP32:

• C: Available in cardano-crypto
• Rust: Implemented by Vincent Hanquez, here.

The preferred implementation is that of Rust, but both are safe to use.

For the C implementation, we have bindings in the following languages:

• Haskell: Available in cardano-crypto

Common mistakes

As the underlying signature algorithm is ed25519, we refer the reader to common mistakes of that section.

ECDSA

ECDSA is one of signature schemes supported natively in Plutus, together with ed25519 and Schnorr. In particular, the natively supported ECDSA algorithm works over curve SECP256k1, enabling support for Bitcoin's and Ethereum's native signatures.

Implementation and bindings

We currently relly in Bitcoin's implementation available in secp256k1. We have analysed, and recommend, bindings in the following languages:

• Haskell: Available in cardano-base

Common mistakes

An ECDSA signature consists of two values $(r,s)$, where are scalars. A problem of using ECDSA in consensus critical contexts, is that the signature algorithm (as defined in the standard) is malleable. Specifically, given a valid signature $(r,s)$, the tuple $(r,-s)$ is also a valid signature. To avoid problems resulting from this malleability, the implementation we use checks that the $$s<p/2$$, where $p$ is the order of the prime order group. More details of such a check in the spec section.

Another common problem of verifying ECDSA signatures is that the hashing of the message must be performed by the verifier itself, rather than accepting a hashed message. This can be dangerous. Therefore, the verifier, before proceeding with verification, hashes the message.

Schnorr

Schnorr is one of signature schemes supported natively in Plutus, together with ed25519 and ECDSA. In particular, the natively supported ECDSA algorithm works over curve SECP256k1, enabling support for Bitcoin's and Ethereum's native signatures. Schnorr signature scheme is also adopted by MuSig2 (Simple Two-Round Schnorr Multisignatures) which will be integrated to Hydra.

Implementation and binding

We currently relly in Bitcoin's implementation available in secp256k1. We have analysed, and recommend, bindings in the following languages:

• Haskell: Available in cardano-base

MuSig2

This API also relies on secp256k1 that is compatible with BIP-340 producing 64-byte Schnorr signatures.

• C: Available in musig2. Note that this API is still in progress.

VRF-ed25519

Verifiable Random Functions ($\text{VRF}$) allow key-pair owners, $({sk}_{\text{VRF}},{vk}_{\text{VRF}})$, to evaluate a pseudorandom function in a provable way given a randomness seed. Any party with access to the verification key, ${vk}_{\text{VRF}}$, the randomness seed, the proof and the generated randomness can indeed verify that the value is computed as expected. The VRF specification has changed overtime in Cardano, and the nodes use a different algorith, pre-Babbage and post-Babbage (if there exists a reference to the HF, we should point it out). We expose both specifications, and the motivations for such a change.

Implementation and bindings

We currently rely in the implementation available in the fork of libsodium. We have analysed, and recommend, bindings in the following languages:

• Haskell: Available in cardano-base

Notation

In this section we introduce some generic notation used throughout the spec. The primitive-specific notation is introduced in the respective sections.

We denote by $E(F_p)$ the finite abelian group based on an elliptic curve over a finite prime-order field $F_p$ (note that we simplify the notation and drop the explicit dependency on $F_p$ and security parameter $\kappa$). Most importantly, we assume the order of the group $E$ to be of the form $\text{cofvar}\cdot q$ for some small cofactor $\text{cofvar}$ (sometimes equal to 1) and large prime number $q$, and that the (hence) unique (sub)group $\mathbf{G}$ of order $q$ is generated by a known base point $G$, i.e., $\mathbf{G}=⟨G⟩$, in which the computational Diffie-Hellman (CDH) problem is believed to be hard. We use $\text{H}$ to denote a cryptographically safe hash function, modeled as a random oracle, $$\text{H}:\{0,1{\}}^{\text{a}}\to \{0,1{\}}^{\ell (\kappa )}.$$ for any value of $a$ (we tried using $\ast$ but the katex compiler was not happy with it).

An elliptic curve point can be determined using the y-coordinate and the sign of the $x$-coordinate, meaning that an elliptic curve point can be represented using $s=\lceil {\log }_2(p)\rceil +1$ bits. All elements in $F_p$ or $F_q$ are serialised in little-endian form. Elliptic curve points are encoded using their $y$-coordinate followed by the sign bit of the $x$ coordinate. An element $x$ in $F_p$ is negative if the enconding of $x$ is lexicographically larger than the encoding of $-x$

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$.

KES

In Cardano, nodes use Key Evolving Signatures (KES). This is another asymmetric key cryptographic scheme, also relying on the use of public and private key pairs. These signature schemes provide forward cryptographic security, meaning that a compromised key does not make it easier for an adversary to forge a signature that allegedly had been signed in the past.

In KES, the public verification key stays constant, but the corresponding private key evolves incrementally. For this reason, KES signing keys are indexed by integers representing the step in the key's evolution. Since the private key evolves incrementally in a KES scheme, the ledger rules require the pool operators to evolve their keys every time a certain number of slots have passed. The details of when these keys are evolved are out of the scope of this document, and the reader is directed to the ledger spec.

Generalised specification

We use the iterated sum construction from Section 4.3 of MMM¹. A KES signature algorithm is parametrized by four algorithms, $\text{KeyGen},\text{Sign},\text{Update}$ and $\text{Verify}$. The sum construction depends on two signing algorithms, ${\Sigma }_0=({\text{KeyGen}}_0,{\text{Sign}}_0,{\text{Update}}_0,{\text{Verify}}_0)$ and ${\Sigma }_1=({\text{KeyGen}}_1,{\text{Sign}}_1,{\text{Update}}_1,{\text{Verify}}_1)$, which are forward-secure with $T_0$ and $T_1$ time periods respectively. As specified in the paper, any digital signature algorithm can be considered as a forward-secure signature algorithm with 1 time period. We use two specialized versions of the key generation, one to generate the public part, and another to generate the secret part, $P\text{KeyGen},S\text{KeyGen}$ respectively. The KES algorithm uses a length doubling pseudorandom generator, $F:\{0,1{\}}^{\lambda }\to \{0,1{\}}^{\lambda }\times \{0,1{\}}^{\lambda }$, where given a random seed, $s$, returns two random seeds of the same size $s_1,s_2$. The sum construction begins by generating a signing algorithm with two periods by merging two instances of the base signature, and proceeds recursively until the desired level of periods is reached.

The Chang hard fork will bring optimizations to the KES signature size, and we therefore have different verification criteria pre and post-Chang. Both instances use a tree of depth 6. For ease of exposure, we compare both constructions using a simple binary tree of depth 3 (see figure below). Consider each node as a KES instance with $2^n$ periods, where $n$ is the height of the node with respect to the leafs. For instance, A is a KES instance with $8$ periods, while node D is a KES instance with $2$ periods. Note that each KES instance is created by two child instances with half the periods. The only relevant details for compatibility on how KES algorithm works is signature generation and signature verification, however we provide a description of the other functions. The details on how the keys are managed are details of implementation which will not be covered here.

digraph keys {
  { 
     A, F, G, J, K, L, M, N, O, t [ shape = box, color = "black" ];
     B, D [ shape = box, color = "black", style = "filled", fillcolor = "green" ];
     C, E, H, I [ shape = box, color = "red", style = "filled", fillcolor = "green" ];
   };
   
   A -> B;
   A -> C;
   B -> D;
   B -> E;
   C -> F;
   C -> G;
   D -> H;
   D -> I;
   E -> J;
   E -> K;
   F -> L;
   F -> M;
   G -> N;
   G -> O;
   H -> t
}

In green, we have the nodes for which we need to store the public key in a signature during pre-babbage eras. With red borders we have the nodes for which we need to store the public keys in post-babbage eras.

Pre-Chang

The signing instances of nodes H-O are single period KES instances, and nodes A-G are defined by recursively calling on the algorithms presented above. In pre-Chang eras the signatures are computed in a naive manner, meaning that a signature is represented (recursively) as the underlying signature and the two public keys, $\sigma =({\sigma }^{\prime },{vk}_0,{vk}_1)$. So for instance, the signature in node A of period 0 contains the signature of node B, ${\sigma }_b$, the public key of node B ${vk}_b$ (which is a hash of ${vk}_d$ and ${vk}_e$) and the public key of node C ${vk}_c$ (which is a hash of ${vk}_f$ and ${vk}_g$). Signature ${\sigma }_b$ in turn contains signature of node D ${\sigma }_d$, the public key of node D ${vk}_d$ (which is a hash of ${vk}_h$ and ${vk}_i$) and public key of node E ${vk}_e$ (which is a hash of ${vk}_j$ and ${vk}_k$). The signature of node D, ${\sigma }_d$ contains in turn the signature of node H, ${\sigma }_h$, the public key of node H, ${vk}_h$ and the public key of node I ${vk}_i$. Verification of the signature works in the naive recursive manner. We check that $\text{H}({vk}_b,{vk}_c)={vk}_a$, and $\text{H}({vk}_d,{vk}_e)={vk}_b$, and $\text{H}({vk}_h,{vk}_i)={vk}_d$, and finally that $\text{Verify}(m,{vk}_h,{\sigma }_h)=\text{true}$. More specifically:

• $\text{KeyGen}(r)$ takes as input a random seed. It then extends the seed into two parts, $(r_0,r_1)\leftarrow F(r)$, and uses each seed to generate the key material of the next layer. In particular $({sk}_0,{vk}_0)\leftarrow \text{KeyGen}(r_0)$ and ${vk}_1\leftarrow P\text{KeyGen}(r_1)$. Finally, it computes the pair's public key $vk\leftarrow \text{H}({vk}_0,{vk}_1)$ and returns $(⟨{sk}_0,r_1,{vk}_0,{vk}_1⟩,vk)$. \item $\text{Sign}(t,\stackrel{sk}{\overbrace{⟨{sk}^{\prime },r_1,{vk}_0,{vk}_1}}⟩,m)$ takes as input a time period $t$, a signing key $sk$ and a message. If $t<T_0$, then it computes the signature using the first signature algorithm, ${\sigma }^{\prime }\leftarrow {\text{Sign}}_0(t,{sk}^{\prime },m)$, otherwise it uses the other ${\sigma }^{\prime }\leftarrow {\text{Sign}}_1(t-T_0,{sk}^{\prime },m)$. Finally, returns $(⟨{\sigma }^{\prime },{vk}_0,{vk}_1⟩,t)$.
• $\text{Update}(t,\stackrel{sk}{\overbrace{⟨,{sk}^{\prime },r_1,{vk}_0,{vk}_1⟩}})$ takes as input a time period $t$, and a signing key $sk$. If $t+1<T_0$, then ${sk}^{\prime }\leftarrow {\text{Update}}_0(t,{sk}^{\prime })$. Otherwise, it checks if its changing the key generation algorithm. Specifically, if $t+1=T_0$, then ${sk}^{\prime }\leftarrow {S\text{KeyGen}}_1(r_1)$ and sets the seed to zero $r_1\leftarrow 0$. Otherwise, ${sk}^{\prime }\leftarrow {\text{Update}}_1(t-T_0,{sk}^{\prime })$.
• $\text{Verify}(vk,m,\stackrel{\sigma }{\overbrace{⟨{\sigma }^{\prime },{vk}_0,{vk}_1⟩}},t)$ takes as input a verification key, $vk$, a message, $m$, a signature, $\sigma$, and a time period, $t$. First, it checks that $\text{H}({vk}_0,{vk}_1)=vk$. If that is not the case, it returns $\text{false}$. Otherwise, if $t<T_0$ then ${\text{Verify}}_0({vk}_0,m,\sigma ,t)$, else ${\text{Verify}}_1({vk}_1,m,\sigma ,t-T_0)$. If verification fails, it returns $\text{false}$, otherwise it returns $\text{true}$.

Post-Chang

The naive definition of the signature used in Pre-Chang results in poor performance with respect to the signature size. We don't need to verify the hash equality at each level, and we simply need to do so at the root. In the Chang hardfork we introduced such an optimization. In particular, instead of storing both public keys in each signature, we only store the one of the branch that we are not in. For the case of the KES instances with 1 period, the KES signature contains not only the underlying signature, but also the public key, which allows us to re-walk the merkle path. Again, assume we are in period 0. Then, the signature in node A of period 0 contains the signature of node B, ${\sigma }_b$, and the public key of node C ${vk}_c$ (which is a hash of ${vk}_f$ and ${vk}_g$). Signature ${\sigma }_b$ in turn contains signature of node D ${\sigma }_d$ and public key of node E ${vk}_e$ (which is a hash of ${vk}_j$ and ${vk}_k$). The signature of node D, ${\sigma }_d$ contains in turn the signature of node H, ${\sigma }_h$, and the public key of node I ${vk}_i$. In this case, ${\sigma }_h=({\sigma }_{0,h},{vk}_h)$, where ${\sigma }_{0,h}$ is the underlying signature. Verification of the signature works going up the tree, rather than down. We check $\text{Verify}(m,{vk}_h,{\sigma }_{0,h})=\text{true}$. Then we compute the expected key of node D, ${vk}_d^{\prime }\leftarrow \text{H}({vk}_h,{vk}_i)$. Then we use that to compute the expected key of node B, ${vk}_b^{\prime }\leftarrow \text{H}({vk}_d^{\prime },v{k}_e)$. Finally, we check that the leaf indeed is part of the merkle tree by checking that $\text{H}({vk}_b^{\prime },{vk}_c)={vk}_a$. To derive the missing public key, we introduce a new function, $\text{DeriveVerKey}$.

Specifically, post-Chang KES signature algorithm modifies the $\text{Sign}$ and $\text{Verify}$ algorithms, and introduces $\text{DeriveVerKey}$ as follows:

• $\text{KeyGen}(r)$ takes as input a random seed. It then extends the seed into two parts, $(r_0,r_1)\leftarrow F(r)$, and uses each seed to generate the key material of the next layer. In particular $({sk}_0,{vk}_0)\leftarrow \text{KeyGen}(r_0)$ and ${vk}_1\leftarrow P\text{KeyGen}(r_1)$. Finally, it computes the pair's public key $vk\leftarrow \text{H}({vk}_0,{vk}_1)$ and returns $(⟨{sk}_0,r_1,{vk}_0,{vk}_1⟩,vk)$.
• $\text{Sign}(t,\stackrel{sk}{\overbrace{⟨{sk}^{\prime },r_1,{vk}_0,{vk}_1}}⟩,m)$ takes as input a time period $t$, a signing key $sk$ and a message. If $t<T_0$, then it computes the signature using the first signature algorithm, ${\sigma }^{\prime }\leftarrow {\text{Sign}}_0(t,{sk}^{\prime },m)$ and lets ${vk}_c={vk}_1$, otherwise it uses the other ${\sigma }^{\prime }\leftarrow {\text{Sign}}_1(t-T_0,{sk}^{\prime },m)$, and lets ${vk}_c={vk}_0$. Finally, returns $(⟨{\sigma }^{\prime },vk⟩,t)$.
• $\text{Update}(t,\stackrel{sk}{\overbrace{⟨,{sk}^{\prime },r_1,{vk}_0,{vk}_1⟩}})$ takes as input a time period $t$, and a signing key $sk$. If $t+1<T_0$, then ${sk}^{\prime }\leftarrow {\text{Update}}_0(t,{sk}^{\prime })$. Otherwise, it checks if its changing the key generation algorithm. Specifically, if $t+1=T_0$, then ${sk}^{\prime }\leftarrow {S\text{KeyGen}}_1(r_1)$ and sets the seed to zero $r_1\leftarrow 0$. Otherwise, ${sk}^{\prime }\leftarrow {\text{Update}}_1(t-T_0,{sk}^{\prime })$.
• $\text{DeriveVerKey}(\stackrel{\sigma }{\overbrace{⟨{\sigma }^{\prime },{vk}_c⟩}},m,t)$ takes as input a signature $\sigma$ and a period $t$. If $t<T_0$, then $({vk}_n,res)=\text{DeriveVerKey}({\sigma }^{\prime },m,t)$ and return $(\text{H}({vk}_n,{vk}_c),res)$, otherwise ${vk}_n=\text{DeriveVerKey}({\sigma }^{\prime },m,t-T_0)$ and return $(\text{H}({vk}_c,{vk}_n),res)$.
• $\text{Verify}(vk,m,\stackrel{\sigma }{\overbrace{⟨{\sigma }^{\prime },{vk}_c⟩}},t)$ takes as input a verification key, $vk$, a message, $m$, a signature, $\sigma$, and a time period, $t$. First, it computes ${vk}_n\leftarrow \text{DeriveVerKey}(\stackrel{\sigma }{\overbrace{⟨{\sigma }^{\prime },{vk}_c⟩}},m,t)$, and then, if $t<T_0$, check that $\text{H}({vk}_n,{vk}_c)=vk$, otherwise, check that $\text{H}({vk}_c,{vk}_n)=vk$. If verification fails, it returns $\text{false}$, otherwise it returns $\text{true}$.

For this recursive explanation to be complete, we need to define what happens when we call $\text{DeriveVerKey}$ on a leaf signature. Recall that the signature of a leaf contains not only the underlying signature, but also the public key with which it is signed. The derive function at the leaf takes as input $(\stackrel{\sigma }{\overbrace{⟨{\sigma }^{\prime },{vk}_c⟩}},m,t)$. It proceeds by verifying the leaf signature. Parse ${\sigma }^{\prime }=({\sigma }_0,vk)$, and compute the result $res\leftarrow \text{Verify}(m,vk,{\sigma }_0)$. If $t=0$, then return $(\text{H}(vk,{vk}_c),res)$, else return $(\text{H}({vk}_c,vk),res)$.

Parameters of instantiation

The instantiation of both eras is the same. The underlying signature scheme is Ed25519. Regarding $P\text{KeyGen}$ and $S\text{KeyGen}$, in Cardano, these functions simply call a seeded version of Ed25519's $\text{KeyGen}$ and extract the public or private part. As a hashing function we use Blake2b². Defining the pseudo random function $F$ is not required for compatibility purposes, as it is only used for private key material. However, for sake of completeness, we specify that the cardano node uses Blake2b as a length doubling pseudorandom generator.

ECDSA

ECDSA, together with Schnorr, were two new signature algorithms introduced in Plutus during Cardano's Valentine upgrade.

Generalised specification

This section presents the generalized signature system ECDSA, and in the parameter section, we present the specific parameters used in Cardano. ECDSA is parametrized with the following parameters. An ECDSA 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 Z_q$. Finally, compute $vk\leftarrow x\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 $k\leftarrow Z_q$. Compute $K=k\cdot \ast generator$ and interpret the result as its two individual coordinates $(K_x,K_y)$. Next, compute $r\leftarrow K_x\mathrm{mod}q$. If $r=0$, generate a new $k$ and start over. Finally compute $s=k^{-1}(z+r\ast x)\mathrm{mod}q$. If $s=0$, generate a new $k$ and start over. Otherwise, return $\sigma =(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 conditions hold and $\text{false}$ otherwise:
  • $r$ and $s$ are between $1$ and $q-1$.
  • Compute $u_1=z\cdot s^{-1}\mathrm{mod}q$ and $u_2=r\cdot s^{-1}\mathrm{mod}q$. Compute $(x,y)=u_1\cdot G+u_2\cdot G$, and ensure it is not equal to the point at infinity. Checks that $r=x\mathrm{mod}q$.

Parameters of instantiation

The above is the standard definition, and in cardano we instantiate it over curve SECP256k1. However, such a signature algorithm enables malleability. Given a valid signature $(r,s)$, if one sets $s^{\prime }=q-s$, then the pair $(r,s^{\prime })$ is also a valid signature, as a point $P$ and its negative $P^{\prime }$ share the same x-coordinate. This can be problematic in consensus critical contexts. To that end, we follow Bitcoin's modification of only accepting signatures with small values of $s$, i.e. with $s<p/2$.

The signatures generated using Haskell's bindings (see here) use hash function SHA256. However, Plutus built-in function takes as input the hashed message, meaning that the signer and verifier can agree which hash function to use in their protocol.

While we follow the verification criteria used in Bitcoin, we do not follow their serialisation convention, DER-encoding, which results in variable sized signatures up to 72 bytes (instead of the 64 byte encoding we describe in this document).

More precisely, the following is what is the specification used in the plutus built-in functions:

• The verification key must correspond to the (x, y) coordinates of a point on the SECP256k1 curve, where x, y are unsigned integers in big-endian form.
• The verification key must correspond to a result produced by secp256k1_ec_pubkey_serialize, when given a length argument of 33, and the SECP256K1_EC_COMPRESSED flag. This implies all of the following:
  • The verification key is 33 bytes long.
  • The first byte corresponds to the parity of the y coordinate; this is 0x02 if y is even, and 0x03 otherwise.
  • The remaining 32 bytes are the bytes of the x coordinate.
• The input to verify must be a 32-byte hash of the message to be checked. We assume that the caller of verifyEcdsaSecp256k1Signature receives the message and hashes it, rather than accepting a hash directly: doing so can be dangerous. Typically, the hashing function used would be SHA256; however, this is not required, as only the length is checked.
• The signature must correspond to two unsigned integers in big-endian form; henceforth r and s.
• The signature must correspond to a result produced by secp256k1_ecdsa_serialize_compact. This implies all of the following:
  • The signature is 64 bytes long.
  • The first 32 bytes are the bytes of r.
  • The last 32 bytes are the bytes of s.

      ┏━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━┓
      ┃ r <32 bytes> │ s <32 bytes>  ┃
      ┗━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━┛
      <--------- signature ---------->
  

Schnorr

Schnorr, together with ECDSA, were two new signature algorithms introduced in Plutus during Cardano's Valentine upgrade. MuSig2 is a two-round multi-signature scheme will be integrated to Hydra.

Generalised specification

This section presents the generalized signature system ECDSA and MuSig2. In the [parameter] (#parameters-of-instantiation) section, we present the specific parameters used in Cardano and MuSig2 C implementation.

A Schnorr 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 Z_q$. Finally, compute $vk\leftarrow x\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 Z_q$. Compute $R=r\cdot G$, then compute $c\leftarrow \text{H}(R,vk,m)$, and finally compute $s=r+c\cdot x$. The signature is $\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 $\text{result}\in \{\text{true},\text{false}\}$ depending on whether the signature is valid or not. The algorithm returns $\text{true}$ if $s\cdot G=R+c\cdot vk$

Let $N$ be the number of signers and $V$ be the number of nonces. A two-round multi-signature scheme MuSig2 that outputs an ordinary Schnorr signature includes the following steps:

• $\text{KeyGen}(1^{\lambda })$ takes as input the security parameter $\lambda$ and returns a key-pair $(x,vk)$. First, it chooses $x\leftarrow Z_q$. Finally, compute $vk\leftarrow x\cdot G$, and return $(x,vk)$.

• $\text{BatchComm}(1^{\lambda })$ takes as input the security parameter $\lambda$ and returns $V$ key-pairs $\{(r_1,R_1),\dots ,(r_V,R_V)\}$. First, it chooses the nonces $r_j\leftarrow Z_q$. Finally, computes the commitments $R_j\leftarrow r_j\cdot G$, and returns the list including $V$ tuples of nonces and commitments.

• $\text{AggrPubKey}(\{v{k}_1,\dots ,v{k}_N\},{vk}_s)$ takes the list of public keys and the signer's public key, returns the aggregate public key $X$ and $a_s$. First creates $L=({vk}_1||{vk}_2||\dots ||{vk}_N)$. Computes $a_i=H_{agg}(L||{vk}_i)$ for $i=1\dots N$. Finally, generates the aggregate public key by $X={\Sigma }_{i=1}^N(a_i\cdot {vk}_i)$ and the signer keeps her own $a_s$.

• $\text{AggrComm}(\{R_{11},R_{12},\dots ,R_{1V},\dots ,R_{N1},\dots ,R_{NV}\})$ takes the list of all signers' commitment lists, returns the list of aggregate commitments. $\{R_j={\Sigma }_{i=1}^N(R_{ij}){\}}_{j=\mathrm{1..}V}$.

• $\text{Sign}(x_s,{vk}_s,m,X,(R_1,\dots ,R_V),(r_{s1},\dots ,r_{sV}))$ takes as input the keypair of the signer, a message $m$, aggregate public key, the list of commitments and the list of nonces of the signer. Returns a signature $\sigma$. First, creates $b=H_{non}(X||(R_1,\dots ,R_V)||m)\in Z_q$. Computes $R={\Sigma }_{j=1}^V(R_j^{r^{j-1}})$ and $c=H_{sig}(X||R||m)$. The single signature is calculated as ${\sigma }_s=c{a}_s{x}_s+{\Sigma }_{i=1}^V(r_{sj}{b}^{j-1})$.

• $\text{AggrSig}(\{{\sigma }_1,\dots ,{\sigma }_N\},R)$ takes the list of all signers' single signatures and aggregate commitment, returns the aggregate signature $(R,\sigma )$ where $\sigma ={\Sigma }_{i=1}^N({\sigma }_i)$.

• $\text{Verify}(m,X,\sigma ,R)$ takes as input a message, aggregate verification key, aggregate signature, and aggregate commitment. Computes $c=H_{sig}(X||R||m)$ and accepts the signature if $\sigma \cdot G=R+c\cdot X$.

Parameters of instantiation

The above is the standard definition, and in cardano we instantiate it over curve SECP256k1. Moreover, we follow BIP-0340. The following are the two specifications of the above algorithm required for compatibility. Citing literally BIP-0340:

• We use implicit Y coordinates. We encode an elliptic curve point with 32 bytes, and we implicitly choose the Y coordinate that is even[6].
• We use tagged hashed of SHA256 for the challenge computation. More precisely, in order to compute H(R, vk, m), one computes SHA256(SHA256("BIP0340/challenge")||SHA256("BIP0340/challenge") || R || vk || m).

More precisely, the following is what is the specification used in the plutus built-in functions:

• The verification key must correspond to the (x, y) coordinates of a point on the SECP256k1 curve, where x, y are unsigned integers in big-endian form.
• The verification key must correspond to a result produced by secp256k1_xonly_pubkey_serialize. This implies all of the following:
  • The verification key is 32 bytes long.
  • The bytes of the signature correspond to the x coordinate.
• The input to verify is the message to be checked; this can be of any length, and can contain any bytes in any position.
• The signature must correspond to a point R on the SECP256k1 curve, and an unsigned integer s in big-endian form.
• The signature must follow the BIP-340 standard for encoding. This implies all the following:
  • The signature is 64 bytes long.
  • The first 32 bytes are the bytes of the x coordinate of R, as a big-endian unsigned integer.
  • The last 32 bytes are the bytes of s.

      ┏━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━┓
      ┃ R <32 bytes> │ s <32 bytes>  ┃
      ┗━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━┛
      <--------- signature ---------->
  

VRF-ed25519

Verifiable Random Functions ($\text{VRF}$) allow key-pair owners, $({sk}_{\text{VRF}},{vk}_{\text{VRF}})$, to evaluate a pseudorandom function in a provable way given a randomness seed. Any party with access to the verification key, ${vk}_{\text{VRF}}$, the randomness seed, the proof and the generated randomness can indeed verify that the value is computed as expected. The VRF specification has changed overtime in Cardano, and the nodes use a different algorith, pre-Babbage and post-Babbage (if there exists a reference to the HF, we should point it out). We expose both specifications, and the motivations for such a change.

Generalised specification

We use an additional hash function to that introduced in the Notation section. In particular one that maps a binary input to an element of the group $\mathbf{G}$, ${\text{H}}_{s2c}:\{0,1{\}}^{\ast }\to \mathbf{G}$.

Pre Babbage

A $\text{VRF}$ function, in pre-Babbage eras, is defined by the following three algorithms:

• $\text{VrfKeyGen}(1^{\lambda })$ follows the exact same procedure as $\text{KeyGen}(1^{\lambda })$ described in ed25519. Output key pair $(x,{vk}_{\text{VRF}})$. We refer to the signing key $sk$ in the Ed25519 section as ${sk}_{\text{VRF}}$.
• $\text{GenerateProof}(x,{vk}_{\text{VRF}},m)$ takes as input a keypair $(x,{vk}_{\text{VRF}})$ and a message $m$, and returns the $\text{VRF}$ randomness $\beta$ together with a proof $\Pi$. Use $x$ to derive ${sk}_{\text{VRF}}$. Let $H\leftarrow {\text{H}}_{s2c}({vk}_{\text{VRF}},m)$. Let $\Gamma \leftarrow {sk}_{\text{VRF}}\cdot H$. Compute $r$ as defined in procedure $\text{Sign}$ as in ed25519. Let $c\leftarrow \text{H}(H||\Gamma ||k\cdot G||k\cdot H)[..128]$. Compute $s\leftarrow (r+c\cdot {sk}_{\text{VRF}})\mathrm{mod}q$. Finally, return the proof $\Pi \leftarrow (\Gamma ,c,s)$ and the randomness $\beta \leftarrow \text{H}(\text{suite\_string}||0x03||\text{cofvar}\cdot \Gamma ||0x00)$.
• $\text{Verify}(m,{vk}_{\text{VRF}},\Pi )$ takes as input a message $m$, a verification key ${vk}_{\text{VRF}}$ and a vrf proof $\Pi$, and returns $\beta$ or $\text{false}$. It parses the proof as $(\Gamma ,c,s)=\Pi$, and computes $H\leftarrow {\text{H}}_{s2c}({vk}_{\text{VRF}},m)$. Let $U\leftarrow s\cdot G-c\cdot {vk}_{\text{VRF}}$ and $V\leftarrow s\cdot H-c\cdot \Gamma$. Compute the challenge $c^{\prime }\leftarrow \text{H}(H||\Gamma ||U||V)[..128]$. If $c^{\prime }=c$, then return $\beta \leftarrow \text{H}(\text{suite\_string}||0x03||\text{cofvar}\cdot \Gamma ||0x00)$, otherwise, return $\text{false}$.

Post Babbage

A $\text{VRF}$ function, in post-Babbage eras, is defined by the following three algorithms:

• $\text{VrfKeyGen}(1^{\lambda })$ follows the exact same procedure as $\text{KeyGen}(1^{\lambda })$ described in ed25519. Output key pair $(x,{vk}_{\text{VRF}})$. We refer to the signing key $sk$ in the Ed25519 section as ${sk}_{\text{VRF}}$.
• $\text{GenerateProof}(x,{vk}_{\text{VRF}},m)$ takes as input a keypair $(x,{vk}_{\text{VRF}})$ and a message $m$, and returns the $\text{VRF}$ randomness $\beta$ together with a proof $\Pi$. Use $x$ to derive ${sk}_{\text{VRF}}$. Let $H\leftarrow {\text{H}}_{s2c}({vk}_{\text{VRF}},m)$. Let $\Gamma \leftarrow {sk}_{\text{VRF}}\cdot H$. Compute $r$ as defined in procedure $\text{Sign}$ as in ed25519. Let $c\leftarrow \text{H}(H||\Gamma ||k\cdot G||k\cdot H)$. Compute $s\leftarrow (r+c\cdot {sk}_{\text{VRF}})\mathrm{mod}q$. Finally, return the proof $\Pi \leftarrow (\Gamma ,k\cdot G,k\cdot H,s)$ and the randomness $\beta \leftarrow \text{H}(\text{suite\_string}||0x03||\text{cofvar}\cdot \Gamma ||0x00)$.
• $\text{Verify}(m,{vk}_{\text{VRF}},\Pi )$ takes as input a message $m$, a verification key ${vk}_{\text{VRF}}$ and a vrf proof $\Pi$, and returns $\beta$ or $\text{false}$. It parses the proof as $(\Gamma ,U,V,s)=\Pi$, and computes $H\leftarrow {\text{H}}_{s2c}({vk}_{\text{VRF}},m)$. Next, compute $c\leftarrow \text{H}(H||\Gamma ||k\cdot G||k\cdot H)[..128]$. Finally, if $U=s\cdot G-c\cdot {vk}_{\text{VRF}}$ and $V=s\cdot H-c\cdot \Gamma$, then return $\beta =\text{H}(\text{suite\_string}||0x03||\text{cofvar}\cdot \Gamma ||0x00)$, otherwise, return $\text{false}$.

This change allows for batch verification of proofs, which achieve up to a times two improvement in verification time, in exchange of a larger proof.

Parameters of instantiation

Some of the concrete parameter instantiations also differ between pre-Babbage and post-Babbage eras. We begin by describing those which coincide, and follow with a separate description for the ones that differ.

• Parameter $\ell (\kappa )$ and suite $\text{suite\_string}$: We set $\ell (\kappa )=512$. We choose the suite $\text{ECVRF\_EDWARDS25519\_SHA512\_ELL2}$, as defined in the standard draft¹. This sets the parameter $\text{suite\_string}$ as $0x04$ and the following parameters.
• Curve: We define the curve, and by consequence the finite prime order field, security parameter, cofactor, prime order subgroup and generator, as described in the ed25519 paper². In particular, we use Edwards25519 which is birationally equivalent to Curve25519.
• Hash: As a hashing algorithm we use SHA512.

Pre Babbage

We proceed with the specifications on pre-Babbage eras.

• Draft version: pre-Babbage eras are build on top of Version 03 of the standards draft³.
• Deserialization: A $\text{VRF}$ proof is represented by 80 bytes: the first 32 bytes, $b_{[..32]}$, represent the point $\Gamma$, the following 16 bytes, $b_{[\mathrm{32..48}]}$, represent the scalar $c$, and the final 32 bytes, $b_{[\mathrm{48..}]}$, represent the scalar $s$. A public key is also represented as 32 bytes, $b_{pk}$. Deserialization is valid only if:
  • $b_{[..32]}$ when read as a little-endian integer, it is smaller than $p$.
  • $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$.
• Hash to curve ${\text{H}}_{s2c}$: Elligator mapping, over a scalar computed by hashing $\text{suite\_string}||0x01||{vk}_{\text{VRF}}||m$. The mechanism is described in Section~5.4.1.2 of version 3 of the draft. Note that for implementing the mechanism as described in the draft, the sign bit is cleared before calling the elligator function, meaning that the latter always works with sign = 0 (see $\text{\_vrf\_ietfdraft03\_hash\_to\_curve\_elligator2\_25519}$ function). See Appendix A.4 of version 3 of the draft for test vectors.

Post Babbage

We finalize with the specifications of post-Babbage eras.

• Draft version: post-Babbage eras are build on top of a batch-compatible version of Version 10 of the standards draft⁴. The specific construction is described in the technical spec studying the security of batch compatibility⁵.
• Deserialization: A $\text{VRF}$ proof is represented by 128 bytes: the first 32 bytes, $b_{[..32]}$, represent the point $\Gamma$, the following 32 bytes, $b_{[\mathrm{32..64}]}$, represent the point $U$, the following 32 bytes, $b_{[\mathrm{64..96}]}$, represent the point $V$, and the final 32 bytes, $b_{[\mathrm{96..}]}$, represent the scalar $s$. A public key is also represented as 32 bytes, $b_{pk}$. Deserialization is valid only if:
  • $b_{[..32]}$ when read as a little-endian integer, it is smaller than $p$.
  • $b_{[\mathrm{96..}]}$ when read as a little-endian integer, is smaller than $q$.
  • $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$.
• Hash to curve ${\text{H}}_{s2c}$: Hash to curve algorithm as defined in the hash to curve standard⁶, version 12, Section 6.8.2 (non uniform version). For test vectors, one can use those presented in Appendix J.5.2 of that same document. Reference implementation can be found in the libsodium fork.