Supplying Hints to Vault operations

All Vault 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 Vault that is close to the correct insert position in the sorted list. Vault 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 Vault being operated on. This approach ensures resilience against changes in neighboring Vaults 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 Vault operations, first checks if _prevId is valid (with a larger LACR than the Vault 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 Vaults 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.

Vault Operation without a Hint

1. User initiates a Vault 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.

Vault Operation with Hints

1. User initiates a Vault 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 Vault 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 Vault operation.

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

Using hints makes Vault 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.