CAP: 0004
Title: Improved Rounding for Cross Offer
Author: Jonathan Jove
Status: Final
Created: 2018-09-17
Discussion: (hackerone)
Protocol version: 10
As of protocol version 9, crossing offers can lead to unbounded relative rounding error and can even leave the book in a crossed state. We propose a new algorithm to resolve these issues.
As of protocol version 9, crossing offers can lead to unbounded relative rounding error and can even leave the book in a crossed state. We propose a new algorithm to resolve these issues. This algorithm will prevent unbounded relative rounding error by adding an error threshold, and will prevent the book becoming crossed by guaranteeing that the less valuable offer must always be removed from the book. The new algorithm also guarantees that any given offer can only suffer a single adverse rounding event by rounding in favor of the offer with more total value (which, equivalently, means the offer which remains in the book).
In what follows, quantities expressed like "100 stroop X" mean 100 times the minimum representable quantity of the asset X. Consider the following situation:
- In transaction 1, account A creates an offer selling 100 stroop X at a price of 3 Y / 2 X.
- In transaction 2, account B creates an offer selling 10 stroop Y at a price of 1 X / 2 Y.
Offer B executes against offer A, but it is impossible to execute the entire offer at the price of 3 Y / 2 X. The protocol uses a rounding algorithm to determine how this situation, and other situations like it, should be handled. As of protocol version 9, 10 stroop Y is exchanged for 6 stroop X meaning that the trade actually executes at a price of 5 Y / 3 X. The relative error in the price is over 11% when viewed as a price in Y / X, and is 10% when viewed as a price in X / Y. This situation is bad, but it is not nearly as bad as it can be: the rounding algorithm as of protocol version 9 actually has unbounded relative error. Consider, for illustration, the following worse situation:
- In transaction 1, account A creates an offer selling 1 stroop X at a price of 1 Y / 50,000 X.
- In transaction 2, account B creates an offer selling 100 Y at a price of 1 X / 1 Y.
As of protocol version 9, 1 stroop Y is exchanged for 1 stroop X meaning that the trade actually executes at a price of 1 Y / 1 X. The relative error in the price is 4999900% when viewed as a price in Y / X, and is 99.998% when viewed as a price in X / Y.
There is still another issue with the rounding algorithm as of protocol version 9. Whenever offers cross, at least one of the offers must execute entirely in order to avoid a crossed book. There are situations, however, where the rounding algorithm as of protocol version 9 will allow the book to remain crossed. Consider the following situation:
- In transaction 1, account A creates an offer selling 100 X at a price of 10 Y / 1 X.
- In transaction 2, account B creates an offer selling 1 stroop Y at a price of 1 X / 10 Y.
As of protocol version 9, nothing is exchanged and the book remains crossed.
We propose a new rounding algorithm that resolves the above issues. The algorithm proceeds through three phases. First, the total value associated with each offer must be computed. Second, rounding is conducted in such a manner that the price never becomes less favorable for the offer with more total value. Third, the offer which initially had less total value is removed from the book regardless of whether it has been executed entirely.
In order to compute the total value associated with an offer, we must choose what this value will be denominated in. This choice is arbitrary, and we elected to use the selling asset of the offer which was already in the book. We define the total value associated with an offer to be the value of the goods on offer in terms of the selling asset of the offer, rescaled by the denominator of the price of the offer which was already in the book.
The manner in which the rounding is conducted is the central aspect of this proposal. The rounding algorithm guarantees that the price never becomes less favorable for the offer with more total value. Since the offer with less total value is always removed from the book, this guarantees that a single offer never suffers adverse rounding more than once. The rounding algorithm is also price aware and attempts to minimize errors by rounding in the less valuable asset. In order to prevent unbounded relative error during rounding, we introduce a new error threshold. If the relative rounding error exceeds the error threshold, nothing is exchanged.
The offer which initially had less total value is removed from the book regardless of whether it has been executed entirely, so it is guaranteed that the book never remains crossed. When the book is no longer crossed, whichever offer ultimately remained in the book is adjusted such that it can be executed entirely. This guarantees that, regardless of rounding and error thresholding, it is always possible to execute against an offer in the book by submitting an offer with more total value. It is possible that an offer cannot be adjusted to any offer that can be executed entirely, in which case that offer is removed from the book.
There is an additional complication with regard to the error threshold in path payment. For path payment, the error threshold is applied asymmetrically in the sense that the price will never become more than 1% less favorable but could become arbitrarily more favorable for the offer which was already in the book. This is sensible as path payment has a max send parameter which determines the worst overall price that should be accepted.
The technical details of implementing the above are subtle and difficult to discuss in the absence of working code. Please refer to the description and implementation of exchangeV10.
A variety of other proposals were considered, among them:
This algorithm had three phases. First, it would determine which offer should remain in the book (for example using the same algorithm as described in Specification). Second, the error induced by rounding up and rounding down would be calculated. Third, the rounding would be performed stochastically such that the expected rounding error was 0. There were several disadvantages to this proposal:
- Requires a source of randomness in the ledger that could not be exploited by validators
- The limit price on any offer could be violated in both directions with unbounded relative error
- Rounding errors average out over time but individuals could still be effected
This proposal focused on restructuring the offer book rather than improving the rounding algorithm. The idea was to split each market into many separate market segments distinguished by the lot size and the base asset (the asset used to express the lot size). The price of an offer would then be the quantity of the non-base asset that you are willing to exchange for lot size of the base asset. This forced the price to be an integer and guaranteed that crossing offers would always execute without any rounding. The advantages of this solution are that rounding never occurs and that each individual market segment is never crossed. There were several disadvantages to this proposal:
- Trading is much more complicated since determining the best price requires looking at every market segment
- Path payment is much more complicated since it needs to process not just every asset but every market segment of every asset
- Significant API changes required
This proposal will change the rounding behavior of offers. If any pre-signed transactions depended on the precise outcome of cross offer either through ManageOffer or PathPayment, it is possible that such a transaction will now fail.
As of protocol version 10, every offer in the book must be immediately executable in full. For more information on this topic, refer to CAP-0003. That proposal notes that offers which are not IEIF will be removed when upgrading to protocol version 10. As part of this process, offers will also be adjusted such that they can be executed entirely as described above. Analogous to what is mentioned in the Specification, offers which cannot be adjusted such that they can be executed entirely will be removed from the book during the upgrade.
Test cases for the new functionality were included in the implementation.
Merged as of stellar-core commit c3c8fd2c95eae9daa8aab324d9ef3e07047aacc9.