helix-onchain / filecoin

Collection of libraries to implement common patterns and standards on the Filecoin Virtual Machine
Other
16 stars 14 forks source link

Update AMT / HAMT libraries to allow for ranged iteration #186

Closed alexytsu closed 1 year ago

alexytsu commented 1 year ago

Currently the only way to iterate through the contents of a HAMT / AMT is via a for_each that explores every node in the tree.

This is prohibitively expensive in gas costs and disallows paginated APIs to be developed on top of these data structures. In particular the motivating use case of enumerating tokens, owners and balances in the FRC53 NFT standard is not feasible without a paginated API. Therefore, enumeration needs to be scoped to a certain predictable set of ranges.

For both the HAMT and AMT the main gas cost comes from expansion of CID -> Nodes during tree traversal. A limit on the number of blocks expanded/explored will put a limit on gas costs.

By specifying a start range and end range for indexes when iterating through AMTs it is possible to limit the number of nodes explored and thus limit the gas costs.

alexytsu commented 1 year ago

POC implementations are found: https://github.com/helix-onchain/filecoin/pull/185 https://github.com/helix-onchain/ref-fvm/pull/1

alexytsu commented 1 year ago

unresolved API question/design decision: should the range of iteration be specified by:

anorth commented 1 year ago

I propose letting the caller decide, by providing both values to a predicate that indicates whether to keep gooing

alexytsu commented 1 year ago

Closed along with https://github.com/filecoin-project/ref-fvm/issues/1514