StateNetwork Database

[ScottyPoi]

State Network Database

TODO

Implement / Modify design for Contract Storage

Summary

The disc space necessary to store state_network content in a key-value database will grow exponentially compared to history_network content. A database full of serialized Container<leaf, proof> will inevitably store duplicate proof hashes.

However the same volume of content can be available through instead storing and updating a set of sparse state tries, or more specifically - the necessary data to reconstruct, update, and generate proofs from a Trie.

Rationale

As a state_network node, our radius covers a range of account addresses. We aim to provide a view of recent state history for those accounts. Currently aiming to serve requests for the most recent 256 state roots.

By storing and updating sparse state tries for each of the 256 most recent state_roots, the node can increase its radius to include more accounts. The capacity to serve state_network content will grow at a rate higher than the actual size of the database, due to the sharing of proof hashes.

Design

TrieLevel

• Implementation of ethereumjs/trie interface DB
• Has attribute this.db that extends AbstractLevel (memory-level / browser-level)
• Construct a TrieLevel with
  • new TrieLevel({ db?: AbstractLevel )}
• Construct a Trie with
  • Trie.create({ db: this.db })
• Update a Trie like

      const trie = Trie.create({ this.db })
      trie.createFromProof(proof)

• Store a Trie like:
  • this.db = Trie.database().db

Trie

EthereumJS/Trie

• Trie.create({ db })
  • Builds a trie object from a database
• Trie.prototype.createFromProof(proof)
  • Will create or update a sparse Trie from proof data
• Trie.prototype.createProof(leaf)
  • Generates a list of witness hashes

StateDB

• Database Manager for StateProtocol
  • StateProtocol.db: StateDB
• Maintains mapping of state_root to TrieLevel
  • this.sublevels: Map<state_root, TrieLevel>
• Keeps Set of known addresses in radius
  • this.knownAddresses: Set<Address>
• Keeps ordered index of known state_roots
  • this.stateRootIndex: StateRootIndex
• Methods to update TrieLevels
• Methods to extract leaf data / proofs from TrieLevels
• Pruning

StateRootIndex

• Set of graph search / sort algorithms
• Maintains an ordered index of state roots updated from sparse trie data
• Can make determinations about the relative order / age of state_roots, when the exact sequence cannot be known.

Purpose:

• Our tries will only contain leafs for accounts that changed in that state transition
  • And only if we've seen that specific gossip
• The sequence of two state tries cannot be determined unless those tries happen to share at least one account.
  • Meaning accounts that have changed more than once in the last 256 blocks ( ~ 1 hr )

Use:

• TBD
• Maybe just for pruning, maybe useful for actual functionality.
• Enables pruning by age (depth) in addition to radius.

Protocol

StateProtocol store and retrieve methods will interact with the StateDB methods, instead of the DBManager class used by HistoryNetwork.