Discussion: Alternative models/implementations for liquidation auction state

[dorranh]

Porting over the relevant bits of an offline conversation to facilitate further thoughts.

cc @utdemir @gkaracha @purcell

Problem:

The current liquidation auction implementation has to do a lot of bookkeeping, keeping track of the auction queue, completed auctions (as a doubly-linked list), the current auction, and all of the slices at auction for a given burrow (also as a double-linked list). The issue with all of this bookkeeping is that it is a bit error-prone to implement since we have to do a lot of manual wrangling of linked list pointers, etc.

Discussion:

In the preliminary work in #131, I've started separating out the linked list logic for burrow slices into its own module to make it easier to test. This also allows liquidationAuction.ml to focus on interacting with the linked lists at a higher level instead of managing their pointers. One of the challenges with this approach is that due to the lack of generics in Ligo, we will end up with two very similar-looking doubly-linked list modules: one for slices and one for auctions. @utdemir suggested an alternative approach (A) where we use "raw" ptrs in the linked list module instead of making them specific to root_ptr or leaf_ptr and provide a thin interface to make them work with either auctions or slices.

Another question is whether the burrow slice list is actually necessary. Most of the current design is driven by requirements for efficient lookups to answer queries such as "does this burrow have any slices in a completed auction?" Specifically, we use the burrow_slices list in the implementation of LiquidationAuction.is_burrow_done_with_liquidations, which is used in burrow entrypoints to block certain operations can be performed on a burrow if it has slices which need to be touched.

An alternative to the approach (A) above could be to remove the burrow_slices list entirely and instead keep a list of the completed auctions associated with each burrow. This would then require changing the behavior of Checker, making a burrow owner wait for all completed liquidation auctions in which its burrow has slices to be cleaned up before being able to access blocked operations like mint_kit. It might* also slightly reduce the cost of touching slices since we only have to update the list when we complete an auction or touch the very last slice. However, in our discussions we were not sure whether this change in behavior would have adverse effects on Checker as a whole.

[gkaracha]

A thought: (a) since we merged #113 we no longer produce empty liquidation slices (or, I hope we don't! :sweat_smile:), and (b) my understanding of ref_split_rec says that if the next slice fit we would include it in the next auction, so splitting also never leaves us with empty slices (cc @utdemir). From (a) and (b) I gather that there should never be empty slices anywhere, which makes me think that:

burrow.collateral_at_auction = 0    iff    the burrow has no slices unprocessed.        (1)

Indeed, the burrow.collateral_at_auction field only increases when a burrow is marked for liquidation (burrow_request_liquidation) and decreases when a slice comes back, either from a cancellation (burrow_return_slice_from_auction) or from processing the slice (burrow_return_kit_from_auction).

All this sounds pretty fragile and subtle to me, but my thought is that via (1) we can just check the collateral_at_auction field and get rid of the list of slices referring to a burrow altogether. Any thoughts on this?

Edit: in retrospect, this thought doesn't work; it tells us efficiently if we have slices at auctions or not, but not if we have slices at completed auctions or not. That's what we really want to do efficiently (we don't want to make burrows totally unusable if they have slices in liquidations - if owners re-collateralize them the should still be able to use them).

[dorranh]

@gkaracha I actually had also thought about this but wasn't sure whether or not to bring it up :sweat_smile:. I think that would work as well, though it does feel a little more brittle than the list approach. Along these lines we could also even potentially do a counter in the burrow state.

Edit: Actually, I don't think a counter would work given how we split slices (unless we update the counter when we split the slices)

[gkaracha]

@dorranh Actually, now that I think about it, we are both probably a little wrong here. What we check at the moment is not if burrows have slices in auctions, but whether the burrows have slices in completed auctions. That's what we need to be able to check efficiently.

[dorranh]

Ah very true @gkaracha, updated the issue text to reflect that.