A Distributed Scalable Cross-chain State Channel Scheme Based on Recursive State Synchronization

As illustrated in Fig. 1, the existing cross-chain schemes can be classified into two categories: non-relay-based schemes and relay-based schemes. In a non-relay-based scheme, two blockchains do not transfer their state information to each other but rely on external components to achieve cross-chain operations. For example, decentralized exchanges [8] use a notary committee as a third party to exchange users’ tokens in one blockchain for tokens in another blockchain. Moreover, atomic cross-chain swaps [9] are achieved by using hashed time-lock contract [10]. However, as a non-relay-based scheme does not transfer blockchain state information, the scheme can only support simple cross-chain operations with a low security guarantee.

In a relay-based scheme, two blockchains transfer their state information to each other by using a cluster of relay nodes. The relay-based scheme was first illustrated by Back et al. [11] in 2014. BTC Relay [12] is a representative implementation. It sends the Bitcoin block headers to the Ethereum smart contract, achieving cross-chain verification of Bitcoin transactions. Based on BTC Relay, Alexei et al. [13] propose XClaim. It achieves trustless cross-chain exchanges using cryptocurrency-backed assets and employs collateralization and punishments to enforce the correct behavior of participants. To further improve efficiency, Xie et al. [14] propose zkBridge. It introduces zk-SNARK to generate the state proof of blockchain. By this act, the state information can be compressed into a small proof to be transferred between blockchains, reducing the overhead of transmission and storage.

The early relay-based schemes mainly focus on the interaction between two blockchains, which is also called one-to-one framework. If a blockchain intends to interact with $n$ blockchains, it has to establish $n$ cross-chain connections, which is inefficient. To solve this problem, the relay nodes cluster begins to establish connections with multiple blockchains, called parachains (parallel blockchains). Besides, the relay nodes maintain a blockchain, called relay chain, by themselves to record the state information from every parachain. At the same time, relay chain is published to every parachain system. Subsequently, a parachain can obtain the states of other parachains by only accessing relay chain. Based on this relay-chain-parachain framework, a parachain only needs to establish one cross-chain connection with relay chain to interact with $n$ parachains that also connect with relay chain, to improve efficiency.

The existing cross-chain platforms such as Polkadot [15] and Cosmos [16] are constructed following the relay-chain-parachain framework. As mentioned in Section I, these platforms are required to support the cross-chain needs of large-scale users with numerous cross-chain transactions per day. However, in previous cross-chain platforms, the cross-chain synchronizations between blockchains are non-real-time. It results that a blockchain cannot learn the latest states of another blockchain on the platform within a certain time limit, as the blockchain features a dynamically growing data structure with continuously updating states. To solve the problem, Liang et al. [17] propose a cross-chain state pulling scheme, called XPull. The relay nodes cluster will periodically pull the latest state information from parachains, and forward the state information to other parachain systems, which achieves real-time state transfer to ensure timeliness.

In 2016, Joseph et al. proposed payment channel [19] to improve the scalability of Bitcoin. In the following works, the payment channel is beginning to develop in two directions, as shown in Fig. 2. The first direction is payment channel network [19], noted PCN. It enables the delivery of assets between two users $U_{1}$ and $U_{n}$ by using a path of payment channels in PCN. In the following works, researchers have further improvements to payment channel network from various perspectives. For example, Giulio et al. [20] propose Fulgor to ensure privacy by using multi-hop hashed time-lock contract. Christoph et al. [21] propose the protocol AMCU for atomic multi-channel updates by jointly creating a multiple-input-multiple-output (MIMO) transaction. Lukas et al. [22] further propose Thora to refine atomicity, in which Thora is compatible with a number of cryptocurrencies having arbitrary payment channel topologies. Lukas et al. [23] propose Sleepy Channel, which does not require either of the channel users to be persistently online. Papadis et al. [24] propose single-hop scheduling (SHS), which provides a decision-making scheme for the users in payment channel network to maximize channel throughput.

The second direction is virtual payment channel [25]. Based on the current two channels, noted as $(U_{1},U_{2})$ and $(U_{2},U_{3})$, the users $U_{1}$ and $U_{3}$ can establish a virtual payment channel $(U_{1},U_{3})$ to have direct interaction. Next, virtual payment channel technology has derived the design of multi-party virtual channel (MPVC) [26]. It means that more than two users can interact within a channel, supporting more complex off-chain operations. Furthermore, Lukas et al. propose bitcoin-compatible virtual channel (BCVC) [27] to improve the compatibility. In the most recent work, Jia et al. propose a scheme (CCVPC) [28] to achieve cross-chain virtual payment channel $(U_{1},U_{3})$, based on $(U_{1},U_{2})$ and $(U_{2},U_{3})$ in different blockchain systems. However, this design cannot resist the conspiracy attack of $U_{1}$, $U_{2}$, and $U_{3}$, posing a security threat.

Moreover, with the extension of blockchain application scenarios from cryptocurrencies to other fields, the operations of transferring tokens within a channel have been generalized into a channel’s state change [30], in which the previous “payment channel” has evolved into “state channel”. Nowadays, state channels have been applied in various fields, such as log audit [31], data sharing [32], and video streaming [33].

The transaction verification schemes of blockchain can be classified into two categories. The first category is based on the well-known Merkle tree [34], applied by Bitcoin. Subsequently, researchers improve the Merkle tree and propose Merkle Patricia tree, applied by Ethereum [3]. It introduces prefix tree to enhance the efficiency of data storage and retrieval.

The second category is based on one-way accumulator. In 1993, Benaloh et al. [35] first constructed the accumulator based on the one-way hash function which satisfies a quasi-commutative property. An accumulator allows a prover to hash the transactions in a blockchain into one short value, which supports efficient cross-chain transfer. Niko et al. [36] further generalize the definition of accumulators and construct a collision-free subtype. Jan et al. [37] propose dynamic accumulator that allows a prover to dynamically add and delete an element in the accumulator. In recent works, Boneh et al. [38] propose batching techniques for cryptographic accumulators, which achieve membership proof and non-membership proof of transactions in blockchain. As the accumulators are well compatible with zk-SNARK, the existing anonymous cryptocurrency schemes, such as Zcash [39] [40], adopt accumulators for transaction retrieval.

To facilitate the understanding, we summarize the main notations in this paper in TABLE I.

The relay-chain-parachain framework is widely used in cross-chain platforms [15] [16] to meet the cross-chain needs of multiple blockchains.

There are $n$ parachains $\{\mathbf{P}_{1},\dots,\mathbf{P}_{n}\}$ and one relay chain $\mathbf{R}$ in the framework. Each parachain $\mathbf{P}_{i}$ $(i\in[n])$ is maintained by a set of parachain nodes $\mathrm{N}^{P}_{i}$ and the relay chain $\mathbf{R}$ is maintained by a set of relay nodes $\mathrm{N}^{R}$. Moreover, $\mathrm{N}^{R}$ are divided into $n$ relay node groups $\{\mathrm{N}^{R\sim}_{1},\dots,\mathrm{N}^{R\sim}_{n}\}$ and $\forall\{i,j\}\subseteq\{1,\dots,n\}\wedge i\neq j,\mathrm{N}^{R\sim}_{i}\cap\mathrm{N}^{R\sim}_{j}=\emptyset$. The relay node group $\mathrm{N}^{R\sim}_{i}$ establish network connections with $\mathrm{N}^{P}_{i}$ to start the cross-chain state transfer, which includes two processes of state reception and state forwarding.

In the state reception process, the relay node groups $\mathrm{N}^{R\sim}_{i}$ $(i\in[n])$ receive the state information of $\mathbf{P}_{i}$ from $\mathrm{N}^{P}_{i}$, and record the information into $\mathbf{R}$ to be published to every entity on the cross-chain platform. In the state forwarding process, $\mathrm{N}^{P}_{j}$ $(j\in[n],i\neq j)$ extract the state information of $\mathbf{P}_{i}$ from $\mathbf{R}$, and record the information into $\mathbf{P}_{j}$. Therefore, by only accessing $\mathbf{P}_{j}$, any entity in $\mathbf{P}_{j}$ system can obtain the state information of $\mathbf{P}_{i}$, supporting cross-chain operations.

Furthermore, to ensure the timeliness of $\mathbf{P}_{i}$ state information in $\mathbf{R}$, the relay node group $\mathrm{N}^{R\sim}_{i}$ adopts a state pulling strategy [17]. $\mathrm{N}^{R\sim}_{i}$ periodically send the state pulling instructions to $\mathrm{N}^{P}_{i}$ to pull the latest state information of $\mathbf{P}_{i}$, and subsequently record the state information into $\mathbf{R}$. Moreover, when an adversary has corrupted $\mathrm{N}^{R\sim}_{i}$ to interrupt the state pulling, a new relay node group $\mathrm{N}^{*R\sim}_{i}$ will be randomly selected from $\mathrm{N}^{R}$ based on distributed randomness [41] generated by $\mathrm{N}^{R}$. $\mathrm{N}^{*R\sim}_{i}$ will replace $\mathrm{N}^{R\sim}_{i}$ to continue the state pulling, ensuring $\mathbf{P}_{j}$ to record the real-time state information of $\mathbf{P}_{i}$.

An accumulator [35] [36] [38] enables one to encode a set into a short digest and prove that an element is in the set. Let $D$ be the domain of an accumulator. An accumulator $\mathcal{ACC}=(\mathsf{Setup},\mathsf{Commit},\mathsf{Add},\mathsf{CreateMemWit},\mathsf{VerifyMem})$ consists of the following five algorithms.

• •

  $\mathsf{Setup}(1^{\lambda})\rightarrow pp$: Given a security parameter $\lambda$, this setup algorithm outputs a public parameter $pp$.

• •

  $\mathsf{Commit}(pp,S)\rightarrow A^{S}$: Given the public parameter $pp$ and a set $S\subseteq D$, this committing algorithm outputs an accumulator digest $A^{S}$ to the set $S$.

• •

  $\mathsf{Add}(A^{S},ct)\rightarrow A^{S\cup\{ct\}}$: Given an accumulator digest $A^{S}$ to a set $S$ and an element $ct\in D\setminus S$, this adding algorithm outputs a new accumulator digest $A^{S\cup\{ct\}}$ to the set $S\cup\{ct\}$.

• •

  $\mathsf{CreateMemWit}(S,A^{S},ct)\rightarrow w^{ct,S}$: Given a set $S$, an accumulator digest $A^{S}$ to the set $S$, and an element $ct\in S$, this witness creation algorithm outputs the membership witness $w^{ct,S}$ of $ct\in S$.

• •

  $\mathsf{VerifyMem}(A^{S},ct,w^{ct,S})\rightarrow b$: Given an accumulator digest $A^{S}$ to a set $S$, an element $ct$, and a membership witness $w^{ct,S}$, this membership verification algorithm outputs a bit $b\leftarrow 1$ to indicate that $w^{ct,S}$ is a valid witness for proving $ct\in S$; otherwise outputs $b\leftarrow 0$.

The zero-knowledge proof (ZKP) scheme [42] [14] enables one to prove a statement without exposing other information. The ZKP scheme $\mathcal{ZKP}=(\mathsf{Setup},\mathsf{Prove},\mathsf{Verify})$ consists of the following three algorithms.

• •

  $\mathsf{Setup}(1^{\mu},R)\rightarrow crs$: Given a security parameter $\mu$ and a relationship $R$, this setup algorithm outputs a common reference string $crs$.

• •

  $\mathsf{Prove}(crs,x,w)\rightarrow\pi$: Given a common reference string $crs$, a statement $x$, and a witness $w$, this proving algorithm outputs a proof $\pi$ for the relationship $R(x,w)$.

• •

  $\mathsf{Verify}(crs,x,\pi)\rightarrow b$: Given a common reference string $crs$, the statement $x$, and the proof $\pi$, this verification algorithm outputs a bit 1/0 to indicate whether $R(x,w)$ holds or not.

ZKP satisfies three properties. Completeness: if the witness being proved is true, the verifier will be convinced of this fact with high probability. Soundness: if the witness being proved is false, no cheating prover can convince the verifier that it is true, except with a negligible probability. Zero-knowledge: the proof does not reveal any information about the witness being proved, except for the fact that it is true.

Interpipe includes one relay chain $\mathbf{R}$, and two parachains $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ called left parachain and right parachain. $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ have established cross-chain connections with $\mathbf{R}$ on a cross-chain platform, following relay-chain-parachain framework. The state information of $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ is synchronized into each other in the following way (see Fig. 3): ① $\mathrm{N}^{R\sim}_{l}$ and $\mathrm{N}^{R\sim}_{r}$ divided from $\mathrm{N}^{R}$ pull the latest state information of $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ from $\mathrm{N}^{P}_{l}$ and $\mathrm{N}^{P}_{r}$ using state pulling strategy; ② $\mathrm{N}^{R\sim}_{l}$ and $\mathrm{N}^{R\sim}_{r}$ generate the state proofs of $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$, and record the state proofs into $\mathbf{R}$; ③ as $\mathbf{R}$ is public on the cross-chain platform, $\mathrm{N}^{P}_{r}$ and $\mathrm{N}^{P}_{l}$ extract the $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ state proofs from $\mathbf{R}$, and record them into $\mathbf{P}_{r}$ and $\mathbf{P}_{l}$, achieving a synchronization.

There are two users Alice and Bob. On the one side, Alice belongs to $\mathbf{P}_{l}$ system. She can access the network of $\mathrm{N}^{P}_{l}$ to obtain the full blockchain data of $\mathbf{P}_{l}$, or publish new transactions on $\mathbf{P}_{l}$ via $\mathrm{N}^{P}_{l}$. Since the state proof of $\mathbf{P}_{r}$ has been recorded into $\mathbf{P}_{l}$, Alice can verify the state or transactions in both $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ by only accessing $\mathbf{P}_{l}$. In the same way, Bob belongs to $\mathbf{P}_{r}$ system, and he can verify the state or transactions in both $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ by only accessing $\mathbf{P}_{r}$. Additionally, a communication connection is established between Alice and Bob to transmit signatures and membership witnesses of transactions. This communication connection is off-chain, which does not require the use of any blockchain network. Based on the above configurations, a cross-chain state channel is established between Alice and Bob.

It is worth noting that among the $n$ parachains on the cross-chain platform, any two parachains can establish cross-chain state channels in the same way as parachain $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$. For convenience, we specifically discuss a cross-chain state channel between $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ in the following content.

• •

  Hard fork: Hard fork can occur in a blockchain to result in a split from the original chain and the creation of a new separate chain.

• •

  Denial-of-service attack: With a sufficiently long period of time, an adversary can control every node in a relay node group to interrupt the information synchronization between parachains.

• •

  Replay attack: An adversary can replay cross-chain transactions and state proofs, attempting to have duplicate operations to cross-chain state channel.

• •

  Counterfeiting: An adversary can tamper the contents in cross-chain transactions and state proofs, attempting to synchronize false information between parachains.

• •

  Eclipse attack: An adversary can create a fake network environment around a user, attempting to prevent the user from learning the new states of blockchains.

• •

  Conspiracy attack: Alice and Bob can collude to publish different cross-chain transactions to $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$, attempting to create parachain data out of thin air.

• •

  Noncooperation: One of Alice and Bob can refuse to cooperate with the other one, attempting to terminate the cross-chain transaction publication to $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$.

We assume the cryptographic primitives, including hash function and digital signature, of relay chain and parachains are secure. Moreover, the zero-knowledge proof algorithms can be deployed in distributed environment without trusted setup [42] [14].

As Interpipe establishes cross-chain state channels by the cooperation of three blockchains $\mathbf{R}$, $\mathbf{P}_{l}$, and $\mathbf{P}_{r}$, we assume the proportion of the corrupted consensus participators in each blockchain system is bounded by the threshold to ensure security. In the existing PoW [43] and PoS [44] protocol, it requires the proportion $\alpha<1/3$.

Moreover, we assume that an adversary is mildly adaptive [44]. Specifically, for a group of honest nodes $\{node_{1},\dots,node_{x}\}$, the adversary cannot instantly corrupt every node in $\{node_{1},\dots,node_{x}\}$, and the corruption may only succeed after a sufficiently long period of time. Otherwise, the adversary possesses enough power to effortlessly control the majority of blockchain nodes, and overthrows the proportion $\alpha<1/3$ or the security threshold in any node group.

Based on the above assumption, we can ensure persistence and liveness [45] of blockchain transactions. Moreover, we ensure a stable block time, as the block generation process is controlled by mining difficulty [46] in PoW consensus protocol or consensus slot [44] in PoS consensus protocol.

• •

  Transaction persistence states that once a transaction goes more than $k$ blocks deep into the blockchain of one honest consensus participator, it will be included in every honest participator’s blockchain with overwhelming probability.

• •

  Transaction liveness states that every transaction originating from an honest user will eventually end up at a depth of more than $k$ blocks in an honest consensus participator’s blockchain, and an adversary cannot perform a selective denial-of-service attack against the honest user.

• •

  Stable block time states that the average time it takes for new blocks to be added to a blockchain remains consistent and predictable over an extended period.

• •

  Consistency: Parachain $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ can synchronize the real-time state proofs of each other. A cross-chain transaction $ct$ can be recorded into both $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$, with their consistency being kept.

• •

  Resistance: It is hard for an adversary to interrupt the cross-chain synchronization between $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$. Resistance relies only on the security guarantees in $\mathbf{R}$, $\mathbf{P}_{l}$, and $\mathbf{P}_{r}$ systems.

• •

  Liveness: Any two users respectively located in $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ systems can have opening, updating, closing, and disputing to a cross-chain state channel.

• •

  Efficiency: Any user in $\mathbf{R}$, $\mathbf{P}_{l}$, and $\mathbf{P}_{r}$ systems can have cross-chain verification to the state and transactions in $\mathbf{R}$, $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$ with low storage and computation overhead.

Cross-chain synchronization has two parts, which are state synchronization and transaction synchronization. First, state synchronization is the underlying design. It is recursively executed in rounds, enabling two parachains to keep real-time records of the state proofs of each other. Based on the real-time state proofs, we achieve transaction synchronization. It means that users can record one cross-chain transaction $ct$ into the two parachains $\mathbf{P}_{l}$ and $\mathbf{P}_{r}$, and keep their consistency.