# Timestamp-to-Block Number Mapper

The Timestamp-to-Block Number Mapper facilitates the mapping of block numbers to their corresponding timestamps.

## Overview

The Timestamp-to-Block Number Mapper provides a simple mechanism to retrieve a Layer 1 or Layer 2 block number given a `timestamp`

.

**Deployment Environment Constraints**

**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

, 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 **(block_number, timestamp)**

to **n**

.**1000n**

**Possible Approaches to the Problem**

**Possible Approaches to the Problem**

**Red-Black Tree**

**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**

**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**

**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**

**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**

**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

represents a recently synchronized Ethereum block hash with Starknet, allowing Starknet applications to access up-to-date data. Given this,**z**

.**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**

**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**

**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**

**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

is true, we search the left half.**1599 > 1460**

**Step 3: Find the Middle Element of 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**

**Step 4: Determine the Next Search Direction**

Again, compare the new middle element's timestamp to our queried value.

Given

is false, we search the right half.**1300 > 1460**

**Step 5: Find the Middle Element of the Right Half**

**Step 5: Find the Middle Element of the Right Half**

**Step 6: Determine the Next Search Direction**

**Step 6: Determine the Next Search Direction**

Given

is true, we search the left half.**1501 > 1460**

**Step 7: Find the Middle Element of 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**

**Step 8: Determine the Final Search Direction**

Given

is false, we search the right half.**1300 > 1460**

**Outcome**

**Outcome**

After these steps, we've effectively performed a binary search through the

array, narrowing down the location of the queried timestamp to its exact position or its nearest neighbours.**reindexedMMRValues**

## 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**

**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 se**t** 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