Date: Mon, 22 Apr 2019 00:07:20 +0000
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <pOqJuLTCi90Cz27QqCYHFBdkKBA0Hc0IY2zplQ0uFILWWqLULdspR6rA6Q_2oMC9yWKrB8p5VX7woQUYhNpV_cjDCcKCJajGsr3gNrcbYho=@protonmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: [bitcoin-dev] Payjoin2swap: Enabling Payjoin Without Merchant
	Purchases
Precedence: list

Introduction
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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 a=
re 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 transa=
ctions, which greatly increases the effort required for blockchain analysis=
.
In particular, it breaks the common-input heuristic (UTXOs that are spent t=
ogether 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 h=
acked or hostilely taken over, with the identifying information of the hodl=
er in the logs of the exchange.
The hodler would prefer to have those who have gotten this identifying info=
rmation 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 ano=
ther.
(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 bitc=
oins in a payjoin to buy bitcoins of similar value.

The same insight underlies the observation that, as long as LN-to-onchain s=
wap services exist, it is possible to gain incoming capacity on Lightning c=
hannels immediately if one has bitcoins already.
One can observe that one gains capacity to receive on Lightning if one spen=
ds on Lightning: the technique, then, is to spend BTC on Lightning to buy B=
TC 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 adva=
ntage that we can build software that interacts solely with the Bitcoin blo=
ckchain.
This simplifies the deployment of payjoin for bitcoin-to-bitcoin swaps, as =
payjoin for merchant deployment requires interaction of the Bitcoin blockch=
ain, and the infrastructure of the merchant.
As most merchants are more interested in their product rather than in Bitco=
in technology, we can expect that deployment of payjoin will be slower comp=
ared 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 propose=
s 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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D

In a payjoin2swap, what is visible on the blockchain is two transactions th=
at 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 ge=
t 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 addre=
sses) 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 th=
e two participants in a payjoin2swap.

These two transactions all pay out to P2WPKH addresses, and (if the payjoin=
2swap 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 [2=
p-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 pro=
tocol runs to completion.
The transactions have an `nLockTime` near the time they are confirmed oncha=
in, looking like Bitcoin Core behavior.

Participants in a payjoin2swap need to own two UTXOs onchain; the values ne=
ed 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 pai=
d 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 c=
oins, except as part of a mix operation.

Suppose Alice has a 90mBTC UTXO and a 80mBTC UTXO that are both post-mix co=
ins.
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 1=
20mBTC from the mix before paying.
This can be problematic if the only available mix is an equal-value coinjoi=
n where the equal value is less than 120mBTC.

With payjoin2swap, Alice simply needs to find a Bob who has at two UTXOs th=
at 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 toge=
ther, 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 c=
hannels 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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D

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 hi=
gher 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 =3D 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 vari=
ous 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 =3D bG), we can use s=
omething like B + h(B | "$name") as the basepoint-derived public key (priva=
te 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 de=
rived from the same base point as other keys since the last step of this pr=
otocol 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 A=
lice non-basepoint private key with Bob "federation" basepoint-derived publ=
ic 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 ke=
y, 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 pa=
ys 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 t=
o the "Bob-to-Alice federation public key" the agreed swap amount, and extr=
a value into a Bob-only change output.

5.  Generate and sign the "pre-swap backout transactions", then exchange si=
gnatures.
    This spends the swap output of the "pre-swap transactions" and return i=
t to the original payer.
    Both Alice and Bob can generate these themselves with information alrea=
dy 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" basep=
oint-derived public key.
        Its `nLockTime` is L1.
    b.  The "Bob pre-swap backout transaction" spends the "Bob pre-swap tra=
nsaction" output and pays the entire value to the Bob "backout" basepoint-d=
erived public key.
        Its `nLockTime` is L0.

6.  Validate the signatures for "pre-swap backout transaction" of the count=
erparty.

7.  Sign the "pre-swap transactions" and exchange the actual transactions w=
ith 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 corr=
ect federation public key.
        e.g. Bob validates that the Alice pre-swap transaction pays the agr=
eed 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 transacti=
on is confirmed, wait for L2 and use the pre-swap backout transaction.

10.  Check if the pre-swap transaction from your counterparty spends a UTXO=
s 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 b=
lacklist.

12.  Create the "payjoined swap transaction" for your counterparty and exch=
ange 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 UT=
XO, minus the feerate times the size of the additional input (including any=
 witness needed).

13.  Generate and sign the "payjoined swap backout transactions" and exchan=
ge signatures, and whether the added output was before or after the existin=
g output.
     Start with the counterparty pre-swap backout transaction.
     Change the input to spend the payjoined swap transaction swap output i=
nstead.
     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, an=
d that the additional payjoin UTXO from the counterparty is an unspent SegW=
it output.

16.  Broadcast both payjoined swap transactions and wait for them to be con=
firmed to height D.
     If L0 is too near and both of the payjoined swap transactions are stil=
l 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 un=
confirmed attempt to respend all UTXOs, or if not, just wait for L2 and bro=
adcast the corresponding payjoined swap backout transaction.

17.  Generate the "HTLC offer transactions".
     Each can generate these transactions without communicating with the ot=
her.
     The `nLockTime` is the block height at which the payjoined swap transa=
ctions 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-derive=
d key.
             Pay to `OP_IF OP_HASH160 <h(x)> OP_EQUALVERIFY <Bob "alice-htl=
c-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-ht=
lc-fail" basepoint-derived key (2) Bob "bob-htlc-fail" basepoint-derived ke=
y.
             Pay to `OP_IF OP_HASH160 <h(x)> OP_EQUALVERIFY <Alice "bob-htl=
c-claim" basepoint-derived key> OP_ELSE L0 OP_CHECKLOCKTIMEVERIFY <N> OP_EN=
DIF 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 pu=
blic key, and the remaining value to Bob "payjoined backout" basepoint-deri=
ved 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 confi=
rmed, Alice must wait for L1 and broadcast the Alice HTLC offer failure tra=
nsaction.

20.  Bob generates the "Bob HTLC offer failure transaction".
     This spends the Bob HTLC offer via the timelock path, with an `nLockTi=
me` equal to L0.
     It gives the agreed swap value to Bob "backout" basepoint-derived publ=
ic key, and the remaining value to Alice "payjoined backout" basepoint-deri=
ved 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 confirm=
ed, Bob must wait for L1 and broadcast the Bob HTLC offer failure tranascti=
on, or for Alice to claim it by revealing x (and Bob must then broadcast an=
d 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 m=
ight need to give, or find another partner to swap with and make sure to co=
mplete 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 "f=
ederation" basepoint-derived key.
        Since Bob has given the Bob non-basepoint key and Alice knows the p=
rivate 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 complet=
ely know the private key wihtout authorization from Alice.

Creating Plausible Transactions
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D

For simplicity, let us consider the case where Alice and Bob each own two U=
TXOs 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 715m=
BTC, 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 th=
e sum of all inputs except the smallest input.
Otherwise, a fee-reducing coin selection algorithm would have eliminated th=
e 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 the=
y have.
    This implies that the swap amount must be less than or equal to the sma=
llest UTXO.
2.  Alice and Bob check if their other coin (the one they will propose of p=
ayjoining) plus the swap amount is greater than the UTXO consumed in the pr=
e-swap transaction from the other side.
    i.e. Alice checks the Bob pre-swap input is smaller than the Alice larg=
er UTXO plus the swap amount.
    If thise fails, they may propose to the counterparty to split their sma=
ller UTXO.

Thus, in the above, Alice and Bob should have started their pre-swap transa=
ctions 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 usua=
lly 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: fir=
st 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-ou=
tput 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' b=
ecomes potentially linked to this transaction, even though it is completely=
 unrelated.

Further, while the swap output is identifiable as V + S', it is not possibl=
e 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 o=
ne side (provided V >=3D S) until the V - S + S' is achievable by the other=
 side.