[Scalability Design Document] Design document and plan to test SMT scalability

[Olshansk]

Objective

Put together a design document and a plan to determine the scalability, efficiency and required improvements we need to make to the SMT to make v1 as scalable as possible.

Goals

• Establish the limits of our current SMT (read, write, storage)
• Determine the limits for leaf sizes to accommodate things like websockets
• Explore alternative key-value stores to badgerdb and compare insert/retrieval speeds
• Investigate the potential benefits of extending the prefix trie from a binary tree to a k-ary tree
• Understand the implications of proof size on data availability costs and estimate our costs

Deliverable

NOTE: The deliverables below are just a starting point

A design document / plan that'll address the following in different steps:

• Benchmarking data on the current SMT's insert/retrieval speeds and proof sizes. For example:
  - Can we insert 0.5/1/10 million leaves in 10/60/200 seconds?
  - What are the retrieval speeds depending on the tree size?
• A report on the feasible leaf sizes for different protocols.
  - If we plan to support larger unhashed values (e.g. for websockets), is there a limit on the leaf size?
  - Do we need to split it into multiple smaller leaves as data is streamed?
• Comparative analysis of different key-value stores alongside badgerdb, focusing on insert/retrieval speeds.
  - Could/should we add adapters for leveldb, gorocksdb, boltdb or others and rerun the benchmarks above?
• Research and consideration if we should look into implementing k-ary support instead of just binary support in this tree?
• Detailed breakdown of proof sizes and strategies to map this onto data availability costs.
  - How big are proofs for a tree of 0.5/1/10 million leaves?
  - How long should our sessions be based on expected volume per servicer per session?
  - What will the data availability cost on Celestia or other DA layers?
  d-js.github.io/mermaid/) diagrams

---

Creator: @Olshansk
Co-Owners: @h5law

[h5law]

Issues that are relavent to this:

• [Enhancement] Research, Benchmark and Implement k-ary trie types #14
• [Testing] Enhance overall testing in the repo #9

Potentially also (regarding optimising for bulk inserts?)

• [Enhancement] Integrate the DeepSubTrie for the SM(S)T #11

[Olshansk]

Capturing offline discussion...

Focus on benchmarking and understand the cost (time, insert, read, proof size, DA cost, etc...) of the current state of the tree and use that as a starting point to prioritize future features.