search

movementlabsxyz / movement

The Movement Network is a Move-based L2 on Ethereum.
Apache License 2.0
84 stars 68 forks source link

ROC-1 High Time Complexity in num_nodes Function Leading to Potential DOS Vulnerability #324

Closed SA124 closed 3 months ago

SA124 commented 3 months ago

ROC-1 High Time Complexity in num_nodes Function Leading to Potential DOS Vulnerability Severity: Minor Discovery Methods: Manual Review Status: Pending Auditor: Movebit Topic: Suzuka-only custom components

Code Location: protocol-units/storage/jelly-move/src/rocksdb.rs#214-222 Descriptions: The function num_nodes has a high time complexity due to its implementation, which requires iterating through all records in RocksDB.

Screenshot 2024-08-08 at 12 52 16 PM

This function iterates over all records in the nodes_cf column family to count the number of nodes. The time complexity is proportional to the number of records, which can be extremely high for large datasets. In local testing, counting 20,000,000 nodes took approximately 30.5 seconds, whereas using rocksdb.estimate-num-keys took only 13.9 microseconds.

Suggestion: To reduce the time complexity and mitigate the risk of DOS attacks, it is recommended to use rocksdb.estimate-num-keys, which provides an estimated count of the keys in the database much more efficiently.

l-monninger commented 3 months ago

We do not use this custom JMT implementation directly anymore, but I do believe it is the same in Aptos JMT. Perhaps Move Bit wants to take credit for this PR against Aptos.

What does RocksDB use for estimations of cardinality btw? Presumably some HyperLogLog heuristic.

l-monninger commented 3 months ago

But, just FYI, the expectation is that $n$ here will be rather small.

jlguochn commented 3 months ago

Our audit focused on the JMT library, which is not currently in use within the project. Although this library does not pose an immediate security risk to the project, we document potential risks to assist in mitigating future issues. For Minor and information issues, while they may not have a direct impact on security, they highlight deviations from best practices that can be addressed during development. During implementation, the project team is free to make their own considerations.

rocksdb.estimate-num-keys estimates the number of keys in the database by analyzing the statistical information and index data maintained by the database itself.

To estimate the order of magnitude of n, we based our calculation on a tenth of the number of Ethereum Unique Addresses from Etherscan .

l-monninger commented 3 months ago

Oh, no, you're correct. I thought this was only counting inner nodes. But, that's not the case. Regardless, no longer relevant.