BOLT 3: Ambiguity in the ordering of commitment tx outputs

[pm47]

I was investigating a sig mismatch between eclair and lnd and I think we need to better specify how the outputs are to be ordered in the commitment tx.

BOLT 3 only refers to BIP 69, but I think it is not sufficient, because offered htlcs with the same amount, same payment_hash and a different cltv_expiry will have the same pubkey script but a different HTLC-Timeout (given that only the latter depends on cltv_expiry), resulting in different incompatible sigs.

I'm not entirely sure of this, but if I'm right fix is easy, e.g. we could just order following BIP69, and then by cltv_expiry.

[cfromknecht]

@pm47 @sstone another possibility for the mismatch could be the stability of the sorting algorithms used to create the BIP69 lexicographic ordering.

Consider the case in which both parties add offered outputs in the same order, such as increasing HtlcID, and then run a stable sorting algorithm. This should result in the same signature hash, even without knowledge of the cltv_expiry or other contextual data. Otherwise, it would be possible for outputs with the same amt/addr to be swapped.

LND's uses quicksort, which oc is unstable. What sorting algo does eclair use for BIP69 lexicographic ordering?

In the end, I still think that the contextual sorting is a better approach for solving the issue. By ensuring each entry contextually-unique, it makes the stability of the sort irrelevant.

[cdecker]

I don't get why stability should be of any concern to us. Either we sort by some key composed of all relevant fields (all fields that are part of the signature) and get a unique order, or the ordering doesn't matter since the items differ only in fields that are not signed, and thus have no influence on the produced signature.

Take for example a sorting of two elements aaaa and aaab, and a signature algorithm that just signs the list of prefixes of length 3. If we also sort by the same prefix we have two allowable sortings (aaaa, aaab) and (aaab, aaaa). Does it matter which one we pick? No, because the part that is signed is identical in both cases (the signature commits only to (aaa, aaa) which both sortings produce).

So either we are missing fields that are committed to in the signature, when sorting, in which case we should append them to the sorting key, otherwise it doesn't make any difference which ordering we use.

[cfromknecht]

I think we're in agreement that the end-goal is to sort on a unique tuple for each htlc, which eliminates concerns around stability :)

In the above example, yes the signatures on aaaa[:3] and aaab[:3] are the same, and thus don't influence the validity of the commitment txn. However, the dependent transactions are signed with distinct timelocks, and commit to distinct input orderings. If one party thinks the ordering is (aaaa, aaab) while the other diverges, they will view the other's HTLC signatures, spending (incorrectly) from (aaab, aaaa), as invalid.

The point I'm trying to make is that in the case where both parties add outputs to the commitment txn in the same order (i.e. log index) and apply a stable BIP69 sort, both parties will arrive at the same txn graph. Thus, the current spec would succeed in reliably sorting the outputs if both parties happen to use:

1. a stable BIP69 sort.
2. the same initial partial-ordering for non-unique keys

If 1 is false, then 2 is irrelevant and the parties may diverge sporadically.
If 1 is true, then the parties can only diverge if 2 is false.

If all implementations were following both constraints, then the issue would never have manifested. So somewhere, it seems, this stricter set of conditions is being violated. This is all in attempts to explain why the divergence is probabilistic, and also appears more frequently between specific implementation pairs.

FWIW, LND does not abide by either, which could be why the issue was discovered between LND-eclair. 🤓

[rustyrussell]

OK, since there seems to be some confusion:

This is nothing to do with sorting stability. It's nothing to do with BIP69 being somehow under-defined. It's simply that we define the htlc_signature order to be the same as the commitment tx output order, yet the identical commitment tx output can correspond to DIFFERENT htlc txs. Let's take this example:

Peer A meets peer B. A offers 3 HTLCs with the SAME AMOUNT and SAME HASH to B; the first two have CTLV X, and the third has CLTV Y:

1. HTLC id 1. amount_msat = 1000000. payment_hash = H. cltv_expiry = X.
2. HTLC id 2. amount_msat = 1000000. payment_hash = H. cltv_expiry = X.
3. HTLC id 3. amount_msat = 1000000. payment_hash = H. cltv_expiry = Y.

For simplicity let's assume that there's no to-local or to-remote output in the commitment tx. The commitment tx outputs look like:

1. amount = 1000 satoshi. script = 0
2. amount = 1000 satoshi. script = 0
3. amount = 1000 satoshi. script = 0

The witness script is (as per BOLT3):

# To remote node with revocation key
OP_DUP OP_HASH160 <RIPEMD160(SHA256(revocationpubkey))> OP_EQUAL
OP_IF
    OP_CHECKSIG
OP_ELSE
    <remote_htlcpubkey> OP_SWAP OP_SIZE 32 OP_EQUAL
    OP_NOTIF
        # To local node via HTLC-timeout transaction (timelocked).
        OP_DROP 2 OP_SWAP <local_htlcpubkey> 2 OP_CHECKMULTISIG
    OP_ELSE
        # To remote node with preimage.
        OP_HASH160 <RIPEMD160(payment_hash)> OP_EQUALVERIFY
        OP_CHECKSIG
    OP_ENDIF
OP_ENDIF

Note there's no CLTV term in here, so the three witness scripts are identical.

So far, so good. BIP69 doesn't define (of course) how to sort identical outputs, and it doesn't matter.

HOWEVER, we need to send the signatures for the HTLC-Timeout tx for each. Note the HTLC-Timeout txs have that cltv_expiry as their nLocktime field, so they are NOT IDENTICAL:

1. nLocktime X.
2. nLocktime X.
3. nLocktime Y.

Clearly, if both sides disagree on the order, the commitment tx signature will be fine, but (unless they're lucky) they'll reject the htlc_signature from the other side as invalid.

To be precise: the order of htlcs 1 and 2 is irrelevant: they are identical anyway. It's HTLC 3 which is distinct here.

SOLUTION

We simply need both sides to agree on the order of HTLC txs, for which the "commitment tx output" order is insufficient. Thus we add a rule that two identical outputs which correspond to offered HTLCs are ordered by increasing HTLC CLTV value.

Rejected Solutions

We could have simply ordered the HTLC outputs of the commitment tx by HTLC id. That's not backwards compatible though, and leaks information on HTLC ordering.

We do not need to define an exact-match ordering for anything other than offered HTLCs: (without a SHA256 collision) no other outputscripts can be identical. Received HTLCs have the CLTV in their witness script. to-local and to-remote wscripts are of different form, even if sides perversely choose the same points (though if we make this symmetrical, it still doesn't matter, because it just means you can take funds from both sides).

We do not need to care about HTLCs for different amounts or different preimages: BIP69 handles both of those already.

We do not need to use HTLC id as a differentiator. This would be canonical even in the "identical HTLC" case, which is overspecification, and a layering violation. It also leaks information on the HTLC ordering, though only for a very small corner case.

[Edit: Oh, and while we could specify a defined input order and a stable sort, that seems like the most baroque way possible that we could resolve this. In particular, in c-lightning our input order is either the order they came in (htlc_id order) the order we got them from the db, or a bit of both, so there's not even a "natural" input order to use. Plus a specification should list what you must do, not how you should do it (though sometimes giving a how to do it is the clearest way). I think @cfromknecht's point is kinda valid, it's also a distraction here]