---
title: Delphinus Cross-Chain Solution
tags: zkp
geometry: margin=1.5cm
fontsize: 8pt
---
# 1 Introduction
Delphinus CrossChain Solution is a universal firmware which synchronise states between different smart contracts on different block-chains. In the world of block-chains, synchronization challenges are two-folded. Firstly contracts from different main block-chain can not communicate with each other which makes it hard to establish a trustworthy communication channel for them to share and maintain a universal state between each other. Secondly, transactions on different block-chains can hardly ordered thus conflicts are common and we need a novel way to avoid and handle these conflicts. Delphinus Cross Chain framework is a zksnark based multi-blockchain aggregator on top of which rich cross chain application can run safely and efficiently.

# 2 Background
As a new distributed computing paradigm, block-chain is rapidly evolving in areas such as digital finance and cryptocurrency. However, existing block-chain projects adopt different blockchain architectures and protocols and, as a consequence, it is difficult in general for different block-chain systems to flow information to each other. Thus different block-chains themself are born isalated islands which brought limitations to the overall usablility, functionality and scalability of block-chain technology.

Recently, the growing demand of flowing value between different chains stimulates the demand of secure and consistent cross chain exchange protocals for cross-chain communication and book-keeping. In order to address the safety, liveness, permissionless and atomicity problem of various protocals, and bulid trustworthy consensus between different block-chain networks, cross-chain techniques received a lot of attention.

In general the difficult part of cross-chain communication is that there is no proper way for a block-chain transaction to confirm whether a transaction was executed successfully in another block-chain. This is because block-chain system is a decentralied computing system that contains a large set of nodes connected over a peer-to-peer network and a successful transaction needs to be audited on multiple nodes, which means that a transaction's result can only depends on block-chain's internal states otherwise the result of a transaction will be inconsistant between different auditing nodes.

This build-in drawback of block-chain, makes it hard to execute a group of transactions involving different chains so that either all of them or none of them succeed on different chains. For example, suppose that Alice would like to swap buy 1 token from Bob on block-chain A by spending 1 token on block-chain B. To achieve this swap, two transactions are bundled:
* TxA on chain A: Alice get a token from Bob on block-chain A.
* TxB on chain B: Alice pay a token to Bob on block-chain B.

TxA and TxB needs to be executed in a safe mannar that either both of them succeed or both of fail. If it is not the case, then either Alice lose a token on block-chain B or Bob lose a token on block-chain A. However since TxA can not access any info of TxB, certain protocal needs to be designed to achieve a safe swap.

Many protocals are developed in the literature including time hash lock, spv, etc and most of them introduce a relayer to establish an information chanel from source block chain A to target block chain B as follows:

digraph hierarchy {
rankdir="LR"
nodesep=1.0 // increases the separation between nodes
node[color=Black,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Black] //All the lines look like this
"Chain A" -> {
    "Relayer"
}  [label="emit event E"]

"Relayer" -> "Chain B" [label ="report event E"]

}

The major security problems regarding the above model is that we require the relayer to be honest and can be identified. A centerlized relayer can be build such that chain B only accepts info reported from a trusted relayer. In such solution, the trusted relayer sign all their messages with their private key and txB in chain B checks signature accordingly. The problem of a centerlized relayer is that the relayer becomes one of the most important trust base for the protocal to work which may leads to SIOF(single point of fail) if relayer is hacked or misbehaved.

To take a step further, if we consider a protocal between Alice and Bob that such that involves three transactions $TxA_0$, $TxB_0$ and $TxA_1$ in the following order:

let x = TxA_0 in
let y = TxB_0(x) in
TxA_1(y)

Then it follows that the safety property require transactions involved in the above bundle to be either all succeed or none of them succeed. Suppose a protocal is designed to help carrying out such bundled transactions between native block chains then we can define the safety, permissionless, liveness and atomicity properties of the protocal as follows:

* permissionless: whether every nodes of certain blockchain are allowed to join the communication network.
* safety: whether all state updates for a single transaction are either successful or fail on all involved block-chains.
* liveness: whetere all valid transaction will eventually success on all block-chains
* atomicity: parallel successful transactions has a linearlizated equavalence so that the consequent state of a group of parallel transactions $tx_i$ is equavalent to performance the transactions sequencely in a special order.

There are many existing protocals designed for specific senarios and they focus on perserving different properties with various trust base. Delphinus Cross-Chain Solution targets to achieve liveness, safety and permissionless properties by using zero knoweledge proof to provide a univeral layer to synchronise states between different smart contracts on different block-chains and this layer together with its communication protocal can be used as a cross-chain communication framework.

The main idea of our protocal is that instead of executing transactions in native block chains we map local state $s_i$ of native block chain $c_i$ into our aggregator chain to form a global state $s = \sum_i\left\{s_i\right\}$. When a bundled transaction is triggerd, we perform a simulating run of the bundled transactions over $s$ to get a result state $s' = \sum_i{s_i'}$ and create zero knowledge proofs to convince native chain $c_i$ that after the bundled transaction has been executed, their local state has to be changed to $s_i'$.

digraph hierarchy {
nodesep=1.0 // increases the separation between nodes
node[color=Black,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Black] //All the lines look like this
"Chain A" -> {
    "ZK Relayer State S0"
}  [label="state mapping"]
"Chain B" -> "ZK Relayer State S0"
    [label ="state mapping"]

"ZK Relayer State S0" -> "ZK Relayer State S1" [label="run transaction"]
"ZK Relayer State S1" -> "Chain A" [label ="synchronize by providing zkp"]
"ZK Relayer State S1" -> "Chain B" [label ="synchronize by providing zkp"]

}

Before presenting the details of our solution, we would like to give a brief overview about a few existing cross-chain communication protocals and discuss their safety, permissionless, liveness, and atomicity properties.

## 2.1 Related Protocal Overview
* Notary schemes:

The main idea of notary schemes is to elect one or more trusted nodes as notary public and verify transactions in different blockchain networks through notaries and also through the notary to prove to the nodes in the other blockchain network. Therefore in a sense as the data exchange between different blockchains is completely managed by notaries.

The centralized notary schemes is high operation and processing efficiency, but suffer with single point of failure problem. Therefore, a multi-sig notary scheme may been proposed inorder to reduce centralized problem. However, this multi-sig notary are surely non-permissionless and needs extra protocals to ensure liveness.

* SPV: Simplified payment verification

SPV is a special case of one direction state pining. In such protocals, block header of A and a merkle proof of a particular transaction was monitored and sent to target blockchain B. Blockchain B accept the transaction trough calculating the partial merkle tree hash and compare it with the block header of blockchain A. The liveness properties of this approach depends on the liveness of monitors of A and the safety property relies on the blockheaders are reported to B honestly.

* Two way peg:

A 2-way peg (2WP) works like a two way SPV which allows the transfer of assets from one block-chain to another and vice-versa. The assets are technically not transferred, but temporarily locked on the source block-chain while the same amount of equivalent tokens are released in the target block-chain. The transferred asset can be withdraw when the equivalent amount of tokens on the target block-chain are locked again. The problem with this scheme is that the transfer is not finished until the target block-chain has release the equivalent amount asset. Therefore any 2WP system must do compromises and rely on assumptions about the honesty of the actors involved in the 2WP.

* Sidechains:

The concept of sidechain was first proposed in 2014, main goal of sidechain is to extend the scalability and functionality of the block-chain system. When using sidechain as an trusted centralized entity in a 2-way peg system, it can be used as a standalone transaction dealer.
Sidechain can enforce the security of transactions on it self by by implementing a protocol which can be validated by consensus. Since the side-chain needs to update state changes back to the underlying block-chains the block-chains needs to trust or verify the transactions sent out by sidechains. Usually the cost of trust(a vulnerable sidechain) or verifiying(gas fee) is very high. The safety properties again relies on whether observation of source chain can be honestly reported to the side chain and whether the verifier on target chain can reject all fraud transactions.

Liveness of communication based on sidechains relies on how robust the sidechain itself is and whether all the transactions happened on side chain will get reported to the target chain eventually. One can refer to Plasma: Scalable Autonomous Smart Contracts for some improved ideas of sidechains.

* Cross Chain Gateway and relays:
Cross Chain Gateway with relays is another extension of the idea of state pinning. While it enables blockchain interoperability applications like cross-blockchain token transfers, the safety properties are got at the cose of storing every single block header of the source blockchain. In general the cost of saving such state is very expensive.

In conclusion we have the following table:

| protocal | liveness | safetyness | permissionless | atomicity |
|----------| ---------| -----------| ---------------| ----------|
| Notary schemes| yes | yes | no | implementation may vary |
| SPV | conditinal | conditional | depends on relay system | yes |
| Peg | conditional| conditional | depends on relay system | yes |
| SideChain| yes | yes but costy | no | depends on sidechain implementation|

## 2.2 Brief of Delphinus Solution:
Delphinus cross-chain layer2 derives the basic ideas from multi-way sidechain (multiple blockchains with a shared sidechain) and solves the trustworthy problem of the third parties by verifying the computation on sidechain via zksnark proofs.

We present the whole picture of our solution first and explain it briefly by a case study of the process of the standard transfer and withdraw and explain how zero knowledge is applied so that the safety and liveness properties holds. In Chapter 3 we describe each components in detais and in Chapter 4 we explain the trust base of our solution and prove that under the trust base our solution has safety, permissionless and liveness properties. In chapter 5 we show that instead of atomic property, our solution has a linearization property which is slightly weaker but since we have liveness transaction will eventually get finalized. In Chapter 6 we present a incentive strategy to keep we have enough decentralized nodes so that 2/3 majority attach is hard enough as stated in our trust base.

**Bundled cross-chain transaction:**
Given a group of Block-chain $C_{k\in[0,N)}$, we say a transaction is a bundled cross-chain transaction $tx$ if it is composed of a sequence of transactions $\left\{tx_j^{k_j}\right\}$ such that each $tx_j^{k_j}$ is suppose to be executed on $C_{k_j\in[0,N)}$ and the inputs of each $tx_j^{k_j}$ depends on the outputs of previous transactions.

tx(params, \left\{s_i\right\}) {
    let params_0 = tx_0(s_0^k_0) in
    let params_1 = tx_1(s_1^k_1, params_0) in
    ....
    tx_j(s_j^{k_j}, params_j-1)
} 

**Chain State:**
The whole state of a native-chain $C^k$.

**Local State:**
In a bundled cross-chain transaction, each local transaction $tx_i^{k_i}$ is executed on its native chain $C_{k_i}$ that changes local state $s^{k_i}$.

**Global State:**
We define the global state of block-chain set $\left\{C_k\right\}$ to be the product of all local state $s^k$ of $s = \Pi_k s^k$.

**Layer2 Chain:**
We call the extra block-chain which stores the global state $s$ as a layer2 chain to distinguish between native-block chains is $C_{k}$.

**State pinning:**
State Pinning is defined as including the state of one blockchain in another blockchain. In our scenario, we denote $h_k$ pins the state $s^k$ if $h_k$ is generated from a collision-resistant hash of $s^k$.

**Side effect:**
We denote the changes of $tx_i^k$ on chain-state $C_k$ other than the partial state $s_k$ to be the side effect $e_k$ of of $tx_i^k$.

## 2.3 A case study of cross chain transfer

As a case study, we focus on a standard simplified asset transfer process from Alice on chain A to Bob on chain B through a liquid provider.

Firstly we define the native-chain set $\mathbb{C}$ to be ${C_A, C_B}$. The local state of $C_A$ is defined as

C_A = state {
    alice: number
}

C_B = state {
    bob: number
}

The global state of $\mathbb{C}$ is

gState = state {
    ca: C_A,
    cb: c_B
}

A transfer transaction $tx$ can be defined as follows:

tx = transaction transfer(amount) {
    token1.transfer(Alice, amount, liquidProvider);
    tx_0^A(amount);
    tx_1^B(amount);
    //if （liquid.amount > amount) {
       token1.transfer(liquidProvider, amount, Bob);
    //}
}

where $tx_0^A$ and $tx_1^B$ are local transations for $C_A$ and $C_B$ as follows:

tx_0^A(amount) {
    C_A.alice = C_A.alice - amount
}

tx_1^B(amount) {
    C_B.bob = C_A.bob + amount

}

Also the side-effects $e_0$ (deposit) of $tx_0^A$ is

token1.transfer(Alice, amount, liquidProvider)

while the side-effects of $e_1$ (withdraw) of $tx_1^B$ is

token1.transfer(liquidProvider, amount, Bob)

To execute the transaction safely we using the following protocal:


1. Deposit: User Alice transfer a certain amount of money into a proxy contract and that contract has a pinned state of layer2 and an actually state in which a map between user and its unsynced amount of deposit is stored. This deposit activity will captured by offlane monitors or relayers and reported to layer2. Here we do not assumes that or relayers are honest but will uses a multisig consensus scheme between all monitors or relayers to ensure all the events are reported honestly and this consensus algorithm will aslo been encoded in the zk circuit on Layer2) Also, Alice are allowed to withdraw unsynced amount after a certain amount of time(based on blockheight). This HTL(hash time lock style) protocal assumes that our layer2 has the advatange of produce correct zk confirmation proof as it knows the entire merkley tree.

2. Perform transaction $tx$ on Layer2:
Once user has deposit their assert into layer2 state, user can perform various predefined functions on layer2 in a decentralized manner just like the side chain solution. However like all side chain solutions a consensus based chain requires audit nodes to validate transactions and can suffer from a majority attack. Delphinus cross chain solution uses zk to validate the transactions in blocks so that all the calculation have to fit in to a valid call of predefined layer2 functions and thus even the majority of the audit nodes are hacked, they can only perform ordering attack that leads to deny-of-service of some of the transactions.
Once the $tx$ was fully performed, Layer2 will broadcasting this transaction together with its proof to native-chain $C_A$ and $C_B$.

3. Withdraw asset on target block-chain.
The withdraw activity is triggered by a layer2 api which will generate the withdraw event. The withdraw event will be packed with other events and then been reported to the target block chain together with a zk-proof. This zero knoweledge proof has the ability to show that all the events are generated via a sequence of valid performing of redefined functions.

After the proxy contract on target blockchain validates the zk-proof, it will peform the sideeffects of each transactions accordingly. For most of the layer2 transactions there side-effect on target chain is nothing, but for withdraw and deposit transaction, they have special side effects.
* withdraw (on target proxy contract): transfer asset from proxy contract to target address
* deposit (on source proxy contract): check the deposit amount is less than the unsynced deposit amount in the proxy chain.

## 2.4 How zero knowledge proof technique is applied:

For correctness, the zk verification on proxy contract makes sure that all transactions are performed under predefined functions and the resulting state are correctly calculated (merkle root hash is pinned). The desposit sideeffect of amount checking makes sure that the custody of locked tokens is reported to layer2 honestly and the transfer triggered by withdraw is performed at end which makes sure that the amount about to withdraw is a consequence of valid transactions.

Regarding the cost problem of state pinning, since Dephinus uses batched transactions to reduce the cost of signature check and snark proof check, the problems of the high cost of state pinning and signature check are also reduced to a acceptable level.

# 3 Protocal Details:
## 3.1 Abstract Components of a Single Delphinus Layer2 Node
Delphinus 's target is to provide a universal layer to manipulate and synchronise the global state between various block-chains which support smart contract. To achieve this, delphinus architecture has four abstract components:
* Delphinus Layer2:
* store the whole state (including the state merkle hash).
* order layer2 transactions under certain consensus.
* process transactions and update the whole state accordingly.
* emit transaction events (with execution order).
* Delphinus Layer1 relays:
* handle message events emit by guest chain
* handle ack events emit by guest chain
* forward message carried by guest chain message events to Delphinus Layer2
* forward message carried by guest chain ack events to Delphinus Layer2
* Delphinus Layer2 relays:
* monitor transaction events from Delphinus Layer2.
* calculating transaction execution proofs.
* calculating proofs of consensus.
* submit proofs to guest chain for validation and finalize.
* Delphinus Layer1 Proxy Contract:
* store the partial state of a particular guest chain.
* verifies the proofs of the batched transactions.
* process the sideffects of each transactions

For example: Suppose that we have two block-chains $\mathcal{A}$ and $\mathcal{B}$. A Delphinus transaction involves the following entities.


* a proxy smart contract $\mathcal{C}_A$ on $\mathcal{A}$ (Trusted).
* a proxy smart contract $\mathcal{C}_B$ on $\mathcal{B}$ (Trusted).
* a $\mathtt{L}2$ handler node that handles transactions.
* a bunch of relayers $\mathcal{R}_A$ to monitor events for $\mathcal{C}_A$.
* a bunch of relayers $\mathcal{R}_B$ to monitor events for $\mathcal{C}_B$.
* a bunch of relayers $\mathcal{R}_{L2}$ to monitor events for $\mathtt{L}2$.

Except the Layer1 proxy contract, we arrange the rest(Layer2 Handler, Layer2 Relayer, Layer1 relayer) into a Delphinus Layer2 Node and the Delphinus Cross Chain Layer is a block chain contains decentralized Delhpinus Layer2 Nodes that works together to synchronsize and alter states between guest block chains.

## 3.2 Transaction lifecycle
An application in Delphinus is a set of operations ($f: S \rightarrow S$) which are defined as how the global state (S) of the appliation can be changed. In Delphinus the global state of an application is compressed as a Merkle hash tree and pinned in all the guest chain prox contracts.

For a transaction to be successfully executed in Delphinus Cross Chain Protocal, it experience four stages: Consensus Stage, Operating Stage, Proving Stage and Finalizing Stage.

Uesr/Guest Chain -> Layer2 Relay: init tx monitored by Layer2 relay
Layer2 Relay -> Layer2 Relay: generate a block via consenus and provide zk evidence.
note left of Layer2 Relay: consensus stage
Layer2 Relay -> Layer2 Relay: add tx into blocks and generate witness
note left of Layer2 Relay: operating stage
Layer2 Relay -> Layer2 Relay: generate and batch zk proofs
note left of Layer2 Relay: proving stage
Layer2 Relay -> Layer1 Contract: broadcast and verify
note left of Layer1 Contract: finalizing stage

* Consensus Stage: As a decentralized protocal, a transaction will not get handled until it is collected in a block. Each blocked is produced by an elected node under a pre-defined consensus algorithm (see 3.2). A node who wins the consensus game needs to provide a zk proof which will later be used as evidence to finalize all transactions within the block on guest proxy contract.
* Operating Stage: At operating stage, an operation is simulated on Delphinus Layer2 and changes the global state (S) thus changes the Merkle root in a sandbox. During the simulation, all the witness needed to create a zkp for it is prepared and stored. Since all transactions are handled sequencely regarding their order in a particular block, their witness are stored in the same order so that they can be batched in the proving stage.
* Proving Stage: After operating stage, the Delphinus Layer2 relay will generate all the proofs for every transaction and compress proofs into a single zkp proof. This proof is then appended after the transaction arguments in the block with a updated merkle tree hash.
* Finalizing Stage: Once a proof of batched operation sequence is generated by Delphinus Layer2 monitor, it will broadcast to various underlying block-chains. Each block-chain will verify the proof and then send acknowledge back to the Delphinus Layer2 to finalize the transaction.

## 3.3 Consensus between Delphinus Layer2 Chain Node

There could be a few ways to arrange decentralized nodes to form a decentralized chain structure and to achieve it we need to consider the following common blockchain questions:

* Who is going to decide the order of the layer two transactions. (consensus protocal).
* How to enroll and identify a valid node.

Morever, since our goal is to synchronize states between guest chain we need to convince guest chain that our generated block are produced under the consensus protocal. Thus we need to encode the conseneus algorithm and its result into a zk proof so that we can confirm guest proxy contract that the blocked which contains all transactions is generated legally.

(fig TODO: data layout of a block)

### 1. Block producing
We uses a modified pow consensus algorithm to form a standard BFT system between Delphinus Layer2 Nodes. Recall that the pow consensus algorithm requires a node to put effort into generating a special hash before it can produce a block legally, our consensus algorithm requires a node to calculate the batched zero knoweledge proof of a sequence of transactions and the one who has produced a zk proof of the longest sequence of transaction between all existing nodes gets the authority to produce the block.

Since we need to convience Layer1 such that a batched transaction proof is send from a legal node, we need to encode the consensus protocal into the batched transaction proof so that the consensus protocal are ensured during verify in guest chain as well.

Every layer2 node in each block generation stage place a vote and send a signature of the vote to their voting target. Suppose that two thirds of the nodes in the system are honest then it follows that only one potential node will win the voting game and this particular node has the authority to produce a block.

When producing the block, the winner node need to calculated the zkp proof of all received signatures and adding the zkp proof to his generated block. After the winner node append all zk proofs of all transactions into the block, it aggregates all the proof into one zk proof so that a full block was generated.

Voting Node -> Target Node: send signature of voting message
Target Node -> Target Node: collecting enough voting.
Target Node -> New block: adding zkp for voting
Target Node -> New block: add transactions
Target Node -> New block: add zkp proofs for transactions

### 2. Register and identify a valid node.

* Valid a voter:

When a node receive a voting from other node, it needs to validate that the sender is a valid voter. If the sender is an invalid node (eg, a malformed node without registration in) then proof of sufficent voter will fail at the stage of finalize thus waste the computing source of the node who is voted.

Recall that all the valid voter is arranged in a merkle tree whose root hash is pinned in the guest proxy contract. The voter needs to provide a identity proof (in forms of zk proof) to show that his id(or voting address) is one of the merkle tree leaf nodes.

Once a node receive a voting from voter $V$, it needs to verify the identity proof of $V$ first before it push it to the list of his supporters for next block generation round.

* Register a node:

Node registration is a layer2 transaction that has side effect of updating the merkely tree root hash of nodes in guest proxy contract. It is every node's responsibility to keep the registeration tree updated so that the root hash are consistent with the pinned hash in the proxy contract.

* Send a valid vote ticket:
A vote ticket contains two parts, a signature and a validation proof. The signature is signed from the current block height together with merkely root hash of all valid voters. The validationg proof is a zero knowledge proof proves that the voter is one of the valid voters.

## 3.4 Proof of a single cross-chain bundled transaction:
As we discussed before, we process bundled transactions of the global state on Layer2 and each transaction is defined by a bunch of operations $(f: state \rightarrow state)$ that alter and query the global state $s$. Since the global state is pinned on native-chain by the merkle hash root of the state, a zero knowledge proof of bundled transactions $tx$ is a proof that ensures the change of merkle hash root change is valid.

<svg version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px" viewBox="0 10 300 100" xml:space="preserve">
<image xlink:href="https://i0.wp.com/delphinuslab.com/wp-content/uploads/2021/10/delphinus-refine.png" width="300" height="160"/>
</svg>

Layer2 state can have different representation as to serve different usages in Delphinus cross chain platform. For instance, in the operation stage, Layer2 state is encoded in a specific blockchain(for example a substrate pallets) while in the proving stage, it is encoded in a standard merkley tree.

Since Layer2 global state can be encoded into a list of Merkle Tree leaf nodes from which a Merkle hash tree can be built. A snark proof of $f(s) = s'$ is a snark proof generated from the following circuit $$ constraints = \begin{cases} r = hash(mht) \\
mht' = encode(f(decode(mht)))\\
r' = hash(encode(f(decode(mht))))\end{cases} $$
At operation stage, $s'$ is calculated and stored in the Delphinus Layer2. Further more, an operation Event is fired after the operation stage which will be captured by the Delphinus Layer2 monitor which will generate the related snark proof.

### 3.4.1 Merkely Tree Encoding of Global State
Merkle tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.Each data block has a unique Merkle Tree Index(MTI) and each MTI encodes a unique path from top to leaf.

Root
/ | \ \
/ | \ \
Layer1 | Node1 Node2 Node3 Node4 | [0,2^2-1]
Layer2 | . | [0,2^4-1]
. | . | .
. | . | .
. | . | .
Layer16 | LeafNodes | [0,2^32-1]
| | | ||
| Data | Address Space

### 3.4.2 Proof of Merle leaf update
Suppose that $p = [p_0, p_1, p_2 \cdots p_n]$ is the MTI of data $D_p$ where $p_k \in [0,4]$. It follows that to calculate the root hash after the modification of data of $D(p)$, we need to calculate new hash of $H(p)$ at each level by the fomular
$$
H_k(p) = H(p_0, \cdots, p_k) = hash_{i\in [0,3]}(H(p_0\cdots p_k, a_i))
$$
where $a_i = \lfloor p_{k+1} \rfloor + i$.

Thus it follows that the entire constrains of merkley tree can be represented as follows:
* before modification
$$\begin{cases}
H(p) = hash (D_p)\\
H_k(p) = hash_{i\in [0,3]}(H(p_0\cdots p_k, a_i))
\end{cases}
$$
* afer modification
$$\begin{cases}
H'(p) = hash (D'({p}))\\
H'_k(p) = hash_{i\in [0,3]}(H'(p_0\cdots p_k, a_i))
\end{cases}
$$

Put it all together the ***merkley_verify*** function takes in path $p$, the old and new value $(D(p_0), D'(p_0))$, $k$ hash values $H(s_i), i={0...k-1}$, the initial and final root hash $(H(p_k)$, $H'(p_k))$ to produce a circuit with the above constraint.

### 3.4.3 Proof of a full transaction:
A full transaction $tx$ is a data transform function $f$ performed on multiple Merkley leaf nodes $L(p)$ that changes $D(p)$ to $D'(p)$. In Delphinus Cross Chain Node $f$ is defined as a combination of the following:

1. A simulator which simulates the state update and produces witness of transactions. Those produced witness then become ingredients of zk proofs that will be generated from Delphinus Cross Chain Relayers.

2. A state transformation which can be written in the form of zk circuit constraints defined in **3.4.3**. This circuit will be used to generate the zk proof of every execution results.

### 3.4.4 Circuit Details of a full transaction:

* **Circuit targets**:
The circuits defined for a transaction can help L1 properly verify the following thing:

1. A Command is sent by an invalid end user (by validating the signature and command target).
- Validate the signature of the command.
- Validate that the command's target assets belongs to the user.
- Check the public key in storage.

2. The storage is properly modified according to the command.
- The transaction logic is written into the circuits.

* **Circuit Inputs**:
1. A batch of commands (See appendix of command format).
2. A secure hash of the batch of commands, thus we can make these commands as private.
3. Signatures of these commands, they can be private because to attack the cuicurts by giving a wrong signature is cryptographically difficult.
4. Merkle tree info (See 2.2.2 for details)
- inital root hash $H(p_0)$
- final root hash $H(p_k)$
- pathes that can help the circuits to verify the merkle tree change. These path are private, because the hash function for the merkle tree is cryptographically secure hash.

* **Circuit constraints**:

1. The hash of the commands equal to the input hash.
2. The signature of each command is valid.
3. The public key should be the correct one stored in merkle tree (so it also needs to verify the merkle tree path for the public key).
4. Each command has multiple steps on changing the merkle tree, so it needs to verify the each merkle tree pathes, and also verify the changes (usually it only changes a leaf value, so the circuits can calculate the root hash after the change).
5. The merkle tree root is truely changed from the start one to the end one through these change steps.

### 3.4.5 Finalize of transaction $tx$.
Although $tx$ is always a monadic function on Layer2 state, it could have side effects during the finalization stage in guest chain proxy contract. For example, if a user would like to withdraw some asset from Layer2 to guest chain, then during the finalize procedure a transfer from guest chain proxy contract to the target accounnt of the withdraw is executed.

(figure: customer function )

In Delphinus native-chain contract, side effects are performed after the proof the of execution of tx is verified.

## 3.5 Aggregate and broadcast multiple tx proofs.
Each time Delphinus Layer2 relayer captures a full block generated by Layer2 tx handler, it opens the block and generate a zk proof for each transaction and then aggregate the consensus proof together with all transaction proofs into one zk proof as the final proof of this block. After the final proof is added into the block, Delphinus Layer2 relayer sends the final proof together with all the transactions contained in the block to delphinus proxy contracts for finalize.

zero knowledge proof aggregation is a zkp technique that can aggregate a sequence of proofs into one proof. The benifit of aggregating zk proofs is that it can reduce the calculation workload of verification. Recall that our layer2 relayer will generate a zk proof for each user transaction and each zk proof ensures that a transaction $tx_k$ changes state from $s_k$ to $s_{k+1}$ by proving that the root of merkely tree hash $H$ changes from $hash(s_k)$ to $hash(s_{k+1})$. An aggeregated proof batches all transaction proofs and generate a proof ensures that by execution a sequence of transaction $tx_0, tx_1, \cdots, tx_{n-1}$, the layer2 state changes from $s_0$ to $s_n$.

Moreover, since the layer2 relayer needs to provide both the consensus proof and the aggregated transaction proof, we can further batch these two zk proofs into one.

## 3.6 Guest Proxy Contract:
Guest Proxy Contract contains two parts: **guest chain interface** and **verification interface**. Both of them manipulates the guset chain local state. Guest chain interface includes invoke and revoke which allowes guest chain user to invoke or revoke a message. Verification interface is called by Delphinus cross chain node to finalize transactions.

(fig: local state of guest proxy contract)

### 3.6.1 Guest chain interface

When a user invoke a **guest chain interface** a transaction info together with the current block height ($h$) is recorded in the pending queue of the guest local state. The invoker can revoke his invocation any time when the transaction remains in the pending queue after a fixed amount ($\delta_h$) of block. This means Delphinus cross chain nodes have to notice and handle this event and finalize this event within $\delta_h$ blocks.


### 3.6.2 Verification Interface
Verification interface verifies the ZK-SNARK proof generated by the L2 Relayer(see section 3.5).

  function verify(
      uint256 l2account,
      uint256[] memory tx_data,
      uint256[] memory verify_data, // zk proofs 
      uint256 vid,
      uint256 nonce,
      uint256 rid
    )

Recall that only the winner of Delphinus voting consensus of the current finalize round (rid) have the authority to invoke verification interface at round $rid$. It follows that the verify function first check the voting proof to ensure that the sender is the winner of round $rid$ and then check every transaction encoded in tx_data is executed honestly via verify the zk proof encoded in verify_data. If both check pass, guest contract will perform all the sideeffects of transactions on guest chain accordinly.

## 3.6.3 Transaction side effects during finalize.

* Invoke
* A invoke tx on layer2 must be related to a invocation call on guest contract. Since every time a guest chain invocation will cause a record of pending invocation to be added in to the pending list in the local state of guest contract.
* Once a invoke tx is verified, the side effect of that tx is removing the invocation record in the pending invocation list.
* Once a invocation was removed from the pending invocation list, its sender lose the capability to withdraw it.
* Deposit is a special case of invoke.

* Callback
* Callback is a special transaction that is invoked through Delphinus Cross Chain Node which tries to trigger a certain callback function from Delphinus Cross Chain to guest Chain.
* Once a callback tx was verified, its side effect is to calling a relataed guest contract api according to the tx info.
* Withdraw is a special case of callback which calles the trasfer api.

* General Cross Chain Node Transaction:
* All general cross chain node transactions are handled on Cross Chain Nodes thus changes the cross chain state.
* As the cross chain state is pinned to guest contract there is no other sideeffect during the process of finalization.

## 3.7 Guest Chain Relay
Guest chain relay is responsible for monitor guest chain events and notify layer2 tx handlers by forwarding them. Guest chain relay needs to sign the event with CrossChain Node's consensus id so that guest chain relay from another CrossChain Node could not forward invoking transaction to other's Layer2 transaction handlers. If a voted CrossChain Node failed to finalize their transactions in guest chain prox contract, then it either failes to calculate a correct aggregated proof of transactions and voting result or it does not pass the checks in the sideeffect of invoking transactions in guest contract. In later case, the failed node could be a malicious node who provides invoking transactions that does not exist on guest chain.

# 4 Permissionless and Liveness property

Delphinus cross chain is a decentralized platform that any one can join the network to help synchronizing cross chain bundled transactions. Thus to show that Delphinus cross chain is a permissionless system, we need to show that althought any running Delphinus cross chain node can play the role of synchronizing cross chain transactions, the data stored in Delphinus cross chain is consistent and all local data stored in distributed nodes converges.

## 4.1 Proof of voting result.
Give a group of bundled transactions $\mathbb{B} = \left\{btx_i\right\}$ submitted simutaneously. A valid trace from a start point of global state $s$ is a seqeunce of state $s_0=s, s_1, s_2, \cdots s_n = s'$ such that $s_k = btx_k(s_{k-1})$ where $btx_k \in \mathbb{B}$.

It is obvious that different order of $btx_k$ from same $\mathbb{B}$ can leads to different valid traces which means all attending nodes in the Delphinus cross chain needs to vote for a unique block producer to generate a trace that is valid globally.

Each round before voting, every attending node's public key is registered in a merkley tree and the root hash is pinned in all native chains and nodes. We assume that each node will synchronize the root hash themselves before vote since if they vote with a wrong root hash then their vote ticket is ignored when producing the final zero knowledge proof of the voting result.

To vote a node, a voter needs to sign a voting message and send the signed voting message to the target it votes. Inside the message it contains the merkle root hash of all attendence. Once a node receives a sufficient number of voting tickets that carry the correct attendence hash it will produce a zeroknowledge proof $\mathbb{P}_v$ which shows that the total number of tickets reachs two-thirds of the total number of voters and all of them has the correct attendence hash.

## 4.2 Block generating:
As mentioned in 3.3, after the winner node calculated the zkp proof of all received signatures, it can start producing a block which represents a valid sequence of bundled transactions $btx_i$. This process is executed locally and the block producer can pick any order of $btx_i$ in the final sequence as long as it can generate a zkp proof of the simulation $btx_i$

Target Node -> Target Node: collecting enough voting.
Target Node -> New block: adding zkp for voting
Target Node -> New block: add transactions
Target Node -> New block: add zkp proofs for transactions

Once the block was generated, it needs to be send to the native block chain $C_i$ to finalize before it can be recorded in the Delphinus Layer2 ledger. Since Delphinus nodes are permissionless, the liveness of the whole system should not relay on the liveness of a particular node. Thus we need to provide a protocal to make sure the winner node can not broadcast the block partially. For example if the winner only broadcast the block to a subset of the native block chains then we need a strategy to continue broadcasting the block even if the winner node quit after generating the block.

To solve the partial synchronize problem, we record the proof data on the native local chain $C_i$ so that if a block was synchronized partially, then all Delphinus node will notice the recorded proof and can continue broadcasting the proof until it is fully synchronized.

Moreover, if the winner does not broadcast its block to any of the local chains, then the voter need to trigger another vote to skip the current round of block producing and send the skip signal to all native block chains. Once all the native block received the skip signal, they will not accept any block with the current round number and the next round of block generation can start. If one of the native chain received the synchronizing call of the generated block, then all the nodes need to perform a revoke-skip vote so that they can revoke the skip signal on native block chains.

## 4.3 Liveness property
Based on protocal defined as above, we abstract the state transition diagram as follows:


Notice that in the protocal, there exists state $S_5$ in which both the block generation voting and skip voting are fired. If skip signal was fully applied to all native chains then the current round was skipped otherwise if any one of the native block chain receives the generated block, then our protocal ensures that all the other nodes will receive the same generated block as well. Thus the final state of all native-block chains converges to the same state.

# 5 Safety property
Recall that for a bundled transaction $tx = {tx_i^{k_i}}$. The safety property of a protocal to carry out $tx$ is that either all $tx_i^{k_i}$ are succeed or none of them succeed.

To prove the safety property of Delphinus cross chain protocal we first show that the safety property holds if a particular transaction $tx$ does not have an init transaction or any sideffects and then we can further prove that if all side-effects are safe then the safety property still holds. Moreover we show that for the init transaction of a bundled transaction (if there exists one) to be safe, we rely on liveness property to ensure once the init transaction succeed then all following transactions needs to be finalized or the init transaction can be revoked as it has never executed before.

## 5.1 Bundled Transaction with no init transaction.
since all components $tx_i$ of $tx$ are simulated and performed on Layer2 which means that a proof of the execution of $tx$ can not been generated if any $tx_i$ fails. Once the proof was generated, then the proof can be broad cast to each native chain. Because the proof is valid, it will pass the validation check and by the design of the smart contract the all the local state will update accordingly.

Since the liveness property promises that all native chain will native eventually receive the broadcasting of the valid proof, it remains to show that all local states will be updated accordingly.

Since smart contract is a piece of code that can not been changed once deployed, its behavior is fixed and predictable. Thus we can assume that our proxy contract always perform correctly according to its pre-defined functionality. Suppose that $s$ is the start global state, $tx$ is the transaction and $s'$ is the final state. When our proxy contract receives $MTH(s_k)$, $tx$ $MTH(s_{k+1})$ $\delta_{s_k}$ and a zero knowledge proof $p_{t}(s_k, s_{k+1}, tx)$, our proxy contract will do the following:

* 0. Proxy contract checks that pined local global hash equals $MTH(s_k)$. This makes sure that the current local state $s_k^i$ is consistant with the global state $s_k$.

* 1. Proxy contract verifies the proof $p_{t}(s_k, s_{k+1}, tx)$. Once the verify succeed, it can guarantee that $s_{k+1}$ is a valid final state after simulating $tx$ over $s$.

* 2. Compute the changes of $s_k^i$ and change the local state from $s_k^i$ to $(s_k^i)'$. Since updating local state is a monadic function of local state, it will never fail which means once the proof of $tx$ is verified, local state will be changed correctly for sure.

* 3. Proxy contract performs all the related side effects for each transactions $tx_k$ in bundled transaction $tx$.

We notice that step 3 is the only place that a finalizing call will fail even the proof are correct. To address this problem, we break down side-effects into two categories. The first category contains side effects like emit events or ecording history which are natually safe since it will never fail by design. The second category includes unsafe function calls like assets transfer. This kind of unsafe functions can still be safe if we perform sanity checks in tx.

For example, if $tx_k$ in $tx$ will trigger a side-effect $e_k$ and $e_k$ is safe under condition $P$ where $P$ is a predicate of global state $s$, then we can insert a check after $tx_k$ as following:

...
let s' = tx_k(s);
if !P_k(s') then raise Excepition(sainity check failure)
let s'' = tx_{k+1}(s);
...

Once $tx$ is modified so as above, a valid proof of a correct simulation of $tx$ will ensure not only the final state are valid but all the sainity checks are all valid and $e_k$ will be safe for sure.

## 5.2 Bundled Transaction with an inovke transaction.
A invoke transaction on chain $C_i$ triggers the execution of the who transaction $tx$ and is usually reported to layer2 through an L1 Relayer. The layer2 bundled transaction simulator relies on the honesty of the reporter and if the relayer is hacked it can exploit the protocal by reporting malformed results of the inovke transaction. For example, in the transfer senario, if a report reports the wrong amount of asserts that been transfered from Alice to Bob in Chain A then a successfully finalized $tx$ will trigger a wrong transfer from Bob to Alice on Chain B.

To address this problem and make sure the protocal is safe even the relayer is dishonest, we split the process of the changes of global state $s$ into two stages. At first stage $s$ is changed to $s'$ after invoke transaction and at second stage $s'$ is changed to $s''$ after the whole simulation of $tx$.

The first stage is recored in Layer1 once the invoke transaction is executed and the second stage is encoded by a zero knowledge proof generated from Delphinus Layer2 Chain Node. During finalize, proof of $tx$ now encodes the proof from $s'$ to $s''$. To ensure that the invoke transaction $tx_0$ is reported correctly, the verifier only needs to compare the MTH of local calculation of $s'$ and the hash provided by the Layer2 Node. If the hash are the same, then it means $tx_0$ are reported honestly. More over since $s'$ are checked, $s''$ can be treated as a valid simulation from $s$ to $s''$. In conclusion the finalization steps are listed as follows:

* 0. Proxy contract checks that pined local global hash equals $MTH(s'')$. This makes sure that the current local state $s_k^i$ is consistant with the global state $s'$ after processing invoke transaction. Thus the invoke transaction are reported honestly.

* 1. Proxy contract verifies the proof $p_{t}(s', s'', tx)$. Once the verify succeed, it can guarantee that $s''$ is a valid final state after simulating $tx$ over $s$.

* 2. Compute the changes of $(s^i)'$ and change the local state from $(s^i)'$ to $(s_i)''$. Since updating local state is a monadic function of local state, it will never fail which means once the proof of $tx$ is verified, local state will be changed correctly for sure.

* 3. Proxy contract performs all the related side effects for each transactions $tx_k$ in bundled transaction $tx$.

# 6 Linearity property
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events. In Delphinus cross chain protocal, the linearity property holds trivially. Because in each block generation round only one node wins the right to produce a block, the linearity hold iff and only if the final state simulated in the block can be represented as a sequence of bundled cross transactions $btx_i$. Since each block producer needs to create a zero knowledge proof to show that $s' = btx_k \circ btx_{k-1} \circ \cdots btx_0(s)$, a valid proof already shows the linearity property.

# 7 Conclusion
TODO

# bibliorgraphy
[1] Survey of crosschain communications protocols, Peter Robinson