SEPoW: Secure and Efficient Proof of Work Sidechains

Abstract

Since the advent of sidechains in 2014, they have been acknowledged as the key enabler of blockchain interoperability and upgradability. However, sidechains suffer from significant challenges such as centralization, inefficiency and insecurity, meaning that they are rarely used in practice. In this paper, we present SEPoW, a secure and efficient sidechains construction that is suitable for proof of work (PoW) sidechain systems. The drawbacks for the centralized exchange of cross-chain assets in the participating blockchains are overcome by our decentralized SEPoW. To reduce the size of a cross-chain proof, we introduce merged mining into our SEPoW such that the proof consists of two Merkle tree paths regardless of the size of the current blockchain. We prove that the proposed SEPoW achieves the desirable security properties that a secure sidechains construction should have. As an exemplary concrete instantiation we propose SEPoW for a PoW blockchain system consistent with Bitcoin. We evaluate the size of SEPoW proof and compare it with the state-of-the-art PoW sidechains protocols. Results demonstrate that SEPoW achieves a proof size of 416 bytes which is roughly 123$\times$, 510$\times$ and 62000$\times$ smaller than zkRelay proof, PoW sidechains proof and BTCRelay proof, respectively.

1 Introduction

Since blockchain technology was introduced by Satoshi [1] in 2008, various blockchains with different characteristics and their applications have been gaining increasing attention and adoption by communities. However, blockchains suffer from several fundamental open questions [2], as organized below: (i) Interoperability: How can assets or other data be interoperated and transferred among different blockchains? (ii) Upgradability: How can a new functionality and an implementation problem, e.g., smart contract and transaction malleability [3], be supported and corrected in a deployed blockchain?

Fortunately, a major approach to overcoming the above-raised questions is to use sidechains [4], which are a technology that can allow different blockchains to communicate with each other and react to events taking place in the other as desired. At present, sidechains have two forms. The former is parallel chains. This means that any two chains, for example, Bitcoin [1] and Ethereum [5], are treated as equals; any of them can be the sidechain of the other. The latter is parent-child chains. In this case, a sidechain can be a “child” of a parent chain; the child chain is somehow bootstrapped from the parent chain.

There are, however, concerns regarding the deficiency of security and efficiency in existing constructions for proof of work sidechains [2, 4, 6,7,8,9,10,11,12,13], which are explained as below:

• Some existing constructions for sidechains are highly centralized making them resistant to change, vulnerable to attacks and failures [14,15,16]. For example, trusted intermediaries on the involved blockchains are responsible for maintaining and managing the exchange of cross-chain assets, which will inevitably lead to a single-point-failure. Moreover, centralized constructions cast a major contradiction to the decentralized nature of blockchain.

• Cross-chain proof used for testifying the validity of cross-chain assets, consisting of a list of block headers that increases linearly with the size of the entire blockchain as well as a cryptographic proof, is fairly large, which reduces the efficiency of the constructions and limits potential scalability development.

• About security properties, many constructions for sidechains lack formal definition and rigorous proof. The security of cross-chain assets transfer can not be guaranteed. Even worse, when a sidechain is corrupted, another sidechain is unable to avoid the damage caused by that compromised sidechain.

Those challenges motivate our work.

1.1 Our Contributions

We present SEPoW, a secure and efficient construction that is suitable for proof of work sidechain systems, to complement deficiencies in the security and efficiency in existing constructions for proof of work sidechains.

In this work, we show that our SEPoW is decentralized and allows bidirectional communication between proof of work blockchains without trusted intermediaries. This means that the exchange of all cross-chain assets is managed not by a centralized party but by all honest nodes in participating blockchains.

To reduce the size of a cross-chain proof, we introduce the merged mining mechanism into our SEPoW such that a public chain of block headers is shared by the participating blockchains. Exploiting this, the proof consists of two Merkle tree paths: a transaction Merkle tree path and a merged Merkle tree path; their sizes depend on the number of transactions included in a block and the number of participating blockchains, respectively, regardless of the size of the current blockchain.

Next, we prove the security of SEPoW using a secure cross-chain proof protocol and a collision resistant hash function. Our SEPoW captures: (i) cross-chain assets can be transferred securely when the security assumptions of the participating blockchains are held, namely that an honest majority of computational power exists in the participating blockchains, and (ii) the firewall property maintained by SEPoW guarantees that any catastrophic blockchain corruption, such as a violation of the blockchain security assumptions, does not impact other blockchains.

Further, we present a concrete exemplary construction for proof of work sidechains. For conciseness our SEPoW is outlined with regard to a generic proof of work (PoW) blockchain consistent with the Bitcoin protocol [1] that underlies the Bitcoin blockchain, which is the most popular PoW blockchain so far.

We also evaluate the size of SEPoW proof and compare it with the state-of-the-art PoW sidechains protocols. Results demonstrate that SEPoW achieves a proof size of 416 bytes which is roughly 123x, 510x and 62000x smaller than zkRelay proof [12], PoW sidechains proof [7, 17] and BTCRelay proof [6] for the blockchain length of 300000 and a 1 MBytes block.

1.2 Organization

The rest of this paper is organized as follows. In Sect. 2, preliminaries of SEPoW are introduced. We provide an exemplary concrete construction for proof of work sidechains in Sect. 3. The security of SEPoW and the discussion of merged mining are proved and presented in Sect. 4 and Sect. 5, respectively. In Sect. 6, we evaluate the size of SEPoW proof and compare it with the state-of-the-art work. Related works are proposed in Sect. 7. We conclude this paper in the last section.

2 Preliminaries

2.1 Cross-Chain Proof Protocol

We introduce a cross-chain proof protocol [17] that attests to the validity of cross-chain transactions into SEPoW. In this protocol the prover is a miner or full node on a chain denoted by $\mathcal {C}_{1}$; the verifier does not have access to $\mathcal {C}_{1}$, but holds a list of block headers on the chain denoted by $\mathcal {C}_{2}$ he/she participates in. The prover wants to convince the verifier that the predicate (i.e., the transaction tx is confirmed in $\mathcal {C}_{1}$) is true by sending a valid proof.

The definition of a cross-chain proof protocol is given below.

Definition 1 (Cross-chain proof protocol)

A cross-chain proof protocol for a predicate q (i.e., an event occurred on blockchain) is a pair of probabilistic polynomial time (PPT) algorithms (P, V) such that:

• P. The algorithm takes as input a full chain $\mathcal {C}$, and outputs proof $\pi$ about the predicate q. We note this as $\pi$ $\leftarrow$ P $(\mathcal {C})$.

• V. The algorithm takes as input a proof $\pi$ produced by an honest node or a malicious node, and outputs a decision d $\in \{T, F\}.$ We note this as d $\leftarrow$ V $(\pi )$. The predicate q is true if V$(\pi )$ = T and false otherwise.

A desired security property of a cross-chain proof protocol is shown as follows.

Definition 2 (Security)

A cross-chain proof protocol for a predicate q is secure if for all environments and for all PPT adversaries $\mathcal {A}$ and for all rounds $r \ge \eta k,$ if V receives a set of proofs $\varPi$ at the beginning of round r,  at least one of which has been generated by the honest prover $\mathcal {P},$ then the output of V at the end of round r has the following constraints:

• If the output of V is false, then the evaluation of q for all honest nodes must be false at the end of round $r-\eta k$.

• If the output of V is true, then the evaluation of q for all honest nodes must be true at the end of round $r+\eta k$.

Note that the parameter $\eta$ represents the rate at which new blocks are produced and k is the number of subsequent blocks. See more details in [17].

2.2 Merged Mining

To generate a succinct cross-chain proof for a predicate, we introduce a merged mining mechanism [18, 19] that allows a miner to produce multiple blocks at different chains with a single PoW solution. Exploiting this, a public chain of block headers, produced and maintained by the miners running the merged mining, is shared by the participating sidechains. Thus, the proof is only two Merkle tree paths: a transaction Merkle tree path and a merged Merkle tree path. As an exemplary concrete instantiation, in Sect. 3.1.4 we describe how a merged mining mechanism is useful for generating a succinct proof for a predicate.

Miners are allowed to perform merged mining for all involved sidechains based on their mining power. The process of the merged mining is as follows.

• Step 1 (Build merged-block-header). Miners will verify transactions for all involved c sidechains (an efficient way that verifies all transactions without monitoring all sidechains is given in Sect. 5) and collect c transaction Merkle tree root $r_i$, i.e., part C in Fig. 1a. Then, the miners calculate the root mr (part B in Fig. 1a) of the merged Merkle tree over the leaves encoded from the following txroots:

  $$\begin{aligned} (r_1, r_2,..., r_{c}). \end{aligned}$$

  (1)

  Fig. 1.

  

  The construction of a merged-block (a) and a mining facility (b).

• Step 2 (Search for nonce). Without merged mining, similar to Bitcoin, miners are required to search for n nonce ne that each satisfies

  $$\begin{aligned} {\text {H}}(pub, r, ne) \le {\text {T}}. \end{aligned}$$

  (2)

  Where pub denotes public block parameters described in part A in Fig. 1a. With merged mining, miners only need to search for a nonce ne that satisfies

  $$\begin{aligned} {\text {H}}(pub, mr, ne) \le {\text {T}}. \end{aligned}$$

  (3)

  Here we assume the difficulty target T is the same for all involved sidechains.

• Step 3 (Diffuse block). Upon finding a valid ne, the miner will compose sidechain-specific merged-blocks and send them to corresponding sidechain networks, as described in Fig. 1b. It is worth pointing out that a merged-block-header is shared by these merged-blocks. As shown in Fig. 1b, for each sidechain, a merged-block includes a merged-block-header and a merged-block-body. A merged Merkle tree path p connecting r to mr is used to verify whether r is tied in the corresponding merged-block-header.

• Step 4 (Extend blockchain). In each sidechain, miners and full nodes verify the merged-block according to the specification of a block. Then the sidechain-specific merged-block will be appended in the corresponding sidechain if it is considered valid.

2.3 Security Definition of Sidechains

The first security definition of sidechains was introduced by Gaži et al. [2]. In a secure sidechains system, two fundamental properties, persistence and liveness, are necessary because a robust public transaction ledger must satisfy persistence and liveness [20]. Especially, a critical security feature that a secure sidechains system should have is the firewall property in which any catastrophic chain corruption, such as a violation of the chain security assumptions, does not impact other chains.

A formal security definition of sidechains is presented as follows.

Definition 3 (Sidechains security)

A system-of-sidechain ledgers protocol $\varPi$ for $\left\{ \mathbf {L}_{i}\right\} _{i \in [c]}$ is pegging-secure with liveness parameter $u \in \mathbb {N}$ with respect to:

• a set of assumptions $\mathbb {A}_{i}$ for ledgers $\left\{ \mathbf {L}_{i}\right\} _{i \in [c]}$,

• a merge mapping ${\text {merge}}$ $(\cdot )$,

• validity languages $\mathbb {V}_{\textsf {A }}$ for each $\textsf {A} \in \bigcup _{i \in [c]}$ Assets $\left( \mathbf {L}_{i}\right)$,

if for all PPT adversaries, all rounds r and for $\mathcal {S}_{r} \triangleq \left\{ i: \mathbb {A}_{i}[r]\right.$ holds $\}$ we have that except with negligible probability in the security parameter:

• Ledger persistence: For each $i \in \mathcal {S}_{r}, \mathbf {L}_{i}$ satisfies the persistence property.

• Ledger liveness: For each $i \in \mathcal {S}_{r}, \mathbf {L}_{i}$ satisfies the liveness property parametrized by u.

• Firewall: For all $\textsf {A} \in \bigcup _{i \in \mathcal {S}_{r}}$ Assets $\left( \mathbf {L}_{i}\right)$

  $$ \pi _{\textsf {A}}\left( {\text {merge}}\left( \left\{ \mathbf {L}_{i}^{\cup }[r]: i \in \mathcal {S}_{r}\right\} \right) \right) \in \pi _{\mathcal {S}_{r}}\left( \mathbb {V}_{\textsf {A}}\right) .$$

Where $\mathbb {A}_{i}$ denotes the security assumption of a ledger $\mathbf {L}_{i}$. For instance, a majority of authority (computational power, stakeholding, or node) is never controlled by the adversary. ${\text {merge}}(\cdot )$ is a function that combines a set of ledger states $\textsf {ST}$ = $\{\mathbf {L}_{1}, \mathbf {L}_{2},...,\mathbf {L}_{c}\}$ into a single ledger state denoted by ${\text {merge}}(\textsf {ST})$. A concrete instantiation of ${\text {merge}}(\cdot )$ we will give later. For each asset denoted by $\textsf {A}$, the validity language $\mathbb {V}_{\textsf {A}}$ can capture specific rules of behavior for $\textsf {A}$, e.g., an asset $\textsf {A}$ is transferred from a chain to the other chain. Note that Assets $\left( \mathbf {L}\right)$ is the set of all assets that belong to the ledger $\mathbf {L}$. $\pi$ is a ledger state projection. Specifically speaking, $\pi _{\textsf {A}}\left( \mathbf {L}\right)$ denotes the projection of the transactions of $\mathbf {L}$ with respect to the asset $\textsf {A}$.

2.4 An Example of an Asset $\mathsf {A}$

In this part we describe an example of a fungible asset $\textsf {A}$, and present the validity language $\mathbb {V}_{\mathsf {A}}$ with respect to the asset $\textsf {A}$. This example is a modification version based on an asset example in [2].

Instantiating $\mathbb {V}_{\mathsf {A}}$. For validity language $\mathbb {V}_{\mathsf {A}}$ we consider two ledger: the mainchain ledger $\mathbf {L}_{1} \triangleq \mathbf {M} \mathbf {C}$ and the sidechain ledger $\mathbf {L}_{2} \triangleq \mathbf {S} \mathbf {C}$. For the asset $\mathsf {A}$, each transaction tx has the form tx = ((oAddr, utxo, $\sigma$), (dAddr, a, $\pi$)), here:

• oAddr is an origin address on the origin ledger $\mathbf {L}_{\textsf {ori}}$. Note that a bitcoin address is derived from its public key.

• utxo is an unspent transaction output. A utxo represents the unspent amount, and is locked by the private key held by the sender.

• $\sigma$ is a signature generated by the sender on the metadata ((oAddr, utxo), (dAddr, a, $\pi$)), which is used to unlock a utxo.

• dAddr is a destination address on the destination ledger $\mathbf {L}_{\textsf {des}}$. We say either $\mathbf {L}_{\textsf {ori}}$ = $\mathbf {L}_{\textsf {des}}$, meaning that tx is a local transaction, or $\mathbf {L}_{\textsf {ori}}$ $\ne$ $\mathbf {L}_{\textsf {des}}$, meaning that tx is a cross-chain transfer transaction.

• a is the transfer amount.

• $\pi$ is the succinct proof data that validates the validity of a cross-chain transfer transaction. Note that $\pi$ is empty iif tx is a local transaction or an origin transaction.

Instantiating Merge($\cdot$). A merge($\cdot$) function takes as input a pair of ledger states ($\mathbf {M} \mathbf {C}$, $\mathbf {S} \mathbf {C}$) outlined above, and outputs a single ledger state.

3 Implementing Sidechain Ledger

We provide SEPoW for sidechains that are based on Bitcoin. Our protocol will execute a system of sidechains with sidechain security with respect to Definition 3 under an assumption on honest hashing-power majority. Here our SEPoW adopts the form of parent-child chains.

The main challenge in SEPoW is how to ensure secure cross-chain transfers. To achieve this, we introduce a cross-chain proof protocol described above into SEPoW. Consider two sidechains $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$ (the notations $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$ will be used throughout the rest of this paper), as well as a predicate (e.g., a cross-chain transaction took place in the sidechain $\mathcal {C}_{1}$ (resp. $\mathcal {C}_{2}$)). A cross-chain proof protocol for the predicate means that, the prover of $\mathcal {C}_{1}$ (resp. $\mathcal {C}_{2}$) can convince the verifier of $\mathcal {C}_{2}$ (resp. $\mathcal {C}_{1}$) that the predicate is true by generating a valid proof.

It is easy to establish valid but not succinct cross-chain proof for any computable predicate: the prover provides the entire linearly-growing chain of block headers as proof and the verifier simply selects the longest chain. To address this problem, we also introduce a merged mining mechanism described above into SEPoW, which allows the miners of sidechains to generate multiple blocks at different sidechains with a single PoW solution. Exploiting this, a public chain of block headers is shared by the participating sidechains. In this case, our proof is composed of two Merkle tree paths and thus is succinct.

3.1 The Sidechain Construction

We now present an elaborate module design of SEPoW based on the fundamental building block described above: cross-chain proof protocol and merged mining. These interacting modules are initialization, maintenance, cross-chain transfer and generating cross-chain proof. A graphical depiction about SEPoW is shown in Fig. 2.

3.1.1 The Sidechain Initialization

The initialization of a new $\mathbf {S} \mathbf {C}$ can be launched by any miners of $\mathbf {M} \mathbf {C}$ deploying the configuration transaction that configures $\mathbf {S} \mathbf {C}$ described below. This action only requires the miners to follow the rule in the configuration to support it (i.e., following merged mining). A sidechain that is successfully created will obtain a unique identifier $\texttt {id}_{\mathbf {S}\mathbf {C}}$.

Consider two rounds $\mathrm {d_{\eta }}$, $\mathrm {s_{\eta }}$ on $\mathbf {M} \mathbf {C}$, as described in Fig. 2. $\mathrm {d_{\eta }}$ means that the first configuration transaction $\textsf {tx}_{0}$ has been included in a block on $\mathbf {M} \mathbf {C}$. $\mathrm {s_{\eta }}$ denotes the start time of the sidechain if it is successfully activated. The configuration transaction contains a set of predefined rules that describe how to activate the sidechain and determine $\mathrm {s_{\eta }}$ successfully. A typical example is as follows: a sidechain starts in the $\mathbf {M} \mathbf {C}$-round $\mathrm {s_{\eta }}$ that meets: (i) $\mathrm {s_{\eta }}$ − $\mathrm {d_{\eta }}$ > $v_1,$ here $v_1$ denotes the number of round, which is used to determine the round $\mathrm {s_{\eta }}$; (ii) at least $v_2$-majority mining power on $\mathbf {M} \mathbf {C}$ is controlled by honest miners that have supported $\mathbf {S} \mathbf {C}$.

Fig. 2.

An overview of SEPoW. $\mathbf {M} \mathbf {C}$ is at the top, while $\mathbf {S} \mathbf {C}$ is at the bottom. $\mathrm {d_{\eta }}$ is the round of deploying sidechain. $\mathrm {s_{\eta }}$ is the round of starting sidechain. Solid arrows is used to connect adjacent blocks. Dashed arrows denote some blocks are omitted. Red rectangles denote some merged-block-headers. Transactions $\textsf {tx}$ of interest: $\textsf {tx}_{0}$. A configuration transaction; $\textsf {tx}_\textsf {ori}$. An origin transaction carrying withdraw operation from $\mathbf {M} \mathbf {C}$ to $\mathbf {S} \mathbf {C}$; $\textsf {tx}_\textsf {des}$. A corresponding deposit transaction from $\mathbf {M} \mathbf {C}$ to $\mathbf {S} \mathbf {C}$; $\textsf {tx}_\textsf {ori}^{'}$. An origin transaction carrying withdraw operation from $\mathbf {S} \mathbf {C}$ to $\mathbf {M} \mathbf {C}$; $\textsf {tx}_\textsf {des}^{'}$. A corresponding deposit transaction from $\mathbf {S} \mathbf {C}$ to $\mathbf {M} \mathbf {C}$.

The process of the activation is as follows (see more details in Algorithm 1).

First, the miners of $\mathbf {M} \mathbf {C}$ that support the sidechain mine a new block including the configuration transaction $\textsf {tx}_{0}$ on mainchain. If the sidechain is successfully activated, then during the round $\mathrm {s_{\eta }}$ the miners of $\mathbf {M} \mathbf {C}$ that support the sidechain create a genesis block $\texttt {GB}$ = (merged-block-header $\triangleq$ (pub, mr, ne, $\texttt {id}_{\mathbf {S}\mathbf {C}}$), merged-block-body $\triangleq$ (p, r)) for $\mathbf {S} \mathbf {C}.$ Here there are the variables pub, ne, p, r, as described in Fig. 1a. Note that $\texttt {GB}$ can be created as soon as ne is found. In addition, if the activation of the sidechain fails, the initialization of the sidechain is aborted.

To demonstrate that $\mathbf {S} \mathbf {C}$ has been successfully created, the miners of $\mathbf {M} \mathbf {C}$ that adopted $\mathbf {S} \mathbf {C}$ broadcast a special transaction success_sidechain$\texttt {(id}_{\mathbf {S}\mathbf {C}}{} \texttt {)}$ into $\mathbf {M} \mathbf {C}$. Otherwise, the miners of $\mathbf {M} \mathbf {C}$ that supported $\mathbf {S} \mathbf {C}$ broadcast another special transaction failure_sidechain$\texttt {(id}_{\mathbf {S}\mathbf {C}}{} \texttt {)}$ into $\mathbf {M} \mathbf {C}$. In this case, we will deduce whether the sidechain is valid, according to the transactions of $\mathbf {M} \mathbf {C}$ only.

3.1.2 The Sidechain Maintenance

Once SC is successfully created, both MC and SC will be maintained by miners and their respective full nodes.

For mainchain, its maintenance procedure is executed by MC-workers who are acted by the miners running merged mining and the full nodes of MC running the proof of work protocol, cf. Algorithm 2. For concreteness, the miners attempt to mine new blocks on top of both the longest $\mathcal {C}_\mathbf{MC}$ and $\mathcal {C}_\mathbf{SC}$ by running the merged mining mechanism described above, and then broadcast them as soon as their nonce ne is found. The full nodes of MC only maintain the longest $\mathcal {C}_\mathbf{MC}$.

MC-workers, on every new round after the round $\mathrm {s_{\eta }}$, receive all the possible MC-chains $\mathcal {C}_{\textsc {mc-}col}$ from the other peers via Diffuse, and then check them to find the “best” chain denoted by $\mathcal {\bar{C}}$. In this case they choose the chain $\mathcal {\bar{C}}$. Adopting the chain $\mathcal {\bar{C}}$ is done for chain validity function (using $\texttt {Check-Chain}$ given in Line 4 of Algorithm 2) and chain comparison function (using $\texttt {Chain-Comparison}$ given in Line 6 of Algorithm 2), as well as transaction validity function (using $\texttt {Check-Tx}$ given in Line 9 of Algorithm 2). Then, the miners try to extend $\mathcal {\bar{C}}$ by running the merged mining (using Merged-PoW given in Line 11 of Algorithm 2) described below.

Most importantly, the miners can simultaneously extend $\mathcal {C}_\mathbf{MC}$ and $\mathcal {C}_\mathbf{SC}$ by invoking Merged-PoW. In this case, a public chain of block headers is formed naturally in $\mathcal {C}_\mathbf{MC}$ and $\mathcal {C}_\mathbf{SC}$. Let us recall the work of Merged-PoW. First, the miners collect two valid txroot r from $\mathcal {C}_\mathbf{MC}$ and $\mathcal {C}_\mathbf{SC}$, and then calculate the root mr of the merged Merkle tree over the two txroot r. Next, the miners search for a nonce ne that satisfies $\mathrm {H(\textit{pub}, \textit{mr}, \textit{ne})}$ $\le$ ${\text {T}}$ (see more details in Eq. 2). Once ne is found, the miner composes specific-chain merged-blocks, consisting of a public merged-block-header and a specific-chain merged-block-body (as described in Fig. 1a), and sends them ($B_{\textsc {mc}}$, $B_{\textsc {sc}}$) to corresponding blockchain networks. Finally, workers of MC (resp. SC) verify $B_{\textsc {mc}}$ (resp. $B_{\textsc {sc}}$) and append it to $\mathcal {C}_\mathbf{MC}$ (resp. $\mathcal {C}_\mathbf{SC}$) if it is considered valid. As a result, a public chain of merged-block-headers is formed naturally in $\mathcal {C}_\mathbf{MC}$ and $\mathcal {C}_\mathbf{SC}$.

Regarding the sidechain, its maintenance procedure is similar to the mainchain. Hence we only present their differences.

The main difference is that in Algorithm 2, MC-workers, all the possible MC-chains $\mathcal {C}_{\textsc {mc-}col}$, the two new blocks $B_{\textsc {mc}}$ and $B_{\textsc {sc}}$, as well as all occurrences of the best chain $\tilde{\mathcal {C}}$ with respect to SC, are respectively replaced by SC-workers, SC-chains $\mathcal {C}_{\textsc {sc-}col}$, $B_{\textsc {sc}}$ and $B_{\textsc {mc}}$, as well as the best chain $\mathcal {C}$ with respect to MC.

3.1.3 Cross-Chain Transfer

Now nodes (or clients) can move funds from MC to SC by a cross-chain transfer transaction, which consists of a transaction $\textsf {tx}_\textsf {ori}$ carrying the withdraw operation, and a transaction $\textsf {tx}_\textsf {des}$ carrying the deposit operation. Two of them have the same fields, except for that metadata $\pi$ for $\textsf {tx}_\textsf {ori}$ is empty and metadata $\pi$ for $\textsf {tx}_\textsf {des}$ includes a cross-chain proof. The origin transaction $\textsf {tx}_\textsf {ori}$ that only involves the state in MC is handled by MC-workers, while the destination transaction $\textsf {tx}_\textsf {des}$ that only involves the state in SC is handled by SC-workers.

Moving funds from the mainchain $\mathbf{MC}$ into the sidechain $\mathbf{SC}$ works as follows. First, a client on MC diffuses $\textsf {tx}_\textsf {ori}$ with the desired utxo and the valid receiving address on $\mathbf{SC}$. If $\textsf {tx}_\textsf {ori}$ is considered valid, the corresponding block B carrying $\textsf {tx}_\textsf {ori}$ will be generated by the miner and only be appended to $\mathbf{MC}$; the withdraw operation will be executed.

When B has been buried under k blocks within $\mathbf{MC}$, $\mathbf{MC}$-workers create a cross-chain proof $\pi$ about the predicate, claiming that $\textsf {tx}_\textsf {ori}$ has been included in the stable mainchain $\mathbf{MC}$. Here, $\pi$ contains a transaction Merkle tree path for $\textsf {tx}_\textsf {ori}$ as well as a merged Merkle tree path p. The construction of $\pi$ is described below. We now suppose that $\pi$ has been produced, and then received by the client that will diffuse it.

After that, the corresponding $\textsf {tx}_\textsf {des}$ is composed by the client in $\mathbf{MC}$ and forwarded to the sidechain $\mathbf{SC}$. If $\textsf {tx}_\textsf {des}$ is considered valid, it contains: (i) a valid cross-chain proof $\pi$; (ii) a valid signature $\sigma$; (iii) sufficient utxo that is not less than the transfer amount a. If included, the deposit operation will be executed, concluding the completion of transferring from MC to SC. The core of transferring from MC to SC is shown in Algorithm 3.

Withdrawing to MC. Clients can then transfer their funds from SC back into MC. They follow the reverse procedure of Algorithm 3.

3.1.4 Generating Cross-Chain Proof

In the part we present a concrete construction of a cross-chain proof $\pi$. Let us consider cross-chain transactions consisting of the origin transaction $\textsf {tx}_\textsf {ori}$ occurring in MC and the destination transaction $\textsf {tx}_\textsf {des}$ occurring in SC, as well as the predicate q which claims that $\textsf {tx}_\textsf {ori}$ has been included in block B in the stable MC. To maintain the transfer of cross-chain assets for the SC verifiers (i.e., full nodes in SC) that cannot evaluate q, a cross-chain proof that deduces q is essential.

When the block B carrying $\textsf {tx}_\textsf {ori}$ has been buried under k blocks within MC, the cross-chain proof $\pi$ about q is produced by the provers on MC, and contains:

• The transaction Merkle tree path. The path for $\textsf {tx}_\textsf {ori}$ is produced from the transaction Merkle tree located in B’ body (see more details in Fig. 1a). It testifies that $\textsf {tx}_\textsf {ori}$ is aggregated in the transaction Merkle tree root r.

• The merged Merkle tree path p. The path is generated from the merged Merkle tree over the pair of ($r_1, r_2$) of the involved mainchain and sidechain. ${{\boldsymbol{p}}}$ connecting the transaction Merkle tree root r to the merged Merkle tree root mr is used to attest that r is tied in B’ header.

The above two paths allow the provers to convince the verifiers that q is true. Concrete space requirements about the proof are discussed in Sect. 6.1.

4 Proofs of Security

In this section, we first prove that SEPoW from Sect. 3 satisfies persistence and liveness, then prove that SEPoW achieves the firewall property, similar to the proof method of Gaži et al. [2].

4.1 Persistence and Liveness

Lemma 1 (Persistence and Liveness)

Consider SEPoW from Sect. 3 with respect to the assumptions $\mathbb {A}_\mathbf{MC }$ and $\mathbb {A}_\mathbf{SC }$. For all rounds r, if $\mathbb {A}_\mathbf{MC }\left[ r\right]$ (resp. $\mathbb {A}_\mathbf{SC }\left[ r\right]$) holds, then MC (resp. SC) achieves persistence and liveness up to round r with overwhelming probability in k.

Proof

(sketch). We directly borrow previous work [20, 21] to prove that both persistence and liveness hold. In [20] it was shown that the Bitcoin protocol with the honest majority of computational power provides three security properties: common prefix, chain quality and chain growth. Further, According to the work [21,22,23], persistence and liveness needed by a ledger can be derived from the above three properties. Therefore, SEPoW satisfies persistence and liveness, completing the proof.

4.2 Firewall Property

Lemma 2

For all PPT adversaries $\mathcal {A}$, SEPoW from Sect. 3 using a secure cross-chain proof protocol and a collision resistant hash function achieves the firewall property with the assumptions $\mathbb {A}_\mathbf{MC }$ and $\mathbb {A}_\mathbf{SC }$ with respect to overwhelming probability in k.

Proof

(sketch). To illustrate that the firewall property holds, we employ the idea of computational reduction in our proof. The line of the proof is as follows: suppose the firewall property is broken, an insecure cross-chain proof protocol or hash function is used by our protocol; then we show the probability of using the insecure cross-chain proof protocol or hash function is negligible.

We denote by $\mathcal {A}$ an arbitrary PPT adversary attacking the firewall property, and denote by $\mathcal {Z}$ an arbitrary environment supporting the execution of $\mathcal {A}$. We will consider two PPT adversaries:

• $\mathcal {A}_1$ is an adversary attacking the cross-chain proof protocol.

• $\mathcal {A}_2$ is an adversary attacking the hash function.

Next, we start by describing the behavior of these adversaries.

The Adversary $\mathcal {A}_1$bf . First, it models the execution of $\mathcal {A}$. That is, $\mathcal {A}$ requests that a cross-chain proof about the predicate q that an origin transaction is included in $\mathbf{MC}$ is produced (without loss of generality, in this proof we consider only the cross-chain transfers from MC to SC due to the symmetry of SEPoW), $\mathcal {A}_1$ calls its proof generation algorithm $\mathbf{P}$ (as described in Sect. 2.1) to get the corresponding proof to provide to $\mathcal {A}$.

$\mathcal {A}_1$ monitors the ledgers, $\mathbf {L}_{\mathbf {MC}}$ and $\mathbf {L}_{\mathbf {SC}}$, adopted by honest $\mathbf{MC}$-workers and $\mathbf{SC}$-workers, and for every round r checks the state of all honest $\mathbf{MC}$-workers and $\mathbf{SC}$-workers. To evaluate whether $\mathcal {A}$ has succeeded, the adversary inspects whether $\mathbf {L}={\text {merge}}\left( \mathbf {L}_{\mathbf {MC}}, \mathbf {L}_{\mathbf {SC}}\right) \notin \mathbb {V}_{\textsf {A}}.$ If $\mathcal {A}_{1}$ can not find such a round r and entities $\mathbf{MC}$-workers, $\mathbf{SC}$-workers, it returns $\textsc {failure}$.

Otherwise it exists a round r such that $\mathbf {L}={\text {merge}}\left( \mathbf {L}_{\mathbf {MC}}, \mathbf {L}_{\mathbf {SC}}\right) \notin \mathbb {V}_{\textsf {A}}.$ Suppose that $\mathbf {L}^{\prime }$ is the prefix of $\mathbf {L}$ that satisfies $\mathbf {L}^{\prime } \notin \mathbb {V}_{\textsf {A}}$ and $\textsf {tx} =\mathbf {L}^{\prime }[-1]$. If tx has oAddr($\textsf {tx}$) $\notin$ MC or dAddr(tx) $\notin$ SC, then $\mathcal {A}_{1}$ returns $\textsc {failure}$. Otherwise oAddr($\textsf {tx}$) $\in$ MC and dAddr(tx) $\in$ SC (and so $\textsf {tx} \in \mathbf {L}_{\mathbf {SC}}$). Therefore, there must exist a predicate q that the origin transaction ($\textsf {tx}^{\prime }$) corresponding to $\textsf {tx}$ is committed in $\mathbf {L}_{\mathbf {MC}}$ is $\textsf {true}$.

Let $\textsc {q}^{*}$ be the set of $\mathbf {L}_{\mathbf {MC}}$ including all predicates up to and containing q. We will show that $\textsc {q}^{*}$ must contain a predicate attested by a forgery cross-chain proof. $\mathcal {A}_{1}$ inspects every predicate $\textsc {q}_{r}$ $\in \textsc {q}^{*}$. $\textsc {q}_{r}$ involves a proof $\pi _r$ for an origin transaction. $\mathcal {A}_{1}$ produces a proof $\pi _r^{\prime }$ for $\textsc {q}_{r}$ based on the view of $\mathbf{SC}$-workers, and examines whether the following predicate violation condition holds:

$$\begin{aligned} (\textsc {q}_{r} \in \textsf {true}) \wedge (\lnot {\text {V}}(\pi _r) \vee (\pi _r \ne \pi _r^{\prime })). \end{aligned}$$

(4)

Suppose it exists a round $r^{*}$ that satisfies the condition (4) and then outputs the tuple ($\textsc {q}_{r^{*}}$, $\pi _{r^{*}}$). Otherwise $\mathcal {A}_{1}$ returns $\textsc {failure}.$

The Adversary $\mathcal {A}_2$. Similar to $\mathcal {A}_1,$ $\mathcal {A}_2$ models the execution of $\mathcal {A}$. When $\mathcal {A}$ requests that a proof of a predicate q is created, $\mathcal {A}_2$ invokes its algorithm $\mathbf{P}$ to get the corresponding proof to provide to $\mathcal {A}$.

$\mathcal {A}_2$ monitors the ledgers, $\mathbf {L}_{\mathbf {MC}}$ and $\mathbf {L}_{\mathbf {SC}}$, adopted by honest $\mathbf{MC}$-workers and $\mathbf{SC}$-workers, and for every round r checks the state of all honest $\mathbf{MC}$-workers and $\mathbf{SC}$-workers. $\mathcal {A}_{2}$ checks whether $\mathbf {L}={\text {merge}}\left( \mathbf{MC} , \mathbf{SC} \right) \notin \mathbb {V}_{\textsf {A}},$ to evaluate whether $\mathcal {A}$ has succeeded. If the adversary can not find such a round r and entities $\mathbf{MC}$-workers, $\mathbf{SC}$-workers, it returns $\textsc {failure}$. Suppose $\textsf {tx},$ $\textsf {tx}^{\prime }$ are as described in $\mathcal {A}_{1}$. If $\textsf {tx}$ has oAddr(tx) $\notin$ $\mathbf {MC}$ or dAddr(tx) $\notin$ $\mathbf {SC}$, then $\mathcal {A}_{2}$ returns $\textsc {failure}$. Then the predicate q that $\textsf {tx}^{\prime }$ is committed in $\mathbf {L}_{1}$ is $\textsf {true}$, and the corresponding cross-chain proof $\pi$ for $\textsf {tx}^{\prime }$ was created. If q is $\textsf {false}$, then $\mathcal {A}_{2}$ returns $\textsc {failure}.$ When q for $\mathbf{SC}$-workers is $\textsf {true}$, there exists a cross-chain proof $\pi ^{\prime }$ that attests to $\textsf {tx}^{\prime }$ in the view of $\mathbf{SC}$-workers. Based on the above results, $\mathcal {A}_{2}$ finds a collision for hash function and returns it.

Probability Analysis. We define the following events:

• sc-failure[ r ]: $\mathcal {A}$ is successful at round r, i.e., $\pi _{\textsf {A}}\left( {\text {merge}}\left( \left\{ \mathbf {L}_{i}[t]: i \in \mathcal {S}_{t}\right\} \right) \right) \notin \pi _{\mathcal {S}_{t}}\left( \mathbb {V}_{\textsf {A}}\right)$.

• ccpp-break: $\mathcal {A}_1$ finds such a round $r^{*}$ such that the condition (4) holds.

• hash-break: $\mathcal {A}_2$ finds a collision for the hash function.

Next, we will argue that the probability Pr[sc-failure[ r ]] is negligible for every time round r. We will demonstrate this probability in three successive claims.

The first claim shows that one of ccpp-break, hash-break happens if sc-failure[ r ] happens. As a result, according to a union bound, we have

$$ {\text {Pr}}[\textsc {sc-failure[{ r}]}] \le {\text {Pr}}[\textsc {ccpp-break}]+{\text {Pr}}[\textsc {hash-break}]. $$

The other two claims show that Pr[ccpp-break] and Pr[hash-break] are negligible.

Claim 1:

sc-failure[r ] $\Rightarrow$ ccpp-break $\vee$ hash-break.

By the Lemma 2, there exist two ledgers $\mathbf {L}_{\mathbf {MC}}$ and $\mathbf {L}_{\mathbf {SC}}$. Thus $\textsc {sc-failure}[r]$ is meant to

$$ {\text {merge}}(\{\mathbf {L}_{\mathbf {MC}}[r], \mathbf {L}_{\mathbf {SC}}[r]\}) \notin \mathbb {V}_{\textsf {A}} .$$

Without loss of generality, suppose that tx, $\textsf {tx}^{\prime }$ and q are as described in $\mathcal {A}_1$. By the Lemma 2 and the Lemma 2 from [2], we deduce that tx is a destination transaction, and oAddr(tx) $\in \mathbf {MC}$ and dAddr(tx) $\in \mathbf {SC}$. Thus, q is $\textsf {true}.$ If $\mathcal {A}_1$ discovers such a round $r^{*}$ that satisfies the condition (4), then ccpp-break has happened and the claim holds. Therefore, for each predicate $\textsc {q}_r$ involving a proof $\pi _r$, the following condition holds:

$$\begin{aligned} (\textsc {q}_r \in \textsf {true}) \wedge {\text {V}}(\pi _r) \Rightarrow (\pi _r = \pi _r^{\prime }). \end{aligned}$$

(5)

Thus, we have a set of all predicates, each of which is $\textsf {true}$ and is proved by the corresponding cross-chain proof $\pi _r$; this equation $\pi _r = \pi _r^{\prime }$ holds. However, the origin transaction $\textsf {tx}^{\prime }$ has been committed by $\pi _r$, but not committed by $\pi _r^{\prime }$. Therefore, there must exist a Merkle tree collision, meaning that a hash collision found by $\mathcal {A}_2$ occurs. As a result, hash-break happens.

Claim 2:

Pr[ccpp-break] is negligible.

Suppose that ccpp-break happens. We can discover that the condition (4) holds. This case, however, is negligible according to the assumption that the cross-chain proof protocol in use is secure.

Claim 3:

Pr[hash-break] is negligible.

It is the same as claim 2, there exists another cross-chain proof $\pi$ for the origin transaction corresponding to $\textsf {tx}$ is created, which contradicts with the assumption that the hash function in use is collision-resistant.

Relying on the three claims above, we conclude that for negligible probability negl, Pr[sc-failure] $\le$ negl. Therefore, $\pi _{\textsf {A}}\left( {\text {merge}}\left( \left\{ \mathbf {L}_{i}[r]: i \in \mathcal {S}_{r}\right\} \right) \right) \in \pi _{\mathcal {S}_{r}}\left( \mathbb {V}_{\textsf {A}}\right)$ holds, completing the proof.

The above two Lemmas directly prove Theorem 1 presented below.

Theorem 1 (Sidechains security)

SEPoW from Sect. 3 using a secure cross-chain proof protocol and a collision resistant hash function is secure with respect to assumptions $\mathbb {A}_{\mathbf {MC}}$ and $\mathbb {A}_{\mathbf {SC}}$, and $\textsf {merge}$ and $\mathbb {V}_{\textsf {A}}$ defined in Sect. 2.4.

5 Discussion of Merged Mining

Transaction Verification. In the merged mining mechanism described in Sect. 2.2, merged miners should validate all transactions in sidechains; otherwise invalid transactions may be included in some sidechain transaction Merkle Trees. To achieve this, the merged miners are required to monitoring all involved sidechains. However, this contradicts the sidechains agnosticism [7]: miners of MC do not need to be aware of SC at all. Only the entities interested in facilitating cross-chain events must be aware of both. To resolve this question, we introduce a cryptographic tool, the recursive composition of zk-SNARKs [24, 25], which can create proofs that attest to the validity of other proofs. We leverage the tool to generate a succinct proof of sidechain transaction Merkle tree that attests to the correctness of all transactions at the base of the tree. By verifying the validity of the proof, the merged miners can efficiently evaluate the validity of all transactions in the tree without re-executing transaction verification and monitoring all involved sidechains.

Consider an example that a list of transactions $\textsf {tx}_\textsf {1}$, $\textsf {tx}_\textsf {2}$, $\textsf {tx}_\textsf {3}$, $\textsf {tx}_\textsf {4}$ in a sidechain transaction Merkle tree needs to be proved. First, a full node in the sidechain generates “base” proofs proving the validity of single transactions. Then two adjacent “base” proofs are merged and further generate a new “merge” proof. Finally, these “merge” proofs are recursively merged into a “merge” proof called root proof. As a result, the root proof attests to the validity of all the transactions.

Fig. 3.

Asynchronous extension of sidechains (a); Sidechain fork (b). (Color figure online)

Sidechains Extension. In SEPoW, some “regular miners” exist who do not run merged mining but only work on the chain they participate in. This will cause the computational power of each sidechain to be different. In this case, one sidechain extension will exceed the other sidechain. A typical example is shown in Fig. 3a. Where MC extension exceeds SC. A red public chain of block headers is broken due to the two gray blocks on MC that the “regular miners” mine. As a result, cross-chain proofs are affected.

To overcome this problem, merged miners need to rebuild a new public chain of block headers to inherit the previous public chain and backup the information testifying these gray blocks’ validity into $\mathbf {SC}$. For the former, merged miners run merged mining on the top of two chains and produce new public block headers (blue block headers in Fig. 3a). For the latter, full nodes on $\mathbf {MC}$ send gray blocks information, consisting of block headers verifying consensus and proofs attesting to the validity of transaction Merkle trees, to merged miners. Upon receiving them, merged miners check their validity by calling a hash function and the zk-SNARKs described above. Then merged miners include these hashes of valid gray block headers into subsequent merged-block-headers by merged mining (here, the hashes are seen as the leaves of a merged Merkle tree).

Fork Solution. The setting of merged mining seems to be a bit coercive in that it makes all sidechains collapse into one single blockchain. That is, the “fork” in a sidechain will affect all sidechains unstable. A typical example is shown in Fig. 3b. Where both MC (i.e., Branch 2) and SC maintain merged mining and form a red public chain of block headers. With blockchains growth, however, the length of Branch 1 exceeds Branch 2. Thus, branch 1 becomes the “main” chain according to the longest chain rule, while Branch 2 is discarded. Meanwhile, blocks b1 and b2 become “orphan” blocks. As a result, the red public chain of block headers on MC and SC is broken; cross-chain proofs are affected.

To complement this deficiency, the following efforts need to be done: 1) merged miners run merged mining on top of Branch 1 and SC, and create a new public chain of block headers (blue block headers in Fig. 3b); 2) the information of gray blocks on Branch 1 need to be backed up to SC via the way described in Sidechains Extension; 3) merged miners need to mark “orphan” blocks as invalid in subsequent merged-blocks. This is because adversaries may utilize the headers information of h1 and h2 blocks, including some proofs that testify to the validity of “orphan” blocks transactions, to implement the double-spend attack.

6 Performance Evaluation

In this section, we evaluate the size of SEPoW proof and compare it with the state-of-the-art work.

6.1 Size of Cross-Chain Proofs

We first evaluate the size of SEPoW proofs, consisting of a transaction Merkle tree path denoted by path and a merged Merkle tree path denoted by p. Similar to Bitcoin Core, we assume a 256-bit hash function is used to build the Merkle tree construction, and a block of 1 MBytes and a block header of 80 bytes are applied to SEPoW. More specifically, in 1 MB block including up to 2048 transactions (in fact, since January 1, 2020, a Bitcoin block includes 1869 transactions¹ on average), we have in bits: |p| = $|256 + 256|$ = 512 bits, |path| = |log(2048) $\times$ 256| = 2,816 bits, and hence the size of SEPoW proofs is |path| + |p| = 512 + 2816 = 416 bytes.

6.2 Comparison with Existing Work

Without loss of generality, let us consider some work: BTCRelay [6], PoW sidechains [7, 17] and zkRelay [12], which have been implemented or can be evaluated. Their cross-chain proofs sizes can be denoted as $O (n \cdot |BH| + \log _2 |BT| \cdot |H|)$ [6], $O (\log _{1 / m}(2) \lambda \cdot ((\log _{2}(n)+1) \cdot |BH|+\log _{2}(n) \cdot \left\lceil \log _{2}\left( \log _{2}(n, 2), 2\right) \right\rceil \cdot |H|))$ [26] and $O (1/504 \cdot n \cdot |BH|)$ [12], respectively, according to their experimental results. Here, n is the length of a blockchain, |BH| is the size of a block header, |BT| is the number of transactions included in the block B, |H| is the size of a hash, m and $\lambda$ denote an attacker who controls a m fraction of honest chain’s mining power succeeds with probability $2^{-\lambda }$.

Fig. 4.

Comparison of SEPoW, BTCRelay, PoW sidechains and zkRelay at different blockchain length, |BH| = 80 bytes, |BT| = 2048, |H| = 32 bytes, m = 0.5, $\lambda$ = 50.

As depicted in Fig. 4, we make comparisons of SEPoW with BTCRelay, PoW sidechains and zkRelay in terms of the size of a cross-chain proof (The source code related to this comparison experiment has been released to the Github²). Figure 4a(1–3) show the impact of blockchain length on a cross-chain proof. Here, BTCRelay proof and zkRelay proof, located in Fig. 4a1 and 4a3, are linear and sublinear in the length of the blockchain, respectively; PoW sidechains proof, located in Fig. 4a2, is logarithmic in the length of the blockchain. More importantly, our SEPoW proof is composed of two Merkle tree paths regardless of the blockchain length, which significantly outperforms all proofs of the above, especially for longer chains.

Figure 4b(1–3) show the multiple relationships between SEPoW proof and the existing work at different blockchain length. Where, the multiple that SEPoW proof is less than BTCRelay proof and zkRelay proof, indicated by Fig. 4b1 and 4b3, increases linearly; the multiple that SEPoW proof is less than PoW sidechains proof, indicated by Fig. 4b2, is exponential growth. Note that for a blockchain length (n) of 300000 and block header size (|BH|) of 80 bytes, SEPoW achieves a proof size of 416 bytes which is roughly 123$\times$, 510$\times$ and 62000$\times$ smaller than zkRelay proof, PoW sidechains proof and BTCRelay proof, respectively.

7 Related Work

Recently, some researchers have focused on federation construction for sidechains. Dilley et al. [9] designed a federation construction that allows cross-chain assets transfer between disparate blockchains. In this construction cross-chain assets are managed by a trusted committee and are transferred only when the majority of the committee sign cross-chain transactions. Similarly, Back et al. [4] proposed a federation cross-chain solution, in which cross-chain assets are transferred by a trusted group of parties. However, their work has not entirely overcome the political centralization risk as the federation constructions still rely on a trusted committee to maintain and manage cross-chain assets transfer.

To prevent centralization risk, decentralized constructions for sidechains have been proposed. Kiayias et al. [7] presented the first decentralized construction for proof of work sidechains. The construction that is built based on a cryptographic primitive, Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) [17], allows the passing of any information between proof of work blockchains without a trusted third party. However, its cross-chain proof has linear in the length of the blockchain and thus is fairly large. Sztorc [10] and Lerner [11] proposed Drivechains, a decentralized construction for proof of work sidechains. In Drivechains cross-chain assets moved from Bitcoin to Drivechain are authenticated by SPV proofs consisting of all Bitcoin block headers. Yet, these SPV proofs are quite large. An implemented and decentralized construction for sidechains was given in BTCRelay [6]. It supports assets transferred from Bitcoin to Ethereum but not back. To verify the validity of the transactions that took place in Bitcoin, BTCRelay requires saving the entirety of Bitcoin block headers into Ethereum; limiting any potential scalability.

Some other studies are devoted to generating succinct cross-chain proofs about the transactions that took place in a blockchain. Garoffolo et al. [8] proposed Zendoo, a decentralized construction for blockchain systems that allows communication with different sidechains without trusted intermediaries. The construction introduces zk-SNARKs [27] to produce a constant-sized proof that attests to the validity of all cross-chain transactions during a period. Westerkamp et al. [12] presented an efficient sidechains construction, which uses zkSNARK-based chain-relays to generate a succinct proof that testifies the validity of cross-chain assets. The proof size does not grow linearly with the number of block headers but is constant for any batch size. However, these work lacked a formal security definition and proof.

In some different efforts, Gaži et al. [2] presented the first formal treatment of sidechains and proof of stake sidechains construction. To attest to the validity of cross-chain assets, they introduce a trust committee chosen among sidechain block creators to generate the sidechain certificates. The first Bitcoin sidechain in production was given in RSK [13]. It supports smart contracts functionality, compatible with the Ethereum standards. Yet, RSK proofs (from Bitcoin to RBTC) have linear complexity in the length of Bitcoin blockchain and RSK lacked a formal security definition and proof.

Furthermore, different ideas regarding cross-chain transfers, such as Polkadot [28], Cosmos [29], Tendermint [29], Blockstream’s Liquid [30] and Interledger [30], have been proposed. Their construction was centralized and lacked formal security definition and proof. Other related effort also included COMIT [31, 32], Plasma [33, 34], NOCUST [35, 36], Dogethereum [37] and XCLAIM [38].

8 Conclusion

In this paper, we proposed SEPoW, which makes up for deficiencies in security and efficiency in existing PoW sidechains construction. In SEPoW the exchange of all cross-chain assets is managed by all honest nodes in participating blockchains. To generate a succinct cross-chain proof, we utilized the merged mining to produce a constant-size proof, regardless of the size of the current blockchain. The security of SEPoW for PoW sidechains is proved formally. We presented a detailed design of SEPoW and evaluated the size of SEPoW proof; SEPoW achieves a proof size of 416 bytes which significantly outperforms all proofs of the existing work, especially for longer chains.