Dynamic `maxDepositPerUser` can stale Fenwick tree state
The protocol uses a Fenwick Tree to efficiently track user time-locked LP deposits, where each update and prefix sum operation is bounded by a configurable maxDepositPerUser.
The protocol uses a Fenwick Tree to efficiently track user time-locked LP deposits, where each update and prefix sum operation is bounded by a configurable maxDepositPerUser.
However, the implementation assumes the tree is consistently populated up to the current max, which fails in two critical scenarios:
- When the max is increased after previously being lower, the new nodes are used in queries (prefix sums) but were never updated for the past deposits.
- When the max is decreased and if the max is increased again later, these stale values corrupt prefix sums.
This results in incomplete or stale sums, which breaks the accuracy of unlock logic and deposit tracking.
The Fenwick tree uses a binary indexing system where each node covers a specific range:
Node 1 (0001) = Sum of elements [1]
Node 2 (0010) = Sum of elements [1-2]
Node 3 (0011) = Sum of elements [3]
Node 4 (0100) = Sum of elements [1-4]
Node 5 (0101) = Sum of elements [5]
Node 6 (0110) = Sum of elements [5-6]
Node 7 (0111) = Sum of elements [7]
Node 8 (1000) = Sum of elements [1-8]
When maxDepositPerUser changes, consider the following scenarios:
-
Increase from 5 to 8:
- Node 8 should contain sum[1-8].
- But elements [1-5] never propagated up before.
- Result: Node 8 has an incomplete sum.
-
Decrease from 5 to 3 then back to 5:
- Nodes [4-5] retain stale values.
- New deposits don't properly update higher nodes.
- Result: Corrupted prefix sums.
However, this issue's practical impact is mitigated by the protocol's default configuration. The maxDepositPerUser is potentially set to a high value. With a max of high value, users would need to make deposits that fill most of these nodes. This makes the scenario unlikely in normal operations, though still possible if the protocol needs to adjust deposit limits frequently.
Consider ensuring that updating the maxDepositPerUser could lead to a potentially stale Fenwick tree state and ultimately lead to an incorrect unlock amount for users. To ensure prefix sums remain accurate when changing maxDepositPerUser, the protocol should implement a safe handling mechanism when resizing the Fenwick tree.
Report provenance
Published by Pashov Audit Group, with Carlos (Bloqarl) participating as a contractor. The source report states that its fixes review was not fully completed; no final remediation disposition is recorded for this finding. Read the full report.