How does routing work in Interledger?

Glancing at some code fragments, I think it was something similar to BGP routing, which is path vector based? Why not something like distance vector routing instead?

Correct, Interledger’s routing protocol CCP is pretty similar to BGP. It’s designed to be a policy-based protocol, i.e. each node actively manages its peering relationships and wants to modify it’s routing preference based on its business needs.

In path vector protocols, route updates contain full information about the path they traveled to reach you. This is a good property to have in practice because it makes it trivial to discard routes that would create routing loops. The overhead is manageable since most routes tend to be short.

1 Like

Leading question: is Interledger routing secure? Haven’t there been big attacks on or failures of BGP routing?

1 Like

No, but this is something we want to enable in the future. Right now, Interledger routing inherits its security properties from BGP, which (again) is how the Internet routes. Given that in Interledger money is only transferred if a packet reaches the correct destination, the security situation isn’t any worse than it is in BGP, which is to say “bad but not prohibitively bad”. There are, however, ways to make it better.

We’ve thought about a public key infrastructure where top-level prefixes would broadcast cryptographic keys. So, for example, if Coil wanted to claim g.coil, it would broadcast a message saying “the key A claims the prefix whose hash is H("g.coil" || nonce)” Then, once everyone has received that message, it would broadcast another message saying “the prefix claimed in the previous message was "g.coil"”. If Coil become the Interledger Service Provider (ILSP) of Bob, Bob may want to use the address g.coil.bob. So Coil may sign a certificate associated with Bob’s key that grant him the right to advertise routes to g.bob.

This is designed to be a more decentralized architecture than what the Internet does where prefixes are assigned in a top-down fashion.

By being a decentralized protocol, this raises the question how to prevent spam. We think that the initial broadcast might include some money that pays for the forwarding and storage of the information. Upon receiving a broadcast, each connector takes a cut and rebroadcasts the information. They can take whatever cut they like, however, if I’m the one broadcasting and one of my peers takes a big cut and another peer takes a small cut, I may configure my connector to attach more money to the broadcast going to the peer that takes a small cut because my message is more likely to reach more people that way for the same amount of money.

Also by being a decentralized protocol, it raises the question of how to deal with conflicts. What if some nodes think g.coil is associated with key A and some think it is associated with key B? I think that the protocol outlined above prevents front-running, i.e. maliciously squatting on a name that somebody else is trying to claim. Because I don’t know what name you’re claiming until after you’ve successfully claimed it, I can’t make my own claim for the same name. That leaves accidental splits where perhaps I claimed a name but didn’t attach quite enough money to reach every crevice of the Interledger. In such a case, we may be able to recover via a protocol that loads the prefix->key mapping from a neighbor when a node sees a route advertisement that it doesn’t have a key for to verify against. After handling all of these cases, there are still some edge cases remaining. For example, a malicious node trying to convince its neighbors that a prefix is owned by a different key than it actually is. I could spend another twenty pages discussing each of those cases in detail but I’ll summarize here by saying that the remaining edge cases can be handled through manual intervention by the connector operators.

Once you have a public-key infrastructure that associates keys with prefixes, it is possible to design a secure routing protocol that verifies that both the origin information of each route as well as the path information. For an example of such a protocol, one need look no further than sBGP, so we could implement something very similar. The computational cost of secure routing protocols is significant, some even claim it is prohibitive. I think watching what happens with sBGP adoption on the internet will give us valuable insights that we can learn from.

3 Likes

Did some extensive reading. Can confirm BGP is probably the best you can do if you want fast convergence on this system. (There’s actually not much literature on this, but I suppose there’s no idea of where to start if you want to do better)

@justmoon Could you provide more context for how the path vector protocol works in terms of seeking Interledger payments? I get that in path-vector, you share the entire path, not the distance, which results in much faster convergence and flexibility… but how do you find/construct these paths to begin with? What is the local policy on a connector for choosing what path to select for routing, and paths for advertisement?

Specifically:

  • Does it just brute force through its routing table containing the path vectors until it finds a feasible route to the receiver?
  • Does it take into account heuristics like what the connectors have in terms of supported currency, number of hops (like in distance vector) or bandwidth/capacity (like in link state)?
  • Maybe you have an example of a flow where I might try do an SPSP payment over multiple currencies, and how the routes are determined from sender to receiver that could explain all of this?

Side question: Would ILP ever need to do some form of intradomain routing? Seems like that what the load balancing stuff is. But wondering if there’s a perspective beyond just the context of horizontal scaling.

FWIW, there is a PR (though dormant/closed) that has a lot of information and discussion about the current routing implementation in the JS Connector. See here: https://github.com/interledger/rfcs/pull/455

Have re-opened that PR. @matdehaast is working on the reference router and will help me finish that doc when he’s done.

2 Likes