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.