AsSequentialSet Manual Review Findings

ASS-01M: Improper Sequential Set Shift Operation

Type	Severity	Location
Logical Fault		AsSequentialSet.sol:L79-L87

Description:

The AsSequentialSet::shift operation will break the sequential nature of the set as it will replace the first element with the last element of the set and then pop the first element from the end of the array, thereby breaking its order.

Example:

Copy
75/**
76 * @dev Removes the first element from the sequential set.
77 * @param q The sequential set.
78 */
79function shift(Set storage q) internal {
80    if (q.data.length == 0) {
81        revert EmptySet();
82    }
83    delete q.index[q.data[0]];
84    q.data[0] = q.data[q.data.length - 1];
85    q.index[q.data[0]] = 1;
86    q.data.pop();
87}

Recommendation:

We advise this trait to be re-evaluated, as the set is no longer sequential via these operations.

Alleviation (59b75fbee1d8f3dee807c928f18be41c58b904e1):

The Astrolab DAO team evaluated this exhibit and clarified that the "Sequential" keyword is meant to refer to memory allocation rather than how the elements are ordered. The team proceeded to rename the library as AsIterableSet to better reflect this fact, addressing any confusion that the exhibit arose from.

ASS-02M: Inexistent Prevention of Duplicate Elements

Type	Severity	Location
Logical Fault		AsSequentialSet.sol:L37, L94, L111

Description:

The AsSequentialSet is inherently incompatible with duplicate entries due to its index system and would cause a fatal corruption of the dataset if any such entry is added.

Impact:

The AsSequentialSet as presently utilized will prevent this misbehaviour from manifesting, however, it is crucial that the duplicate entry limitation is enforced at the library level to avoid this behaviour surfacing as part of future development efforts.

Example:

Copy
32/**
33 * @dev Adds an element to the end of the sequential set.
34 * @param q The sequential set.
35 * @param o The element to be added.
36 */
37function push(Set storage q, bytes32 o) internal {
38    q.data.push(o);
39    q.index[o] = uint32(q.data.length);
40}

Recommendation:

We advise the code to prevent duplicate entries by ensuring that the q.index of an entry being added is 0.

Alleviation (59b75fbee1):

While the AsIterableSet::push and AsIterableSet::insert functions have been updated to prevent duplicates, the AsIterableSet::unshift function continues to permit them rendering this exhibit partially alleviated.

Alleviation (efbeab6478):

A require check was introduced at the top of the AsIterableSet::unshift function that disallows duplicate entries correctly, rendering this exhibit fully alleviated.

ASS-03M: Invalid Sequential Set Shift Operation

Type	Severity	Location
Logical Fault		AsSequentialSet.sol:L83-L86

Description:

If the length of the set is 1, the AsSequentialSet::shift operation will retain a non-zero q.index for the entry being removed even though it is no longer present in the array.

Impact:

When the last element of the array is shifted, the element will have a non-zero index even though it is no longer present in the set which is invalid and would cause AsSequentialSet::has evaluations to yield true after other elements are placed as well as incorrect behaviour if anyone attempts to remove it.

Example:

Copy
75/**
76 * @dev Removes the first element from the sequential set.
77 * @param q The sequential set.
78 */
79function shift(Set storage q) internal {
80    if (q.data.length == 0) {
81        revert EmptySet();
82    }
83    delete q.index[q.data[0]];
84    q.data[0] = q.data[q.data.length - 1];
85    q.index[q.data[0]] = 1;
86    q.data.pop();
87}

Recommendation:

We advise the code to instead delete the q.index of the last remaining element and simply pop it if the q.data.length value is 1, ensuring that the entries are correctly updated.

Alleviation (59b75fbee1d8f3dee807c928f18be41c58b904e1):

Our recommendation was adhered to, deleting the index of the last element (i.e. the only one in the array s.data[0]) and issuing a pop operation to the s.data array.

ASS-04M: Invalid Sequential Set Unshift Operation

Type	Severity	Location
Logical Fault		AsSequentialSet.sol:L98-L100

Description:

The AsSequentialSet::unshift function will overwrite the last element of the array if the q.data.length is non-zero and will also not update its index, corrupting the sequential set.

Impact:

Whenever an element is unshifted and the array is not empty, the last entry of the set will be removed from the system while its index will yield a non-zero entry thereby causing AsSequentialSet::has evaluations to yield true as well as incorrect behaviour if anyone attempts to remove it.

Example:

Copy
89/**
90 * @dev Adds an element to the beginning of the sequential set.
91 * @param q The sequential set.
92 * @param o The element to be added.
93 */
94function unshift(Set storage q, bytes32 o) internal {
95    if (q.data.length == 0) {
96        q.data.push(o);
97    } else {
98        q.data[q.data.length - 1] = q.data[0];
99        q.index[q.data[0]] = uint32(q.data.length);
100        q.data[0] = o;
101    }
102    q.index[o] = 1;
103}

Recommendation:

We advise the code to instead push to the q.data array and perform the referenced statements afterwards, ensuring that no data is overwritten from the sequential set and that all indexes are correct.

To note, this would also break the order of the sequential set as specified in a separate exhibit and an alternative approach should be utilized if the order is expected to remain the same.

Alleviation (59b75fbee1):

While the code was refactored to push and perform the relevant index updates, the s.index[o] assignment of 1 was relocated within the else block of the AsIterableSet::unshift function which causes an AsIterableSet::unshift operation on an empty s.data structure to not update the index of the element added.

We advise the s.index[0] update to be relocated outside the if-else block as it was in the original implementation, ensuring that the index of the unshifted o element is correctly maintained under all scenarios.

Alleviation (efbeab6478):

The q.index assignment has been relocated outside the if-else clause per the original implementation, addressing this exhibit in full.