Update hopr-connect to automatically relay whenever intermediate node has no direct connection to recipient

[0xjjpa]

Introduction

Whenever possible, hopr-connect tries to establish a direct connection between nodes. The entire spec can be seen in the libp2p repository. However, it will be inevitable that some nodes will eventually fail to ever achieve direct connection.

As a workaround, we are looking to use the concept of “Decentralized Relay”, where another node that has a successful connection in the network to the final recipient of the packet is used in exchange.

Let's take the normal example, where a node (bob) is used as an intermediate by alice to send a message to charlie. In this case, bob has both a payment channel opened to charlie, and can reach it directly.

                       HOPR mixing workflow using 1 intermediate node


    ┌─────────┐    ┌─────────┐    ┌─────────┐
    │         │    │         │    │         │
    │  Alice  ├───►│   Bob   ├───►│ Charlie │    ─────►  Open Channel
    │         │    │         │    │         │
    │         ├────┤         ├────┤         │    ──────  Network connection
    └─────────┘    └─────────┘    └─────────┘

However, there could be a case where bob has indeed agreed to relay to charlie, but for some reason, it's unable to reach charlie. In such case, bob can use monica and relay the packet instead.

                       HOPR mixing workflow using decentralized relay


    ┌─────────┐    ┌─────────┐    ┌─────────┐
    │         │    │         │    │         │
    │  Alice  ├───►│   Bob   ├───►│ Charlie │    ─────►  Open Channel
    │         │    │         │    │         │
    │         ├────┤         │    │         │    ──────  Network connection
    └─────────┘    └───┬─────┘    └────┬────┘
                       │               │
                       │  ┌─────────┐  │
                       │  │         │  │
                       └──┤ Monica  ├──┘
                          │         │
                          │         │
                          └─────────┘

Task Description

• Discuss on the incentives for monica to actually relay the package to charlie, considering that a) monica has no payment channel to charlie and bob will be the receiver of the ticket, not monica
• Store within the node a data structure that contains all n -> m connections from the DHT, such as it's not only possible to know what other nodes are in the network, but the next immediate nodes such nodes have (this would mean to build a tree with a depth level of 1)
• Update hopr-connect to lookup within our n -> m tree other registered nodes whenever a failed connection happens, such as given a -> b -> c, if b[x -> c] exists, and b -> c fails, we can use x -> c.

Additional notes

See #1495. The “DR” in DEADR refers to this in particular.

Multiple assumptions were made on the task description, in particular,

• The tree n -> m structure is something that does not exist, and should be implemented
• The tree n -> m has O(log)n with a maximum depth of 1 on lookup and writing
• An alternative solution has not been proposed, and the blockchain is not used.

[SCBuergel]

Isn't this a standard feature of what hopr-connect is doing for about half a year now? If not, what's the difference?

[0xjjpa]

@SCBuergel this is done only using the bootstrap server, see https://github.com/hoprnet/hopr-connect/blob/main/src/index.ts#L86. The goal is that it can be any node.

[SCBuergel]

I find this scope hard to tackle - it's too big for a normal issue so I'd break it down into manageable parts(and e.g. take the incentivized transport-level incentivization out). If this is a full-blown HIP, then I'd need a clearer Spec and Rationale to comment on it.

[0xjjpa]

@SCBuergel Please check the “Additional notes”. The “HIP” is already defined in #1495. In case this wasn't clear before, within the DEADR proposal (Decentralized Entry Advertisement & Distributed Relaying), the DR at the end refers to the Distributed Relaying, i.e, this ticket.

This is not complex, if anything, it's complicated. At most, we need to:

• populate the relay arrays with multiple nodes (what we have done only with the boostrap server)
• define how we will iterate through this list

In the chat, we are discussing with @peterbraden we can start with a naive approach (for looping all nodes), and then decide on better heuristics when needed.

[robertkiel]

Implemented in HoprConnect, but changing slight details:

• Nodes learn about new relay opportunities through the relay management API. Once there is a new relay opportunity, nodes contact the new opportunity and add it to their list of potential entry nodes. This list is later on announced to other nodes through the DHT
• If a node notices that a potential relay node is offline, it removes that node from its own list of entry nodes.
• Once another node (in this case Bob) intends to talk to (in this case Charly), it will get the nodes behind which Charly is reachable by checking the latest DHT entry which populates the n->m mapping. All retrieved addresses (direct ones and indirect ones) provide a way how to reach Charly, including other nodes such as Monica

Incentivizing nodes for providing signaling services (such as STUN) to other nodes as well as relaying services (such as TURN) is currently out of scope.

[0xjjpa]

As discussed with @robertkiel since the amount of work needed for relaying is minimal compared to mixing, for now there are no practical incentives for nodes to relay other than a perceptual increase in connectivity in the network. We might explore this afterwards.

Since everything else was completed and documented, this issue can now be closed.