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.

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.

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.

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;
}

Procedure

Step 1: Find the Middle Element

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

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.

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.

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.

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

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

Step 6: Determine the Next Search Direction

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.

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

Step 8: Determine the Final Search Direction

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.

Typescript implementation of the algorithm

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