Sike: Finding Optimal Swap Paths

This repository houses the code for the smart contract named Sike, which facilitates two functionalities:

1. Path Finding Algorithm: This algorithm excels at identifying the optimal path for swapping tokens across various Decentralized Exchanges (DEXs) using intermediate tokens.
2. Swap Execution: Following the identification of the optimal path, Sike efficiently executes the swap transactions.

How Sike Functions

1. Calling getBestPath():

This function requires various data inputs, but the most crucial ones are: - The token you intend to swap. - The swap amount. - A list encompassing the DEXs you'd like to explore for path identification.

2. Path Exploration and Depth Determination:

• getBestPath() ascertains the optimal search depth for swap paths based on the provided data.
• It then iterates through the sequence of swaps, aiming to find the path that yields the most favorable outcome.

3. Iterative Path Optimization:

• At each step:
  • The function meticulously examines each DEX within the specified list to determine the one offering the most advantageous trade for the current level (e.g., inputToken -> pathToken1).
  • Subsequently, it explores multi-path possibilities, prioritizing the path that results in the most significant output from the previous level to the subsequent one (e.g., pathToken1 -> pathToken2).
  • Finally, it investigates the DEX delivering the best final output for the designated input amount (e.g., pathToken2 -> outputToken).

4. Greedy Approach:

• To enhance efficiency, Sike employs a greedy approach. It doesn't exhaustively analyze all potential combinations but progressively optimizes based on the current best outcome, ultimately leading to an efficient yet likely not guaranteed-optimal solution.

Understanding Time Complexity

Notation:

• n: Number of intermediate tokens (typically 5-6)
• m: Number of DEXs (routers) (generally 10-15)

Formula:

Number of function calls = (n * m) * ((n - 1) * m) = (n^2 * m^2)

Explanation:

• Since m is typically larger than n, the dominant factor in the time complexity is m^2.
• Therefore, the time complexity can be approximated as O(m^2).

Getting Started

1. Installation:

   yarn install```

2. Test:

   yarn hardhat test```