Hello,
In this thread, I want to propose a LIP for the roadmap objective “Define cross-chain messaging protocol”. The proposal’s main contribution is to define new transactions, the cross-chain updates, for the Lisk ecosystem.
I’m looking forward to your feedback.
Here is a complete LIP draft:
LIP:
Title: Introduce cross-chain update transactions
Author: Maxime Gagnebin <maxime.gagnebin@lightcurve.io>
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: "Cross-chain messages", "Properties, serialization, and initial values of the interoperability module"
Abstract
This LIP introduces cross-chain update transactions which are used to post certified information and cross-chain messages in Lisk ecosystem chains.
Cross-chain update transactions are the carriers of the information transmitted between chains. By posting a cross-chain update, the receiving chain gets the information required about the advancement of the sending chain. The transaction can also include cross-chain messages and thus serves as an envelope for messages from one chain to another.
Copyright
This LIP is licensed under the Creative Commons Zero 1.0 Universal.
Motivation
Motivation for the Lisk interoperability module and the cross-chain update transaction can be found in LIP “Properties, serialization, and initial values of the interoperability module”.
Rationale
Cross-chain Update Transaction Properties
sendingChainId
Identifies the chain sending the cross-chain update. Only cross-chain update transactions coming from registered chains are valid, registered chains are the ones with an entry in the interoperability store corresponding to their chainID
.
certificate
Used to update the cross-chain account. It must be a certificate with an adequate BLS signature. The signature is always validated against the public key set stored in the sending chain account.
It is important to note here that the validation of this signature is done with respect to the network identifier of the sending chain. This network identifier is included in the sending chain account in the interoperability store.
validatorUpdate
The chain account will store the public keys required to validate the certificate signature. Those public keys have to be updated if the validator set changes in the chain sending the certificate. The difference between the old public key set and the new one is included in this property.
This update also contains the newCertificateThreshold
property. This value is the new certificate threshold used on the sending chain to attest the validity of signed certificates.
inboxUpdate
The inboxUpdate
contains the information relative to the messages to be included in the sending chain inbox. As specified in LIP “Properties, serialization, and initial values of the interoperability module”, cross-chain messages are stored in the chain outbox on the sending chain and in the corresponding inbox on the receiving chain. This property contains three elements: the cross-chain messages themselves, an inclusion witness into the outbox root, and an inclusion witness of this outbox root into the state root.
crossChainMessages
An array of cross-chain messages. See LIP “Cross-chain messages” for the general properties and processing of cross-chain messages. The crossChainMessages
property must contain consecutive messages from the outbox.
messageWitness
In the sending chain, all cross-chain messages are added to a regular Merkle tree attested by the outbox root. The messageWitness
contains two values relative to that Merkle tree: the partnerChainOutboxSize
, giving the total messages sent by the partner chain,
and the siblingHashes
, which is part of a regular Merkle proof.
This Merkle proof is required if not all messages necessary to recompute the outbox root were given in crossChainMessages
. If all messages required to compute the outbox root are included in crossChainMessages
then siblingHashes
can be left empty.
outboxRootWitness
The outbox root of the sending chain is part of a sparse Merkle tree attested by the state root (provided in the certificate). The outboxRootWitness
property is an inclusion proof into the state root of the outbox root computed from the receiving chain inbox, crossChainMessages
and messageWitness
. If the cross-chain update transaction contains an empty certificate, this property can also be left empty, as the required root was already attested in a previous cross-chain update.
Posting Cross-chain Updates on Mainchain and on Sidechains
As the roles of both mainchain and sidechain are quite different, so are the transactions used to post cross-chain updates. The most notable differences are:
- On the mainchain, all CCMs included in the
inboxUpdate
must have theirsendingChainID
equal to the chainID sending the cross-chain update. - On sidechains, all CCMs included in the
inboxUpdate
must have theirreceivingChainID
equal to the chainID of the sidechain receiving the cross-chain update. - As the mainchain accepts CCMs with
receivingChainID
corresponding to another sidechain, the cross-chain update processing on the mainchain is responsible for the inclusion of those CCMs in the corresponding outbox.
These points guarantee that the CCMs are always forwarded to the correct chains and that the receiving chain can be confident that the chain specified in CCM.sendingChainID
was truly the chain issuing the CCM.
Creating and Posting Cross-chain Update Transactions
The Lisk consensus mechanism is designed to create and publish certificates regularly, at least once per round. In that regard, obtaining the information required to post a cross-chain update transaction is easy and straightforward. The following is an example workflow that a relayer for a given sidechain could follow.
Setup to gather the required mainchain information:
- Run a mainchain node.
- Maintain a list of all CCMs included in the sidechain outbox. For each height where a CCM was included in the outbox, also save the inclusion witness of the outbox into the state root. All CCMs and witnesses for heights that have been certified on the sidechain can be discarded.
- Maintain a history of all validator changes on the mainchain for rounds that have not yet been certified on the sidechain.
Create a cross-chain update transaction for a given height h1
:
- Find a signed certificate in the mainchain block headers for a height (say
h2
) higher or equal toh1
. This will be used as thecertificate
property of the transaction. - The property
inboxUpdate.crossChainMessages
lists all CCMs that have been included in the sidechain outbox up toh2
(and which have not been included on the sidechain yet). In this case, themessageWitness
will be empty. - Compute the inclusion proof for the outbox root of the sidechain account into the mainchain state root. This proof is then used to compute
inboxUpdate.outboxRootWitness
. - If the
validatorsHash
property of the certificate is different from thevalidatorsHash
derived from thevalidators
property of the mainchain account on the sidechain, compute the required update between both sets and include it invalidatorUpdate
. How to obtain this update is detailed in the Appendix. - Post the cross-chain update transaction on the sidechain.
Relayers should post cross-chain update transactions on the sidechain when the need for it arises. This can be either because some CCMs have been included in the outbox and need to be relayed, or when the mainchain validator changes require the channel to be updated on the sidechain.
The role of relayer is totally symmetric for relaying information from a sidechain to the mainchain.
Posting Partial Cross-chain Updates
The Lisk protocol allows relayers to post cross-chain update transactions which do not contain all CCMs, as opposed to the mechanism explained in the previous section. This can be useful for example when the list of CCMs is too large to be included in a single block.
The cross-chain update transaction can contain an inboxUpdate
which does not contain all CCMs required to recompute the outbox root corresponding to the given state root. In that case, the relayer has to make sure that an appropriate messageWitness
is provided. This witness is constructed as a right witness as defined in LIP 0031.
If a cross-chain update was submitted without all the CCMs (as explained in the previous paragraph), then it is possible to provide those missing CCMs without the need to provide another certificate
or outboxRootWitness
(technically an empty certificate
and outboxRootWitness
are provided). The cross-chain update transaction contains only the missing CCMs and the potential messageWitness
.
Those options for partial cross-chain update transactions are not expected to be used regularly. It is however a good option in corner case events where the sidechain outbox suddenly becomes very large.
Malicious Cross-chain Update Transactions
A cross-chain update transaction may have been created with validly signed information according to the validity rules and hence be included in the blockchain. However, the transaction could include invalid CCMs. Those will be detected when trying to process the inboxUpdate
. If a CCM is invalid (as specified in the “Execute Cross-chain Updates” section), then the sending chain is terminated.
First Cross-chain Update from a Sidechain
The first cross-chain update from a given sidechain posted on mainchain has a special function. It will change the chain status from CHAIN_REGISTERED
to CHAIN_ACTIVE
. This change means that the sidechain is now available to receive cross-chain messages and can interact with the mainchain. Additionally, the sidechain must now follow the liveness condition and regularly post cross-chain updates (at least once a month). If the sidechains fails to follow the liveness condition, it is terminated on the mainchain.
When a sidechain is started and registered, the sidechain developers might decide to not activate the sidechain straight away (maybe to do further testing). It could happen then (intentionally or not) that an old block header (almost 30 days old) is submitted to the mainchain to activate the sidechain. This could result in the sidechain being punished for liveness failure very soon after the activation (maybe only a few minutes later). To prevent this issue (and without any significant drawbacks) the first cross-chain update to be submitted on mainchain must contain a certificate less that 15 days old. The sidechain has therefore at least 15 days to submit the next cross-chain update to the mainchain and start the regular posting of cross-chain updates.
Specification
The interoperability module supports two commands used to certify the state of another chain. Those commands have moduleID = MODULE_ID_INTEROPERABILITY
. One of them, meant to be posted on the mainchain, has commandID = COMMAND_ID_MAINCHAIN_CCU
, while the other, meant to be posted on sidechains, has commandID = COMMAND_ID_SIDECHAIN_CCU
.
Constants and Notations
The following constants are used throughout the document:
Name | Type | Value |
---|---|---|
Interoperability Constants | ||
MODULE_ID_INTEROPERABILITY |
uint32 | 64 |
STORE_PREFIX_CHAIN_DATA |
bytes | 0x8000 |
Interoperability Command and Cross-chain Command IDs | ||
COMMAND_ID_SIDECHAIN_CCU |
uint32 | 2 |
COMMAND_ID_MAINCHAIN_CCU |
uint32 | 3 |
CROSS_CHAIN_COMMAND_ID_CCU_RECEIPT |
uint32 | 1 |
Chain Status | ||
CHAIN_REGISTERED |
uint32 | 0 |
CHAIN_ACTIVE |
uint32 | 1 |
CHAIN_TERMINATED |
uint32 | 2 |
Message Tags | ||
MESSAGE_TAG_CERTIFICATE |
bytes | “LSK_CE_” ASCII-encoded |
Several of those constants are shared with the other LIPs defining the interoperability module and all of the needed constants for the interoperability module are defined in LIP “Properties, serialization, and initial values of the interoperability module”. That LIP should be considered correct if a value stated here differs.
uint32be
uint32be(x)
returns the big endian uint32 serialization of an integer x
, with 0 <= x < 2^32
.
This serialization is always 4 bytes long.
Parameters Schema
Both commands will use the following params
schema:
crossChainUpdateTransactionParams = {
"type": "object",
"properties": {
"sendingChainID": {
"dataType": uint32,
"fieldNumber": 1
},
"certificate": {
"dataType": bytes,
"fieldNumber": 2
},
"validatorUpdate": {
"type": object,
"fieldNumber": 3,
"properties":{
"keysUpdate": {
"type": "array",
"fieldNumber": 1,
"items": {
"dataType": "bytes"
}
},
"weightsUpdate": {
"type": "array",
"fieldNumber": 2,
"items": {
"dataType": "uint64"
}
},
"newCertificateThreshold": {
"dataType": "uint64",
"fieldNumber": 3,
}
},
"required":[
"keysUpdate",
"weightsUpdate",
"newCertificateThreshold"
]
},
"inboxUpdate": {
"type": "object",
"fieldNumber": 4,
"properties": {
"crossChainMessages": {
"type": "array",
"fieldNumber": 1,
"items": {
"dataType": "bytes"
}
},
"messageWitness": {
"type": "object",
"fieldNumber": 2,
"properties": {
"partnerChainOutboxSize":{
"dataType": "uint64",
"fieldNumber": 1
},
"siblingHashes":{
"type": "array",
"fieldNumber": 2,
"items": {
"dataType": "bytes"
}
}
}
},
"required": ["partnerChainOutboxSize", "siblingHashes"]
},
"outboxRootWitness": {
"type": "object",
"fieldNumber": 3,
"properties": {
"bitmap":{
"dataType": "bytes",
"fieldNumber": 1
},
"siblingHashes":{
"type": "array",
"fieldNumber": 2,
"items": {
"dataType": "bytes"
}
}
},
"required": ["bitmap", "siblingHashes"]
}
},
"required": [
"crossChainMessages",
"messageWitness",
"outboxRootWitness"
]
},
"required": [
"sendingChainID",
"certificate",
"validatorUpdate",
"inboxUpdate"
]
}
Parameters Validity
In the following, let sendingAccount
be the entry in the interoperability store with store prefix STORE_PREFIX_CHAIN_DATA
and store key uint32be(sendingChainID)
.
Liveness of Sending Chain
A CCU transaction is only valid if the sending chain is not terminated and follows the liveness rule. This is done by asserting the two points below:
-
sendingChain.status != CHAIN_TERMINATED
, - if
sendingChain.status == CHAIN_ACTIVE
then also validateisLive(sendingChainID,timestamp) == True
. TheisLive
function is specified in LIP “Properties, serialization, and initial values of the interoperability module”, andtimestamp
is the timestamp of the block including the CCU.
Liveness Requirement for the First CCU
If sendingChain.status == CHAIN_REGISTERED
, the proposed CCU must contain a non-empty certificate
which must follow the schema defined in LIP “Introduce a certificate generation mechanism”.
In the following, let certificate
be the deserialized certificate.
Furthermore, the certificate is only valid if it allows the sidechain account to remain live for a reasonable amount of time.
This is done by checking that
timestamp - CCU.params.certificate.timestamp < 15*24*3600
where timestamp
is the timestamp of the block including the CCU.
Certificate and Validator Update Validity
If params
contains a non-empty certificate
, it is valid if:
-
params.certificate
follows the schema defined in LIP “Introduce a certificate generation mechanism”.
Again, we writecertificate
for the deserialized certificate. -
certificate.height
is greater thansendingAccount.lastCertifiedHeight
. -
certificate.timestamp < timestamp
, where timestamp is the timestamp of the block including the CCU. -
certificate.signature
is a valid aggregate signature for thesendingAccount.validators
property of the cross-chain account. This is done by verifying that the function below defined in the LIP 0038 returnsVALID
.verifyWeightedAggSig( keysList = sendingAccount.validators.keys, aggregationBits. = certificate.aggregationBits, signature = certificate.signature, tag = MESSAGE_TAG_CERTIFICATE, networkIdentifier = sendingAccount.networkID, weights = sendingAccount.validators.weights, threshold = sendingAccount.validators.threshold, message = params.certificate )
If params
contains a non-empty validatorUpdate
property (with deserialized value not equal to {keysUpdate:[], weightsUpdate:[], newCertificateThreshold: 0}
),
it is valid if:
-
params
contains a non-emptycertificate
. -
validatorUpdate
has the correct format:-
keysUpdate
is an array of unique BLS public keys, hence all elements are 48 bytes long. -
weightsUpdate
is of the same length askeysUpdate
.
-
-
certificate.validatorsHash
is obtained as the SHA-256 digest of the updatedsendingAccount.validators
, see “Update Validators” section below, serialized according tovalidatorsSchema
defined in the LIP “New Block Header and Block Asset Schema” (and copied below).validatorsSchema = { "type": "object", "properties": { "keys": { "type": "array", "fieldNumber": 1, "items": { "dataType": "bytes" } }, "weights": { "type": "array", "fieldNumber": 2, "items": { "dataType": "uint64" } }, "certificateThreshold": { "dataType": uint64, "fieldNumber": 3 } }, "required" : [ "keys", "weights", "certificateThreshold" ] }
InboxUpdate Validity
If params
contains a non-empty certificate
and an inboxUpdate
, the validity of the latter is checked by:
- Let
newInboxRoot
,newInboxAppendPath
andnewInboxSize
be the resulting new root, append path and size of the Merkle tree that would be obtained if all messages fromcrossChainMessages
would be appended to thesendingAccount
inbox.
Note thatsendingAccount.inbox
is not updated here. - If
inboxUpdate
contains a non-emptymessageWitness
, then updatenewInboxRoot
to the output ofcalculateRootFromRightWitness(newInboxSize, newInboxAppendPath, inboxUpdate.messageWitness.siblingHashes)
as specified in LIP 0031. - Then validate the newly updated root against the certificate state root using the provided
outboxRootWitness
.
Using notation from LIP “Introduce sparse Merkle trees”, this is done via the functionverify(queryKeys, proof, certificate.stateRoot)
withqueryKeys = [outboxKey], proof = {siblingHashes: outboxRootWitness.siblingHashes, queries: [{ key: outboxKey, value: newInboxRoot, bitmap: outboxRootWitness.bitmap }], } outboxKey = MODULE_ID_INTEROPERABILITY || STORE_PREFIX_OUTBOX || SHA-256(uint32be(sendingChainID)).
If params
contains an empty certificate
and a non-empty inboxUpdate
, the validity of the latter is checked as follows:
- Let
newInboxRoot
,newInboxAppendPath
andnewInboxSize
be the resulting new root, append path and size of the Merkle tree that would be obtained if all messages fromcrossChainMessages
would be appended to thesendingAccount
inbox. Note thatsendingAccount.inbox
is not updated here. - If
inboxUpdate
contains amessageWitness
, then updatenewInboxRoot
to the output ofcalculateRootFromRightWitness(newInboxSize, newInboxAppendPath, inboxUpdate.messageWitness.siblingHashes)
as specified in LIP 0031. - Then validate that
newInboxRoot == sendingAccount.partnerChainOutboxRoot
.
Execute Cross-chain Updates
Cross-chain updates posted on the mainchain or sidechains follow a different execution logic, which we describe in the following two subsections, and a common one, described in the “Common Processing” section.
In the following, let CCU
be the cross-chain update transaction. Let partnerChainID = CCU.sendingChainID
and partnerChain
the entry in the interoperability store with store prefix STORE_PREFIX_ACCOUNT
and store key uint32be(partnerChainID)
.
Cross-chain Updates Posted on Mainchain
Cross-chain update transactions posted on mainchain are transactions with
-
moduleID = MODULE_ID_INTEROPERABILITY
, -
commandID = COMMAND_ID_MAINCHAIN_CCU
.
Then, the following is done in the given order:
- If
partnerChain.status == CHAIN_REGISTERED
, setpartnerChain.status = CHAIN_ACTIVE
- For every
CCM
ininboxUpdate.crossChainMessages
:- Validate that
params.sendingChainID == CCM.sendingChainID
. - Validate the format of
CCM
according to the function provided in LIP “Cross-chain messages”.
- Validate that
- Validate that the first CCM in
inboxUpdate.crossChainMessages
hasCCM.index == partnerChain.inbox.size
. - Validate that all CCMs in
inboxUpdate.crossChainMessages
have increasing and sequential index property. - Validate that the sum of all
CCM.fee
and all amounts for LSK cross-chain transfers is smaller or equal than the escrowed amount for the sending chain. The escrowed amount is obtained with the token functiongetEscrowAmount(params.sendingChainID,0)
. - If one of those validation points fails:
-
terminateChain(partnerChainID)
as specified in LIP “Properties, serialization, and initial values of the interoperability module”. - Exit the transaction processing, the CCU has no further effect.
-
- For every
CCM
ininboxUpdate.crossChainMessages
whereCCM.receivingChainID
corresponds to an active and live sidechain account:- transfer
CCM.fee
from the sending sidechain escrowed balance to the receiving sidechain escrowed balance.
This is done with the token functiontransferEscrow(CCM.sendingChainID, CCM.receivingChainID, 0, CCM.fee)
.
- transfer
- Continue the processing by executing all steps in the “Common Processing” section.
Cross-chain Updates Posted on Sidechains
Cross-chain update transaction posted on sidechains are transactions with
-
moduleID = MODULE_ID_INTEROPERABILITY
, -
commandID = COMMAND_ID_SIDECHAIN_CCU
.
To execute cross-chain updates, the following is done:
- If
partnerChain.status == CHAIN_REGISTERED
, setpartnerChain.status = CHAIN_ACTIVE
. - For every
CCM
ininboxUpdate.crossChainMessages
:- Validate that
ownChainID == CCM.receivingChainID
. - Validate the format of
CCM
according to the function provided in LIP “Cross-chain messages”.
- Validate that
- Validate that the first CCM in
inboxUpdate.crossChainMessages
hasCCM.index == partnerChain.inbox.size
. - Validate that all CCMs in
inboxUpdate.crossChainMessages
have increasing and sequential index property. - If one of those validation points fails:
-
terminateChain(partnerChainID)
as specified in LIP “Properties, serialization, and initial values of the interoperability module”. - Exit the transaction processing, the CCU has no further effect.
-
- Continue the processing by executing all steps in the “Common Processing” section.
Common Processing
For CCU transactions posted on the mainchain or on sidechains, once the specific execution steps described above have been completed, the following is done in the given order:
- For every
CCM
ininboxUpdate.crossChainMessages
withCCM.receivingChainID == ownChainID
:- Assign
CCM.fee
to the relayer, hererelayerAddress
is the address corresponding to the sender public key of the CCU. This is done with the token functionbeforeExecuteCCM(relayerAddress, CCM)
.
- Assign
- For every
CCM
ininboxUpdate.crossChainMessages
(respecting the order of the array):- Call
appendToInboxTree(partnerChainID, SHA-256(serializedMessage))
whereserializedMessage
is the serialized CCM according to the schema given in LIP “Cross-chain messages”. - Process
CCM
as detailed in LIP “Cross-chain messages”.
- Call
- Update
partnerChain.validators
according tovalidatorUpdate
, see “Update Validators” section. - Set
partnerChain.lastCertifiedStateRoot
tocertificate.stateRoot
. - Set
partnerChain.lastCertifiedTimestamp
tocertificate.timestamp
. - Set
partnerChain.lastCertifiedHeight
tocertificate.height
. - Set
partnerChain.partnerChainOutboxSize
to-
inboxUpdate.messageWitness.partnerChainOutboxSize
ifparams
contains a non-emptyinboxUpdate.messageWitness
. -
partnerChain.inbox.size
otherwise.
-
- Set
partnerChain.partnerChainOutboxRoot
to-
calculateRootRightWitness(inbox.size, inbox.appendPath, inboxUpdate.messageWitness.siblingHashes)
ifparams
contains a non-emptyinboxUpdate.messageWitness
. -
partnerChain.inbox.root
otherwise.
-
- Append a cross-chain update receipt to the partner chain outbox by calling
addToOutobx(partnerChain, CCUR)
withCCUR = createCrossChainMessage( moduleID = MODULE_ID_INTEROPERABILITY, crossChainCommandID = CROSS_CHAIN_COMMAND_ID_CCU_RECEIPT, receivingChainID = CCU.params.sendingChainID, fee = 0, params = { paidFee = CCU.fee, relayerPublicKey = CCU.senderPublicKey, partnerChainInboxSize = partnerChain.inbox.size } )
Update Validators
Updating sendingAccount.validators
with respect to a given validatorUpdate
is done following the points below:
- Update the weight of all public keys present in
keysUpdate
with the corresponding weight specified inweightsUpdate
(elements inkeysUpdate
array correspond to weights with the same index inweightsUpdate
). If the key was not present insendingAccount.validators
before the update, it is added to it. Keys are always maintained in lexicographical order. - Remove all keys which have now weight
0
fromsendingAccount.validators.keys
, and remove the corresponding0
insendingAccount.validators.weights
. - Set
sendingAccount.validators.threshold
=validatorUpdate.newCertificateThreshold
.
Backwards Compatibility
This proposal, together with LIP “Chain registration”, LIP “Cross-chain messages”, and LIP “Sidechain recovery transactions”, is part of the interoperability module.
Chains adding this module will need to do so with a hard fork.
Appendix
Computing the Validator Update
When posting a CCU transaction, the validator root given in the certificate certifies the new set of validators of the sending chain. The CCU must therefore include the difference between the validators currently stored in the chain account and the validator set authenticated by the certificate.
getValidatorDiff((keys, weights, threshold),
(newKeys, newWeights, newCertificateThreshold)):
keysDiff = []
weightDiff = []
for i from 0 to length(newKeys)-1:
if there exist j in [0,length(keys)] such that
(newKeys[i],newWeights[i]) == (keys[j],weights[j]):
continue
else:
append newKeys[i] to keysDiff
append newWeights[i] to weightDiff
for i from 0 to length(keys)-1:
if there exist j in [0,length(newKeys)] such that newKeys[j] == keys[i]:
continue
else:
append keys[i] to keysDiff
append 0 to weightDiff
return (keysDiff, weightsDiff, newCertificateThreshold)