Harmonic quanta: DEX order matching that generates no change

Published in

flatus vocis

11 min readJul 17, 2018

One of the snags in atomic swaps is that if you place, say, 1 BTC on sale, and a counterparty takes 0.3 BTC, then the remaining 0.7 BTC would be sent to a change address in your wallet — but this would render the remainder of your order unspendable until it is at least a few blocks deep in the chain, which would make quite a mess if you want to liquidate the entire order quickly. Now while it would be simple enough to solve this by splitting your coins into small amounts at many addresses in your wallet, this would still create change for at least one of your addresses, which means that you would not generally be able to sell all your coins in one go. Worse still, it would create additional complexities in the order book, as it would have to continually check for change and reduce order sizes by any change generated. Because of all these drawbacks, I thought I’d try a little trick to generate no change whatsoever.

Let’s start on the simple end of the problem, with a straightforward story in BDD. The story describes the behaviour of a script that Block DX may run in order to correctly determine quanta for tick size and transaction input size.

##Runs on each trader’s instance of Block DX (if they don’t run it, then they generate change, effectively DOSing themselves)
##Splits coins into equal tiny amounts per input
##Uses an amount per input, “x”, which functions as a minimum transaction size and is (a) above the dust threshold of the coin, and (b) harmonic with (specifically, a standardised divisor of) a calculated tick size, “y”, for the market.
##Sends the remainder from the splitting tx to a separate trade-fee-paying address
##Makes sure the total balance in fee-paying addresses is ≥ the maximum trade fee (0.2%) a trader would pay if (s)he sold all coins
##Ensures that tick sizes and minimum transaction sizes do not require re-running this script when changing to a new coin pair.Given
 Block DX autoconfig script has run on a wallet integrated to Block DX, so that the wallet has:
 — addresses (recorded in .conf) from which it pays trade fees
 — addresses (recorded in .conf) from which it swaps coinsWhen
 Block DX launches
And
 Either (a)
 	All trade-fee-paying addresses hold < 0.2% of the wallet
 	balance
 Or (b)
	 Any input in any wallet holds over x coinsThen
 When (a)
 	Reserve 0.2% of the total coins in trade-fee-paying 
	addresses
 When (b)
 	Create a tx that consumes all current inputs (excluding 
	trade-fee-paying addresses) that do not hold exactly x 
	coins, and create outputs of exactly x coins each
 And
 	Send any remaining coins as change to a trade-fee-paying 
	address

Determining “x” and “y”

To determine x and y in the above script, several size-thresholds will be considered in turn: the dust threshold, the tick size, the minimum order size, and maximum price precision. Following this, the discussion will proceed through stages to a specification of x and y in the above script. The intention is to quantise certain critical minimum sizes at standardised levels above the dust threshold, in such a way that they are always factors or divisors of one another. If order sizes may only be whole quanta of some minimum order size, and if changes in price may only be whole quanta of some minimum tick size, then it is possible to split inputs into sizes that will always result in whole inputs being consumed in a trade.

1. Handling Dust

A very small trade may spend a single input at the value of x. In order to avoid creating unspendable transactions, x must always be above a coin’s dust threshold, or else at least one side of the transaction will be unspendable and the swap will cease to be atomic.

The most valuable coin on Block DX is Bitcoin. Hence, for every trade, it can be expected to be the coin with the smallest units of currency traded. All else being equal, it is thus reasonable to assume that it is the most likely coin to hit its dust threshold.

The worst case scenario for this design would be in cases of a sudden stratospheric rise in price unaccompanied by the usual lowering of the dust threshold. For example, assume Bitcoin goes to $200k and its dust threshold is not lowered; as per current Core dust rules, a dust threshold of 546 Satoshis (for non-segwit transactions) would then equal $10.92.

(Note: this figure shall be used throughout this blog post as a nominal shorthand for “dust threshold.” However, if a bail-in transaction consumes both a fee input and a trading input, the dust threshold would be somewhat higher, and a real implementation would need to accommodate this. Whatever the actual dust threshold, it need only be the lowest dust threshold for any atomic swap transaction, since in swap transactions that use more than one standard-sized input, the transaction amount increases to a greater degree than the dust threshold increases.)

In such a scenario, the total transaction value for a Bitcoin transaction would have to be > $10.92.

For Block DX, this transaction value would include:

the value of a matched order
the trade fee (in cases where the fee system includes fee txs in the bail-in tx itself)
the network fee

To generate no change, orders would have to be in regular multiples of some value >$10.92, and the smallest permissible change in price would have to be harmonic with this value (for example, if a sell order of $10.92 worth of BTC fetches 0.5 BLOCK, then the smallest change in price must be at least $10.92, or else a quantum smaller than $10.92 would be required in a trade — for, say, 0.51 BLOCK — and this would thus generate dust.)

How might fee transactions affect the scenario? Well, the largest proportion of a trade that could be charged as a trade fee is currently 0.2%, for takers. For a $200k Bitcoin, a single trade at the dust threshold would incur a trade fee of $0.02184. In an implementation where fees are paid in separate transactions from swap transactions, this would impose a significant limitation on the minimum trade size, as the fee would have to be >$10.92.

Assuming that, instead of independent fee transactions, a protocol that spends trade fees as an output of the bail-in tx is implemented, then only the total value of the transaction would be significant. This is obviously advantageous to the scalability of the solution across sudden changes of coins’ value — a phenomenon perhaps uniquely frequent in crypto.

As such,

in an atomic swap, the minimum bail-in transaction amount shall be >546 Satoshis,
trade fees shall be one output of a multi-output bail-in tx, spendable upon revelation of the swap’s secret;
its total output (i.e. including the trade fee) shall be returned to the user upon nlocktime maturation, or else in some circumstances, traders will pay a fee when no trade completes. (In terms of antispam and anti-DOS incentives, this is acceptable because it would not be necessary to charge malicious parties a trade fee if, instead, their coins get locked up until nlocktime maturation, as the opportunity cost of capital lockup is far more significant than a fee. For background on this assumption, see this post.)

2. Tick size and maximum price precision

One “tick” on an exchange is the minimum amount that the price of a given coin in a currency pair may increase or decrease. “Price precision” is the number of decimal places permitted in an order. It should correspond to tick size and, in traditional designs, should have an explicit rounding logic so that when, for a given trade, a calculation of (coin A @ price y ) / (coin B @ price z) generates a value of either coin extending beyond the maximum price precision, the number will be rounded up or down to some value that falls within the bounds of price precision permitted. Of course, in this post, we are aiming at a non-traditional design with the convenient property of eliminating the need for rounding.

Tick size and maximum price precision are useful for:

eliminating tiny, trivial orders (a kind of spam).
eliminating trivial competition when traders (usually bots) place a minimally better-priced order (e.g. a difference of 0.000001 BTC) in front of their competitors. This activity does not stimulate demand because minimally better-priced orders do not create a significant increase in incentive to take an order. Hence, it produces a minimal increase in trading volume at a high bandwidth cost for the order system, and it gives bots an unfair advantage over human traders.
avoiding the dust threshold.
avoiding rounding errors by specifying either bounds of precision, or in our case, by precisely harmonising quanta in both coins so that traded amounts never need to be rounded.
avoiding creating change (and confirmation times) by using tick amounts that are always multiples of wallets’ input sizes.

3. Cryptoeconomics

Nothing in this spec need be enforced by network protocol, because all logic reduces to counterparties’ order book rules and no party stands to be penalised except those whose quantisation scripts do not conform with those of the rest of the network. If a trader uses different rules, then either (a) the trader will end up with change, or (b) other traders will not parse orders as valid, since the offending party’s orders will involve coins with fewer confirmations than the threshold set by other traders.

The only check required in this system is that traders should conduct a UTXO check on coins prior to updating an order on their order books, which is already implemented in Block DX.

4. High level strategy

Rounding errors and change can be eradicated by using minimum transaction amounts and tick sizes with carefully-chosen divisors that correspond to coins’ input amounts.
Furthermore, by adopting, across all coins, standard minimum transaction amounts and tick sizes that have many common divisors, where each input size in any coin’s wallet will always be a divisor (simple example: 1, 2, 3, 4, 6, and 8 are divisors of 24, 36, and 72), not only will all trades on a given coin pair generate no change, but when a trader switches to a new coin pair, (s)he need not re-run the above input script for different values of x and y.

5. Specification to determine x and y

The minimum transaction amount shall determine x.
For a given coin, its minimum transaction amount shall be defined as either 0.36*10^n or 0.72*10^n, whichever is the next number higher than its dust threshold, where n is the number of decimal places counted little-endian up to the last nonzero digit of the lowest dust threshold.
(For example, if the dust threshold is 546 sats, then n is 3 and the minimum transaction amount will be 720 sats.)
Tick size determines y.
For a given coin pair, one tick shall be defined by the lowest common multiple of their minimum transaction amounts. Tick size shall be denominated in the least valuable coin of the coin pair, while the most valuable coin shall be termed the “base currency” henceforth.
(For example, if coin A’s minimum transaction amount is 720 sats and coinB’s is 3600, then their market’s tick size shall be 3600 sats, denominated in whichever is the least valuable coin.)
(UX note: base currency in this calculation is independent of the user’s choice of base currency, which may be inverted at will.)
For a given coin pair, maximum price precision shall be defined by y, as in (2) above. In other words, not only shall prices increase or decrease by the tick size, but no order’s price may be smaller than one whole unit of the tick size.
For a given coin pair, the input size shall equal x, the minimum transaction amount, as in (1) above. Input size will thus differ from coin to coin, but in all cases, inputs will be exact divisors of y.

To combine the above into an example, if Bitcoin’s minimum transaction amount is 546 Satoshis and the Blocknet’s is 0.00002000 BLOCK, then for the BLOCK:BTC currency pair:

The next good choice of divisor is 0.00000720 for BTC and 0.00003600 for BLOCK.
Their lowest common multiple is 0.00003600.
Exchange rate shall now vary by a tick size of 0.00003600 BLOCK:BTC
All transaction amounts (and of course orders too) shall be multiples of 0.00000720 BTC or 0.00003600 BLOCK. Due to the tick size, every 0.00000720 BTC input will always be equal to a certain number of whole BLOCK inputs.

6. Why this ensures zero change

From the preceding section, the higher-valued coin will always have inputs exactly proportioned to the market’s maximum price precision, y.
The lower-valued coin will always increase or decrease in value relative to the higher-priced coin in increments of their lowest common multiple, y.
(For example, if 50 BLOCK inputs buy 1 BTC input, and then the price increases by one tick (0.00003600), then 49 BLOCK inputs buy 1 BTC input.)

The result: one input of the higher-valued coin will always buy some number of whole inputs of the lower-valued coin.

7. Novel points worth noting

If price increases enormously, so that, for example, 1 BLOCK input buys 1 BTC input, then a further increase or decrease in price would result in one tick doubling or halving the input:input ratio. As such, this design has the novel property of decreasing price resolution (the size of the smallest increase in price in dollar terms) as the lowest common multiple increases in real-world value.
This will not be problematic outside of the most garish cases of poor coin maintenance, however. As a lower-priced coin increases in value, its fee and dust thresholds ought to be adjusted down so that micropayments remain feasible and users do not inadvertently find that their transactions do not get accepted into a block and their coins are stuck. This adjustment, then, would cause the tick size and minimum transaction size in Block DX to return to a normal level, where a “smooth” or near-continuous variation in price is experienced.
In exchange for a variable price resolution, this solution offers Block DX the ability to create zero change for all trades. I believe this is a desirable compromise.
Note that this system is independent of network fees and network congestion. Changing network fees will have further effects on users’ incentives to trade.

8. Weaknesses

Currently, the principal weakness of this design is that it has not been turned into mathematics and tested. Until it is implemented, there is a chance that this idea is a mere flatus vocis and I am confused.

A secondary weakness is the need for wallets to be aware of coins’ prices (specifically, which coin is the more valuable one) in order for the script to run. This adds complexity and may lengthen setup time somewhat.

A further weakness is that if, at any point, different wallets run differing versions of this script, then it is possible that they could end up with incommensurable xs or ys, which would generate change.

Finally, transactions that consume many inputs are more expensive than single-input transactions. This will not affect the calculation of input size though, because a single-input bail-in transaction will have a low cost, and multi-input transactions will have higher amounts with only a nominally higher cost. As such, this drawback is limited only to increasing the network fee for trades.