Multi-hop lock from invisible script

Author: Jonas Nick

Source: https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/multi-hop-locks.md

"Multi-hop locks" refer to protocols that allow two parties to exchange funds and payment proofs without manually funding a multi-signature output. That is, these two parties are connected through intermediate nodes that have shared multi-signature outputs with each of them. Currently, multi-hop locks based on cryptographic hash functions are used for forwarding in the Lightning Network protocol.

Multi-hop locks based on "scriptless scripts" first appeared in a post on the mimblewimble mailing list and were formally defined in the paper "Privacy-Preserving Multi-Hop Locks for Blockchain Scalability and Interoperability". By using scriptless scripts, the final transaction size is smaller and closer to a regular transaction, thus improving privacy. More importantly, it can hide the correlation between payments, meaning that the nodes participating in a multi-hop lock will not be able to determine whether they are on the same path, i.e., they cannot know if they are forwarding the same transaction (unless they perform timing and amount analysis). Payment correlation attacks become particularly dangerous when the first and last intermediate nodes in the forwarding path are controlled by the same entity, as they will know the source and destination of a payment. In addition, scriptless script multi-hop locks also support optimized payment proofs and "atomic multi-path payments" (see below).

Notation

• Pij is the MuSig2 aggregated public key of users i and j. The MuSig2 paper provides more details.
• T := t*G, where t is a randomly chosen value, called the "adapter secret value", and T is called the "adapter point".
• psig(i, m, T) denotes a partial signature from signer i on message m using the adapter point T, which can be aggregated into a 2-of-2 MuSig2 signature. For brevity, the other signer is not shown in the notation; typically, the other signer is the node i has a channel with, and will be determined by context. It is called a "partial" or "pre-signature" because it needs to be combined with the other party's partial signature to form a valid Schnorr signature.
• sig(m, T) := psig(i, m, T) + psig(j, m, T) + t is the final complete Schnorr signature from users i and j.

Protocol

In the initialization phase, the payment receiver first randomly chooses a z and sends z*G to the payment sender. The sender will then set up a multi-hop lock to ensure that a successful payment will reveal z only to her, and to no one else. Knowledge of z can serve as a payment proof, similar to the "payment preimage" in the current Lightning Network (details below).

We depict the payment flow from the leftmost sender, through intermediate nodes, to the rightmost receiver.

Then, the sender will establish a tuple (Li, yi, Ri) for each node i, where Li is the "left-facing lock" and Ri is the "right-facing lock":

• Each yi is a uniformly random scalar
• The sender's own left-facing lock L0 is set to z*G, which was received from the receiver earlier.
• For the right-facing lock of node 0 <= i < n, and the left-facing lock Lj of node j = i + 1, the sender sets Ri <- Li + yi*G and Lj <- Ri (see the diagram above) (Translator's note: This means that the right-facing lock of the previous node is the left-facing lock of the next node)

Note that in the Lightning Network, the sender does not directly send (Li,yi,Ri) to the intermediate nodes: They will use onion routing to carry these values, while keeping the intermediate nodes' identities hidden.

In the update phase, the adjacent nodes will include a multi-signature output in their off-chain transaction, similar to how HTLC outputs are added to transactions in the current Lightning Network. We call this new type of scriptless script output a "Point Time-Locked Contract (PTLC)". Like HTLC, PTLC also has a timeout condition that allows the left-side node to recover its funds in case of payment failure. But unlike HTLC, PTLC is just a regular 2-of-2 MuSig2 output, and the hash lock is implicitly added to the output by receiving a partial signature (see below). For demonstration purposes, we assume the use of eltoo-style channels, meaning the parties have symmetric state and no need for revocation.

If the payment does not time out, the funds in the scriptless script PTLC output shared by the adjacent nodes will be claimed by the right-side node. Therefore, the left-side node i needs to create a transaction txj that spends this PTLC and sends the funds to an output controlled by the right-side node j. Assuming the nonce exchange round required by the MuSig2 signing protocol has already occurred at a more convenient time (e.g., when establishing a connection), this round of communication will not happen during the critical payment flow.

Upon receiving the new PTLC, the right-side node j will create the transaction txj and its partial signature psig(j,txj,Lj). The left-side node will verify this partial signature and then send its own partial signature on txj to the right-side node in either of the following two cases:

• The left-side node is the sender
• The left-side node i has received the partial signature psig(i-1,txi,T-yi*G) from the previous node i-1 on txi. Combined with the just-received partial signature from the right-side node, it can be held, and the left-side node can open the left-facing lock and claim the funds using txi, as shown in the diagram above.

So the update phase progresses from the leftmost pair of nodes all the way to the rightmost set of nodes. After receiving the partial signature from the left-side node, the right-side node can quickly complete the signature once it knows the secret of its left-facing lock. To reduce the overall communication rounds, the initialization and update phases can be combined (e.g., using the onion routing in the Lightning Network).

The settlement phase starts after the receiver receives the partial signature from its left-side node. The multi-hop lock was set up by the sender, and the receiver can add its secret z to the partial signature from the left-side node, and then aggregate its own partial signature on top. Finally, it can obtain a signature valid for the transaction to the right-side node (the receiver). At this point, the right-side node can broadcast the transaction and settle on-chain (in case the left-side node disappears or attempts to cheat).

After the left-side node knows the transaction signature, it can learn the secret of the right-facing lock by subtracting the partial signature it received from the right-side node and its own partial signature.

sig(tx,T) - psig(i,tx,Ri) - psig(j,tx,Lj) = yj

Alternatively, the right-hand node can directly send the secret value yj to the left-hand node, and then request an update of the commitment transaction (based on LN-penalty) or a settlement transaction (based on eltoo), thereby removing the PTLC, and then the output of the left-hand node will be reduced by the payment amount, while the output of the right-hand node will be increased by the payment amount. If the left-hand node does not follow the update, the right-hand node can still broadcast its own transaction before the PTLC expires.

In any case, as long as the recipient claims the payment, the left-hand node can know the right-facing lock secret value, and then can calculate its left-facing lock secret value by subtracting yi, and then create the final Schnorr signature for its own transaction. This process will occur on each node until the sender, who will know the payment proof z used to complete the payment.

Payment Proof (PoP)

The difference between multi-hop locks based on PTLC and multi-hop locks based on HTLC is that the payment proof (z) is only known to the sender, and not to each node along the path. Therefore, the payment proof can be used to authenticate the identity of the payer to the recipient. There is no need to reveal the PoP itself, a signature of z*G can be provided. Since the association between payments is broken, the intermediate nodes cannot associate the PoP with a particular payment.

Obviously, it is not only the sender who can know z. Anyone the recipient and sender are willing to share z with can know it, so it is still unclear who the real payer is. Therefore, a signed statement (lightning invoice) from the recipient to the sender should include z*G and the sender's public key. Then the PoP includes both a signature of z and a signature of the sender's private key, which can only be provided by the sender (or someone the sender chooses to cooperate with).

Ideally, if a static invoice can be paid by multiple parties, it would allow for collaborative payments and eliminate the need for additional communication with the recipient. But this is incompatible with the payment proof, as the PoP must be created from ephemeral randomness for each payment. However, repeated payments from the same sender can be achieved using a hash chain.

Atomic Multi-Path Payments (AMP)

Using scriptless script multi-hop locks, it is possible to implement a multi-path payment similar to "base MPP", while allowing the payment associations between paths to be hidden. The sender uses uncorrelated locks to create multiple paths to the recipient, such that the recipient claiming any part of the payment will reveal the payment proof (z) to the sender. Since the recipient does not want to reveal the PoP by only claiming a partial payment, they will wait for all paths to be fully established before taking the entire payment at once.

In the original "base AMP proposal", the "atomicity" was not just achieved through incentives, but also relied on intentional path planning, such that the recipient's secret value (z) would only be revealed once all paths were established. However, in this proposal, the payer could not obtain the payment proof. Using scriptless script multi-hop locks, we can achieve the atomicity of the original base AMP proposal, while also obtaining the payment proof. This is referred to as "high AMP".

In high AMP, the sender first chooses a random number q, and then selects some random numbers q1,...,qn based on the number of paths n, such that q = q1 + ... + qn. The sender adds q*G to the payment point of the recipient in each path. This way, the recipient cannot claim any partial payment, as they do not know q. However, the sender sends the corresponding qi to the recipient in each path i they plan. Thus, the recipient can only calculate q and claim the full payment when all paths are successfully established.

Cancellable Payments

In the current Lightning Network, payments can get stuck for a long time if the intermediate nodes go offline while forwarding the payment. The payer cannot safely retry (other paths) because the (original path's) intermediate nodes may come back online before the PTLC timeout and make the payer pay again.

Example scenario:

1. Alice sends a 10mBTC PTLC to Bob, hoping Bob will forward it to Dave (Alice -> Bob -> Dave).
2. Bob receives the PTLC but does not forward anything to Dave.
3. After a few blocks, Alice loses patience and tries to forward the payment through Carol (Alice -> Carol -> Dave).
4. This payment succeeds, Alice correctly pays 10mBTC to Dave and receives the payment proof.
5. However, Bob comes back online before his PTLC times out and forwards 10mBTC to Dave.
6. For Dave, this is a windfall, so Dave accepts it and returns the payment proof.
7. Finally, Alice receives another payment proof, but she has paid 20mBTC instead of 10mBTC.

This can be prevented if the payment requires a secret value from the sender to complete. This solution was originally called "Cancellable Payments".

The sender's secret value is y0 + y1 + y2. In the initialization phase, Alice cannot send it to Dave. Alice uses (z + y0 + y1 + y2) * G as Dave's left-facing lock, effectively making Dave reveal (y0 + y1 + y2) * G. In the late update phase, Dave cannot create a signature because he does not know y0 + y1 + y2. Dave can request y0 + y1 + y2 from Alice (and show (y0 + y1 + y2) * G to prove he has received the PTLC). When Alice receives this request, she knows the PTLC has been properly delivered to Dave. She can safely send y0 + y1 + y2 to Dave, allowing Dave to proceed to the settlement phase.

Note that this does not prevent payments from getting stuck in the settlement phase (if nodes go offline). However, the intermediate nodes have much greater incentive to stay online during settlement: 'He Yi' has been translated into 'He Yi'. 'Block' has been translated into 'Block'. 'Nonce' has been translated into 'Nonce'. 'Script' has been translated into 'Script'. 'TRON' has been translated into 'TRON'. 'Amp' has been translated into 'Amp'. 'BTC' has been translated into 'BTC'. 'HT' has been translated into 'HT'. 'GT' has been translated into 'GT'. 'OP' has been translated into 'OP'. 'AR' has been translated into 'AR'. 'AMP' has been translated into 'AMP'. 'RON' has been translated into 'RON'. 'ONG' has been translated into 'ONG'.

• During the update phase, they will receive bitcoins from the peer node on the left: they have not sent anything yet, so the only incentive is the forwarding fee they will receive
• During the settlement phase, they have already sent bitcoins to their peer node on the right: now they have the incentive to return the payment proof to collect the incoming payment

Resources

• MuSig2
• Lightning Network protocol
• Scripless Scripts in Lightning
• Privacy-preserving Multi-hop Locks for Blockchain Scalability and Interoperability
• Payment Decorrelation
• eltoo
• Post-Schnorr Lightning Txs
• Bolt11 in the world of Scriptless Scripts
• Base AMP
• Stuckless Payments