PathDiscovery
The goal of Ripple path discovery is to find a set of paths from payer to recipient that together have enough available credit to complete the payment. The fastest method to discover these paths would be to flood the network with queries along every possible path, but this approach would not scale. The more scalable approach adopted is a targetted depth-first search, guided by a routing system (see Routing), with an intelligent approach to parallel forking where there is insufficient credit along a unique shortest path. The result of each search is a set of paths totalling the precise amount needed for the payment.
A search begins by either the payer or recipient sending out one or more queries asking their neighbour(s) to find a set of paths for transferring up to a certain amount to/from the other transaction endpoint. The sum of all the query amounts is equal to the payment amount (in the case of the recipient) or the payment amount plus estimated fees (in the case of the payer). Each neighbour receiving a query then adds/deducts fees to the amount (depending on the direction of the query), and passes it along to one or more of its neighbours, according to the available credit on their accounts and distance to the target as determined by the routing scheme.
Queries that have forked in multiple directions do not recombine if they end up back on the same path later: for simplicity, they remain logically split into separate amounts with different path IDs sent in separate messages. Therefore each query represents a unique path back to its origin. Queries from the same search may not reserve the same credit since when those paths are used, the amounts will be added together.
When a query reaches its target or a dead end, the query recipient returns the amount of available credit discovered along the unique path defined by that query. When a node receives a query return value, it compares it to the requested amount on the query it sent. If the return value is less than the amount requested, and there is account credit left unrequested for this particular search, it forks a new query to search for the remainder. Once all queries forked from a single incoming query have returned, the their total available amount is returned as the result for the incoming query.
To avoid loops, each node records the IDs of the queries it has seen, and refuses to accept them a second time. When a query forks in multiple directions, each fork has a different new ID appended to the original ID so the IDs of all previous queries along each path can be read as a prefix of the current ID.
Both payer and recipient may conduct multiple simultaneous searches in order to maximize the chances of finding a useable path set in a reasonable amount of time. Finding multiple path sets also allows the payer to choose the one with the lowest fees.
As each hop, the potential payment intermediary may guarantee the availability of credit for that path for a certain amount of time. If the next phase of payment (transaction phase) has not happened by that time, then the credit guarantee expires. This does not mean that the transaction will fail if attempted, only that its success has not been assured by each intermediary. Since only one search will ultimately be chosen to perform the payment, the same credit may be used to guarantee all searches with the same payment ID.
Whenever path discovery messages are propagating from recipient to payer, be it for query messages originating from the recipient, or return values for queries originating at the payer, a sort of routing onion may be optionally constructed by each node in the path adding a layer of data and encryption to an onion-routing blob. That blob is to be included in promise messages during the next phase of payment (PaymentTransaction), and decrypted layer-by-layer by the node that encrypted it in the first place.
In this path-discovery scenario, nodes may put whatever data they wish into the blob. For example, a node may wish to leave itself directions on where the path goes next, and what exchange rates it is going to use. The reasons for incorporating a routing onion into the promise messages is to allow the transaction phase of the payment to be theoretically independent of the path-discovery phase, so that other path discovery methods might be used that do not require communicating with every single intermediary directly to inform them ahead of time how to route promise messages for a given payment. Since the standard method of path-discovery outlined here requires the intermediaries to construct the paths themselves, meaning they already know how to route promise messages for the payment, the routing onion is not strictly required, but it may be used to store data somewhere other than in the node's local persistent storage. If an intermediary does not wish to use this facility, it can simply neglect to add a layer to the routing-onion blob.
For more information on onion routing during the transaction phase, see Onion Routing.
The payer and recipient send out path_query messages to one or more account partners, which they in turn pass on to one or more of their partners as described in Query Routing. A path_query message consists of:
- payment ID
- search ID
- path ID
- direction of query, forward or backward, depending on whether query originates at payer or recipient
- path units (backward direction only, optional)
- credit available for paying the recipient along this path so far, in path units (backward direction only)
- ID for the account between message sender and recipient that will form part of the path
- credit available along path so far, in account units for that account (defines a conversion rate from transaction units to account units)
- the target's routing information
- the time this available credit guarantee will expire, measured in connection time between sender and recipient (optional)
- promise penalty deadline (forward: maximum offered; backward: minimum required), in connection time
- promise daily penalty rate (forward: maximum offered; backward: minimum required)
- promise final deadline (forward: maximum offered; backward: minimum required), in connection time
- the deadline for the query to reach its goal, in connection time
- a list containing aliases for each of the locations visited on this path
- the per-hop fee limit for this query (as a percentage of the query amount)
- the total accumulated fee limit for this query (as a percentage of the query amount -- backward only)
- routing-onion blob (backward direction only)
{
"path_query": {
"payment_id": "393ff635-de8b-486f-b650-c4f1b151172c",
"search_id": 0,
"path_id": [
"781e22d3-8d91-46ef-8002-8a6b1e0b4bc2"
],
"direction": "fwd",
"path_units": "urn:ripple:units:USD",
"path_amount": 89.9326,
"account_id": "c074162d-d3df-4dcc-9150-3aa634adf4c8",
"account_amount": 100.00,
"target": "7136976c-251d-4be4-b6e2-74baf4b4a53c",
"guarantee_expiry": "2006-11-25 12:55:49.504000",
"promise_penalty_deadline": "2006-11-25 13:55:49.504000",
"promise_penalty_rate": 0.5,
"promise_final_deadline": "2006-11-27 12:55:49.504000",
"query_expiry": "2006-11-25 12:45:49.504000",
"per_hop_fee_limit": 0.001,
"onion": "[base64-encoded encrypted onion blob]"
}
}
Final payment will be made using the paths found by queries within a single search (i.e., having the same search ID). Therefore, queries within a single search may not reserve the same credit. Queries within different searches, but with the same payment ID, may reserve the same credit. Queries with different payment IDs may not reserve the same credit. When a query forks in two or more separate directions, it splits into different paths with different IDs, but each maintain the same swarm ID. One forked path maintains the original path ID. To avoid overlap, payer-initiated (forward) queries should use even-numbered swarm IDs, and recipient-initiated (backward) queries odd-numbered swarm IDs. (Technically, this means that the direction field is redundant.) See Query Routing.
The payer sends out fwd (forward) queries, and the recipient sends out bwd (backward) queries, refering to the direction the payment will ultimately take. The backward queries are more precise: the path_amount is the amount to be received by the recipient, and the backward queries can begin with this exact amount converted to account_amounts which will have fees added to them. The forward queries cannot know how much of their initial amount will reach the recipient and how much will be deducted as fees, so they cannot know precisely the path_amount that will reach the recipient. Therefore the path_amount on forward-direction queries is interpreted as a lower bound. Forward queries should begin with account_amounts that add up to the maximum the payer is willing to spend, and then the recipient will convert the received account_amounts to exact path_amounts in the return values.
The path_amount allows the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. The path_amount does not change as queries are propagated through the network, except where a query is forked into two or more directions, in which case the path_amount is divided among the directions so that the sum of the path_amounts of the forked directions is equal to the path_amount of the incoming query.
The path_units used to measure the path_amount may or may not be divulged to intermediaries. The only purpose of allowing intermediaries to know the path_units is so they may gauge whether the overall fee limit has been surpassed, and abort the query. When the account units at a particular hop are the same as the path_units, the fees charged along the path so far may be calculated precisely, but if they are different, the total fees can only be estimated using the intermediary's own exchange rate between account units and path_units. If an intermediary does not recognize the path_units, or cannot convert them into its account units at that particular hop, then that intermediary simply does not have the opportunity to check whether the overall fee limit has been surpassed, and should route the query regardless.
The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path, if there is more than one. The amount in account units is the amount that is to be reserved on that account for this query's payment path. It also defines a conversion rate between account units and path units that can be used to calculate whether or not the full path amount can be passed on to a single neighbour, and what proportion to pass on to various neighbours otherwise. This conversion rate is also used in subsequent payment messages. (*** Routing onion to store this ***)
The target location is used by each intermediary to route the query. Generally the target for forward queries is the recipient's location, and the target for backward queries is the payer's location, but this is not strictly required. Either payer or recipient may direct the other to route their queries to a different target location, and then ensure that the node with this target location receives a query from the opposite direction to point back to the correct target. For more on how nodes route queries, see Routing.
The guarantee_expiry gives a deadline for the next phase of the payment to occur. If this time limit is reached, the credit held for this path will be released and made available to other payments. Each intermediary should subtract from this time before passing it on to give themselves a small buffer in which to process messages from the next payment phase. The time is given in the connection time between each of the intermediaries, so each one must convert if the time on the incoming account is not in sync with the time on the outgoing account. See Connection Time. If there is to be no guarantee of available credit for this path, then guarantee_expiry should be omitted.
The promise_penalty_deadline, promise_penalty_rate, and promise_final_deadline refer to fields in the promise message in the next payment phase. In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds. The times are again given in connection time, and the penalty rate is a daily proportion of the total amount.
The hop limit is the maximum number of hops for all queries spawned from the one received, including forks. When a query forks in several different directions, the hop limit must be divided up amongst them.
The list containing aliases of the locations already visited is to prevent loops -- no location should occur twice in the same path. Nodes can use any alias they want as long as it is unique among potential intermediaries with high probability and they remember it to compare against incoming queries with the same payment and swarm IDs.
The per-hop fee limit is a limit on the percentage fee charged per hop in the path. The accumulated fee limit is an overall limit to the fees on this query. This can only be enforced if intermediaries recognize the transaction units.
When the query reaches the opposing payment endpoint, or creates a loop or otherwise hits a dead end, the node receiving the query message returns a path-response message:
- payment ID
- swarm ID
- list of path IDs with corresponding available amounts in transaction units
- path ID of query to which this message is a response
- expiry time for these paths
- unused hop limit
These path-responses are propagated back to the query originator in the following fashion: When an intermediary receives a path-response, it checks whether the available amounts equal the amount on the query to which it is a response. If the sum of the path amounts is less than the original query, it sends out new secondary queries for the remaining amounts, if possible. (Multiple queries are permitted on the same accounts, but each must have a different path ID as described in Query Routing.) Unused hop limit may be used for this purpose. Credit amounts held for the outgoing query should be reduced to reflect the amounts in the path-response.
If the path amounts equal the original query amount, if there is no unused hop limit, or if there are no directions remaining to query, it waits until it has received responses to all its queries, and then packages the nonzero paths together into a new query response. The new expiry time is the soonest expiry time of any of the path-responses. The unused hop limit is the total unused hop limit from all the responses that hasn't been used in a secondary query fork.
Fees charged may be integrated as a percentage into conversion rates between units. There is no provision for flat fees at the moment. Minimum fees for any payment through an account are shared with account partners as part of the account data.
The payer and recipient should send a path-cancel down each path they know they will not need:
- payment ID
- swarm ID
- path ID
When passing a path-cancel before having returned a path-response, intermediaries should fork the path-cancel just as they did the path-query with the same identifiers.