[bitcoin-dev] Payjoin2swap: Enabling Payjoin Without Merchant Purchases

[ZmnSCPxj <ZmnSCPxj@protonmail.com>]

Introduction
============

Payjoin vs. Existing Equal-Valued CoinJoins
-------------------------------------------

Any non-equal-value coinjoin is easily solvable via [value sudoku](https://www.coinjoinsudoku.com/advisory/).
Thus, common deployments of coinjoin use equal-value coinjoins.

Equal-valued coinjoins are very obvious onchain: it has many outputs that are of equal value, or have multiples of some base value.
Although it is in practice difficult to correlate the inputs to outputs, it is still an open indication to blockchain analysis that a break occurs in their analysis.
However, equal-valued coinjoins are needed to break value sudoku.

The exception to value sudoku for non-equal value coinjoins is if value is transferred between participants in the coinjoin, i.e. the Payjoin proposal.

Payjoin transactions are difficult to differentiate from non-payjoin transactions, which greatly increases the effort required for blockchain analysis.
In particular, it breaks the common-input heuristic (UTXOs that are spent together stay together).
They may cause blockchain analysis to go astray without blockchain analysis being able to pinpoint which transaction broke the analysis.

Payjoin For Hodlers?
--------------------

As payjoin transfers Bitcoin value, it is planned to be used for payments (i.e. spending) rather than hodling.
The issue is that it appears that payjoin cannot be used by hodlers, since hodlers are not interested in paying, but in saving.

Yet hodlers want to retain their privacy also.
They do not want their exchange snooping on them and finding out that they have not moved their coins from cold storage.
For long enough timeframes, a KYC-demanding exchange might eventually get hacked or hostilely taken over, with the identifying information of the hodler in the logs of the exchange.
The hodler would prefer to have those who have gotten this identifying information to believe that the value has been spent elsewhere, rather than in UTXOs that have not been moved.

At the same time, they are not interested in purchasing items and therefore cannot utilize payjoin as-is.
After all, payjoin requires a transfer of value from one participant to another.
(they can continue to utilize existing equal-value coinjoins, if those are acceptable to the hodler)

The key insight here is that hodlers "buy Bitcoin".
Thus there is still the possibility of hodlers using payjoin, by using bitcoins in a payjoin to buy bitcoins of similar value.

The same insight underlies the observation that, as long as LN-to-onchain swap services exist, it is possible to gain incoming capacity on Lightning channels immediately if one has bitcoins already.
One can observe that one gains capacity to receive on Lightning if one spends on Lightning: the technique, then, is to spend BTC on Lightning to buy BTC off Lightning (i.e. onchain).
We shall see later that Lightning has some parallels to payjoin2swap.

Using payjoin for purchases of bitcoins using bitcoins has the massive advantage that we can build software that interacts solely with the Bitcoin blockchain.
This simplifies the deployment of payjoin for bitcoin-to-bitcoin swaps, as payjoin for merchant deployment requires interaction of the Bitcoin blockchain, and the infrastructure of the merchant.
As most merchants are more interested in their product rather than in Bitcoin technology, we can expect that deployment of payjoin will be slower compared to a payjoin2swap deployment made by Bitcoin tech weenies.

References
----------

* This idea is not original to me: a [feature request on AdamISZ/CoinSwapCS](https://github.com/AdamISZ/CoinSwapCS/issues/52) by Chris Belcher proposes P2EP for CoinSwapCS.
  However, I have not found any follow up on this idea and the fleshed-out protocol and thoughts below are my own.

Payjoin2swap On the Blockchain
==============================

In a payjoin2swap, what is visible on the blockchain is two transactions that occur at about the same time.
They appear to pay two different addresses, and each has a change output.
The payment addresses are then spent almost immediately, as a self-to-self transfer (one input, one output), while the change output may or may not get spent any time soon.
If the wallet used follows [ZeroLink](https://github.com/nopara73/ZeroLink) strictly, then the four addresses (two payment addresses, two change addresses) do not seem to be related, and there would be no reason to think that the two transactions are related.

In reality, one payout and one change address each are actually owned by the two participants in a payjoin2swap.

These two transactions all pay out to P2WPKH addresses, and (if the payjoin2swap protocol is followed correctly) we do not see anything special: no 2-of-2, no HTLCs, nothing.
This is possible even without Schnorr-based signature schemes, by use of [2p-ECDSA](https://eprint.iacr.org/2017/552.pdf) to create a 2-of-2 multisig in ECDSA among the participants that operates the protocol.
Any special contracts are hosted inside a temporary offchain cryptocurrency system (slightly like a Lightning channel), and are not exposed if the protocol runs to completion.
The transactions have an `nLockTime` near the time they are confirmed onchain, looking like Bitcoin Core behavior.

Participants in a payjoin2swap need to own two UTXOs onchain; the values need not be equal.

Example 1
---------

Suppose Alice owns a 900 mBTC and a 10 mBTC UTXO.
And suppose Bob owns a 15 mBTC and 4 mBTC UTXO.
Both of the above users would have difficulty with current Wasabi coinjoins which use equal values of around 100mBTC: Alice would have to run several rounds, while Bob cannot participate at all.

What would be seen onchain would be:

1.  Alice 900mBTC, Bob 4mBTC -> Alice&Bob 903mBTC, Bob 1mBTC
2.  Alice 10mBTC, Bob 15mBTC -> Alice 7mBTC, Alice&Bob 18mBTC

Followed quickly by:

1.  Alice&Bob 903mBTC -> Alice 903mBTC
2.  Alice&Bob 10mBTC -> Bob 10mBTC

By use of 2p-ECDSA, the Alice&Bob addresses are P2WPKH addresses and do not reveal that they are actually 2-of-2 multisig.
Obviously, all the public keys would be different.

The above would lead blockchain analysts to believe that Alice is being paid 903mBTC from some confusing combination of Alice and Bob, and that Bob is being paid 10mBTC from some confusing combination of Alice and Bob.

Example 2
---------

Under ZeroLink, post-mix coins cannot be joined, even with other post-mix coins, except as part of a mix operation.

Suppose Alice has a 90mBTC UTXO and a 80mBTC UTXO that are both post-mix coins.
Now suppose Alice needs to pay Carol 120 mBTC.
Alice cannot simply join the post-mix coins and pay 120mBTC and get 50mBTC change, as it can reduce the privacy of the mix participants.
Under ZeroLink, Alice needs to re-mix the post-mix coins and get at least 120mBTC from the mix before paying.
This can be problematic if the only available mix is an equal-value coinjoin where the equal value is less than 120mBTC.

With payjoin2swap, Alice simply needs to find a Bob who has at two UTXOs that are at least 30mBTC each.

Suppose Alice finds a Bob with 37mBTC UTXO and 66mBTC UTXO.

They make:

1.  Alice 90mBTC, Bob 37mBTC -> Alice&Bob 120mBTC, Bob 7mBTC
2.  Alice 80mBTC, Bob 66mBTC -> Alice 50mBTC, Alice&Bob 96mBTC

Then:

1.  Alice&Bob 120mBTC -> Carol 120mBTC
2.  Alice&Bob 96mBTC -> Bob 96mBTC


There is no transaction directly tying the two post-mix UTXOs of Alice together, but we have effectively "consolidated" the inputs of Alice.

This is in fact quite similar to "rebalancing" channels on Lightning.
Post-mix UTXOs under ZeroLink and with payjoin2swap function similarly to channels on Lightning: you can transfer from one UTXO to another in order to make a large payment, just as you might transfer funds from one channel to another in order to make or forward a large payment on Lightning.

Payjoin2swap Swap Protocol
==========================

1.  Alice and Bob agree on various details.
    a.  Who Alice and Bob is.
        Alice is the one who knows the secret x and pays to an HTLC with higher time L1.
        Alice gives h(x) to Bob.
    b.  The start time (a blockheight) of the protocol, Ls.
    c.  An amount to swap.
        This should be smaller than the smallest UTXO that will be involved in the swap.
    d.  A "safe" confirmation depth for anchoring, D.
        This could be D = 6 as per the Bitcoin whitepaper.
    e.  Twp future blockheights, L0 and L1, such that Ls + D < L0 < L1.
    f.  Various public keys whose private keys are known by Alice, and various public keys whose private keys are known by Bob.
        This can be done by using a "base point" and deriving the keys from tweaking this base point.
        Let us call this the (Alice|Bob) "$name" basepoint-derived (public|private) key.
        Give a basepoint B (private key b such that B = bG), we can use something like B + h(B | "$name") as the basepoint-derived public key (private key is left as a trivial exercise to the reader).
    g.  A public key whose private key is known by Alice, and a public key whose private key is known by Bob.
        If we use the "base point" technique above, these keys cannot be derived from the same base point as other keys since the last step of this protocol involves sharing this private key to the other participant.
        Let us call this the (Alice|Bob) non-basepoint (public|private) key.
    h.  The feerate.

2.  Alice and Bob generate two 2p-ECDSA federation public keys.
    a.  The "Alice-to-Bob federation key" involves the Alice non-basepoint key, and the Bob "federation" basepoint-derived key.
        As per 2p-ECDSA, Alice can compute this public key by multiplying Alice non-basepoint private key with Bob "federation" basepoint-derived public key.
        Bob can compute this public key by multiplying his private key with the Alice public key.
    b.  The "Bob-to-Alice federation key" involves the Bob non-basepoint key, and the Alice "federation" basepoint-derived key.
        Similar to above as per 2p-ECDSA.

3.  Alice and Bob select from their UTXOs:
    a.  A set of UTXOs whose sum is greater than the swap value.
        Call these the "swap UTXOs", i.e. Alice swap UTXOs, Bob swap UTXOs.
    b.  A UTXO to use for a payjoin receive.
        Call this the "payjoin UTXO", i.e. Alice payjoin UTXO, Bob payjoin UTXO.

4.  Generate (but not sign) the "pre-swap transactions".
    Alice and Bob exchange the txids of these transactions and which output is the swap output.
    Their `nLockTime` is Ls.
    a.  The "Alice pre-swap transaction" spends the Alice swap UTXOs and pays to the "Alice-to-Bob federation public key" the agreed swap amount (the swap output).
        Any extra value is put into a change output that Alice controls.
    b.  The "Bob pre-swap transaction" spends the Bob swap UTXOs and pays to the "Bob-to-Alice federation public key" the agreed swap amount, and extra value into a Bob-only change output.

5.  Generate and sign the "pre-swap backout transactions", then exchange signatures.
    This spends the swap output of the "pre-swap transactions" and return it to the original payer.
    Both Alice and Bob can generate these themselves with information already exchanged before.
    a.  The "Alice pre-swap backout transaction" spends the "Alice pre-swap transaction" output and pays the entire value to the Alice "backout" basepoint-derived public key.
        Its `nLockTime` is L1.
    b.  The "Bob pre-swap backout transaction" spends the "Bob pre-swap transaction" output and pays the entire value to the Bob "backout" basepoint-derived public key.
        Its `nLockTime` is L0.

6.  Validate the signatures for "pre-swap backout transaction" of the counterparty.

7.  Sign the "pre-swap transactions" and exchange the actual transactions with witness.

8.  Validate the pre-swap transaction from the counterparty:
    a.  All inputs are signed correctly and are SegWit.
        All inputs are unspent.
    b.  The indicated "swap" output does pay the correct amount to the correct federation public key.
        e.g. Bob validates that the Alice pre-swap transaction pays the agreed swap amount to the Alice-to-Bob federation key.

9.  From this point onward, if either of the pre-swap transactions appears in the mempool or confirmed, abort.
    Attempt to spend all your own swap UTXOs, and if the pre-swap transaction is confirmed, wait for L2 and use the pre-swap backout transaction.

10.  Check if the pre-swap transaction from your counterparty spends a UTXOs in your blacklist.
     If there are, attempt to spend all your own swap UTXOs and abort.

11.  Add the UTXOs spent by the counterparty pre-swap transaction to your blacklist.

12.  Create the "payjoined swap transaction" for your counterparty and exchange their txids and the value of the swap outputs.
     i.e. Bob creates the Alice payjoined swap transaction and vice versa.
     Start with the counterparty pre-swap transaction.
     Insert your own payjoin UTXO at a random index of the inputs.
     Then increase the swap output according to the value of the payjoin UTXO, minus the feerate times the size of the additional input (including any witness needed).

13.  Generate and sign the "payjoined swap backout transactions" and exchange signatures, and whether the added output was before or after the existing output.
     Start with the counterparty pre-swap backout transaction.
     Change the input to spend the payjoined swap transaction swap output instead.
     Then add a new output that pays to the counterparty "payjoined backout" basepoint-derived public key, the difference of the input minus the other output, minus the feerate times the size of the additional output.

14.  Exchange the payjoined swap transactions and sign them completely.

15.  Validate that the payjoined swap transactions are signed correctly, and that the additional payjoin UTXO from the counterparty is an unspent SegWit output.

16.  Broadcast both payjoined swap transactions and wait for them to be confirmed to height D.
     If L0 is too near and both of the payjoined swap transactions are still unconfirmed, abort and attempt to respend all UTXOs you control that are involved.
     If L0 is too near and one of the payjoined swap transactions is still unconfirmed, abort, and if it is your payjoined swap transaction that is unconfirmed attempt to respend all UTXOs, or if not, just wait for L2 and broadcast the corresponding payjoined swap backout transaction.

17.  Generate the "HTLC offer transactions".
     Each can generate these transactions without communicating with the other.
     The `nLockTime` is the block height at which the payjoined swap transactions were confirmed at depth D.
     a.  The Alice HTLC offer:
         i. Spend the Alice payjoined swap transaction output.
         ii. Compute backout address N as the 2p-ECDSA of (1) Alice "alice-htlc-fail" basepoint-derived key (2) Bob "alice-htlc-fail" basepoint-derived key.
             Pay to `OP_IF OP_HASH160 <h(x)> OP_EQUALVERIFY <Bob "alice-htlc-claim" basepoint-derived key> OP_ELSE L1 OP_CHECKLOCKTIMEVERIFY OP_DROP <N> OP_ENDIF OP_CHECKSIG`
     b.  The Bob HTLC offer:
         i. Spend the Bob payjoined swap transaction output.
         ii. Compute backout address O as the 2p-ECDSA of (1) Alice "bob-htlc-fail" basepoint-derived key (2) Bob "bob-htlc-fail" basepoint-derived key.
             Pay to `OP_IF OP_HASH160 <h(x)> OP_EQUALVERIFY <Alice "bob-htlc-claim" basepoint-derived key> OP_ELSE L0 OP_CHECKLOCKTIMEVERIFY <N> OP_ENDIF OP_CHECKSIG`

18.  Alice generates the "Alice HTLC offer failure transaction".
     This spends the Alice HTLC offer via the timelock path.
     It thus has an `nLockTime` equal to L1.
     It gives the agreed swap value to Alice "backout" basepoint-derived public key, and the remaining value to Bob "payjoined backout" basepoint-derived public key.
     Alice and Bob generate a signature for this via 2p-ECDSA.
     Then they generate a signature for the Alice HTLC offer.

19.  From this point if the Alice HTLC offer appears on mempool or is confirmed, Alice must wait for L1 and broadcast the Alice HTLC offer failure transaction.

20.  Bob generates the "Bob HTLC offer failure transaction".
     This spends the Bob HTLC offer via the timelock path, with an `nLockTime` equal to L0.
     It gives the agreed swap value to Bob "backout" basepoint-derived public key, and the remaining value to Alice "payjoined backout" basepoint-derived public key.
     Alice and Bob generate a signature for this.
     Then they generate a signature for the Bob HTLC offer.

21.  From this point if the Bob HTLC offer appears on mempool or is confirmed, Bob must wait for L1 and broadcast the Bob HTLC offer failure tranasction, or for Alice to claim it by revealing x (and Bob must then broadcast and claim the Alice HTLC offer).

22.  Alice gives Bob x.

23.  Bob gives the Bob non-basepoint private key.

24.  Alice gives the Alice non-basepoint private key.

25.  Alice must now spend the Bob payjoined swap transaction swap output on or before L0.
     Bob must now spend the Alice payjoined swap transaction swap output on or before L1.
     They can send it to themselves, send it to any pending payments they might need to give, or find another partner to swap with and make sure to complete up to step 16 in the new cycle before their respective timeouts.
     a. Alice must spend from the Bob-to-Alice federation pubkey address.
        This is a combination of the Bob non-basepoint key and the Alice "federation" basepoint-derived key.
        Since Bob has given the Bob non-basepoint key and Alice knows the private keys in all the Alice basepoint-derived keys, Alice can now spend it without Bob authorization.
     b. Bob must spend from the Alice-to-Bob federation puobkey address.
        Again, Alice has given enough information to Bob for Bob to completely know the private key wihtout authorization from Alice.

Creating Plausible Transactions
===============================

For simplicity, let us consider the case where Alice and Bob each own two UTXOs each.
This means that the payjoined transactions have two inputs, and are likely to have two outputs.
Fortunately, a good number of transactions onchain are two-input two-output affairs.
However, we should attempt to build plausible transactions.

For example, suppose we have:

* Alice has 70mBTC and 800mBTC UTXOs.
* Bob has 100mBTC and 7 mBTC UTXOs.

They could propose to swap 85mBTC.
Then Alice would give the Alice pre-swap transaction as:

* Alice 800mBTC -> Alice 715mBTC, Alice&Bob 85mBTC

And Bob would make the Bob pre-swap transaction:

* Bob 100mBTC -> Alice&Bob 85mBTC, Bob 15mBTC

After payjoining:

* Alice 800mBTC, Bob 7mBTC -> Alice 715mBTC, Alice&Bob 92mBTC
* Alice 70mBTC, Bob 100mBTC -> Ailce&Bob 155mBTC, Bob 15mBTC

The first transaction above is implausible: if the payment amount were 715mBTC, then a fee-reducing coin selector would have just chosen the 800mBTC.
Thus, we should ensure that there exists one output which is larger than the sum of all inputs except the smallest input.
Otherwise, a fee-reducing coin selection algorithm would have eliminated the smaller coins from the transaction.

For the case where both Alice and Bob each have two inputs to mix, we could impose the below rules:

1.  Alice and Bob generate pre-swap transactions using the smaller UTXO they have.
    This implies that the swap amount must be less than or equal to the smallest UTXO.
2.  Alice and Bob check if their other coin (the one they will propose of payjoining) plus the swap amount is greater than the UTXO consumed in the pre-swap transaction from the other side.
    i.e. Alice checks the Bob pre-swap input is smaller than the Alice larger UTXO plus the swap amount.
    If thise fails, they may propose to the counterparty to split their smaller UTXO.

Thus, in the above, Alice and Bob should have started their pre-swap transactions as:

* Alice 70mBTC -> Alice 64mBTC, Alie&Bob 6mBTC
* Bob 7mBTC -> Alice&Bob 6mBTC, Bob 1mBTC

Then the payjoined versions would be:

* Alice 70mBTC, Bob 100mBTC -> Alice 64mBTC, Alice&Bob 106mBTC
* Alice 800mBTC, Bob 7mBTC -> Alice&Bob 806mBTC, Bob 1mBTC

Linking (and Overlinking) Payjoin2swap
--------------------------------------

Using the heuristic above leads to the strong tendency that the difference of an input to the smaller output will be the swap value.
(or if the transaction is 1 output, then one of the inputs will be exactly the swap value)
Also, the main transactions will usually be in the same block and will usually be 2-input transactions.
There are fewer possibilities, thus it is a possible avenue for blockchain analysis to attempt linking.

It is useful to remember that generating this transaction is two steps: first create the pre-swap transaction with the UTXO of one side, before adding a new UTXO for the other side.

Suppose our agreed swap value is S.
Then one side creates a pre-swap transaction from a UTXO V:

* V -> V - S, S

The other side can then monitor the mempool for two-input two-output/one-output transactions and compute an "apparent swap value" from the difference of an input and the lower input (or 0 if one-output).
Suppose it finds S'.
Then the other side can simply synthesize a UTXO of value V - S + S'.
The other side can do this by spending a larger UTXO and splitting out that value.
This leads to a swap transaction of:

* V, V - S + S' -> V - S, V + S'

The above still leads to plausible transaction as defined above; the V + S' output will always be larger than the inputs, thus having to combine both inputs is plausible.
In doing so, the existing mempool transaction with apparent swap value S' becomes potentially linked to this transaction, even though it is completely unrelated.

Further, while the swap output is identifiable as V + S', it is not possible to be sure whether S or S' is the swap value.
The difference between V + S' and V is S', while the difference between V + S' and V - S + S' is S, so either could be the swap value.

This operation to mislead blockchain analysis can be called "overlinking", as it can lead blockchain analysis to believe that an unrelated transaction is linked to one of the swap transactions.
Participants should refuse to swap unlesss they can overlink at least one (and preferably both) of the payjoined swap transactions.
If the swap is not possible, both sides can agree to lower the V value of one side (provided V >= S) until the V - S + S' is achievable by the other side.