How is Key-Evolving Signature used in Cardano?

A Key-Evolving Signature scheme is a type of digital signature scheme that is used by Cardano to protect the immutability of the ledger. The private keys that are used for signing blocks are rotated in regular intervals. Old keys are deleted so they cannot be used for forging blocks produced in the past. Let's take a closer look at this mechanism.

Understanding forward security

A traditional signature scheme is a method of verifying the authenticity and integrity of digital messages or documents. It allows a sender to attach a string of data, called a signature, to a message, that can be verified by anyone using the sender’s public key.

Let's explain how the traditional signature scheme works to make it easier for you to understand forward security.

A signature scheme usually consists of three algorithms: a key generation algorithm, a signing algorithm, and a verification algorithm.

The sender (author of the message) generates a set of keys, private and public. He must carefully guard the private key and provide the public key to everyone who wants to verify the message (verifiers). The sender so-called signs the message (usually a digest/hash of the message) with a private key. All verifiers can verify its authenticity and integrity through the public key.

Recipients (verifiers) of the message are sure that it was generated by the author (owner of the private key) and that the message has not been changed. Security is based on the assumption that the private key is not compromised.

In the figure below, you can see all the processes and uses of cryptographic keys when sending a message securely over the Internet (danger zone) between Alice and Bob. Alice carefully saved the generated private key and shared the public key with Bob. She then signed the message and sent it to Bob, who could verify it via the public key.

The described principles should be familiar to all cryptocurrency users, as something similar happens when signing transactions and submitting them to the blockchain network.

Imagine that Bob is the blockchain network that verifies if Alice can spend digital assets. If so, the network writes the transaction into the blockchain (through the block) and someone else gets the right to spend the assets. If Alice protects her private key well, no one else in the world can spend her digital assets.

A traditional digital signature scheme relies on the assumption that the secret key is never leaked or stolen by an adversary. However, this assumption may not hold in reality, due to various factors such as hardware failures, software bugs, malware attacks, or human errors. If an adversary obtains the secret key of a traditional digital signature scheme, they can forge signatures for any past or future messages, and invalidate the authenticity and integrity of all signed messages.

A key-evolving signature scheme (KES) is a type of digital signature scheme that aims to provide forward security.

Forward security means that if the secret key of a signer is compromised at some point in time, the signatures generated before that point remain valid and unforgeable. This is achieved by dividing the lifetime of the signer into time periods and using a different secret key for each period. The secret key for each period is derived from the previous one, and then erased after use. The public key remains the same for all periods.

KES prevents the scenario where an adversary obtains the secret key and thus it is possible to forge signatures for any past or future messages. In such a scenario, the adversary can invalidate the authenticity and integrity of all signed messages.

KES limits the scope of each secret key to a specific time period and ensures that old secret keys are erased and unrecoverable. Therefore, even if an adversary obtains a secret key for a certain period, they can only forge signatures for that period, and not for any previous or future periods.

In the picture below you can see the time divided into 5 periods. In the first period, the signer (sender) generated a private KEY 1 and a public KEY 1. He shared the public KEY 1 with the verifier (recipient). In period 2, a new private KEY 2 was generated and then private KEY 1 was deleted. This was repeated in period 3, in which a new private KEY 3 was generated and private KEY 2 was deleted.

Note that the verifier in all periods always uses the same public KEY 1 to verify all messages.

Period 3 is active and only private KEY 3 can be used to sign messages. Private keys KEY 1 and KEY 2 have been deleted, so messages 1 and 2 cannot be forged. If an adversary succeeds in obtaining private KEY 3 (it is the only one that currently exists), he cannot change the past, i.e. messages 1 and 2. He can only change messages in period 3. If the adversary is not able to generate keys for future periods, he is not able to change future messages either.

How the KES scheme is used in Cardano

Cardano must ensure the immutability of the blockchain. The KES scheme is used for signing blocks by the stake pool operators.

For the secure operation of the pool, it is necessary to generate multiple keys. In this article, we will focus only on KES keys. To fully understand the topic, it is necessary to know the entire key generation process, the creation of certificates, and the usage of all keys.

A stake pool operator needs to have three types of keys: a stake pool key (also called an operator key), a KES key pair, and a VRF key pair. Key pairs are a prerequisite for configuring the pool node (there must be signing VRF and KES keys in hot storage) and creating certificates.

The stake pool key is an offline key pair (stored in cold storage) that identifies the stake pool (to be more precise, it is a hash of the key). The signing stake pool key is used for signing certificates.

The KES key pair is an online key pair (the signing KES key is stored in hot storage on the node) that authenticates the block producer and evolves over time. The verification KES key is used for the verification of the signatures of newly minted blocks by the pool.

The VRF key pair is another online key pair that is used for private lottery (slot leader election) and proves the right to mint a block in a given slot. In this article, we will focus on KES keys.

First of all, the stake pool must be registered through the register stake pool certificate. This certificate contains, among other things, a verification stake pool key (ID) and verification VRF key. Pool registration does not need to be renewed regularly. An operational key certificate is used to renew the KES key. As you will see later, this certificate is renewed at regular intervals. Both certificates must be signed by the signing stake pool key.

By signing the operational key certificate by the signing stake pool key (cold storage), the pool operator transfers the right to the KES key to sign blocks.

The operational key certificate contains two verification (public) keys: The stake pool key and the KES key. Further, the certificate counter and the validity period. The validity period indicates how many time periods (or slots) the certificate is valid for. The operational key certificate is submitted to the network and stored on the blockchain.

All nodes track the information needed for verification. VRF keys and counter certificates are the pieces of information that nodes have immediately available without having to search the blockchain.

All pool operators must create and submit operational key certificates to the blockchain. The operational key certificates represent the link between the operators’ offline keys and operational (hot) keys. The certificate contains the verification KES key and must be signed by the signing stake pool key (cold storage). New blocks must be signed by the signing KES key (hot storage).

Certificates allow all nodes in the network to verify the authenticity and integrity of the blocks through the verification KES keys.

In the image below you can see the creation of an operational key certificate. Note mainly the signing of the certificate with a signing stake pool key (operator key). If the hot private keys were compromised, an adversary still does not have access to the operator's private key that is in cold storage.

If the operator discovers that the private (hot) keys have been compromised, it is enough to create and submit a new operational key certificate with an increased certificate counter. This will invalidate the previous certificate.

In the picture below, you can see that the block N+1 contains an operational key certificate with a counter that has a value of N. The pool operator decided to submit a new certificate with a counter that has a value of N+1. It happened in block N+5. The older certificate is now invalid.

As we have already said, all certificates (in this context, stake pool registration certificate and operational key certificate) are stored in the blockchain, so they are available to every full node in the network. This is important for verifying the blocks that a node receives from the network.

To sign a block in a given slot, the block producer needs to use the private KES key. Before that, the node inserts VRF output and VRF proof into the block header (and a few other things). The signing KES key is used to generate a signature that can be verified by anyone using the corresponding verification KES key from the operational certificate. The link between a newly minted block and the certificate (that contains the KES key) is a hash of the stake pool key (ID). ID is also part of the block header. So it is easy for the node to take ID from the block header and use it to find the corresponding certificate (verification KES key) in the local set of certificates.

The VRF function is used to generate proof that can be verified by anyone using the public VRF key from the stake pool registration certificate. The proof shows that the block producer has been elected by a VRF function based on provided inputs: slot ID, nonce, signing VRF key, and total stake of the pool (VRF output is compared with the threshold that is calculated based on the stake).

In the image below you can see the minting and verification of a new block. The stake pool registration certificate and operational key certificate of the pool (the block producer) are already in the blockchain and signed by the signing stake pool key (cold storage). There is only one block in the blockchain in the image. The verifier node has all the verification keys and data it needs to verify the blocks in its local states. Keys and data were retrieved from the certificates that have been stored in the blockchain before minting the block. The block producer node inserts the pool ID (verification stake pool key), VRF output and proof, and other data for verification into the block. Then it signs the block with the signing KES key. The verifier node can easily verify the block by checking the VRF data and KES signature (and other things). Notice how the verifier node created the necessary local state from the data stored in the blockchain.

To update the secret KES key to the next time period, the block producer needs to use a predefined algorithm that derives a new secret KES key from the old one, and then erases the old one. This way, only one private KES key is stored at any time, and it cannot be used to forge signatures for previous periods. The public KES key remains unchanged, so there is no need to update the operational certificate or register it again on the blockchain.

The key will evolve automatically after each period of 129,600 (one and a half days, approximately 6,500 blocks are produced during this time) slots and it can evolve up to 62 times before it needs to be renewed. In other words, one period lasts 129,600 slots (seconds). The operational key certificate has a lifetime of 90 days after which it becomes invalid. It encourages pool operators to regularly rotate their operational keys.

In the picture below you can see how new KES keys are regularly generated every period and after 3 months a new operational key certificate is generated. A Cardano node can mint several blocks in each period depending on the stake size.

The advantage of using the KES scheme in Cardano is that it provides stronger security guarantees in case of key exposure. If an adversary obtains the private KES key of a block producer, they can only forge signatures for the current period, but not for any previous or future periods. Moreover, they cannot rewrite history or create forks, because they do not have access to the VRF key or the operator key. Therefore, using the KES schemes reduces the risk of losing control over the stake pool or compromising its reputation.

The KES scheme ensures that the history of the Cardano blockchain is immutable. Security is based on the assumption that pool operators follow the protocol and delete old KES keys, and the network is highly decentralized, i.e. there are as many pool operators as possible. The more operators (signers) there are, the less risk there is that they will cooperate with each other in order to compromise the network.

If the pool operators do not delete the previous private keys as expected, then they could potentially sell or leak them to an adversary, who could then use them to forge signatures for blocks that have been added in past periods. This would undermine the forward security property of the scheme and allow the adversary to tamper with the history of signed blocks.

Active pool operators are economically motivated to guard private KES keys if they do not delete them and keep them for later use. Operators who go out of business (and sell all ADA coins) no longer have an economic incentive to keep the Cardano network secure and can potentially sell the old KES keys. It is important to note that keys from one operator will only allow a small portion of the blocks to be overwritten, depending on what the operator's stake was and how long he has been producing blocks. In order to overwrite the history of the blockchain, an adversary would have to obtain more than half of the old keys.

Dozens of the largest operators, or hundreds of smaller ones, would have to break the rules of the protocol and deliberately keep the keys for this purpose. This seems very unlikely.

In the future, even this risk can be eliminated through so-called one-shot signature cryptography. This allows the private key to be used only for a single signature. Subsequently, the private key can be published without causing any damage in the context of the digital signature for which it was used.

Conclusion

KES and VRF cryptography allows Cardano to ensure the immutability of the blockchain and the random selection of the slot leader (the node that gets the right to produce a block in a given slot) in an efficient way, i.e. without the use of Proof-of-Work (PoW). PoW fulfills essentially the same role. In the PoW network, the node that first finds a solution to a complex cryptographic task will mine the block (random selection of node). Mining the block involves spending a huge amount of energy, which essentially prevents the history of the blockchain from being overwritten. Rewriting history is possible provided that the same amount of energy is expended again and the adversary chain becomes the longest chain.

Achieving higher efficiency in ensuring random selection and immutability of the ledger through modern cryptography is an important technological advance, especially in the context of long-term economic sustainability of the network and environmental protection.