Certificate Generation and Consensus

  • By Jan Hackfeld Ph.D. in Research
  • 24 Feb 2022
  • 12 min read

In this blog post, we will have a detailed look at certificates - the key object for making Lisk’s interoperability secure. We explain what certificates are, how they are generated, and how they are connected to the consensus protocol. Moreover, we discuss the security assumptions and guarantees of Lisk’s interoperability solution.

 

The topic of this blog post was also presented at Lisk.js 2021. Further note that this blog post is part of an ongoing blog post series about interoperability in Lisk. We mostly tried to keep the content self-contained, but as background some general understanding of Lisk’s interoperability solution is helpful (check out this blog post or this video at Lisk.js 2021 for a general introduction to the topic).

 

Lisk Research Forum

Lisk Interoperability and Certificates

Lisk’s interoperability solution is based on the paradigm of cross-chain certification. In a nutshell, this means that information from another blockchain is accepted and processed if the correctness of this information is attested by a certificate. A certificate in this context is an object signed by several entities, typically the validators of the blockchain where the information originates from. This ensures that the certificate and hence the associated information is trustworthy and cannot be manipulated. In a way, you can view these cross-chain certificates as a decentralized version of public key certificates that secure most of the communication over the internet today.

 

Let us shortly recap here how interoperability works in the Lisk ecosystem and in which way certificates are used in Lisk. The means for sending information from one blockchain to another are cross-chain messages (CCMs). Cross-chain messages can be emitted by any transaction and are then relayed to the receiving chain where they are processed. For more information on cross-chain messages, check out this blog post or the related talk from Lisk.js 2021.

 

The containers for submitting information to another blockchain are cross-chain update transactions (CCUs). These transactions allow anyone to submit cross-chain messages together with a certificate that attests the correctness of these messages to another blockchain. See also the diagram below. If you want to learn more details about cross-chain update transactions, check out this blog post or this talk from Lisk.js 2021

An overview of Lisk Interoperability

Figure 1: An overview of Lisk Interoperability showing how cross-chain messages (CCMs) and a certificate are submitted in a cross-chain update transaction (CCU) to another chain.

 

In Lisk, every blockchain will regularly generate certificates that are collectively signed by the current validators of the respective blockchain. Moreover, every blockchain in the Lisk ecosystem keeps track of the current validators of every blockchain they are directly communicating with. For instance, the Lisk Mainchain keeps track of the validators of all sidechains. This allows the Lisk Mainchain in the example above to check if the certificate indeed was collectively signed by the sidechain validators. Note that not all validators are required to sign it, but only a certain quorum.

 

To summarize, certificates and the validity of signatures contained in certificates are the basis for the security of interoperability and the reason why information from other chains is deemed correct and trustworthy.

Lisk-BFT consensus

Before explaining the certificate generation process, let us first go over some basic concepts related to the consensus protocol used in Lisk, as these are connected to the certificate generation and the security guarantees discussed later. By consensus protocol we mean the protocol for validators (delegates in the case of DPoS and authorities in the case of PoA) to agree on one chain of blocks. In particular, the consensus protocol defines when a block and all included transactions are final, i.e., irrevocably deemed part of the blockchain.

Several blocks generated by the different validators

Figure 2: The diagram shows an example of several blocks generated by the different validators. The two blocks B1 and B2 are conflicting and the purpose of the consensus protocol is to resolve this situation such that the validators agree on one chain of blocks.

 

The consensus protocol used in the Lisk SDK and on the Lisk Mainchain is called Lisk-BFT (a detailed introduction to the protocol can be found in this blog post). An important property of this protocol, as suggested by the name, is that it provides Byzantine fault tolerance (BFT). This means that the protocol works correctly even if some of the validators are Byzantine, i.e., they are offline or are maliciously trying to manipulate the network. The two key technical properties that we mean by “works correctly” are the following:

  • Safety: There are never two conflicting blocks (blocks where none is a descendant of the other) that are considered final. This property is important for preventing double-spending, i.e., that a user can spend funds twice, each in a different manner in the two finalized blocks.
  • Liveness: New blocks are always eventually finalized. This property is important as users want to rely on a payment being irreversible at some point.

The liveness and safety property are only guaranteed if not too many validators are Byzantine or, in other words, if enough validators are honest, i.e., correctly following the Lisk-BFT protocol. Concretely, if more than ⅔ of the validators are honest, then Lisk-BFT guarantees safety and liveness (As a technical note: some extra conditions are necessary for changing validators and for the liveness condition, see the technical paper for details). For the Lisk Mainchain, this means that as long as at least 68 of the active delegates are honest, both the safety and liveness property hold.

Certificate Generation Process

As mentioned in the introduction, in the Lisk ecosystem every blockchain will be regularly generating new certificates. This process can be described in the following three steps.

Step 1: Compute Unsigned Certificate From Finalized Block

In this first step, as soon as a new block B is finalized, every validator in the blockchain computes an unsigned certificate from block B. This is simply done by taking a subset of the block header properties of B, namely those relevant for cross-chain communication.

A certificate derived from a finalized block

Figure 3: A certificate is derived from a finalized block by taking a subset of the block header properties.

 

It is also very important that certificates are only ever generated for finalized blocks. The reason is that only cross-chain messages emitted by transactions in finalized blocks can be reliably communicated to other chains. Otherwise, the problematic situation could arise that a message is communicated to another chain (e.g., 10 LSK should be credited to a user) although the transaction emitting the message in the sending chain is reversed  (e.g., debiting 10 LSK from a user).

Step 2: Compute and Broadcast Certificate Signatures

As a second step, after computing the unsigned certificate, every validator computes their signature of the certificate and subsequently broadcasts this signature to the P2P network. For the Lisk Mainchain, this means that all 101 active delegates compute their certificate signature and subsequently 101 distinct signatures are shared via the P2P network.

Broadcasting a certificate signature

Figure 4: Every validator node broadcasts its certificate signature to its connected peers in the P2P network.

Step 3: Signature Aggregation and Inclusion in Block

In the third step, one of the validators of the blockchain aggregates all signatures for the certificate that they received via the P2P network and adds this aggregate signature to a block. In the case of the Lisk Mainchain, up to 101 different signatures would be aggregated into one compact signature, which is then added to a block.

An aggregate BLS signature of the certificate

Figure 5: The aggregate BLS signature of the certificate derived from block B is included in a subsequent block.

 

Here it is important to note that for certificate signatures we use BLS signatures in Lisk (see LIP 38 for technical details). These are different from the signatures used in transactions and have the convenient property that many different signatures can be compactly aggregated to one signature. For instance, all 101 distinct BLS signatures of the active delegates of the Lisk Mainchain would each have a size of 96 bytes, but can be aggregated to one BLS signature of size 96 bytes only. As certificates will be frequently exchanged between different blockchains in the Lisk ecosystem, having compact aggregate signatures and therefore compact certificates is important for efficient communication between different chains.

 

Now, after all three steps are completed, anyone can obtain the full certificate from the blockchain by obtaining block B, computing the unsigned certificate, and then obtaining the aggregate signature added to the blockchain in Step 3. This means that anyone following the blockchain has the possibility to create cross-chain updates because all of the necessary data is available to them.

Certificate Validation and Chain of Trust

In the introduction, we mentioned that every blockchain keeps track of the validators of every other blockchain they are communicating with, and uses this information to validate the certificates submitted as part of cross-chain update transactions. In this section, we explain further in detail how this works.

 

What a blockchain actually keeps track of for validating certificates is the following information:

  • the BLS public keys of the validators of the other blockchain,
  • for every BLS public key an associated weight called BFT weight,
  • the certificate threshold, a threshold value required for certificates to be valid.

Then a certificate is valid if apart from some basic format checks on all properties, it is signed by a subset of the currently known BLS public keys, and the sum of BFT weights of the signers is at least the certificate threshold value.

 

To better understand what this means, let us look at the example shown in Figure 6 below. Here the public keys of four validators, A, B, C, and D, which are known to the Lisk Mainchain, each of them has a BFT weight of 1 and the certificate threshold is 3. This means a valid certificate has to be signed by at least 3 of the 4 validators. Note that the initial validator public keys, BFT weights and certificate threshold are set in the sidechain registration on the Lisk Mainchain. In the example, we observe that if the validators on the sidechain change, but the public keys on the Lisk Mainchain are not updated, certificates generated by the sidechain are not considered valid for the Lisk Mainchain anymore.

An example of a sidechain with four active validators that change over time

Figure 6: An example of a sidechain with four active validators that change over time so that eventually certificates generated by the sidechain are rejected by the Lisk Mainchain.

 

The solution to this problem is to also use certificates to attest changes of the validators, BFT weights, or the certificate threshold. The validators hash property contained in every certificate is computed from the BLS public keys, BFT weights, and the certificate threshold valid from the next block onwards. This means that notifications about a future change of any of these properties from the next block onwards can be included in a cross-chain update transaction and the validators hash property in the certificate allows verifying that the provided information was correct.

 

Let us revisit the example above. The diagram below illustrates how the validators hash attests the changes of BLS public keys. For instance, Certificate 1 attests the replacement of validator A by validator E and Certificate 2 the replacement of validator B by validator F. Submitting these certificates as part of a cross-chain update together with the information about the change of validators, i.e., the new validator public keys, then allows to keep the Lisk Mainchain up to date with the currently active sidechain validators.

a sidechain with four active validators that change over time, but which generate certificates attesting the validator changes

Figure 7: An example of a sidechain with four active validators that change over time, but which generate certificates attesting the validator changes.

 

One important property that we would like to be satisfied by the generated certificates of one blockchain is that they can actually be sequentially submitted to another blockchain. For instance, if Certificate 2 in Figure 7 would never be generated, then Certificate 3 cannot be submitted as part of a cross-chain update directly after Certificate 1, because validator F was not yet communicated to the Lisk Mainchain and signatures by at least 3 validators are required.

 

So what we need is that in the sequence of certificates generated by a blockchain, the certificate signature is always valid with respect to the BLS public keys, BFT weights, and certificate threshold authenticated by the validators hash of the previous certificate. We say in that case that the sequence of certificates satisfies the chain of trust property. Observe that the three certificates in Figure 7 satisfy the chain of trust property. If this chain of trust property is satisfied, then certificates can always be sequentially submitted as part of cross-chain update transactions, and other blockchains can be kept updated about the current validators.

 

As the chain of trust property is crucial for interoperability, we put additional incentives in place to ensure that it is always satisfied. In a blockchain utilizing DPoS, we require that a certificate is generated attesting that a delegate leaves the set of active delegates before that delegate and their voters can unlock their tokens (see LIP 59 for details). For a blockchain utilizing PoA, the authorities typically have some degree of ownership in the project and are typically public entities with their reputation at stake. Hence, no additional incentives are included for PoA blockchains.

Security Assumptions and Guarantees

Certificates are the foundation for the security of cross-chain communication and in this section we want to discuss the desired security guarantees and the necessary security assumptions.

 

For cross-chain communication to be secure, we would like (1) each received cross-chain message by a blockchain in the Lisk ecosystem to be a message that was indeed sent by the sending chain. Additionally, we would like (2) every cross-chain message to be eventually delivered. Let us consider the following two properties of certificates generated by a blockchain and thereafter discuss how these relate to the previous properties.

  • Certification validity: The certificates generated by one blockchain are derived from a chain of finalized blocks defining valid state transitions according to the protocol of the blockchain.
  • Certification liveness: The blockchain continuously generates new certificates derived from new blocks and the sequence of certificates satisfies the chain of trust property. In particular, new blocks are continuously finalized.

Assume that both the certification validity and certification liveness are satisfied for a sidechain. Then the certificates generated by that sidechain can be sequentially submitted to the Lisk Mainchain. In particular, this allows creating cross-chain update transactions for keeping the Lisk Mainchain up to date with the active validators in the sidechain, and for submitting new cross-chain messages. Moreover, due to the certification validity property, all cross-chain messages attested by the certificate must have indeed been emitted by a transaction in the sidechain. Hence, both of the desired initial properties (1) and (2) hold.

 

In general, the cross-chain communication between a group of blockchains in the Lisk ecosystem is secure if each chain in the group satisfies the certification validity and liveness property. However, even if one blockchain fails one of the properties, this failure is limited only to the messages emitted by that blockchain. Moreover, there are additional measures in place, such as the escrow in the Token module, that limit the potential impact of messages from a blockchain failing these conditions.

 

Observe that both properties are closely connected to the properties of the consensus protocol of the blockchain. Certification validity requires the safety property to hold because two conflicting finalized blocks would lead to conflicting certificates violating the certification validity. Furthermore, the liveness property is required as without new finalized blocks no new certificates can be generated.

 

Now let us consider some sufficient assumptions for both certification validity and certification liveness to hold. Assume that more than two-thirds of the active validators of the blockchain, in terms of BFT weights, are always honest. This means that both the safety and liveness property are satisfied (for simplicity, we neglect some additional conditions for changing validators here). We further assume that the certificate threshold is the same as the threshold required for finalizing a block, which in general is the recommended choice and the default in the Lisk protocol. If we then extend the definition of honest to also mean correctly participating in the certificate generation process protocol, then both the certification validity and certification liveness property hold. This is a fundamental property as it means that cross-chain messaging is basically as secure as the underlying consensus protocol.

Summary

Certificates are the key object for making Lisk’s interoperability secure. We learned that certificates are an important part in cross-chain update transactions attesting the correctness of cross-chain messages and updates about the current validator set. Additionally, we explained the certificate generation process, the rules for validating certificate signatures, and the importance of the chain of trust property that guarantees that certificates can always be submitted sequentially to another blockchain. Finally, we saw that the necessary and sufficient conditions for cross-chain communication to be secure are basically the same as those already required for the consensus protocols of the involved blockchains to be secure.

 

If you wish to dive further into the technical specifications, check out the protocol specifications in LIP 0061 or ask technical questions about certificates in the Lisk Research forum.

Jan Hackfeld Ph.D.

Head of Research

Jan holds a Ph.D. in Mathematics from Technische Universität Berlin, specializing in Distributed Algorithms and Optimization. As the Head of Research at Lightcurve, he is responsible for researching ways to improve different aspects of the current Lisk protocol. Outside of the workplace, Jan is a fan of the outdoors and enjoys beach volleyball, cycling, and hiking.