Sidechain recovery transactions

Hello everyone,

I would like to propose another LIP for the roadmap objective "Define sidechain registration and lifecycle”. This LIP specifies the message, token and NFT recovery mechanisms.

I’m looking forward to your feedback.

Here is the complete LIP draft:

LIP:
Title: Sidechain recovery transactions
Author: Iker Alustiza <iker@lightcurve.io>
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: Introduce an interoperable token modulee LIP, 
                 Introduce a non-fungible token module module LIP, 
                 Properties, serialization, and initial values of the interoperability module LIP, 
                 Cross-chain messages LIP, State model and state root LIP

Abstract

This LIP introduces three new transactions to the Lisk ecosystem, the message recovery transaction, the token recovery transaction and the NFT recovery transaction. The first one allows users to recover a cross-chain message that is pending in the outbox of an inactive or terminated sidechain. The second one is used to recover the balance of a token from an inactive or terminated sidechain whereas the latter allows to recover NFTs.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

In the Lisk ecosystem, the ability of a sidechain to interoperate with other chains can be revoked, i.e., terminated, permanently. Specifically, this occurs when the sidechain has been inactive for too long, i.e., not posting a cross-chain update (CCU) transaction for more than a month, or if it posted a malicious CCU transaction on the mainchain. Once a sidechain is terminated in the ecosystem, the users of said chain cannot have any cross-chain interaction with it. This means they will no longer be able to send or receive any (fungible or non-fungible) token or message from or to the sidechain.
Therefore, it is useful to provide a trustless on-chain mechanism to recover tokens or messages from terminated sidechains. This mechanism will noticeably improve the user experience of the Lisk ecosystem without affecting the security guarantees of the general interoperability solution.

Rationale

This LIP introduces three transactions to the Lisk ecosystem, the message recovery transaction, the token recovery transaction and the NFT recovery transaction, to provide a recovery mechanism for sidechain users in the scenario stated in the previous section. These transactions are part of the Lisk interoperability module, thus they make use of the information provided in the interoperability store of the terminated sidechain. Each of these transactions allows a different way for users to recover their tokens or messages.

  • The users can recover a pending cross-chain message (CCM) from the sidechain account outbox by submitting a message recovery transaction on the Lisk mainchain.
  • They can recover their tokens from the sidechain state by submitting a token recovery transaction on the Lisk mainchain.
  • They can recover their NFTs from the sidechain state by submitting a NFT recovery transaction on the Lisk mainchain

In the next subsections, these mechanisms are explained together with their conditions, sidechain data availability requirements, effects, and their potential usage by certain network participants.

Message Recovery from the Sidechain Account Outbox

This mechanism allows to recover any CCM pending in the sidechain outbox. That is, those CCMs that have not been included in the receiving sidechain yet. Specifically, this includes all the CCMs whose indices are larger than the last message index that the receiving sidechain reported to be acted in its inbox on the mainchain. This recovery mechanism requires these conditions to work:

  • The pending CCMs to be recovered have to be available to the sender of the recovery transaction.
  • The indices of the pending CCMs to be recovered have to be larger than the value of the partnerChainInboxSize property of the interoperability account of the sidechain. This implies that these CCMs are still pending or that their processing has not been certified to the mainchain.
  • The proof of inclusion for the pending CCMs into the current outbox.root has to be available. When a message recovery transaction is processed, the outbox.root property of the interoperability account of the corresponding sidechain is updated to account for the recovered CCMs (see Figure 1). This implies that the future potential message recovery transactions have to include a proof of inclusion into the updated Merkle tree against the new outbox.root.

Figure 1: (top) The message recovery transaction, trs, recovers CCM1, CCM3 and CCM5 by providing the siblingHashes to compute the outbox root (the proof of inclusion for these CCMs in the tree). The data provided by trs is highlighted in red in the tree. The outbox root is then updated by recomputing the Merkle tree root with the recovered CCMs.
(bottom) In the second Merkle tree the updated nodes are highlighted in green. A new recovery transaction will need to provide a proof of inclusion for this updated Merkle tree.

Assuming these conditions are fulfilled, any user can submit a message recovery transaction to recover several CCMs at the same time. When the transaction is processed, the corresponding CCMs are recovered differently depending on their sending chain:

  • If the sending chain of the pending CCM is the Lisk mainchain, it must be a cross-chain LSK token transfer CCM. The amount of LSK transferred in the CCM will be added back to the sender of the original transaction.
  • If the sending chain of the pending CCM is any other sidechain, the CCM will be sent back to this chain. The sending sidechain will act on the CCM as usual, i,e., with respect to the specific logic associated with the CCM asset.

Bear in mind that users are not guaranteed to recover their CCMs in every situation.
Certain state information of the terminated sidechain might have been modified before termination and this would make the recovered CCM application fail. For example, the escrowed LSK in the sidechain account on the mainchain could have been subtracted by prior malicious behavior in the terminated sidechain.

Token and NFT Recoveries from the Sidechain State Root

The mechanisms to recover tokens or NFTs from the user account on the sidechain are analogous.
Both are based on the sidechain state root, stateRoot, set in the last certificate before sidechain termination. These two recovery mechanisms require these 3 conditions to be valid:

  • The state of the sidechain has to be consistent with respect to the value of the stateRoot property in the interoperability account of the sidechain in the mainchain.
  • The user token/NFT store for the specific token/NFT to be recovered has to be available.
  • The proof of inclusion for the user token/NFT store to be recovered into the current stateRoot has to be available. When one of these transactions is processed, the stateRoot property of the interoperability account of the corresponding sidechain is updated to account for the recovered tokens. This implies that the future potential token/NFT recovery transactions have to include a proof of inclusion into the updated sparse Merkle tree against the new stateRoot.

Assuming these conditions are fulfilled, the balance for a specific token or a specific NFT in the user account can be recovered from a terminated sidechain. In the case of a token recovery transaction, cross-chain token transfer messages will be created on the Lisk mainchain sending back the corresponding token balance to its native chain. For NFT recovery transactions, it will happen analogously with cross-chain NFT transfer messages.

Similar to the case for message recovery transactions, users are not guaranteed to recover their tokens and NFTs in every situation. Certain state information of the terminated sidechain might have been modified before termination and this would fail the recovery process.

In summary, the functionality provided by these recovery transactions applies for sidechains that were terminated for inactivity or other violations of the interoperability protocol. If the validators of the terminated sidechain were byzantine in the past, i.e., the security guarantees of the sidechain were broken, it is likely that these recovery mechanisms would not work.

Recovery Transactions as an Off-chain Service

As explained in the previous subsections, these recovery transactions require specific information from the terminated sidechain to be available. In particular, for the message recovery mechanism, the entire sidechain outbox Merkle tree has to be available, or alternatively, reconstructed from the mainchain history. For the token and NFT recovery mechanisms, the sidechain state up to the last valid cross-chain update has to be available.
Moreover, this information has to be updated for future recovery transactions every time a recovery transaction is successfully processed.

In particular, message recovery transactions are better suited to be submitted by accounts with access to a Lisk mainchain full node. The complete Merkle tree with root equal to the last value of the outbox.root property of the sidechain account can be computed from the history of the Lisk mainchain. In the case of submitting token or NFT recovery transactions, a full node of the sidechain should also keep a snapshot of the sidechain state tree corresponding to the last certified stateRoot on mainchain.
As explained above, these transactions require the state of the sidechain to be consistent with the last value of stateRoot. However, the state of the sidechain may have evolved since the last CCU. That is why if a sidechain node intends to be ready to eventually submit these transactions, they need to store this extra state information.

Since these technical requirements are not straightforward, the three recovery transactions are better suited to be offered as an off-chain service to sidechain users. When a sidechain is terminated, these recovery-service providers can recover the CCMs, tokens or NFTs for the interested users.

Specification

Constants

Name Type Value
Module
MODULE_ID_INTEROPERABILITY uint32 64
MODULE_ID_TOKEN uint32 TBD
MODULE_ID_NFT uint32 TBD
Storage Prefix
STORE_PREFIX_ACCOUNT bytes 0x8000
STORE_PREFIX_USER bytes 0x0000
Status
CHAIN_TERMINATED uint32 2
CCM_STATUS_OK uint32 0
CCM_STATUS_RECOVERED uint32 4
Asset ID
ASSET_ID_MESSAGE_RECOVERY uint32 4
ASSET_ID_TOKEN_RECOVERY uint32 5
ASSET_ID_NFT_RECOVERY uint32 6
ASSET_ID_CCM_CROSS_CHAIN_TRANSFER uint32 2
ASSET_ID_CCM_CROSS_CHAIN_NFT_TRANSFER uint32 2
Other
MAINCHAIN_ID uint32 1
EMPTY_HASH bytes SHA-256("")

This LIP specifies three transactions for Lisk mainchain. These transactions are part of the interoperability module, with moduleID = MODULE_ID_INTEROPERABILITY.

General Notation

In the rest of the section:

Message Recovery Transaction

The assetID of this transaction is ASSET_ID_MESSAGE_RECOVERY.

  • asset:
    • chainID: An integer representing the chain ID of the terminated sidechain.
    • crossChainMessages: An array of serialized CCMs, according to the schema specified in Cross-chain messages LIP, to be recovered.
    • siblingHashes: Array of bytes with the paths in the Merkle tree for the proofs of inclusion of crossChainMessages in the outbox root of the sidechain as specified in LIP 0031.

Message Recovery Transaction Asset Schema

messageRecoveryAsset = {
   "type":"object",
   "properties":{
      "chainID":{
         "dataType":"uint32",
         "fieldNumber":1
      },
      "crossChainMessages":{
         "type":"array",
         "items":{
            "dataType":"bytes"
         },
         "fieldNumber":2
      },
      "siblingHashes":{
         "type":"array",
         "items":{
            "dataType":"bytes"
         },
         "fieldNumber":3
      }
   },
   "required":[
      "chainID",
      "crossChainMessages",
      "siblingHashes"
   ]
}

Message Recovery Transaction Validation

Let trs be the message recovery transaction to be validated and deserializedCCMs be an array with the deserialization of every element in trs.asset.crossChainMessages according to the schema specified in Cross-chain messages LIP. Then trs is valid if the following logic returns true:

if trs.asset.chainID does not correspond to a registered sidechain:
	return false
let sidechainAccount = account(trs.asset.chainID)

# chain has to be either terminated or inactive
if sidechainAccount.status != CHAIN_TERMINATED and isLive(trs.asset.chainID, timestamp):
	return false

# check the validity of the CCMs to be recovered
for CCM in deserializedCCMs:
	if CCM.index < sidechainAccount.partnerChainInboxSize:
		return false
	if CCM.status != CCM_STATUS_OK:
		return false

# check the inclusion proof against the sidechain outbox root
let proof = {size: sidechainAccount.outbox.size, 
	     idxs: [CCM.index for CCM in deserializedCCMs], 
	     siblingHashes: trs.asset.siblingHashes}

return RMTVerify([SHA-256(CCMData) for CCMData in trs.asset.crossChainMessages], 
		 proof, 
		 sidechainAccount.outbox.root)

Message Recovery Transaction Application

Processing a valid message recovery transaction trs implies the following logic:

let trsSenderAddress be the address of the trs.senderPublicKey
let sidechainAccount = account(trs.asset.chainID)

# terminate chain if necessary
if sidechainAccount.status != CHAIN_TERMINATED:
	terminateChain(trs.asset.chainID)

# set CCM status to recovered and assign fee to trs sender
updatedCCMs = []
for CCM in deserializedCCMs:
	unescrow(trs.asset.chainID, trsSenderAddress, 0, CCM.fee)
	set CCM.fee = 0
	set CCM.status = CCM_STATUS_RECOVERED
	push serialized(CCM) to updatedCCMs # CCM is serialized again

# update sidechain outbox root
let proof = {size: sidechainAccount.outbox.size,
	     idxs: [CCM.index for CCM in deserializedCCMs],
	     siblingHashes: trs.asset.siblingHashes}

sidechainAccount.outbox.root = RMTCalculateRoot([SHA-256(CCMData) for CCMData in updatedCCMs], proof)

# process recovery
for CCM in deserializedCCMs:
	if CCM.sendingChainID == MAINCHAIN_ID:
		# this is a LSK transfer CCM
		unescrow(trs.asset.chainID, CCM.asset.senderAddress, 0, CCM.asset.amount)
	else:
		if CCM.moduleID == MODULE_ID_TOKEN
		and CCM.sendingChainID != MAINCHAIN_ID
		and CCM.asset.tokenChainID == 1
		and CCM.asset.tokenLocalID == 0: 
			# transfer LSK between escrow accounts
			transferEscrow(CCM.receivingChainID,
				       CCM.sendingChainID, 
				       0, 
				       CCM.asset.amount)

        swap CCM.sendingChainID and CCM.receivingChainID
        process(CCM)

Token Recovery Transaction

The assetID of this transaction is ASSET_ID_TOKEN_RECOVERY.

  • asset:
    • chainID: An integer representing the chain ID of the terminated sidechain.
    • tokenStores: An array of objects containing:
      • storageKey: An object with the following properties:
        • userAddress: A byte array with the address of the user owning the tokens to be recovered.
        • nativeChainID: An integer indicating the ID of the native chain of the tokens to be recovered.
        • localID: An integer with the ID indicating the local ID of the tokens to be recovered.
      • storageValue: The token stores, serialized as specified in Introduce an interoperable token module LIP.
      • bitmap: The bitmap corresponding to storageValue in the sparse Merkle tree as specified in Introduce sparse Merkle trees LIP.
    • siblingHashes: Array of bytes with the sibling hashes in the sparse Merkle tree for the inclusion proofs of tokenStores in the stateRoot of the sidechain.

Token Recovery Transaction Asset Schema

tokenRecoveryAsset = {
   "type":"object",
   "properties":{
      "chainID":{
         "dataType":"uint32",
         "fieldNumber":1
      },
      "tokenStores":{
         "type":"array",
         "items":{
            "type":"object",
            "fieldNumber":2,
            "properties":{
               "storageKey":{
                  "type":"object",
                  "fieldNumber":1,
                  "properties":{
                     "userAddress":{
                        "dataType":"bytes",
                        "fieldNumber":1
                     },
                     "nativeChainID":{
                        "dataType":"uint32",
                        "fieldNumber":2
                     },
                     "localID":{
                        "dataType":"uint32",
                        "fieldNumber":3
                     }
                  },
                  "required":[
                     "userAddress",
                     "nativeChainID",
                     "localID"
                  ]
               },
               "storageValue":{
                  "dataType":"bytes",
                  "fieldNumber":2
               },
               "bitmap":{
                  "dataType":"bytes",
                  "fieldNumber":3
               }
            },
            "required":[
               "storageKey",
               "storageValue",
               "bitmap"
            ]
         }
      },
      "siblingHashes":{
         "type":"array",
         "items":{
            "dataType":"bytes"
         },
         "fieldNumber":3
      }
   },
   "required":[
      "chainID",
      "tokenStores",
      "siblingHashes"
   ]
}

Token Recovery Transaction Validation

Let trs be the token recovery transaction to be validated. Then trs is valid if the following logic returns true:

if trs.asset.chainID does not correspond to a registered sidechain:
	return false
  
let sidechainAccount = account(trs.asset.chainID)

# chain has to be either terminated or inactive
if sidechainAccount.status != CHAIN_TERMINATED and isLive(trs.asset.chainID, timestamp):
	return false

let tokenQueries and queryKeys be empty arrays

for each token in trs.asset.tokenStores:
	if length(token.storageKey.userAddress) != 20:
		return false

	if token.storageKey.nativeChainID == trs.asset.chainID:
		return false

  	queryKey = uint32be(MODULE_ID_TOKEN) || STORE_PREFIX_USER || SHA-256(token.storageKey.userAddress || 
  	uint32be(token.storageKey.nativeChainID) || uint32be(token.storageKey.localID))

  	push queryKey to queryKeys
  	query = {key: queryKey, 
		 value: SHA-256(token.storageValue), 
	   	 bitmap: token.bitmap}
  	push query to tokenQueries

proofOfInclusionTokens = {siblingHashes: trs.asset.siblingHashes, queries: tokenQueries}

return SMTVerify(queryKeys, proofOfInclusionTokens, sidechainAccount.stateRoot)

Token Recovery Transaction Application

Processing a valid token recovery transaction trs implies the following logic:

let sidechainAccount = account(trs.asset.chainID)

# terminate chain if necessary
if sidechainAccount.status != CHAIN_TERMINATED:
	terminateChain(trs.asset.chainID)

let tokenQueries be an empty array

for each token in trs.asset.tokenStores:
	let deserializedToken be the deserialized token.storageValue

	let totalBalance = deserializedToken.availableBalance
	for each lockedToken in deserializedToken.lockedBalances
		totalBalance += lockedToken.amount

	if token.storageKey.nativeChainID == MAINCHAIN_ID:
		# this is a LSK token store 
		unescrow(trs.asset.chainID, token.storageKey.userAddress, 0, totalBalance)
	else:
		create a cross-chain token transfer message recoveredTokenCCM as
		
		recoveredTokenCCM = {
			"moduleID": MODULE_ID_TOKEN,
			"assetID": ASSET_ID_CCM_CROSS_CHAIN_TRANSFER,
			"index": 0,
			"originalIndex": 0,
			"sendingChainID": trs.asset.chainID,
			"receivingChainID": token.storageKey.nativeChainID,
			"fee": 0,
			"status": CCM_STATUS_RECOVERED,
			"asset":{
			"tokenChainID": token.storageKey.nativeChainID,
			"tokenLocalID": token.storageKey.localID,
			"amount": totalBalance,
			"senderAddress": token.storageKey.userAddress,
			"recipientAddress": token.storageKey.userAddress,
			"data": "",
			}
		}
		
    		process(recoveredTokenCCM)

	key = uint32be(MODULE_ID_TOKEN) || STORE_PREFIX_USER || SHA-256(token.storageKey.userAddress ||
	uint32be(token.storageKey.nativeChainID) || uint32be(token.storageKey.localID))

	emptyTokenStore = 0x 0800 # define an empty token store
	query = {key: key, 
		 value: SHA-256(emptyTokenStore), 
		 bitmap: token.bitmap}
	push query to tokenQueries

sidechainAccount.stateRoot = SMTCalculateRoot(trs.asset.siblingHashes, tokenQueries)

NFT Recovery Transaction

The assetID of this transaction is ASSET_ID_NFT_RECOVERY.

  • asset:
    • chainID: An integer representing the chain ID of the terminated sidechain.
    • NFTStores: An array of objects containing:
      • storageKey: An object with the following properties:
        • nativeChainID: An integer with the ID of the native chain of the NFTs to be recovered.
        • collection: An integer with the collection of the NFT to be recovered.
        • index: An integer with the index of the specific NFT inside the collection.
      • storageValue: The NFT stores, serialized as specified in Introduce a non-fungible token module LIP, with the tokens to be recovered.
      • bitmap: The bitmap corresponding to storageValue in the sparse Merkle tree as specified in Introduce sparse Merkle tree LIP.
    • siblingHashes: Array of bytes with the sibling hashes in the sparse Merkle tree for the proofs of inclusion of NFTStores in the stateRoot of the sidechain.

NFT Recovery Transaction Asset Schema

NFTRecoveryAsset = {
   "type":"object",
   "properties":{
      "chainID":{
         "dataType":"uint32",
         "fieldNumber":1
      },
      "NFTStores":{
         "type":"array",
         "items":{
            "type":"object",
            "fieldNumber":2,
            "properties":{
               "storageKey":{
                  "type":"object",
                  "fieldNumber":1,
                  "properties":{
                     "nativeChainID":{
                        "dataType":"uint32",
                        "fieldNumber":1
                     },
                     "collection":{
                        "dataType":"uint32",
                        "fieldNumber":2
                     },
                     "index":{
                        "dataType":"uint64",
                        "fieldNumber":3
                     }
                  },
                  "required":[
                     "nativeChainID",
                     "collection",
                     "index"
                  ]
               },
               "storageValue":{
                  "dataType":"bytes",
                  "fieldNumber":2
               },
               "bitmap":{
                  "dataType":"bytes",
                  "fieldNumber":3
               }
            },
            "required":[
               "storageKey",
               "storageValue",
               "bitmap"
            ]
         }
      },
      "siblingHashes":{
         "type":"array",
         "items":{
            "dataType":"bytes"
         },
         "fieldNumber":3
      }
   },
   "required":[
      "chainID",
      "NFTStores",
      "siblingHashes"
   ]
}

NFT Recovery Transaction Validation

Let trs be the token recovery transaction to be validated. Then trs is valid if the following logic returns true:

if trs.asset.chainID does not correspond to a registered sidechain:
	return false

let sidechainAccount = account(trs.asset.chainID)

# chain has to be either terminated or inactive
if sidechainAccount.status != CHAIN_TERMINATED and isLive(trs.asset.chainID, timestamp):
	return false

let NFTQueries and queryKeys be empty arrays

for each NFT in trs.asset.NFTStores:

	if NFT.storageKey.nativeChainID == trs.asset.chainID:
		return false

	if NFT.storageValue == EMPTY_HASH:
		return false

	
  	queryKey = uint32be(MODULE_ID_NFT) || STORE_PREFIX_USER || SHA256(uint32be(NFT.storageKey.nativeChainID) || 
  	uint32be(NFT.storageKey.collection) || uint32be(NFT.storageKey.index)) 

  	push queryKey to queryKeys
  	query = {key: queryKey,
	   	 value: SHA-256(NFT.storageValue), 
	   	 bitmap: NFT.bitmap}
  	push query to NFTQueries

proofOfInclusionNFTs = {siblingHashes: trs.asset.siblingHashes, queries = NFTQueries}

return SMTVerify(queryKeys, proofOfInclusionNFTs, sidechainAccount.stateRoot)

NFT Recovery Transaction Application

Processing a valid NFT recovery transaction trs implies the following logic:

let sidechainAccount = account(trs.asset.chainID)

# terminate chain if necessary
if sidechainAccount.status != CHAIN_TERMINATED:
	terminateChain(trs.asset.chainID)

let NFTQueries be an empty array

for each NFT in trs.asset.NFTStores:
	let deserializedNFT be the deserialized NFT.storageValue

	create a cross-chain token transfer message recoveredNFTCCM as

	recoveredNFTCCM = {
		"moduleID": MODULE_ID_NFT,
		"assetID": ASSET_ID_CCM_CROSS_CHAIN_NFT_TRANSFER,
		"index": 0,
		"originalIndex": 0,
		"sendingChainID": trs.asset.chainID,
		"receivingChainID": NFT.storageKey.nativeChainID,
		"fee": 0,
		"status": CCM_STATUS_RECOVERED,
		"asset":{
		"chainID": NFT.storageKey.nativeChainID,
		"collection": NFT.storageKey.collection,
		"index": NFT.storageKey.index,
		"attributes": deserializedNFT.attributes,
		"senderAddress": deserializedNFT.owner,
		"recipientAddress": deserializedNFT.owner,
		}
	}

	process(recoveredNFTCCM)

	key = uint32be(MODULE_ID_NFT) || STORE_PREFIX_USER || SHA-256(uint32be(NFT.storageKey.nativeChainID) || 
	uint32be(NFT.storageKey.collection) || uint32be(NFT.storageKey.index)) 

	query = {key: key, 
		 value: EMPTY_HASH, 
		 bitmap: NFT.bitmap}
	push query to NFTQueries

sidechainAccount.stateRoot = SMTcalculateRoot(trs.asset.siblingHashes, NFTQueries)

Backwards Compatibility

This LIP introduces new transactions with new effects to the Lisk mainchain state, thus it will imply a hardfork. It also assumes that the sidechains implement the token module, the NFT module and the interoperability module and follows the standard state model structure.

1 Like