Taker algorithm adjustment to dissuade duplicate bots

Taker-sophistication.md

This idea is due to @Adlai

This is a rough overview of the idea; there may well be refinements in practice.

Consider the following issue: a Maker is incented to find a way to get chosen more frequently in joins. He can try these approaches:

1. Publish more offers from his single bot, which cover the same btc amount range
2. Create multiple bots which make duplicated offers from the same wallet/utxo set.

Note that there is no "3. create multiple bots referring to different utxo sets"; there is nothing wrong with doing that.

Point 1 is already addressed since the early days; we simply don't consider more than one offer from one bot, so no statistical advantage is gained by doing it (albeit this creates friction in an important corner case: see 356.

This proposal aims to make 2 less desirable, although assessing how much less desirable is an open question (for me at least!).

###Proposed alteration to Taker algo

• Suppose Taker desires a join with N counterparties, where N << T = total number of Maker bots in the pit. After receiving the public orderbook, he sends !fill to k*N Makers instead of the current N; for concreteness we'll assume here k=2 and N=5, so he will send 10 !fills.

• Taker continues the protocol in parallel with these 10, up to the point of receiving !ioauth, and thus utxos, from all 10.

• Taker chooses 5 of the 10, with additional check: for any utxo that is seen to be in more than one received list, he bans (adds to ignored_makers) both of those Makers. Note that this is a disincentive to publish multiple orders, but would not totally prevent such a Maker from publishing more than one offer on the same utxo set; he would need to do some fairly sophisticated coding though, to create the right kind of non-determinism in his selection. In the limit, if he codes it to completely partition the utxo set between different offers, then this is back to an honest protocol execution anyway.

• For concreteness, suppose at this stage the Taker found 2 such bots (i.e. 2 bots offering at least one utxo in common). He will remove both of these from his list of viable counterparties, and continue with the remaining 8. He will pick 5 based on his criteria. This extra filtering step is potentially very useful: as well as the initial cut based on choosing makers that fit criteria based on amount and fee, read in the plaintext offers, the Taker can now, with this subset of 8, apply more sophisticated selection criteria based on the age and size of the Makers' utxos. This can provide extra anti-Sybil resistance (e.g. only allowing utxos of a certain age, or a more general "priority" style formula).

• He sends !tx to the 5, expecting !sig in return as normal. If 1 of 5 are non-responsive, then the recovery code, after a timeout, can recognize the incompleteness (as the code currently does), recreate the transaction template, and complete/repeat the !tx - !sig interaction for 1,2,3,4 and the new choice 6, and then broadcast. Since there is no timeout on the Maker side (incomplete tx proposals are just held in memory and only overwritten if a new proposal from the same Taker occurs), this should be workable although it requires some more code - also, from a brief look it appears that receiving a new !tx message on Maker side doesn't break anything, but this needs careful review. It looks like this part of the suggestion is unworkable since Maker.active_orders[nick] is set to None at the end of recv_tx(). Leaving it here for now in case it can be patched up.

###Ideas about more complete prevention of duplication

This section is sadly rather empty. While Makers could post some properly hiding commitment of the utxos they own, e.g. a Merkle tree, and open to it, this kind of proof is only of set membership; but to ensure non-duplication of utxos it would require that the commitment proves that utxos are not shared, i.e proof of non-set membership; there is no obvious (to me) way to do that, so it remains an open question.

###Other issues

• Using two bots on one Joinmarket wallet it completely unsupported by the existing code: it will tend to lead to address reuse, especially if the bots are rather active; it may also be unsafe in ways not considered, so to state the obvious: don't do it! As you can see, this is not just an economic problem but a functional/privacy one too.

• DOS and maliciousness: note that the behaviour described here is different from, but related to, the more general problem of counterparties simply not completing the protocol. In 0.1, this was addressed only with "recovery" code: if one party does not finish, pick up another one. The assumption is that there will always be enough honest Makers around, which may not be perfectly true but seems to be sufficient in practice. In 0.2 this problem is at least somewhat magnified, since the recovery process perforce must use up another commitment. The extra steps above for the Taker will not prevent this entirely, but will still make the situation strictly better rather than worse.