Presenting the Cross-chain Update Transaction

  • By Maxime Gagnebin Ph.D. in Research
  • 25 Aug 2021
  • 8 min read

This is the next edition of the blog post series covering the details of the Lisk interoperability solution. In the previous blog post we discussed the lifecycle of a sidechain, its registration, and its termination. Here, we cover an important transaction used to communicate information from one chain to another: the cross-chain update. 

 

This topic was covered during the Lisk.js event and the speech given by Andreas Kendziorra can be found here.

 

Before delving into details of the topic itself, let us recap the basic paradigm of cross-chain communication that will be used in the Lisk ecosystem, as depicted in the diagram below.

CCU1
Figure 1: Cross-chain messages M1 to M3 are included in the sending chain along with a certificate. They are then combined in a cross-chain update and included in the receiving chain.

The standard method for cross-chain communication in the Lisk ecosystem is through cross-chain messages (CCMs). They are emitted when executing certain transactions, for example a cross-chain token transfer, and are then stored in the sending chain's outbox. The messages along with a certificate (described in more details below), are then gathered and included in a cross-chain update transaction (CCU). They are the envelopes carrying all the messages. When executing a CCU, the receiving chain opens the envelope, adds all the CCMs to the chain inbox, and executes the cross-chain commands corresponding to the messages.

Roles of the CCU

The foremost role of the CCU transaction is to allow CCMs to be transmitted from the sending chain to the receiving chain. This must be done in a secure and trustless manner. Secure means that nodes on the receiving chain are guaranteed that the CCMs were included in the sending chain in finalized blocks. Trustless means that the CCU can be submitted by anyone to the receiving chain and does not require any special privileges.

Guaranteeing Security

Let us first describe the main ingredient to our solution's security: the certificate. Certificates are compact objects derived from a block header and containing the minimal amount of information required for interoperability, namely the block ID, the block height, the block timestamp, the state root, the hash of validators, and an aggregated signature. The aggregated signature must be created by validators of the chain and must contain enough signatures to guarantee that the information in the certificate is final. Of course, we would not want to transmit information to another chain with the risk that it is reverted in the sending chain. This would lead to inconsistent state information between the involved chains, which would be disastrous for their communication.

 

In our state store, each chain maintains an interoperability store containing the data of other chains that they interact with. Amongst other properties, this includes the state root, the validator set, the inbox (as an append only merkle tree), the height, and the timestamp. Setting or changing those properties can only be done if the values are signed by the delegates of the sending chain. This can happen with a certificate, hence, for this reason we state that those values are certified.

 

It is important that the information concerning other chains is regularly updated in order for the cross-chain communication to remain active. This is done by posting CCUs which contain recent certificates.

 

How does this allow us to guarantee the inclusion of CCMs in the sending chain? Well, as part of the interoperability account, each chain maintains an outbox to which all CCMs are added. This outbox is authenticated by a Merkle root, which we call the outbox root. This outbox root is part of the whole state store which was certified in the CCU, namely by the state root. This means that on the receiving chain, the certified state root and a Merkle inclusion proof are enough to verify that a CCM was included in the sending chain.

 

Lastly, guaranteeing security is only possible if the interoperable chains maintain the correct set of validators for the sending chains. The validators of the sending chain might change over time, and it is important that the receiving chain stays up to date with the new validators. To this effect, the certificates contain the hash of the set of validators required to sign the next certificate, and the CCU contains the public keys needed to verify this hash.

Trustless CCUs

The trustless property of our interoperability comes naturally from the fact that certificate signatures must be included in block headers. Validators are incentivized to sign certificates and to exchange signatures, those signatures are then aggregated and incorporated into a block header. In a future blog post, we will delve more into the details of the certificate generation and incentivization. As the signature is readily available, anyone can use it to generate a certificate and consequently a CCU.

 

CCU2

 

Figure 2: A CCU contains the following properties: the ID of the sending chain, the certificate, the validator update, and the inbox update. The certificate contains the certified state root, a signature guaranteeing the validity of the certificate, and the hash of the validators set endorsed to sign the next certificate from this chain. The validator update describes how the validator set stored in the chain data must be updated to match the validator hash. The inbox update contains the transmitted CCMs, and the necessary Merkle proofs that those messages are part of the certified state root.

The First CCU

Let's mention a unique role that the first CCU fulfills. The previous blog post described the lifecycle of a blockchain and its start in the registered phase. This phase can last as long as desired; it is only when including the very first CCU sent by the registered chain that the chain's status will change to active. From this point onwards, the chain can interact with the ecosystem.

The Liveness Condition

This condition is designed to guarantee that all active chains in the ecosystem regularly update their data on the mainchain. As detailed in our previous blog post, if a chain fails to update its data each month, it will be terminated. This termination procedure is necessary to allow users to recover funds and messages that were sent to the inactive chain. Satisfying the liveness condition is done by posting CCUs regularly.

An Extended Example of Cross-chain Interaction

For the remainder of this blog post, we will focus on a particular example of communication between chain A (the sending chain), and chain B (the receiving chain). In this regard, we will not consider the blocks of chain A, this is because its actual block structure is not relevant to chain B when receiving CCUs. Rather, on chain A, the focus is on the messages added to the outbox and the certified roots. On chain B, the focus will be on the certified state root, the inbox, and the inbox root.

 

A typical scenario depicting the information of interest on chain A is shown below, the CCMs included in the outbox (denoted by M0, M1, ...) and the generated certificates (in green boxes).

CCU3
Figure 3: Our example scenario sketching chain A, the CCMs included in the outbox (M0, M1, ...), and the generated certificates (in green boxes).

The aim of the cross-chain communication is now to bring those messages to chain B, the receiving chain. This is accomplished using CCUs and we will see below the different options available for creating CCUs. To be fully complete, the CCUs presented below would also need to include the appropriate Merkle proofs, signature and validator updates, however, for the sake of simplicity we will omit them here. The Lisk products will provide tools to automatically and easily generate, or request those missing pieces.

 

Let us assume that on chain B, the first 2 certificates and all CCMs up to M5 have been received. Thus the state of the inbox and certified roots is as shown below:

CCU4
Figure 4: Initial setting of chain B, the receiving chain, for our example. The CCMs up to M5 have been included in the inbox and the chain data is shown in the green box.

CCU Contains All Pending CCMs up to a Certificate

This case is the most likely one. Here, all the CCMs needed to compute the certified outbox root are included in the CCU. This is the most efficient way to update the receiving chain as there is no need for an additional proof of inclusion. In our example, this would be the case for the example shown below:

 

CCU5

 

Figure 5: A CCU containing certificate 3 and the CCMs from M6 to M11.

 

Hence, chain B would be updated as follows:

CCU6
Figure 6: The inbox on chain B now includes all CCMs up to M11 and the chain data has been updated.

Notice that even though there exists an additional certificate (the certificate for height 23 in our example), there is no obligation to include it in the receiving chain. The only requirement being that the included certificate is validly signed by the validator set stored in the interoperability store (on chain B).

Missing Some CCMs

It should be noted that it is not always possible to follow the pattern just described. The reason being that the CCU transaction must fully fit in a single block of the receiving chain (as is the case for any transaction). So, if the CCMs included in the outbox between two certified state roots have a total size larger than the block size, it becomes impossible to include them all in chain B. For this reason, it is possible to certify a state without including all messages. For example by posting:

 

CCU7

 

Figure 7: A CCU containing certificate 4 and the CCMs from M12 to M14.

 

In this CCU, certificate 4 is included in the CCU along with the CCMs M12, M13, and M14. Notice that CCMs M15, M16, and M17 are included in the certified outbox root, but not in the CCU. In that case, an additional Merkle proof is included in the CCU to prove that the given CCMs were the ones included in the outbox. The state of chain B is now as can be seen below:

CCU8
Figure 8: As expected, the inbox now contains the messages up to M14. The box containing the certified data has been shifted to the right to indicate that not all messages corresponding to the certified state root have been included in the inbox yet.

Completing the Inbox

It is now time to fill in the inbox. Here there is no obligation to include a new certificate in the CCU and only CCMs can be given.

 

CCU9

 

Figure 9: A CCU containing the CCMs from M15 to M17. Notice that no certificate is included in this CCU.

 

The CCMs are authenticated against the stored certified state root and included in the receiving chain:

CCU10
Figure 10: The CCMs M15 to M17 are now included in the inbox.

Again, if the given CCMs would be insufficient to complete the inbox (for example if M17 was not included), another proof of their inclusion in the outbox would be given.

 

We have now progressed up to M17 and the cross-chain communication will continue in a similar fashion. More messages will be included in chain A, growing the outbox, and those messages will be forwarded to chain B growing the inbox, and updating the certified information.

Conclusion and Next Topic

In this blog post we have covered the different roles of the CCU, and how CCUs and certificates are used to guarantee that the cross-chain communication happens securely. The details of CCMs and the certificate generation process will be the main subject of future editions of this blog post series. If you want to know more about how CCMs can transfer tokens and NFTs, or how recovery transactions actually work, we highly recommend you not to miss them. 

 

The technical specifications of the topic covered in this blog post can be found in our Lisk Research forum. In particular, the LIP “Introduce cross-chain update transactions” defines the CCU and its application. This LIP, together with an additional 10 LIPs describing the interoperability solution, were recently published and proposed for the Lisk protocol. Cross-chain communication between blockchains is still a novel and open area of research, therefore we are happy to receive technical feedback, suggestions, or questions about our approach in the Lisk Research forum.

Maxime Gagnebin Ph.D.

Research Scientist

A long time lover of mathematics and logic, Maxime completed his PhD in probability theory in Geneva. He then turned to applied aspects of problem solving and studied machine learning as well as blockchain technology. He joined Lightcurve in 2019 as a Research Scientist and has since been working on improving the Lisk protocol. His other passions include climbing, yoga and brass band music.