Time complexity of accesing contract storage

[gorbak25]

Our contracts currently need to have the entire contract storage as an in memory map. This map is currently generated inefficiently by iterating over each key in the contract state tree. This means that after we have looked up a contract in O(log(N)) we then iterate over the whole tree in O(N) which will be to slow for production use (Ethereum currently has many milion contracts in their trees).

We have two ways of solving this issue:

1. We can solve the issue easily by implementing a wrapper or functions for accessing a particular sub-tree of a merkle patricia tree(https://github.com/aeternity/elixir-merkle-patricia-tree/issues/17). This wrapper will need to implement the Enumerable protocol and function exactly as a map.

2. We can look if we can refactor our current code in a way which avoids generating the contract storage. For instance if listing the contents of the storage is not required then all we need to do is to directly access the required keys in the tree.

Personally I would prefer method 1 as it would easier to debug contracts later(we would have access to the entire storage in the interactive shell) and wouldn't require much code refactoring here.

• [ ] Solve the time complexity issue.
• [ ] Tests for the solution.
• [ ] Implement stress tests for the tries - for instance create and do a lookup in a tree containing 100k entries

[cytadela8]

I would sat we should:

1. Check if epoch also has one big tree for contract data without subtrees (this is a potential compatibility issue)
2. Implement a get_all_with_prefix function in our elixir-merkle-patricia-tree lib that will iterate only over proper part of tree and return a map. This should be simpler to creating some wrapper implementing Enumerable protocol.
3. Write tests for the new get_all_with_prefix function

We should not create stress tests for that in any near future probably. There are many more important (and much, much easier) tests to write.

[gorbak25]

@cytadela8 Epoch stores the contract storage in the same tree(https://github.com/aeternity/protocol/blob/epoch-v0.16.0/serializations.md#contract) as all contracts.

[cytadela8]

I don't trust docs. Especially old ones ;) We should investigate deeper and check if it hasn't changed in current version. If it has, then this issue might not be worth solving.