I think we are both circling around (converging?) to a similar type of solution.

The cut and choose aspect is not requiring any details about bitcoin scripts. The idea is that one side commits to a large number of keypairs, the other side picks a random one and then the original side sends the privkeys to all keypairs except for the chosen one.

Probabilistically as long as the cost of the fee (which is required) must be more than the expected return. Current settings are 1000 keypairs and 1/777 as the fee, so there is about a 13% negative cashflow for anybody that tries to cheat on a large scale. Now whether preventing economically motivated attackers is enough or not, clearly it is a necessary problem to solve completely.

With both sides doing the above, each side has a privkey that can be used. I call it privAm and privBn, for Alice m and Bob n. These privkeys enable proof that you didnt cheat by sneaking in a fake keypair. It cannot be disclosed until after the protocol is past all the possible refund claims and the actual payments as they all hinge on these privkeys. To commit to them, a hash of the privkey is included in the protocol for each side, before any big money is committed.

For now, let us agree that a vandalism oriented attack can tie up other's fees, but allowing the victim to recoup the fee for failed trades is adequate. It is 0.13% of the trade, so for the normal user not a big deal, but this small fee adds up to the friction that makes cheating uneconomical.

The enforcement of fee collection for only the swaps that complete is by requiring the InstantDEX account to proactively spend the fees using both privAm and privBn, which are disclosed in the cases of successful swaps. [there might be some cases where a failed swap also ends up disclosing both privkeys, but not sure if it is even possible. if it is an additional time window would need to be created]. After the time window (probably 24hrs), both bob and alice can recoup their fees. By doing it once per day, there can be a single fee reclaim tx to aggregate all fees from the failed trades. This reduces the bitcoin txfees needed and a user can actually delay for however long they want. Might need to add another secret to the fee reclaim script to prevent the other party from reclaiming, but the high level concept is that if the trade goes through, the fee is paid and if not the fee is reclaimed.

By making it so the fees are not sent until after both sides commit to their set of keypairs, we can identify the attacker. The method is for the field product of the privkeys to be made part of the protocol. We have the privAm * (privkeys other than privA) and the hash(privAm), so given the former two we can verify the hashes match. The privAm is disclosed after it is not a sensitive secret anymore. If cheating was going on, the hashes wont match and the corresponding party immediately punished.

As soon as a failed proof of commitment is detected, this violation can be broadcast to all the nodes, who immediately update reputation score.

With such a realtime feedback, it does not seem likely that an attacker can do any prolonged attack from the same address.

Sybil attacks are reduced in effect dramatically if the nodes all know the historical performance of that account. Zero activity would mean potential attacker. non-zero activity (and by activity I mean fees paid to eliminate any advantage from self-trading) would enable the attacker to start attacking, but after the first failure to disclose, he is blacklisted in realtime.

Similarily attackers who just want to tie up your funds for the deposit or payment (not the fee) it is a different attack. They cant both follow the keypairs commitment protocol and also prevent the trade from completing as in order to prove your commitment, you need to disclose the privAm or privBn.

The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade. But it would rapidly exhaust the utxo the attacker can use in addition to being blacklisted, and losing funds.

I believe the following fee policy solves the incentives issue, especially penalizing the attacker.
Fee policy:
1. When both sides have committed to their set of keypairs, the fee is paid
2. If the trade completes, the fee goes to InstantDEX account
3. If the trade doesnt complete the party that followed the protocol can recover the fee

With the above three rules, there is not even a fee tied up, until both parties have committed. Once committed, both parties will have to complete the protocol or get flagged and I think a penalty of forfeiting the fee is needed to enforce economic unviability for attacks.

pseudo-code for a payment script would be:

if ( elapsedtime < day && privAm disclosed && privBn disclosed )
    InstantDEX claims the fees; // this is the case where trade has been completed
else if ( elapsedtime >= day )
{
    if ( no privAm )
       Bob claims his fee
    else if ( no privBn )
       Alice claims her fee
}

Separately, for all failed trades, the keypairs commitments are verified and any violations detected are broadcast to the network. (Or all the peers can monitor all the other trades)

Any feedback regarding economically motivated attackers is much appreciated.

James