A decentralized exchange protocol with trustless trade fees *and* atomicity between orders and swaps

I was asked recently to apply myself to the challenge of imagining how a decentralized exchange with a trustless fee system would work. This is what came of it — with a welcome surprise: atomicity between the order system and the settlement (atomic swap) system!

Life in a trustless DEX: congregate with whomever you like; no harm can come of it.

Note: those without the leisure to absorb a dense protocol sketch may gain perspective on the design by skipping to “Rationale for the design” and the sections that follow it.

Background

While Block DX’s features are progressively implemented, its design is subject to an iterative process: insights from developers, the careful weighing of consequences of design decisions, and potential alternative systems are open to be entertained. The whitepaper’s order system design (p.31) has the merits of being reasonably simple to grasp, lacking security scenarios that are especially hard to analyse, and being readily implementable upon our service node infrastructure. It also prevents two perennial evils in p2p systems: spam and DOS attacks, while providing fee functionality of key importance to users: not being charged a fee unless a trade completes (or unless they play foul). However, no system is perfect. Two of its most notable shortcomings are that it has no true atomicity between an order being accepted and an atomic swap commencing, and that service nodes may (at considerable cost to themselves) “charge” users trade fees at times and for outcomes where they ought not be charged. In other words, it would be advantageous if no trust in any party’s good behaviour was required when trade fees are charged (hence, “trustlessness”), and if no trader could abandon a trade prior to settlement without encountering (at the very least) a significant economic deterrent. This design is a first stab at remedying both these imperfections in one fell swoop (in one bleary-but-obsessive all-nighter).

Key

Participants

• a market-maker, who adds liquidity to the order book
• a market-taker, who takes liquidity from the order book
• service nodes, which function to accept fees, and to buy and distribute BLOCK to the Blocknet network. The nature of service nodes may be further explored in the Blocknet whitepaper.

High-level description

This protocol features one secret generated by the maker and used in a commit-and-reveal pattern for three atomic swaps (well, strictly, one atomic swap and two contingent payments, but if you’re familiar with an atomic swap then that will suffice): one between the maker and a service node, another between the taker and (probably a different) service node, and a third between maker and taker.

Possibly unfamiliar terms

• native coin: whichever coin a maker or taker is offering.
• tx: transaction
• txid: transaction ID
• atomic swap: a trade of one cryptocurrency or token for another, done in such a way that either the swap occurs in its entirety, or it doesn’t occur at all, so that no party can lose coins. In this respect it is indivisible, hence “atomic.” Those unfamiliar with how an atomic swap works can read an introduction in the Blocknet whitepaper (pp. 21–22).
• bail-in tx: a party’s commitment to an atomic swap
• fee bail-in tx: a party’s commitment to pay a trade fee. When reading, take care not to confuse this with a bail-in tx.

Notation

• Major steps of the protocol are in Arabic numerals.
• Lowercase letters serve to further specify the major steps
• Roman numerals give reasons or actor-motivations behind the current step.

Protocol sketch

1. Maker maintains a list of many service nodes’ addresses which function to receive fees in various native coins (or alternatively, contacts a service node for its address).
2. Maker creates a secret.
3. Maker creates and broadcasts a fee bail-in tx which further functions as an order message:
   a) To the value of 0.05% of its order, in its native coin
   b) Spendable only by a given service node
   c) Spendable only upon revelation of the maker’s secret
   d) The secret isn’t revealed until the coins are swapped, so that the service node can’t spend the maker’s fee unless the trade occurs.
4. Taker maintains a list of many service nodes’ addresses which function to receive fees in various native coins (or: it contacts a service node to get its address).
5. Taker observes a desirable order on the order book, and notes its hash of its secret.
6. Taker creates but does not broadcast its fee bail-in tx:
   a) This is a swap of its native coin for BLOCK at the value of 0.2% of the intended trade size; however, the BLOCK sent by a service node will be consumed entirely by the network fee for this transaction.
   b) Spendable upon revelation of the maker’s secret
   ~ i) This is because the taker is going to commit to the trade by broadcasting its bail-in tx; hence, its fee must only spendable if the maker reveals its secret, thus also committing to the swap, or else the taker might pay a fee when the maker abandons the trade.
   c) Spendable by only the service node
7. Taker creates order acceptance message for a maker’s order, including in the message:
   a) The amount of the maker’s order to consume
   b) The fee bail-in tx
   ~ i) This is included because the taker should not broadcast its fee bail-in tx unless the maker matches its order, or else its fee would be held up until nlocktime maturation even if no trade were to take place.
   ~ ii) However, if the maker matches its order, then unless the maker possesses the bail-in tx, the taker may abandon the trade without penalty. As such, the taker must send it to the maker in order that it may be broadcast even if the taker abandons the trade.
   ~ iii) The maker may now maliciously broadcast it (virtuous motive: to ensure that the taker pays the fee) — but the tx will only be spendable if the maker reveals its own secret too — and then its own fee will be spendable, so the attack is not very attractive.
   ~ iv) If the maker broadcasts the taker’s fee bail-in tx and then abandons the trade, the taker may claim the fee in a refund tx after nlocktime matures (minor penalty).
8. Order matching: the maker matches its order to the taker’s by creating and broadcasting its bail-in tx (and, if necessary, the taker’s fee bail-in tx too).
   a) Spendable upon revelation of the maker’s secret
   b) Spendable only by the taker
   ~ i) In order to prove to the network that it’s the maker and not some other entity, the maker signs its bail-in tx with the private key corresponding to the coins it offered when it created an order.
   ~ ii) This signed bail-in tx also proves to the network that the maker’s order is matched, so they can update their books. For more information about how this system handles state changes in a self-sovereign way, see p. 29 of the whitepaper.
   ~ iii) Note how this matching event is simultaneously a commitment to settlement, because to match orders is identical with broadcasting a bail-in tx. Thus, an order’s state change from open to accepted is intrinsic to the swap. Additionally, both parties’ trade fees are now committed too. Thus, ordering and settlement are atomic.
9. Taker observes maker’s bail-in tx and broadcasts its own bail-in tx.
   a) Spendable upon revelation of the maker’s secret
   b) Spendable only by the maker
10. Maker spends the taker’s bail-in tx, revealing the secret.
11. Taker observes the revelation of the maker’s secret and spends the maker’s bail-in tx.
12. Maker’s service node observes the revelation of the maker’s secret and spends the maker’s fee bail-in tx
13. Taker’s service node observes the revelation of the maker’s secret and spends the taker’s fee bail-in tx.
14. Maker’s service node observes the spending of the taker’s bail-in tx and broadcasts its fee bail-in tx in BLOCK:
    a) Spendable only upon revelation of the maker’s secret
    b) Spendable only by the maker
    c) Upon nlocktime maturity, may be refunded to the service node, but is nonetheless entirely consumed by the network fee
    d) May voluntarily be replaced by a simple transaction that spends the BLOCK to the network, since its outcome is equivalent.
    ~ i) Broadcasting of the BLOCK fee entails the service node permanently losing BLOCK, since it will either be spent to the network or unspent in the tx forever. As such, it is motivated to delay broadcasting its fee tx until the swap is completed.
    ~ ii) Revelation of the maker’s secret enables the service node to claim its fee in native coins, and thus that it has no risk of losing income by broadcasting its BLOCK fee tx.
    ~ iii) Failure to broadcast the BLOCK fee will lead to blacklisting of the service node
    ~ iv) Failure to spend the correct amount of BLOCK will lead to blacklisting of the service node
15. Taker’s service node observes the spending of the taker’s bail-in tx and broadcasts its fee bail-in tx in BLOCK:
    a) As in step 13.

Rationale for the design

Fairness of fee logic

• The maker may cancel its order for free prior to matching its order with a taker (step 8), by recovering its fee at nlocktime maturation. This is trustless because the service node cannot spend the fee until the maker reveals its secret. Additionally, the fee still functions as a hashcash-style antispam measure, since real funds are committed to each order.
• Unlike the collateral-based fee system, after matching, fees do not act to penalise the abandonment of a trade; rather, abandonment causes the trade capital itself to be locked up until nlocktime maturation. This is a more painful (better) penalty than imposing mere trade fees, since it embodies an opportunity cost.
• The “gap” between order-acceptance and bail-in tx broadcast no longer exists, removing an intermediate phase which would otherwise have to be penalised when a party abandons a trade.
• Once the bail-in transactions are made, it is no longer possible to penalise only the party who abandons a trade. Rather, both parties have their funds held up until nlocktime maturation. This is identical to scenarios in the collateral-based system in which both parties have broadcast their bail-in transactions, save for the additional (minor) charging of a fee to the offending party. I doubt that this makes much difference to the incentive structure of the swap, since the opportunity cost of having one’s funds locked up is by far the greatest problem — in in such cases it is generally economically optimal to complete a trade and then re-trade back to one’s original coin instead of abandoning the trade, as the market exposure is far shorter.
• Service nodes do not spend BLOCK without guaranteed native coin income.

Reasons to blacklist a service node

Note: augments the blacklist proof here.

• Not broadcasting BLOCK fee bail-in tx
• Not spending enough BLOCK to the network
• Spending the maker’s fee tx without a BLOCK tx being spent (evidence of collusion with maker)
• Not having BLOCK to spend (might just affect its ranking and thus profitability)
• Not responding within the necessary timeframes (might just affect its ranking and thus profitability)

Virtues of the design

1. It leaves the slow business of buying BLOCK to pay trade fees until after the (fast) order matching process, where it can happen alongside settlement.
2. Avoids traders having to pay a fee upfront (i.e. regardless of whether the order never finds a counterparty or their trade never completes).
3. Prevents collusion between service nodes and makers by always spending the BLOCK tx to the network.
4. Adds atomicity between order-acceptance and the atomic swap: the taker requests to accept an order by exposing its bail-in tx to broadcast, and a maker accepts an order by broadcasting its bail-in tx.

Vices of the design

1. Because the fees paid are in proportion to the value of the order posted and not to the amounts swapped, there is no obvious way to support the part-consumption of orders.
2. Order TTL (“time-to-live”) is limited by the nlocktime value of the maker’s fee bail-in tx. This produces a dilemma: either order TTL will be inflexible and short, or there will be long waiting periods before a fee refund is possible: traders who want orders open for a long time must be prepared to wait a long time to get their fees back if they cancel an order.
3. 7.b.iii allows the maker to maliciously hold up the taker’s fee until nlocktime maturation. There is no economic gain to the maker in doing this, and a merely temporary inconvenience to the taker, so this is a minor weakness. Furthermore, this places the taker in the same position as the maker — that of having to pay a fee which is only refundable after nlocktime maturation, so the situation is still equitable even if the maker acts maliciously.
4. BLOCK spent is somewhat arbitrary and is not directly market-determined (BLOCK is still bought at some point prior, so this is still market-related), because service nodes would hold BLOCK and then simply calculate the amount they need to spend, rather than buying it in real time from the market. This needs a good method across the network to determine BLOCK required, and further requires policing.
5. While traders’ fees strictly are trustless, the transactions that spend BLOCK to the network are not. As such the system as a whole is not trustless. I believe that on the current approach, this is a fundamentally unavoidable scenario: to construct this protocol I went through several iterations (quite possibly all of them) and there is always at least one moment in the transition from orders to swaps, or swaps to fees, where trustlessness depends upon two parties revealing something before the other one does — a clearly circular situation. As such, I arranged it so that a policeable entity — a service node — is saddled with the single trust-laden role, moreover one which does not affect the trade, only the network’s remuneration from the trade (and this virtuously incentivises the network to be all the more vigilant in its policing).
6. In step 14, if both the maker fails tp spend the service node’s BLOCK fee tx, and the service node fails to spend it via a refund tx, then the BLOCK will remain unspent in the fee tx forever. This would thus prevent the network from benefitting from the fee. However, due to service nodes being blacklistable for not spending this tx, this outcome will extremely unlikely and this of negligible impact.

Novel properties (not obviously virtues or vices)

1. Service nodes now directly receive fees in native coins, instead of receiving fees via block rewards
2. Service nodes now need to buy BLOCK to swap with native coins. Note that this need not expose service nodes to exchange risk, as (a) in a BLOCK downtrend they can calculate the BLOCK returned in the fee swap by what they’d receive from a market-buy, and (b) in an uptrend they can buy BLOCK in advance and profit from having to swap increasingly less of it as the price increases. Furthermore, they can earn the spread if they scalp and if the network protocol for pricing BLOCK fees assumes a market order.
3. Service nodes now determine how much BLOCK is to be spent in a fee tx.
4. Incentives/disincentives to run a given coin now include earning income in that coin.
5. If a service node and a maker are controlled by the same entity, then the maker’s secret can be passed privately to the service node, who can then spend the native coin without first sending BLOCK. However, this is not a vice:
   a. If no BLOCK is sent, the network can reliably blacklist the service node.
   b. This is easy to police because the network can match BTC received with BLOCK sent in the fee swap by their common secret.

Scope for further enhancements

1. I steered away from the (exciting) prospect of including in a transaction commitments, opcodes, or entire transactions from other blockchains, due to risk of invalid txs and unforeseeable interoperability limitations. Without low-level analysis of the scope for (very) widely interoperable techniques, this direction is difficult to evaluate.
2. I opted for simple crypto along the lines of what is already implemented; considerable advantages may potentially be gained, though, by using state channels to handle fee payments, as they may allow adjustments of the fee if an order is partially consumed.
3. State channels may also solve the order TTL issue, as a channel may stay open for a very long time, or be closed voluntarily, independently of the commit-and-reveal pattern of the main swap.
4. The fee txs are actually “contingent payments” (spendable upon revelation of the secret) rather than atomic swap txs, since service nodes are policed into broadcasting their BLOCK after the secret is already revealed and they’ve claimed their native coins. This warrants revisiting the BLOCK fee txs to see whether the current policing might be replaced with some different crypto (something equivalent to “this BLOCK will automatically be spent if the maker’s fee bail-in tx is spent”).

Arlyn Culwick is a philosopher and technologist, a co-founder of the Blocknet, and an independent researcher in sign action. Flatus Vocis is a repository for spontaneous ideas and brain farts in decentralized p2p design scenarios. Posts are optimised for uberty over certainty, and are intended mainly to bootstrap musement. Chew before ingesting.