# Timestamp to Block Mapper ## 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.

Cryptographic linkage between blocks

## **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`**. {% hint style="info" %} **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. {% endhint %} ## **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. ```typescript type ArguablyFullBlockHeader = { blockNumber: number, timestamp: number, stateRoot: string, parentHash: string }; type TransformedBlockHeader = { blockNumber: number, timestamp: number }; type Hash = { value: string; preimage: T; } const originalMMRValues: Hash[] = [ { value: "0x...", preimage: { blockNumber: 1000, timestamp: 1500100900, stateRoot: "0x...", parentHash: "0x ...", } }, { value: "0x...", preimage: { blockNumber: 999, timestamp: 1500100800, stateRoot: "0x...", parentHash: "0x ...", } }, { value: "0x...", preimage: { blockNumber: 998, timestamp: 1500100700, stateRoot: "0x...", parentHash: "0x ...", } }, { value: "0x...", preimage: { blockNumber: 1020, timestamp: 1500101600, stateRoot: "0x...", parentHash: "0x ...", } }, { value: "0x...", preimage: { blockNumber: 1019, timestamp: 1500101500, stateRoot: "0x...", parentHash: "0x ...", } } ]; const reindexedMMRValues: Hash[] = []; let lastBlockNumberAppended = 0; function appendToReindexedMMR(indexInOriginalMMR: number) { const value = originalMMRValues[indexInOriginalMMR]?.preimage; if(!value) throw new Error("Non existing value"); const isAppendedValueMoreRecent = value.blockNumber > lastBlockNumberAppended; if(!isAppendedValueMoreRecent) throw new Error("Only more recent blocks can be appended"); if(lastBlockNumberAppended !== 0) { const delta = value.blockNumber - lastBlockNumberAppended; if (delta !== 1) throw new Error("Blocks have to be appended one by one"); } reindexedMMRValues.push({ preimage: { blockNumber: value.blockNumber, timestamp: value.timestamp }, value: "0xthehash" }); lastBlockNumberAppended = value.blockNumber; } ``` ### Procedure #### **Step 1: Find the Middle Element** To begin our binary search, we first find the middle element of **`reindexedMMRValues`**. ```typescript const middleIndex = reindexedMMRValues.length / 2; // 12 / 2 = 6 ``` #### **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. ```typescript if (reindexedMMRValues[middleIndex].preimage.timestamp > 1460) { // Search left half } else { // Search right half } ``` 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. ```typescript const newMiddleIndex = middleIndex / 2; // 6 / 2 = 3 ``` #### **Step 4: Determine the Next Search Direction** Again, compare the new middle element's timestamp to our queried value. ```tsx if (reindexedMMRValues[newMiddleIndex].preimage.timestamp > 1460) { // Search left half } else { // Search right half } ``` Given **`1300 > 1460`** is false, we search the right half. #### **Step 5: Find the Middle Element of the Right Half** ```typescript const nextMiddleIndex = (middleIndex + reindexedMMRValues.length) / 2; // 4 / 2 = 2 ``` #### **Step 6: Determine the Next Search Direction** ```typescript if (reindexedMMRValues[nextMiddleIndex].preimage.timestamp > 1460) { // Search left half } else { // Search right half } ``` 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. ```tsx const finalMiddleIndex = nextMiddleIndex / 2; // 1 / 2 = 0 ``` #### **Step 8: Determine the Final Search Direction** ```tsx if (reindexedMMRValues[finalMiddleIndex].preimage.timestamp > 1460) { // Search left half } else { // Search right half } ``` 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](/herodotus-docs/protocol-design/timestamp-to-block-number-mapper/edge-cases.md). ## Typescript implementation of the algorithm ```typescript interface Data { timestamp: number; blockId: number; } interface QueryResult extends Data { index: number; size: number; } class TimestampsToBlockNumberMapper { private data: Data[] = []; insert(data: Data) { this.data.push(data); } query(timestamp: number): QueryResult | null { let left = 0; let right = this.data.length; while (left < right) { const mid = Math.floor((left + right) / 2); if (timestamp >= this.data[mid].timestamp) { left = mid + 1; } else { right = mid; } } if (left == 0) return null; return { ...this.data[left - 1], index: left - 1, size: this.data.length, }; } } ``` ## **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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.herodotus.dev/herodotus-docs/protocol-design/timestamp-to-block-number-mapper.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.