Timestamp to Block Mapper
The Timestamp to Block Mapper facilitates the mapping of block numbers to their corresponding timestamps.
Overview
The Timestamp to Block Mapper provides a simple mechanism to retrieve a Layer 1 or Layer 2 block number given a timestamp
.
Deployment Environment Constraints
The utility is designed to be a smart contract which is deployed on an L2 such as Starknet or zkSync.
For efficiency, data should not be stored using plain arrays of (block_number, timestamp)
, as this consumes a significant amount of storage. Additionally, linear searching is deemed ineffective: a dataset growth from 1,000 to 1,000,000 would increase query steps from n
to 1000n
.
Possible Approaches to the Problem
Red-Black Tree
A binary search tree, specifically a balanced binary tree like the Red-Black Tree.
Benefits
Enables data insertion and closest block searches in O(log n) time. For perspective, operations on a tree with 1,000 elements might take 0.01s, but increasing it to 1,000,000 only doubles the time, and reaching 1,000,000,000 elements is projected to take 0.03s.
Offers flexibility by accepting data in any order, self-arranging for quick block queries. It can easily remove specific timestamps in O(log n) or limit the data by storing only the last N elements.
Drawbacks
The frequent need for on-chain storage or numerous accesses if only the root is stored.
The demand for tree rebalancing during writes, risking a complete on-chain accumulator root recomputation.
Binary Search
An alternate approach could be conducting a binary search on an off-chain list. The root of the MMR that commits to the list would be stored on-chain.
Benefits
Ensures constant insertion times irrespective of tree size and retains an O(log n) query complexity.
Requires data to be inserted in ascending order.
Doesn't support random element removal (except for the first and last) if O(log n) complexity is to be maintained.
Drawbacks
Data must be inserted in ascending timestamp order.
Cannot easily remove random elements while preserving O(log n) complexity, unless they're the first or last elements.
Original Data Source: HeadersStore
Herodotus utilizes an on-chain MMR dedicated to storing only validated Ethereum block headers. The contract overseeing this operation is termed the "HeadersStore.” The HeadersStore contract is responsible for managing the MMR.
Features
On-Chain Accessibility
After a block header is added to the HeadersStore, a L2 smart contract can retrieve it. This retrieval is facilitated by verifying an inclusion proof against the MMR's root which is found in the HeadersStore.
Ordering Limitation
Despite its utility, the MMR does not ensure a specific order of its elements. This absence of order can make binary search operations challenging.
Understanding the MMR's Block Number Ordering
Consider the MMR, which has indexed block numbers:
block number | x | x-1 | x-2 | x-3 | x-4 | x-5 | z>x | z-1 |
---|---|---|---|---|---|---|---|---|
index in the MMR | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
In this structure:
The block number
z
represents a recently synchronized Ethereum block hash with Starknet, allowing Starknet applications to access up-to-date data. Given this,z > x
.
Implication: The primary construction of the MMR doesn't maintain a consistently ascending order for the entire dataset it commits. As a result, this dataset cannot be directly used with binary search methods. Preprocessing would be required to place the data in a unique and consistent order suitable for binary search.
Remapping the Original MMR for Binary Search
The following Typescript code can be used to convert the MMR into a format optimized for binary search.
Procedure
Step 1: Find the Middle Element
To begin our binary search, we first find the middle element of reindexedMMRValues
.
Step 2: Determine the Search Direction
Next, check the timestamp of the middle element against the queried timestamp to determine which half to search next.
Given 1599 > 1460
is true, we search the left half.
Step 3: Find the Middle Element of the Left Half
Divide the left half's length by 2 to find its middle.
Step 4: Determine the Next Search Direction
Again, compare the new middle element's timestamp to our queried value.
Given 1300 > 1460
is false, we search the right half.
Step 5: Find the Middle Element of the Right Half
Step 6: Determine the Next Search Direction
Given 1501 > 1460
is true, we search the left half.
Step 7: Find the Middle Element of the Left Half
Divide the left half's length by two once again.
Step 8: Determine the Final Search Direction
Given 1300 > 1460
is false, we search the right half.
Outcome
After these steps, we've effectively performed a binary search through the reindexedMMRValues
array, narrowing down the location of the queried timestamp to its exact position or its nearest neighbours.
Specification
Since the algorithm is deterministic, we are able to predict what data points it will access. By supplying the L2 contracts with MMR inclusion proofs and their associated preimages, specified as (block_number, timestamp) tuples, we effectively enable on-chain searching. This method requires verification of only specific MMR inclusion proofs, maxing out at log(n)
verifications in the most demanding scenarios. Further optimization is possible through the use of batched inclusion proofs.
Edge Cases
Some chains can produce multiple blocks with identical timestamps. Read more about this edge case here.
Typescript implementation of the algorithm
Summary
Remapping the Original MMR for Binary Search optimizes resource utilization on Layer 2s by significantly reducing the reliance on the most costly resource, state, while efficiently leveraging the more affordable resource, computation. Layer 2s, such as Starknet, are particularly well suited to benefit from this approach.
Future Work
Our team is exploring the possibility of generating the timestamped ordered set off-chain. We plan to offer support for this functionality soon. If you think this would be useful, we encourage you to contact us.
Last updated