Smaran means “remembering” in Sanskrit, which is pretty much the whole job.
When Alice texts Bob on WhatsApp, her phone asks the server for Bob’s encryption key. A compromised server could hand her a fake key and quietly read everything. Key transparency guards against this by keeping every key in a public log. But a lot of security questions are about the past: which key did Bob have when Alice sent that message in March? To answer honestly, the server has to show Bob’s whole key history for that period and prove it didn’t skip or change anything.
Blockchains have the same problem. If you want your Ethereum account’s history for 2024, today you mostly take a website’s word for it.
The usual way to prove these answers is one proof per version. Ask about a longer stretch of time and the proof grows with it. With Smaran, it doesn’t: the proof is the same small size whether you ask about one week or the last ten years.
Pick a start and an end version.
In our experiments, Smaran gets 5.7× the query throughput of CONIKS and OPTIKS for key transparency, and up to 589× the throughput of Merkle trees, Verkle trees, and Cauchyproofs on 2.6 million Ethereum blocks from 2024.
Abstract
Time-travel queries ask what data looked like at a past time or over an interval. Modern databases support time-travel queries, but this support is insufficient for applications that cannot trust the query server, such as secure messaging and decentralized applications, where clients need proofs that the returned results are correct. Existing approaches either require aggregating evidence from multiple auditors, incur per-step proof costs that scale linearly with history length, or impose massive storage and communication costs.
In this paper, we introduce Smaran, an authenticated data structure that enables servers to answer time-travel queries efficiently with a constant number of fixed-size proofs, independent of the query range. Smaran achieves this through a novel integration of segment trees with vector commitments, sidestepping scalability challenges as history grows via a hierarchical architecture, and avoiding redundancy by introducing versioned vector commitments.