[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:

• [x] 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:

• 14

• 9

Potentially also (regarding optimising for bulk inserts?)

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