A discussion on lock time of multi-hop payment in payment channel network

English CKB Development & Technical Discussion
1

This post discusses the problem of locking time in multi-hop payments. First of all, many thanks to @janx, @doitian, @thewawar and @driftluo for their help and feedback on this problem.

Introduction

HTLC is a contract between two parties (Alice and Bob, for example), which has the following logic. Alice offers 100 CKBytes and tells Bob, “if you can tell me the preimage of the hash value H before the block height 100, then you can take the money. Otherwise, the money will be refunded”. HTLC is utilized by many blockchain applications, what I will discuss in this post is its role in multi-hop payments. You can find how it works here.

Problem statement

I know at this point the HTLC in your mind must look like this: Bob can take the money with preimage before the HTLC expires. Otherwise, the money belongs to Alice. However, the story is quite different in BTC. Let’s think about how to implement this contract (script)? Suppose that the expiration time of HTLC is E, the hash value is H and the preimage is P. Then the unlocking condition of this cell (UTXO) should be

  1. Bob shows P before E.

  2. Alice refunds after E.

So, we need the following three functionalities in the contract.

  1. Check P.

  2. Prevent Alice from getting the refund before E.

  3. Prevent Bob from submitting the preimage after E.

The first one can be achieved by any script language with if logic and hash function. The second one can be achieved by since in CKB or nounce in BTC, but how about the third one? The third functionality is a mechanism called until. AFAIK, there is no such mechanism in BTC, which means Bob can still unlock the funds through preimage after the expiration date.

Let’s pause the discussion for a moment and talk about how multi-hop payments work in Lightning Network. We assume that Alice pays Carol through Bob, and the corresponding HTLC expiration block heights are E_{AB} and E_{BC}, respectively. Also, we assume that a transaction takes \Delta blocks from being broadcast to being on-chain and confirmed. We suppose the deadline of HTLC_{BC} is reached, and both Bob and Carol intend to unlock HTLC_{BC}. Note that the until mechanism is lacking in this setting, so Carol can unlock HTLC_{BC} by submitting the preimage after the deadline.

  • At E_{BC}

  • action: Bob submits refund transactions Tx^{refund}_{BC}.

  • action: Carol shows P and trys to get the payments in Tx^{payment}_{BC}.

Unfortunately, Carol’s transaction goes up first. But the good news is that Bob now knows the preimage, so he can use it to unlock HTLC_{AB}.

  • At E_{BC}+\Delta

  • result of last step: Tx^{payment}_{BC} wins.

  • action: Bob knows P from blockchain and trys to get the payments in Tx^{payment}_{AB}.

Tx^{payment}_{AB} is on-chain.

  • At E_{BC}+2\Delta

  • result of last step: Tx^{payment}_{AB} wins.

At this point, we know that Bob will get paid until E_{BC}+2\Delta in the worst case. Therefore, we can get the following inequality

E_{AB} \geq E_{BC}+2\Delta

In brief, we stop Alice from initiating a refund before Bob can get the payment with preimage. And this can occur at every hop so that the expiration block height is incremental with the number of hops reversely (1st hop has the latest expiry time). If we consider the lock time in the last hop as 2\Delta too, then the sum of multi-hop payment locking time in LN of length N is

L_{sum}=2\Delta+4\Delta+...+2N\Delta

To make the problem easier to understand, I have omitted some details in the above description. What I want to convey is the complexity of L_{sum} is O(N^2) in multi-hop payment in Lightning Network. Then we will discuss how to reduce it to O(N) on ckb in the remainder of the post.

Fortunately, we can support until mechanism on CKB thanks to its powerful programmability. In a nutshell, users can add preimage to their own cell first, then use it as cell_deps in the HTLC unlocking transaction. Meanwhile, he should add the hash of block that generates the cell in header_deps . At this point, we ask the script to read the block header and verify the block height is before the deadline. From this, we can make actions valid only before a certain block height.

Okay, now that we have the until mechanism, is the problem solved? The answer is no. Following the example above, but with the difference that we now have the until mechanism and an extra hop in the path, i.e. the scenario is Alice paying Dave (A->B->C->D). Here we assume that the expiration time E is the same for each hop. Then for Dave, if he wants to get this payment, he needs to submit the preimage before N-\Delta to ensure it will be on-chain before E. And Bob is asked to do the same because they have the same expiration date. However, Bob knows nothing about preimage at N-\Delta. There are two solutions to this problem

  1. Make the act that Dave submitting the preimage able to affect every hop in the path.

  2. Let all nodes on the path listen to the public zone (blockchain, mempool for example).

Sprites adopts the former, and I will discuss how it works in the next section.

Sprites

Sprites is an Ether-based multi-hop payment solution that consist of two contracts contract_{htlc} and contract_{pm} (preimage manager). The former is an HTLC contract, but the difference is that it works by asking contract_{pm} to determine the outcome. The latter is a preimage manager, which provides two interfaces

  1. function submitPreimage(bytes32 x)

  2. function revealedBefore(bytes32 h, uint T) returns(bool)

submitPreimage allows the user to submit a preimage P and store it as dictionary {H: T}, where H is the hash of P and T is the block number containing the transaction. The logic of until is implied here, that is, if the user submits a preimage after the expiration date, the block height being recorded will not meet the requirements. revealedBefore provides a query interface to contract_{htlc}, returns true if the preimage of H was committed before T, false otherwise.

Now, let’s go back to the payment scenarios. Likewise, Dave submits the preimage to contract_{pm} before E-\Delta and the transaction is on-chain before E. Now, Bob can initiate a dispute in contract_{htlc}^{AB} without knowing the preimage, because Dave’s behaviour affects all HTLCs with preimage P through a globally shared contract_{pm}.

Now, you might think that global sharing is the key to achieving constant lock time, but I would like to give an example to illustrate the importance of until. Let’s assume Sprite without the until mechanism. it’s simple, we just need to remove the block num when submitting the preimage. In other words, the revealedBefore only looks for the existence of the corresponding hash without paying attention to when it was committed. Now let’s still assume the scenario where Alice pays Carol. The expiration time E has now been reached. Alice and Bob both initiate dispute transactions Tx_{AB} and Tx_{BC}, Carol submits the preimage transaction Tx_{preimage}. At this point all three transactions can be accepted by the blockchain, a possible order is.

  1. Tx_{AB}

  2. Tx_{preimage}

  3. Tx_{BC}

Since the preimage had not been submitted at the time, Tx_{AB} ended up with a refund, i.e., Alice got money. However, Tx_{BC} had succeeded because the preimage has been revealed (Carol got coins). At this point, Bob suffered a loss. Thus a pair of conscious nodes can use this to scam money. A good protocol should not have the possibility of rational nodes losing money. Therefore, the until mechanism is essential.

Story in CKB

Sprites relies on a globally shared contract, the simplest equivalence is cell_{pm}. However, there would be the state sharing problem. First, collisions occur when two users want to submit preimages with the same cell_{pm} as input. Secondly, when I want to unlock HTLC with cell_{pm} as a cell_dep , someone else may change it too.

So I’m thinking of another direction, having nodes on the path look for the proof cell on-chain and use it to unlock their HTLC. Specifically, if Dave submits a proof cell before E-\Delta, then all nodes can see it after E, then both Bob and Carol can utilize it to unlock the corresponding HTLCs.

However, there are two concerns about this solution. First, the cell in cell_deps must be live. How can we ensure the proof cell is live when Bob and Carol want to use it? Second, after HTLC expires, one party can take the proof cell to get the payment, but the other party can initiate a refund. How to solve this conflict?

For the first concern, we use the time lock. The lock script of the proof cell is


lock.args:

<owner's pubkey> <htlc_expire_date> <grace_period>

Witnesses

<Signature>

First, we will require expiration date in HTLC cell must be consistent with htlc_expire_date field of the proof_cell. Second, we will require that the proof cell cannot be unlocked before htlc_expire_date+grace_period, where grace_period is utilized to allow other nodes on the same path to unlock their payments. At this point, we ensure that each node has enough time to use the proof cell to unlock their payment.

For the second problem, I prefer to call it proof of absence. That is, how do we go about proving on the blockchain that something didn’t happen? A naive solution is that we first let one party give the proof of attendance. If it is not provided within this period, then absence is proved. In HTLC, we allow Bob to unlock HTLC_{AB} after E by providing proof cell in cell_deps. Then, we allow Alice to unlock HTLC_{AB} unconditionally after E+grace\_period.

Discussion

In a nutshell, this post discusses the locking time of multi-hop payments. Specifically, I elaborate on the problem, introducing the Ether-based Sprites and the proof cell on CKB. Next, I would like to discuss the pros and cons of these two solutions.

Atomicity

As with many Layer 2 designs, I introduce grace period (challenge period) at the time of final settlement of HTLC in the proof cell. Thus, the atomicity of multi-hop payments may be broken when the network has a traffic jam. But I’ve recently seen very interesting discussions about elastic challenge periods. In short, it means that the challenge period will be extended when the network is congested. This effectively mitigates the risk of losing funding due to network congestion.

There is no doubt that Sprites excels in atomicity. Neither party needs to worry about the other cheating because the outcome of the dispute is strongly dependent on contract_{pm}. In the meantime, the contract has irreversibility. The results of the HTLC are determined and can not be modified after the deadline.

If you want to improve the atomicity of the proof cell, I highly recommend that you think about the following two questions.

  1. How to efficiently prove the non-existence of proof cell?

  2. How to achieve the elastic challenge period on CKB?

Capacity cost

As I discussed above, Sprites must have irreversibility. Then when we want to port Sprites to CKB, the capacity required by cell_{pm} will keep growing. You may ask, “Well, can we clean the cell_pm regularly?” From my perspective, the answer is no.

If you choose to clean up regularly, that’s actually adding a challenge period. You are telling the user: “Please come and reference this contract before I clean it up or you won’t find the record you need for dispute”. So a simple thought, can I wait until all the HTLC disputes that require this preimage have been processed and then clean it up? Unfortunately, not all users are willing to settle disputes on-chain. Because it means they need to close the channel between them. So you will most likely not be able to collect a complete dispute record. On the contrary, proof cell is economical in terms of the cost it requires. All proof cells need to be locked only during the grace period, and users can spend them after that.

Therefore, if you wish to implement Sprites in CKB, then I suggest you think about the following two questions.

  1. How to solve the state sharing problem?

  2. How do you address the continued growth in space occupation that Sprites bring?

If you have any idea about the above mentioned open challenges, don’t hesitate to PM me. Also, any comments are welcome.

6 Likes
3

（翻译）关于『支付通道网络中多跳支付的锁定时间』的讨论

原文：A discussion on lock time of multi-hop payment in payment channel network

介绍

HTLC（Hash Time Lock Contract，哈希时间锁合约） 是涉及双方（例如：Alice 和 Bob）之间的一份合约，合约逻辑可以简单抽象为：

Alice 拿出 100 CKB 并且告诉 Bob：“如果你能在区块高度 100 之前，告诉我哈希值H的原像（preimage，Hash(R)=H，则 R 为 H 的原像），那么你就可以拿走这 100 CKB；没有的话，钱就会退回。”

HTLC 已经应用在许多 DApp 中，本文我将着重聊聊其在多跳支付中的角色。进一步了解 HTLC 请查阅此文。

问题陈述

我估计此时你脑海中对 HTLC 的运行流程是这样演绎的：

Bob 能在 HTLC 到期前，使用正确的原像（preimage）拿走资金；或者，Alice 失败了，资金退回给了 Alice。

不过，在比特币网络中，故事的剧本走向就完全不同了。

首先，我们先来想想如何实现这个合约（脚本）？

假设 HTLC 的到期时间为E，哈希值为H，原像为P，那么这笔资金所在的 Cell 的解锁条件应该为：

  1. 在E到期前，Bob 证明了P。
  2. 在E过期后，Alice 取回了资金。

因此，在合约中，我们需要以下三个功能：

  1. 检查P的正确性。
  2. 防止 Alice 在E到期前取回资金。
  3. 防止 Bob 在E到期后仍然提交P。

第一个功能可以通过任何脚本语言的 if 逻辑和哈希函数来实现。

第二个功能可以通过 CKB 中的since参数或者比特币协议中的nounce参数来实现。

第三个功能可以叫作一种until机制。据我所知，比特币协议中没有这种机制，也就是说，即使E到期后，Bob 仍然可以解锁资金。

我们先就此打住，先来聊聊在闪电网络中，多跳支付的工作原理。

我们假设 Alice 通过 Bob 向 Carol 付款，对应的 HTLC 到期区块高度分别为EAB和EBC。

我们也假设一笔交易从开始广播到上链完成确认需要经历Δ个区块时间，我们假设 HTLCBC 的截止日期也到，Bob 和 Carol 都打算解锁HTLCBC；由于在当前的设置中，还不具备until机制，所以 Carol 在到期后依旧可以提交原像（preimage）解锁HTLCBC。

  • 区块高度为EBC时
  • 操作：Bob 提交取回资金的交易TxrefundBC
  • 操作：Carol 出示P并且在交易TxpaymentBC中试图拿走资金

可是，Carol 交易更早地提交了交易。不过还好 Bob 现在也知道了原像（preimage），所以他也可以使用原像解锁HTLCAB。

  • 区块高度为EBC+Δ时
  • 结果：由于 Carol 的交易更早提交，所以其交易TxpaymentBC优先执行
  • 操作：Bob 从链上知道P，并在交易TxpaymentAB中试图拿走资金。

TxpaymentAB为脸上交易。

  • 区块高度为EBC+2Δ时
  • 结果：TxpaymentAB交易成功执行。

现在，我们知道，在最坏的情况下，在区块高度为EBC+2Δ之前，Bob 都能拿走资金。因此，我们可以得到以下不等式：

EAB≥EBC+2Δ

简而言之，我们在 Bob 用原像拿走资金之前，阻止 Alice 发起退款。而且这种情况可以发生在每一跳，每一跳的到期区块高度随着跳数反向递增（第一跳的到期时间最晚）。如果我们考虑将最后一跳的锁定时间定为2Δ，那么在闪电网络中，长度为N的多跳支付的锁定时间总和为：

Lsum=2Δ+4Δ+…+2NΔ

为了使问题更容易理解，在上面的描述中我省略了一些细节。

归根结底，我想说的是，在闪电网络的多跳支付中，Lsum的复杂度是O(N2)。

在接下来的篇幅中，我们将讨论如何在 CKB 上将其该复杂度降低到O(N)。

幸运地是，由于 CKB 强大的可编程性，我们能够在 CKB 上实现until机制。总的来说，用户可以先将原像添加到自己的 cell 中，然后在 HTLC 解锁交易中作为cell_deps来使用。同时，用户应该在header_deps中添加生成 cell 的区块哈希值。然后，我们要求脚本读取区块头，并验证区块高度是否在截止日期之前。这样，我么就可以让操作只在某个区块高度之前有效。

好了，现在我们有了until机制，可是问题解决了吗？显然还没有。继续上述的例子，不过现在我们有了until机制，并且在路径上多了一跳（即现在是 Alice 支付给 Dave，A → B → C → D）.

这里我们假设每一跳的到期时间E都是一样的，那么对于 Dave 来说，如果他想得到这笔资金，他需要在区块高度为N−Δ之前提交原像，以确保在E之前上链。Bob 也一样，因为他们的到期时间是一样的。但是 Bob 在区块高度为N−Δ时对原像一无所知。这个问题有两种解决方案：

  1. 使 Dave 提交原像的操作能够影响路径中的每一跳。
  2. 让路径上的所有节点监听公共域（如链上，内存池）

Sprites采用第一种解决方案，下面章节我们来讨论一下它的工作原理。

Sprites

Sprites 是一个基于以太坊的多跳支付解决方案，由两份合约contracthtlc和contractpm（preimage manager）组成。前者是一份 HTLC 合约，但不同的是，它由contractpm来决定结果。后者是一个原像管理器，提供两个接口：

  1. function submitPreimage(bytes32 x)
  2. function revealedBefore(bytes32 h, uint T) returns(bool)

submitPreimage可以让用户提交一个原像P并且保存为字典 {H:T}, 其中H是P的哈希值，T是交易所在区块高度。until的逻辑隐藏于此：

如果用户在到期时间后提交了一个原像，会与已记录的区块高度不匹配。revealedBefore是一个访问contracthtlc的接口，如果H的原像是在区块高度T之前提交的，则返回 true；反之返回 false。

现在，我们回到支付场景。同样地，Dave 在区块高度E−Δ之前向contractpm提交了原像，交易在区块高度E之前已上链。现在，Bob 在不知道原像的情况下，可以在contractABhtlc中发起争议，因为 Dave 的行为会通过全局共享的contractpm影响到所有具有原像P的HTLC。

现在，你可能认为全局共享是实现固定锁定时间的关键，但我想举一个例子来说明unti的重要性。我们假设 Sprite 没有until机制（很简单，我们只需要在提交原像时去掉区块高度即可）。换句话说，revealedBefore只判断原像是否正确，而不关心它是什么时候提交的。

我们仍然假设 Alice 支付给 Carol 的场景，现在已经到了到期时间E。Alice 和 Bob 都发起了争议交易TxAB和TxBC，Carol 提交了原像交易Txpreimage。此时，这三笔交易都可以被网络接受，可能的顺序如下：

  1. TxAB
  2. Txpreimage
  3. TxBC

由于TxAB交易确认时，Txpreimage交易尚未提交，所以TxAB能够拿回资金。然而，因为提供了原像，所以TxBC交易也能成功（即 Carol 也能够拿到资金）。这时候，Bob 就吃了哑巴亏。因此，一对共谋的节点可以利用这个来骗钱。一个好的协议不应该有理性节点赔钱的可能。因此，until机制是必不可少的。

CKB 版实现

Sprites依赖于全局共享的合约，在 CKB 中我们可以等价为cellpm，不过存在状态共享问题。首先，当两个用户想要用同一个cellpm作为输入提交原像时，就会发生冲突；其次，当我想要使用cellpm作为cell_dep解锁 HTLC 时，别人可能会修改cellpm。

所以我另辟蹊径，通过让路径上节点来搜索链上的proof cell，并利用它来解锁自己的 HTLC。具体来说，就是如果 Dave 在区块高度E−Δ之前提交了一个 proof cell，然后所有节点都可以在区块高度E后看到它，那么 Bob 和 Carol 都可以利用它来解锁相应的 HTLC。

不过，这个解决方案有两个问题。首先，cell_deps中的 cell 必须是可用 cell，可是当 Bob 和 Carol 想要使用 proof cell 时，我们如何确保它是可用 cell 呢？第二，HTLC 到期后，一方可以通过 proof cell 取回资金，但是另一方也可以发起退款。如何解决这个冲突？

对于第一个问题，我们使用时间锁来解决，proof cell 的锁脚本（lock script）如下：

lock.args:
<owner’s pubkey> <htlc_expire_date> <grace_period>
Witnesses

首先，我们要求 HTLC cell 中的到期时间必须与 proof cell 中的字段htlc_expire_date一致。其次，我们会要求 proof cell 在htlc_expire_date+grace_period之前不能解锁，其中grace_period是用来让同一路经上的其他节点解锁资金的。此时，我们要保证每个节点有足够的时间来使用 proof cell 来解锁他们的资金。

对于第二个问题，我更愿意把它叫作**“不在场证明（proof of absence）”。就是说，我们如何在区块链上证明某件事情没有发生？一个天真的解决方案是，我们先让一方出示“在场证明（proof of attendance）”。如果在这段时间内没有提供，那么就证明不在场**。在 HTLC 中，我们可以让 Bob 在区块高度E之后通过提供cell_deps中的 proof cell 来解锁HTLCAB；然后，我们可以让 Alice 在区块高度E+grace_period后无条件解锁HTLCAB。

讨论一番

总的来说，本文讨论的是多跳支付的锁定时间。

具体来说，我先是进行了问题陈述，然后介绍了基于以太坊的 Sprites 和 CKB 上的 proof cell。

接下来，我想讨论一下这两种解决方案的优缺点。

原子性

跟许多 Layer 2 设计一样，我在 proof cell 的 HTLC 最终结算时引入了宽限期（挑战期）。因此，当网络拥堵时，多跳支付的原子性可能会被打破。但我最近看到了一些关于弹性挑战期的讨论。简而言之，就是当网络拥堵时，挑战期会被延长，这有效地降低了因网络拥堵而导致资金损失的风险。

毫无疑问，Sprites 在原子性方面表现出色。任何一方都不需要担心对方作弊，因为争端的结果仅取决于contractpm。同时，合约具有不可逆转性，HTLC 的结果是确定的，过了期限就不能修改。

如果你想要提高 proof cell 的原子性，我强烈建议你思考以下两个问题：

  1. 如何有效证明 proof cell 不存在？
  2. 在 CKB 上如何实现弹性挑战期？

容量成本

As I discussed above, Sprites must have irreversibility. Then when we want to port Sprites to CKB, the capacity required bycellpmwill keep growing. You may ask, “Well, can we clean thecellpmregularly?” From my perspective, the answer is no.

正如上文提及的，Sprites 必须具有不可逆转性。那么当我们要把 Sprites 移植到 CKB 时，cellpm所需要的容量（capacity ）就会不断增加。

你可能会问：“那么我们可以定期清理cellpm吗？”

从我的角度来看，是不可以的。

如果你选择定期清理，其实就是增加了一个挑战期。

你是在告诉用户：“在我清理之前，请先来引用这份合约，否则你将找不到你需要的争议记录。”

你可能会这么想：“能不能等所有需要这个原像的 HTLC 争议处理完毕后再清理？”

遗憾地是，并不是所有用户都愿意在链上解决争议，因为这意味着他们需要关闭他们之间的通道。所以你很可能无法收集到完整的争议记录。相反，proof cell 的成本是相对经济的，所有的 proof cell 只需要在宽限期内锁定，之后用户就可以正常消费这个 cell 了。

因此，如果你想在 CKB 中实现 Sprites，那么我建议你思考以下两个问题：

  1. 如何解决状态共享问题？
  2. 如何解决 Sprites 带来的持续增长的空间占用？

如果你对上述难题有什么想法，不要犹豫，请私信联系我。另外，欢迎大家提出任何意见。

3 Likes