# 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**

**Trove Operation without a Hint**

User initiates a Trove operation in their browser.

The operation is called with

`_lowerHint = _upperHint = userAddress`

.Gas cost worst-case scenario:

`O(n)`

, where`n`

is the size of the`SortedTroves`

list.

**Trove Operation with Hints**

**Trove Operation with Hints**

User initiates a Trove operation in their browser.

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

Calls

`HintHelpers::getApproxHint(...)`

with the calculated ratio, receiving a Trove address close to the correct insertion position.Calls

`SortedTroves::findInsertPosition(...)`

with the approximate hint (`_prevId`

and`_nextId`

) and the new ratio.Passes the exact neighbors (

`_nextId`

as`_lowerHint`

and`_prevId`

as`_upperHint`

) to the Trove operation.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.

Last updated