Snooping attacks on joinmarket - mitigation ideas

With the ongoing attack on Joinmarket privacy, the developers are discussing responses and will code and test once there is some agreement. These ideas are from https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8

Basic background:

See sequence of messages in canonical joinmarket in

https://github.com/JoinMarket-Org/JoinMarket-Docs/blob/master/encryption_protocol.txt

Attack description:

See https://github.com/chris-belcher/joinmarket/issues/156.

Requirements of a solution:

1. some cost imposed on gaining access to maker's utxos.
2. Allow joinmarket to remain usable without a lot of initial setup for the taker.
3. Allow it to be feasible to integrate at least taker (and ideally maker) functionality
   into an existing Bitcoin wallet software.

Background on the current status:

Maker's utxos are passed in the !ioauth message
(under E2E encryption with the taker), after the taker has sent one utxo pubkey, and a signature of his
encryption pubkey with that btc pubkey (but note currently: the utxo is not sent at this step, so the
utxo's status is not queried by the maker at this step).

The current design is an attempt to prevent trivial MITM attacks -
since the maker will not sign transactions not using a utxo which corresponds to the btc pubkey used for signing,
it will not be possible for a MITM to receive btc signatures from a taker for the transaction.
But the current design does not prevent using a fictitious btc pubkey, with no attempt to to receive signatures,
but only with the goal of receiving knowledge of the maker's current utxos.

Defence #1 : Require taker to send the actual utxo to the maker, and prevent (too many) repeats.

This allows the maker to check that the taker utxo is real before sending any information (his own utxos) to the taker
(technically this is already possible, but computationally impractical).

Further, the maker can keep a local database of already-used utxos and prevent re-use after a certain number
of retries. Even further, additional limits can be placed on the utxo (the most obvious being the coin age).
A simple implementation (briefly tested but still needs some work) can be found in this PR.

Defence #2: Committing to a utxo in public/plaintext at the start of the handshake.

An idea due to gmaxwell on how to do this: use ``proof of discrete log equivalence''. In brief:
starting from an owned utxo U with keypair (pub=P, priv=x), using another basepoint on the curve J (as opposed
to secp256k1's G), construct: P2 = x*J, and publish H(P2) (H=sha256, say).

Thus !fill becomes

!fill <oid> <amount> <H(P2)>

Once encryption is established, in !auth, append a zero knowledge proof that P2->J and P->G have
the same discrete log (i.e. same secret key x).

1. Taker chooses a nonce value k
2. Taker computes K_G = k*G, K_J = k*J
3. Taker computes hash e= H(K_G || K_J || P || P2)
4. Taker computes signature s = k + x*e

Taker then sends:

!auth <P> <txid:N> <btc sig of encryption pubkey using P> <P2> <s> <e>

Maker verifies in these steps, before revealing his own utxos:

1. Verify H(P2) = value previously committed in !fill.
2. Check that H(P2) is not repeated (too often).
3. As in Defence #1, verify that utxo txid:N is real, and check that P matches it.
4. Compute K_G = s*G - e*P
5. Compute K_J = s*J - e*P2
6. Finally, verify that H(K_G || K_J || P || P2) = e.

At this point, the maker has verified that the previously committed to utxo in the !fill (with commitment H(P2))
is the same as the one received in the auth, and that it is real, and that its private key is owned by the taker.

(Notes: J will be have to be a NUMS, see Confidential Transactions for an example (can be reused here presumably).
Also, note the brief description of this idea here.

This more complex procedure in Defence #2 compared with Defence #1 allows additional flexibility: if
the commitment values H(P2) are publicised (they are in any case in the clear in this proposal, but not broadcast
by default), then attempts to re-use utxos across makers may be blocked, but without sacrificing privacy for takers
(since there is no way to derive H(P2) from P for those who don't know x - this would be the weakness if one just
used H( P) instead).

Defence #3 Pay-to-contract (hash).

In this proposal, the taker is required to create a utxo specifically for the purpose of doing a transaction.
The utxo is created in such a way that he can prove ownership, and can prove that it was created specifically
in connection with a certain 'message' (wich could be the hash of a contract), and can still spend this output
after it has been used for proof purposes. See some discussion here.

In the simplest iteration we would
have this message be simply the amount of the proposed coinjoin.

Taker follows these steps:

1. Generates a new privkey=x, whose pubkey is P = x*G

2. Constructs a derived spending key = x+H(P||m), and thus a derived spending pubkey Q = P + H(P||m)*G (m is the coinjoin amount)

3. Constructs the bitcoin address of Q and spends amount A to Q, with utxo reference txid:N

4. Sends new !auth message as follows:

   !auth <input utxo> <btc sig of encryption pubkey> <P> <txid:N>
   

Maker performs these checks, before revealing his own utxos:

1. Check that input utxo is real and check btc signature (as usual)
   (these parts are not part of Defence #3 but discussed at the start of this doc)
2. Construct Q = P + H(P||m)*G, and corresponding address.
3. Check that txid:N is real (utxo on the network), corresponds to Q and (optionally)
   check that A is an acceptable amount, (optionally) check that this transaction has confirmations.
4. Check Q against a list to disallow too many repeats.

Final comments.

The first element is outside any of the 3 proposals, which is just ensuring
that the taker's initial utxo proposal is real by querying the blockchain.
This seems clearly necessary and should have been done already. Defence #1 is just
an addition / completion of that; checking repeats, and I believe should be done.

W.r.t. Defence #2 and #3, I feel that #3 affects the workflow of the taker too much
(see the comments at the start of the doc). #2 isn't hugely different from #1, but
can require takers to commit early to utxos, and in public (while keeping privacy).
I'm also interested to think about whether the mechanism in #2 can be applied to
makers too (can they commit to utxos in public like this also?).