# Routing Payments in Lightning Network using HTLCs

Recall that in [this](https://dev.to/tvpeter/understanding-how-payment-channels-work-in-lightning-network-30ia) article, we discussed how peers on the Lightning Network (LN) establish a channel to make numerous payments without announcing them to the network. However, if every payment requires setting up a channel between nodes on the LN, then there will be delays in the first payment as the transaction establishing a channel has to be broadcasted and confirmed on-chain. Also, there are on-chain transaction fees and the challenge of managing multiple channels. Alternatively, nodes may choose to route payment across the network to a destination node. In this article, we will discuss how a payment can be routed through other nodes in LN to a destination node in the same trustless manner using Hash Time Lock Contracts (HTLCs).

The first step in routing a payment using HTLCs is for the receiver node to generate a payment invoice and send it to the payer. The invoice contains the amount, a payment hash, the receiver identity on the LN, an optional description, timelock, request expiration, and an on-chain fallback address.

The most vital data on the invoice is the receiver node identity and the payment hash as this is all the information the sender is given about the identity of the recipient. The identity is a `secp256k1` public key of the node, which uniquely identifies the node on the network.

The receiver node generates the payment hash by first generating a 32-byte random number called a `preimage`. The preimage remains a secret. It is then hashed using the `SHA256` hash algorithm to generate a payment hash for the invoice. Recall that, `SHA256` is a one-way hash function whose input cannot be calculated from the result.

The recipient node may also optionally include routing hints in the payment invoice. These hints enable the sender to include unannounced channels while constructing a route to the recipient. Also optionally included in the invoice is the timestamp which enables the sender to know how old the invoice is, and also permits the receiver to enforce the expiration of the payment invoice.

Alongside other earlier stated information, the payment invoice is signed by the receiver node. `BOLT11` invoice can also include the recipient pubkey as a tagged field which is covered by the signature. However, it's also possible to omit the recipient pubkey and to perform [pubkey recovery](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Public_key_recovery) on the signature itself to extract the pubkey it was signed with.

As we will see later in the article, payment invoices are meant to be used once and never to be reused, though new LN specifications exist that make it possible to reuse invoices (those are not covered in this article).

The signed invoice is then communicated to the sender. This is often done outside the LN through emails and QR codes or fetched via a webserver e.g. during a checkout process, though new specifications include using LN onion messages.

Once the sender node receives the invoice, it first computes a path to send the payment to the recipient. This path is constructed by examining the information the sender node has about the network. (Recall that, when channels are created, they are announced to the network and nodes keep this information to represent the state of the network called the network graph).

Provided the sender and recipient nodes are connected with channels that have enough capacity, the sender node will create a list of possible paths, and attempt to deliver payment in a trial and error loop until a path is found that can deliver the payment. Whilst the network graph includes **total channel capacity** for each channel, nobody except the two nodes in each channel knows how that capacity is distributed within the channel, i.e. what the _balance_ at each side of the channel is.

### ROUTING A PAYMENT

When the sender node identifies a path to deliver payment to the recipient, it will encrypt a payment instruction containing the invoice’s payment hash in nested layers (like an onion) and send it to the first (intermediary) node on the path (hop). The intermediary node will unwrap the outermost layer of the payment instruction, identify and send it to the next hop along the path. This approach is called source-based onion routing (SPHINX), and each hop can only decrypt one layer at a time to reveal the next hop to forward the payment.

Intermediate nodes only gain knowledge of `previous_hop` and `next_hop` relative to themselves, so if there is more than 1 hop in the path then nobody other than the sender will ever know the complete path. The final recipient will only ever know `previous_hop` and then that the payment was destined for them.

As illustrated below, let’s assume Alice wants to send a letter to Chan through Bob (i.e, Alice is connected to Bob who is then connected to Chan). She will write the letter and seal the letter in an envelope addressed to Chan which only Chan can open. But because Alice is not connected to Chan directly, she will put the first envelope and the instruction inside another envelope and address it to Bob. When Alice delivers the entire packaged letters, Bob will open the first outer envelope which reveals the instruction TO CHAN. Bob will then forward the letter to Chan, the intended receiver.


Developing on the above illustration further, the intermediary (Bob) might decide to charge a fee for forwarding the payment instruction to the next hop on the path (in this example Chan). So Alice will pledge to pay Bob an additional 100sats for forwarding the instruction. However, the payment will only be made if and only if Chan will share a secret number (the preimage discussed earlier) with Bob that can be hashed to result in the payment hash stated on the payment invoice.

With this pledge, Bob will also pledge to Chan that he will pay Chan an amount less than 100sats if Chan will present a preimage that Bob can hash that will result in the payment hash. Once Chan reveals the preimage, Bob will verify by hashing the preimage and if the result matches the payment hash, Bob will then pay Chan the amount stated on the payment instruction. Bob will then share the preimage with Alice who pledged to pay Bob the amount and an additional 100sats if Bob shares the secret hashing to the payment hash. Once Alice verifies by hashing the preimage and it results in the payment hash, she will pay Bob the amount she pledged earlier, which is the invoice amount + 100sats.

The above illustration has a single hop between the sender and recipient. Whilst the specification currently allows for a maximum of 27 hops in the route, in normal usage more than 7 hops would be considered unusual. In computing a path, the sender often optimizes for fewer hops to reduce the chance for failure and routing fees.

So, how does Alice (our payment sender) knows what fee to pay to each hop (fee_base_msat) and whether a channel exists between nodes capable of forwarding this payment? This is the information Alice sought during the path-finding phase. She is also aware of how long it will take for Bob to pay Chan the agreed amount (cltv_expiry_delta). All this information aids the sender to construct a payment instruction that will pass through each intermediary with minimal chance of failure.

Also, as illustrated in our example, the sender starts constructing the payment instruction from the destination backward to them. Each layer of the onion is encrypted in such a way that only the node meant to read it can be able to read. The sender achieves this using the intermediate node’s public key and the Elliptic Curve Diffie–Hellman (ECDH) on Bitcoin’s secp256k1 curve. And the message can be checked that it has not been modified. Also, the sender generates a temporal key for the entire session so that no other node can identify her node as the sender of the payment instruction. All these measures ensure the integrity of messages and the privacy of the nodes.

If for any reason, the payment instruction could not go through at any point, it will fail and the failed status will propagate backward along the same path so that any pledged payment will be canceled.

As we have seen, sending payments this way on the LN is both beneficial and safe for everyone involved (the sender, the intermediary nodes, and the recipient). Intermediary nodes earn fees for forwarding payment instructions. The sender pays the recipient within a short time and with a minimal fee. The recipient node receives its payment within a short time without risk. This enables payments to be made on the LN without establishing channels between nodes for each payment.

References:
- [Mastering Lightning Network](https://github.com/lnbook/lnbook): By Andreas M. Antonopoulos (@aantonop), Olaoluwa Osuntokun (@roasbeef), Rene Pickhardt (@renepickhardt).
- Public Key Recovery question on Stackoverflow explanation [here](https://bitcoin.stackexchange.com/questions/96204/what-is-signature-recovery)
- [Bolt11 Invoice for Lightning Payment](https://github.com/lightning/bolts/blob/master/11-payment-encoding.md) Specifications.