# Multi-chain Atomic Commit (*MAC*)

This blog will discuss the Multi-chain Atomic Commit (*MAC*) problem. MAC involves the transfer of assets between $n$ parties $P = \{p_0, p_1, \cdots, p_{n-1} \}$ where party $p_i$ transfer their assets to $p_{(i+1)\%n}$ and each party owns the asset on a possibly distinct blockchain, say $L_i$. MAC is vital to solving because it facilitates different use cases, such as supply chains and decentralized exchanges, where more than $2$ parties are involved in the transfer. Similar to the two-party swap, we will use standard HTLC to accomplish the transfer in MAC. Using a signature-based approach, such as [universal swap](), for MAC to claim the assets locked in the contract becomes even worse compared to two-party swaps. This is because the protocol has to deal with $n$ different signature schemes and $n$ different wallets, one for each blockchain. Given this, we will start with the discussion on using standard HTLC for MAC.

<!-- However, using a startdard HTLC for MACCS has its own pros and cons. -->

<!-- The MACCS involving two parties can be solved using hashed timelock contract (HTLC). -->

<!-- However, when the number of parties rises beyond 2 ($n>2$), the standard HTLC is inadequate to solve MACCS (explained below). So we provide the solution to the MACCS that requires a modified version of HTLC. The further blog is organized as follows: First, we will talk about the naive solution to MACCS using a standard hashed timelock contract (HTLC) and issues with the naive solution, specifically when $n>2$. Next, we will talk about our protocol, and lastly, we will discuss the code-level modifications to be done in the standard HTLC to make it compatible to encorporate with our protocol. -->

### MAC when $n>2$

The detailed protocol steps for MAC using a standard HTLC are as follows. Each step in the protocol is represented in the figure below. Note that the arrow in the figure on the right indicates the direction of asset transfer.


**Step 1**: Party $p_0$ generates a random secret $r$ and computes its hash with a random hash function $H(r)$. $p_0$ then creates a contract and locks the assets they want to transfer on the blockchain ledger $L_0$ with a hashlock (unlocks when r is supplied) and a timelock $T_0$, i.e., $r$ should be revealed before $T_0$. Party $p_0$ next put $H(r)$ on some public channel.

<!-- with a hashlock (unlocks when r is supplied) and a timelock $T_0$, i.e., $r$ should be revealed before $T_0$. Party $p_0$ next sends $H(r)$ to $p_1$. -->

**Step 2**: Similarly, each party $p_i$ creates a contract and locks the assets on $L_i$ using the same hashlock, i.e., $H(r)$ however, using different timelock $T_i$ such that $T_i < T_{(i-1)}$. The order of timelock indicates the order of contract creation and hence the order of asset unlock.

<!-- on receipt of $H(r)$ create a contract on $L_i$ with the same hashlock, i.e., $H(r)$ and timelock $T_i < T_{(i-1)}$. -->

<!-- **Step 3**: After all the parties create the contract, each party locks their assets in the created contract in the same order of a contract creation. -->

**Step 3**: After all the contracts are created and assets are locked in the specific order, party $p_0$ reveals the secret $r$ to unlock the contract created by party $p_{(n-1)}$ on chain $L_{(n-1)}$, and ultimately revealing it to everyone observing the chain $L_{(n-1)}$.

**Step 4**: Because we assume that each party has either account or read access to all the blockchains involved in the swap, once $p_0$ reveals the secret to $p_{n-1}$, it is revealed to all the parties involved in the swap. So all the parties unlock their respective contract using the secret $r$ and claim their assets.

<!-- Similarly, each party $p_i$ reveals the secret $r$ on the chain $L_{(i-1)}$ to claim their assets. -->

Let's understand the MAC with an example involving three users named Alice, Bob, and Carol, each owning assets on different blockchain networks: Bitcoin, Ethereum, and Dot. They agree that Alice will give Bob 10 BTC, Bob will give Carol 12 ETH, and Carol will give Alice 20 DOT. The expected outcome of this exchange is that a transfer of 10 BTC from Alice to Bob should be confirmed on the Bitcoin network. At the same time, the transfer of 12 ETH from Bob to Carol and 20 DOT from Carol to Alice should be confirmed on Ethereum and Polkadot networks, respectively. Given this, the MAC can be done using the standard HTLC as follows:


**Step 1**: Alice generates a random secret $r$ and computes its hash with a random hash function $H(r)$. Alice then creates a contract and locks the assets on the chain of BTC with a hashlock $H(r)$ and a timelock $T_A$. Alice then put the hash on a public channel.

**Step 2**: Bob creates a contract and locks the assets on the chain of ETH with the same hashlock $H(r)$ and a timelock with a timelock $T_B$ lesser than $T_A$,i.e., $T_B<T_A$), as shown in the figure above.

**Step 3**: Similarly, Charlie creates a contract and locks the assets on the DOT chain with the hashlock $H(r)$ and a timelock $T_C$ lesser than $T_B$, i.e., $T_C<T_B$.

**Step 4**: After all the parties in the cycle setup the contract, Alice unlocks the contract posted by Charlie by revealing $r$, effectively revealing it to everyone observing the DOT chain, and 20 DOTs are transferred to Alice’s account.

**Step 5**: Now Charlie claims 12 ETH by using the same $r$, unlocking the contract Bob posted on the ETH chain. Similarly, Bob unlocks the contract posted by Alice on the BTC chain. As a result of this, 10 ETHs are transferred to Charlie’s wallet, and 10 BTCs are transferred to Bob’s wallet.

<!--  -->

<!-- From the above example, we can generalize the model for the exchange between the set of users/parties $P = \{p_0, p_1, \cdots, p_{n-1} \}$, each owning the asset $a_i$ on the ledger $L_1$. Each party $p_i$ sends the asset $a_i$ to $p_{(i+1)\%n}$. A canonical solution for this exchange is the {\em Hash Time-Locked Contract (HTLC)}, where each involved party $i$ ($i\geq0$) locks the assets for a fixed time duration $\tau_i$, such that $\tau_{(i-1)\%n}>\tau_{i\%n}$. The involved party $i$ has to reveal the proof of knowledge to $(i-1)\%n$ to claim the assets before $\tau_{(i-1)\%n}$. However, this approach suffers from different issues, which we will discuss next -->

<!-- which locks the assets from each involved party for a fixed time duration $\tau$. -->

### Pros and cons of using standard HTLC for MAC.

<!--  -->

The above protocol works well when all the parties create the contract (locks the assets) in the specific order, and Alice honestly reveals $r$ at the expected time in step 4. The transaction initiator (source) who picks $r$, i.e., Alice in the above example, gains complete control over when to reveal $r$. The source can reveal the secret after $T_j$, which is the timelock for party $p_j$, as shown in the figure below. This prevents parties from $p_{(j+1)}$ to $p_{(n-1)}$ from completing their swaps if the source so desires.

<!-- **For example...** -->

Parties who are forcefully aborted (e.g., $p_j$ above) don't incur any loss. This may create an incentive for them to collude with the source to abort certain swaps after Step 3. However, once the source reveals the secret, it is visible to all the parties whose timelock is still alive and they have all the necessary information to complete the swap for their assets.

To overcome the excessive influence of the source in this transaction, we propose another solution in the [next blog](https://hackmd.io/@3zL75pX3S1K1zegt7ZjDhw/Sk5R3Bmwi).

<!-- and any other party $j$, $0 \leq j \leq (n-1)$, put a set of parties from $j+1$ to $n-1$ out of the cycle. Let's consider the cyclic swap example explained above to understand it better. If party $A$ (source) colludes with $B$, it ($A$) lets the $T_C$ expire and then secretly shares the secret to $B$. This way, $A$ can put $C$ out of the cycle. Things become worse, i.e., prone to attacks where the honest party ends up losing the asset when multiple owners are associated with an asset and/or multiple assets are shared between a pair of parties [[Krishnasuri Narayanam et al.]](https://arxiv.org/abs/2202.12855). -->

<!-- Furthermore, this simple approach is susceptible to bribery attacks[[Winzer et al.]](https://ieeexplore.ieee.org/document/8802377), [Harris et al.](https://arxiv.org/abs/2006.08513). The attack proceeds as follows: Party B will bribe the blockchain nodes for not including the $C's$ transaction in the block until $B's$ contract expires. This way, $B$ ends up receiving fare from A without paying a penny to C. At the same time, C ends up losing his assets. The solution provided in [[MAD-HTLC]](https://arxiv.org/pdf/2006.12031.pdf) can't apply here directly. Because it leads to both $B$ and $C$ is ending up losing their asset, although $C$ behaves honestly. Given this, we can conclude that the standard HTLC is incapable of solving MACCS. So we propose a new protocol that circumvents the above issues. -->

<!-- Furthermore, if the order of contract creation, in Figure~\ref{fig:stateChange}, is $T_A > T_B < T_C$, then one possible attack is Alice will hold the key till $T_B$ expires. This will make $C$ lose the assets, i.e., $A$ will successfully claim the asset from $C$. However, $C$ can't claim it from $B$ as $T_B$ is expired. The primary cause of this to happen is each blockchain network grows its chain at different rates.
-->

<!-- ### Modified HTLC to solve MACCS -->
<!--

 -->

<!-- The root cause of the issues discussed above is each party uses the same secret, which is generated by the transaction source ($A$ in our example), to claim the assets, because of which two parties can collude to put intermediate parties out of the loop. So in this section, we propose a novel HTLC protocol where different parties contribute to generate the secret for a party.<!-- all parties contribute to generating the secret, and hence unlocking the assets locked in the contract requires all the parties to reveal the secret. -->
<!-- We made a following assumptions for the correct functioning of the protocol -->

<!-- 1. Parties involved in the swap come to a consensus on the set of secret hashes H = {$dig_0, dig_1, \cdots dig_{n-1}$}. This can be achieved with any of the existing Byzantine agreement protocols. -->
<!-- 1. Each party has an account on all the blockchains involved in the swap.
2. All the blockchains should be smart contract compatible.

Given the above assumptions, the detailed protocol steps are as follows: -->

<!-- **step 1**: Each party $i$ involved in the swap generates a random secret $pre_i$ and computes its hash $dig_i$ with a random hash function $H(pre_i)$, i.e., $dig_i = Hash(pre_i)$. Source broadcasts its hash ($dig_S$) while other parties multicast their hash to all the parties that appear before them in the order, i.e. party $i$ multicast their hash to all the parties $j$ such that $j<i$. For example, $C$ multicast its hash to $A$ and $B$ while $B$ sends it to $A$.

**step 2**: Once a party $i$ ($i\geq0$) receives a set of hashes, they create a contract. Note that the party still needs to lock its assets. After all the parties involved in the swap create a contract, a party $i$ hashlock $H = \{dig_S \cup dig_j | j>i\}$, and timelock with time $\tau_{(i-1)\%n}>\tau_{i\%n}$.

**step 3**: After the assets are locked in the contract, to unlock them, i.e., to claim the asset party appears after it has to reveal the secret. In other words, party $i$ requires a preimage from the source and all the parties $j$, such that $j>i$, to claim their asset from party $i-1$.


Next we will describe each protocol step with an example.

Unlike the naive HTLC solution transaction source can not collude with an intermediate party to omit the set of parties that appears after it out of the cycle. For example, party $A$ can't collude with $B$ to remove $C$ from the cycle. This is because unlocking funds from $A$ by $B$ requires $B$ to have $C's$ secret, which they will get by unlocking assets to $C$. -->

<!-- each party should reveal the secret, unlike the standard HTLC, where only the receiver has to reveal the secret. The discloser of the secret is constrained by the time, i.e., it should be revealed within a certain block height ($B_c$) after the contract is created. After each party reveals the secret, assets are committed to being unlocked to be transferred to the intended recipient (lines 20-29 in Algorithm 1). In our example, A transfer to B, B to C, and C to A. We called this phase a *commit phase*

and hashlock the assets
H = {$dig_0, dig_1, \cdots dig_{n-1}$}, they create a contract and hashlock the assets with a different timelock for each phase(lines 5-18 in Algorithm 1).

and multicast it to all the parties appears later in the order. For example, $C$ will multicast the $dig_C$ to $A$ and $B$ while

broadcasts it all the parties, through some communication channel.

**step 2**: Once a party receives the set of hashes H = {$dig_0, dig_1, \cdots dig_{n-1}$}, they create a contract and hashlock the assets with a different timelock for each phase(lines 5-18 in Algorithm 1).

**step 3**: After the assets are locked in the contract, to unlock them, each party should reveal the secret, unlike the standard HTLC, where only the receiver has to reveal the secret. The discloser of the secret is constrained by the time, i.e., it should be revealed within a certain block height ($B_c$) after the contract is created. After each party reveals the secret, assets are committed to being unlocked to be transferred to the intended recipient (lines 20-29 in Algorithm 1). In our example, A transfer to B, B to C, and C to A. We called this phase a *commit phase*

**step 4**: If some party doesn't receive a secret from at least one party (because of network delay and/or a deliberate attack), then it will publish a refund transaction and enter the *refund phase*. As shown in the figure above, parties $A$ and $B$ receive preimage from all the parties involved in the swap. However, party $C$ doesn't receive preimage from $A$, so it enters the refund phase and publishes a refund transaction. Note that a party is constrained to publish a refund transaction within a specific time limit, say block height $B_r$ ($B_r > B_c$).

**step 5**: At the block height $B_p$ ($B_p > B_r > B_c$), if all the parties are in the commit phase, then each party unlocks the assets in the contract to facilitate the transfer; else, abort the swap and refund the asset to the sender (original owner) (lines 35-40 in Algorithm 1). We called this a *payment phase*.


To better understand the protocol, let's run through an example involving three parties, $A$, $B$, and $C$, with a sequence diagram below. Note that we have assumed that parties involved in the swap agreement on the set of secret hashes H = {$dig_0, dig_1, \cdots dig_{n-1}$}. Each party calls the *newContract*, with the sender, receiver, set of hashes (hashlocks), and a timelock. This locks the assets using the set of hashlocks and a different timelock for each phase, i.e., CommitTimelock, RefundTimelock, and paymentTimelock, to get the *contractId* (for party $A$, its $contractId_{AB}$). Note that the order of contract creation doesn't matter for the correct functioning of the protocol.
Once all the parties create the contract, they broadcast the secret, and each party enters the commit phase, which is done by publishing a blockchain transaction. Because we assume that each party has an account on all the blockchains involved in the swap, it is sufficient for a party to reveal the secret on at least one blockchain network. After the party, say $A$, receives a secret from all the parties, it makes a *Commit* call to a contract created ($contractId_AB$ for party $A$) earlier with a set of secret($pre_A, pre_B, and pre_C$) it has received from each party involved in the swap.
If any parties don't receive the revealed secret, they enter the refund phase by making a *Refund* call with a contractId, before a *RefundTimelock* expires.
If no party enters the refund phase even after the *RefundTimelock* expires, all the parties progress to the payment phase by making a *Payment* call with a contractId. The complete Ethereum code for the MACCS-supported HTLC is available at [MACCS-HTLC]()
-->
<!--

Note that our protocol eliminates the bribery attack explained above. If any party colludes with blockchain nodes to avoid including a transaction in the block, then the protocol won't progress, as the protocol requires all the parties to reveal the secret to unlock the contract. It will timeout and revert the asset to the respective initial owners. -->

<!-- We have evaluated our protocol for consistency using a TLA+ specification. Note that in the specification, we have omitted the notion of time and focused on the events, such as if all the parties enter the commit phase, then only a party will proceed to the payment phase. Similarly, if a party receives the secret from all other parties, then it moves to the commit phase (please refer to the code snippet above). In comparison, actual implementation follows the time strictly. The complete TLA+ code is available at [Cycli swap](https://github.com/nitinawathare/CyclicSwap-TLA-Spec.git), while the detailed explanation of the TLA+ specification is presented in the next blog ([Cyclic swap TLA+](https://hackmd.io/@3zL75pX3S1K1zegt7ZjDhw/H1_PT3SIs)).
-->

<!-- Please note to disable the deadlock and disable profiling, specifically while running for a large number of parties. -->

<!-- We have tested the specification for three parties, which result in 1453 distinct states, while the total number of states is 11956 (as shown in the figure above). -->

<!-- **step 1**: All the parties involved in the cyclic swap share a unique hash of preimage with each other, i.e., each party will share $dig_i = Hash(pre_i)$.

**step 2**: Once they receive the set of hashes from all the parties, each party will deploy the contract (HTLC) and lock the assets on the respective blockchain network.

**step 3**: After the assets are locked, each party should reveal the secret. The discloser of the secret is constrained by the time, i.e., it should be revealed within a certain block height ($B_c$) after the contract is deployed.
-->

<!-- parties must reveal the secret to . The protocol proceeds as follows:

In this section, we propose a novel HTLC protocol, where all parties must reveal the secret to unlocking the assets locked in the contract. The protocol proceeds as follows:
-->

<!-- ********************************************************************* -->

<!-- Over the past few years, blockchain has attracted researchers from academia and industries, resulting in the emergence of diverse blockchain and distributed ledger technologies (DLTs). Such diversity motivates the researcher to develop the standards [[Emily Dawson]](https://www.iso.org/committee/6266604.html),[[Thomas Hardjono et al.]](https://datatracker.ietf.org/doc/draft-hardjono-blockchain-interop-arch/03/), and mechanisms [[Ermyas Abebe et al.]](https://doi.org/10.1145/3366626.3368129), [[Rafael Belchior et al.]](https://doi.org/10.1145/3471140), that facilitate the interoperability between the different Blockchains. Lack of interoperability isolates the business process and hence assets associated with it from the outside world, preventing them from scaling up and decreasing their relevance in the overall blockchain economy. A key to enabling interoperability is enabling an exchange of assets between two different blockchain networks, *atomically* [[Andrey Sergeenkov]](https://www.coindesk.com/tech/2021/08/20/a-beginners-guide-to-atomic-swaps/). However, the existing state-of-art models and solutions are inadequate to support complex exchanges involving more than two different blockchain networks. -->

<!-- ACCS involing $n$ parties, where $n>2$. Next we will talk about issues

The naive solution to perform a atomic cyclic swap is by using the hashed timelock contract (HTLC)

Moving further we will talk about, importance of the problem, naive solution using standard a hashed timelock contract (HTLC), issues with the naive solution, and lastly we will elaborate about our protocol, that curcumvent the issues faced by the standard htlc solution.

Development of different blockchains over the time has raised importance of interoperability between the blockchains. Lack of interoperability isolates the business process and hence assets associated with the specific blockchain from the outside world.

The cyclic swap is the more prominent use case involving more than two blockchain networks.
-->