Pathfinding Service

Overview

A pathfinding service (PFS) has a global view on a token network and can provide suitable payment paths for Raiden nodes. Raiden nodes can request paths from a PFS via a public REST API and pay per request.

The service will keep its view on the token network updated by listening to blockchain events and a public matrix room where current capacities and fees are being published. Nodes will publish this information in order to advertise their channels for mediation.

Assumptions & Goals

  • The PFS should be able to handle a similar amount of active nodes as currently present in Ethereum (~20,000).
  • Nodes are incentivized to publicly report their current capacities and fees to “advertise” their channels.
  • Uncooperative nodes are dropped by the PFS, so paths provided by the service can be expected to work most of the time.
  • No guarantees are or can be made about the feasibility of the path with respect to node uptime or neutrality.

High-Level-Description

A node can request a list of possible paths from start point to endpoint for a given transfer value. The get_paths method implements the bi-directional Dijkstra algorithm to return a given number of paths for a mediated transfer of a given value. The design regards the Raiden network as an unidirectional weighted graph, where the weights of the edges/channels are the sum of multiple penalty terms:

  • a base weight of 1 per edge, to incentivize short paths
  • a term proportional to the mediation fees for that channel
  • if the edge is included in a route, all following routes will get a penalty if they include the same edge. This increases the diversity of routes and reduces the likelihood that multiple routes fail due to the same problem.

See Routing Preferences for information on how to configure the trade-off between these penalties.

Public REST API

A pathfinding service must provide the following endpoints. The interface has to be versioned.

The examples provided for each of the endpoints is for communication with a REST endpoint.

POST api/v1/<token_network_address>/paths

The method will do max_paths iterations of Dijkstras algorithm on the last-known state of the Raiden Network (regarded as directed weighted graph) to return max_paths different paths for a mediated transfer of value.

  • Checks if an edge (i.e. a channel) has capacity > value, else ignores it.
  • Checks that further constraints are met, like the lock timeout being smaller than the settle timeout.
  • Applies on the fly changes to the graph’s weights - depends on DIVERSITY_PEN_DEFAULT from config, to penalize edges which are part of a path that is returned already.

Arguments

The arguments are POSTed as a JSON object.

Field Name Field Type Description
token_network_address address The token network address for which the paths are requested.
from address The address of the payment initiator.
to address The address of the payment target.
value int The amount of token to be sent.
max_paths int The maximum number of paths returned.
iou object IOU object as described in Communication between client and PFS to pay the service fee
diversity_penalty float (optional) Routing penalty per channel that is reused across multiple different routes returned in the same response.
fee_penalty float (optional) Penalty applied to a channel for requiring 1 RDN as mediation fee.

Returns

When successful, the request returns a list of path objects and a feedback token. A feedback token is the 32-character hexadecimal string representation of a UUID and is valid for all routes that are included in the response.

Each path object consists of the following information:

Field Name Field Type Description
path List[address] An ordered list of the addresses that make up the payment path.
estimated_fee int An estimate of the fees required for that path.

An example response looks like:

{
    "result":
    [
        {
            "path":
            [
                "0x627E3C777232243a6C766D20404f790B66456747",
                "0x574b315075443878652f2F403645743d5b4a7950",
                "0x49650D660c475e65253F666f302A4A662A3d533D",
                "0x6A273E6D557454520964484D23502C207361597D"
            ],
            "estimated_fee": 123
        }
    ],
    "feedback_token": "381e4a005a4d4687ac200fa1acd15c6f"
}

Routing Preferences

The PFS will search for routes that are:

  • short
  • cheap
  • diverse (using different channels for different routes when multiple routes are returned)

Since these goals can be conflicting, a trade-off between them has to be chosen. This is done by assigning a penalty to all undesired properties of a channel, summing up these penalties across all channels used in a route and then choosing the route with the lowest total penalty.

When requesting a route, the calculated penalties depend on the diversity_penalty and fee_penalty parameters. If those parameters are omitted, reasonable defaults are chosen. A diversity_penalty of 5 means that a channel which has already been used in previous route is as bad as adding 5 more channels to the path which have not been used, yet. A fee_penalty of 100 means that spending 1 RDN is as bad as adding 100 more channels to the route (or that spending 0.01 RDN is as bad as adding one more channel).

Errors

Each error consists of three parts:

  • errors: a human readable error message
  • error_code: a machine readable identifier for the type of error
  • error_details: additional information on the failure, e.g. values that caused the failure or expected input values (can be empty for some errors)

Please have a look at the full list of errors.

Example

// Request
curl -X POST --header 'Content-Type: application/json' --data '{
    "from": "0xalice",
    "to": "0xbob",
    "value": 45,
    "max_paths": 10
}'
// Result for success
{
    "result": [
    {
        "path": ["0xalice", "0xcharlie", "0xbob"],
        "estimated_fee": 110,
    },
    {
        "path": ["0xalice", "0xeve", "0xdave", "0xbob"]
        "estimated_fee": 142,
    },
    ...
    ],
    "feedback_token": "aaabbbcccdddeeefff"
}
// Wrong IOU signature
{
    'errors': 'The signature did not match the signed content',
    'error_code': 2001,
}
// Missing `amount` in IOU
{
    'errors': 'Request parameter failed validation. See `error_details`.',
    'error_code': 2000,
    'error_details': {'iou': {'amount': ['Missing data for required field.']}}
}

GET api/v1/info

Request price and path information on how and how much to pay the service for additional path requests. The service is paid in RDN tokens, so they payer might need to open an additional channel in the RDN token network.

Returns

A JSON object with at least the following properties:

Field Name Field Type Description
price_info int Amount of RDN per request expected by the PFS
network_info.chain_id int The chain ID for the network this PFS works on

Example

// Request
curl -X GET api/v1/info

// Result for success
{
    "price_info": 100,
    "network_info": {
        "chain_id": 5,
        "token_network_registry_address": "0xFfaf04Ad776AAa3AbD62AFA340f3c55931a68fB1",
        "user_deposit_address": "0xB85703628262C8301298474e072D426fE9C3fEeC",
        "service_token_address": "0xc116edAD88cda44E703ef1fc59766268E4aa187B",
        "confirmed_block": {
            "number": 2441022
        }
    },
    "version": "0.7.0",
    "contracts_version": "0.37.0b0",
    "operator": "John Doe",
    "message": "This is your favorite PFS.",
    "payment_address": "0x062C12c01D0f17fC9eAa33940D994594d91a0182",
    "UTC": "2020-03-31T09:33:26.073566"
}

GET api/v1/<token_network_address>/payment/iou

Request the last IOU used by sender to pay the PFS. This IOU can be used by the client to generate the next IOU to pay the PFS by increasing the amount and updating the signature.

Arguments

Field Name Field Type Description
sender address Sender of the payment (Ethereum address of client)
receiver address Receiver of the payment (Ethereum address of PFS)
timestamp string Current UTC date and time in ISO 8601 format (e.g. 2019-02-25T12:53:16Z)
signature bytes Signature over the other three arguments [1]
[1]

The signature is calculated by

ecdsa_recoverable(privkey,
                  sha3_keccak("\x19Ethereum Signed Message:\n[LENGTH]"
                              || sender || receiver || timestamp ))

Returns

A JSON object with a single property:

Field Name Field Type Description
last_iou object IOU object as described in Communication between client and PFS

POST api/v1/<token_network_address>/feedback

Send feedback about a given route to the pathfinding service. For more information see the routing feedback ADR.

Arguments

Field Name Field Type Description
token string Hexadecimal string representation of the token
success boolean Whether or not the route worked
path List[address] The route feedback is given for

Returns

  • HTTP 200 when feedback was accepted
  • HTTP 400 when feedback was not accepted

GET api/v1/<token_network_address>/suggest_partner

When a Raiden node joins a token network, it should connect to nodes which will be able to mediate payments. Since the PFS observes the whole network, it is in a better position than the client to choose suitable partners for a channel opening. This endpoint provides partners recommended by the PFS.

The endpoint is free to use to encourage users to join the network. To avoid load on the PFS for these free requests, the recommendations can be aggressively cached by the PFS.

Arguments

None. A custom limit on the number of results is not used to facilitate caching.

Returns

A sorted list of objects describing the suggested partners. The best recommendations come first, so the simplest approach to use the results is to connect to the node address given in the first element.

Each object has an address attribute containing the recommended node’s Ethereum address. For advanced use cases and for debugging, additional scoring information is provided (The overall score in the score attribute, as well as centrality, uptime and capacity). There is no long term guarantee regarding the meaning of the specific values, but greater values will always indicate better recommendations.

Example

// Request
curl -X GET api/v1/0x3EA2a1fED7FdEf300DA19E97092Ce8FdF8bf66A3/suggest_partner

// Result for success
[
  {
    "address": "0x99eB1aADa98f3c523BE817f5c45Aa6a81B7c734B",
    "score": 2906634538666422000,
    "centrality": 0.0004132990448199853,
    "uptime": 7032.763746,
    "capacity": 1000000000000000000
  },
  {
    "address": "0x4Fc53fBa9dFb545B66a0524216c982536012186e",
    "score": 2906693668947465000,
    "centrality": 0.0004132990448199853,
    "uptime": 7032.906815,
    "capacity": 1000000000000000000
  }
]

Network Topology Updates

The creation of new token networks can be followed by listening for TokenNetworkCreated events on the TokenNetworksRegistry contract.

To learn about updates of the network topology of a token network the PFS must listen for the following events:

  • ChannelOpenened: Update the network to include the new channel
  • ChannelClosed: Remove the channel from the network

Capacity and Fee Updates

Updates for channel capacities and fees are published over a public matrix room. Path finding services can pick these capacity updates from there and update the topology represented internally. The Raiden nodes that want to earn fees mediating payments would be incentivized to publish their capacity updates in order to provide a path.

Capacity Update

PFSCapacityUpdates are messages that the Raiden client broadcasts to Pathfinding Services in order to let them know about updated channel balances.

Fields

Field Name Field Type Description
chain_id uint256 Chain identifier as defined in EIP155
token_network_identifier address Address of the TokenNetwork contract
channel_identifier uint256 Channel identifier inside the TokenNetwork contract
updating_participant address Channel participant who sends the balance update
other_participant address Channel participant who doesn’t send the balance update
updating_nonce uint256 Strictly monotonic value used to order transfers. The nonce starts at 1
other_nonce uint256 Strictly monotonic value used to order transfers. The nonce starts at 1
updating_capacity uint256 Available capacity for the participant sending the update
other_capacity uint256 Available capacity for the participant not sending the update
reveal_timeout uint256 Reveal timeout of this channel

Signature

The signature is created by using ecdsa_recoverable on the fields in the order given above and stored in the signature field.

All of these fields are required. The Pathfinding Service MUST perform verification of these data, namely channel existence. A Pathfinding service SHOULD accept the message if and only if the sender of the message is same as the sender address recovered from the signature.

Fee Update

PFSFeeUpdates are broadcast by the Raiden Client to Pathfinding Services in order to let them know about updated mediation fee schedules.

Fields

Field Name Field Type Description
chain_id uint256 Chain identifier as defined in EIP155
token_network_identifier address Address of the TokenNetwork contract
channel_identifier uint256 Channel identifier inside the TokenNetwork contract
updating_participant address Channel participant who sends the balance update
fee_schedule.flat uint256 Flat mediation fee in Wei of the mediated token
fee_schedule.proportional uint256 Proportional mediation fee as parts-per-million of the mediated token
fee_schedule.imbalance_penalty array of [int, int] pairs (capacity, penalty) pairs for the IP function. This is RLP encoded in the signature.
timestamp string Current UTC date and time in ISO 8601 format (e.g. 2019-02-25T12:53:16Z)

Signature

The signature is created by using ecdsa_recoverable on the fields in the order given above and stored in the signature field.

When to send PFSFeeUpdates

The fees depend on the total channel capacity across both participants, so whenever that changes, a PFSFeeUpdate should be sent. The capacity changes when participants deposit to or withdraw from a channel. For both of these actions, there is a time of uncertainty between the initiation and the confirmation of the action. The updates should assume the lower capacity during time, since it is the safe thing to do and it matches the node’s internal state.

Deposit

With this pessimistic approach, the update must be sent when the blockchain confirms the deposit (ContractReceiveChannelDeposit).

Withdraw

The update will be sent when the withdraw is successfully initiated (SendWithdrawRequest and ReceiveWithdrawRequest). If the withdraw succeeds on-chain, this fee remains correct. In the unlikely case that the withdraw never reaches the blockchain, we have to revert back to the old fee schedule by sending a new fee update on the SendWithdrawExpired/ReceiveWithdrawExpired state change.

Routing feedback

In order to improve the calculated routes, the PFS requires feedback about the routes it provides to Raiden clients. For that reason the routing feedback mechanism is introduced.

When a client requests a route from a PFS (see POST api/v1/<token_network_address>/paths), the PFS returns a feedback token together with the number of routes requested. This feedback token is a UUID in version 4. The client stores it together with the payment id and then initiates the payment. Whenever a particular route fails or the payment succeeds by using a certain route, this feedback is given to the PFS.

While the individual feedback cannot be trusted by the PFS, it can use general trends to improve it’s routing algorithm, e.g. lowering the precedence or removing channels from the routing table when payments including them often fail.