Supplying Hints to Trove operations

All Trove operations that modify the collateralization ratio require insertion or reinsertion into the SortedTroves list. To optimize gas costs and computational complexity during insertion, two hints can be provided.

A hint is the address of a Trove that is close to the correct insert position in the sorted list. Trove operations use two hint arguments: _lowerHint, which refers to nextId, and _upperHint, which refers to prevId—the two adjacent nodes that are (or would become) neighbors of the Trove being operated on. This approach ensures resilience against changes in neighboring Troves before the transaction is processed.

The effectiveness of a hint significantly reduces gas costs by minimizing the list traversal required. The SortedList:findInsertPosition(...) function, called during Trove operations, first checks if _prevId is valid (with a larger LACR than the Trove being inserted) and descends the list from there. If unsuccessful, it checks _nextId (with a smaller LACR) and ascends from there.

To generate useful hints, the HintHelpers::getApproxHint(...) function randomly selects Troves and returns one closest to the target position for insertion. Mathematically, with numTrials = k * sqrt(n), where n is the list size, the function's gas cost is typically O(sqrt(n)) when k >= 10. This function also accepts a random seed _inputRandomSeed to potentially yield different results across calls, improving approximation accuracy over successive attempts.

Trove Operation without a Hint

1. User initiates a Trove operation in their browser.

2. The operation is called with _lowerHint = _upperHint = userAddress.

3. Gas cost worst-case scenario: O(n), where n is the size of the SortedTroves list.

Trove Operation with Hints

1. User initiates a Trove operation in their browser.

2. The frontend calculates a new collateralization ratio locally based on collateral and/or debt changes.

3. Calls HintHelpers::getApproxHint(...) with the calculated ratio, receiving a Trove address close to the correct insertion position.

4. Calls SortedTroves::findInsertPosition(...) with the approximate hint (_prevId and _nextId) and the new ratio.

5. Passes the exact neighbors (_nextId as _lowerHint and _prevId as _upperHint) to the Trove operation.

6. Gas cost: Steps 2-4 are gas-free, and step 5 is O(1).

Using hints makes Trove operations cheaper for users, albeit with a slightly longer completion time due to the need to await results from JSON-RPC requests to Infura, unless the frontend operator runs a full node.