Two-party Lightning Trade Protocol with Threshold Escrow

This is a Bisq Network proposal. Please familiarize yourself with the submission and review process.

Introduction

In https://github.com/bisq-network/proposals/issues/373, a three-party lightning trade protocol was described, which involved setting up pending lightning payments (routes of HTLCs) between a BTC buyer, seller and a third party (escrow agent), with the latter playing a passive role after the initial payment setup and finalisation of their receipt of the escrow. In the event of a dispute, the remaining pending lightning payments simply time out and the escrow ends up in the hands of the third party, otherwise all the payments finalise and escrow falls back into the hands of the two traders.

There are a few problems with that protocol:

1) It involves setting up six pending lightning payments in total, forming a complete directed graph between the three parties and moving a total of three times the escrow amount. This requires the parties (especially the escrow agent) to have quite a lot of channel capacity. Furthermore, experimenting with the LND gRPC API indicates that setting up pending lightning payments is a little temperamental, so its not clear setting up six of them will work well at all. 2) The sender of a lightning payment normally needs to know the node ID (public key) of the recipient, otherwise he cannot route the payment. So it's hard to prevent all three parties learning the other two parties' node IDs. This is bad for privacy, since the escrow agent learns all the traders' node IDs and those are static (without closing and reopening all ones lightning channels). 3) Since there is a single active third party, the protocol is not very decentralised. This could cause legal problems for Bisq, as insufficiently decentralised financial organisations could fall under the scope of some recent EU regulations.

In this proposal, an alternative two-party lightning protocol is described. Instead of six lightning payments, the buyer simply makes a pending payment (of his security deposit) to the seller and the seller makes a pending payment (of the trade amount plus the security deposit) to the buyer. If the trade closes successfully, the two pending payments are finalised, transferring the lightning BTC trade amount to the buyer. Otherwise, the traders confiscate each other's deposit and forward it onto a third party, with either an on-chain or an off-chain (lightning) forwarding payment. In the case of the former, there need not be a single recipient. Instead, it could work much like the current system of multiple Burning Men in Bisq 1, with the confiscated amount being divided up between them.

This requires the ability to force through the counterparty's payment in the event of arbitration. In particular, the buyer needs to be able to force-finalise the seller's pending lightning payment. What is to stop the buyer from simply running off with that money instead of forwarding it on? By completing the forwarding payment, a secret key is revealed to the buyer which allows him to learn the SHA-256 preimage of the seller's payment hash. Instead of entrusting the secret key with a single third party, which would make the protocol centralised, we may break it up into shares held by a set of third parties, similar to Shamir secret sharing. To forward on the seller's payment, the buyer would need to handshake with a quorum (say 40%) of the key shareholders, to negotiate a multisig BTC address (in the simpler case of an on-chain payment) to pay into. Once payment to that address is made, any quorum of key shareholders may then collectively spend that UTXO (to anywhere, with a prepared tx pre-signed by the buyer). Doing so reveals the secret key that the buyer needs to force through the seller's payment. Otherwise, the buyer may claim the on-chain amount back with a timelocked tx in case too many of the key shareholders are unresponsive to be able to form a quorum.

Making the on-chain forwarding efficient and practical will involve the use of Schnorr signatures for threshold multisig and hence taproot. In this way, there could be very many key shares (100's or maybe 1000's) divided up amongst a dozen or so shareholders, so there is no need for them to have equal weight when forming a quorum.

Setting up the key shares

The secret key revealed to the buyer, when the seller's payment is forwarded for arbitration, shall be a secp256k1 ("bitcoin curve") private key (scalar), with corresponding public key (curve point) known to both the buyer and seller at the start of the trade. In order to allow any quorum to reveal the private key, distinct from the set of key shareholders which assigns the public key to the seller to use with the given trade, it is necessary to generate it in advance in cooperation with all the key shareholders, and make it single use.

For this reason, each key shareholder must in fact hold a large list (say a million elements long) of private key sub-shares p_ij for j = 1,...,1000000, where i is the index of key shareholder, say from 1 to N. Thus there would be an N * 1000000 matrix S = (p_ij) of private key sub-shares, which are secp256k1 scalars. This must be generated in advance of all the trading, in a big multiparty computation between all the key shareholders. Then, each trade would use a fresh index j out of the list of a million indices, never to be used again, using up the column (p_1j,...,p_Nj) of sub-shares in the matrix S.

Similar to the techniques in Shamir secret sharing, we pick an MDS (maximum distance separable) length N linear code C over the scalar field (and hence possessing an MDS dual code C^⊥), such as the Reed-Solomon code. (The code being 'good', that is, large distance like an MDS code, ensures that any quorum can recover the respective secret and the dual code being good ensures that any sub-quorum will not be able to.) Then we require each column (p_1j,...,p_Nj) of the matrix S to be a C-codeword. This will allow the entire column of sub-shares to be recovered even if only a subset of p_1j,...,p_Nj are revealed, as long as the set is at least as big as the quorum size.

The construction of the matrix S is trustless in the sense that no sub-quorum of key shareholders may leak anything besides their own secrets and no party or parties may collude to result in an invalid S without it being detected. Achieving the former is reasonably straightforward: get each key shareholder to produce his own N 1000000 matrix S_i (for shareholder index i in 1,...,N), satisfying the required properties, namely that each column is a C-codeword. Then set S to be the sum S₁+...+S_N. The matrix S can be computed, with each shareholder knowing only his respective row, by sharing the k-th row of each S_i with party k only, so each party sends and receives (N - 1) 1000000 private keys in total each way (say 3.2 GB of data for N = 100).

To achieve the latter, each key shareholder computes and publishes public keys P_i,1,...,P_i,1000000 corresponding to the respective private keys p_i,1,...,p_i,1000000 in his row of the matrix S. So the entire N * 1000000 matrix T = (P_ij) of public keys (curve points) is public information. Then we may pick a random linear constraint that all C-codewords satisfy (i.e. an element of C^⊥) and check that every column of T satisfies it. This will prove that, in fact, all such constraints are satisfied by both S and T and every column is a C-codeword as required. The entire computation requires N million base point multiplications and N million general point multiplications, so with a well optimised native secp256k1 library it should take a few hours at most, I think.

Marginal public and private keys

From each column of index j (from 1 to 1000000) of the matrices S and T, we derive a marginal private-public key pair (p_j, P_j) as follows: pick a linear functional f such that the span of f and C^⊥ is itself an MDS code (of one higher dimension than C^⊥). Then define p_j to be f(p_1j,...,p_Nj) and P_j to be f(P_1j,...,P_Nj), for the respective columns (p_1j,...,p_Nj) and (P_1j,...,P_Nj) of S and T. Thus we obtain a million public keys (P_j) which are known to everyone, with a million matching private keys (p_j) which are known to no one unless a quorum of key shareholders decide to reveal their sub-shares in the respective column of the matrix S.

This is equivalent to having an extra dummy key shareholder who never participates in the initial construction of S or the subsequent quorum forming. The extra row of dummy sub-shares added to S then forms the list of marginal private keys.

Using the key shares

We shall reserve the marginal public-private key pair (P₁, p₁) for all threshold signing of txs by the key shareholders. All the remaining marginal key pairs are use-once, with the private key p_j revealed to the buyer when he completes the forwarding payment to the third party (or parties). This will be the secret that unlocks the seller's lightning payment preimage.

Each seller maintains a small cache of column index reservations from the list 1 to 1000000, which he negotiates with a supermajority of key shareholders possibly well before the start of the trade. The key shareholders communicate with each other (say by syncing bitsets of used/reserved column indices) to help ensure that an index never gets assigned more than once. Some kind of DoS protection may be required to help prevent a malicious seller or key shareholder from spamming the synced bitset with reservations. There need be no further communication with the key shareholders unless a trade goes bad.

It is the responsibility of the seller to make sure his reserved public key P_j is never used in more than one trade. It is no loss to the buyer if a key pair (or equivalently a column index) is reused - it simply means there is a risk to the seller that the private key which forces through his payment could be discovered and used prematurely, allowing the buyer to steal money.

The on-chain forwarding payment

A Schnorr (or ECDSA) signature consists of a lifting R of a secret nonce k to a curve point, together with a scalar s formed out of a hash, the private key and the nonce k. Publishing the signature creates a pseudorandom affine dependency between the nonce and the private key, thus revealing one will reveal the other. We would like to arrange things so that the reserved private key p_j will be revealed by the shareholders publishing the s-component of the Schnorr signature for the final forwarding tx, but to prevent a race to double spend, it is critical that the signing key p₁ does not also get revealed. Therefore, we need a third secret scalar, which we shall take to be another marginal private key p_a from the million-key list, but this time assigned to the buyer from the key shareholders. (Since it is absolutely critical that p_a doesn't get reused, lest the signing key p₁ gets revealed, we could record the index choice a in the OP_RETURN data of the buyer's forwarding tx, so we're not just relying on the index bitsets shared between the key shareholders.)

Now publishing a carefully chosen affine dependency between the three private keys p₁, p_j and p_a will ensure that once the prepared (and buyer pre-signed) tx spending the locked up UTXO the buyer paid into has been published, the published signature will reveal p_j and unlock the seller's preimage.

Calculating the three-key affine dependency (without leaking the individual keys to corrupt shareholders) is easy for a quorum of shareholders, as is the calculation of s for the actual signing (which is just a two-key affine dependency). These are both just linear combinations of the three keys p₁, p_j and p_a, hence mapped by f from linear combination of the columns of the matrix S, and any such column combination can be determined by interpolating from corresponding linear combinations of their sub-shares p_ij (which, unlike the individual sub-shares, they may share with each other).

So the order of events when the buyer wishes to start arbitration is as follows:

1) Buyer publishes a forwarding tx paying to a lockup P2TR (pay-to-taproot) address. This may be spent either with both the buyer's signature (against his own key) and a quorum's signature against the public key P₁, or a CSV-timelocked tx with only the buyer's signature. An OP_RETURN output or something similar could be placed in the tx to attempt to reserve an index a as above, which may require messaging some key shareholders to check that it is free. 2) Buyer messages a quorum of key shareholders to prepare a tx spending from the lockup and compute the triple-key affine dependency mentioned above, which will reveal the private key p_j once it is signed by a quorum. Meanwhile, the buyer adds his signature. In the unlikely event that the index a the buyer attempted to reserve was used after all, extra blockchain publications will first be needed to reserve one that wasn't. 3) A quorum of shareholders signs and publishes the prepared tx, revealing p_j to the buyer, which he uses to unlock the seller's payment preimage. The lightning payment is then immediately finalised, before it has a chance to time out.

A much simpler on-chain forwarding approach

The above method makes the on-chain forwarding transactional, so that either both the buyer's and the seller's payments go through or neither do, regardless of any errant behaviour by the key shareholders. However, the buyer already has to trust the key shareholders to be responsive to avoid losing money, just as the seller has to trust the shareholders not to inappropriately leak keys to avoid losing money. So a much simpler way for the buyer to forward the payment would be to just send it directly to the Burning Men (or any other designated recipient(s)). Then, when a key shareholder sees that the tx has confirmed, he reveals his sub-share p_ij to the buyer. When the buyer has enough such sub-shares for i from 1 to N, he may recover p_j to unlock the seller's payment.

Since this does not require anything specific to the curve secp256k1, we may instead use a faster curve such as ed25519 throughout the protocol.

Off-chain payment forwarding

In order to save on mining fees, the buyer could alternatively forward the seller's payment to a dedicated single third party with another lightning payment. This would be a bonded role, and not very high trust since the bond is chosen to be high enough to cover any forwarded-on monies that the third party will be liable for at any given time. There could also be multiple such third parties for the buyer to choose between. However, it is crucial that the third party is accountable (in the sense defined in the five security properties listed in https://github.com/bisq-network/proposals/issues/373). This is in contrast to the key shareholders who, in this protocol, are collectively considered to be reliable and essentially beyond reproach, even though any one of them could be corrupt or flaky.

Because of the accountability and the fact that the third party could be corruptly in collusion with the seller, it is insufficient for the forwarding lightning payment to simply share the seller's payment hash (so that when it finalises the buyer learns the preimage and can finalise the seller's payment to him). Instead, the preimage can be any secret chosen by the third party, who then signs a message containing the corresponding SHA-256 payment hash. This message makes the third party liable for the forwarded money in the event that the buyer can produce the preimage of that hash.

Then the buyer makes a lightning payment to the third party (with a short timeout) which, as soon as it has been finalised, reveals the third party's preimage to the buyer. The preimage, together with the signed message, obliges the key shareholders to reveal p_j to the buyer (via their individual sub-shares), unlocking the seller's payment.

Preimage puzzles

The seller needs a way to assure the buyer that revealing the private key p_j will allow the buyer to recover the payment preimage. One way to achieve this would be to simply encrypt the preimage with the corresponding public key P_j using, say, ElGamal encryption, then share this with the buyer. But then the seller would have to furnish the buyer with a zero-knowledge proof that whatever the stated ciphertext decrypts to is, in fact, a preimage of the stated SHA-256 hash. Such a proof may be very big or difficult and computationally expensive to construct, since it requires encoding both the SHA-256 hashing circuit and the elliptic curve arithmetic inside the same proof object.

Instead, the seller can construct a special object which we shall call a preimage puzzle, and carry out an interactive zero knowledge proof with the buyer using garbled circuits (with the latter mentioned and used in https://github.com/bisq-network/proposals/issues/373). This interactive proof will show that the puzzle may be solved efficiently with knowledge of the private key p_j, and that solving it reveals the preimage. The puzzle may be partially corrupted, consisting of a large number of pieces (256), any of which may be invalid. Upon receipt of the puzzle, the buyer challenges the seller to unlock a sample subset of the pieces that the buyer chooses at random. The seller does so and carries out a zero-knowledge proof using a garbled circuit (supplied by the buyer) that the unlocked puzzle pieces are valid (specifically, that they decrypt to symbols in a 256-byte extended Reed-Solomon codeword which embeds the payment preimage along with some random padding for blinding).

The sampling shows that even though the puzzle may be partially corrupted, most pieces in it are valid and will decrypt successfully with the private key p_j, revealing a corrupted 256-byte extended Reed-Solomon codeword. The number of errors in the codeword will be small enough to successfully decode and recover the preimage, with very low failure probability (say 1 in 4 * 10¹⁶ for reasonable puzzle parameters).

The garbled circuit is used for validation only, instead of a full secure two-party computation, so it only needs to use half-AND gates for the embedded SHA-256 hashing boolean circuit. This makes it around 350 kB in size. The puzzle itself is fairly small - only around 8448 bytes. Not much more data than that in total will need to be exchanged between the two parties for the puzzle and interactive proof.

Note that such preimage puzzles, linking a private key to a payment preimage, could be used in other interesting protocols like (trustless) lightning-Monero submarine swaps, or indeed lightning swaps with any UTXO-based coin that supports non-malleable transactions but not necessarily scripting or timelocks.

(I have been writing a Java implementation of such preimage puzzles extending the earlier garbled circuit work, which is nearly in a working state - mostly just some oblivious transfers work and tidying up remains.)

Payment hashes and timeouts

The seller needs to make a pending lightning payment P_SB to the buyer (of his security deposit and trade amount) with the decided upon payment hash. OTOH, the buyer's pending lightning payment P_BS to the seller (of his security deposit) cannot use the same payment hash, since that would require that he goes second. But then either P_BS times out first, in which case an unresponsive (say future trading) buyer could avoid losing his security deposit, or it times out last, in which case the key shareholders would have to intervene to force through P_SB in case the seller fails to release (before it times out), without knowing for sure whether P_BS got successfully set up or not, with the buyer's word against the seller's.

Because of this, P_BS must in fact be a latched payment, as defined in https://github.com/bisq-network/proposals/issues/373, and therefore requires a secure two party computation between the buyer and seller to compute the payment hash, using a garbled circuit (say combined with the above garbled circuit to verify the seller's preimage puzzle). This will, unfortunately, add another 2/3 MB to the size, making the entire garbled circuit sent from the buyer to the seller roughly 1 MB in total.

After sending the preimage puzzle, carrying out the interactive ZKP and computing the payment hash of P_BS with a secure 2PC, the two traders may simultaneously set up the pending payments P_SB and P_BS. The payment preimage of the latter is some combination, say XOR or concatenation, of the seller's preimage and a secret (that is, the latch) of the buyer. Once the buyer gets a signed acknowledgement from the seller that P_BS was routed successfully, and he sees his own incoming payment P_SB, then he may release the latch by revealing his secret to the seller, to start the trade. So that the key shareholders are willing to later intervene to help force through P_SB, it needs to be undeniable that the latch was released, so this requires use of the broadcast-with-backup-notary mechanism described in https://github.com/bisq-network/proposals/issues/373.

At this point the seller may release and close the trade at any time (even, unfortunately, before the buyer has started his fiat or altcoin payment, though it is not clear to me why this would be a major security issue). By finalising P_BS, the seller's payment preimage is revealed to the buyer, allowing the buyer to finalise P_SB, closing the trade. Therefore, much like the current on-chain protocol in Bisq 1, the buyer does not need to be online for the seller to release and walk away with his security deposit, nor does the seller have to be online by the time the buyer is available again to claim his payout.

The seller's payment P_SB is set to time out first, after perhaps five days or so. Then, say a day or so later, P_BS times out. The buyer has until near the end of the time window of P_SB to start arbitration and confiscate that payment. At that point, the seller is expected to immediately finalise P_BS, claiming back the security deposit. (If the buyer is unresponsive, like in the case of future trades, and P_SB times out, then the seller has a small window of time left in which he can safely finalise P_BS to claim the security deposit and walk away with the full escrow amount.)

Now, unless the seller hands over his reclaimed security deposit from P_BS, once the buyer has started arbitration, then the buyer shall automatically win the case and be entitled to everything left, so the forwarded seller's payment will be automatically returned in full to the buyer. This incentivises the seller to hand over his security deposit to the third party (or parties), ensuring that the full escrow amount is handed over in the event of a genuine dispute between the two traders. Of course, it is possible that an unresponsive seller could force the buyer to start arbitration and then claim back his security deposit and walk away, not having lost anything but potentially costing the buyer mining fees for the forwarding payment (as well as causing inconvenience). However, there is really nothing even in the existing on-chain protocol to stop the seller from closing the trade and claiming back his security deposit just before arbitration is about to start, and well after mediation has started.

bisq-network / proposals