# Timestamp-to-Block Number Mapper

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

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

`timestamp`

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

A binary search tree, specifically a balanced binary tree like the Red-Black Tree.

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

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

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.

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

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

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.

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

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.

The following Typescript code can be used to convert the MMR into a format optimized for binary search.

type ArguablyFullBlockHeader = { blockNumber: number, timestamp: number, stateRoot: string, parentHash: string };

type TransformedBlockHeader = { blockNumber: number, timestamp: number };

type Hash<T> = {

value: string;

preimage: T;

}

const originalMMRValues: Hash<ArguablyFullBlockHeader>[] = [

{

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<TransformedBlockHeader>[] = [];

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;

}

To begin our binary search, we first find the middle element of

**.**`reindexedMMRValues`

const middleIndex = reindexedMMRValues.length / 2; // 12 / 2 = 6

Next, check the timestamp of the middle element against the queried timestamp to determine which half to search next.

if (reindexedMMRValues[middleIndex].preimage.timestamp > 1460) {

// Search left half

} else {

// Search right half

}

Given

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

Divide the left half's length by 2 to find its middle.

const newMiddleIndex = middleIndex / 2; // 6 / 2 = 3

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

if (reindexedMMRValues[newMiddleIndex].preimage.timestamp > 1460) {

// Search left half

} else {

// Search right half

}

Given

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

const nextMiddleIndex = (middleIndex + reindexedMMRValues.length) / 2; // 4 / 2 = 2

if (reindexedMMRValues[nextMiddleIndex].preimage.timestamp > 1460) {

// Search left half

} else {

// Search right half

}

Given

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

Divide the left half's length by two once again.

const finalMiddleIndex = nextMiddleIndex / 2; // 1 / 2 = 0

if (reindexedMMRValues[finalMiddleIndex].preimage.timestamp > 1460) {

// Search left half

} else {

// Search right half

}

Given

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

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`

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.Some chains can produce multiple blocks with identical timestamps. Read more about this edge case here.

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,

};

}

}

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.

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 modified 4mo ago