Description

The update_vote_weight_window_length is responsible for passing in what timestamp ranges the voting checkpoints should use during cast_vote(). The instruction for reading window length uses a binary search algorithm similar to the logic used in checkpoint searches. However, unlike the checkpoint searches, it pushes a new window length the program does not validate for uniqueness in the search criterion. This is a critical invariant required by binary search to ensure determinism (i.e., the same search criteria returns the same value result every time).

If two window lengths can exist for the same timestamp, when reading from the set of (window length, timestamp) tuples, we will receive different values for the same fixed timestamp query depending on the length of the data set. This is strictly because the midpoint may fall on one of those duplicate values; upon adding values, the midpoint shifts to the duplicate, changing the outcome of the returned value.

Consider the following example:

(value, timestamp): [(1,0), (50,1), (100,2), (150,2), (200, 3), (250, 4)]
Search criteria: Less than or equal to timestamp of 2
Return value: 100

If in the next iteration the set increases by a size of one more value, the original midpoint changes, and we will have the following search:

(value, timestamp): [(1,0), (50,1), (100,2), (150,2), (200, 3), (250, 4), (300, 5)]
Search criteria: Less than or equal to timestamp of 2
Return value: 150

Impact

This behavior could result in nondeterministic results for searches against the same timestamp.

Recommendations

Ensure a duplicate timestamp overwrites the existing value or reverts.

Remediation

This issue has been acknowledged by Wormhole Foundation, and a fix was implemented in commit 508585ea↗.