Noncustodial, Decentralized Exchange

I found an overview of assurances and threats for crypto/blockchain, but it’s incomplete.

Returning my focus to one of the key issues of atomic cross-chain exchange for noncustodial, decentralized exchange (aka DEX).

I wrote on this blog:

My guess is the more significant near-term threat (after the posited SegWit attack event) will be centralized exchanges refusing to cash out legacy Bitcoins that have either SegWit lineage or the hodler lacking proof-of-source-of-funds (PoSoF). Non-custodial decentralized exchanges might exist to trade tainted Bitcoin until the miners are fully regulated. Yet I’m not certain if the upcoming non-custodial decentralized exchanges support TierNolan’s automic cross-chain protocol for Bitcoin and the fixes I had proposed to the denial-of-service (jamming) flaw in TierNolan’s protocol. McAfee did mention recently that he thought we were geniuses for creating the protocol, although he may not have been referring to my and @jl777’s contribution to it.

I wrote in my recent blog Bitcoin’s Whiplash Bear Trap:

Decentralized exchanges which can never be banned, are receiving intensive development, c.f. also, also and also.

Afaik, I was in 2014 the original person at BCTalk focusing on the problem with “jamming” (aka DoS) (c.f. also) of interactive protocols such Gmaxwell’s (aka Core/Blockstream) CoinJoin (and subsequent conceptually equivalent interactive, decentralized coin mixing protocols taking on many different names) and jamming for atomic cross-chain exchange employing either TierNolan’s original nLockTime compatible with Satoshi’s legacy protocol or the protocols (including TierNolan’s cut-and-choose) employing the Locktime opcodes added as one of omnibus suite of changes that accompanied SegWit which are incompatible with Satoshi’s immutable legacy protocol.

nLockTime variant protocol

The nLockTime variant requires each of the two parties to sign and exchange a transaction which refunds the respective sending transaction back to the sender (which is locked via nLockTime against acceptance on the blockchain until the future timeout). This is done before each party posts their respective sending transaction to the other party. On timeout failure, the parties can obtain a refund. The sending transactions are conditioned on the hash of a secret known to one party, so when that payee redeems, the secret is revealed (on the blockchain) so that the other party can also redeem. Both redeem scripts in addition to the hashed secret condition, also require (via OP_CHECKSIG) the redeem transaction to be signed by the private key of the redeeming party which is only known to said redeeming party. Thus other than refunds on timeout, only the intended payee can redeem.

CIYAM’s symmetrical Locktime protocol

When both blockchains support Locktime opcodes then the protocol is simplified because no separate refund transactions are needed. On timeout, the sending transactions are redeemable by the senders.

TierNolan’s asymmetrical Locktime cut-and-choose protocol

When only one of the blockchains supports Locktime or nLockTime and the other doesn’t support either (or doesn’t support the non-standard transaction replacement required by the nLockTime protocol), the cut-and-choose protocol proves with probabilistic assurance that hash of a secret private key matches a public key so that the sending transaction on the deficient blockchain can commit to a 2-of-2 OP_CHECKMULTISIG (requiring senders key and said public key) without fear that the other party can refund their forfeitable deposit transaction without releasing the correct private key so the said 2-of-2 multisig can be also be refunded.

My asymmetrical costs jamming objection

All of those protocols have the weakness that one of the parties has to issue a transaction first to the blockchain, so if their counterparty times out, then one of the parties has lost funds due to both transaction fees and the delay of having their UTXO locked up while awaiting the protocol to complete.

The jamming could be repeated over and over again to essentially keep the other party perpetually locked in repeated instances of the protocol that always timeout. I proposed UTXO age threshold whitelist as a partial solution for preventing malevolent actors from recently mixing their coins to hide the lineage of recent jamming, so that such lineage could be blacklisted. Yet that’s problematic because users can’t reliably trust shared blacklists thus have not enough economies-of-scale to make blacklists effective.

Lowering the transaction fees to zero doesn’t resolve the perpetual jamming vulnerability.

This is a serious problem which makes truly decentralized, noncustodial exchange extremely vulnerable to jamming.

My amended solution

I blogged in 2017:

Viable Trustless Cross-chain DEX Protocol

In early 2017, I devised a simplified protocol for truly trustless, decentralized cross-chain trades which removes the jammable race condition. I publish it widely now for the first time (had originally published it to a Pastebin which I think not very many people were aware of). The HTLC escrow requires OP_CHECKLOCKTIMEVERIFY (OP_CLTV) (which was introduced into Bitcoin by SegWit) on every blockchain for the token of the bidders. This protocol can’t be achieved with nLockTime. The ask side of the trade must be on a blockchain (or any form of decentralized ledger) which implements the following protocol. The asker issues an ask offer open to all bidders and this is confirmed by the ledger. The ledger is then able to automate the release of tokens being offered by the asker if a bidder’s transaction is confirmed. Thus the bidder has no risk of the asker jamming the trade by refusing to release the signed transaction.

Multiple bidders may commit to a HTLC on the blockchain for the token they’re offering. Bidders which are not chosen to complete the trade are refunded automatically by the HTLC. The ledger for the ask side selects and commits to one of the bidders. The chosen bidder must release the signed transaction before the ledger for the ask will release the tokens. The bidder can trust the ledger because by definition a decentralized ledger is trustless and always fulfills the protocol.

The bidder could fail to release (and obtain a refund via the HTLC) but this is not the race condition of @‍TierNolan’s protocol, because there’s already a list of alternative bids confirmed on the bidders’ blockchain which the ledger for the ask side can opt to next. The attacker would have to get to the back of the line to re-enter the same attack. Thus if even one of the bidders is honest, then presuming the time lock duration is sufficient to try all the bidders, then the trade will succeed (after some delay) and not be indefinitely jammed.

Also my proposal requires only very little delay to wait on the bidder to release the HTLC solution, thus can cycle through the bids much faster. Also the bidder's funds are locked up for some time before they are refunded so this isn't cost free (time opportunity cost) for the attacker. Also bids in the same block could be prioritized by the ones with the longest refund time, so that time opportunity cost can be ramped up as needed to squelch attacks. This is a clever solution to @‍TierNolan’s ingenuous but flawed concept.

So in my proposed protocol, the bidders had to be on a blockchain that supports Locktime and they would bid with transactions condition on the hash of a secret chosen by each bidder. The asker’s blockchain would automatically commit to these bids (also conditioned on the hash of the secret) one-by-one until the protocol completes with one of the bidders redeeming and releasing their secret so the asker can also redeem on the bidder’s blockchain.

The potential flaw is that the asker can jam the bidders in a way that is indistinguishable from not jamming, by bidding on their own ask. If the bidders are chosen randomly, then the malevolent asker would need to saturate the bids, so this might be too costly unless transaction fees are free. And we would not want the cost to bid to be free for this reason (even if the malevolent actor is not the asker).

Yet transaction fees are a cost on all bidders even if their bid is not the one that is accepted. So this proposal is flawed unless we amend it so that bids are only charged a (significant) fee (e.g. confiscate a deposit) if accepted or timeout. So then jamming always has a significant asymmetric cost on the malevolent actor. This amendment may have been in my original conceptualization and failed to write down all the details of my conceptualization.

If the bidder’s blockchain does not offer free or very low-cost transactions, then the bid offers could be placed on the asker’s blockchain if it does offer free or not very low fees. In this case, the protocol would be slower because cycling through the bidders would require waiting for the bidder’s send transaction to be accepted into the bidder’s blockchain with a timeout. That delay would not be cost-free to a malevolent actor, because timeouts would be charged a fee.

Essentially afaics the difference between my amended solution and what @jl777 was proposing is that the processing of numerous bid offers is performed by the decentralized blockchain, so that no party is charged a fee unless they fail to complete their end of the protocol, because the asker neither can stall the protocol nor dictate which bids are processed first in the case that a protocol does not always charge on timeouts. And the asker pays no fee until the protocol completes.

The only remaining flaw is that sometimes timeouts occur unintentionally thus a fee charged on non-attackers. But that should not happen rarely and the fees should not be egregious.

My proposal requires that one of the blockchains is running this specialized protocol. And it would work best if the other blockchain has an option for free or very low cost transactions along with Locktime. Otherwise the mentioned slower cycling through bids is required. But at least even in this slower mode, my proposal seems to be compatible with legacy Bitcoin, BCH, and BSV. That’s good news.

I will need to do some research to determine if anyone has or is about to implement my proposal or a rough equivalent. If not, I will need to focus on accelerating my programming work!

P.S. readers should note the edits I made to one of my other replies to @zoidsoft.