Introduction

cross-chain swap protocol can be applied into

1. cross-chain transactions
2. single chian sharding.

Atomic swap protocol guarantees.

1. if all parties conform to the protocol, then all swaps take place.
2. if some parties deviate from the protocol, then no conforming party ends up worse of
3. no coalition has an incentive to deviate from the protocol.

This paper propose a theory underlying the protocol. And make those contributations

1. Cross-chain swap is modeled as a DAG, vertexs are parties and whose arcs are proposed sset transfers.
2. For a (D, L), the paper give a cross-chain swap protocol using a form of hashed timelock contracts.
3. The paper prove that there is no such protocol is possible if D is not strongly connect. Or, if D is strongly connected but the set of leaders L is not a feedback vertex set.

// In graph theory, a "feedback vertex set" is a set of vertices whose removal makes a directed graph acyclic (i.e., it doesn't have any cycles). In simpler terms, if you remove the vertices in this set from the graph, there will be no loops or cycles left in that graph.
// Strongly connected = for every pair u,v of distinct vertexes in D, u is reachable from v and v is reachable from u

Model

Digraph D : Represented as D=(V,A) Where V: Set of vertices. A: Set of ordered pairs of distinct vertices (arcs).

**Subdigraph C : **Is a subset of D if V(C)⊆V(D) and A(C) ⊆ A(D) and every arc in A(C) is in (C)

Cycle: A path is a cycle if it starts and ends at the same vertex.

Transpose D^T: Obtained by reversing all arcs in D.

SWAP digraphs and games

Each vertex is a party and each arc is a asset transfer.

One party have multiple actions

1. FreeRide: The party acquires assets without paying. The party has incomming arc but not outcomming arcs
2. Discount: The party acquires assets while paying less. The party has incomming arc but less outcomming arcs
3. Deal: The party swap as expected, all incomming arcs are triggered.
4. Nodeal: No deal happends, no arch incomming or outcomming.
5. Underwater: The party pay without acquiring all assets. It has less incomming but full outcomming.

Defnition 3.1. A swap protocol P is uniform if it satisfes:

• If all parties adhere to the protocol, they all get the outcome “Deal.”
• If a group (coalition) deviates from the protocol, parties that are conforming (those who stick to the protocol) don’t end up with the unfavorable “Underwater” outcome.

In game theory, a strategy is in a “Nash Equilibrium” if no player can benefit by changing only their strategy, given that all other players keep their strategies unchanged. And a strategy is a “strong Nash equilibrium” when no coalition (group of players) can jointly deviate in a way that is beneficial for all of them.

Defnition 3.2. A swap protocol P is atomic if it is both uniform and a strong Nash equilibrium strategy

// A uniform protocol ensures that the honest parties won't be penalized even if some parties deviate.
// A strong Nash equilibrium strategy ensures that there's no collective incentive for any group of participants to deviate from the protocol.

// When a swap protocol is both uniform and follows a strong Nash equilibrium strategy, it ensures that either every part of the swap happens as intended, or if there's any deviation (due to malicious intent, errors, etc.), the swap doesn't proceed at all (honest parties remain unaffected). This indivisibility — the all-or-nothing property — is what's encapsulated in the term "atomic." Thus, a swap protocol P is deemed "atomic" if it has these two properties, ensuring both safety and incentive-compatibility in the swap process.

// If everyone is following the protocol, the swap will complete as intended, based on the Uniformity property. However, if there's a deviation, by the definition of Uniformity, those who remain honest don't end up worse off. That means they don't proceed with the swap if it's going to harm them. The Nash Equilibrium property further ensures that no group finds it beneficial to deviate in the first place, so there's a significant disincentive against deviation.

// Thus, the combination of these two properties essentially creates an environment where:
// 1. Deviating doesn't offer benefits to a coalition, disincentivizing malicious actions.
// 2. If someone does try to cheat or make an error, the protocol ensures that the honest parties remain unaffected.

Lemma 3.3. If D is strongly connected, then any uniform swap protocol P is atomic.

In short, if a deriating group achieve a getter payoff than DEAL, then it must be freeride or discount, where the incomine is full and the outcome is none or less.

While in a strongly connected network, each pair nodes are connected, then

• if outcome of C is less or none, the honest party following the C group will not triggered, which will result in the income of C is less or none, thus contridice with the if outcome of C is triggered.

1. If C(the coalition that deviates) benefits: The outcome of C, meaning the assets they should receive, must be triggered (they get the assets). However, for them to cheat and truly benefit, the assets they should give out (outgoing arcs from C) would remain untriggered (they don’t give away anything).

2. Impact on honest parties that follow C: If there’s an honest party v that is supposed to receive assets fromCCC, andCCCcheats by not triggering their outgoing arcs, then v doesn’t receive its due assets.

3. Chain reaction due to v: Now, if v doesn’t get its assets, then as an honest participant, it won’t trigger its own outgoing arcs either (because of the uniformity of the protocol). This means the parties expecting assets fromvvvwon’t get them, and this chain reaction can ripple throughout the system.

4. Coming full circle: Due to the strong connectivity of D, this ripple can eventually circle back to C. This might mean that in some indirect way, C is expecting assets from another party that’s now not triggering its arcs because of the initial cheat by C. So, C’s cheating not only affects its immediate honest neighbors but can also backfire on C itself.

Lemma 3.4. If D is not strongly connected, then no uniform swap protocol is atomic.

Theorem 3.5. A uniform swap protocol for D is atomic if and only if D is strongly connected.

Atomic swap protocol

hashlocks and hashkeys

Hashed time-lock contract stores a pari (h,t) and ensures if contract receies the matching s before t has elapsed, then the contract is triggered, otherwise the asset is refunded.

In the three-way swap recounted, each arc had a single hashlock and a single timeout.

• ← Previous Post
• Next Post →