Dynamic multi-path transfers
Systems and methods for determining and executing complex multi-route transfers of digital assets are described. A multi-route transfer of a source asset for a destination asset may be determined by analyzing a graph representing a plurality of assets and exchanges to determine a plurality of unique transfer paths. A transfer path may reflect a direct transfer in which the source asset is swapped for the destination asset, or it may reflect a series of intermediate transfers in which the source asset is swapped for intermediate asset(s) that are swapped for the destination asset. Dynamic programming can be used to select the transfer paths to include in the multi-route transfer, how to distribute swaps across those transfer paths, and how to distribute swaps for each transfer of a transfer path—thereby optimizing for the total amount of the destination asset received while accounting for transaction fees.
1. A computer-implemented method performed by a swap platform to determine a multi-route transfer for optimizing an amount of destination asset received, the method comprising:
receiving, from a user device of a user, an order to swap a starting amount of a source asset in exchange for a destination asset;
selecting a subset of intermediate assets from a datasource of assets based on asset data;
selecting a subset of exchanges from a datasource of exchanges based on the source asset, the destination asset, and exchange data;
generating a graph data structure based on the subset of intermediate assets and the subset of exchanges, wherein the graph data structure comprises:
a plurality of nodes comprising:
a source node representing the source asset;
a destination node representing the destination asset; and
a plurality of intermediate nodes representing the subset of intermediate assets;
a plurality of directed edges linking the plurality of nodes, wherein each edge links a pair of neighboring nodes and represents an exchange of the subset of exchanges that supports a transfer from a first asset represented by a first node of the pair to a second asset represented by a second node of the pair;
wherein each pair of neighboring nodes and all the edges linking that pair of neighboring nodes is represented as a set;
determining, for each edge in the graph data structure, relative amounts of the second asset received for corresponding amounts of the first asset transferred through the exchange represented by the edge;
determining, for each set using dynamic programming, a set of exchange distributions corresponding to different amounts of the first asset of the set, wherein each exchange distribution indicates a portion of a volume of the first asset to transfer through each exchange represented by the edges of the set that maximizes the amount of second asset received, wherein the set of exchange distributions are determined using dynamic programming based on the previously-determined relative amounts of the second asset received that is associated with each of the edges in the set;
traversing the graph data structure from the source node to the destination node to determine a set of unique transfer paths from the source node to the destination node, wherein each transfer path corresponds to a series of sets from the source node to the destination node;
determining, for each transfer path in the set of transfer paths using dynamic programming, relative amounts of destination asset received after transaction fees for corresponding amounts of the source asset transferred using the transfer path, wherein the relative amounts of destination asset are determined using dynamic programming by using the previously-determined sets of exchange distributions associated with each set in the transfer path to progressively determine an optimal exchange distribution for each set in the transfer path, starting from the set containing the source node until the destination node is reached;
determining, using dynamic programming, a multi-route transfer comprising a combination of non-conflicting transfer paths and a path distribution that optimizes a total amount of destination asset exchanged for the starting amount of the source asset after transaction fees, wherein the path distribution indicates a portion of the starting volume of the source asset to be transferred via each of the transfer paths in the combination that maximizes the total amount of the destination asset received, wherein the combination of non-conflicting transfer paths and the path distribution are determined using dynamic programming based on the previously-determined relative amounts of destination asset received that is associated with each of the transfer paths in the combination;
sending, to the user device, data indicating the multi-route transfer and the combination of transfer paths; and
receiving, from the user device, a user input to execute the multi-route transfer,
wherein dynamic programming involves breaking down a problem into simpler sub-problems in a recursive manner and efficiently reusing calculated results of the sub-problems so that calculations do not need to be repeated.
2. The computer-implemented method of claim 1 , wherein the subset of intermediate assets is selected from the datasource of assets based on the source asset and the destination asset indicated in the order.
3. The computer-implemented method of claim 1 , wherein at least one transfer path in the set of transfer paths comprises a direct transfer.
4. The computer-implemented method of claim 1 , wherein at least one transfer path in the set of transfer paths comprises an intermediate transfer.
5. The computer-implemented method of claim 1 , further comprising distributing data about the multi-route transfer across a network of computers acting to validate and authenticate blockchain transactions.
6. The computer-implemented method of claim 1 , wherein the number of intermediate nodes in the plurality of intermediate nodes is bound by a max number.
7. The computer-implemented method of claim 1 , wherein the source asset and the destination asset are both cryptocurrency tokens.
8. A computer system comprising:
one or more processing devices; and
one or more memory devices operably coupled to the one or more processing devices, the one or more memory devices storing executable code that, when executed by the one or more processing devices, causes the one or more processing devices to:
receive, from a user device of a user, an order to swap a starting amount of a source asset in exchange for a destination asset;
select a subset of intermediate assets from a datasource of assets based on asset data;
select a subset of exchanges from a datasource of exchanges based on the source asset, the destination asset, and exchange data;
generate a graph data structure based on the subset of intermediate assets and the subset of exchanges, wherein the graph data structure comprises:
a plurality of nodes comprising:
a source node representing the source asset;
a destination node representing the destination asset; and
a plurality of intermediate nodes representing the subset of intermediate assets;
a plurality of directed edges linking the plurality of nodes, wherein each edge links a pair of neighboring nodes and represents an exchange of the subset of exchanges that supports a transfer from a first asset represented by a first node of the pair to a second asset represented by a second node of the pair;
wherein each pair of neighboring nodes and all the edges linking that pair of neighboring nodes is represented as a set;
determine, for each edge in the graph data structure, relative amounts of the second asset received for corresponding amounts of the first asset transferred through the exchange represented by the edge;
determine, for each set using dynamic programming, a set of exchange distributions corresponding to different amounts of the first asset of the set, wherein each exchange distribution indicates a portion of a volume of the first asset to transfer through each exchange represented by the edges of the set that maximizes the amount of second asset received, wherein the set of exchange distributions are determined using dynamic programming based on the previously-determined relative amounts of the second asset received that is associated with each of the edges in the set;
traverse the graph data structure from the source node to the destination node to determine a set of unique transfer paths from the source node to the destination node, wherein each transfer path corresponds to a series of sets from the source node to the destination node;
determine, for each transfer path in the set of transfer paths using dynamic programming, relative amounts of destination asset received after transaction fees for corresponding amounts of the source asset transferred using the transfer path, wherein the relative amounts of destination asset are determined using dynamic programming by using the previously-determined sets of exchange distributions associated with each set in the transfer path to progressively determine an optimal exchange distribution for each set in the transfer path, starting from the set containing the source node until the destination node is reached;
determine, using dynamic programming, a multi-route transfer comprising a combination of non-conflicting transfer paths and a path distribution that optimizes a total amount of destination asset exchanged for the starting amount of the source asset after transaction fees, wherein the path distribution indicates a portion of the starting volume of the source asset to be transferred via each of the transfer paths in the combination that maximizes the total amount of the destination asset received, wherein the combination of non-conflicting transfer paths and the path distribution are determined using dynamic programming based on the previously-determined relative amounts of destination asset received that is associated with each of the transfer paths in the combination;
send, to the user device, data indicating the multi-route transfer and the combination of transfer paths; and
receive, from the user device, a user input to execute the multi-route transfer,
wherein dynamic programming involves breaking down a problem into simpler sub-problems in a recursive manner and efficiently reusing calculated results of the sub-problems so that calculations do not need to be repeated.
9. The system of claim 8 , wherein the subset of intermediate assets is selected from the datasource of assets based on the source asset and the destination asset indicated in the order.
10. The system of claim 8 , wherein at least one transfer path in the set of transfer paths comprises a direct transfer.
11. The system of claim 8 , wherein at least one transfer path in the set of transfer paths comprises an intermediate transfer.
12. The system of claim 8 , wherein the executable code, when executed by the one or more processing devices, further causes the one or more processing devices to distribute data about the multi-route transfer across a network of computers acting to validate and authenticate blockchain transactions.
13. The system of claim 8 , wherein the number of intermediate nodes in the plurality of intermediate nodes is bound by a max number.
14. A non-transient computer readable medium containing program instructions for causing a computer system to perform the steps of:
receiving, from a user device of a user, an order to swap a starting amount of a source asset in exchange for a destination asset;
selecting a subset of intermediate assets from a datasource of assets based on asset data;
selecting a subset of exchanges from a datasource of exchanges based on the source asset, the destination asset, and exchange data;
generating a graph data structure based on the subset of intermediate assets and the subset of exchanges, wherein the graph data structure comprises:
a plurality of nodes comprising:
a source node representing the source asset;
a destination node representing the destination asset; and
a plurality of intermediate nodes representing the subset of intermediate assets;
a plurality of directed edges linking the plurality of nodes, wherein each edge links a pair of neighboring nodes and represents an exchange of the subset of exchanges that supports a transfer from a first asset represented by a first node of the pair to a second asset represented by a second node of the pair;
wherein each pair of neighboring nodes and all the edges linking that pair of neighboring nodes is represented as a set;
determining, for each edge in the graph data structure, relative amounts of the second asset received for corresponding amounts of the first asset transferred through the exchange represented by the edge;
determining, for each set using dynamic programming, a set of exchange distributions corresponding to different amounts of the first asset of the set, wherein each exchange distribution indicates a portion of a volume of the first asset to transfer through each exchange represented by the edges of the set that maximizes the amount of second asset received, wherein the set of exchange distributions are determined using dynamic programming based on the previously-determined relative amounts of the second asset received that is associated with each of the edges in the set;
traversing the graph data structure from the source node to the destination node to determine a set of unique transfer paths from the source node to the destination node, wherein each transfer path corresponds to a series of sets from the source node to the destination node;
determining, for each transfer path in the set of transfer paths using dynamic programming, relative amounts of destination asset received after transaction fees for corresponding amounts of the source asset transferred using the transfer path, wherein the relative amounts of destination asset are determined using dynamic programming by using the previously-determined sets of exchange distributions associated with each set in the transfer path to progressively determine an optimal exchange distribution for each set in the transfer path, starting from the set containing the source node until the destination node is reached;
determining, using dynamic programming, a multi-route transfer comprising a combination of non-conflicting transfer paths and a path distribution that optimizes a total amount of destination asset exchanged for the starting amount of the source asset after transaction fees, wherein the path distribution indicates a portion of the starting volume of the source asset to be transferred via each of the transfer paths in the combination that maximizes the total amount of the destination asset received, wherein the combination of non-conflicting transfer paths and the path distribution are determined using dynamic programming based on the previously-determined relative amounts of destination asset received that is associated with each of the transfer paths in the combination;
sending, to the user device, data indicating the multi-route transfer and the combination of transfer paths; and
receiving, from the user device, a user input to execute the multi-route transfer,
wherein dynamic programming involves breaking down a problem into simpler sub-problems in a recursive manner and efficiently reusing calculated results of the sub-problems so that calculations do not need to be repeated.
15. The non-transient computer readable medium of claim 14 , wherein the subset of intermediate assets is selected from the datasource of assets based on the source asset and the destination asset indicated in the order.
16. The non-transient computer readable medium of claim 14 , wherein at least one transfer path in the set of transfer paths comprises a direct transfer.
17. The non-transient computer readable medium of claim 14 , wherein at least one transfer path in the set of transfer paths comprises an intermediate transfer.
18. The non-transient computer readable medium of claim 14 , wherein the steps further comprise distributing data about the multi-route transfer across a network of computers acting to validate and authenticate blockchain transactions.
19. The non-transient computer readable medium of claim 14 , wherein the number of intermediate nodes in the plurality of intermediate nodes is bound by a max number.
20. The non-transient computer readable medium of claim 14 , wherein the source asset and the destination asset are both cryptocurrency tokens.