This page explains the architecture of a helper tool that will be deployed along side Herodotus’ deployment on Starknet in September/October.
We want to create a data structure that stores pairs of (timestamp, blockId) and is able to find the closest block to a given timestamp really quickly.
Imagine an example scenario where you want to know an L1 block number given a timestamp.
The role of this util is to always return the block on the left side of the queried timestamp or fail in case an exception has occurred.
This utility has to be implemented as a smart contract deployed on Starknet.
Of course we don’t want to store it in plain array of tuples (block_number, timestamp) in the state as it would require storing a lot of data.
Also searching it linearly is not feasible, because that would mean that if query on dataset of size 1,000 takes n steps, then increasing size to 1,000,000 would change the steps required to 1000n! So a smarter solution should be used.
We have considered two solutions for the problem mentioned above, however we decided to go with the second solution which is classical binary search.